数据结构 - 链表 - 《C语言、数据结构课件》

回顾数组
改变存储策略
单向链表
双向链表
静态链表
考试题目
不带头结点的循环单链表
补充：链表排序
抽象数据类型（ADT）

回顾数组

时间复杂度：

访问：由于可以随机访问，O(1)
插入：O(n)
删除：O(n)
静态操作：访问或修改某个元素的值，常数时间内完成
动态操作：插入或删除一个元素，线性时间内完成

此外数组还有一个限制：数组大小一经确定不得修改，存在数组满的风险。

可扩容数组实现原理：当数组满后创建一个更大的数组，将原来数组中的内容复制到新的数组，释放掉原来数组所占内存。

究其本质：数组在逻辑结构和物理结构上都是连续的，对数组局部进行的修改可能引起大范围甚至整个数据结构的调整。

改变存储策略

保留逻辑上的次序（通过使用指针），每个节点的物理地址不作要求
不再具有数组随机访问的特性，静态访问操作时间复杂度O(n)
插入删除操作仅在局部进行，动态修改操作时间复杂度O(1)。当然确定在哪个节点上操作仍需O(n)的时间复杂度。
空间利用率更高，按需确定大小，可以动态扩容。但每个节点指针的存储需额外占用一定空间。

单向链表

节点定义

C++写法

struct Node {    //C++写法
    int data;
    Node* next;
    //构造函数
    Node(int x = 0) { data = x; next = NULL; }
};
int main() {
    Node* temp1 = new Node(1);
    Node* temp2 = new Node(2);
    temp1->next = temp2;
}

C语言写法

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {    //C语言写法
    int data;
    struct Node* next;
}Node;
Node* createNode(int data) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = data;
    temp->next = NULL;
    return temp;
}
int main() {
    Node* temp1 = createNode(1);
    Node* temp2 = createNode(2);
    temp1->next = temp2;
}

关于头结点

又称哨兵节点。将链表空与非空情况进行统一，使得各类算法无需对各种边界退化情况做专门处理。
除非题目特别说明，否则默认链表都有头结点。

链表定义

struct LinkList {
    Node* head;        //头节点，必须
    //Node* rear;        //尾指针，指向链表最后一个节点，可选
    //int size;        //链表节点个数，可选
    LinkList() {    //构造函数，链表创建时的初始化操作
        head = new Node();    //创建头结点
        //rear = head;        //尾指针指向头结点
        //size = 0;
    }
};
int main() {
    LinkList* L = new LinkList();
}

使用头插法建立链表

1532966189624

//头插法建立链表
LinkList* createLinklist1(int A[], int n) {
    LinkList* L = new LinkList();
    for (int i = 0; i < n; i++) {
        Node* temp = new Node(A[i]);
        temp->next = L->head->next;
        L->head->next = temp;
    }
    return L;
}

使用尾插法建立链表

1532966334497

//尾插法建立链表
LinkList* createLinklist2(int A[], int n) {
    LinkList* L = new LinkList();
    Node* rear = L->head;        //创建尾指针
    for (int i = 0; i < n; i++) {
        Node* temp = new Node(A[i]);
        rear->next = temp;
        rear = rear->next;        //更新尾指针
    }
    return L;
}

统计链表节点个数、输出整个链表

int getSize(LinkList* L) {
    int cnt = 0;
    for (Node* p = L->head->next; p != NULL; p = p->next) {
        cnt++;
    }
    return cnt;
}
void printLinkList(LinkList* L) {
    for (Node* p = L->head->next; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}

查找

查找指定值节点位置

//在链表中查找第一个值为x的节点，并返回该节点的指针，未找到则返回NULL
Node* findElem(LinkList* L, int x) {
    for (Node* p = L->head->next; p != NULL; p = p->next) {
        if (p->data == x) {
            return p;
        }
    }
    return NULL;
}

访问第i个节点

//访问第i个节点（i从0开始计数）
int getNodeAt(LinkList* L, int i) {
    int cnt = 0;
    for (Node* p = L->head->next; p != NULL; p = p->next) {
        if (cnt == i) return p->data;
        cnt++;
    }
    printf("越界了\n");
    return -1;    //越界了
}

插入

在指定节点后面插入一个节点

1532965858870

//在指定节点后面插入节点e，并返回新插入节点的位置
Node* insertAfter(Node* p, int e) {
    Node* temp = new Node(e);
    temp->next = p->next;
    p->next = temp;
    return temp;
}

在下标i处插入一个节点

1565270326383

//在下标i节点处插入一个节点e，并返回新插入节点的指针
//i从0开始计数，不包括头结点（与数组的操作统一）
//即在下标i节点的前面插入一个节点e
Node* insertAt(LinkList* L, int i, int e) {
    Node* p = L->head;
    while (i--) {    //p向后移动i次
        p = p->next;
        if (p == NULL) {
            printf("越界了，插入失败\n");
            return NULL;
        }
    }
    //return insertAfter(p, e);
    Node* temp = new Node(e);
    temp->next = p->next;
    p->next = temp;
    return temp;
}

删除

要删除节点p，必须找到节点p的前驱节点。

删除节点p的后继节点

1532965552954

int removeNodeAfter(Node* p) {    //删除指定节点的后继节点，并返回删除节点的值
    if (p->next == NULL) return -1;    
    Node* temp = p->next;
    int ret = temp->data;
    p->next = temp->next;    
    delete temp;    //free(temp);
    return ret;
}

删除指定位置节点

//给定节点t的地址，在链表中删除该节点
int removeNode(LinkList* L, Node* t) {
    Node* p;
    //找到节点t的前驱节点p
    for (p = L->head; p != NULL; p = p->next) {
        if (p->next == t) break;
    }
    //return deleteNodeAfter(p);
    int ret = t->data;
    p->next = t->next;
    delete t;
    return ret;
}

删除下标i处的节点

//删除下标i节点，并返回删除节点的值
//即删除下标i-1节点的后一个节点
int removeAt(LinkList* L, int i) {
    Node* p = L->head;
    //p向后移动i次，最终p指向带删除节点的前驱节点
    while (i-- && p->next != NULL) {
        p = p->next;
    }
    if (p->next == NULL) {
        printf("越界了，删除失败\n");
        return -1;
    }
    //return removeAfter(p);
    Node* temp = p->next;
    int ret = temp->data;
    p->next = temp->next;
    delete temp;
    return ret;
}

完整代码

#include <cstdio>
struct Node {
    int data;
    Node* next;
    //构造函数，将该节点的data赋值为x（默认为0），next置为NULL
    Node(int x = 0) { data = x; next = NULL; }
};
struct LinkList {
    Node* head;        //头节点，必须
    //构造函数，将链表初始化为仅含头结点的空链表
    LinkList() {
        head = new Node();    //创建头结点
    }
};
//头插法建立链表
LinkList* createLinklist1(int A[], int n) {
    LinkList* L = new LinkList();
    for (int i = 0; i < n; i++) {
        Node* temp = new Node(A[i]);
        temp->next = L->head->next;
        L->head->next = temp;
    }
    return L;
}
//尾插法建立链表
LinkList* createLinklist2(int A[], int n) {
    LinkList* L = new LinkList();
    Node* rear = L->head;        //创建尾指针
    for (int i = 0; i < n; i++) {
        Node* temp = new Node(A[i]);
        rear->next = temp;
        rear = rear->next;        //更新尾指针
    }
    return L;
}
//在链表中查找第一个值为x的节点，并返回该节点的指针，未找到则返回NULL
Node* findElem(LinkList* L, int x) {
    for (Node* p = L->head->next; p != NULL; p = p->next) {
        if (p->data == x) {
            return p;
        }
    }
    return NULL;
}
//访问第i个节点（i从0开始计数）
int getNodeAt(LinkList* L, int i) {
    int cnt = 0;
    for (Node* p = L->head->next; p != NULL; p = p->next) {
        if (cnt == i) return p->data;
        cnt++;
    }
    printf("越界了\n");
    return -1;    //越界了
}
//在指定节点后面插入节点e，并返回新插入节点的位置
Node* insertAfter(Node* p, int e) {
    Node* temp = new Node(e);
    temp->next = p->next;
    p->next = temp;
    return temp;
}
//在下标i节点处插入一个节点e，并返回新插入节点的指针
//i从0开始计数，不包括头结点（与数组的操作统一）
//即在下标i节点的前面插入一个节点e
Node* insertAt(LinkList* L, int i, int e) {
    Node* p = L->head;
    while (i--) {    //p向后移动i次
        p = p->next;
        if (p == NULL) {
            printf("越界了，插入失败\n");
            return NULL;
        }
    }
    //return insertAfter(p, e);
    Node* temp = new Node(e);
    temp->next = p->next;
    p->next = temp;
    return temp;
}
//删除指定节点的后继节点，并返回删除节点的值
int removeAfter(Node* p) {
    if (p->next == NULL) return -1;
    Node* temp = p->next;
    int ret = temp->data;
    p->next = temp->next;
    delete temp;
    return ret;
}
//删除下标i节点，并返回删除节点的值
//即删除下标i-1节点的后一个节点
int removeAt(LinkList* L, int i) {
    Node* p = L->head;
    while (i-- && p->next != NULL) {    //p向后移动i次
        p = p->next;
    }
    if (p->next == NULL) {
        printf("越界了，删除失败\n");
        return -1;
    }
    //return removeAfter(p);
    if (p->next == NULL) return -1;
    Node* temp = p->next;
    int ret = temp->data;
    p->next = temp->next;
    delete temp;
    return ret;
}
//给定节点t的地址，在链表中删除该节点
int removeNode(LinkList* L, Node* t) {
    Node* p;
    for (p = L->head; p != NULL; p = p->next) {    //找到节点t的前驱节点p
        if (p->next == t) break;
    }
    //return deleteNodeAfter(p);
    int ret = t->data;
    p->next = t->next;
    delete t;
    return ret;
}
int getSize(LinkList* L) {
    int cnt = 0;
    for (Node* p = L->head->next; p != NULL; p = p->next) {
        cnt++;
    }
    return cnt;
}
void printLinkList(LinkList* L) {
    for (Node* p = L->head->next; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n\n");
}
int main() {
    int A[] = { 1,2,3,4,5 };
    int N = sizeof(A) / sizeof(int);
    printf("尾插法创建一个链表，记为L2:\n");
    LinkList* L2 = createLinklist2(A, N);
    printLinkList(L2);
    printf("头插法创建一个链表，记为L1:\n");
    LinkList* L1 = createLinklist1(A, N);
    printLinkList(L1);
    printf("以下均是对链表L1进行操作:\n\n");
    printf("在下标6处尝试插入节点10：\n");
    insertAt(L1, 6, 10);
    printf("\n");
    insertAt(L1, 5, 10);
    printf("在下标5处插入节点10：\n");
    printLinkList(L1);
    insertAt(L1, 0, 11);
    printf("在下标0处插入节点11：\n");
    printLinkList(L1);
    Node* p = findElem(L1, 3);
    printf("查找第一个值为3的节点，将该节点记为p\n");
    Node* p1 = insertAfter(p, 20);
    printf("在节点p后面插入一个节点20，并将新插入的节点记为p1：\n");
    printLinkList(L1);
    removeNode(L1, p1->next);
    printf("删除p1节点后的节点：\n");
    printLinkList(L1);
    removeAfter(p1);
    printf("再删除p1节点后的节点：\n");
    printLinkList(L1);
    removeAt(L1, 0);
    printf("删除下标0节点：\n");
    printLinkList(L1);
    printf("尝试删除下标5节点:");
    removeAt(L1, 5);
    printf("\n");
    removeAt(L1, 4);
    printf("删除下标4节点：\n");
    printLinkList(L1);
    printf("访问下标3的节点：");
    printf("%d\n\n", getNodeAt(L1, 3));
    return 0;
}

完整代码（头结点裸露、纯C语言实现）

写法1：

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int data;
    struct Node* next;
} Node;
Node* createNode(int data) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = data;
    temp->next = NULL;
    return temp;
}
//创建一个空链表
Node* createLinklist0() {
    Node* head = createNode(0);
    return head;
}
//头插法建立链表
Node* createLinklist1(int A[], int n) {
    Node* head = createNode(0);
    for (int i = 0; i < n; i++) {
        Node* temp = createNode(A[i]);
        temp->next = head->next;
        head->next = temp;
    }
    return head;
}
//尾插法建立链表
Node* createLinklist2(int A[], int n) {
    Node* head = createNode(0);
    Node* rear = head;        //创建尾指针
    for (int i = 0; i < n; i++) {
        Node* temp = createNode(A[i]);
        rear->next = temp;
        rear = rear->next;        //移动尾指针
    }
    return head;
}
Node* findElem(Node* L, int x) {
    for (Node* p = L->next; p != NULL; p = p->next) {
        if (p->data == x) {
            return p;
        }
    }
    return NULL;
}
//在指定节点后面插入节点，并返回新插入节点的位置
Node* insertNodeAfter(Node* p, int x) {
    Node* temp = createNode(x);
    temp->next = p->next;
    p->next = temp;
    return temp;
}
//删除指定节点的后继节点，并返回删除节点的值
int deleteNodeAfter(Node* p) {
    if (p->next == NULL) return -1;
    Node* temp = p->next;
    int ret = temp->data;
    p->next = temp->next;
    free(temp);
    return ret;
}
//删除指定节点，并返回删除节点的值
int deleteNode(Node* L, Node* t) {
    Node* p;
    for (p = L; p != NULL; p = p->next) {    //找到节点t的前驱节点p
        if (p->next == t) break;
    }
    //return deleteNodeAfter(p);
    int ret = t->data;
    p->next = t->next;
    free(t);
    return ret;
}
int getLinklistSize(Node* head) {
    int cnt = 0;
    for (Node* p = head->next; p != NULL; p = p->next) {
        cnt++;
    }
    return cnt;
}
void printLinklist(Node* head) {
    for (Node* p = head->next; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}
int main() {
    int A[] = { 1,2,3,4,5 };
    int N = sizeof(A) / sizeof(int);
    Node* head = createLinklist1(A, N);    //头插法
    printLinklist(head);
    Node* head2 = createLinklist2(A, N);    //尾插法
    printLinklist(head2);
    Node* p = findElem(head, 3);    //找到节点3的位置
    Node* p1 = insertNodeAfter(p, 10);    //在节点3后面插入一个节点10
    printLinklist(head);
    deleteNode(head, p1->next);
    printLinklist(head);
    deleteNode(head, p1->next);
    printLinklist(head);
    return 0;
}

写法2：

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int data;
    struct Node* next;
} Node;
typedef Node* Linklist;        //关键语句
Node* createNode(int data) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = data;
    temp->next = NULL;
    return temp;
}
//创建一个空链表
Linklist createLinklist0() {
    Node* head = createNode(0);
    return head;
}
//头插法建立链表
Linklist createLinklist1(int A[], int n) {
    Node* head = createNode(0);
    for (int i = 0; i < n; i++) {
        Node* temp = createNode(A[i]);
        temp->next = head->next;
        head->next = temp;
    }
    return head;
}
Node* findElem(Linklist L, int x) {
    for (Node* p = L->next; p != NULL; p = p->next) {
        if (p->data == x) {
            return p;
        }
    }
    return NULL;
}
//在指定节点后面插入节点，并返回新插入节点的位置
Node* insertNodeAfter(Node* p, int x) {
    Node* temp = createNode(x);
    temp->next = p->next;
    p->next = temp;
    return temp;
}
void printLinklist(Linklist L) {
    for (Node* p = L->next; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}
int main() {
    int A[] = { 1,2,3,4,5 };
    int N = sizeof(A) / sizeof(int);
    Linklist L = createLinklist1(A, N);    //头插法
    printLinklist(L);
    Node* p = findElem(L, 3);    //找到节点3的位置
    Node* p1 = insertNodeAfter(p, 10);    //在节点3后面插入一个节点10
    printLinklist(L);
    return 0;
}

备注：

typedef可以为一个已有类型取多个别名，比如

typedef int numType1, numType2;    //给int类型取了两个别名
numType1 a = 5;
numType2 b = 10;

在严蔚敏的数据结构教材中，会出现这种写法：

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

其实就相当于下面这种写法：

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

typedef Node* Linklist;

例题：多项式加法

一个多项式可以使用链表来表示，设计一个算法，可以对用链表表示的多项式进行加法运算。

  P1 = 3x^5 + 4x^4 - x^3        + 2x - 1
+ P2 =        2x^4 + x^3 - 7x^2 +  x
-----------------------------------------
   P = 3x^5 + 6x^4       - 7x^2 + 3x - 1

思路：指数相同的项系数可以直接相加，其余部分直接拷贝

#include <iostream>
#include <initializer_list>
#include <string>
using namespace std;

struct PolyNode {
    int coef;    //系数
    int exp;    //指数
    PolyNode* next;

    PolyNode() :next(NULL) {}
    PolyNode(int coef, int exp) :next(NULL), coef(coef), exp(exp) {}
};

PolyNode* poly_add(PolyNode* A, PolyNode* B) {
    PolyNode* p = A->next;
    PolyNode* q = B->next;
    PolyNode* C = new PolyNode();
    PolyNode* rear = C;
    while (p != NULL && q != NULL) {
        PolyNode* temp = NULL;
        if (p->exp > q->exp) {
            temp = new PolyNode(p->coef, p->exp);
            p = p->next;
        }
        else if (p->exp < q->exp) {
            temp = new PolyNode(q->coef, q->exp);
            q = q->next;
        }
        else {    //p、q所指的项指数相同，可以直接相加
            int x = p->coef + q->coef;
            if (x != 0) {
                temp = new PolyNode(x, p->exp);
            }    //如果相加后系数为0，此时temp==NULL
            p = p->next;
            q = q->next;
        }
        //如果temp不为null则将其插入多项式C的末尾
        if (temp != NULL) {
            rear->next = temp;
            rear = temp;    //rear = rear->next;
        }
    }
    while (p != NULL) {
        rear->next = new PolyNode(p->coef, p->exp);
        rear = rear->next;
        p = p->next;
    }
    while (q != NULL) {
        rear->next = new PolyNode(q->coef, q->exp);
        rear = rear->next;
        q = q->next;
    }
    return C;
}

//如果你不在意输出格式，该函数可以简单这样写
void printPoly_simply(PolyNode* head) {
    for (PolyNode* p = head->next; p != NULL; p = p->next) {
        printf("%dx^%d + ", p->coef, p->exp);
    }
    printf("\n");
}

void printPoly(PolyNode* head) {
    bool isFirst = true;    //当前输出的这一项是否是该多项式的第一项
    bool hasOutput = false;
    for (PolyNode* p = head->next; p != NULL; p = p->next) {
        int coef = p->coef, exp = p->exp;
        if (coef == 0) continue;

        //输出系数部分
        if (coef == 1) {
            printf("%s", isFirst ? "" : " + ");
        }
        else if (coef == -1) {
            printf("%s", isFirst ? "-" : " - ");
        }
        else if (coef > 1) {
            if (isFirst) printf("%d", coef);
            else printf(" + %d", coef);
        }
        else if (coef < -1) {
            if (isFirst) printf("%d", coef);
            else printf(" - %d", -coef);
        }

        //输出指数部分
        if (exp == 0) {
            if (coef == 1 || coef == -1) {
                printf("1");
            }
        }
        else if (exp == 1) {
            printf("x");
        }
        else {
            printf("x^%d", exp);
        }

        isFirst = false;
        hasOutput = true;
    }
    //如果一个多项式链表为空或者其每一项的系数都为0，则最终输出一个0
    if (hasOutput == false) printf("0");
    printf("\n");
}

void test(const initializer_list<pair<int, int>> &il1,
    const initializer_list<pair<int, int>> &il2) {
    static int cnt = 0;
    printf("-------------------------------\n");
    printf("测试用例 #%d:\n", ++cnt);

    PolyNode* A = new PolyNode();
    PolyNode* rear_A = A;
    for (pair<int, int> p : il1) {
        rear_A->next = new PolyNode(p.first, p.second);
        rear_A = rear_A->next;
    }

    PolyNode* B = new PolyNode();
    PolyNode* rear_B = B;
    for (pair<int, int> p : il2) {
        rear_B->next = new PolyNode(p.first, p.second);
        rear_B = rear_B->next;
    }

    printf("多项式A：\n");
    printPoly(A);
    printf("多项式B：\n");
    printPoly(B);
    printf("\n");

    PolyNode* C = poly_add(A, B);
    printf("多项式A+B：\n");
    printPoly(C);
}

int main() {
    test({ {3,5}, {4,4}, {-1,3}, {2,1}, {-1,0} },
        { {2,4}, {1,3}, {-7,2}, {1,1} });

    test({ {-1,0} },
        { {1,0} });

    return 0;
}

双向链表

节点、链表定义

struct Node {
    int data;
    Node *pre, *next;

    Node(int x = 0) { data = x; pre = NULL; next = NULL; }
};

struct LinkList {
    Node *head, *rear;    //头节点、尾节点
    int size;

    LinkList() {
        head = new Node();
        rear = new Node();
        head->next = rear;
        rear->pre = head;
        size = 0;
    }
};

插入

在p节点后面插入节点

1532964112744

Node* insertNodeAfter(Node* p, int x) {        //在p后面插入
    Node* temp = new Node(x);
    temp->next = p->next;
    temp->pre = p;
    p->next->pre = temp;
    p->next = temp;
    size++;
    return temp;
}

在p节点前面插入节点

1532964385694

Node* insertNodeBefore(Node* p, int x) {    //在p前面插入
    Node* temp = new Node(x);
    temp->next = p;
    temp->pre = p->pre;
    p->pre->next = temp;
    p->pre = temp;
    size++;
    return temp;
}

删除

1532965147131

int deleteNode(Node* p) {
    int ret = p->data;
    p->pre->next = p->next;
    p->next->pre = p->pre;
    delete p;
    size--;
    return ret;
}

清空

void clear() {
    Node* p = head->next;
    while (p != rear) {
        Node* temp = p;
        p = p->next;
        delete temp;
    }
    head->next = rear;
    rear->pre = head;
    size = 0;
}

完整代码（使用C++面向对象的方法描述）

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *pre, *next;

    Node(int x = 0) { data = x; pre = nullptr; next = nullptr; }
};

class LinkList {
private:
    Node *head, *rear;    //头节点、尾节点（注意区分尾节点与尾指针）
    int size;

public:
    //构造函数，自动创建头结点、尾节点，用于链表的初始化
    LinkList() {
        head = new Node();
        rear = new Node();
        head->next = rear;
        rear->pre = head;
        size = 0;
    }

    //重载了一个新的构造函数，该构造函数会先调用上面不带参数的构造函数
    //然后依次将initializer_list容器中的每个元素插入链表末尾，相当于尾插法初始化链表
    //定义了一个接受参数为初始化列表的构造函数后，就可以使用{}语法来初始化该链表
    //如 LinkList L = { 1,2,3,4,5 }; 编译器会自动调用该构造函数
    LinkList(const initializer_list<int> &il) :LinkList() {
        for (int x : il) {
            push_back(x);
        }
    }

    ~LinkList() {    //析构函数
        clear();
        delete head; delete rear;
    }

    //访问第k个节点（k从0开始计数）
    int& get(int k) {
        //这里函数返回的是引用，因为不加引用get(k)只能作为右值  int a = get(k); 
        //而使用引用后get(k)则可以作为左值  get(k) = 100;
        if (k >= size) throw exception("访问下标越界");    //越界了
        int cnt = 0;
        for (Node* p = head->next; p != rear; p = p->next) {
            if (cnt == k) return p->data;
            cnt++;
        }
    }

    Node* findElem(int x) {
        for (Node* p = head->next; p != rear; p = p->next) {
            if (p->data == x) return p;
        }
        return nullptr;    //没找到
    }

    Node* insertNodeAfter(Node* p, int x) {
        Node* temp = new Node(x);
        temp->pre = p;
        temp->next = p->next;
        p->next->pre = temp;
        p->next = temp;
        size++;
        return temp;
    }

    Node* insertNodeBefore(Node* p, int x) {
        Node* temp = new Node(x);
        temp->next = p;
        temp->pre = p->pre;
        p->pre->next = temp;
        p->pre = temp;
        size++;
        return temp;
    }

    int removeNode(Node* p) {
        int ret = p->data;
        p->pre->next = p->next;
        p->next->pre = p->pre;
        delete p;
        size--;
        return ret;
    }

    void printAll() {
        if (head->next == rear) {
            printf("linklist is empty\n");
            return;
        }
        for (Node* p = head->next; p != rear; p = p->next) {
            printf("%d ", p->data);
        }
        printf("\n");
    }

    bool empty() {
        return size == 0;
    }

    void clear() {
        Node* p = head->next;
        while (p != rear) {
            Node* temp = p;
            p = p->next;
            delete(temp);
        }
        head->next = rear;
        rear->pre = head;
        size = 0;
    }

    int& operator[] (int k) {    //重载下标[]访问
        return get(k);
    }

    //下面这6个操作是为下一章学习队列做准备的
    int& front() {        //访问第一个节点
        if (empty()) throw exception("链表为空");
        return head->next->data;
    }

    int& back() {        //访问最后一个节点
        if (empty()) throw exception("链表为空");
        return rear->pre->data;
    }

    Node* push_back(int x) {    //在链表末尾插入一个节点
        return insertNodeBefore(rear, x);
    }

    Node* push_front(int x) {    //在链表开始插入一个节点
        return insertNodeAfter(head, x);
    }

    int pop_back() {        //删除链表末尾的节点
        if (empty()) throw exception("链表为空");
        return removeNode(rear->pre);
    }

    int pop_front() {        //删除链表开始的节点
        if (empty()) throw exception("链表为空");
        return removeNode(head->next);
    }
};

int main() {
    // 调用构造函数 LinkList(const initializer_list<int> &il)
    LinkList L = { 1,2,3,4,5 };    
    L.printAll();

    printf("L[2] = %d\n", L[2]);
    L[4] = 100;
    L.printAll();

    Node* p = L.findElem(4);
    L.insertNodeBefore(p, 10);
    L.printAll();

    L.removeNode(p);
    L.printAll();

    L.clear();
    L.printAll();
    return 0;
}

静态链表

1532843001360

节点定义

typedef int NodePosi;    // 空指针NULL用-1表示，因此这里不能使用无符号int

struct Node {
    int data;
    NodePosi next;    //模拟指针
};

静态链表与普通链表的联系

其实整个内存也可以看成是一个数组，比如4GB的内存，每个字节分配一个数组编号的话，这个“数组”的下标范围就是从 0 ~ 2^32 - 1。这样普通链表也可以看成是静态链表，指针就相当于是内存这个数组的下标。

完整代码*

#include <iostream>
using namespace std;

typedef int NodePosi;    // 约定空指针NULL用-1表示，因此这里不能使用无符号int

struct Node {
    int data;
    NodePosi next;    //模拟指针
};

class LinkList {    //使用数组模拟的静态单向链表
private:
    const int MAX_SIZE = 1000;

    Node* nodes;

    NodePosi head;    //头结点，对于静态链表，头结点的数组下标一定是0

    NodePosi index_allocator;    //记录当创建一个新节点时，当前可分配的数组下标。
                                //这算是一个非常笨的“内存池”，只会分配下标，不会回收下标。

    NodePosi createNode(int x = 0) {
        if (index_allocator >= MAX_SIZE) throw exception("静态链表已满");
        nodes[index_allocator].data = x;
        nodes[index_allocator].next = -1;    // 相当于节点temp.next = NULL
        return index_allocator++;
    }

public:
    LinkList() {
        index_allocator = 0;
        nodes = new Node[MAX_SIZE];
        head = createNode();    //数组0号下标作为头结点
        printf("静态链表初始化完成\n");
    }

    ~LinkList() {
        delete[] nodes;
    }

    NodePosi insertNodeAfter(NodePosi p, int x) {    //在指定节点p后面插入节点，并返回新插入节点的位置
        NodePosi temp = createNode(x);
        nodes[temp].next = nodes[p].next;
        nodes[p].next = temp;
        return temp;
    }

    int deleteNodeAfter(NodePosi p) {    //删除指定节点p的后继节点，并返回删除节点的值
        if (nodes[p].next == -1) throw exception("不能删除链表最后一个节点的后继节点");
        NodePosi temp = nodes[p].next;
        nodes[p].next = nodes[temp].next;
        return nodes[temp].data;
    }

    bool empty() {
        return nodes[head].next == -1;
    }

    void print() {
        for (NodePosi p = nodes[head].next; p != -1; p = nodes[p].next) {
            printf("%d ", nodes[p].data);
        }
        printf("\n");
    }
};

int main() {
    LinkList L;
    printf("L.empty() = %s\n", L.empty() ? "true" : "false");

    for (int i = 1; i <= 5; i++) {
        L.insertNodeAfter(0, i);    //在0号节点（头结点）后插入一个节点，相当于头插法建立链表
    }
    L.print();
    printf("L.empty() = %s\n", L.empty() ? "true" : "false");

    for (int i = 0; i < 5; i++) {
        L.deleteNodeAfter(0);
        L.print();
    }

    printf("L.empty() = %s\n", L.empty() ? "true" : "false");

    return 0;
}

考试题目

删除链表中值最小值的点

假设链表各节点的值不重复

#include <iostream>
#include <initializer_list>
using namespace std;

struct Node {
    int data;
    Node* next;

    Node(int x = 0) :data(x), next(NULL) {}
};

void deleteMinNode(Node* head) {
    if (head->next == NULL) return; //链表为空
    Node* minNode_pre = head;

    for (Node* p = head; p->next != NULL; p = p->next) {
        if (p->next->data < minNode_pre->next->data) {
            minNode_pre = p;
        }
    }

    Node* temp = minNode_pre->next;
    minNode_pre->next = temp->next;
    delete temp;
}

void printLinkList(Node* head) {
    for (Node* p = head->next; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}

void test(const initializer_list<int> &il) {
    static int cnt = 0;
    printf("-------------------------------\n");
    printf("测试用例 #%d:\n", ++cnt);
    Node* head = new Node();
    Node* rear = head;
    for (int x : il) {
        rear->next = new Node(x);
        rear = rear->next;
    }
    printf("调用算法前:\n");
    printLinkList(head);
    printf("\n");
    deleteMinNode(head);
    printf("调用算法后:\n");
    printLinkList(head);
}

int main() {
    test({ 1,2,3,-2,4 });
    test({ 1 });
    test({ 1,2 });
    test({ });

    return 0;
}

快慢指针

查找中间节点

如果链表的节点个数（不包括头节点）为奇数，则返回中间那个节点的指针。

如果链表的节点个数为偶数，则返回中间两个节点的前面那个节点的指针。

#include <iostream>
#include <initializer_list>
using namespace std;

struct Node {
    int data;
    Node* next;

    Node(int x = 0) :data(x), next(NULL) {}
};

Node* findMid(Node* head) {
    if (head->next == NULL) return NULL;
    Node* fast = head->next;
    Node* slow = head->next;
    while (fast->next != NULL && fast->next->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

void printLinkList(Node* head) {
    if (head->next == NULL) {
        printf("null\n");
        return;
    }
    for (Node* p = head->next; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}

void test(const initializer_list<int> &il) {
    static int cnt = 0;
    printf("-------------------------------\n");
    printf("测试用例 #%d:\n", ++cnt);

    Node* head = new Node();
    Node* rear = head;
    for (int x : il) {
        rear->next = new Node(x);
        rear = rear->next;
    }
    printLinkList(head);
    Node* ret = findMid(head);
    if (ret == NULL) printf("mid = null\n");
    else printf("mid = %d\n", ret->data);
}

int main() {
    test({ 1,2,3,-2,4 });
    test({ 1,2,3,4 });
    test({ 1 });
    test({ 1,2 });
    test({ });

    return 0;
}

查找链表倒数第n个节点

#include <iostream>
#include <initializer_list>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int x = 0) :data(x), next(NULL) {}
};

//找到链表倒数第n个节点，当n=1时返回最后一个节点位置
Node* findNthFromEnd(Node* head, int n) {
    if (head->next == NULL || n < 1) return NULL;
    Node* fast = head->next;
    while (n--) {
        if (fast == NULL) return NULL;    //越界
        fast = fast->next;
    }
    Node* slow = head->next;
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

void printLinkList(Node* head) {
    if (head->next == NULL) {
        printf("null\n");
        return;
    }
    for (Node* p = head->next; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}

void test(const initializer_list<int> &il, int n) {
    static int cnt = 0;
    printf("-------------------------------\n");
    printf("测试用例 #%d:\n", ++cnt);

    Node* head = new Node();
    Node* rear = head;
    for (int x : il) {
        rear->next = new Node(x);
        rear = rear->next;
    }
    printLinkList(head);
    printf("n = %d,  ", n);
    Node* ret = findNthFromEnd(head, n);
    if (ret == NULL) printf("ret = null\n");
    else printf("ret = %d\n", ret->data);
}

int main() {
    test({ 1,2,3,4 }, 1);
    test({ 1,2,3,4 }, 2);
    test({ 1,2,3,4 }, 3);
    test({ 1,2,3,4 }, 4);
    test({ 1,2,3,4 }, 5);
    test({ 1 }, 1);
    test({ }, 0);

    return 0;
}

链表逆置

设计一个算法将带头结点的单链表L逆置，要求不能建立新的节点，只能使用表中已有的节点重新组合完成。

1565278872095

#include <iostream>
#include <initializer_list>
using namespace std;

struct Node {
    int data;
    Node* next;

    Node(int x = 0) :data(x), next(NULL) {}
};

void reverseLinkList(Node* head) {
    Node* p = head->next;
    head->next = NULL;    //将头节点与其它节点断开
    while (p != NULL) {
        Node* temp = p;
        p = p->next;
        temp->next = head->next;    //将temp节点插在头节点后面
        head->next = temp;
    }
}

void printLinkList(Node* head) {
    for (Node* p = head->next; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}

void test(const initializer_list<int> &il) {
    static int cnt = 0;
    printf("-------------------------------\n");
    printf("测试用例 #%d:\n", ++cnt);
    Node* head = new Node();
    Node* rear = head;
    for (int x : il) {
        rear->next = new Node(x);
        rear = rear->next;
    }
    printf("链表逆置前:\n");
    printLinkList(head);
    printf("\n");
    reverseLinkList(head);
    printf("链表逆置后:\n");
    printLinkList(head);
}

int main() {
    test({ 1,2,3,4,5,6 });
    test({ 1 });
    test({});

    return 0;
}

有序链表去重

void uniqueLinkList(Node* head) {
    //错误写法，绝对不能这么写
    for (Node* p = head->next; p->next != NULL; p = p->next) {
        if (p->next->data == p->data) {
            Node* temp = p->next;
            p->next = temp->next;
            delete temp;
        }
    }
}

经验：对于单向链表来说，for (Node* p = head->next; p != NULL; p = p->next)遍历链表只适用于静态访问操作，对于遍历链表的同时进行插入删除等动态操作，应想清楚代码逻辑，改用while循环。

#include <iostream>
#include <initializer_list>
using namespace std;

struct Node {
    int data;
    Node* next;

    Node(int x = 0) :data(x), next(NULL) {}
};

void uniqueLinkList(Node* head) {
    Node* p = head->next;
    if (p == NULL) return;    //链表为空
    while (p->next != NULL) {
        if (p->next->data == p->data) {
            Node* temp = p->next;
            p->next = temp->next;
            delete temp;
        }
        else {
            p = p->next;
        }
    }
}

void printLinkList(Node* head) {
    for (Node* p = head->next; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}

void test(const initializer_list<int> &il) {
    static int cnt = 0;
    printf("-------------------------------\n");
    printf("测试用例 #%d:\n", ++cnt);
    Node* head = new Node();
    Node* rear = head;
    for (int x : il) {
        rear->next = new Node(x);
        rear = rear->next;
    }
    printf("调用算法前:\n");
    printLinkList(head);
    printf("\n");
    uniqueLinkList(head);
    printf("调用算法后:\n");
    printLinkList(head);
}

int main() {
    test({ 1,1,1,2,3,3,3,5,5 });
    test({ 1,1,1 });
    test({ 1 });
    test({ 1,2 });

    return 0;
}

拆分链表

设计一个算法，将一个带头节点的单链表A（数据域为整数）拆分为两个单链表A、B，其中链表A只含原链表data为奇数的节点，链表B只含原链表data为偶数的节点，且均需要保留原链表节点的相对次序。算法应接收两个链表A、B，其中链表B并未初始化。

#include <iostream>
#include <initializer_list>
using namespace std;

struct Node {
    int data;
    Node* next;

    Node(int x = 0) :data(x), next(NULL) {}
};

void splitLinkList(Node* A, Node* &B) {
    B = new Node();
    Node* rear = B;
    Node* p = A;
    while (p->next != NULL) {
        if (p->next->data % 2 == 0) {
            Node* temp = p->next;
            p->next = temp->next;
            rear->next = temp;
            rear = temp;    //rear = rear->next;
        }
        else {
            p = p->next;
        }
    }
    rear->next = NULL;
}

void printLinkList(Node* head) {
    for (Node* p = head->next; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}

void test(const initializer_list<int> &il) {
    static int cnt = 0;
    printf("-------------------------------\n");
    printf("测试用例 #%d:\n", ++cnt);

    Node* LinkList_A = new Node();
    Node* rear = LinkList_A;
    for (int x : il) {
        rear->next = new Node(x);
        rear = rear->next;
    }
    Node* LinkList_B = NULL;

    printf("调用算法前链表A:\n");
    printLinkList(LinkList_A);
    printf("\n");
    splitLinkList(LinkList_A, LinkList_B);
    printf("调用算法后:\n");
    printf("链表A:\n");
    printLinkList(LinkList_A);
    printf("链表B:\n");
    printLinkList(LinkList_B);
}

int main() {
    test({ 1,2,3,4,5 });
    test({ 2,2,1,3,4,4,4,5,6,6 });
    test({ 1,1,1 });
    test({ 2,2,2 });
    test({ 1 });
    test({ 2 });

    return 0;
}

合并两个有序单链表

链表A、B是两个带头结点的递增有序单链表，设计一个算法，将链表A、B合并成一个有序的单链表C，其中链表C的节点只能由链表A、B的节点组成，不能创建新的节点。合并结束应销毁链表A、B。

#include <iostream>
#include <initializer_list>
using namespace std;

struct Node {
    int data;
    Node* next;

    Node(int x = 0) :data(x), next(NULL) {}
};

Node* mergeLinkList(Node* &A, Node* &B) {
    Node* p = A->next;
    Node* q = B->next;

    Node* C = A;    //将链表A的头结点给链表C使用
    C->next = NULL;

    A = NULL;
    delete B;    //链表B的头结点不需要了，释放掉
    B = NULL;

    Node* rear = C;    //对链表C进行尾插法
    while (p != NULL && q != NULL) {
        if (p->data < q->data) {
            rear->next = p;
            p = p->next;
        }
        else {
            rear->next = q;
            q = q->next;
        }
        rear = rear->next;
    }
    //rear->next = NULL;

    if (p != NULL) {
        rear->next = p;
    }
    if (q != NULL) {
        rear->next = q;
    }

    return C;
}

void printLinkList(Node* head) {
    for (Node* p = head->next; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}

Node* createLinkList(const initializer_list<int> &il) {
    Node* head = new Node();
    Node* rear = head;
    for (int x : il) {
        rear->next = new Node(x);
        rear = rear->next;
    }
    return head;
}

void test(const initializer_list<int> &il1, const initializer_list<int> &il2) {
    static int cnt = 0;
    printf("-------------------------------\n");
    printf("测试用例 #%d:\n", ++cnt);

    Node* LinkList_A = createLinkList(il1);
    Node* LinkList_B = createLinkList(il2);

    printf("调用算法前:\n");
    printf("链表A:\n");
    printLinkList(LinkList_A);
    printf("链表B:\n");
    printLinkList(LinkList_B);
    printf("\n");

    Node* LinkList_C = mergeLinkList(LinkList_A, LinkList_B);
    printf("调用算法后:\n");
    printf("链表C:\n");
    printLinkList(LinkList_C);
}

int main() {
    test({ 1,3,5,7 }, { 2,4,6,20,30 });
    test({ 1, 1 }, { 2 });
    test({ 1 }, { });
    test({ }, { 2 });
    test({ }, { });

    return 0;
}

判断循环双向链表是否对称

给定一个带头节点的循环双向链表，设计一个算法判断其是否对称。

判断数组是否对称

bool judge(int A[], int N) {
    for (int i = 0, j = N - 1; i < j; i++, j--) {
        if (A[i] !=  A[j]) return false;
    }
    return true;
}

1567169263039

对于链表

bool judge(Node* head) {
    //for循环头部比较长，不习惯的话可以拆分成while循环。
    for (Node *p = head->next, *q = head->pre;
        p != q && q->next != p; p = p->next, q = q->pre) {
        if (p->data != q->data) return false;
    }
    return true;
}

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *pre, *next;
    Node(int data = 0) :data(data), pre(NULL), next(NULL) {}
};

Node* createLinklist(const initializer_list<int> &il) {
    Node* head = new Node();
    head->next = head;
    head->pre = head;
    Node* rear = head;
    for (int x : il) {
        Node* temp = new Node(x);
        //双向链表的插入操作
        temp->next = rear->next;
        temp->pre = rear;
        rear->next->pre = temp;
        rear->next = temp;
        //更新尾指针
        rear = temp;
    }
    return head;
}

void printLinklist(Node* head) {
    if (head->next == head) {
        printf("empty\n");
        return;
    }
    for (Node* p = head->next; p != head; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}

bool judge(Node* head) {
    //for循环头部比较长，不习惯的话可以拆分成while循环。
    for (Node *p = head->next, *q = head->pre;
        p != q && q->next != p; p = p->next, q = q->pre) {
        if (p->data != q->data) return false;
    }
    return true;
}

int main() {
    printf("%s\n", judge(createLinklist({1,2,3})) ? "true" : "false");
    printf("%s\n", judge(createLinklist({3,1})) ? "true" : "false");
    printf("%s\n", judge(createLinklist({1,2,2,1})) ? "true" : "false");
    printf("%s\n", judge(createLinklist({1,2,3,2,1})) ? "true" : "false");
    printf("%s\n", judge(createLinklist({1})) ? "true" : "false");
    printf("%s\n", judge(createLinklist({ })) ? "true" : "false");

}

不带头结点的循环单链表

1554433151259

判断链表是否为空：first == NULL

判断链表是否只有一个节点：first != NULL && first->next == first

判断指针p所指的节点是否是链表最后一个节点：p != NULL && p->next == first

因为链表没有带头结点，所以很多算法都需要对链表是否为空、是否是对第一个节点进行操作而做单独处理，难度大大增加。建议等有一定基础后再研究该代码。

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int x = 0) :data(x), next(NULL) {}
};

Node* createLinkList_rearInsertion(int A[], int N) {
    if (N == 0) return NULL;
    //先手动创建第一个节点
    Node* first = new Node(A[0]);
    //再使用尾插法添加剩下的节点
    Node* rear = first;
    for (int i = 1; i < N; i++) {
        rear->next = new Node(A[i]);
        rear = rear->next;
    }
    //循环链表需要首尾相连
    rear->next = first;
    return first;
}

Node* insertAfter(Node* &p, int x) {
    if (p == NULL) {
        p = new Node(x);
        p->next = p;
        return p;
    }
    Node* temp = new Node(x);
    temp->next = p->next;
    p->next = temp;
}

//在链表下标i处插入一个节点，链表第一个节点从编号0开始计数，与数组接口保持一致
//返回新插入节点的指针
Node* insertAt(Node* &first, int i, int x) {
    if (i < 0) throw invalid_argument("插入下标i小于0");
    Node* temp = new Node(x);    //先把要插入的节点创建好
    //因为链表没有头节点，在下标0处插入/删除一个节点需特殊处理
    if (i == 0) {
        if (first == NULL) {    //链表为空
            first = temp;
            first->next = first;
            return first;
        }
        else {
            //在下标0处插入相当于是在链表最后一个节点后面添加一个节点
            //首先找到循环链表的最后一个节点（记为last）
            Node* last = first;
            while (last->next != first) last = last->next;
            //最后一个节点（last）后面插入新的节点temp
            last->next = temp;
            temp->next = first;
            first = temp;    //修改first指针，让新插入的temp节点作为下标0
            return temp;
        }
    }
    else {        //与普通带头节点的单链表操作基本一致
        Node* p = first;
        for (int t = 0; t < i - 1; t++) {    //p往后移动i-1次
            p = p->next;
            if (p == first) throw out_of_range("插入下标越界");
        }
        temp->next = p->next;
        p->next = temp;
        return temp;
    }
}

//删除链表下标i处的节点，同上，与数组接口保持一致
void removeAt(Node* &first, int i) {
    if (i < 0) throw invalid_argument("删除的下标i小于0");
    if (first == NULL) throw invalid_argument("不能对空链表进行删除操作");
    if (i == 0) {
        if (first->next == first) {    //链表只有一个节点
            delete first;
            first = NULL;
            return;
        }
        //找到循环链表的最后一个节点
        Node* last = first;
        while (last->next != first) last = last->next;
        //删除链表第一个节点
        Node* temp = first;
        first = first->next;
        last->next = first;
        delete temp;
    }
    else {
        Node* p = first;
        for (int t = 0; t < i - 1; t++) {    //p往后移动i-1次
            p = p->next;
            if (p->next == first) throw out_of_range("删除下标越界");
        }
        Node* temp = p->next;
        p->next = temp->next;
        delete temp;
    }
}

//删除链表中所有值为x的节点，并返回已删除的节点的个数
int removeValueEqualsTo(Node* &first, int x) {
    if (first == NULL) return 0;
    int cnt = 0;
    //先将第一个节点当成是头结点，对剩下的节点按照带头结点的单链表进行处理
    Node* p = first;
    while (p->next != first) {    //因为是循环链表，这里循环中止的条件跟普通单链表不一样
        if (p->next->data == x) {
            Node* temp = p->next;
            p->next = temp->next;
            delete temp;
            cnt++;
        }
        else {
            p = p->next;
        }
    }
    //再对第一个节点进行处理
    if (first->data == x) {
        if (first->next == first) {    //如果此时只剩一个节点
            delete first;
            first = NULL;
        }
        else {
            //前面的while循环执行完，指针p指向链表最后一个节点
            //在循环链表中删除第一个节点相当于是删除最后一个节点(指针p)的后继节点
            Node* temp = first;
            p->next = first->next;
            first = first->next;
            delete temp;
        }
        cnt++;
    }
    return cnt;
}

void printLinkList(Node* first) {
    if (first == NULL) {
        printf("链表为空\n");
        return;
    }

    printf("%d ", first->data);    //先手动输出第一个节点
    //然后把第一个节点当成是头节点，输出剩下的
    for (Node* p = first->next; p != first; p = p->next) {
        printf("%d ", p->data);
    }

    // 也可以使用do-while循环
    //Node* p = first;
    //do {
    //    printf("%d ", p->data);
    //    p = p->next;
    //} while (p != first);

    printf("\n");
}

void test_createLinkList_rearInsertion() {
    printf("对 createLinkList_rearInsertion 进行测试:\n");
    int A[] = { 1,2,3 };
    Node* L1 = createLinkList_rearInsertion(A, 3);
    printLinkList(L1);
    Node* L2 = createLinkList_rearInsertion(A, 2);
    printLinkList(L2);
    Node* L3 = createLinkList_rearInsertion(A, 1);
    printLinkList(L3);
    Node* L4 = createLinkList_rearInsertion(A, 0);
    printLinkList(L4);
    printf("-----------------------------------\n");
}

void test_insertAt() {
    printf("对 insertAt 进行测试:\n");
    Node* first = NULL;

    printf("在下标0插入元素10:\n");
    insertAt(first, 0, 10);
    printLinkList(first);

    printf("在下标0插入元素20:\n");
    insertAt(first, 0, 20);
    printLinkList(first);

    printf("在下标2插入元素30:\n");
    insertAt(first, 2, 30);
    printLinkList(first);

    printf("尝试在下标4插入元素40:\n");
    try {
        insertAt(first, 4, 40);
    }
    catch (exception e) {
        printf("%s\n", e.what());
    }

    printf("-----------------------------------\n");
}

void test_removeAt() {
    printf("对 removeAt 进行测试:\n");

    int A[] = { 1,2,3,4 };
    Node* first = createLinkList_rearInsertion(A, sizeof(A) / sizeof(int));
    printf("初始链表为:\n");
    printLinkList(first);

    printf("尝试删除下标4的元素:\n");
    try {
        removeAt(first, 4);
    }
    catch (exception e) {
        printf("%s\n", e.what());
    }

    printf("删除下标2的元素:\n");
    removeAt(first, 2);
    printLinkList(first);

    printf("删除下标2的元素:\n");
    removeAt(first, 2);
    printLinkList(first);

    printf("删除下标0的元素:\n");
    removeAt(first, 0);
    printLinkList(first);

    printf("删除下标0的元素:\n");
    removeAt(first, 0);
    printLinkList(first);

    printf("-----------------------------------\n");
}

void test_removeValueEqualsTo() {
    printf("对 removeValueEqualsTo 进行测试:\n");

    int A[] = { 2,2,2,2 };
    Node* first = createLinkList_rearInsertion(A, sizeof(A) / sizeof(int));
    printf("初始链表为:\n");
    printLinkList(first);

    printf("删除值为2的元素:\n");
    int cnt = removeValueEqualsTo(first, 2);
    printLinkList(first);
    printf("cnt = %d\n", cnt);
    printf("-----------------------------------\n");
}

int main() {
    //test_createLinkList_rearInsertion();
    //test_insertAt();
    //test_removeAt();
    test_removeValueEqualsTo();
    return 0;
}

补充：链表排序

选择排序

sorted         unsorted
----------  ------------
             r

#include <iostream>
#include <algorithm>
#include <initializer_list>
using namespace std;

struct Node {
    int data;
    Node* next;

    Node(int x = 0) :data(x), next(NULL) {}
};

void selectionSort(Node* head) {
    //链表前半部分已排序，后半部分未排序
    //r指针指向未排序部分节点的第一个
    //初始时所有节点（不含头节点）都属于未排序部分
    Node* r = head->next;
    while (r != NULL) {
        Node* minNode = r;
        for (Node* p = r; p != NULL; p = p->next) {
            if (p->data < minNode->data) {
                minNode = p;
            }
        }
        swap(r->data, minNode->data);
        r = r->next;
    }
}

void printLinkList(Node* head) {
    if (head->next == NULL) {
        printf("empty\n");
        return;
    }
    for (Node* p = head->next; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}

void test(const initializer_list<int> &il) {
    static int cnt = 0;
    printf("-------------------------------\n");
    printf("测试用例 #%d:\n", ++cnt);

    Node* head = new Node();
    Node* rear = head;
    for (int x : il) {
        rear->next = new Node(x);
        rear = rear->next;
    }
    printLinkList(head);
    selectionSort(head);
    printLinkList(head);
}

int main() {
    test({ 2,5,3,7 });
    test({ 2,1,4,3 });
    test({ 3,2,1 });
    test({ 1 });
    test({ 2, -1 });
    test({ });

    return 0;
}

冒泡排序

unsorted       sorted
----------  ------------
             r

#include <iostream>
#include <algorithm>
#include <initializer_list>
using namespace std;

struct Node {
    int data;
    Node* next;

    Node(int x = 0) :data(x), next(NULL) {}
};

void bubbleSort(Node* head) {
    //链表前半部分未排序，后半部分已排序
    //r指针指向已排序部分节点的第一个
    Node* r = NULL;    //初始时已排序部分为空
    while (r != head->next) {
        bool isChanged = false;
        Node* p = head->next;
        while (p->next != r) {
            if (p->data > p->next->data) {
                swap(p->data, p->next->data);
                isChanged = true;
            }
            p = p->next;
        }
        if (isChanged == false) break;
        r = p;
    }
}

void printLinkList(Node* head) {
    if (head->next == NULL) {
        printf("empty\n");
        return;
    }
    for (Node* p = head->next; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}

void test(const initializer_list<int> &il) {
    static int cnt = 0;
    printf("-------------------------------\n");
    printf("测试用例 #%d:\n", ++cnt);

    Node* head = new Node();
    Node* rear = head;
    for (int x : il) {
        rear->next = new Node(x);
        rear = rear->next;
    }
    printLinkList(head);
    bubbleSort(head);
    printLinkList(head);
}

int main() {
    test({ 2,5,3,7 });
    test({ 2,1,4,3 });
    test({ 3,2,1 });
    test({ 1 });
    test({ 2, -1 });
    test({ });

    return 0;
}

插入排序

sorted         unsorted
----------  ------------
         r  r.next

#include <iostream>
#include <algorithm>
#include <initializer_list>
using namespace std;

struct Node {
    int data;
    Node* next;

    Node(int x = 0) :data(x), next(NULL) {}
};

void insertionSort(Node* head) {
    Node* r = head;
    while (r->next != NULL) {
        //查找r->next节点应该插入的位置
        Node* p = head;
        while (p->next->data < r->next->data) {
            p = p->next;
        }
        //此时应将r后面的节点(记为temp)插入到p节点的后面
        if (p == r) {
            r = r->next;
            continue;
        }
        Node* temp = r->next;
        //先将temp从原链表中移除
        r->next = temp->next;
        //再将temp插入p的后面
        temp->next = p->next;
        p->next = temp;
    }
}

void printLinkList(Node* head) {
    if (head->next == NULL) {
        printf("empty\n");
        return;
    }
    for (Node* p = head->next; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}

void test(const initializer_list<int> &il) {
    static int cnt = 0;
    printf("-------------------------------\n");
    printf("测试用例 #%d:\n", ++cnt);

    Node* head = new Node();
    Node* rear = head;
    for (int x : il) {
        rear->next = new Node(x);
        rear = rear->next;
    }
    printLinkList(head);
    insertionSort(head);
    printLinkList(head);
}

int main() {
    test({ 2,5,3,7 });
    test({ 2,1,4,3 });
    test({ 3,2,1 });
    test({ 1 });
    test({ 2, -1 });
    test({ });

    return 0;
}

抽象数据类型（ADT）

各种数据结构都可看作是由若干数据项组成的集合，同时对数据项定义一组标准的操作。现代数据结构普遍遵从“信息隐藏”的理念，通过统一接口和内部封装，分层次从整体上加以设计、实现与使用。

所谓封装，就是将数据项与相关的操作结合为一个整体，并将其从外部的可见性划分为若干级别，从而将数据结构的外部特性与其内部实现相分离，提供一致且标准的对外接口，隐藏内部的实现细节。于是，数据集合及其对应的操作可超脱于具体的程序设计语言、具体的实现方式，即构成所谓的抽象数据类型（abstract data type, ADT）。抽象数据类型的理论催生了现代面向对象的程序设计语言，而支持封装也是此类语言的基本特征。

线性表是一个抽象数据类型，它定义了一组元素（称为集合），这些元素在逻辑上应满足线性关系。同时也定义了对该集合的一些常用操作，比如查找、插入、删除等。

线性表的具体实现有两种实现方式，顺序存储和链式存储，由于实现的方式不同，其操作的效率也不一样。