我正在尝试查看数据结构并实现一个基本的链表。当我运行此代码时，我得到以下输出：
3 4 6
找到并删除了1 个 4 个被找到并删除
3
应该删除 4，但显然不应该删除 1，我想知道我的代码/逻辑中的错误在哪里。
提前感谢任何帮助。
#include <iostream>
using namespace std;
class List {
private:
struct node {
int data;
node * next;
};
node * head;
node * curr;
node * temp;
public:
List();
void addNode(int newData);
void deleteNode(int delData);
void printList();
};
int main() {
List test;
test.addNode(3);
test.addNode(4);
test.addNode(6);
test.printList();
cout << endl << endl;
test.deleteNode(1);
test.deleteNode(4);
cout << endl << endl;
test.printList();
}
List::List(){
head = NULL;
curr = NULL;
temp = NULL;
}
void List::addNode(int newData){
node * n = new node;
n->next = NULL;
n->data = newData;
if (head != NULL) { // List is intact
curr = head; // if List is not empty, make curr equal to the head, and start at the beginning of the list.
while(curr->next != NULL) { // Get to last item on the list
curr = curr->next;
}
curr->next = n; // Use the last item, and point to the new node.
}
else { // empty list
head = n; // new node is the head of the list.
}
}
void List::deleteNode(int delData){
node * n = new node;
temp = head;
curr = head;
if (head != NULL) {
while (curr->next != NULL && curr->data != delData) {
temp = curr;
curr = curr->next;
}
if (curr == NULL) {
cout << delData << " was not found in the listn";
delete n;
}
else {
n = curr;
curr = curr->next;
temp->next = curr;
delete n;
cout << delData << " was found and deletedn";
}
}
}
void List::printList(){
curr = head;
while (curr != NULL) {
cout << curr->data << endl;
curr = curr->next;
}
}
以下行分配一个新节点。
node * n = new node;
正如评论中已经指出的那样，目前尚不清楚deleteNode()为什么要这样做。后续delete n行实际上是删除这个新节点，而不是列表中的节点之一。
我会尝试写deleteNode()这样的东西：
void List::deleteNode(int delData) {
// Empty list
if (!head) return;
// The first node is to be deleted
if (head->data == delData) {
node * old_head = head;
head = head->next;
delete old_head;
return;
}
// A non-first node is to be deleted
for (node * cur = head; cur; cur = cur->next) {
if (cur->next && cur->next->data == delData) {
node * del_node = cur->next;
cur->next = cur->next->next;
delete del_node;
break;
}
}
}
实际上，代码中的问题是条件：
curr-> next !=NULL had to be replaced by curr!= NULL
因为代码在需要停止之前停止一步。
这是您的工作代码：
#include <iostream>
using namespace std;
class List {
private:
struct node {
int data;
node * next;
};
node * head;
node * curr;
node * temp;
public:
List();
void addNode(int newData);
void deleteNode(int delData);
void printList();
};
int main() {
List test;
test.addNode(3);
test.addNode(4);
test.addNode(6);
test.printList();
cout << endl << endl;
test.deleteNode(1);
test.deleteNode(4);
cout << endl << endl;
test.printList();
}
List::List(){
head = NULL;
curr = NULL;
temp = NULL;
}
void List::addNode(int newData){
node * n = new node;
n->next = NULL;
n->data = newData;
if (head != NULL) { // List is intact
curr = head; // if List is not empty, make curr equal to the head, and start at the beginning of the list.
while(curr->next != NULL) { // Get to last item on the list
curr = curr->next;
}
curr->next = n; // Use the last item, and point to the new node.
}
else { // empty list
head = n; // new node is the head of the list.
}
}
void List::deleteNode(int delData){
node * n = new node;
temp = head;
curr = head;
if (head != NULL) {
while (curr!= NULL && curr->data != delData) {
temp = curr;
curr = curr->next;
}
cout<<temp->data<<" ";
if (temp->next == NULL) {
cout << delData << " was not found in the listn";
delete n;
}
else {
n = curr;
curr = curr->next;
temp->next = curr;
delete n;
cout << delData << " was found and deletedn";
}
}
}
void List::printList(){
curr = head;
while (curr != NULL) {
cout << curr->data << endl;
curr = curr->next;
}
}
正如@drescherjm所说，可以跳过额外的分配。 最后的删除节点函数是：
void List::deleteNode(int delData){
node * n ;
temp = head;
curr = head;
if (head != NULL) {
while (curr!= NULL && curr->data != delData) {
temp = curr;
curr = curr->next;
}
cout<<temp->data<<" ";
if (temp->next == NULL) {
cout << delData << " was not found in the listn";
// delete n;
}
else {
n = curr;
curr = curr->next;
temp->next = curr;
delete n;
cout << delData << " was found and deletedn";
}
}
}