链表removeNode C编程

Question

我在ListNode和LinkedList之间有一些混淆。基本上我的问题分为两个部分。对于第一部分，我应该使用ListNode。函数原型如下:

int removeNode(ListNode **ptrHead, int index);

ListNode部分的所有函数都工作正常。然后对于第二部分，我应该将上面的函数更改为:

int removeNode(LinkedList *11, int index);

第1部分的代码运行正常，如下所示:

int removeNode(ListNode **ptrHead, int index) {
ListNode *pre, *cur;
if (index == -1)
    return 1;
else if (findNode(*ptrHead, index) != NULL) {
    pre = findNode(*ptrHead, index - 1);
    cur = pre->next;
    pre->next = cur->next;
    return 0;
}
else
    return 1;
}
ListNode *findNode(ListNode *head, int index) {
    ListNode *cur = head;
    if (head == NULL || index < 0)
        return NULL;
    while (index > 0) {
        cur = cur->next;
        if (cur == NULL) return NULL;
        index--;
    }
    return cur;
}

下面是我的第2部分的全部代码，它不能工作:

#include "stdafx.h"
#include <stdlib.h>
typedef struct _listnode {
    int num;
    struct _listnode *next;
}ListNode;
typedef struct _linkedlist {
    ListNode *head;
    int size;
}LinkedList;
void printNode2(ListNode *head);
int removeNode2(LinkedList *ll, int index);
int main()
{
    int value, index;
    ListNode *head = NULL, *newNode = NULL;
    LinkedList *ptr_ll = NULL;
    printf("Enter value, -1 to quit: ");
    scanf("%d", &value);
    while (value != -1) {
        if (head == NULL) {
            head = malloc(sizeof(ListNode));
            newNode = head;
        }
        else {
            newNode->next = malloc(sizeof(ListNode));
            newNode = newNode->next;
        }
        newNode->num = value;
        newNode->next = NULL;
        scanf("%d", &value);
    }
    printNode2(head);
    printf("nEnter index to remove: ");
    scanf("%d", &index);
    removeNode2(ptr_ll, index);
    printNode2(head);
    return 0;
}
void printNode2(ListNode *head) {
    printf("Current list: ");
    while (head != NULL) {
        printf("%d ", head->num);
        head = head->next;
    }
}
int removeNode2(LinkedList *ll, int index) {
    ListNode *head = ll->head;
    if (head == index)
    {
        if (head->next == NULL)
        {
            printf("There is only one node. The list can't be made empty ");
            return 1;
        }
        /* Copy the data of next node to head */
        head->num = head->next->num;
        // store address of next node
        index = head->next;
        // Remove the link of next node
        head->next = head->next->next;
        return 0;
    }

    // When not first node, follow the normal deletion process
    // find the previous node
    ListNode *prev = head;
    while (prev->next != NULL && prev->next != index)
        prev = prev->next;
    // Check if node really exists in Linked List
    if (prev->next == NULL)
    {
        printf("n Given node is not present in Linked List");
        return 1;
    }
    // Remove node from Linked List
    prev->next = prev->next->next;
    return 0;
}

当我尝试运行第2部分时，cmd只是没有响应，过了一会儿，它只是自己关闭，我不知道哪个部分出了问题。我在想我是在正确的轨道上还是整个LinkedList部分都错了?

当我尝试在调试模式下运行时，弹出以下错误信息:

Exception thrown at 0x01201FD1 in tut.exe: 0xC0000005: Access violation reading location 0x00000000.
If there is a handler for this exception, the program may be safely continued.

Answer 1

您说当列表仅通过头指针定义时，您使链表工作。在这个设置中，当列表可能被更新时，你必须传递一个指向头指针的指针，当你只检查列表而不修改时，只传递一个指向头指针的指针，例如:

int removeNode(ListNode **ptrHead, int index);
ListNode *findNode(ListNode *head, int index);

此处，头指针是客户端代码可见的列表句柄。

使用list结构体的方法为链表定义了一个新的接口。虽然头部节点已经足够了，但是为了方便附加节点或节点的数量，最好也跟踪尾部节点。这些数据可以被捆绑在链表结构体中。

这意味着节点的处理留给列表，客户端代码只使用链表结构，例如:

typedef struct ListNode ListNode;
typedef struct LinkedList LinkedList;
struct ListNode {
    int num;
    ListNode *next;
};
struct LinkedList {
    ListNode *head;
    ListNode *tail;
    int size;
};
void ll_print(const LinkedList *ll);
void ll_prepend(LinkedList *ll, int num);
void ll_append(LinkedList *ll, int num);
void ll_remove_head(LinkedList *ll);
int main()
{
    LinkedList ll = {NULL};
    ll_append(&ll, 2);
    ll_append(&ll, 5);
    ll_append(&ll, 8);
    ll_print(&ll);
    ll_prepend(&ll, 1);
    ll_prepend(&ll, 0);
    ll_print(&ll);
    ll_remove_head(&ll);
    ll_print(&ll);
    while (ll.head) ll_remove_head(&ll);
    return 0;
}

还有一个区别:在头节点设置中，头节点可能为空。这里，列表不能为空，它必须存在。(不过，它的头和尾成员可以为空。)这里列表是在堆栈上分配的，它的地址&ll必须传递给函数。

在链表设置中，修改访问和只读访问的区别是通过const关键字完成的:

void ll_print(const LinkedList *ll);
void ll_prepend(LinkedList *ll, int num);

在您的示例中，您使用两个独立结构的混合方法，一个头节点和一个列表。这是不行的，一个单独的列表由一个结构体描述，选择一个。

链表结构方法的优点是所有需要的数据，如头、尾和大小总是一起传递给函数。还可以通过不公开结构体成员来对用户隐藏实现，这样用户就只能操作指向该结构体的指针。

最后，这里是上述接口的一个示例实现供您使用:

void ll_print(const LinkedList *ll)
{
    ListNode *node = ll->head;
    while (node != NULL) {
        printf("%d ", node->num);
        node = node->next;
    }
    putchar('n');
}
void ll_prepend(LinkedList *ll, int num)
{
    ListNode *nnew = malloc(sizeof *nnew);
    nnew->next = ll->head;
    nnew->num = num;
    ll->head = nnew;
    if (ll->tail == NULL) ll->tail = ll->head;
    ll->size++;
}
void ll_append(LinkedList *ll, int num)
{
    ListNode *nnew = malloc(sizeof *nnew);
    nnew->next = NULL;
    nnew->num = num;
    if (ll->tail == NULL) {
        ll->tail = ll->head = nnew;
    } else {
        ll->tail->next = nnew;
        ll->tail = nnew;
    }
    ll->size++;
}
void ll_remove_head(LinkedList *ll)
{
    if (ll->head) {
        ListNode *ndel = ll->head;
        ll->head = ll->head->next;
        ll->size--;
        free(ndel);
    }
}