C语言双向链表删除节点异常：调用deleteatPosition(2)误删两个节点

问题描述 #

实现了包含创建、插入、删除操作的C语言双向链表程序，在执行deleteatPosition(&head,2)时出现异常，误删了两个节点。实际输出丢失了节点25，而预期应保留该节点。

原代码 #

#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *pre;
    struct node *next;
};
 void createNode(struct node **head, int data)
{
    struct node *newNode;
    newNode=(struct node*)malloc(sizeof(struct node ));
    newNode->data=data;
    newNode->next=NULL;
    newNode->pre=NULL;
    if(*head==NULL)
    {
        *head=newNode;
        newNode->pre=NULL;
        return;
    }
    else
    {
        struct node *temp=*head;
        while(temp->next!=NULL)
        {
            temp=temp->next;
        }
        temp->next=newNode;
        newNode->pre=temp;
    }
}
void insertatBegin(struct node **head,int data)
{
    
    struct node *newNode;
    newNode=(struct node*)malloc(sizeof(struct node ));
    newNode->data=data;
    newNode->next=*head;
    newNode->pre=NULL;
    if(*head!=NULL)
    {
        (*head)->pre=newNode;
    }
    *head=newNode;
}
void display(struct node *head)
{
    int count =0;
    struct node *temp=head;
    while(temp!=NULL)
    {
        printf("%d\n",temp->data);
        count++;
        temp=temp->next;
    }
    printf("\nno of nodes = %d\n",count);
}
void insertatPosition(struct node **head,int data,int pos)
{
    if(pos==0)
    {
        insertatBegin(head,data);
    }
    else
    {
        struct node *newNode;
    newNode=(struct node*)malloc(sizeof(struct node ));
    newNode->data=data;
    newNode->next=*head;
    newNode->pre=NULL;
    struct node *temp=*head;
    while(--pos)
        {
            temp=temp->next;
        }
        newNode->next=temp->next;
        newNode->pre=temp;
        temp->next=newNode;
    }
}
void deleteatLast(struct node **head)
{
    struct node *temp=*head;
    struct node *temp2;
    while(temp->next!=NULL)
    {
        temp=temp->next;
        
    }
    temp2=temp;
    temp=temp->pre;
    temp->next=NULL;
    free(temp2);
    
    return;
}
void deleteatBegin(struct node **head)
{
    struct node *temp=*head;
    *head=(*head)->next;
    (*head)->pre=NULL;
    free(temp);
    return;
}
void deleteatPosition(struct node **head,int pos)
{
    struct node *temp=*head;
    struct node *before,*after;
    int count =0;
    struct node *temp4=*head;
    while(temp4!=NULL)
    {
        
        count++;
        temp4=temp4->next;
    }
    
    if(pos==0)
    {
        deleteatBegin(head);
        return;
    }
    else if(pos==count-1)
    {
        deleteatLast(head);
        return;
    }
else
{
    while(pos!=0)
    {
        temp=temp->next;
        pos--;
    }
    before=temp->pre;
    after=temp->next;
    if(before != NULL) 
        { 
        before->next=temp->next;
    }
    if(after != NULL) 
        {
        after->pre=temp->pre;
    }
    free(temp);
    return;
}

}
void main()
{
    struct node *head=NULL;
    createNode(&head,10);
    createNode(&head,20);
    createNode(&head,30);
    insertatBegin(&head,100);
    insertatPosition(&head,25,1);
    display(head);
    deleteatPosition(&head,3);
    display(head);
    deleteatPosition(&head,2);
    display(head);
    return;
    
    
}

实际输出 #

100
25
10
20
30

no of nodes = 5
100
25
10
30

no of nodes = 4
100
30

no of nodes = 2

--------------------------------
Process exited after 0.03383 seconds with return value 17
Press any key to continue . . .

预期输出 #

100
25
10
20
30

no of nodes = 5
100
25
10
30

no of nodes = 4
100
25
30

no of nodes = 3

错误根源 #

1. insertatPosition函数双向链接断裂：插入中间节点时，仅设置了新节点的pre和前驱节点的next，但未更新原后继节点的pre指针，导致链表反向链接失效。例如插入25到pos1后，节点10的pre仍指向100而非25，破坏了双向链表的结构。
2. 删除函数边界处理缺失：deleteatBegin和deleteatLast未处理链表只剩一个节点的情况，存在空指针访问风险。

修复后的代码 #

#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *pre;
    struct node *next;
};

void createNode(struct node **head, int data)
{
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->pre = NULL;
    if(*head == NULL)
    {
        *head = newNode;
        return;
    }
    struct node *temp = *head;
    while(temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->pre = temp;
}

void insertatBegin(struct node **head,int data)
{
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = data;
    newNode->next = *head;
    newNode->pre = NULL;
    if(*head != NULL)
    {
        (*head)->pre = newNode;
    }
    *head = newNode;
}

void display(struct node *head)
{
    int count = 0;
    struct node *temp = head;
    while(temp != NULL)
    {
        printf("%d\n",temp->data);
        count++;
        temp = temp->next;
    }
    printf("\nno of nodes = %d\n",count);
}

void insertatPosition(struct node **head,int data,int pos)
{
    if(pos == 0)
    {
        insertatBegin(head,data);
        return;
    }
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = data;
    struct node *temp = *head;
    while(--pos)
    {
        temp = temp->next;
    }
    newNode->next = temp->next;
    newNode->pre = temp;
    temp->next = newNode;
    // 修复：更新后继节点的pre指针
    if(newNode->next != NULL)
    {
        newNode->next->pre = newNode;
    }
}

void deleteatLast(struct node **head)
{
    if(*head == NULL) return;
    struct node *temp = *head;
    while(temp->next != NULL)
    {
        temp = temp->next;
    }
    if(temp->pre == NULL)
    {
        // 链表只剩一个节点，删除后为空
        *head = NULL;
    }
    else
    {
        temp->pre->next = NULL;
    }
    free(temp);
}

void deleteatBegin(struct node **head)
{
    if(*head == NULL) return;
    struct node *temp = *head;
    *head = (*head)->next;
    if(*head != NULL)
    {
        (*head)->pre = NULL;
    }
    free(temp);
}

void deleteatPosition(struct node **head,int pos)
{
    if(*head == NULL) return;
    struct node *temp = *head;
    struct node *before,*after;
    int count = 0;
    struct node *temp4 = *head;
    while(temp4 != NULL)
    {
        count++;
        temp4 = temp4->next;
    }
    
    if(pos == 0)
    {
        deleteatBegin(head);
        return;
    }
    else if(pos == count-1)
    {
        deleteatLast(head);
        return;
    }
    else if(pos >= count)
    {
        // 处理超出范围的pos，避免越界
        return;
    }
    
    while(pos != 0)
    {
        temp = temp->next;
        pos--;
    }
    before = temp->pre;
    after = temp->next;
    if(before != NULL)
    {
        before->next = after;
    }
    if(after != NULL)
    {
        after->pre = before;
    }
    free(temp);
}

void main()
{
    struct node *head=NULL;
    createNode(&head,10);
    createNode(&head,20);
    createNode(&head,30);
    insertatBegin(&head,100);
    insertatPosition(&head,25,1);
    display(head);
    deleteatPosition(&head,3);
    display(head);
    deleteatPosition(&head,2);
    display(head);
    return;
}

修复说明 #

1. insertatPosition修复：添加newNode->next->pre = newNode，确保插入节点后，原后继节点的反向指针指向新节点，维护双向链表的完整性。
2. deleteatBegin修复：增加空链表判断，且仅当删除后链表非空时才设置pre指针，避免空指针访问。
3. deleteatLast修复：处理链表只剩一个节点的情况，将head置为NULL，避免访问空指针的next成员。
4. deleteatPosition增强：增加pos超出链表长度的判断，防止越界访问。

运行修复后的代码，输出将与预期一致。

内容的提问来源于stack exchange，提问作者NAVEENRAJ R