C語言實現雙向循環鏈表：節點插入操作詳解

雙向循環鏈表插入操作核心邏輯

在雙向循環鏈表中，每個節點擁有左右兩個指針（llink 指向前驅，rlink 指向後繼），並且頭尾相連形成閉環。這種結構使得在任意已知節點 p 前後插入新節點變得非常靈活。

插入原理圖解

假設 s、p、q 為三個連續節點：

• 在 p 前插入節點 r：將 s->rlink 指向 r，r->llink 指向 s，r->rlink 指向 p，p->llink 指向 r。
• 在 p、q 之間插入：同理，只需調整 p、q 及新節點的四個指針即可。

完整代碼示例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 10

typedef struct node {
    char name[20];
    struct node *llink, *rlink;
} stud;

/* 建立雙向循環鏈表 */
stud *creat(int n) {
    stud *p, *h, *s;
    int i;
    if ((h = (stud *)malloc(sizeof(stud))) == NULL) {
        printf("記憶體分配失敗！\n");
        exit(0);
    }
    h->name[0] = '\0';
    h->llink = h->rlink = NULL;
    p = h;
    for (i = 0; i < n; i++) {
        if ((s = (stud *)malloc(sizeof(stud))) == NULL) {
            printf("記憶體分配失敗！\n");
            exit(0);
        }
        p->rlink = s;
        printf("請輸入第 %d 個人的姓名：", i + 1);
        scanf("%s", s->name);
        s->llink = p;
        s->rlink = NULL;
        p = s;
    }
    /* 首尾相連形成循環 */
    h->llink = s;
    p->rlink = h;
    return h;
}

/* 查找指定姓名節點 */
stud *search(stud *h, char *x) {
    stud *p = h->rlink;
    char *y;
    while (p != h) {
        y = p->name;
        if (strcmp(y, x) == 0) return p;
        p = p->rlink;
    }
    printf("未找到該數據！\n");
    return NULL;
}

/* 列印鏈表所有節點 */
void print(stud *h) {
    stud *p = h->rlink;
    printf("數據信息為：\n");
    while (p != h) {
        printf("%s ", p->name);
        p = p->rlink;
    }
    printf("\n");
}

/* 在節點 p 後插入新節點 */
void insert(stud *p) {
    char stuname[20];
    stud *s;
    if ((s = (stud *)malloc(sizeof(stud))) == NULL) {
        printf("記憶體分配失敗！\n");
        exit(0);
    }
    printf("請輸入要插入的人的姓名：");
    scanf("%s", stuname);
    strcpy(s->name, stuname);
    /* 四步指針重連 */
    s->rlink = p->rlink;
    p->rlink = s;
    s->llink = p;
    (s->rlink)->llink = s;
}

int main() {
    int number = N;
    char studname[20];
    stud *head, *searchpoint;
    head = creat(number);
    print(head);
    printf("請輸入要查找的人的姓名：");
    scanf("%s", studname);
    searchpoint = search(head, studname);
    if (searchpoint) {
        printf("找到：%s\n", searchpoint->name);
        insert(searchpoint);
        print(head);
    }
    return 0;
}

關鍵點總結

1. 插入操作只需修改 4 個指針，時間複雜度 O(1)。
2. 建表時務必將頭節點的 llink 指向尾節點，尾節點的 rlink 指向頭節點，形成閉環。
3. 查找函數遍歷條件為 p != h，避免無限循環。