回顾数组

时间复杂度:

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

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

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

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

改变存储策略

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

单向链表

节点定义

C++写法

  1. struct Node { //C++写法
  2. int data;
  3. Node* next;
  4. //构造函数
  5. Node(int x = 0) { data = x; next = NULL; }
  6. };
  7. int main() {
  8. Node* temp1 = new Node(1);
  9. Node* temp2 = new Node(2);
  10. temp1->next = temp2;
  11. }

C语言写法

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef struct Node { //C语言写法
  4. int data;
  5. struct Node* next;
  6. }Node;
  7. Node* createNode(int data) {
  8. Node* temp = (Node*)malloc(sizeof(Node));
  9. temp->data = data;
  10. temp->next = NULL;
  11. return temp;
  12. }
  13. int main() {
  14. Node* temp1 = createNode(1);
  15. Node* temp2 = createNode(2);
  16. temp1->next = temp2;
  17. }

关于头结点

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

链表定义

  1. struct LinkList {
  2. Node* head; //头节点,必须
  3. //Node* rear; //尾指针,指向链表最后一个节点,可选
  4. //int size; //链表节点个数,可选
  5. LinkList() { //构造函数,链表创建时的初始化操作
  6. head = new Node(); //创建头结点
  7. //rear = head; //尾指针指向头结点
  8. //size = 0;
  9. }
  10. };
  11. int main() {
  12. LinkList* L = new LinkList();
  13. }

使用头插法建立链表

1532966189624

  1. //头插法建立链表
  2. LinkList* createLinklist1(int A[], int n) {
  3. LinkList* L = new LinkList();
  4. for (int i = 0; i < n; i++) {
  5. Node* temp = new Node(A[i]);
  6. temp->next = L->head->next;
  7. L->head->next = temp;
  8. }
  9. return L;
  10. }

使用尾插法建立链表

1532966334497

  1. //尾插法建立链表
  2. LinkList* createLinklist2(int A[], int n) {
  3. LinkList* L = new LinkList();
  4. Node* rear = L->head; //创建尾指针
  5. for (int i = 0; i < n; i++) {
  6. Node* temp = new Node(A[i]);
  7. rear->next = temp;
  8. rear = rear->next; //更新尾指针
  9. }
  10. return L;
  11. }

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

  1. int getSize(LinkList* L) {
  2. int cnt = 0;
  3. for (Node* p = L->head->next; p != NULL; p = p->next) {
  4. cnt++;
  5. }
  6. return cnt;
  7. }
  8. void printLinkList(LinkList* L) {
  9. for (Node* p = L->head->next; p != NULL; p = p->next) {
  10. printf("%d ", p->data);
  11. }
  12. printf("\n");
  13. }

查找

查找指定值节点位置

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

访问第i个节点

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

插入

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

1532965858870

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

在下标i处插入一个节点

1565270326383

  1. //在下标i节点处插入一个节点e,并返回新插入节点的指针
  2. //i从0开始计数,不包括头结点(与数组的操作统一)
  3. //即在下标i节点的前面插入一个节点e
  4. Node* insertAt(LinkList* L, int i, int e) {
  5. Node* p = L->head;
  6. while (i--) { //p向后移动i次
  7. p = p->next;
  8. if (p == NULL) {
  9. printf("越界了,插入失败\n");
  10. return NULL;
  11. }
  12. }
  13. //return insertAfter(p, e);
  14. Node* temp = new Node(e);
  15. temp->next = p->next;
  16. p->next = temp;
  17. return temp;
  18. }

删除

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

删除节点p的后继节点

1532965552954

  1. int removeNodeAfter(Node* p) { //删除指定节点的后继节点,并返回删除节点的值
  2. if (p->next == NULL) return -1;
  3. Node* temp = p->next;
  4. int ret = temp->data;
  5. p->next = temp->next;
  6. delete temp; //free(temp);
  7. return ret;
  8. }

删除指定位置节点

  1. //给定节点t的地址,在链表中删除该节点
  2. int removeNode(LinkList* L, Node* t) {
  3. Node* p;
  4. //找到节点t的前驱节点p
  5. for (p = L->head; p != NULL; p = p->next) {
  6. if (p->next == t) break;
  7. }
  8. //return deleteNodeAfter(p);
  9. int ret = t->data;
  10. p->next = t->next;
  11. delete t;
  12. return ret;
  13. }

删除下标i处的节点

  1. //删除下标i节点,并返回删除节点的值
  2. //即删除下标i-1节点的后一个节点
  3. int removeAt(LinkList* L, int i) {
  4. Node* p = L->head;
  5. //p向后移动i次,最终p指向带删除节点的前驱节点
  6. while (i-- && p->next != NULL) {
  7. p = p->next;
  8. }
  9. if (p->next == NULL) {
  10. printf("越界了,删除失败\n");
  11. return -1;
  12. }
  13. //return removeAfter(p);
  14. Node* temp = p->next;
  15. int ret = temp->data;
  16. p->next = temp->next;
  17. delete temp;
  18. return ret;
  19. }

完整代码

  1. #include <cstdio>
  2. struct Node {
  3. int data;
  4. Node* next;
  5. //构造函数,将该节点的data赋值为x(默认为0),next置为NULL
  6. Node(int x = 0) { data = x; next = NULL; }
  7. };
  8. struct LinkList {
  9. Node* head; //头节点,必须
  10. //构造函数,将链表初始化为仅含头结点的空链表
  11. LinkList() {
  12. head = new Node(); //创建头结点
  13. }
  14. };
  15. //头插法建立链表
  16. LinkList* createLinklist1(int A[], int n) {
  17. LinkList* L = new LinkList();
  18. for (int i = 0; i < n; i++) {
  19. Node* temp = new Node(A[i]);
  20. temp->next = L->head->next;
  21. L->head->next = temp;
  22. }
  23. return L;
  24. }
  25. //尾插法建立链表
  26. LinkList* createLinklist2(int A[], int n) {
  27. LinkList* L = new LinkList();
  28. Node* rear = L->head; //创建尾指针
  29. for (int i = 0; i < n; i++) {
  30. Node* temp = new Node(A[i]);
  31. rear->next = temp;
  32. rear = rear->next; //更新尾指针
  33. }
  34. return L;
  35. }
  36. //在链表中查找第一个值为x的节点,并返回该节点的指针,未找到则返回NULL
  37. Node* findElem(LinkList* L, int x) {
  38. for (Node* p = L->head->next; p != NULL; p = p->next) {
  39. if (p->data == x) {
  40. return p;
  41. }
  42. }
  43. return NULL;
  44. }
  45. //访问第i个节点(i从0开始计数)
  46. int getNodeAt(LinkList* L, int i) {
  47. int cnt = 0;
  48. for (Node* p = L->head->next; p != NULL; p = p->next) {
  49. if (cnt == i) return p->data;
  50. cnt++;
  51. }
  52. printf("越界了\n");
  53. return -1; //越界了
  54. }
  55. //在指定节点后面插入节点e,并返回新插入节点的位置
  56. Node* insertAfter(Node* p, int e) {
  57. Node* temp = new Node(e);
  58. temp->next = p->next;
  59. p->next = temp;
  60. return temp;
  61. }
  62. //在下标i节点处插入一个节点e,并返回新插入节点的指针
  63. //i从0开始计数,不包括头结点(与数组的操作统一)
  64. //即在下标i节点的前面插入一个节点e
  65. Node* insertAt(LinkList* L, int i, int e) {
  66. Node* p = L->head;
  67. while (i--) { //p向后移动i次
  68. p = p->next;
  69. if (p == NULL) {
  70. printf("越界了,插入失败\n");
  71. return NULL;
  72. }
  73. }
  74. //return insertAfter(p, e);
  75. Node* temp = new Node(e);
  76. temp->next = p->next;
  77. p->next = temp;
  78. return temp;
  79. }
  80. //删除指定节点的后继节点,并返回删除节点的值
  81. int removeAfter(Node* p) {
  82. if (p->next == NULL) return -1;
  83. Node* temp = p->next;
  84. int ret = temp->data;
  85. p->next = temp->next;
  86. delete temp;
  87. return ret;
  88. }
  89. //删除下标i节点,并返回删除节点的值
  90. //即删除下标i-1节点的后一个节点
  91. int removeAt(LinkList* L, int i) {
  92. Node* p = L->head;
  93. while (i-- && p->next != NULL) { //p向后移动i次
  94. p = p->next;
  95. }
  96. if (p->next == NULL) {
  97. printf("越界了,删除失败\n");
  98. return -1;
  99. }
  100. //return removeAfter(p);
  101. if (p->next == NULL) return -1;
  102. Node* temp = p->next;
  103. int ret = temp->data;
  104. p->next = temp->next;
  105. delete temp;
  106. return ret;
  107. }
  108. //给定节点t的地址,在链表中删除该节点
  109. int removeNode(LinkList* L, Node* t) {
  110. Node* p;
  111. for (p = L->head; p != NULL; p = p->next) { //找到节点t的前驱节点p
  112. if (p->next == t) break;
  113. }
  114. //return deleteNodeAfter(p);
  115. int ret = t->data;
  116. p->next = t->next;
  117. delete t;
  118. return ret;
  119. }
  120. int getSize(LinkList* L) {
  121. int cnt = 0;
  122. for (Node* p = L->head->next; p != NULL; p = p->next) {
  123. cnt++;
  124. }
  125. return cnt;
  126. }
  127. void printLinkList(LinkList* L) {
  128. for (Node* p = L->head->next; p != NULL; p = p->next) {
  129. printf("%d ", p->data);
  130. }
  131. printf("\n\n");
  132. }
  133. int main() {
  134. int A[] = { 1,2,3,4,5 };
  135. int N = sizeof(A) / sizeof(int);
  136. printf("尾插法创建一个链表,记为L2:\n");
  137. LinkList* L2 = createLinklist2(A, N);
  138. printLinkList(L2);
  139. printf("头插法创建一个链表,记为L1:\n");
  140. LinkList* L1 = createLinklist1(A, N);
  141. printLinkList(L1);
  142. printf("以下均是对链表L1进行操作:\n\n");
  143. printf("在下标6处尝试插入节点10:\n");
  144. insertAt(L1, 6, 10);
  145. printf("\n");
  146. insertAt(L1, 5, 10);
  147. printf("在下标5处插入节点10:\n");
  148. printLinkList(L1);
  149. insertAt(L1, 0, 11);
  150. printf("在下标0处插入节点11:\n");
  151. printLinkList(L1);
  152. Node* p = findElem(L1, 3);
  153. printf("查找第一个值为3的节点,将该节点记为p\n");
  154. Node* p1 = insertAfter(p, 20);
  155. printf("在节点p后面插入一个节点20,并将新插入的节点记为p1:\n");
  156. printLinkList(L1);
  157. removeNode(L1, p1->next);
  158. printf("删除p1节点后的节点:\n");
  159. printLinkList(L1);
  160. removeAfter(p1);
  161. printf("再删除p1节点后的节点:\n");
  162. printLinkList(L1);
  163. removeAt(L1, 0);
  164. printf("删除下标0节点:\n");
  165. printLinkList(L1);
  166. printf("尝试删除下标5节点:");
  167. removeAt(L1, 5);
  168. printf("\n");
  169. removeAt(L1, 4);
  170. printf("删除下标4节点:\n");
  171. printLinkList(L1);
  172. printf("访问下标3的节点:");
  173. printf("%d\n\n", getNodeAt(L1, 3));
  174. return 0;
  175. }

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

写法1:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef struct Node {
  4. int data;
  5. struct Node* next;
  6. } Node;
  7. Node* createNode(int data) {
  8. Node* temp = (Node*)malloc(sizeof(Node));
  9. temp->data = data;
  10. temp->next = NULL;
  11. return temp;
  12. }
  13. //创建一个空链表
  14. Node* createLinklist0() {
  15. Node* head = createNode(0);
  16. return head;
  17. }
  18. //头插法建立链表
  19. Node* createLinklist1(int A[], int n) {
  20. Node* head = createNode(0);
  21. for (int i = 0; i < n; i++) {
  22. Node* temp = createNode(A[i]);
  23. temp->next = head->next;
  24. head->next = temp;
  25. }
  26. return head;
  27. }
  28. //尾插法建立链表
  29. Node* createLinklist2(int A[], int n) {
  30. Node* head = createNode(0);
  31. Node* rear = head; //创建尾指针
  32. for (int i = 0; i < n; i++) {
  33. Node* temp = createNode(A[i]);
  34. rear->next = temp;
  35. rear = rear->next; //移动尾指针
  36. }
  37. return head;
  38. }
  39. Node* findElem(Node* L, int x) {
  40. for (Node* p = L->next; p != NULL; p = p->next) {
  41. if (p->data == x) {
  42. return p;
  43. }
  44. }
  45. return NULL;
  46. }
  47. //在指定节点后面插入节点,并返回新插入节点的位置
  48. Node* insertNodeAfter(Node* p, int x) {
  49. Node* temp = createNode(x);
  50. temp->next = p->next;
  51. p->next = temp;
  52. return temp;
  53. }
  54. //删除指定节点的后继节点,并返回删除节点的值
  55. int deleteNodeAfter(Node* p) {
  56. if (p->next == NULL) return -1;
  57. Node* temp = p->next;
  58. int ret = temp->data;
  59. p->next = temp->next;
  60. free(temp);
  61. return ret;
  62. }
  63. //删除指定节点,并返回删除节点的值
  64. int deleteNode(Node* L, Node* t) {
  65. Node* p;
  66. for (p = L; p != NULL; p = p->next) { //找到节点t的前驱节点p
  67. if (p->next == t) break;
  68. }
  69. //return deleteNodeAfter(p);
  70. int ret = t->data;
  71. p->next = t->next;
  72. free(t);
  73. return ret;
  74. }
  75. int getLinklistSize(Node* head) {
  76. int cnt = 0;
  77. for (Node* p = head->next; p != NULL; p = p->next) {
  78. cnt++;
  79. }
  80. return cnt;
  81. }
  82. void printLinklist(Node* head) {
  83. for (Node* p = head->next; p != NULL; p = p->next) {
  84. printf("%d ", p->data);
  85. }
  86. printf("\n");
  87. }
  88. int main() {
  89. int A[] = { 1,2,3,4,5 };
  90. int N = sizeof(A) / sizeof(int);
  91. Node* head = createLinklist1(A, N); //头插法
  92. printLinklist(head);
  93. Node* head2 = createLinklist2(A, N); //尾插法
  94. printLinklist(head2);
  95. Node* p = findElem(head, 3); //找到节点3的位置
  96. Node* p1 = insertNodeAfter(p, 10); //在节点3后面插入一个节点10
  97. printLinklist(head);
  98. deleteNode(head, p1->next);
  99. printLinklist(head);
  100. deleteNode(head, p1->next);
  101. printLinklist(head);
  102. return 0;
  103. }

写法2:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef struct Node {
  4. int data;
  5. struct Node* next;
  6. } Node;
  7. typedef Node* Linklist; //关键语句
  8. Node* createNode(int data) {
  9. Node* temp = (Node*)malloc(sizeof(Node));
  10. temp->data = data;
  11. temp->next = NULL;
  12. return temp;
  13. }
  14. //创建一个空链表
  15. Linklist createLinklist0() {
  16. Node* head = createNode(0);
  17. return head;
  18. }
  19. //头插法建立链表
  20. Linklist createLinklist1(int A[], int n) {
  21. Node* head = createNode(0);
  22. for (int i = 0; i < n; i++) {
  23. Node* temp = createNode(A[i]);
  24. temp->next = head->next;
  25. head->next = temp;
  26. }
  27. return head;
  28. }
  29. Node* findElem(Linklist L, int x) {
  30. for (Node* p = L->next; p != NULL; p = p->next) {
  31. if (p->data == x) {
  32. return p;
  33. }
  34. }
  35. return NULL;
  36. }
  37. //在指定节点后面插入节点,并返回新插入节点的位置
  38. Node* insertNodeAfter(Node* p, int x) {
  39. Node* temp = createNode(x);
  40. temp->next = p->next;
  41. p->next = temp;
  42. return temp;
  43. }
  44. void printLinklist(Linklist L) {
  45. for (Node* p = L->next; p != NULL; p = p->next) {
  46. printf("%d ", p->data);
  47. }
  48. printf("\n");
  49. }
  50. int main() {
  51. int A[] = { 1,2,3,4,5 };
  52. int N = sizeof(A) / sizeof(int);
  53. Linklist L = createLinklist1(A, N); //头插法
  54. printLinklist(L);
  55. Node* p = findElem(L, 3); //找到节点3的位置
  56. Node* p1 = insertNodeAfter(p, 10); //在节点3后面插入一个节点10
  57. printLinklist(L);
  58. return 0;
  59. }

备注:

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)。抽象数据类型的理论催生了现代面向对象的程序设计语言,而支持封装也是此类语言的基本特征。

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

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