c - 用 C 语言编写带有哨兵和结构类型的动态双链表

Question

我试图通过使用“算法简介(第三版)”中的示例来创建该列表。但我遇到了一些我无法理解的困难。首先，由于 printf 函数在精确位置的存在，程序的工作正在发生变化。有一个地方需要 printf，而很多其他地方不能有 printf。其次，L.nil.next 的值在执行引用结构的每一行代码之后都会发生变化。不幸的是，由于值的变化，我无法修复该程序。如果有人修复并强制它像带有哨兵的动态双链表一样工作，我会非常高兴。

有一个代码

#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

struct sentinel{
    struct listel* nil;
};

struct listel{
    struct listel* prev;
    int key;
    struct listel* next;
};

int list_search(struct sentinel *L, int k);
void list_insert(struct sentinel *L, struct listel *x);
void list_delete(struct sentinel *L, struct listel *x);

int main(int argc, char *argv[]) {
    int s;
    struct sentinel *L=(struct sentinel*)malloc(sizeof(struct sentinel));
    printf("---sentinel created\n"); //FORCED TO WRITE
//  printf("L.nil = %p\nL.nil.prev = %p\nL.nil.next = %p\n", L->nil, L->nil->prev, L->nil->next);
    L->nil->next=L->nil;
    L->nil->prev=L->nil;
//  printf("sentinel parameters set\n"); //NOT ALLOWED TO WRITE
//  printf("L.nil = %p\nL.nil.prev = %p\nL.nil.next = %p\n", L->nil, L->nil->prev, L->nil->next); //NOW ALLOWED TO WRITE
    struct listel *x=(struct listel*)malloc(sizeof(struct listel));
    printf("created x\n");
//  printf("L.nil.next=%p\n", L->nil->next); //NOT ALLOWED TO WRITE
//  printf("prev = %p\nkey = %d\nnext = %p\n", x->prev, x->key, x->next); //NOW ALLOWED TO WRITE
    struct listel *y=(struct listel*)malloc(sizeof(struct listel));
    printf("created y\n");
//  printf("L.nil.next=%p\n", L->nil->next); //NOT ALLOWED TO WRITE
    struct listel *z=(struct listel*)malloc(sizeof(struct listel));
    printf("created z\n");
//  printf("L.nil.next=%p\n", L->nil->next); //NOT ALLOWED TO WRITE
    x->key=8;
//  printf("x.key = %d is set\n", x->key); //NOT ALLOWED TO WRITE
//  printf("L.nil.next=%p\n", L->nil->next); //NOT ALLOWED TO WRITE
//  x->next=L->nil->next;   //Trying to check line from list_insert without using that function
//  printf("x.next=L.nil.next=%p\n", x->next); //NOT ALLOWED TO WRITE
    list_insert(L, x); //I have checked no further
    x->key=3;
    list_insert(L, y);
    x->key=4;
    list_insert(L, z);
    printf("%d\n", list_search(L, 8));
    printf("%d\n", list_search(L, 6));
    printf("%d\n", list_search(L, 3));
    return 0;
}

int list_search(struct sentinel *L, int k){
    struct listel *x=(struct listel*)malloc(sizeof(struct listel));
    x = L->nil->next;
    while (x!=L->nil && x->key!=k) x=x->next;
    if (x==L->nil) return 0;
    return (x->key);
}

void list_insert(struct sentinel *L, struct listel *x){
    printf("    LIST INSERT\n");
//  printf("    L.nil.next=%p\n", L->nil->next);
    x->next=L->nil->next;
//  printf("    x.next=L.nil.next=%p\n", x->next); //NOT ALLOWED TO WRITE - I have checked no further
    L->nil->next->prev=x;
    L->nil->next=x;
    x->prev=L->nil;
}

void list_delete(struct sentinel *L, struct listel *x){
    x->prev->next=x->next;
    x->next->prev=x->prev;
}

Answer 1

malloc 不会将分配的内存初始化为任何合理的内容，因此

struct sentinel *L=(struct sentinel*)malloc(sizeof(struct sentinel));
printf( ... L->nil,   L->nil->prev ... UNDEFINED!! CRASH!! );
L->nil->next=L->nil; // UNDEFINED!! CRASH!!
L->nil->prev=L->nil; // UNDEFINED!! CRASH!!

删除所有这些并开始:

struct sentinel *L=(struct sentinel*)malloc(sizeof(struct sentinel));
L->nil = NULL;

你应该能够看到 L->nil->prev 和 L->nil->next 是没有意义的，除非 L 实际上包含一个有效的列表元素，例如如果你这样做:

struct listel *x=(struct listel*)malloc(sizeof(struct listel));
x->prev = NULL;
x->next = NULL;
L->nil = x;

然后 L->nil->prev == x->prev == NULL 和 L->nil->next == x->next == NULL