c-这段代码几乎适用于所有测试用例，除非要删除的元素是列表末尾的倒数第二个元素

Question

程序用于从双链接列表中删除节点并打印出新列表

除了要删除的元素是列表末尾的倒数第二个元素之外，该代码几乎适用于所有测试用例。当它被给定时，我在我的删除函数中得到了一个分段错误，我只是无法修复，希望得到修复。

#include <stdio.h>
#include <stdlib.h>
//no work
struct node{
int data;
struct node *next;
struct node *prev;
};
struct node *head = NULL;
void display();
void addnode(int x){
struct node *current = (struct node *)malloc(sizeof(struct node));
current->data = x;
current->next = NULL;
current->prev = NULL;
if (head == NULL)
head = current;
else{
struct node *temp;
for (temp = head; temp->next != NULL; temp = temp->next);
temp->next = current;
current->prev = temp;
}
}
void delete(int t){
struct node *temp;
if (head->next == NULL){
if (head->data != t)
printf("Target Element is Not Foundn");
else{
display();
printf("List is Emptyn");
}
}else{
for (temp = head; temp->next != NULL && temp->data != t; temp = temp->next);
if (temp->data == t){
if (temp->next != NULL){
temp->next->next->prev = temp;
temp->next = temp->next->next;
}
}
}
}
void display(){
struct node *temp;
printf("List->");
for (temp = head; temp->next != NULL; temp = temp->next)
printf("%d ", temp->data);
printf("%d->NULLn", temp->data);
}
int main(){
int n, temp;
scanf("%d", &n);
while (n--){
scanf("%d", &temp);
addnode(temp);
}
int t;
scanf("%d", &t);

display();
delete(t);
display();
}

这似乎有一些世界限制，所以让我试着很快把它填满。因为我真的想赢得一些声誉，最后问一大堆我想问的问题。[1] ：https://i.stack.imgur.com/Nke8q.png

Answer 1

当temp指向要删除的节点，并且它是倒数第二个时，则temp->next不为空，而temp->next->next为空，并且您的代码尝试执行temp->next->next->prev = temp;。由于temp->next->next为null，因此使用temp->next->next->prev不起作用。你需要重新思考你的代码在做什么以及为什么。

Answer 2

除了要删除的元素是列表末尾的倒数第二个元素外，代码几乎适用于所有测试用例。

我不同意，原因如下：

delete()函数中存在多个问题。

• Major(您已经知道这一点(：如果列表中有多个1元素，并且为了删除，用户输入了倒数第二个要删除的节点，则会发生分段错误。正因为如此，delete():

  temp->next->next->prev = temp;
  

temp->next->next是NULL，您的代码正试图访问NULL指针。

• Major：如果列表只包含一个元素，并且您将该元素作为要删除的输入，则它将输出-List is Empty，并且具有该值的节点将不会被删除：

  if (head->next == NULL){
  if (head->data != t)
  printf("Target Element is Not Foundn");
  else{
  display();
  printf("List is Emptyn");
  }
  ....
  ....
  

• Major：如果列表中有多个1元素，并且为了删除，用户输入了除最后一个和倒数第二个节点之外的任何要删除的节点，则delete()最终将删除用户输入的节点旁边的节点(应该是删除的(。此外，在这种情况下还存在内存泄漏。

  if (temp->data == t){
  if (temp->next != NULL){
  temp->next->next->prev = temp;
  temp->next = temp->next->next;
  }
  ....
  ....
  

所有语句都在temp->next指针中进行更改，而不是在temp指针中。此外，被删除的节点内存不会在任何地方释放。

• Major：如果列表中有多个1元素，并且为了删除，用户输入了最后一个节点，则不会发生删除，最后一个结点仍将是列表的一部分。正因为如此，delele():

  if (temp->data == t){
  if (temp->next != NULL){
  

如果temp指向最后一个节点，则temp->next将是NULL。

• Minor：如果列表中有多个1元素，并且为了删除，用户输入了列表中不存在的某个节点，则没有输出消息通知用户

display()函数中的问题：

• Major：将NULL传递给display()函数，会出现分割错误。如果您的列表只有一个元素，并且该元素将被删除，则列表将为空，并且当在delete()之后调用display()时，将导致分段错误。这是因为display():

  for (temp = head; temp->next != NULL; temp = temp->next)
  ^^^^^^^^^^
  

如果temp是NULL，则它将尝试访问作为UB的NULL指针。

要删除双链接列表中的节点，需要注意它的上一个和下一个指针。上一个的下一个应重置为其下一个节点，下一个的上一个应重设为其上一个节点。如果它的前一个是NULL，这意味着它在列表中的第一个节点，在这种情况下，将列表的head重置为指向它的下一个节点。

实施：

void delete (int t) {
struct node *temp;
for (temp = head; temp != NULL && temp->data != t; temp = temp->next);
if (temp == NULL) {
printf("Target Element is Not Foundn");
return;
}
if (temp->prev != NULL) {
temp->prev->next = temp->next;
temp->prev = NULL;
}
else {
head = temp->next;
}
if (temp->next != NULL) {
temp->next->prev = temp->prev;
temp->next = NULL;
}
free (temp);
}

还需要修复显示器。应该是这样的：

void display (void) {
struct node *temp;
printf("List->");
for (temp = head; temp != NULL; temp = temp->next)
printf("%d ", temp->data);
printf ("n");
}

Answer 3

要删除cur指向的元素，您需要重定向上一个的指针next和下一个的指示器pred，前提是这些元素存在。使用获取这些元素

node* pred= cur->pred, * next= cur->next;

现在分流

(pred ? pred->next : head)= next;
(next ? next->pred : tail)= pred;

并释放当前元素：

delete cur;