玩转C语言链表，单链表/双向链表的建立/遍历/插入/删除

小样岁月

　　最近临近期末的C语言课程设计比平时练习作业一下难了不止一个档次，第一次接触到了C语言的框架开发，了解了View(界面层)、Service(业务逻辑层)、Persistence(持久化层)的分离和耦合，一种面向过程的MVC的感觉。
' ]8 G4 q$ k7 T' b. I% v　　而这一切的基础就在于对链表的创建、删除、输出、写入文件、从文件读出......
　　本篇文章在于巩固链表的基础知识(整理自《C语言程序设计教程--人民邮电出版社》第十章——指针与链表)，只对链表的概念及增删改查作出探讨，欢迎指教。
& n2 _: e/ z2 R, R# A4 A8 v　　一、链表结构和静态/动态链表
) M& O' C- K7 p% [　　二、单链表的建立与遍历
9 l0 R3 O; F. o" D/ i　　三、单链表的插入与删除
1 J* v1 q! g1 U4 U　　四、双向链表的概念
; Q5 L+ P% U% @; B' ?1 ]- @/ C0 ^　　五、双向链表的建立与遍历
　　六、双向链表的元素查找
% F. X. Q$ Z% H5 E7 C　　七、循环链表的概念
1 @" h  L1 \6 f8 G* L　　八、合并两个链表的实例
/ o7 O' r" w6 R) F! ~0 j2 J; I　　九、链表实战
+ O* P2 O7 U, R9 Q7 R+ D. A　　拓展思维、拉到最后去看看 (•̀ᴗ•́)و ̑̑
　　一、链表结构和静态/动态链表
　　链表是一种常见的数据结构——与数组不同的是：
8 \  b7 h0 o! o. Y8 K+ V　　1.数组首先需要在定义时声明数组大小，如果像这个数组中加入的元素个数超过了数组的长度时，便不能正确保存所有内容;链表可以根据大小需要进行拓展。
　　2.其次数组是同一数据类型的元素集合，在内存中是按一定顺序连续排列存放的;链表常用malloc等函数动态随机分配空间，用指针相连。
( R; C! I% O$ T; H# z　　链表结构示意图如下所示：
1 }$ I1 {$ [9 P) w

　　

1 D. V. ^) A4 R0 ~　　在链表中，每一个元素包含两个部分;数据部分和指针部分。数据部分用来存放元素所包含的数据，指针部分用来指向下一个元素。最后一个元素的指针指向NULL，表示指向的地址为空。整体用结构体来定义，指针部分定义为指向本结构体类型的指针类型。
* g8 O5 Y1 l$ U. \$ n$ R8 I　　静态链表需要数组来实现，即把线性表的元素存放在数组中。数组单元存放链表结点，结点的链域指向下一个元素的位置，即下一个元素所在数组单元的下标。这些元素可能在物理上是连续存放的，也有可能是不连续的，它们之间通过逻辑关系来连接——这就要涉及到数组长度定义的问题，实现无法预知定义多大的数组，动态链表随即出现。
　　动态链表指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点的数据，并建立起前后相连的关系。
% I+ S0 M* ?- T6 v& ~　　二、单链表的建立与遍历
8 H7 O& m* P1 {　　单链表中，每个结点只有一个指针，所有结点都是单线联系，除了末为结点指针为空外，每个结点的指针都指向下一个结点，一环一环形成一条线性链。
　　链表的创建过程：

　　

- i" T2 C# U9 ^2 @　　接下来在源码中建立并遍历输出一个单链表。

1 d( J! `# h8 L3 X
, G8 v6 v2 |& [' s4 W" N

1. 　　#include
   
2. 
   
3. 　　#include
   
4. 
   
5. 　　#include
   
6. 
   
7. 　　/*单向链表*/
   $ i9 O7 \+ W2 @7 L) k
8. 
   ' d6 _  ~6 c6 }. R: i
9. 　　struct Student/*建立学生信息结构体模型*/
   
10. 
    5 o0 N, ], \$ ]* `1 T* Y4 u; S
11. 　　{
    2 C0 J" o6 K" {- y+ n
12. 
    
13. 　　char cName[20];/*学生姓名*/
    # S/ k+ {6 V( K  _$ F: X' T
14. 
    
15. 　　int iNumber;/*学生学号*/
    
16. 
    
17. 　　struct student *next;/*指向本结构体类型的指针类型*/
    $ D4 Y. m. }1 T! [
18. 
    
19. 　　};
    
20. 
    
21. 　　int iCount;/*全局变量表示链表长度*/
    6 F: |, U6 A' F  U! @1 n0 A1 u
22. 
    
23. 　　struct Student *Create();/*创建链表函数声明*/
    7 h0 }, @: x$ [& R; @( J
24. 
    % [# y3 D# @% f' Q% V  O
25. 　　void print(struct Student *);/*遍历输出链表函数声明*/
    1 r) K/ f0 y3 z* V
26. 
    
27. 　　int main()
    : ?. b; Y: g9 W0 ^8 h) M1 h
28. 
    3 n2 S4 i' [+ B, _; r- X" ?# w
29. 　　{
    4 ]3 y' G4 Q: t& ]" }2 G# B
30. 
    
31. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
    0 q: w# x2 `- q
32. 
    4 B& V# T) H; l- [1 F0 M
33. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
    
34. 
    
35. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
    
36. 
    
37. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    
38. 
    % d, E( n0 z: Q/ j) P5 A# J+ n
39. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
40. 
    & n1 i  {% I& Z0 f* ^$ _2 U
41. 　　return 0;
    / E5 g" W! U1 W6 s( n$ E
42. 
    ! q) o& _, e: j; L0 x2 B
43. 　　}
    + |" I7 K7 a* d$ `, y
44. 
    ' @* }7 o. j+ f: e4 H) S7 f
45. 　　struct Student *Create()
    1 R. n8 p3 ^& f; H7 y, Y- _5 e3 M
46. 
    5 q# S+ i8 g7 H8 v
47. 　　{
    2 I4 z8 H, r  ?2 ?
48. 
    
49. 　　struct Student *pHead=NULL;/*初始化链表，头指针为空*/
    
50. 
    
51. 　　struct Student *pEnd,*pNew;
    
52. 
    
53. 　　iCount=0;/*初始化链表长度*/
    
54. 
    % H3 S5 n" E- u# w0 ?
55. 　　pEnd=pNew=(struct Student *)malloc(sizeof(struct Student));/*动态开辟一个学生信息结构体类型大小的空间，使得pEnd和pNew同时指向该结构体空间*/
    
56. 
    
57. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    0 }& b! x% X- w2 ~3 O7 m
58. 
    
59. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    
60. 
    
61. 　　while(pNew->iNumber!=0)/*设定循环结束条件——学号不为0时*/
    - U4 G7 n# S/ F1 k
62. 
    8 K% Y9 D% W, K7 B
63. 　　{
    * v! ?! J* l) j
64. 
    ) x' U+ q3 L" k' T3 C+ I
65. 　　iCount++;/*链表长度+1，即学生信息个数+1*/
    
66. 
    
67. 　　if(iCount==1)/*如果链表长度刚刚加为1，执行*/
    # ]: f9 ^4 c  l9 f; a# W0 P
68. 
    " M1 c! e% b% N0 K8 r9 I6 ^
69. 　　{
    
70. 
    * @& g9 c( @3 V# k5 m$ n2 [! ]) J
71. 　　pNew->next=pHead;/*使指针指向为空*/
    
72. 
    6 o" j7 T8 k( A5 R7 U& I
73. 　　pEnd=pNew;/*跟踪新加入的结点*/
    ! a1 w, y& m; K5 M: W3 n. S1 [
74. 
    - |  \4 a, D  e* L# P* ~
75. 　　pHead=pNew;/*头结点指向首结点*/
    
76. 
    
77. 　　}
    4 k/ d4 n  F9 _0 l7 X
78. 
    
79. 　　else/*如果链表已经建立，长度大于等于2时，执行*/
    ) @, u8 Q2 N7 n
80. 
    , b+ |5 G, r2 b6 F- W2 ?: A
81. 　　{
    % L0 Z- P, b; L+ J
82. 
    
83. 　　pNew->next=NULL;/*新结点的指针为空*/
    
84. 
    
85. 　　pEnd->next=pNew;/*原来的结点指向新结点*/
    2 {9 t" k/ @2 W6 D2 u
86. 
    
87. 　　pEnd=pNew;/*pEnd指向新结点*/
    0 ~9 I$ u4 l+ [1 z# p
88. 
    
89. 　　}
    
90. 
    
91. 　　pNew=(struct Student *)malloc(sizeof(struct Student));/*再次分配结点的内存空间*/
    
92. 
    
93. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    - g* o3 `0 h( n4 W
94. 
    
95. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    
96. 
    7 }. d$ a& F! x
97. 　　}
    2 O- H! B8 \4 B1 T+ L  g' ]$ ~5 p4 O
98. 
    
99. 　　free(pNew);/*释放结点空间*/
    
100. 
     3 z0 ^/ ^! C' @9 D
101. 　　return pHead;/*返回创建出的头指针*/
     / X8 U; x1 }7 K+ `# S2 m
102. 
     
103. 　　}
     
104. 
     % h, X! N! C  ^. u" ?9 u
105. 　　void print(struct Student *pHead)
     ) N+ N8 L$ A" l, F; K2 }
106. 
     
107. 　　{
     
108. 
     
109. 　　struct Student *pTemp;/*定义指向一个学生信息结构体类型的临时指针*/
     3 r; z8 K" B( z4 N4 V2 w6 I! t; @
110. 
     
111. 　　int iIndex=1;/*定义并出事哈变量iIndex，用来标识第几个学生(信息)*/
     + n7 X# A6 p6 ]; ?0 f% F* [
112. 
     
113. 　　printf("总共%d个学生(信息)：\n",iCount);
     
114. 
     1 d- Y4 u6 b9 l7 T( N/ _3 D
115. 　　pTemp=pHead;/*指针得到首结点的地址*/
     . }8 D; @: c+ Z/ Y/ e2 C
116. 
     
117. 　　while(pTemp!=NULL)/*当临时指针不指向NULL时*/
     
118. 
     ! t  x0 ^: T/ O. P) \
119. 　　{
     4 a4 S+ J$ ?+ H( f8 a8 P" }. f4 e
120. 
     
121. 　　printf("第%d个学生信息：\n",iIndex);
       E1 D0 v# @3 _
122. 
     1 S8 \" r+ _. l) d% c! i
123. 　　printf("姓名：%s",pTemp->cName); /*输出姓名*/
     
124. 
     / i3 N. I" D- p
125. 　　printf("学号：%d",pTemp->iNumber);/*输出学号*/
     - @2 t, f/ t" R! h; C
126. 
     
127. 　　pTemp=pTemp->next;/*移动临时指针到下一个结点*/
     
128. 
     
129. 　　iIndex++;/*进行自加运算*/
     " m0 m9 ]$ `6 b7 }
130. 
     
131. 　　}
     # J: l( f1 I  \3 r
132. 
     
133. 　　}

复制代码

$ R: t) y; c/ U- i& z


　　三、单链表的插入与删除
$ Z5 f5 h. B6 Q5 s. p8 K+ G1 |; T　　在本实例中，插入时根据传递来的学号，插入到其后。
7 s. u& o- q( t. G8 o　　删除时根据其所在链表的位置，删除并释放该空间。
# L4 B; Q* I8 y+ e　　主函数增加如下：
7 n1 f# q' Z3 }# @5 l; I% F2 i

6 f6 F# w$ U6 `8 p1 e

1. 　　int main()
   ; E" ~0 G' ~( Y2 g% g
2. 
   
3. 　　{
   
4. 
   
5. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
   2 \$ ^3 E! a* ^7 V8 Q
6. 
   % A  l; C2 C7 ?0 t1 P- I; b8 J
7. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
   
8. 
   
9. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
   : g. x4 Q9 w$ v  u5 G6 L# T$ E; i
10. 
    
11. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    & Z- }" b* X; O5 P6 M
12. 
    
13. 　　pHead=Insert(pHead,insert_n);/*将指针pHead和要插入的结点数传递给插入函数*/
    " G  b% V7 I& `* u
14. 
    ) N6 n- F* i1 p4 ?) {' [* O
15. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
16. 
    + Z6 h. W1 g1 u4 ^1 I% ]
17. 　　Delete(pHead,delete_n);/*将指针pHead和要删除的结点数传递给删除函数*/
    * N/ z' j# ~6 |( s
18. 
    & @' u) E7 t, A3 O/ k& a+ u
19. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
20. 
    
21. 　　return 0;
    
22. 
    
23. 　　}

复制代码

& d; e7 a2 q( l. R( M
2 ]5 {- M( j' T4 w$ e& k  k

　　插入函数：


  b+ e! p" j) j1 w  V5 v7 f6 [( C  e7 s
8 ^. t1 G2 h1 ~0 n" A9 t, q1 h( h

1. 　　struct Student *Insert(struct Student *pHead,int number)
   
2. 
   - L4 e3 _( E# t2 [9 p* y( s
3. 　　{
   
4. 
   2 \; q% ^! P$ B: y* {4 r; k; z
5. 　　struct Student *p=pHead,*pNew;/*定义pNew指向新分配的空间*/
   
6. 
   
7. 　　while(p&&p->iNumber!=number)
   4 h: z& a5 B1 }+ K
8. 
   ( \. Q, i1 q- c
9. 　　p=p->next;/*使临时结点跟踪到要插入的位置(该实例必须存在学号为number的信息，插入其后，否则出错)*/
   
10. 
    
11. 　　printf("姓名和学号：\n");
    7 B# H& c! _7 p# L
12. 
    5 f  U0 r1 n  |, G. L5 P
13. 　　/*分配内存空间，返回该内存空间的地址*/
    7 R& O$ p& W9 }8 _9 F% C/ m, v
14. 
    
15. 　　pNew=(struct Student *)malloc(sizeof(struct Student));
    ) i3 b8 N7 b$ c7 ?8 w
16. 
    / H2 o! U) J+ {% |
17. 　　scanf("%s",pNew->cName);
    
18. 
    
19. 　　scanf("%d",&pNew->iNumber);
      K" I8 ?! f2 d4 M9 X4 ?8 ~' n6 n
20. 
    
21. 　　pNew->next=p->next;/*新结点指针指向原来的结点*/
    1 [  u# y3 w# K* ~9 o- d0 `. ~" |
22. 
    0 J* a; w0 c6 h* e0 R
23. 　　p->next=pNew;/*头指针指向新结点*/
    
24. 
    / k8 f; o% ?% b
25. 　　iCount++;/*增加链表结点数量*/
    9 |5 y& f7 d4 q1 w4 t- `; o+ u
26. 
    
27. 　　return pHead;/*返回头指针*/
    : I2 }4 U) r+ E. N5 x
28. 
    
29. 　　}

复制代码

8 `) B& I$ p3 o) E2 c5 k# H- q" P

　　删除函数：

: B; D# v' t2 k2 g1 D7 K6 B0 q

0 P3 T0 e  s( b, ]& s
& L- o7 @4 ^3 K

1. 　void Delete(struct Student *pHead,int number)
   
2. 
   6 X2 r, g  n2 w! z
3. 　　{
   
4. 
   " h; ~/ B' c0 K' k
5. 　　int i;
   
6. 
   * k# t, t  y$ K/ n
7. 　　struct Student *pTemp;/*临时指针*/
   + N4 ?* o2 ]1 u& X2 m
8. 
   
9. 　　struct Student *pPre;/*表示要删除结点前的结点*/
   7 I9 P+ O! u. E, L3 |
10. 
    
11. 　　pTemp=pHead;/*得到链表的头结点*/
    % \3 {8 ~* h2 {" Y) @! l+ a" ~
12. 
    
13. 　　pPre=pTemp;
    
14. 
    
15. 　　for(i=0;i
    0 e- u3 T, P& b6 G  o
16. 
    
17. 　　{/*通过for循环使得Temp指向要删除的结点*/
    
18. 
    
19. 　　pPre=pTemp;
    2 o2 h! k; j( V6 W9 u
20. 
    - }5 H! F* n5 ^3 ^6 O7 b. _8 g4 P4 v
21. 　　pTemp=pTemp->next;
    
22. 
    , x. J1 t% C. u+ p4 v$ v* Y
23. 　　}
    
24. 
    9 r7 B# p8 ?/ r; Z" A: C# e
25. 　　pPre->next=pTemp->next;/*连接删除结点两边的结点*/
    9 A# T* i6 y6 ?2 m) h* H6 v8 V1 ]7 r
26. 
    ! F: t1 f% c6 ]1 F7 Z/ q
27. 　　free(pTemp);/*释放要删除结点的内存空间*/
    8 l" C' [4 z6 s# J) g
28. 
    
29. 　　iCount--;/*减少链表中的结点个数*/
    
30. 
    6 [0 w3 _6 C7 z! j- V" b7 p  b1 H3 P. [
31. 　　}

复制代码

1 F" L$ h" q0 ]' t0 u% T

, y# F, a) E8 i/ H3 O; ?, Y　　四、双向链表的概念
　　双向链表基于单链表。单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。
: B$ F, S, K5 T% S6 L0 f　　在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点的地址，一般称为右链域;一个存储直接前驱结点地址，一般称之为左链域。
　　双向链表结构示意图：

9 z. I' u/ b0 m6 g  U6 [8 f. x
6 H; f  r6 K# u8 \

　　

　　五、双向链表的建立与遍历
, M, J, X# f! B　　双向链表的源码实战和单链表类似，只是多了第二个指针域的控制，这里直接贴上没有注释的源代码。

9 L+ X( `8 H. l; n

4 g0 Z7 K1 k% g0 J+ o

1. 　　#include #include
   & U) k2 w1 n3 N* {( y; R' _
2. 
   
3. 　　#include
   
4. 
   
5. 　　#define N 10
   
6. 
   * I9 O4 O. {( g( e3 J* B7 F( v
7. 　　typedef struct Node
   
8. 
   9 ]- `- S& O8 x) {6 t, f
9. 　　{
   9 `, m, y0 {& a; m, Q9 w
10. 
    % f9 t3 X) v  R8 z
11. 　　char name[20];
    : ^9 v8 F3 a9 w5 x1 d& I
12. 
    - z9 y; n/ w  f/ U; u0 b* V  U! m3 D+ @" f+ T
13. 　　struct Node *llink,*rlink;
    
14. 
    
15. 　　}STUD;
    1 S/ C' Z9 f0 Y# V; h. L
16. 
    ; O4 k' Y) k& d  L8 d, V3 v. S
17. 　　STUD *creat(int);void print(STUD *);
    
18. 
    
19. 　　int main()
    
20. 
    
21. 　　{
    
22. 
    ( H, J) O6 S! Z: Q) Z
23. 　　int number;
    
24. 
    
25. 　　char studname[20];
    
26. 
    
27. 　　STUD *head,*searchpoint;
    0 g7 d% e- ^5 k7 S
28. 
    9 S: K. V: A8 q, m$ _/ t
29. 　　number=N;
    ; v! f5 v# O& R5 p' X
30. 
    # y* i; V, F6 @7 [6 n
31. 　　head=creat(number);
    / T) K8 ~; r, h9 M
32. 
    
33. 　　print(head);
    
34. 
    
35. 　　printf("请输入你要查找的人的姓名：");
    8 g. Q; o& Q$ \7 V) H- D6 ^
36. 
    2 W1 b9 L7 U  r+ y$ \& ?
37. 　　scanf("%s",studname);
    
38. 
    4 Y" Y9 A% |; B( F/ E# }8 w1 o
39. 　　searchpoint=search(head,studname);
    
40. 
    $ O% a( i3 {4 ?% c& Z0 U
41. 　　printf("你所要查找的人的姓名是：%s",*&searchpoint->name);
    
42. 
    & t  n& e* A) t2 e9 S* K. |
43. 　　return 0;
    + j% Y4 G, n* b- `, `
44. 
    , N2 g3 l+ h4 ^4 N7 m
45. 　　}
    
46. 
    
47. 　　STUD *creat(int n)
    
48. 
    0 c  i" m% ~9 h0 I0 d
49. 　　{
    
50. 
    9 J- L0 x8 U2 K; G0 @1 ^3 N* d
51. 　　STUD *p,*h,*s;
    : m2 n6 h! r: c5 a2 a
52. 
    
53. 　　int i;
    
54. 
    & o% _! f$ O4 ~+ K0 L  X! k4 q
55. 　　if((h=(STUD *)malloc(sizeof(STUD)))==NULL)
    ( `8 w) N  s. Z! S% v
56. 
      t) f8 X) }" N
57. 　　{
    3 e) C7 P6 k; K1 B
58. 
    ! h# N* z. V9 a% N
59. 　　printf("不能分配内存空间");
    
60. 
    
61. 　　exit(0);
    9 y) S" D: y8 [) r' p4 i$ j+ ]: c
62. 
    3 E% N" ]3 |8 d: i$ A0 v3 m
63. 　　}
    , M1 Q  \; V3 T$ w  z4 n3 }
64. 
    ! Y0 U8 s) \5 L, u. o" z8 d
65. 　　h->name[0]='\0';
    2 F  ?, R1 O3 q0 o
66. 
    
67. 　　h->llink=NULL;
    
68. 
    
69. 　　h->rlink=NULL;
    + g. k, w/ v( s9 K( W
70. 
    6 w. ]% N- B) e, d
71. 　　p=h;
    
72. 
    * ~8 Z3 H0 l  K' O7 Z! Y
73. 　　for(i=0;i
    
74. 
    & _( {$ p2 R* I; R
75. 　　{
    # h6 n/ G( i( `  M1 s3 R
76. 
    
77. 　　if((s=(STUD *)malloc(sizeof(STUD)))==NULL)
    , y6 l/ f! I* w$ T
78. 
    
79. 　　{
    
80. 
    
81. 　　printf("不能分配内存空间");
    9 l0 V5 F, l8 l" t4 J( Q& u
82. 
    
83. 　　exit(0);
    * M2 D- o4 a7 u/ R
84. 
    
85. 　　}
    
86. 
    , i; E: e/ q* O
87. 　　p->rlink=s;
    
88. 
    , u1 G7 a( H+ \# \( Q1 E+ j
89. 　　printf("请输入第%d个人的姓名",i+1);
    
90. 
    
91. 　　scanf("%s",s->name);
    6 X# t) @4 P5 Z# D
92. 
    ! L# F8 h# C- _; @
93. 　　s->llink=p;
    
94. 
    
95. 　　s->rlink=NULL;
    , S; N# z7 C4 ?$ _
96. 
    ; F4 H% L) f, y$ p" X% e
97. 　　p=s;
    , ~* X4 v6 [! d8 c. `" s
98. 
    0 Q: y4 R. e9 _) L% [0 b2 c7 A# ?' p
99. 　　}
    3 B" |1 ?1 c- n+ R1 _! N
100. 
     / M* n  M5 O+ T  [( F8 ?& X6 N  x
101. 　　h->llink=s;
     
102. 
     
103. 　　p->rlink=h;
     # w6 D4 P2 l5 b" f$ k& _. G, C3 P
104. 
     3 u' O* C: y& r4 [  J4 I3 o) c$ U$ w
105. 　　return(h);
     ( M7 h% ~: G) u* Q5 B
106. 
     
107. 　　}void print(STUD *h)
     2 L, ~2 B) ~; J: w# _6 z
108. 
     5 m/ _' s1 t% E/ D
109. 　　{
     
110. 
     + A/ y) ^* \8 |* Q9 u
111. 　　int n;
     8 c3 U1 v. W7 F$ m- y* ^
112. 
     3 D, u" U' A! P! x, r. ~0 y
113. 　　STUD *p;
     
114. 
     
115. 　　p=h->rlink;
     - ]; x9 B- q1 z$ r2 M" v
116. 
     
117. 　　printf("数据信息为：\n");
     
118. 
     
119. 　　while(p!=h)
     
120. 
     7 Y' V) c% P, z$ g0 v9 s/ Y
121. 　　{
     " ?3 |7 n7 u. q  `
122. 
     
123. 　　printf("%s ",&*(p->name));
     % k% g: j. a" p, `% p  B
124. 
     
125. 　　p=p->rlink;
     
126. 
       f' ?8 ^* W: s( Q% y$ _/ \
127. 　　}
     / d$ W/ ]0 T, B5 j9 M* n. N5 \
128. 
     + }4 ?5 [' a8 I/ `: v
129. 　　printf("\n");
     
130. 
     % A1 R- Y# i; F: E. o6 C
131. 　　}

复制代码

; \. u8 E, n2 T$ Y! ?
　　六、双向链表的元素查找
3 Q6 W+ r  x2 {" s$ O　　查找函数 STUD *search(STUD *,char *);
  s! l4 i% Y8 i- d6 }& |9 T
1 p0 s% V/ [1 Y4 [. n$ D

1 C* G4 r8 J3 `

1. 　　STUD *search(STUD *h,char *x)
   
2. 
   $ @/ v7 q6 ^3 b3 f' s8 K# `
3. 　　{
   
4. 
   9 j) y  Q; {. w8 V" t1 Z; P
5. 　　STUD *p;
   
6. 
   
7. 　　char *y;
   
8. 
   
9. 　　p=h->rlink;
   8 [5 k6 z( m/ t4 A) X% E
10. 
    
11. 　　while(p!=h)
    
12. 
    1 g  r1 u, [' t
13. 　　{
    
14. 
    
15. 　　y=p->name;
    6 f9 @5 i% Y4 _% Y! M, O2 I) t! z
16. 
    
17. 　　if(strcmp(y,x)==0)
    
18. 
    
19. 　　return(p);
    9 C, Q3 y. b- T/ n4 o! B+ k8 j
20. 
    % K1 d- ~' t) k- l
21. 　　else
    
22. 
    ; p' c6 h2 K4 v# z" D/ L, e! p5 F- E
23. 　　p=p->rlink;
    6 z8 A' o5 _* Z, P% S% Y# Y; L
24. 
    ! Y0 D- p( I& l( M1 F9 y4 Z
25. 　　}
    ! R5 s$ \6 U+ V- ^
26. 
    " L  j  b& f" b
27. 　　printf("没有查到该数据!");
    
28. 
    ! P* l% l% J- V, M$ ?
29. 　　}

复制代码

1 _' h( D' m) f  q

　　七、循环链表的概念
　　类似于单链表，循环链表也是一种链式的存储结构，由单链表演化而来。
& L( c1 E, K' a0 N  `) O　　单链表的最后一个结点的指针指向NULL，而循环链表的最后一个结点的指针指向链表头结点。
　　这样头尾相连，形成了一个环形的数据链。
  U* I6 L" x+ B0 E* G' P5 h& O　　循环链表的建立不需要专门的头结点。
　　判断循环链表是否为尾结点时，只需判断该节点的指针域是否指向链表头节点。
　　八、合并两个链表的实例
: R5 V* c- S8 @% r2 n　　建立两个带头节点的学生链表，每个节点包含学号、姓名和成绩，链表都按学号升序排列，将它们合并为一个链表仍按学号升序排列。
　　算法分析：
# w8 @* P( b  h8 S　　合并链表用merge()函数实现。函数中定义3个工作指针a、b、c，其中a、b分别指向La链表、Lb链表的当前结点，C指向合并后的链表尾结点。合并后链表的头结点共用La链表的头结点。
　　①合并前，先让a和b分别指向两个链表的第一个结点，c指向La链表的头结点。
　　②合并时应该分3种情况讨论，即La和Lb都没有处理完;La没处理完，但Lb处理完毕;Lb没处理完，但La处理完毕。
　　③合并过程中应始终将La和Lb链表中较小的一个链接在Lc中，方能保持有序。

3 a& Y7 D8 G; x2 Q& w6 w: v0 s3 s% \

1. 　void merge(struct stud *La,struct stud *Lb)
   
2. 
   
3. 　　{
   
4. 
   
5. 　　struct stud *a,*b,*c;
   4 D3 g. X' \7 Q% O
6. 
   3 o8 P+ U; k( G( @! m* @  m: v
7. 　　c=La;
   
8. 
   
9. 　　a=La->next;/* 合并前 */
   + B9 e/ J* X4 c9 j6 {# y- n
10. 
    0 m7 U4 T* x/ h/ M
11. 　　b=Lb->next;
    
12. 
    ; h$ g; H( C- ]
13. 　　while(a!=NULL && b!=NULL)/* La和Lb都没处理完 */
    ; s3 q2 u9 E3 B/ V- }  C5 Y- d
14. 
    
15. 　　{
    ! G# J2 J  x0 O' v9 }* E# k4 |( \
16. 
    
17. 　　if(a->num <= b->num)
    
18. 
    , q) ~6 k  x4 t& w
19. 　　{
    / F- ]5 x$ B0 m& t6 E3 J
20. 
    
21. 　　c->next=a;
    
22. 
    
23. 　　c=a;
    , `/ H2 ?" y8 c8 n
24. 
    
25. 　　a=a->next;
    
26. 
    / z, C/ H" k5 z5 }
27. 　　}
    & w. E$ I6 E- _4 w3 Z& ?
28. 
    
29. 　　else
    
30. 
    
31. 　　{
    
32. 
    
33. 　　c->next=b;
    % ]4 S2 ~9 l# U6 l4 u) ~
34. 
    + [& P4 T8 ?+ j, `* V$ n6 F
35. 　　c=b;
    , S9 S. y8 O4 p  C9 S
36. 
    8 ^# }& ]3 D3 Y- J
37. 　　b=b->next;
    6 V1 I; w" p+ o. n' O/ i3 |
38. 
    
39. 　　}
    
40. 
    1 u5 _' q: |+ J4 g
41. 　　}
    + w0 E; B3 F5 K" Y
42. 
    
43. 　　if(a!=NULL)
    
44. 
    
45. 　　c->next=a;/* 若La没有处理完 */
    
46. 
    7 K! h6 L8 ~" u# `6 S0 R
47. 　　else
    % L) k6 H; B, X9 |" M! @9 a
48. 
    
49. 　　c->next=b;/* 若Lb没有处理完 */
    
50. 
    
51. 　　free(Lb); /* 释放Lb的头结点 */
    * [  S0 f- C" `- U
52. 
    
53. 　　}

复制代码

5 D7 c0 L/ \: ~" H; E