c语言 双向链表 节点删除功能问题

Question

双链表的节点删除操作，会删除掉其上一个节点，具体代码和问题输出如下：

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int data;
    struct node *next;
    struct node *pre;
} node;
void init(node *head)
{
    head->data = 0;
    head->next = NULL;
    head-> pre = NULL;
}
void head_insert(node *head, int n)
{
    node *p = (node *)malloc(sizeof(node));
    p->data = n;
    p->pre = head;
    p->next = head->next;
    head->next = p;
    head->data++;
}
void tail_insert(node *head, int n)
{
    node *p = head;
    node *q = (node *)malloc(sizeof(node));
    while(p->next!=NULL){
        p = p->next;
    }
    q->data = n;
    q->next = p->next;
    q->pre = p;
    p->next = q;
    head->data++;
}
void delete(node *head, int n)
{
    node *pre;
    node *next;
    node *p = head->next;
    while(p!=NULL){
        if(p->data==n&&p->next!=NULL){
            pre = p->pre;
            next = p->next;
            next->pre = pre;
            pre->next = next;
            head->data--;
           // free(p);
            break;
        }else if(p->data==n&&p->next==NULL){
            pre->next = p->next;
            p = p->next;
            head->data--;
            //free(p);
            break;
        }
        p = p->next;
    }
}
void print(node *head)
{
    node *p = head->next;
    while(p!=NULL){
        printf("%d ", p->data);
        p = p->next;
    }
}
int listlen(node *head)
{
    return head->data;
}
int main()
{
    node *head = (node *)malloc(sizeof(node));
    init(head);
    head_insert(head, 8);
    head_insert(head, 11);
    head_insert(head, 9);
    tail_insert(head, 13);

    printf("before delete :\n");
    print(head);
    printf("\n");
    delete (head, 11);
    printf("After delet :\n");
    printf("Head->next data: %d\n", (head->next)->data);
    print(head);
    printf("\n");

    printf("Node count: %d\n", listlen(head));

    return 0;
}

输出图片

Answer 1

代码的主要问题出在void head_insert(node* head, int n) 函数里，当头插法插入第二个结点时，已存在的第一个结点的 pre 指向新插入的第二个结点才对，而不是都指向 head。第二个问题是 delete 是 C 的关键字，所以 void delete(node head, int n) 函数改名为：void Delete(node head, int n)。问题处均已标注修改，修改如下，供参考：

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int data;
    struct node* next;
    struct node* pre;
} node;
void init(node* head)
{
    head->data = 0;
    head->next = NULL;
    head->pre = NULL;
}
void head_insert(node* head, int n)
{
    node* p = (node*)malloc(sizeof(node));
    p->data = n;
    if (head->next)           // 修改
        head->next->pre = p;  // 修改
    p->pre = head;
    p->next = head->next;
    head->next = p;
    head->data++;
}
void tail_insert(node* head, int n)
{
    node* p = head;
    node* q = (node*)malloc(sizeof(node));
    while (p->next != NULL) {
        p = p->next;
    }
    q->data = n;
    q->next = p->next;
    q->pre = p;
    p->next = q;
    head->data++;
}
void Delete(node* head, int n) //void delete(node* head, int n) // 修改
{
    node* pre = NULL;
    node* next = NULL;
    node* p = head->next;
    while (p != NULL) {
        if (p->data == n && p->next != NULL) {
            pre = p->pre;
            next = p->next;
            next->pre = pre;
            pre->next = next;
            head->data--;
            free(p);
            break;
        }
        else if (p->data == n && p->next == NULL) {
            pre = p->pre;        // 修改 
            pre->next = p->next; 
            //p = p->next;       // 修改
            head->data--;
            free(p);
            break;
        }
        p = p->next;
    }
}
void print(node* head)
{
    node* p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
}
int listlen(node* head)
{
    return head->data;
}
int main()
{
    node* head = (node*)malloc(sizeof(node));
    init(head);
    head_insert(head, 8);
    head_insert(head, 11);
    head_insert(head, 9);
    tail_insert(head, 13);

    printf("before delete :\n");
    print(head);
    printf("\n");
    Delete (head, 11);  //delete (head, 11); 修改
    printf("After delet :\n");
    printf("Head->next data: %d\n", (head->next)->data);
    print(head);
    printf("\n");

    printf("Node count: %d\n", listlen(head));

    return 0;
}