链表模板

Created Mar 31, 2025 - Last updated: Mar 31, 2025

Growing 🌿

链表 algorithm 模板

单链表

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

typedef struct {
    int Num;
    char Name[10];
} ElemType;

struct node {
    ElemType data;
    struct node* next;
};

typedef struct node* Nodeptr;
typedef struct node Node;

// 含有空白头指针
Nodeptr initList()
{
    Nodeptr list = malloc(sizeof(Node));
    list->next = NULL;
    return list;
}

int getLength(Nodeptr list)
{
    Nodeptr p;
    int n = 0;
    for (p = list->next; p != NULL; p = p->next) {
        n++;
    }
    return n;
}

// 插入p的下一个位置
void insertNext(Nodeptr p, ElemType item)
{
    Nodeptr q;
    q = malloc(sizeof(Node));
    q->data = item;
    q->next = NULL;
    q->next = p->next;
    p->next = q;
}

// 插入第n个位置，n从0开始
void insertNode(int n, Nodeptr list, ElemType item)
{
    Nodeptr p;
    p = list;
    for (int i = 0; i < n; i++) {
        p = p->next;
    }
    insertNext(p, item);
}

// 删除节点p,pre为p的前置节点
void deleteNode(Nodeptr pre, Nodeptr p)
{
    pre->next = p->next;
    free(p);
}

// 删除第n个位置，n从0开始
void deleteNodeN(int n, Nodeptr list)
{
    Nodeptr pre = list, p = list->next;
    for (int i = 0; i < n; i++) {
        pre = pre->next;
        p = p->next;
    }
    deleteNode(pre, p);
}

void printList(Nodeptr list)
{
    Nodeptr p = list->next;
    printf("List elements:\n");
    while (p != NULL) {
        printf("Num: %d, Name: %s\n", p->data.Num, p->data.Name);
        p = p->next;
    }
    printf("-----------------\n");
}

void freeList(Nodeptr list)
{
    Nodeptr ptr = list;
    while (ptr) {
        Nodeptr next = ptr->next;
        free(ptr);
        ptr = next;
    }
}

int main()
{
    Nodeptr list = initList();
    ElemType e1 = { 1, "Alice" };
    ElemType e2 = { 2, "Bob" };
    ElemType e3 = { 3, "Charlie" };
    ElemType e4 = { 4, "David" };

    // 使用 insertNext 正确插入元素
    insertNext(list, e1); // 插入到位置0
    insertNext(list->next, e3); // 插入到e1后（位置1）
    printf("After inserting e1 and e3:\n");
    printList(list);
    printf("Length: %d\n", getLength(list)); // 应为2

    // 插入e2到e1和e3之间（位置1）
    insertNext(list->next, e2);
    printf("\nAfter inserting e2 at position1:\n");
    printList(list);
    printf("Length: %d\n", getLength(list)); // 应为3

    // 删除位置2的节点（e3）
    deleteNodeN(2, list);
    printf("\nAfter deleting position2 (e3):\n");
    printList(list); // 剩余 e1, e2
    printf("Length: %d\n", getLength(list)); // 应为2

    // 测试 insertNode 函数（注意：原函数存在逻辑错误）
    // 试图插入e3到位置1，预期结果可能不符合注释
    printf("\nTesting insertNode (may have issues):\n");
    insertNode(0, list, e3); // 原函数存在错误，实际插入到错误位置
    printList(list); // 观察实际插入位置
    printf("Length: %d\n", getLength(list));

    // 释放链表
    freeList(list);
    return 0;
}

双向链表

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

typedef struct {
    int Num;
    char Name[10];
} ElemType;

struct node {
    ElemType data;
    struct node* prev;
    struct node* next;
};

typedef struct node* Nodeptr;
typedef struct node Node;

// 初始化双向链表，带空白头指针
Nodeptr initList()
{
    Nodeptr list = malloc(sizeof(Node));
    list->prev = NULL;
    list->next = NULL;
    return list;
}

// 获取链表长度
int getLength(Nodeptr list)
{
    Nodeptr p;
    int n = 0;
    for (p = list->next; p != NULL; p = p->next) {
        n++;
    }
    return n;
}

// 在p后插入新节点
void insertNext(Nodeptr p, ElemType item)
{
    Nodeptr q = malloc(sizeof(Node));
    q->data = item;
    q->next = p->next;
    q->prev = p;

    if (p->next) {
        p->next->prev = q;
    }
    p->next = q;
}

// 在第n个位置插入节点，n从0开始
void insertNode(int n, Nodeptr list, ElemType item)
{
    Nodeptr p = list;
    for (int i = 0; i < n; i++) {
        p = p->next;
    }
    insertNext(p, item);
}

// 删除节点p
void deleteNode(Nodeptr p)
{
    if (p->prev) {
        p->prev->next = p->next;
    }
    if (p->next) {
        p->next->prev = p->prev;
    }
    free(p);
}

// 删除第n个位置的节点，n从0开始
void deleteNodeN(int n, Nodeptr list)
{
    Nodeptr p = list->next;
    for (int i = 0; i < n; i++) {
        p = p->next;
    }
    deleteNode(p);
}

void printList(Nodeptr list)
{
    Nodeptr p = list->next;
    printf("List elements:\n");
    while (p != NULL) {
        printf("Num: %d, Name: %s\n", p->data.Num, p->data.Name);
        p = p->next;
    }
    printf("-----------------\n");
}

// 释放链表
void freeList(Nodeptr list)
{
    Nodeptr ptr = list;
    while (ptr) {
        Nodeptr next = ptr->next;
        free(ptr);
        ptr = next;
    }
}

// 测试
int main()
{
    Nodeptr list = initList();
    ElemType e1 = { 1, "Alice" };
    ElemType e2 = { 2, "Bob" };
    ElemType e3 = { 3, "Charlie" };
    ElemType e4 = { 4, "David" };

    // 使用 insertNext 正确插入元素
    insertNext(list, e1); // 插入到位置0
    insertNext(list->next, e3); // 插入到e1后（位置1）
    printf("After inserting e1 and e3:\n");
    printList(list);
    printf("Length: %d\n", getLength(list)); // 应为2

    // 插入e2到e1和e3之间（位置1）
    insertNext(list->next, e2);
    printf("\nAfter inserting e2 at position1:\n");
    printList(list);
    printf("Length: %d\n", getLength(list)); // 应为3

    // 删除位置2的节点（e3）
    deleteNodeN(2, list);
    printf("\nAfter deleting position2 (e3):\n");
    printList(list); // 剩余 e1, e2
    printf("Length: %d\n", getLength(list)); // 应为2

    // 测试 insertNode 函数（注意：原函数存在逻辑错误）
    // 试图插入e3到位置1，预期结果可能不符合注释
    printf("\nTesting insertNode (may have issues):\n");
    insertNode(0, list, e3); // 原函数存在错误，实际插入到错误位置
    printList(list); // 观察实际插入位置
    printf("Length: %d\n", getLength(list));

    // 释放链表
    freeList(list);
    return 0;
}

单循环链表

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

typedef struct {
    int Num;
    char Name[10];
} ElemType;

struct node {
    ElemType data;
    struct node* next;
};

typedef struct node* Nodeptr;
typedef struct node Node;

// 初始化单循环链表（第一个节点）
Nodeptr initList(ElemType item)
{
    Nodeptr head = (Nodeptr)malloc(sizeof(Node));
    if (!head) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    head->data = item;
    head->next = head; // 自己指向自己，形成循环
    return head;
}

// 获取链表长度
int getLength(Nodeptr list)
{
    if (!list)
        return 0;

    int n = 1;
    Nodeptr p = list->next;
    while (p != list) {
        n++;
        p = p->next;
    }
    return n;
}

// 在 p 后插入新节点
Nodeptr insertNext(Nodeptr p, ElemType item)
{
    if (!p)
        return NULL;

    Nodeptr q = (Nodeptr)malloc(sizeof(Node));
    if (!q) {
        printf("Memory allocation failed!\n");
        exit(1);
    }

    q->data = item;
    q->next = p->next;
    p->next = q;

    return q;
}

// 删除节点（考虑删除头节点）
Nodeptr deleteNode(Nodeptr list, Nodeptr pre, Nodeptr p)
{
    if (!list || !p)
        return list;

    if (p == list && list->next == list) { // 只有一个节点
        free(p);
        return NULL;
    }

    pre->next = p->next;
    if (p == list) // 删除的是头节点，更新头指针
        list = p->next;
    free(p);

    return list;
}

// 打印链表
void printList(Nodeptr list)
{
    if (!list) {
        printf("List is empty.\n");
        return;
    }

    Nodeptr p = list;
    printf("List elements:\n");
    do {
        printf("Num: %d, Name: %s\n", p->data.Num, p->data.Name);
        p = p->next;
    } while (p != list);
    printf("-----------------\n");
}

// 释放链表
void freeList(Nodeptr list)
{
    if (!list)
        return;

    Nodeptr p = list->next;
    while (p != list) {
        Nodeptr temp = p;
        p = p->next;
        free(temp);
    }
    free(list);
}

// 测试
int main()
{
    ElemType e1 = { 1, "Alice" };
    Nodeptr list = initList(e1);
    ElemType e2 = { 2, "Bob" };
    ElemType e3 = { 3, "Charlie" };

    // 插入元素
    printf("After inserting e1:\n");
    printList(list);
    printf("Length: %d\n", getLength(list));
    Nodeptr pos = list;
    pos = insertNext(pos, e3); // e1 -> e3
    printf("After inserting e3:\n");
    printList(list);
    printf("Length: %d\n", getLength(list));

    // 插入e2到e1和e3之间
    insertNext(list->next, e2);
    printf("\nAfter inserting e2 at position 1:\n");
    printList(list);
    printf("Length: %d\n", getLength(list));

    int n = getLength(list);

    Nodeptr curr = list, pre = NULL;
    for (int i = 0; i < n; i++) {
        pre = curr;
        curr = curr->next;
    }
    list = deleteNode(list, pre, curr);

    // 释放链表
    freeList(list);
    return 0;
}

双向循环链表

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

typedef struct {
    int Num;
    char Name[10];
} ElemType;

struct node {
    ElemType data;
    struct node* next;
    struct node* prev;
};

typedef struct node* Nodeptr;
typedef struct node Node;

// 初始化双循环链表
Nodeptr initList(ElemType item)
{
    Nodeptr head = (Nodeptr)malloc(sizeof(Node));
    if (!head) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    head->data = item;
    head->next = head;
    head->prev = head; // 自己指向自己，形成双向循环
    return head;
}

// 获取链表长度
int getLength(Nodeptr list)
{
    if (!list)
        return 0;
    int n = 1;
    Nodeptr p = list->next;
    while (p != list) {
        n++;
        p = p->next;
    }
    return n;
}

// 在 p 后插入新节点
Nodeptr insertNext(Nodeptr p, ElemType item)
{
    if (!p)
        return NULL;

    Nodeptr q = (Nodeptr)malloc(sizeof(Node));
    if (!q) {
        printf("Memory allocation failed!\n");
        exit(1);
    }

    q->data = item;
    q->next = p->next;
    q->prev = p;
    p->next->prev = q; // 更新原后继节点的 prev
    p->next = q;

    return q;
}

// 删除指定节点（包括头节点情况）
Nodeptr deleteNode(Nodeptr list, Nodeptr p)
{
    if (!list || !p)
        return list;

    if (p == list && list->next == list) { // 只有一个节点
        free(p);
        return NULL;
    }

    p->prev->next = p->next;
    p->next->prev = p->prev;

    Nodeptr newHead = (p == list) ? p->next : list; // 如果删除头节点，更新 head
    free(p);
    return newHead;
}

// 打印链表
void printList(Nodeptr list)
{
    if (!list) {
        printf("List is empty.\n");
        return;
    }

    Nodeptr p = list;
    printf("List elements:\n");
    do {
        printf("Num: %d, Name: %s\n", p->data.Num, p->data.Name);
        p = p->next;
    } while (p != list);
    printf("-----------------\n");
}

// 释放链表
void freeList(Nodeptr list)
{
    if (!list)
        return;

    Nodeptr p = list->next;
    while (p != list) {
        Nodeptr temp = p;
        p = p->next;
        free(temp);
    }
    free(list);
}

// 测试
int main()
{
    ElemType e1 = { 1, "Alice" };
    Nodeptr list = initList(e1);
    
    ElemType e2 = { 2, "Bob" };
    ElemType e3 = { 3, "Charlie" };

    // 插入元素
    printf("After inserting e1:\n");
    printList(list);

    Nodeptr pos = list;
    pos = insertNext(pos, e3); // e1 -> e3
    printf("After inserting e3:\n");
    printList(list);

    // 插入e2到e1和e3之间
    insertNext(list, e2);
    printf("\nAfter inserting e2 at position 1:\n");
    printList(list);

    int n = getLength(list);
    printf("Length: %d\n", n);

    // 删除最后一个节点
    Nodeptr last = list->prev;
    list = deleteNode(list, last);
    printf("After deleting last node:\n");
    printList(list);

    // 释放链表
    freeList(list);
    return 0;
}