我正在尝试为我的双向链表类实现一个删除函数。
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
class DblLinkedBag
{
private:
struct node{
string data;
node* next;
node* prev;
}*start=NULL;
int itemCount;
string item;
node *head;
node *tail;
public:
DblLinkedBag();
~DblLinkedBag();
int getCurrentSize();
bool isEmpty();
bool add(string value);
bool remove(string item);
void clear();
bool contains(string target);
int getFrequencyOf();
string retStart();
string getItem();
};
这就是到目前为止删除功能的内容。
bool DblLinkedBag::remove(string value)
{
node* to_remove = head;
while(to_remove && to_remove->data != item)
to_remove = to_remove->next;
// Do the removal if we found it
if(to_remove)
{
// If it was at the head, advance the head to the next item
if(to_remove == head)
head = head->next;
// Remove from the list
if(to_remove->next)
to_remove->next->prev = to_remove->prev;
if(to_remove->prev)
to_remove->prev->next = to_remove->next;
// Free the removed node
delete to_remove;
itemCount--;
return true;
}
return false;
当我尝试运行它时，没有任何反应，它甚至不返回 false。 可能是因为我实现 add 函数的方式吗？这是我的添加函数。
bool DblLinkedBag::add(string value)
{
node* n;
bool add=false;
cout<<itemCount<<endl;
if(itemCount==0)
{
n=new node;
n->data=value;
n->prev=NULL;
head=n;
tail=n;
add=true;
}
if(itemCount>0 && itemCount<7)
{
n= new node;
n->data=value;
n->prev=tail;
tail->next=n;
tail=n;
add=true;
}
itemCount++;
return add;
}
任何帮助将不胜感激。
这就是我调用函数的方式。
void displayBag(int size)
{ DblLinkedBag bag;
cout << "The bag contains " <<size
<< " items:" << endl;
int numberOfEntries = size;
//for (int i = 0; i < numberOfEntries; i++)
// {
// cout <<bagItems[i] << " ";
// } // end for
// cout << endl << endl;
} // end displayBag
void copyConstructorTester()
{
DblLinkedBag bag;
string items[6] = {"zero", "one", "two", "three", "four", "five"};
for (int i = 0; i < 6; i++)
{
cout << "Adding " << items[i] << endl;
bag.add(items[i]);
// bool success = bag.add(items[i]);
//if (!success)
// cout << "Failed to add " << items[i] << " to the bag." << endl;
}
void bagTester()
{
DblLinkedBag bag;
cout << "Testing the Link-Based Bag:" << endl;
cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 1 (true)" << endl;
cout<<"*BAG TESTER*"<<endl;
displayBag(bag.getCurrentSize());
string items[] = {"one", "two", "three", "four", "five", "one"};
cout << "Add 6 items to the bag: " << endl;
for (int i = 0; i < 6; i++)
{
bag.add(items[i]);
} // end for
displayBag(bag.getCurrentSize());
bag.display();
cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 0 (false)" << endl;
cout << "getCurrentSize: returns " << bag.getCurrentSize()
<< "; should be 6" << endl;
cout << "Try to add another entry: add("extra") returns "
<< bag.add("extra") << endl;
cout << "contains("three"): returns " << bag.contains("three")
<< "; should be 1 (true)" << endl;
// cout << "contains("ten"): returns " << bag.contains("ten")
// << "; should be 0 (false)" << endl;
// cout << "getFrequencyOf("one"): returns "
// << bag.getFrequencyOf("one") << " should be 2" << endl;
cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 1 (true)" << endl;
// cout << "getFrequencyOf("one"): returns "
// << bag.getFrequencyOf("one") << " should be 1" << endl;
cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 1 (true)" << endl;
cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 0 (false)" << endl;
// cout << endl;
displayBag(bag.getCurrentSize());
cout << "After clearing the bag, ";
bag.clear();
cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 1 (true)" << endl;
} // end bagTester
int main()
{
copyConstructorTester();
bagTester();
return 0;
} // end main
这就是绘制双向链表以找出节点删除的方法。
Node 1
+----------+------+------+
| Previous | Data | Next |
| -0- | ? | |
+----------+------+------+
^ |
| Node 2 V
+----------+------+------+
| Previous | Data | Next |
+----------+------+------+
^ |
| Node 3 V
+----------+------+------+
| Previous | Data | Next |
| | ? | -0- |
+----------+------+------+
让我们假设以下指针：
Node * node1 = head;
Node * node2(node1->next);
Node * node3(node2->next);
一种可能性是从前面的链接开始：
使节点 3 的先前链接指向节点 1：
node3->previous = node1;
Node 1
+----------+------+------+
| Previous | Data | Next |
| -0- | ? | |
+----------+------+------+
^ ^ |
| | |
+--+ | |
| | Node 2 V
| +------+------+------+
| | Prev | Data | Next |
| +------+------+------+
| |
+---+ |
| Node 3 V
+----------+------+------+
| Previous | Data | Next |
| | ? | -0- |
+----------+------+------+
下一步是使Node 1的Next链接指向节点 3：
node1->next = node3;
Node 1
+----------+------+------+
| Previous | Data | Next |
| -0- | ? | |
+----------+------+------+
^ ^ |
| | |
+--+ | +------+
| | Node 2 |
| +------+------+------+ |
| | Prev | Data | Next | |
| +------+------+------+ |
| | |
| | +-----+
+---+ | |
| Node 3 V V
+----------+------+------+
| Previous | Data | Next |
| | ? | -0- |
+----------+------+------+
在上图中，当您跟踪从Node 1到Node 3和Node 3到Node 1的链接时，您会注意到未访问Node 2。
因此，可以安全地删除Node 2。
最后，删除节点 2
delete node2;
总结：
Node * current = head;
Node * previous = head;
// Find the node
while (current->data != key)
{
previous = current;
current = current->next;
}
// Assume node was found.
Node after = current->next;
// Make previous point to the node after the current.
previous->next = after;
// Make the node after the current node point to the previous.
if (after != NULL)
{
after->previous = previous;
}
// Delete the current node.
delete current;