c - 我在c中实现循环链​​表的情况是否太多了

Question

我正在用 C 语言实现循环链​​表，其核心部分是 add2list() 函数，该函数根据 int data 字段按升序添加节点。我有 5 种不同的场景来决定何时在函数中添加节点，这让我觉得这有点太多了。我在google看到的大部分实现都有2到3种情况。然而，大多数这些实现还使用多个函数来添加节点(用于将节点添加到列表的开头/结尾的单独函数)。如果我有可以合并的案例(例如案例 2 和案例 4 非常相似)，我将不胜感激。如果您想打印列表，我添加了 printList() 函数。

这是我的代码:

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

typedef struct node * ptr;
typedef struct node {
    int data;
    ptr next;
}item;

void add2list(ptr *head, int num);
void printList(ptr p);

int main() {
    ptr head = NULL;

    add2list(&head, 1);
    add2list(&head, 2);
    add2list(&head, 5);
    add2list(&head, 3);
    add2list(&head, 0);
    add2list(&head, 4);
    add2list(&head, -2);
    printList(head);

    return 0;
}


void add2list(ptr *head, int num) {
    ptr p1, p2, t;

    t = (ptr) malloc(sizeof(item));

    if(!t) {
        printf("not enough memory\n");
        exit(0);
    }

    t -> data = num;
    p1 = *head;

    while(p1 != NULL && p1 -> next != *head && p1 -> data < num) {
        p2 = p1;
        p1 = p1 -> next;
    }

    if(!p1) { 
        //case 1 - if the list is empty
        *head = t;
        t -> next = *head;
    } else if(p1 == *head) {
        if(p1 -> data < t -> data) {
            //case 2 - if we need to add a node to the end of the list if there was only one node before
            (*head) -> next = t;
            t -> next = *head;
        } else {
            //case 3 - if we need to add a node to the beginning of the list
            while(p1 -> next != *head) {
                p1 = p1 -> next;
            }
            p1 -> next = t;
            t -> next = *head;
            *head = t;
        }
    } else if(p1 -> data < t -> data){
        //case 4 - need to add a node at the end of the list if there's more than one node
        p1 -> next = t;
        t -> next = *head;
    } else {
        //case 5 - need to add a node in the middle
        p2 -> next = t;
        t -> next = p1;
    }
}

void printList(ptr head) {
    ptr tmp;

    tmp = head;
    while(tmp -> next != head) {
        printf("%d ->\n", tmp -> data);
        tmp = tmp -> next;
    }
    printf("%d ->\n", tmp -> data);
}

Answer 1

这是我的尝试(警告，代码未经测试):

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

typedef struct Node Node;
struct Node {
    int data;
    Node *next;
};

void add2list(Node **proot, int value) {
    Node **pcur;
    Node *new;

    if (!(new = malloc(sizeof *new))) {
        fprintf(stderr, "malloc(%zu): %s\n", sizeof *new, strerror(errno));
        exit(EXIT_FAILURE);
    }
    new->data = value;

    if (!*proot) {
        // case 1: insert into empty list
        new->next = new;
        *proot = new;
        return;
    }

    if ((*proot)->data >= value) {
        // case 2: insert at beginning of list
        pcur = &(*proot)->next;
        while (*pcur != *proot) {
            pcur = &(*pcur)->next;
        }
        new->next = *proot;
        *proot = *pcur = new;
        return;
    }

    // case 3: insert elsewhere
    pcur = &(*proot)->next;
    while (*pcur != *proot && (*pcur)->data < value) {
        pcur = &(*pcur)->next;
    }
    new->next = *pcur;
    *pcur = new;
}

该函数首先分配一个新节点并设置其data成员。正如您的代码中一样，这对于所有三种情况都是常见的。

情况 1 是插入到空列表中。这是非常微不足道的。

情况 3 是“正常”情况，几乎与插入非循环列表相同(唯一的区别是列表末尾的测试，其中涉及非循环的 NULL循环列表)。 (这包含您的案例 2、4、5。)

情况 2(在开头插入)是比较棘手的地方。这种情况很特殊，因为这里我们必须更新两个变量，而不仅仅是一个:调用者中的变量，*proot(因为它也必须更新为列表的新头)作为列表中最后一个节点的下一个指针(以保持正确的循环)。在这种情况下，我们有一个额外的循环来遍历整个列表，只是为了找到列表中最后一个 next 指针的地址(存储在 pcur 中)。最后我们一起更新*proot和*pcur。 (这是您的案例 3。)