Jinyun's Notes
笔记 标签 分类 文档 友链 关于
Jinyun's Notes

目录

线性表

 收录于
   约 6565 字   预计阅读 14 分钟 

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是 n 个具有相同特性的数据元素的有限序列。

基本概念

定义

线性表（Linear List）：是一种线性结构，它是由 n(n>=0) 个数据元素组成的有穷序列，数据元素又称结点。结点个数 n 称为表长。

  • 当 n=0 时，线性表不含任何数据元素，称为空表，记为 () 或 ø；
  • 当 n>0 时，线性表通常表示成 (a1, a2, …, an)，a1 称为起始结点，an 称为终端结点。对任意一对相邻结点 ai 和 ai+1 (1<=i<n)，ai 称为 ai+1 的直接前驱，ai+1 称为 ai 的直接后继；

基本特征

线性表基本特征：线性表中结点具有一对一的关系，如果结点数不为零，则除起始结点没有直接前驱外，其它每个结点有且仅有一个直接前驱；除终点结点没有直接后继外，其它每个结点有且仅有一个直接后继。

线性表的顺序存储

顺序表

顺序表：线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表中的各数据元素，用这种存储形式存储的线性表称为顺序表。

设 a1 的存储地址为 Loc(a1)，每个数据元素占 d 个存储单元，则第 i 个数据元素的地址为：Loc(ai)=Loc(a1)+(i-1)*d (1≤i≤n)。

顺序表的基本操作

  • 创建空表：SeqList *CreateSeqList();；
  • 插入元素：int InsertSeqList(SeqList *list, int pos, int value);；
  • 删除元素：int DeleteSeqList(SeqList *list, int pos);；
  • 更新元素：int UpdateSeqList(SeqList *list, int pos, int value);；
  • 查找元素：int SearchSeqList(SeqList *list, int pos);；
  • 定位元素：int LocateSeqList(SeqList *list, int value);；
  • 求表长度：int GetSeqListLength(SeqList *list);；
  • 合并有序表：void MergeSeqList(SeqList p, SeqList q, SeqList *t)；
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215

#include <gtest/gtest.h>
#include <stdbool.h>
#include <stdlib.h>

const int MaxSize = 100;

typedef struct {
  int data[MaxSize]; // 存放数据的数组
  int length;        // 顺序表的实际长度
} SeqList;           // 顺序表类型名为 SeqList

SeqList *CreateSeqList();
bool InsertSeqList(SeqList *list, int pos, int value);
bool DeleteSeqList(SeqList *list, int pos);
bool UpdateSeqList(SeqList *list, int pos, int value);
int SearchSeqList(SeqList *list, int pos);
int LocateSeqList(SeqList *list, int value);
int GetSeqListLength(SeqList *list);

SeqList *CreateSeqList() {
  SeqList *list = (SeqList *)malloc(sizeof(SeqList));
  list->length = 0;
  return list;
}

bool InsertSeqList(SeqList *list, int pos, int value) {
  if (list->length >= MaxSize) {
    return false;
  }
  if (pos < 1 || pos > list->length + 1) {
    return false;
  }
  for (int i = list->length; i >= pos; i--) {
    list->data[i] = list->data[i - 1];
  }
  list->data[pos - 1] = value;
  list->length++;
  return true;
}

bool DeleteSeqList(SeqList *list, int pos) {
  if (list->length == 0) {
    return false;
  }
  if (pos < 1 || pos > list->length) {
    return false;
  }
  for (int i = pos - 1; i < list->length - 1; i++) {
    list->data[i] = list->data[i + 1];
  }
  list->length--;
  return true;
}

bool UpdateSeqList(SeqList *list, int pos, int value) {
  if (list->length == 0) {
    return false;
  }
  if (pos < 1 || pos > list->length) {
    return false;
  }
  list->data[pos - 1] = value;
  return true;
}

int SearchSeqList(SeqList *list, int pos) {
  if (list->length == 0) {
    return 0;
  }
  if (pos < 1 || pos > list->length) {
    return 0;
  }
  return list->data[pos - 1];
}

int LocateSeqList(SeqList *list, int value) {
  if (list->length == 0) {
    return 0;
  }
  for (int i = 0; i < list->length; i++) {
    if (list->data[i] == value) {
      return i + 1;
    }
  }
  return 0;
}

int GetSeqListLength(SeqList *list) { return list->length; }

void MergeSeqList(SeqList p, SeqList q, SeqList *t) {
  int i = 0, j = 0, k = 0;
  while (i < p.length && j < q.length) {
    if (p.data[i] < q.data[j]) {
      t->data[k++] = p.data[i++];
    } else {
      t->data[k++] = q.data[j++];
    }
  }
  while (i < p.length) {
    t->data[k++] = p.data[i++];
  }
  while (j < q.length) {
    t->data[k++] = q.data[j++];
  }
  t->length = k;
}

TEST(TestSeqList, CreateSeqList) {
  SeqList *list = CreateSeqList();
  ASSERT_EQ(0, GetSeqListLength(list));
  ASSERT_EQ(0, list->data[list->length]);
}

TEST(TestSeqList, InsertSeqList) {
  SeqList *list = CreateSeqList();
  ASSERT_TRUE(InsertSeqList(list, 1, 1));
  ASSERT_EQ(1, GetSeqListLength(list));

  ASSERT_TRUE(InsertSeqList(list, 2, 2));
  ASSERT_EQ(2, GetSeqListLength(list));

  ASSERT_TRUE(InsertSeqList(list, 3, 3));
  ASSERT_EQ(3, GetSeqListLength(list));
  ASSERT_TRUE(InsertSeqList(list, 4, 4));

  ASSERT_FALSE(InsertSeqList(list, -1, 1 - MaxSize));
  ASSERT_FALSE(InsertSeqList(list, MaxSize + 1, MaxSize + 1));
  ASSERT_TRUE(InsertSeqList(list, 4, 44));

  list->length = 100;
  ASSERT_FALSE(InsertSeqList(list, 100, 100));
}

TEST(TestSeqList, DeleteSeqList) {
  SeqList *list = CreateSeqList();
  ASSERT_FALSE(DeleteSeqList(list, 0));
  ASSERT_FALSE(DeleteSeqList(list, 1 - MaxSize));
  ASSERT_FALSE(DeleteSeqList(list, MaxSize + 1));

  InsertSeqList(list, 1, 1);
  InsertSeqList(list, 2, 2);
  InsertSeqList(list, 3, 3);
  InsertSeqList(list, 4, 4);
  InsertSeqList(list, 5, 5);

  ASSERT_TRUE(DeleteSeqList(list, 1));
  ASSERT_EQ(4, GetSeqListLength(list));

  ASSERT_TRUE(DeleteSeqList(list, 2));
  ASSERT_EQ(3, GetSeqListLength(list));

  ASSERT_FALSE(DeleteSeqList(list, 0));
  ASSERT_TRUE(DeleteSeqList(list, 1));
  ASSERT_TRUE(DeleteSeqList(list, 2));
}

TEST(TestSeqList, UpdateSeqList) {
  SeqList *list = CreateSeqList();
  ASSERT_FALSE(UpdateSeqList(list, 1, 1));

  InsertSeqList(list, 1, 1);
  ASSERT_TRUE(UpdateSeqList(list, 1, 11));
  ASSERT_EQ(1, LocateSeqList(list, 11));
  ASSERT_EQ(11, SearchSeqList(list, 1));
  ASSERT_FALSE(UpdateSeqList(list, 2, 22));
  ASSERT_FALSE(UpdateSeqList(list, -1, 33));
  ASSERT_FALSE(UpdateSeqList(list, 0, 44));
  ASSERT_FALSE(UpdateSeqList(list, MaxSize + 1, 55));
}

TEST(TestSeqList, SearchSeqList) {
  SeqList *list = CreateSeqList();
  ASSERT_EQ(0, SearchSeqList(list, 0));

  InsertSeqList(list, 1, 1);
  UpdateSeqList(list, 1, 11);
  ASSERT_EQ(11, SearchSeqList(list, 1));
  ASSERT_EQ(0, SearchSeqList(list, -1));
  ASSERT_EQ(0, SearchSeqList(list, 0));
  ASSERT_EQ(0, SearchSeqList(list, MaxSize + 1));
}

TEST(TestSeqList, LocateSeqList) {
  SeqList *list = CreateSeqList();
  ASSERT_EQ(0, LocateSeqList(list, 99));

  InsertSeqList(list, 1, 11);
  ASSERT_EQ(1, LocateSeqList(list, 11));

  InsertSeqList(list, 2, 22);
  ASSERT_EQ(2, LocateSeqList(list, 22));
  ASSERT_EQ(0, LocateSeqList(list, -1));
  ASSERT_EQ(0, LocateSeqList(list, 0));
  ASSERT_EQ(0, LocateSeqList(list, MaxSize + 1));
}

TEST(TestSeqList, MergeSeqList) {
  SeqList p, q, t;
  p.length = 5;
  q.length = 5;
  p.data[0] = 1;
  p.data[1] = 2;
  p.data[2] = 3;
  p.data[3] = 4;
  p.data[4] = 5;
  q.data[0] = 6;
  q.data[1] = 7;
  q.data[2] = 8;
  q.data[3] = 9;
  q.data[4] = 10;
  MergeSeqList(p, q, &t);
  for (int i = 0; i < t.length; i++) {
    EXPECT_EQ(i + 1, t.data[i]);
  }
}

顺序表实现算法的分析

  • 建表算法：时间复杂度为 O(n)；
  • 插入算法：最坏情况下，时间复杂度为 O(n)，比较和移动的次数为 n-i+1；平均移动次数为 n/2，时间复杂度为 O(n)；
  • 删除算法：最坏情况下，时间复杂度为 O(n)，比较和移动的次数为 n-1；平均移动次数为 (n-1)/2，时间复杂度为 O(n)；
  • 更新算法：最坏情况下，时间复杂度为 O(n)；
  • 查找算法：按序号查找元素，平均时间复杂度为 O(n)，求表长和读表元素算法的时间复杂度为 O(1)；
  • 定位算法：按域值查找元素，时间复杂度为 O(1)；
  • 合并有序表：算法的时间复杂度是 O(m+n)，其中 m 是 A 的表长，n 是 B 的表长；

线性表的链接存储

为了方便操作，有时在链表的头部加入一个「头结点」，头结点的类型与数据结点一致，标识链表的头指针变量 head 中存放该结点的地址，这样即使是空表，头指针变量 head 也不为空了。头结点的加入使得「第一个结点」的问题不再存在，也使得「空表」和「非空表」的处理一致。头结点的加入完全是为了操作的方便，它的数据域无定义，指针域中存放的是第一个数据结点的地址，当空表时该指针域为空。

单链表

单链表：就是线性表的数据元素用指针链接起来的存储结构，指针表示数据元素之间的逻辑关系。

线性表的链接存储是指它的存储结构是链式的，常见的链式存储结构有 单链表、循环链表 和 双向循环链表。

单链表中的 data 部分称为 数据域，用于存储线性表的一个数据元素，next 部分称为 指针或链域，用于存放一个指针，该指针指向本结点所含数据元素的直接后继结点。

所有结点通过指针链接形成 链表（Link List），head 称为头指针变量，该变量的值是指向单链表的第一个结点的指针。尾结点指针域的值 NULL 称为空指针，它不指向任何结点，表示链表结束。如果 head 等于 NULL，则表示该链表无任何结点，是空单链表。

单链表的第一个结点之前增设一个类型相同的结点，称之为 头结点，其它结点称为 表结点。表结点中的第一个和最后一个结点分别就是首结点和尾结点。

单链表基本操作：

  • 创建空表：LinkedList CreateLinkedList();；
  • 插入元素：void InsertLinkedList(LinkedList head, int pos, int value);；
  • 删除元素：void DeleteLinkedList(LinkedList head, int value);；
  • 更新元素：void UpdateLinkedList(LinkedList head, int pos, int value);；
  • 查找元素：Node *SearchLinkedList(LinkedList head, int pos);；
  • 定位元素：int LocateLinkedList(LinkedList head, int value);；
  • 求表长度：int GetLinkedListLength(LinkedList head);；

单链表算法分析：

  • 建表算法：时间复杂度为 O(n)；
  • 插入算法：时间复杂度为 O(n)；
  • 删除算法：时间复杂度为 O(n)；
  • 查找算法：按序号查找元素，时间复杂度为 O(n)，求表长和读表元素算法的时间复杂度为 O(n)；
  • 定位算法：按域值查找元素，时间复杂度为 O(n)；
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249

#include <gtest/gtest.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct node {
  int data;          // 数据域
  struct node *next; // 指针域
} Node, *SinglyLinkedList;

SinglyLinkedList CreateSinglyLinkedList();
bool InsertSinglyLinkedList(SinglyLinkedList head, int pos, int value);
bool DeleteSinglyLinkedList(SinglyLinkedList head, int pos);
bool UpdateSinglyLinkedList(SinglyLinkedList head, int pos, int value);
Node *SearchSinglyLinkedList(SinglyLinkedList head, int pos);
int LocateSinglyLinkedList(SinglyLinkedList head, int value);
int GetSinglyLinkedListLength(SinglyLinkedList head);
SinglyLinkedList MergeSinglyLinkedList(SinglyLinkedList a, SinglyLinkedList b);

SinglyLinkedList CreateSinglyLinkedList() {
  SinglyLinkedList head = (SinglyLinkedList)malloc(sizeof(Node));
  if (head == NULL) {
    return NULL;
  }
  head->next = NULL;
  return head;
}

bool InsertSinglyLinkedList(SinglyLinkedList head, int pos, int value) {
  Node *p, *q;
  p = (Node *)malloc(sizeof(Node));
  if (p == NULL) {
    return false;
  }
  p->data = value;
  q = pos == 1 ? head : SearchSinglyLinkedList(head, pos - 1);
  if (q == NULL) {
    return false;
  }
  p->next = q->next;
  q->next = p;
  return true;
}

bool DeleteSinglyLinkedList(SinglyLinkedList head, int pos) {
  if (head == NULL) {
    return false;
  }
  Node *p, *q;
  q = pos == 1 ? head : SearchSinglyLinkedList(head, pos - 1);
  if (q == NULL || q->next == NULL) {
    return false;
  }
  p = q->next;
  q->next = p->next;
  free(p);
  return true;
}

bool UpdateSinglyLinkedList(SinglyLinkedList head, int pos, int value) {
  if (head == NULL) {
    return false;
  }
  Node *node;
  node = pos == 1 ? head : SearchSinglyLinkedList(head, pos - 1);
  if (node == NULL || node->next == NULL) {
    return false;
  }
  node->next->data = value;
  return true;
}

Node *SearchSinglyLinkedList(SinglyLinkedList head, int pos) {
  int i = 1;
  if (head == NULL || pos < i) {
    return NULL;
  }
  Node *p = head->next;
  while (p != NULL && i < pos) {
    p = p->next;
    i++;
  }
  return i == pos ? p : NULL;
}

int LocateSinglyLinkedList(SinglyLinkedList head, int value) {
  if (head == NULL) {
    return 0;
  }
  int i = 0;
  Node *p = head->next;
  while (p != NULL && p->data != value) {
    p = p->next;
    i++;
  }
  return i;
}

int GetSinglyLinkedListLength(SinglyLinkedList head) {
  if (head == NULL) {
    return 0;
  }
  int cnt = 0;
  SinglyLinkedList p = head->next;
  while (p != NULL) {
    p = p->next;
    cnt++;
  }
  return cnt;
}

SinglyLinkedList MergeSinglyLinkedList(SinglyLinkedList a, SinglyLinkedList b) {
  if (a == NULL) {
    return b;
  } else if (b == NULL) {
    return a;
  }
  SinglyLinkedList head, tail;
  Node *p, *q, *t;
  p = a;
  q = b;
  head = p->data <= q->data ? a : b;
  tail = head;
  p = p->next;
  q = q->next;
  while (p && q) {
    if (p->data <= q->data) {
      t = p;
      p = p->next;
    } else {
      t = q;
      q = q->next;
    }
    tail->next = t;
    tail = t;
  }
  if (p) {
    tail->next = p;
  } else if (q) {
    tail->next = q;
  }
  return head;
}

TEST(TestSinglyLinkedList, CreateSinglyLinkedList) {
  SinglyLinkedList head = CreateSinglyLinkedList();
  EXPECT_FALSE(head == NULL);
  EXPECT_EQ(NULL, head->next);
  EXPECT_EQ(0, GetSinglyLinkedListLength(head));
}

TEST(TestSinglyLinkedList, InsertSinglyLinkedList) {
  SinglyLinkedList head = CreateSinglyLinkedList();
  EXPECT_FALSE(InsertSinglyLinkedList(head, 0, 0));
  EXPECT_TRUE(InsertSinglyLinkedList(head, 1, 1));
  EXPECT_TRUE(InsertSinglyLinkedList(head, 2, 2));
  EXPECT_EQ(2, GetSinglyLinkedListLength(head));
}

TEST(TestSinglyLinkedList, DeleteSinglyLinkedList) {
  SinglyLinkedList head = CreateSinglyLinkedList();
  InsertSinglyLinkedList(head, 1, 1);
  InsertSinglyLinkedList(head, 2, 2);
  InsertSinglyLinkedList(head, 3, 3);
  EXPECT_EQ(3, GetSinglyLinkedListLength(head));

  EXPECT_TRUE(DeleteSinglyLinkedList(head, 3));
  EXPECT_TRUE(DeleteSinglyLinkedList(head, 2));
  EXPECT_TRUE(DeleteSinglyLinkedList(head, 1));
  EXPECT_EQ(0, GetSinglyLinkedListLength(head));
  EXPECT_FALSE(DeleteSinglyLinkedList(head, 4));
}

TEST(TestSinglyLinkedList, UpdateSinglyLinkedList) {
  SinglyLinkedList head = CreateSinglyLinkedList();
  InsertSinglyLinkedList(head, 1, 1);
  InsertSinglyLinkedList(head, 2, 2);
  InsertSinglyLinkedList(head, 3, 3);

  EXPECT_TRUE(UpdateSinglyLinkedList(head, 1, 11));
  EXPECT_EQ(11, SearchSinglyLinkedList(head, 1)->data);

  EXPECT_TRUE(UpdateSinglyLinkedList(head, 2, 22));
  EXPECT_EQ(22, SearchSinglyLinkedList(head, 2)->data);
}

TEST(TestSinglyLinkedList, SearchSinglyLinkedList) {
  SinglyLinkedList head = CreateSinglyLinkedList();
  EXPECT_EQ(NULL, SearchSinglyLinkedList(head, 0));
  EXPECT_EQ(NULL, SearchSinglyLinkedList(head, 1));

  InsertSinglyLinkedList(head, 1, 1);
  EXPECT_EQ(1, SearchSinglyLinkedList(head, 1)->data);
}

TEST(TestSinglyLinkedList, LocateSinglyLinkedList) {
  SinglyLinkedList head = CreateSinglyLinkedList();
  EXPECT_EQ(0, LocateSinglyLinkedList(head, 0));
  EXPECT_EQ(0, LocateSinglyLinkedList(head, 1));

  InsertSinglyLinkedList(head, 1, 11);
  EXPECT_EQ(0, LocateSinglyLinkedList(head, 11));

  InsertSinglyLinkedList(head, 2, 22);
  EXPECT_EQ(1, LocateSinglyLinkedList(head, 22));
}

TEST(TestSinglyLinkedList, MergeSinglyLinkedList) {
  SinglyLinkedList a = CreateSinglyLinkedList();
  SinglyLinkedList b = CreateSinglyLinkedList();
  InsertSinglyLinkedList(a, 1, 1);
  InsertSinglyLinkedList(a, 2, 2);
  InsertSinglyLinkedList(a, 3, 3);
  InsertSinglyLinkedList(b, 1, 4);
  InsertSinglyLinkedList(b, 2, 5);
  InsertSinglyLinkedList(b, 3, 6);
  SinglyLinkedList head = MergeSinglyLinkedList(a, b);
  int i = 1;
  SinglyLinkedList node = head->next;
  while (node != NULL) {
    EXPECT_EQ(i, node->data);
    node = node->next;
    i++;
  }

  SinglyLinkedList a1 = CreateSinglyLinkedList();
  InsertSinglyLinkedList(a1, 1, 22);
  Node *t1 = SearchSinglyLinkedList(a1, 1);
  ASSERT_EQ(22, t1->data);

  SinglyLinkedList b1 = CreateSinglyLinkedList();
  InsertSinglyLinkedList(b1, 1, 11);
  Node *t2 = SearchSinglyLinkedList(b1, 1);
  ASSERT_EQ(11, t2->data);

  SinglyLinkedList p1 = MergeSinglyLinkedList(a1, b1);
  ASSERT_EQ(11, p1->next->data);

  SinglyLinkedList a2 = NULL;
  SinglyLinkedList b2 = CreateSinglyLinkedList();
  InsertSinglyLinkedList(b2, 1, 5);
  Node *p2 = MergeSinglyLinkedList(a2, b2);
  ASSERT_EQ(5, p2->next->data);

  SinglyLinkedList a3 = CreateSinglyLinkedList();
  SinglyLinkedList b3 = NULL;
  InsertSinglyLinkedList(a3, 1, 6);
  Node *p3 = MergeSinglyLinkedList(a3, b3);
  ASSERT_EQ(6, p3->next->data);
}

单向循环链表

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209

#include <gtest/gtest.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct node {
  int data;
  struct node *next;
} Node, *SCLinkedList;

SCLinkedList CreateSCLinkedList();
bool InsertSCLinkedList(SCLinkedList head, int pos, int value);
bool DeleteSCLinkedList(SCLinkedList head, int pos);
bool UpdateSCLinkedList(SCLinkedList head, int pos, int value);
Node *SearchSCLinkedList(SCLinkedList head, int pos);
int LocateSCLinkedList(SCLinkedList head, int value);
int GetSCLinkedListLength(SCLinkedList head);

SCLinkedList CreateSCLinkedList() {
  Node *head = (Node *)malloc(sizeof(Node));
  if (head == NULL) {
    return NULL;
  }
  head->next = NULL;
  return head;
}

bool InsertSCLinkedList(SCLinkedList head, int pos, int value) {
  Node *p, *q;
  p = (Node *)malloc(sizeof(Node));
  if (p == NULL) {
    return false;
  }
  p->data = value;
  q = pos == 1 ? head : SearchSCLinkedList(head, pos - 1);
  if (q == NULL) {
    return false;
  }
  p->next = q->next;
  q->next = p;
  return true;
}

bool DeleteSCLinkedList(SCLinkedList head, int pos) {
  if (head == NULL) {
    return false;
  }
  Node *p, *q;
  p = (Node *)malloc(sizeof(Node));
  if (p == NULL) {
    return false;
  }
  q = pos == 1 ? head : SearchSCLinkedList(head, pos - 1);
  if (q == NULL || q->next == NULL) {
    return false;
  }

  p = q->next;
  q->next = p->next;
  free(p);
  return true;
}

bool UpdateSCLinkedList(SCLinkedList head, int pos, int value) {
  if (head == NULL) {
    return false;
  }
  Node *node;
  node = pos == 1 ? head : SearchSCLinkedList(head, pos - 1);
  if (node == NULL) {
    return false;
  }
  node->next->data = value;
  return true;
}

Node *SearchSCLinkedList(SCLinkedList head, int pos) {
  int i = 1;
  if (head == NULL || pos < i) {
    return NULL;
  }
  Node *p, *q;
  p = head->next;
  q = head;
  while (p != NULL && p != q && i < pos) {
    p = p->next;
    i++;
  }
  return i == pos ? p : NULL;
}

int LocateSCLinkedList(SCLinkedList head, int value) {
  if (head == NULL) {
    return 0;
  }
  int i = 0;
  Node *p = head->next;
  while (p != NULL && p != head && p->data != value) {
    p = p->next;
    i++;
  }
  return i;
}

int GetSCLinkedListLength(SCLinkedList head) {
  if (head == NULL) {
    return 0;
  }
  int cnt = 0;
  Node *p = head->next;
  while (p != NULL && p != head) {
    p = p->next;
    cnt++;
  }
  return cnt;
}

TEST(TestSCLinkedList, CreateSCLinkedList) {
  SCLinkedList head = CreateSCLinkedList();
  EXPECT_FALSE(head == NULL);
  EXPECT_EQ(NULL, head->next);
  EXPECT_EQ(0, GetSCLinkedListLength(head));
}

TEST(TestSCLinkedList, InsertSCLinkedList) {
  SCLinkedList head = CreateSCLinkedList();
  EXPECT_EQ(0, GetSCLinkedListLength(head));
  EXPECT_TRUE(InsertSCLinkedList(head, 1, 1));
  EXPECT_EQ(1, GetSCLinkedListLength(head));

  EXPECT_TRUE(InsertSCLinkedList(head, 2, 2));
  EXPECT_EQ(2, GetSCLinkedListLength(head));

  EXPECT_TRUE(InsertSCLinkedList(head, 3, 3));
  EXPECT_EQ(3, GetSCLinkedListLength(head));
}

TEST(TestSCLinkedList, DeleteSCLinkedList) {
  SCLinkedList p = CreateSCLinkedList();
  InsertSCLinkedList(p, 1, 1);
  InsertSCLinkedList(p, 2, 2);
  InsertSCLinkedList(p, 3, 3);

  EXPECT_EQ(3, GetSCLinkedListLength(p));
  EXPECT_TRUE(DeleteSCLinkedList(p, 3));
  EXPECT_EQ(2, GetSCLinkedListLength(p));
  EXPECT_TRUE(DeleteSCLinkedList(p, 2));
  EXPECT_EQ(1, GetSCLinkedListLength(p));
  EXPECT_TRUE(DeleteSCLinkedList(p, 1));
  EXPECT_EQ(0, GetSCLinkedListLength(p));

  SCLinkedList q = CreateSCLinkedList();
  InsertSCLinkedList(q, 1, 1);
  InsertSCLinkedList(q, 2, 2);
  InsertSCLinkedList(q, 3, 3);

  EXPECT_TRUE(DeleteSCLinkedList(q, 2));
  EXPECT_EQ(2, GetSCLinkedListLength(q));
  EXPECT_TRUE(DeleteSCLinkedList(q, 1));
  EXPECT_EQ(1, GetSCLinkedListLength(q));
  EXPECT_FALSE(DeleteSCLinkedList(q, 3));
  EXPECT_EQ(1, GetSCLinkedListLength(q));
  EXPECT_TRUE(DeleteSCLinkedList(q, 1));
  EXPECT_EQ(0, GetSCLinkedListLength(q));
  EXPECT_EQ(NULL, q->next);

  SCLinkedList t = NULL;
  EXPECT_FALSE(DeleteSCLinkedList(t, 1));

  SCLinkedList r = CreateSCLinkedList();
  InsertSCLinkedList(r, 1, 11);
  EXPECT_TRUE(DeleteSCLinkedList(r, 1));
  EXPECT_EQ(NULL, r->next);
}

TEST(TestSCLinkedList, UpdateSCLinkedList) {
  SCLinkedList p = CreateSCLinkedList();
  InsertSCLinkedList(p, 1, 1);
  EXPECT_TRUE(UpdateSCLinkedList(p, 1, 11));
  EXPECT_EQ(11, SearchSCLinkedList(p, 1)->data);

  InsertSCLinkedList(p, 2, 2);
  EXPECT_TRUE(UpdateSCLinkedList(p, 2, 22));
  EXPECT_EQ(22, SearchSCLinkedList(p, 2)->data);
}

TEST(TestSCLinkedList, SearchSCLinkedList) {
  SCLinkedList head = CreateSCLinkedList();
  EXPECT_EQ(NULL, SearchSCLinkedList(head, 0));
  EXPECT_EQ(NULL, SearchSCLinkedList(head, 1));

  InsertSCLinkedList(head, 1, 1);
  EXPECT_EQ(1, SearchSCLinkedList(head, 1)->data);
}

TEST(TestSCLinkedList, LocateSCLinkedList) {
  SCLinkedList p = CreateSCLinkedList();
  EXPECT_EQ(0, LocateSCLinkedList(p, 0));
  EXPECT_EQ(0, LocateSCLinkedList(p, 1));

  InsertSCLinkedList(p, 1, 11);
  EXPECT_EQ(0, LocateSCLinkedList(p, 11));

  InsertSCLinkedList(p, 2, 22);
  EXPECT_EQ(1, LocateSCLinkedList(p, 22));

  SCLinkedList q = NULL;
  EXPECT_EQ(0, LocateSCLinkedList(q, 1));
  EXPECT_EQ(0, GetSCLinkedListLength(q));
}

双链表

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194

#include <gtest/gtest.h>
#include <stdlib.h>

typedef struct node {
  int data;
  struct node *prev; // 前驱结点
  struct node *next; // 后驱结点
} Node, *DoublyLinkedList;

DoublyLinkedList CreateDoublyLinkedList();
bool InsertDoublyLinkedList(DoublyLinkedList head, int pos, int value);
bool DeleteDoublyLinkedList(DoublyLinkedList head, int pos);
bool UpdateDoublyLinkedList(DoublyLinkedList head, int pos, int value);
Node *SearchDoublyLinkedList(DoublyLinkedList head, int pos);
int LocateDoublyLinkedList(DoublyLinkedList head, int value);
int GetDoublyLinkedListLength(DoublyLinkedList head);

DoublyLinkedList CreateDoublyLinkedList() {
  DoublyLinkedList head = (DoublyLinkedList)malloc(sizeof(Node));
  if (head == NULL) {
    return NULL;
  }
  head->prev = head->next = NULL;
  return head;
}

bool InsertDoublyLinkedList(DoublyLinkedList head, int pos, int value) {
  Node *p, *q;
  p = (Node *)malloc(sizeof(Node));
  p->data = value;
  p->prev = p->next = NULL;
  q = pos == 1 ? head : SearchDoublyLinkedList(head, pos - 1);
  if (q == NULL) {
    return false;
  }

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

  if (q->next != NULL) {
    q->next->prev = p;
  }
  q->next = p;
  return true;
}

bool DeleteDoublyLinkedList(DoublyLinkedList head, int pos) {
  if (head == NULL) {
    return false;
  }
  Node *p, *q;
  q = pos == 1 ? head : SearchDoublyLinkedList(head, pos - 1);
  if (q == NULL || q->next == NULL) {
    return false;
  }
  p = q->next;
  if (p->prev != NULL) {
    p->prev->next = p->next;
  }
  if (p->next != NULL) {
    p->next->prev = p->prev;
  }
  free(p);
  return true;
}

bool UpdateDoublyLinkedList(DoublyLinkedList head, int pos, int value) {
  if (head == NULL) {
    return false;
  }
  Node *p;
  p = pos == 1 ? head : SearchDoublyLinkedList(head, pos - 1);
  if (p == NULL || p->next == NULL) {
    return false;
  }
  if (p->next != NULL) {
    p->next->data = value;
  }
  return true;
}

int LocateDoublyLinkedList(DoublyLinkedList head, int value) {
  if (head == NULL) {
    return 0;
  }
  int i = 0;
  Node *p = head->next;
  while (p != NULL && p->data != value) {
    p = p->next;
    i++;
  }
  return i;
}

Node *SearchDoublyLinkedList(DoublyLinkedList head, int pos) {
  int i = 1;
  if (head == NULL || pos < i) {
    return NULL;
  }
  Node *p = head->next;
  while (p != NULL && p != head && i < pos) {
    p = p->next;
    i++;
  }
  return i == pos ? p : NULL;
}

int GetDoublyLinkedListLength(DoublyLinkedList head) {
  if (head == NULL) {
    return 0;
  }
  int cnt = 0;
  DoublyLinkedList p = head->next;
  while (p != NULL && p != head) {
    p = p->next;
    cnt++;
  }
  return cnt;
}

TEST(TestDoublyLinkedList, CreateDLinkedList) {
  DoublyLinkedList head = CreateDoublyLinkedList();
  EXPECT_EQ(NULL, head->prev);
  EXPECT_EQ(NULL, head->next);
  EXPECT_EQ(0, GetDoublyLinkedListLength(head));
}

TEST(TestDoublyLinkedList, InsertDLinkedList) {
  DoublyLinkedList p = CreateDoublyLinkedList();
  EXPECT_TRUE(InsertDoublyLinkedList(p, 1, 1));
  EXPECT_EQ(1, GetDoublyLinkedListLength(p));
  EXPECT_TRUE(InsertDoublyLinkedList(p, 2, 2));
  EXPECT_EQ(2, GetDoublyLinkedListLength(p));
  EXPECT_TRUE(InsertDoublyLinkedList(p, 3, 3));
  EXPECT_EQ(3, GetDoublyLinkedListLength(p));

  DoublyLinkedList q = CreateDoublyLinkedList();
  EXPECT_TRUE(InsertDoublyLinkedList(q, 1, 11));
  EXPECT_TRUE(InsertDoublyLinkedList(q, 2, 22));
  EXPECT_TRUE(InsertDoublyLinkedList(q, 3, 33));
  EXPECT_TRUE(InsertDoublyLinkedList(q, 3, 30));
  EXPECT_EQ(4, GetDoublyLinkedListLength(q));
  EXPECT_EQ(30, SearchDoublyLinkedList(q, 3)->data);
}

TEST(TestDoublyLinkedList, DeleteDoublyLinkedList) {
  DoublyLinkedList p = CreateDoublyLinkedList();
  InsertDoublyLinkedList(p, 1, 1);
  InsertDoublyLinkedList(p, 2, 2);
  InsertDoublyLinkedList(p, 3, 3);
  EXPECT_EQ(3, GetDoublyLinkedListLength(p));
  EXPECT_TRUE(DeleteDoublyLinkedList(p, 3));
  EXPECT_EQ(2, GetDoublyLinkedListLength(p));
  EXPECT_TRUE(DeleteDoublyLinkedList(p, 2));
  EXPECT_EQ(1, GetDoublyLinkedListLength(p));
  EXPECT_TRUE(DeleteDoublyLinkedList(p, 1));
  EXPECT_EQ(0, GetDoublyLinkedListLength(p));
  EXPECT_FALSE(DeleteDoublyLinkedList(p, 4));
  EXPECT_EQ(NULL, p->next);

  InsertDoublyLinkedList(p, 1, 11);
  InsertDoublyLinkedList(p, 2, 22);
  InsertDoublyLinkedList(p, 3, 33);
  EXPECT_TRUE(DeleteDoublyLinkedList(p, 2));
  EXPECT_EQ(2, GetDoublyLinkedListLength(p));

  DoublyLinkedList q = NULL;
  EXPECT_FALSE(DeleteDoublyLinkedList(q, 1));
}

TEST(TestDoublyLinkedList, UpdateDoublyLinkedList) {
  DoublyLinkedList head = CreateDoublyLinkedList();
  InsertDoublyLinkedList(head, 1, 1);
  InsertDoublyLinkedList(head, 2, 2);
  InsertDoublyLinkedList(head, 3, 3);

  EXPECT_TRUE(UpdateDoublyLinkedList(head, 1, 11));
  EXPECT_EQ(11, SearchDoublyLinkedList(head, 1)->data);

  EXPECT_TRUE(UpdateDoublyLinkedList(head, 2, 22));
  EXPECT_EQ(22, SearchDoublyLinkedList(head, 2)->data);
}

TEST(TestDoublyLinkedList, LocateDoublyLinkedList) {
  DoublyLinkedList head = CreateDoublyLinkedList();
  EXPECT_EQ(0, LocateDoublyLinkedList(head, 0));
  EXPECT_EQ(0, LocateDoublyLinkedList(head, 1));

  InsertDoublyLinkedList(head, 1, 11);
  EXPECT_EQ(0, LocateDoublyLinkedList(head, 11));

  InsertDoublyLinkedList(head, 2, 22);
  EXPECT_EQ(1, LocateDoublyLinkedList(head, 22));
}

双向循环链表

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

#include <gtest/gtest.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct node {
  int data;
  struct node *prev;
  struct node *next;
} Node, *DCLinkedList;

DCLinkedList CreateDCLinkedList();
bool InsertDCLinkedList(DCLinkedList head, int pos, int value);
bool DeleteDCLinkedList(DCLinkedList head, int pos);
bool UpdateDCLinkedList(DCLinkedList head, int pos, int value);
Node *SearchDCLinkedList(DCLinkedList head, int pos);
int LocateDCLinkedList(DCLinkedList head, int value);
int GetDCLinkedListLength(DCLinkedList head);

DCLinkedList CreateDCLinkedList() {
  DCLinkedList head = (DCLinkedList)malloc(sizeof(DCLinkedList));
  if (head == NULL) {
    return NULL;
  }
  head->prev = head->next = NULL;
  return head;
}

bool InsertDCLinkedList(DCLinkedList head, int pos, int value) {
  Node *p, *q;
  p = (Node *)malloc(sizeof(Node));
  if (p == NULL) {
    return false;
  }
  p->data = value;
  p->prev = p->next = p;
  q = pos == 1 ? head : SearchDCLinkedList(head, pos - 1);
  if (q == NULL) {
    return false;
  }

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

  if (q->next != NULL) {
    q->next->prev = p;
  }
  q->next = p;
  return true;
}

bool DeleteDCLinkedList(DCLinkedList head, int pos) {
  if (head == NULL) {
    return false;
  }
  Node *p, *q;
  q = pos == 1 ? head : SearchDCLinkedList(head, pos - 1);
  if (q == NULL || q->next == NULL) {
    return false;
  }

  p = q->next;
  if (p->prev != NULL) {
    p->prev->next = p->next; // p 前驱结点的后继结点指向 p 的后继结点
  }
  if (p->next != NULL) {
    p->next->prev = p->prev; // p 后继结点的前驱结点指向 p 的前驱结点
  }
  free(p);
  return true;
}

bool UpdateDCLinkedList(DCLinkedList head, int pos, int value) {
  if (head == NULL) {
    return false;
  }
  Node *p;
  p = pos == 1 ? head : SearchDCLinkedList(head, pos - 1);
  if (p == NULL || p->next == NULL) {
    return false;
  }
  p->next->data = value;
  return true;
}

Node *SearchDCLinkedList(DCLinkedList head, int pos) {
  int i = 1;
  if (head == NULL || pos < i) {
    return NULL;
  }
  Node *p = head->next;
  while (p != NULL && p != head && i < pos) {
    p = p->next;
    i++;
  }
  return i == pos ? p : NULL;
}

int LocateDCLinkedList(DCLinkedList head, int value) {
  if (head == NULL) {
    return 0;
  }
  DCLinkedList p = head->next;
  int i = 0;
  while (p != NULL && p != head && p->data != value) {
    p = p->next;
    i++;
  }
  return i;
}

int GetDCLinkedListLength(DCLinkedList head) {
  if (head == NULL) {
    return 0;
  }
  int cnt = 0;
  DCLinkedList p = head->next;
  while (p != NULL && p != head) {
    p = p->next;
    cnt++;
  }
  return cnt;
}

TEST(TestDCLinkedList, CreateDCLiedList) {
  DCLinkedList head = CreateDCLinkedList();
  EXPECT_EQ(NULL, head->prev);
  EXPECT_EQ(NULL, head->next);
  EXPECT_EQ(0, GetDCLinkedListLength(head));
}

TEST(TestDCLinkedList, InsertDCLinkedList) {
  DCLinkedList head = CreateDCLinkedList();
  EXPECT_TRUE(InsertDCLinkedList(head, 1, 1));
  EXPECT_EQ(1, GetDCLinkedListLength(head));
  EXPECT_TRUE(InsertDCLinkedList(head, 2, 2));
  EXPECT_EQ(2, GetDCLinkedListLength(head));
  EXPECT_TRUE(InsertDCLinkedList(head, 3, 3));
  EXPECT_EQ(3, GetDCLinkedListLength(head));
}

TEST(TestDCLinkedList, DeleteDCLinkedList) {
  DCLinkedList p = CreateDCLinkedList();
  EXPECT_TRUE(InsertDCLinkedList(p, 1, 1));
  EXPECT_TRUE(InsertDCLinkedList(p, 2, 2));
  EXPECT_TRUE(InsertDCLinkedList(p, 3, 3));
  EXPECT_EQ(3, GetDCLinkedListLength(p));

  EXPECT_TRUE(DeleteDCLinkedList(p, 3));
  EXPECT_EQ(2, GetDCLinkedListLength(p));

  EXPECT_TRUE(DeleteDCLinkedList(p, 2));
  EXPECT_EQ(1, GetDCLinkedListLength(p));

  EXPECT_TRUE(DeleteDCLinkedList(p, 1));
  EXPECT_EQ(0, GetDCLinkedListLength(p));

  EXPECT_FALSE(DeleteDCLinkedList(p, 4));
  EXPECT_EQ(NULL, p->next);

  InsertDCLinkedList(p, 1, 11);
  InsertDCLinkedList(p, 2, 22);
  InsertDCLinkedList(p, 3, 33);
  EXPECT_TRUE(DeleteDCLinkedList(p, 2));
  EXPECT_EQ(2, GetDCLinkedListLength(p));

  DCLinkedList q = NULL;
  EXPECT_EQ(NULL, DeleteDCLinkedList(q, 1));
}

TEST(TestDCLinkedList, UpdateDCLinkedList) {
  DCLinkedList head = CreateDCLinkedList();
  InsertDCLinkedList(head, 1, 1);
  InsertDCLinkedList(head, 2, 2);
  InsertDCLinkedList(head, 3, 3);

  EXPECT_TRUE(UpdateDCLinkedList(head, 1, 11));
  EXPECT_EQ(11, SearchDCLinkedList(head, 1)->data);

  EXPECT_TRUE(UpdateDCLinkedList(head, 2, 22));
  EXPECT_EQ(22, SearchDCLinkedList(head, 2)->data);
}

TEST(TestDCLinkedList, LocateDCLinkedList) {
  DCLinkedList head = CreateDCLinkedList();
  EXPECT_EQ(0, LocateDCLinkedList(head, 0));
  EXPECT_EQ(0, LocateDCLinkedList(head, 1));

  InsertDCLinkedList(head, 1, 11);
  EXPECT_EQ(0, LocateDCLinkedList(head, 11));

  InsertDCLinkedList(head, 2, 22);
  EXPECT_EQ(1, LocateDCLinkedList(head, 22));
}

其它运算在单链表上的实现

建表

  • 通过已实现的插入算法 InsertLinkedList(LinkedList head, int i, int x) 来实现，依次增大插入位置 i，使新的结点链入到链表中：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

LinkedList CreateLinkedList1() {
  LinkedList head = CreateLinkedList();
  int x;
  int i = 1;
  scanf("%d", &x);
  while (x != 0) {
    InsertLinkedList(head, i, x);
    i++;
    scanf("%d", &x);
  }
  return head;
}

int main() {
  LinkedList head = CreateLinkedList1();
  LinkedList p = head->next;
  while (p != NULL) {
    printf("%d ", p->data);
    p = p->next;
  }
  return 0;
}

此算法时间复杂度为 O(n2)。

  • 用一个指针指向尾结点，这样就为下一个新结点指明了插入位置，可称为「尾插」操作，最终形成的链表的数据顺序与输入顺序正好相同：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

LinkedList CreateLinkedList2() {
  LinkedList head;
  Node *p, *q;
  int x;
  head = (LinkedList)malloc(sizeof(Node)); // 生成头结点
  q = head;                                // 尾指针置初值
  scanf("%d", &x);                         // 读入第一个元素
  while (x != 0) {
    p = (LinkedList)malloc(sizeof(Node));
    p->data = x;
    q->next = p;     // 新结点 p 链入
    q = p;           // 修改尾指针 q，指向新的尾结点
    scanf("%d", &x); // 读入下一个元素
  }
  q->next = NULL;
  return head;
}

int main() {
  LinkedList head = CreateLinkedList2();
  LinkedList p = head->next;
  while (p != NULL) {
    printf("%d ", p->data);
    p = p->next;
  }
  return 0;
}

此算法时间复杂度为 O(n)。

  • 将新增的结点插入到头结点之后，第一个数据结点之前，可称为「前插」操作，最终形成的链表的数据顺序与输入顺序正好相反：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

LinkedList CreateLinkedList3() {
  LinkedList head;
  Node *p;
  int x;
  head = (LinkedList)malloc(sizeof(Node));
  head->next = NULL;
  scanf("%d", &x);
  while (x) {
    p = (LinkedList)malloc(sizeof(Node));
    p->data = x;
    p->next = head->next;
    head->next = p;
    scanf("%d", &x);
  }
  return head;
}

int main() {
  LinkedList head = CreateLinkedList3();
  LinkedList p = head->next;
  while (p != NULL) {
    printf("%d ", p->data);
    p = p->next;
  }
  return 0;
}

此算法时间复杂度为 O(n)。

删除重复结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

void RemoveDuplicateLinkedList(LinkedList head) {
  Node *p, *q, *t;
  q = head->next;
  while (q != NULL) {
    p = q;
    while (p->next != NULL) {
      if (p->next->data == q->data) {
        t = p->next;
        p->next = t->next;
        free(t);
      } else {
        p = p->next;
      }
    }
    q = q->next;
  }
}
更新于 2022-05-04
 
返回 | 主页