数据结构C代码汇总【1-线性表】

 下面直接往下看源代码及注释即可，注意，每一种数据结构都是按照数据结构定义+基本运算算法代码实现汇总在一起（包含常见算法的代码实现），这样在回顾数据结构的同时，掌握基本运算算法的代码实现，掌握住这些基础算法，就不用担心考研题目没思路了！

一、线性表

1、顺序表

1. //顺序表运算算法
2. #include <stdio.h>
3. #include <malloc.h>
4. #define MaxSize 50
5. typedef char ElemType;
6. typedef struct
7. { ElemType data[MaxSize]; //存放顺序表元素
8. int length; //存放顺序表的长度
9. } SqList; //声明顺序表的类型
10. void CreateList(SqList *&L,ElemType a[],int n) //整体建立顺序表
11. {
12. L=(SqList *)malloc(sizeof(SqList));
13. for (int i=0;i<n;i++)
14. L->data[i]=a[i];
15. L->length=n;
16. }
17. void InitList(SqList *&L) //初始化线性表
18. {
19. L=(SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间
20. L->length=0;
21. }
22. void DestroyList(SqList *&L) //销毁线性表
23. {
24. free(L);
25. }
26. bool ListEmpty(SqList *L) //判线性表是否为空表
27. {
28. return(L->length==0);
29. }
30. int ListLength(SqList *L) //求线性表的长度
31. {
32. return(L->length);
33. }
34. void DispList(SqList *L) //输出线性表
35. {
36. for (int i=0;i<L->length;i++)
37. printf("%c ",L->data[i]); //若是int类型，就改为%d即可，注意细节
38. printf("\n");
39. }
40. bool GetElem(SqList *L,int i,ElemType &e) //求线性表中第i个元素值
41. {
42. if (i<1 || i>L->length)
43. return false;
44. e=L->data[i-1];
45. return true;
46. }
47. int LocateElem(SqList *L, ElemType e) //查找第一个值域为e的元素序号
48. {
49. int i=0;
50. while (i<L->length && L->data[i]!=e) i++;
51. if (i>=L->length)
52. return 0;
53. else
54. return i+1;
55. }
56. bool ListInsert(SqList *&L,int i,ElemType e) //插入第i个元素
57. {
58. int j;
59. if (i<1 || i>L->length+1)
60. return false;
61. i--; //将顺序表位序转化为elem下标
62. for (j=L->length;j>i;j--) //将data[i]及后面元素后移一个位置
63. L->data[j]=L->data[j-1];
64. L->data[i]=e;
65. L->length++; //顺序表长度增1
66. return true;
67. }
68. bool ListDelete(SqList *&L,int i,ElemType &e) //删除第i个元素
69. {
70. int j;
71. if (i<1 || i>L->length)
72. return false;
73. i--; //将顺序表位序转化为elem下标
74. e=L->data[i];
75. for (j=i;j<L->length-1;j++) //将data[i]之后的元素前移一个位置
76. L->data[j]=L->data[j+1];
77. L->length--; //顺序表长度减1
78. return true;
79. }

复制代码

2、单链表

1. //单链表运算算法
2. #include <stdio.h>
3. #include <malloc.h>
4. typedef char ElemType;
5. typedef struct LNode
6. {
7. ElemType data;
8. struct LNode *next; //指向后继结点
9. } LinkNode; //单链表结点类型
10. void CreateListF(LinkNode *&L,ElemType a[],int n)
11. //头插法建立单链表
12. {
13. LinkNode *s;
14. L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
15. L->next=NULL;
16. for (int i=0;i<n;i++)
17. {
18. s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点s
19. s->data=a[i];
20. s->next=L->next; //将结点s插在原开始结点之前,头结点之后
21. L->next=s;
22. }
23. }
24. void CreateListR(LinkNode *&L,ElemType a[],int n)
25. //尾插法建立单链表
26. {
27. LinkNode *s,*r;
28. L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
29. L->next=NULL;
30. r=L; //r始终指向尾结点,开始时指向头结点
31. for (int i=0;i<n;i++)
32. {
33. s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点s
34. s->data=a[i];
35. r->next=s; //将结点s插入r结点之后
36. r=s;
37. }
38. r->next=NULL; //尾结点next域置为NULL
39. }
40. void InitList(LinkNode *&L) //初始化线性表
41. {
42. L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
43. L->next=NULL; //单链表置为空表
44. }
45. void DestroyList(LinkNode *&L) //销毁线性表
46. {
47. LinkNode *pre=L,*p=pre->next;
48. while (p!=NULL)
49. { free(pre);
50. pre=p; //pre、p同步后移一个结点
51. p=pre->next;
52. }
53. free(pre); //此时p为NULL,pre指向尾结点,释放它
54. }
55. bool ListEmpty(LinkNode *L) //判线性表是否为空表
56. {
57. return(L->next==NULL);
58. }
59. int ListLength(LinkNode *L) //求线性表的长度
60. { int i=0;
61. LinkNode *p=L; //p指向头结点,n置为0(即头结点的序号为0)
62. while (p->next!=NULL)
63. { i++;
64. p=p->next;
65. }
66. return(i); //循环结束,p指向尾结点,其序号i为结点个数
67. }
69. void DispList(LinkNode *L) //输出线性表
70. { LinkNode *p=L->next; //p指向首结点
71. while (p!=NULL) //p不为NULL,输出p结点的data域
72. { printf("%c ",p->data); //若是int类型，改为%d即可，注意细节
73. p=p->next; //p移向下一个结点
74. }
75. printf("\n");
76. }
78. bool GetElem(LinkNode *L,int i,ElemType &e) //求线性表中第i个元素值
79. { int j=0;
80. if (i<=0) return false; //i错误返回假
81. LinkNode *p=L; //p指向头结点,j置为0(即头结点的序号为0)
82. while (j<i && p!=NULL) //找第i个结点p
83. { j++;
84. p=p->next;
85. }
86. if (p==NULL) //不存在第i个数据结点,返回false
87. return false;
88. else //存在第i个数据结点,返回true
89. { e=p->data;
90. return true;
91. }
92. }
94. int LocateElem(LinkNode *L,ElemType e) //查找第一个值域为e的元素序号
95. { int i=1;
96. LinkNode *p=L->next; //p指向首结点,i置为1(即首结点的序号为1)
97. while (p!=NULL && p->data!=e) //查找data值为e的结点,其序号为i
98. { p=p->next;
99. i++;
100. }
101. if (p==NULL) //不存在值为e的结点,返回0
102. return(0);
103. else //存在值为e的结点,返回其逻辑序号i
104. return(i);
105. }
107. bool ListInsert(LinkNode *&L,int i,ElemType e) //插入第i个元素
108. { int j=0;
109. if (i<=0) return false; //i错误返回假
110. LinkNode *p=L,*s; //p指向头结点,j置为0(即头结点的序号为0)
111. while (j<i-1 && p!=NULL) //查找第i-1个结点p
112. { j++;
113. p=p->next;
114. }
115. if (p==NULL) //未找到第i-1个结点,返回false
116. return false;
117. else //找到第i-1个结点p,插入新结点并返回true
118. { s=(LinkNode *)malloc(sizeof(LinkNode));
119. s->data=e; //创建新结点s,其data域置为e
120. s->next=p->next; //将结点s插入到结点p之后
121. p->next=s;
122. return true;
123. }
124. }
126. bool ListDelete(LinkNode *&L,int i,ElemType &e) //删除第i个元素
127. { int j=0;
128. if (i<=0) return false; //i错误返回假
129. LinkNode *p=L,*q; //p指向头结点,j置为0(即头结点的序号为0)
130. while (j<i-1 && p!=NULL) //查找第i-1个结点
131. { j++;
132. p=p->next;
133. }
134. if (p==NULL) //未找到第i-1个结点,返回false
135. return false;
136. else //找到第i-1个结点p
137. { q=p->next; //q指向第i个结点
138. if (q==NULL) //若不存在第i个结点,返回false
139. return false;
140. e=q->data;
141. p->next=q->next; //从单链表中删除q结点
142. free(q); //释放q结点
143. return true; //返回true表示成功删除第i个结点
144. }
145. }

复制代码

3、循环单链表

1. //循环单链表运算算法
2. #include <stdio.h>
3. #include <malloc.h>
4. typedef int ElemType;
5. typedef struct LNode //定义单链表结点类型
6. {
7. ElemType data;
8. struct LNode *next;
9. } LinkNode;
10. void CreateListF(LinkNode *&L,ElemType a[],int n) //头插法建立循环单链表
11. {
12. LinkNode *s;int i;
13. L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
14. L->next=NULL;
15. for (i=0;i<n;i++)
16. {
17. s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点
18. s->data=a[i];
19. s->next=L->next; //将结点s插在原开始结点之前,头结点之后
20. L->next=s;
21. }
22. s=L->next;
23. while (s->next!=NULL) //查找尾结点,由s指向它
24. s=s->next;
25. s->next=L; //尾结点next域指向头结点
27. }
28. void CreateListR(LinkNode *&L,ElemType a[],int n) //尾插法建立循环单链表
29. {
30. LinkNode *s,*r;int i;
31. L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
32. L->next=NULL;
33. r=L; //r始终指向终端结点,开始时指向头结点
34. for (i=0;i<n;i++)
35. {
36. s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点
37. s->data=a[i];
38. r->next=s; //将结点s插入结点r之后
39. r=s;
40. }
41. r->next=L; //尾结点next域指向头结点
42. }
43. void InitList(LinkNode *&L) //初始化线性表
44. {
45. L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
46. L->next=L;
47. }
48. void DestroyList(LinkNode *&L) //销毁线性表
49. {
50. LinkNode *pre=L,*p=pre->next;
51. while (p!=L)
52. {
53. free(pre);
54. pre=p; //pre、p同步后移一个结点
55. p=pre->next;
56. }
57. free(pre); //此时p=L,pre指向尾结点,释放它
58. }
59. bool ListEmpty(LinkNode *L) //判线性表是否为空表
60. {
61. return(L->next==L);
62. }
63. int ListLength(LinkNode *L) //求线性表的长度
64. {
65. LinkNode *p=L;int i=0; //p指向头结点,n置为0(即头结点的序号为0)
66. while (p->next!=L)
67. {
68. i++;
69. p=p->next;
70. }
71. return(i); //循环结束,p指向尾结点,其序号n为结点个数
72. }
73. void DispList(LinkNode *L) //输出线性表
74. {
75. LinkNode *p=L->next;
76. while (p!=L) //p不为L,输出p结点的data域
77. {
78. printf("%d ",p->data);
79. p=p->next;
80. }
81. printf("\n");
82. }
83. bool GetElem(LinkNode *L,int i,ElemType &e) //求线性表中第i个元素值
84. { int j=1;
85. LinkNode *p=L->next;
86. if (i<=0 || L->next==L) //i错误或者空表返回假
87. return false;
88. if (i==1) //求第1个结点值，作为特殊情况处理
89. {
90. e=L->next->data;
91. return true;
92. }
93. else //i不为1时
94. {
95. while (j<=i-1 && p!=L) //找第i个结点p
96. {
97. j++;
98. p=p->next;
99. }
100. if (p==L) //没有找到返回假
101. return false;
102. else //找到了提取它的值并返回整
103. {
104. e=p->data;
105. return true;
106. }
107. }
108. }
110. int LocateElem(LinkNode *L,ElemType e) //查找第一个值域为e的元素序号
111. {
112. LinkNode *p=L->next;
113. int i=1;
114. while (p!=L && p->data!=e) //查找第一个值域为e的结点p
115. {
116. p=p->next;
117. i++; //i对应结点p的序号
118. }
119. if (p==L)
120. return(0); //没有找到返回0
121. else
122. return(i); //找到了返回其序号
123. }
124. bool ListInsert(LinkNode *&L,int i,ElemType e) //插入第i个元素
125. {
126. int j=1;
127. LinkNode *p=L,*s;
128. if (i<=0) return false; //i错误返回假
129. if (p->next==L || i==1) //原单链表为空表或i=1作为特殊情况处理
130. {
131. s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
132. s->data=e;
133. s->next=p->next; //将结点s插入到结点p之后
134. p->next=s;
135. return true;
136. }
137. else
138. {
139. p=L->next;
140. while (j<=i-2 && p!=L) //找第i-1个结点p
141. {
142. j++;
143. p=p->next;
144. }
145. if (p==L) //未找到第i-1个结点
146. return false;
147. else //找到第i-1个结点p
148. {
149. s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
150. s->data=e;
151. s->next=p->next; //将结点s插入到结点p之后
152. p->next=s;
153. return true;
154. }
155. }
156. }
157. bool ListDelete(LinkNode *&L,int i,ElemType &e) //删除第i个元素
158. {
159. int j=1;
160. LinkNode *p=L,*q;
161. if (i<=0 || L->next==L)
162. return false; //i错误或者空表返回假
163. if (i==1) //i=1作为特殊情况处理
164. {
165. q=L->next; //删除第1个结点
166. e=q->data;
167. L->next=q->next;
168. free(q);
169. return true;
170. }
171. else //i不为1时
172. {
173. p=L->next;
174. while (j<=i-2 && p!=L) //找第i-1个结点p
175. {
176. j++;
177. p=p->next;
178. }
179. if (p==L) //未找到第i-1个结点
180. return false;
181. else //找到第i-1个结点p
182. {
183. q=p->next; //q指向要删除的结点
184. e=q->data;
185. p->next=q->next; //从单链表中删除q结点
186. free(q); //释放q结点
187. return true;
188. }
189. }
190. }

复制代码

4、双链表

1. //双链表运算算法
2. #include <stdio.h>
3. #include <malloc.h>
4. typedef int ElemType;
5. typedef struct DNode
6. {
7. ElemType data;
8. struct DNode *prior; //指向前驱结点
9. struct DNode *next; //指向后继结点
10. } DLinkNode; //声明双链表结点类型
11. void CreateListF(DLinkNode *&L,ElemType a[],int n) //头插法建双链表
12. {
13. DLinkNode *s;
14. L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点
15. L->prior=L->next=NULL;
16. for (int i=0;i<n;i++)
17. {
18. s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点
19. s->data=a[i];
20. s->next=L->next; //将结点s插在原开始结点之前,头结点之后
21. if (L->next!=NULL) L->next->prior=s;
22. L->next=s;s->prior=L;
23. }
24. }
25. void CreateListR(DLinkNode *&L,ElemType a[],int n) //尾插法建双链表
26. {
27. DLinkNode *s,*r;
28. L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点
29. L->prior=L->next=NULL;
30. r=L; //r始终指向终端结点,开始时指向头结点
31. for (int i=0;i<n;i++)
32. {
33. s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点
34. s->data=a[i];
35. r->next=s;s->prior=r; //将结点s插入结点r之后
36. r=s;
37. }
38. r->next=NULL; //尾结点next域置为NULL
39. }
40. void InitList(DLinkNode *&L) //初始化线性表
41. {
42. L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点
43. L->prior=L->next=NULL;
44. }
45. void DestroyList(DLinkNode *&L) //销毁线性表
46. {
47. DLinkNode *pre=L,*p=pre->next;
48. while (p!=NULL)
49. {
50. free(pre);
51. pre=p; //pre、p同步后移一个结点
52. p=pre->next;
53. }
54. free(p);
55. }
56. bool ListEmpty(DLinkNode *L) //判线性表是否为空表
57. {
58. return(L->next==NULL);
59. }
60. int ListLength(DLinkNode *L) //求线性表的长度
61. {
62. DLinkNode *p=L;
63. int i=0; //p指向头结点,i设置为0
64. while (p->next!=NULL) //找尾结点p
65. {
66. i++; //i对应结点p的序号
67. p=p->next;
68. }
69. return(i);
70. }
71. void DispList(DLinkNode *L) //输出线性表
72. {
73. DLinkNode *p=L->next;
74. while (p!=NULL)
75. {
76. printf("%c ",p->data);
77. p=p->next;
78. }
79. printf("\n");
80. }
81. bool GetElem(DLinkNode *L,int i,ElemType &e) //求线性表中第i个元素值
82. {
83. int j=0;
84. DLinkNode *p=L;
85. if (i<=0) return false; //i错误返回假
86. while (j<i && p!=NULL) //查找第i个结点p
87. {
88. j++;
89. p=p->next;
90. }
91. if (p==NULL) //没有找到返回假
92. return false;
93. else //找到了提取值并返回真
94. {
95. e=p->data;
96. return true;
97. }
98. }
99. int LocateElem(DLinkNode *L,ElemType e) //查找第一个值域为e的元素序号
100. {
101. int i=1;
102. DLinkNode *p=L->next;
103. while (p!=NULL && p->data!=e) //查找第一个值域为e的结点p
104. {
105. i++; //i对应结点p的序号
106. p=p->next;
107. }
108. if (p==NULL) //没有找到返回0
109. return(0);
110. else //找到了返回其序号
111. return(i);
112. }
113. bool ListInsert(DLinkNode *&L,int i,ElemType e) //插入第i个元素
114. {
115. int j=0;
116. DLinkNode *p=L,*s; //p指向头结点,j设置为0
117. if (i<=0) return false; //i错误返回假
118. while (j<i-1 && p!=NULL) //查找第i-1个结点p
119. {
120. j++;
121. p=p->next;
122. }
123. if (p==NULL) //未找到第i-1个结点
124. return false;
125. else //找到第i-1个结点p
126. {
127. s=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点s
128. s->data=e;
129. s->next=p->next; //将结点s插入到结点p之后
130. if (p->next!=NULL)
131. p->next->prior=s;
132. s->prior=p;
133. p->next=s;
134. return true;
135. }
136. }
137. bool ListDelete(DLinkNode *&L,int i,ElemType &e) //删除第i个元素
138. { int j=0;
139. DLinkNode *p=L,*q; //p指向头结点,j设置为0
140. if (i<=0) return false; //i错误返回假
141. while (j<i-1 && p!=NULL) //查找第i-1个结点p
142. { j++;
143. p=p->next;
144. }
145. if (p==NULL) //未找到第i-1个结点
146. return false;
147. else //找到第i-1个节p
148. { q=p->next; //q指向第i个结点
149. if (q==NULL) //当不存在第i个结点时返回false
150. return false;
151. e=q->data;
152. p->next=q->next; //从双链表中删除结点q
153. if (p->next!=NULL) //若p结点存在后继结点,修改其前驱指针
154. p->next->prior=p;
155. free(q); //释放q结点
156. return true;
157. }
158. }

复制代码

5、循环双链表

1. //循环双链表运算算法
2. #include <stdio.h>
3. #include <malloc.h>
4. typedef int ElemType;
5. typedef struct DNode //定义双链表结点类型
6. {
7. ElemType data;
8. struct DNode *prior; //指向前驱结点
9. struct DNode *next; //指向后继结点
10. } DLinkNode;
11. void CreateListF(DLinkNode *&L,ElemType a[],int n) //头插法建立循环双链表
12. {
13. DLinkNode *s;
14. L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点
15. L->next=NULL;
16. for (int i=0;i<n;i++)
17. {
18. s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点
19. s->data=a[i];
20. s->next=L->next; //将结点s插在原开始结点之前,头结点之后
21. if (L->next!=NULL) L->next->prior=s;
22. L->next=s;s->prior=L;
23. }
24. s=L->next;
25. while (s->next!=NULL) //查找尾结点,由s指向它
26. s=s->next;
27. s->next=L; //尾结点next域指向头结点
28. L->prior=s; //头结点的prior域指向尾结点
30. }
31. void CreateListR(DLinkNode *&L,ElemType a[],int n) //尾插法建立循环双链表
32. {
33. DLinkNode *s,*r;
34. L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点
35. L->next=NULL;
36. r=L; //r始终指向尾结点,开始时指向头结点
37. for (int i=0;i<n;i++)
38. {
39. s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点
40. s->data=a[i];
41. r->next=s;s->prior=r; //将结点s插入结点r之后
42. r=s;
43. }
44. r->next=L; //尾结点next域指向头结点
45. L->prior=r; //头结点的prior域指向尾结点
46. }
47. void InitList(DLinkNode *&L) //初始化线性表
48. {
49. L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点
50. L->prior=L->next=L;
51. }
52. void DestroyList(DLinkNode *&L) //销毁线性表
53. {
54. DLinkNode *pre=L,*p=pre->next;
55. while (p!=L)
56. {
57. free(pre);
58. pre=p; //pre、p同步后移一个结点
59. p=pre->next;
60. }
61. free(pre); //此时p=L,pre指向尾结点,释放它
62. }
63. bool ListEmpty(DLinkNode *L) //判线性表是否为空表
64. {
65. return(L->next==L);
66. }
67. int ListLength(DLinkNode *L) //求线性表的长度
68. {
69. DLinkNode *p=L;
70. int i=0;
71. while (p->next!=L)
72. {
73. i++;
74. p=p->next;
75. }
76. return(i); //循环结束,p指向尾结点,其序号i为结点个数
77. }
78. void DispList(DLinkNode *L) //输出线性表
79. {
80. DLinkNode *p=L->next;
81. while (p!=L)
82. {
83. printf("%c ",p->data);
84. p=p->next;
85. }
86. printf("\n");
87. }
88. bool GetElem(DLinkNode *L,int i,ElemType &e) //求线性表中第i个元素值
89. {
90. int j=1;
91. DLinkNode *p=L->next;
92. if (i<=0 || L->next==L)
93. return false; //i错误或者L为空表返回假
94. if (i==1) //i=1作为特殊情况处理
95. {
96. e=L->next->data;
97. return true;
98. }
99. else //i不为1时
100. {
101. while (j<=i-1 && p!=L) //查找第i个结点p
102. {
103. j++;
104. p=p->next;
105. }
106. if (p==L) //没有找到第i个节，返回假
107. return false;
108. else //找到了第i个节，返回真
109. {
110. e=p->data;
111. return true;
112. }
113. }
114. }
115. int LocateElem(DLinkNode *L,ElemType e) //查找第一个值域为e的元素序号
116. {
117. int i=1;
118. DLinkNode *p=L->next;
119. while (p!=NULL && p->data!=e)
120. {
121. i++;
122. p=p->next;
123. }
124. if (p==NULL) //不存在值为e的结点,返回0
125. return(0);
126. else //存在值为e的结点,返回其逻辑序号i
127. return(i);
128. }
129. bool ListInsert(DLinkNode *&L,int i,ElemType e) //插入第i个元素
130. {
131. int j=1;
132. DLinkNode *p=L,*s;
133. if (i<=0) return false; //i错误返回假
134. if (p->next==L) //原双链表为空表时
135. {
136. s=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点s
137. s->data=e;
138. p->next=s;s->next=p;
139. p->prior=s;s->prior=p;
140. return true;
141. }
142. else if (i==1) //L不为空，i=1作为特殊情况处理
143. {
144. s=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点s
145. s->data=e;
146. s->next=p->next;p->next=s; //将结点s插入到结点p之后
147. s->next->prior=s;s->prior=p;
148. return true;
149. }
150. else //i不为1时
151. {
152. p=L->next;
153. while (j<=i-2 && p!=L) //查找第i-1个结点p
154. { j++;
155. p=p->next;
156. }
157. if (p==L) //未找到第i-1个结点
158. return false;
159. else //找到第i-1个结点*p
160. {
161. s=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点s
162. s->data=e;
163. s->next=p->next; //将结点s插入到结点p之后
164. if (p->next!=NULL) p->next->prior=s;
165. s->prior=p;
166. p->next=s;
167. return true;
168. }
169. }
170. }
171. bool ListDelete(DLinkNode *&L,int i,ElemType &e) //删除第i个元素
172. {
173. int j=1;
174. DLinkNode *p=L,*q;
175. if (i<=0 || L->next==L)
176. return false; //i错误或者为空表返回假
177. if (i==1) //i==1作为特殊情况处理
178. {
179. q=L->next; //删除第1个结点
180. e=q->data;
181. L->next=q->next;
182. q->next->prior=L;
183. free(q);
184. return true;
185. }
186. else //i不为1时
187. {
188. p=L->next;
189. while (j<=i-2 && p!=NULL) //查找到第i-1个结点p
190. {
191. j++;
192. p=p->next;
193. }
194. if (p==NULL) //未找到第i-1个结点
195. return false;
196. else //找到第i-1个结点p
197. {
198. q=p->next; //q指向要删除的结点
199. if (q==NULL) return 0; //不存在第i个结点
200. e=q->data;
201. p->next=q->next; //从单链表中删除q结点
202. if (p->next!=NULL) p->next->prior=p;
203. free(q); //释放q结点
204. return true;
205. }
206. }
207. }

复制代码

6、一些常见算法的代码实现

【1】删除[x,y]区间内的值

1. #include "sqlist_int.cpp"
3. //一种更高效的算法删除[x,y]区间内的值（即把不在此区间内的值放在一个新建的顺序表中）
4. void fun(SqList *&L,ElemType x,ElemType y)
5. { int k=0; //新建的顺序表的下标变量
6. for (int i=0;i<L->length;i++)
7. if (!(L->data[i]>=x && L->data[i]<=y))
8. L->data[k++]=L->data[i];
9. L->length=k;
10. }
12. int main()
13. {
14. SqList *L;
15. ElemType a[]={-1,-9,0,8,-7,11,5,-6};
16. CreateList(L,a,8);
17. printf("L:");DispList(L);
18. printf("执行删除运算\n");
19. fun(L,-6,5);
20. printf("L:");DispList(L);
21. DestroyList(L);
22. return 1;
23. }

复制代码

→代码执行结果如下：

 【2】使顺序表内所有小于0的值移到大于或等于0的值前面 

1. #include "sqlist.cpp"
3. //用高效的算法使顺序表内所有小于0的值移到大于或等于0的值前面
4. void move2(SqList *&L) //快速排序的思想
5. { int i=0,j=L->length-1;
6. ElemType pivot=L->data[0]; //以data[0]为基准
7. while (i<j) //从顺序表两端交替向中间扫描,直至i=j为止
8. { while (j>i && L->data[j]>=0)
9. j--; //从右向左扫描,找一个小于等于pivot的data[j]
10. L->data[i]=L->data[j]; //找到这样的data[j],放入data[i]处
11. while (i<j && L->data[i]<0)
12. i++; //从左向右扫描,找一个大于pivot的记录data[i]
13. L->data[j]=L->data[i]; //找到这样的data[i],放入data[j]处
14. }
15. L->data[i]=pivot; //最后将基准归位
16. }
18. int main()
19. {
20. SqList *L;
21. ElemType a[]={-1,-9,0,8,-7,0,5,-6};
22. CreateList(L,a,8);
23. printf("L:");DispList(L);
24. printf("执行移动运算\n");
25. move2(L);
26. printf("L:");DispList(L);
27. DestroyList(L);
28. return 1;
29. }

复制代码

【3】找到下标为n/2的元素 

1. #include "linklist.cpp"
3. //找到下标为n/2的元素
4. ElemType Midnode(LinkNode *L) //此算法采用双指针法，通过移动不同的步数最终找到中间的元素位置
5. { LinkNode *q,*p;
6. for (q=p=L->next; p->next!=NULL && p->next->next!=NULL; q=q->next,p=p->next->next)
7. ;
8. return q->data;
9. }
11. int main()
12. {
13. LinkNode *L;
14. ElemType a[]="12345678";
15. int n=(sizeof(a)-1)/sizeof(ElemType);
16. CreateListR(L,a,n); //创建表
17. printf("输出顺序表L:\n");
18. DispList(L);
19. printf("中间元素为：%c\n", Midnode(L));
20. DestroyList(L);
21. return 1;
22. }

复制代码

 【4】循环单链表实现两个单链表的合并 

1. #include "clinklist.cpp"
3. //循环单链表实现两个单链表的合并
4. void Merge(LinkNode *ha, LinkNode *hb, LinkNode *&hc)
5. { LinkNode *p;
6. hc=ha;
7. for (p=ha;p->next!=ha;p=p->next)
8. ; //找到ha的尾结点p
9. p->next=hb->next; //将结点p的next指向hb的首结点
10. for ( ;p->next!=hb;p=p->next)
11. ; //找到hb的尾结点p
12. p->next=hc; //构成循环单链表
13. free(hb); //释放hb单链表的头结点
14. }
15. int main()
16. {
17. LinkNode *ha,*hb,*hc;
18. ElemType a[]={1,2,3,4,5},b[]={6,7,8,9,10};
19. int n=5;
20. CreateListR(ha,a,n);
21. CreateListR(hb,b,n);
22. printf("ha:");DispList(ha);
23. printf("hb:");DispList(hb);
24. Merge(ha,hb,hc);
25. printf("hc:");DispList(hc);
26. printf("\n释放链表hc。");
27. DestroyList(hc);
28. return 1;
29. }

复制代码

【5】将L中所有数据结点按x进行划分，尾插法新建L表  

1. #include "linklist.cpp" //包含单链表的基本运算算法
3. void Split(LinkNode *&L,ElemType x) //将L中所有数据结点按x进行划分，尾插法新建L表
4. {
5. LinkNode *p=L->next,*t,*r;
6. L->next=NULL; //L变为空链表
7. r=L;
8. while (p!=NULL) //等价于while (p)
9. {
10. if (p->data<x) //若p结点值小于x，将其插入在开头
11. {
12. t=p->next; //t帮p临时站岗
13. p->next=L->next;//将结点p插入到L的开头
14. L->next=p;
15. if (p->next==NULL) //若p结点是第一个在开头插入的结点
16. r=p; //则它是尾结点
17. p=t; //t还给p
18. }
19. else //若p结点值大于或等于x，将其插入到末尾
20. {
21. r->next=p;
22. r=p;
23. p=p->next;
24. }
25. }
26. r->next=NULL;
27. }
28. int main()
29. {
30. LinkNode *L;
31. ElemType a[]="adbacbchfdeg";
32. int n=(sizeof(a)-1)/sizeof(ElemType);
33. CreateListR(L,a,n);
34. printf("L："); DispList(L);
35. ElemType x='d';
36. printf("以%c进行划分\n",x);
37. Split(L,x);
38. printf("L："); DispList(L);
39. DestroyList(L);
40. return 1;
41. }

复制代码

这是第一章线性表的全部内容了，因为很详细，篇幅较长，下一章的栈和队列在下篇博客里，需要学习的朋友可以直接去点击→第二章 栈和队列