c - 使用尾随指针将节点插入链表 C

Question

我正在尝试按字母顺序创建名称链接列表，我注意到这是一个半常见的问题，但我在实现时遇到了一些困难。

所以，我的看法是，该项目可以添加到链表的开头、中间或末尾，我想我很难将其添加到末尾。

这是我对 bool 值的实现:

typedef int bool;
#define TRUE 1
#define FALSE 0

这是我的节点/项目/结构:

typedef struct student_s Student;

struct student_s {
    char name[MAX_NAME_SIZE];
    int age;
    Student* next;              // Pointer to next student in a list
};

我的比较函数:

// Compares two student structs based on their name and age, and returns true
// if student1 should come before student2 in alphabetical order
bool comesBefore(const Student* student1, const Student* student2) {
    int name_compare = strcmp(student1->name, student2->name);

    if (name_compare < 0) {
        return TRUE;
    }
    else if (name_compare == 0) {
        int age1 = student1->age;
        int age2 = student2->age;
        if (age1 < age2) {
            return TRUE;
        }
    }
    return FALSE;
}

我的插入函数:

Student* insert(Student* student, Student* list) {
    Student* curr = NULL;
    Student* prev = NULL;
    if (list == NULL) {
        printf("list == null\n");
        return student;
    }
    if (comesBefore(student, list)) {
        printf("Student comes before list\n");
        printf("Student age = %d\n", student->age);
        printf("List age = %d\n", list->age);
        student->next = list;
        return student;
    }
    for (curr = list, prev = NULL; curr != NULL && comesBefore(student, 
        curr) != TRUE; prev = curr, curr = curr->next) {
        printf("Stage 1\n\n");
        printf("curr age = %d\n", curr->age);
        printf("student age = %d\n", student->age);
        if (comesBefore(student, curr)) {
            printf("Stage 2\n");
            if (prev != NULL) {
                prev->next = student;
            }
            student->next = curr;
            break;
        }
        if ((curr->next) == NULL) {
            printf("Appended at the end of the list\n");
            curr->next = student;
            break;
        }       
    }
    return list; 

}

我的主要功能是所有测试:

int main(void)
{
    Student* student1 = malloc(sizeof(Student));
    Student* student2 = malloc(sizeof(Student));
    Student* student3 = malloc(sizeof(Student));
    strncpy(student1->name, "AAAAA", MAX_NAME_SIZE);
    student1->age = 10;
    student1->next = NULL;
    student2->next = NULL;
    student3->next = NULL;
    strncpy((*student2).name, "BBBBB", MAX_NAME_SIZE);
    (*student2).age = 100;
    strncpy((*student3).name, "CCCC", MAX_NAME_SIZE);
    (*student3).age = 1000;
    Student* list1 = insert(student1, NULL);
    Student* list2 = insert(student3, list1);
    Student* list3 = insert(student2, list2);
    printf("head %d\n", list3->age);
    printf("second element %d\n", (list3->next)->age);
    printf("third element %d\n", ((list3->next)->next)->age);
}

问题是我一直遇到段错误。我认为是当 next 设置为 NULL 时我尝试访问列表中的下一个节点 (curr->next)，但无论出于何种原因我的 if 语句

    if ((curr->next) == NULL) {
        printf("Appended at the end of the list\n");
        curr->next = student;
        break;
    }   

永远不会被触发。为什么？还是我完全错了？

Answer 1

问题是您的插入函数在一般情况下并没有真正插入。查看循环体:

for (curr = list, prev = NULL; curr != NULL && comesBefore(student, 
    curr) != TRUE; prev = curr, curr = curr->next) {
    printf("Stage 1\n\n");
    printf("curr age = %d\n", curr->age);
    printf("student age = %d\n", student->age);
    if (comesBefore(student, curr)) {
        printf("Stage 2\n");
        if (prev != NULL) {
            prev->next = student;
        }
        student->next = curr;
        break;
    }
    if ((curr->next) == NULL) {
        printf("Appended at the end of the list\n");
        curr->next = student;
        break;
    }       
}

只有在curr != NULL && comesBefore(student, curr) != TRUE时才进入循环体, 所以 if (comesBefore(student, curr))在循环内永远不会为真。

相反，您希望在循环终止后插入，即在循环之后。你也不需要 if ((curr->next) == NULL)在循环内；如果是，则循环将再迭代一次，curr将是 NULL和 prev将是您感兴趣的指针。循环条件写得很好，您只是在错误的地方做事。

这会起作用:

for (curr = list, prev = NULL;
     curr != NULL && comesBefore(student, curr) != TRUE;
     prev = curr, curr = curr->next) {
    printf("Stage 1\n\n");
    printf("curr age = %d\n", curr->age);
    printf("student age = %d\n", student->age);
}

student->next = curr;
prev->next = student;

return list;

这是此修复后的整个函数:

Student* insert(Student* student, Student* list) {
    Student* curr = NULL;
    Student* prev = NULL;
    if (list == NULL) {
        printf("list == null\n");
        return student;
    }
    if (comesBefore(student, list)) {
        printf("Student comes before list\n");
        printf("Student age = %d\n", student->age);
        printf("List age = %d\n", list->age);
        student->next = list;
        return student;
    }
    for (curr = list, prev = NULL;
         curr != NULL && comesBefore(student, curr) != TRUE;
         prev = curr, curr = curr->next) {
        printf("Stage 1\n\n");
        printf("curr age = %d\n", curr->age);
        printf("student age = %d\n", student->age);
    }

    student->next = curr;
    prev->next = student;

    return list;
}

当你完成调试后，循环体将是空的；您可能想添加一条评论说这是有意的(我通常喜欢这样做，以便其他阅读代码的人知道这不是错误)。像这样的东西:

Student* insert(Student* student, Student* list) {
    Student* curr = NULL;
    Student* prev = NULL;
    if (list == NULL)
        return student;

    if (comesBefore(student, list)) {
        student->next = list;
        return student;
    }

    for (curr = list, prev = NULL;
         curr != NULL && comesBefore(student, curr) != TRUE;
         prev = curr, curr = curr->next)
        ; /* Intentionally left blank */

    student->next = curr;
    prev->next = student;

    return list;
}

此外，您不需要测试 prev != NULL ，因为如果到达循环，那么我们就知道 comesBefore(student, list)为 false(因为我们在代码的前面测试过)，所以循环将始终至少执行一次。对于 self 文档(并确保 future 的代码更改不违反此变体)，您可能需要添加 assert(3)循环之后，像这样:

Student* insert(Student* student, Student* list) {
    Student* curr = NULL;
    Student* prev = NULL;
    if (list == NULL)
        return student;

    if (comesBefore(student, list)) {
        student->next = list;
        return student;
    }

    for (curr = list, prev = NULL;
         curr != NULL && comesBefore(student, curr) != TRUE;
         prev = curr, curr = curr->next)
        ; /* Intentionally left blank */

    assert(prev != NULL);

    student->next = curr;
    prev->next = student;

    return list;
}

您需要 #include <assert.h>使用 assert(3) .