是我当前正在进行的将单链接列表转换为双链接列表的代码。我还没有触摸删除功能。我已经在空列表中插入，列表的末尾和列表的开头显然都在工作。
然而，插入中间的节点似乎无法创建到前一个节点的链接。我插入的调试行似乎显示了具有正确内存地址的n->next和n->prev，但当我进行反向打印时，插入中间的任何节点都会丢失，链接也会消失。在这方面我哪里错了？
以下代码：
#include <iostream>
#include <string>
using namespace std;
// define a node for storage and linking
class node {
public:
string name;
node *next;
node *prev;
};
class linkedList {
public:
linkedList() :top(NULL) {}
bool empty() { return top == NULL; }
node *getTop() { return top; }
node *getEnd() { return end; }
void setTop(node *n) { top = n; }
void setEnd(node *p) { end = p; }
void add(string);
int menu();
void remove(string);
~linkedList();
void reversePrint();
friend ostream& operator << (ostream&, const linkedList&); // default output is in-order print.
private:
node *top;
node *end;
};
void main() {
linkedList l;
cout << l.empty() << endl;
int option = 0;
string s;
bool go = true;
while (go) {
option = l.menu();
switch (option) {
case 1: cout << "enter a name: "; cin >> s; l.add(s); break;
case 2: cout << "enter name to be deleted: "; cin >> s; l.remove(s); break;
case 3: cout << l; break;
//case 4: cout << "can not be done with a singly linked list" << endl;
case 4: l.reversePrint(); break;
case 5: cout << "exiting" << endl; go = false; break;
}
}
system("pause");
}
void linkedList::remove(string s) {
bool found = false;
node *curr = getTop(), *prev = NULL;
while (curr != NULL) {
// match found, delete
if (curr->name == s) {
found = true;
// found at top
if (prev == NULL) {
node *temp = getTop();
setTop(curr->next);
delete(temp);
// found in list - not top
}
else {
prev->next = curr->next;
delete(curr);
}
}
// not found, advance pointers
if (!found) {
prev = curr;
curr = curr->next;
}
// found, exit loop
else curr = NULL;
}
if (found)cout << "Deleted " << s << endl;
else cout << s << " Not Found " << endl;
}
void linkedList::add(string s) {
node *n = new node();
n->name = s;
n->next = NULL;
n->prev = NULL;
// take care of empty list case
if (empty()) {
top = n;
end = n;
// take care of node belongs at beginning case
}
else if (getTop()->name > s) {
n->next = getTop();
n->prev = NULL;
setTop(n);
node *temp;
temp = n->next;
temp->prev = n;
// take care of inorder and end insert
}
else {
// insert in order case
node *curr = getTop(), *prev = curr;
while (curr != NULL) {
if (curr->name > s)break;
prev = curr;
curr = curr->next;
}
if (curr != NULL) { // search found insert point
n->next = curr;
cout << n->name << " " << n << " prev " << prev << " " << prev->name << endl;
n->prev = prev;
prev->next = n;
cout << "n->prev is: " << n->prev << " " << n->prev->name << endl;
cout << "n->next is: " << n->next << " " << n->next->name << endl;
}
// take care of end of list insertion
else if (curr == NULL) {// search did not find insert point
prev->next = n;
n->prev = prev;
cout << "n->prev is: " << n->prev << " " << n->prev->name << endl;
setEnd(n);
}
}
}
ostream& operator << (ostream& os, const linkedList& ll) {
//linkedList x = ll; // put this in and the code blows up - why?
node *n = ll.top;
if (n == NULL)cout << "List is empty." << endl;
else
while (n != NULL) {
os << n->name << endl;
os << n << endl;
if (n->next != NULL) {
os << "next is " << n->next << endl;
}
n = n->next;
}
return os;
}
void linkedList::reversePrint() {
node *n = end;
if (n == NULL)cout << "List is empty." << endl;
else
while (n != NULL) {
//cout << n->name << endl;
cout << "memory address of " << n->name << " is " << n << endl;
if (n->prev != NULL) {
cout << "prev is " << n->prev << endl;
}
n = n->prev;
}
return;
}
// return memory to heap
linkedList::~linkedList() {
cout << "~linkedList called." << endl;
node *curr = getTop(), *del;
while (curr != NULL) {
del = curr;
curr = curr->next;
delete(del);
}
}
int linkedList::menu() {
int choice = 0;
while (choice < 1 || choice > 5) {
cout << "nEnter your choice" << endl;
cout << " 1. Add a name." << endl;
cout << " 2. Delete a name." << endl;
cout << " 3. Show list." << endl;
cout << " 4. Show reverse list. " << endl;
cout << " 5. EXIT " << endl;
cin >> choice;
}
return choice;
}
您没有在插入中间时设置当前的prev，只需执行：
n->next = curr;
curr->prev = n; // <-- this