数据结构核心：链表（单链表、双链表及循环链表）

3. 求表长

遍历链表统计数据结点个数。

int Length(LinkList L) {
    int len = 0;
    LNode* p = L;
    while (p->next != NULL) {
        p = p->next;
        len++;
    }
    return len;
}

4. 按序号查找结点

从表头开始遍历，找到第 i 个结点。若越界或链表过短则返回 NULL。

LNode* GetElem(LinkList L, int i) {
    LNode* p = L;
    int j = 0;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

5. 按值查找表结点

遍历链表寻找第一个值为 e 的结点。

LNode* LocateElem(LinkList L, ElemType e) {
    LNode* p = L->next;
    while (p != NULL && p->data != e)
        p = p->next;
    return p;
}

6. 插入结点操作

指定位置插入： 先定位到第 i-1 个结点，再执行指针修改。

bool ListInsert(LinkList& L, int i, ElemType e) {
    if (i < 1) return false;
    LNode* p = L;
    int j = 0;
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL) return false;
    
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

指定结点前插： 利用已知结点 p，在其后插入新结点并交换数据，避免重新遍历。

bool InsertPriorNode(LNode* p, ElemType e) {
    if (p == NULL) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

指定结点后插： 直接在 p 之后插入新结点。

bool InsertNextNode(LNode* p, ElemType e) {
    if (p == NULL) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

7. 删除结点操作

定位到第 i-1 个结点，释放第 i 个结点内存。

bool ListDelete(LinkList& L, int i, ElemType& e) {
    LNode* p = L;
    int j = 0;
    while (p->next != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p->next == NULL || j > i - 1) return false;
    
    LNode* q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

8. 建立单链表

头插法： 每次新结点插在头结点之后，生成的链表顺序与输入顺序相反。

LinkList List_HeadInsert(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    int x;
    scanf("%d", &x);
    while (x != 9999) {
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

尾插法： 维护尾指针 r，新结点插在尾部，保持输入顺序。

LinkList List_TailInsert(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));
    LNode* r = L;
    int x;
    scanf("%d", &x);
    while (x != 9999) {
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}

三、双链表的定义

双链表在单链表基础上增加了前驱指针 prior，可双向遍历。结点结构如下：

typedef struct DNode {
    ElemType data;
    struct DNode* prior, * next;
} DNode, *DLinklist;

双链表插入与删除操作的时间复杂度可优化至 O(1)，因为可以直接访问前驱结点。

四、双链表的基本操作

1. 初始化

申请头结点，将 prior 和 next 均置为 NULL。

bool InitDLinklist(DLinklist& L) {
    L = (DNode*)malloc(sizeof(DNode));
    if (!L) return false;
    L->prior = NULL;
    L->next = NULL;
    return true;
}

2. 插入结点

在已知结点 p 后插入结点 s，需同时调整前后指针关系。

bool InsertNextDNode(DNode* p, DNode* s) {
    if (!p || !s) return false;
    s->next = p->next;
    if (p->next) p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}

3. 删除结点

删除结点 p 的后继结点，需断开前后连接并释放内存。

bool DeleteNextNode(DNode* p) {
    if (!p) return false;
    DNode* q = p->next;
    if (!q) return false;
    p->next = q->next;
    if (q->next) q->next->prior = p;
    free(q);
    return true;
}

4. 销毁链表

循环删除所有数据结点，最后释放头结点。

void DestroyList(DLinklist& L) {
    while (L->next != NULL)
        DeleteNextNode(L);
    free(L);
    L = NULL;
}

五、循环链表

1. 循环单链表

表尾结点的 next 指针指向头结点，形成环状。判空条件变为 L->next == L。

2. 循环双链表

头结点的 prior 指针也指向表尾结点。判空需同时检查 next 和 prior 是否指向头指针。

六、静态链表

使用数组模拟链式存储，next 字段存储数组下标而非地址。适合无法动态分配内存的环境，但长度固定。

#define MaxSize 50
typedef struct {
    ElemType data;
    int next;
} SLinkList[MaxSize];

以 -1 作为结束标志。

七、顺序表和链表的区别

顺序表适合频繁查询的场景，而链表更适合频繁插入删除且长度不确定的场景。