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

小样岁月

　　最近临近期末的C语言课程设计比平时练习作业一下难了不止一个档次，第一次接触到了C语言的框架开发，了解了View(界面层)、Service(业务逻辑层)、Persistence(持久化层)的分离和耦合，一种面向过程的MVC的感觉。
( g6 r; W0 g. O. H4 }! w　　而这一切的基础就在于对链表的创建、删除、输出、写入文件、从文件读出......
6 R4 Z6 j' U- ]  }, J　　本篇文章在于巩固链表的基础知识(整理自《C语言程序设计教程--人民邮电出版社》第十章——指针与链表)，只对链表的概念及增删改查作出探讨，欢迎指教。
' h% @' c6 ~9 y0 V4 p  `. q　　一、链表结构和静态/动态链表
　　二、单链表的建立与遍历
0 k& ?, |$ w% s# r3 d　　三、单链表的插入与删除
2 a# H& _7 j2 N/ `% j% Z, K, Y: m# F　　四、双向链表的概念
6 o4 F. q5 y4 D0 a6 s7 C: Q　　五、双向链表的建立与遍历
0 M5 o2 d9 y9 d8 I　　六、双向链表的元素查找
/ i2 b5 k- V5 {8 B/ c$ Y　　七、循环链表的概念
  j" h: }0 S6 @- O0 v　　八、合并两个链表的实例
9 c8 b/ X# d/ b8 j　　九、链表实战
$ {: j. w* x7 D# f2 {, C9 i　　拓展思维、拉到最后去看看 (•̀ᴗ•́)و ̑̑
5 I$ C7 ^7 S! m' S　　一、链表结构和静态/动态链表
5 K2 {# }3 q3 n! G! x　　链表是一种常见的数据结构——与数组不同的是：
　　1.数组首先需要在定义时声明数组大小，如果像这个数组中加入的元素个数超过了数组的长度时，便不能正确保存所有内容;链表可以根据大小需要进行拓展。
　　2.其次数组是同一数据类型的元素集合，在内存中是按一定顺序连续排列存放的;链表常用malloc等函数动态随机分配空间，用指针相连。
　　链表结构示意图如下所示：

　　

0 v7 f0 c( C2 F3 h　　在链表中，每一个元素包含两个部分;数据部分和指针部分。数据部分用来存放元素所包含的数据，指针部分用来指向下一个元素。最后一个元素的指针指向NULL，表示指向的地址为空。整体用结构体来定义，指针部分定义为指向本结构体类型的指针类型。
5 m- o9 j  Z2 P/ z2 l　　静态链表需要数组来实现，即把线性表的元素存放在数组中。数组单元存放链表结点，结点的链域指向下一个元素的位置，即下一个元素所在数组单元的下标。这些元素可能在物理上是连续存放的，也有可能是不连续的，它们之间通过逻辑关系来连接——这就要涉及到数组长度定义的问题，实现无法预知定义多大的数组，动态链表随即出现。
　　动态链表指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点的数据，并建立起前后相连的关系。
# k& ~$ |4 C8 X  F' u" {4 t　　二、单链表的建立与遍历
6 I  Q0 l4 [$ U# J' F% o3 p4 W　　单链表中，每个结点只有一个指针，所有结点都是单线联系，除了末为结点指针为空外，每个结点的指针都指向下一个结点，一环一环形成一条线性链。
# L& x' i% _) F6 a* s+ ~6 j5 J- C　　链表的创建过程：
( ?: P6 l6 s. ~; q6 w$ h+ k

　　

; ]/ B! {, g& t: C" k　　接下来在源码中建立并遍历输出一个单链表。



' B" n6 F9 d$ w: h

1. 　　#include
   3 @" J* p: v4 i, v
2. 
   
3. 　　#include
   . t& _. ~1 L7 l7 D& F
4. 
   5 e" C$ I. j2 P7 Q0 _/ z0 B
5. 　　#include
   + f7 U3 o5 i6 U1 J" l8 w
6. 
   
7. 　　/*单向链表*/
   : n' N$ U. u$ X
8. 
   
9. 　　struct Student/*建立学生信息结构体模型*/
   
10. 
    6 [, X0 X$ j. _  n, [8 y8 Y% ^
11. 　　{
    : ^0 q/ R% d3 v$ N6 z2 K
12. 
    
13. 　　char cName[20];/*学生姓名*/
    * ?+ a5 ]9 [0 i6 K  Q1 w
14. 
    
15. 　　int iNumber;/*学生学号*/
    0 x/ z# _$ ?; b$ m% D: o: W
16. 
    
17. 　　struct student *next;/*指向本结构体类型的指针类型*/
    # I9 d6 H3 z+ E& y
18. 
    ; d3 Y* I7 g9 j$ _/ M
19. 　　};
    8 k0 l$ {) q" F! L7 q0 A. B7 N
20. 
    . \# d  E2 r$ V) |$ Z* G
21. 　　int iCount;/*全局变量表示链表长度*/
    
22. 
    ! ?- @! E6 w2 e
23. 　　struct Student *Create();/*创建链表函数声明*/
    & N# h$ N. L4 H' Z. a8 p0 _' F( k4 d
24. 
    
25. 　　void print(struct Student *);/*遍历输出链表函数声明*/
    6 F& [! x/ j# k
26. 
    $ J4 U1 }- q1 z* J
27. 　　int main()
    4 S$ P, b7 k. X# Z+ i9 K
28. 
    $ V. e) Z1 X+ W9 r
29. 　　{
    7 R8 ?- u2 w5 D0 l, c' c  l% N
30. 
    ! j: K. ~" c" D7 Q( z" ^0 B, B
31. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
    
32. 
    
33. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
    - K* ~; M$ c, S' X% R2 Y7 F
34. 
    
35. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
    . ?/ {: E- `% F7 `2 q  f& o' X
36. 
    : N) u) l* k2 X, M0 }" w
37. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    
38. 
    
39. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    - l6 \5 q4 [7 i7 [
40. 
    " j$ Z7 O* Z8 `( i' n( |
41. 　　return 0;
    . M7 ~+ l8 {1 s7 s" f1 ~% O7 }3 p
42. 
    
43. 　　}
    
44. 
    
45. 　　struct Student *Create()
    $ a/ v0 n; z8 |$ c, \
46. 
    
47. 　　{
    7 n  H: F1 H, I' K
48. 
    
49. 　　struct Student *pHead=NULL;/*初始化链表，头指针为空*/
    
50. 
    
51. 　　struct Student *pEnd,*pNew;
    
52. 
    
53. 　　iCount=0;/*初始化链表长度*/
    2 u, B$ R, `& m! j. t! {: @
54. 
    & s* [. e5 Z( z& I
55. 　　pEnd=pNew=(struct Student *)malloc(sizeof(struct Student));/*动态开辟一个学生信息结构体类型大小的空间，使得pEnd和pNew同时指向该结构体空间*/
    
56. 
    . W# q4 q6 `3 |6 a3 X! A: v1 _
57. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    - l( H  k) w6 I( x  W9 N
58. 
    
59. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    4 g# i" P2 }( Y) _& j: W7 I
60. 
    
61. 　　while(pNew->iNumber!=0)/*设定循环结束条件——学号不为0时*/
    2 f" i+ k* |5 h& ?1 d# ?; F
62. 
    - ~, j6 I) H3 p9 r) ^( E
63. 　　{
    # K$ l4 @3 _& E
64. 
    # m5 _2 p" [- U* s/ o2 x
65. 　　iCount++;/*链表长度+1，即学生信息个数+1*/
    
66. 
    
67. 　　if(iCount==1)/*如果链表长度刚刚加为1，执行*/
    
68. 
    
69. 　　{
    7 l2 ~! A/ @# q  ]) J* w: J6 b
70. 
    # x: a! P, g1 G- D  @7 U6 w
71. 　　pNew->next=pHead;/*使指针指向为空*/
    : z3 F( ?+ s- ?- ]
72. 
    
73. 　　pEnd=pNew;/*跟踪新加入的结点*/
    
74. 
    
75. 　　pHead=pNew;/*头结点指向首结点*/
    * \. D$ _- q6 L! q; A; M+ U
76. 
    
77. 　　}
    / c: v' o5 {9 r- p
78. 
    " C9 O* ^( p' P# d6 r7 g9 J
79. 　　else/*如果链表已经建立，长度大于等于2时，执行*/
    ; A) U6 A. }' |
80. 
    ) }6 t4 l# n  V
81. 　　{
    
82. 
    
83. 　　pNew->next=NULL;/*新结点的指针为空*/
    
84. 
    : L  D5 y/ y: C
85. 　　pEnd->next=pNew;/*原来的结点指向新结点*/
    
86. 
    $ \, V: e( y5 Q3 R# I* _9 ]
87. 　　pEnd=pNew;/*pEnd指向新结点*/
    $ w4 r% N6 A. h: X, j
88. 
    ! c* z: q7 b/ O4 k
89. 　　}
    ' a8 [  K0 o# X7 r* u# o( Y
90. 
    & Y% I' b8 W( P/ B6 I# ^
91. 　　pNew=(struct Student *)malloc(sizeof(struct Student));/*再次分配结点的内存空间*/
    
92. 
    ! H7 W$ Q0 E1 V# S  E, p$ J
93. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    
94. 
    6 j) t3 M1 s/ \9 g# i) ^
95. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    : u# t9 P8 G- j+ V: Y2 S$ S
96. 
    8 W% n% C( J8 R" h
97. 　　}
    
98. 
    
99. 　　free(pNew);/*释放结点空间*/
    
100. 
       |1 U0 M: l& J. L
101. 　　return pHead;/*返回创建出的头指针*/
     ' I/ y! v: A, \5 h3 f- n
102. 
     & }1 P9 R. c9 A$ k$ L3 Y  |
103. 　　}
     " C, t  o1 Q" b0 ?2 G' X8 c
104. 
     
105. 　　void print(struct Student *pHead)
     
106. 
     
107. 　　{
     / ?$ T) ]; |2 [( ]  D
108. 
     * ~) y$ E& V2 e) B4 M, f* r2 P
109. 　　struct Student *pTemp;/*定义指向一个学生信息结构体类型的临时指针*/
     
110. 
     $ k; q% z! M2 P* N$ p( N: X" k
111. 　　int iIndex=1;/*定义并出事哈变量iIndex，用来标识第几个学生(信息)*/
     
112. 
     
113. 　　printf("总共%d个学生(信息)：\n",iCount);
     7 }4 o2 b3 d% j5 D. v
114. 
     6 M7 x, m# H8 A! A
115. 　　pTemp=pHead;/*指针得到首结点的地址*/
     
116. 
     ) x+ z( O, Q9 O4 Z6 I
117. 　　while(pTemp!=NULL)/*当临时指针不指向NULL时*/
     
118. 
     
119. 　　{
     
120. 
     # E4 z  k* T' D( ^7 z  C
121. 　　printf("第%d个学生信息：\n",iIndex);
     5 V# s: ?  y8 t  m, v
122. 
     
123. 　　printf("姓名：%s",pTemp->cName); /*输出姓名*/
     
124. 
     
125. 　　printf("学号：%d",pTemp->iNumber);/*输出学号*/
     
126. 
     0 s9 m- L% o' Z: h4 P( l
127. 　　pTemp=pTemp->next;/*移动临时指针到下一个结点*/
     
128. 
     
129. 　　iIndex++;/*进行自加运算*/
     
130. 
     9 x8 o* ^, K3 D. [
131. 　　}
     
132. 
     4 j, C8 @$ s7 b- k) _
133. 　　}

复制代码

; M5 y% Y/ f* D# W3 g  X
# i" u$ W7 o: `: n% e9 e) A

3 U/ `9 @, P2 y! m6 c　　三、单链表的插入与删除
7 `. j2 K+ V: S6 K& G# h, K) I; o　　在本实例中，插入时根据传递来的学号，插入到其后。
, M$ c. |( o' \2 a$ G. C7 {" w　　删除时根据其所在链表的位置，删除并释放该空间。
; v3 P/ y( I0 a! ^9 {1 b　　主函数增加如下：


( t6 y. n& m. z3 U  {& z
/ v  \3 X  H. K# X' H0 i+ q% q. A! {; \

1. 　　int main()
   
2. 
   ; j. b4 S; y# j+ o
3. 　　{
   " M1 J* y' ~- u# d: k& n5 c- x
4. 
   
5. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
   
6. 
   
7. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
   
8. 
   7 d  R# c3 {6 ?! [, D+ n
9. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
   : i/ e# u, d1 u) |# e0 d5 N, v, u7 o
10. 
    
11. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    
12. 
    
13. 　　pHead=Insert(pHead,insert_n);/*将指针pHead和要插入的结点数传递给插入函数*/
    " D7 e. V& s5 E: b6 O4 f
14. 
    
15. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    ) ]& Z* Q4 [# W, L% q; P- t( e
16. 
    
17. 　　Delete(pHead,delete_n);/*将指针pHead和要删除的结点数传递给删除函数*/
    - O  |. C$ Y: r8 n! B: P
18. 
    
19. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    ! |, Q4 a* |8 o: K3 A5 ]
20. 
    
21. 　　return 0;
    2 W$ p" J( X4 j! a- d  g, Q3 o! m+ X
22. 
    - k; X" ^, s$ h0 R$ n' v8 {* M3 G
23. 　　}

复制代码

2 R1 [8 K; ?. @0 Z" D% Z

　　插入函数：
: {2 R/ i7 I4 _$ `; g' ~: p
3 l" y$ k; F2 q) H  F. b2 O

( ?0 t0 y( P! N  Y$ @; X; \

1. 　　struct Student *Insert(struct Student *pHead,int number)
   
2. 
   
3. 　　{
   
4. 
   8 ]( K# c$ [* u. Y, Z& L9 A
5. 　　struct Student *p=pHead,*pNew;/*定义pNew指向新分配的空间*/
   
6. 
   
7. 　　while(p&&p->iNumber!=number)
   
8. 
   
9. 　　p=p->next;/*使临时结点跟踪到要插入的位置(该实例必须存在学号为number的信息，插入其后，否则出错)*/
   
10. 
    " J& P* [4 f% w! R5 Z
11. 　　printf("姓名和学号：\n");
    6 B! M  w+ G! s6 m7 S
12. 
    6 V* L' r. W. q& U- G' l
13. 　　/*分配内存空间，返回该内存空间的地址*/
    
14. 
    
15. 　　pNew=(struct Student *)malloc(sizeof(struct Student));
    7 o9 t9 ^4 p" Y
16. 
    
17. 　　scanf("%s",pNew->cName);
    
18. 
    
19. 　　scanf("%d",&pNew->iNumber);
    " k, y8 k2 T* c2 {( q0 b
20. 
    , }9 f9 Y2 b9 X- X+ c% @
21. 　　pNew->next=p->next;/*新结点指针指向原来的结点*/
    & t9 V- [  z6 {2 j: L
22. 
    
23. 　　p->next=pNew;/*头指针指向新结点*/
    0 {' Q) A+ x3 }6 y  w+ o  H+ W+ E
24. 
    
25. 　　iCount++;/*增加链表结点数量*/
    
26. 
    & P" F- V8 M$ @; n$ Y
27. 　　return pHead;/*返回头指针*/
    
28. 
    " \6 U5 u; M, g- {  z
29. 　　}

复制代码

　　删除函数：


9 d! c4 ^0 h- u0 i' e

1. 　void Delete(struct Student *pHead,int number)
   3 T' w+ a, p' W/ _8 a
2. 
   $ m6 e/ c" j+ t0 o0 P
3. 　　{
   9 `* [" |+ o; k
4. 
   
5. 　　int i;
   ! C/ d6 {$ F% w; R9 t6 L
6. 
   
7. 　　struct Student *pTemp;/*临时指针*/
   8 G6 A/ W/ q' Y  X4 c, E/ h
8. 
   ( V' m" v7 b7 S5 s# _( }
9. 　　struct Student *pPre;/*表示要删除结点前的结点*/
   
10. 
    6 M7 ?$ a% {: |; L' j$ _4 u
11. 　　pTemp=pHead;/*得到链表的头结点*/
    " B9 z* |% V6 a  G
12. 
    
13. 　　pPre=pTemp;
    ) y: E( |% e5 u. P) m" n
14. 
    
15. 　　for(i=0;i
    ! w' L; n' O; G2 o) p  ^$ t
16. 
    
17. 　　{/*通过for循环使得Temp指向要删除的结点*/
      L' q0 K0 m+ [2 K
18. 
    
19. 　　pPre=pTemp;
    : b# L: V+ ~, w9 S6 M6 _
20. 
    
21. 　　pTemp=pTemp->next;
    
22. 
    * |3 N  Z& i4 W2 U3 T3 O/ [
23. 　　}
    
24. 
    
25. 　　pPre->next=pTemp->next;/*连接删除结点两边的结点*/
    ' L5 z7 C, M0 O/ A; ^, @; r! D
26. 
    ; d: h0 |  S* B/ H
27. 　　free(pTemp);/*释放要删除结点的内存空间*/
    : I) w" j# _# W4 J  w3 _5 c
28. 
    9 Y! U9 }+ `) v9 `& R, `" ?
29. 　　iCount--;/*减少链表中的结点个数*/
    " J* [: U/ h3 a' ~1 L, m
30. 
    7 C+ {' G1 p* G6 M! H
31. 　　}

复制代码

, U$ r) v1 W0 n5 f& s
& g; x! s& K/ @, x3 A: G3 M; {8 ~5 g3 F　　四、双向链表的概念
( c, J# d9 h. G3 p　　双向链表基于单链表。单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。
　　在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点的地址，一般称为右链域;一个存储直接前驱结点地址，一般称之为左链域。
+ \! \* x4 m" {: j; L* m　　双向链表结构示意图：


2 E8 r5 G: b0 K4 g

　　

) @! Z  F- v# z! F- \　　五、双向链表的建立与遍历
0 k7 j0 M. a+ m; P5 e+ N　　双向链表的源码实战和单链表类似，只是多了第二个指针域的控制，这里直接贴上没有注释的源代码。
, |# M% w1 Y! W$ E. J
) q' X$ H; |% c6 _% P5 K0 J

- h5 Y# R& M' h1 G5 n

1. 　　#include #include
   
2. 
   : k( U% U( _; ]/ T. R- ]
3. 　　#include
   
4. 
   3 V$ t, K) y" u' T& x! Z' o
5. 　　#define N 10
   : h7 p* {! Z# e; A" w
6. 
   6 A! Y& ]5 D) q/ s+ o+ |
7. 　　typedef struct Node
   - ~' y$ ~1 {9 M/ U1 z3 Y
8. 
   
9. 　　{
   
10. 
    
11. 　　char name[20];
    7 I6 T$ L% T, Z0 E9 I
12. 
    ! Z- P6 k. m" }( R
13. 　　struct Node *llink,*rlink;
    
14. 
    
15. 　　}STUD;
    
16. 
    
17. 　　STUD *creat(int);void print(STUD *);
    % h/ R4 Y6 r4 j; X' g6 B
18. 
    " Z" N" d/ j3 q5 ~  @
19. 　　int main()
    
20. 
    
21. 　　{
    
22. 
    
23. 　　int number;
    
24. 
    9 q8 ]% X+ L+ V4 n7 ^
25. 　　char studname[20];
    
26. 
    / l$ X7 k* c; L+ C6 ?+ g
27. 　　STUD *head,*searchpoint;
    
28. 
    2 W; V4 L" ^- o! o( k+ Y: G
29. 　　number=N;
    
30. 
    % h3 G* w- |# V, j5 }, d
31. 　　head=creat(number);
    3 j: u8 v$ j$ ^- {7 Y! F
32. 
    4 o# n% b! Y/ Y
33. 　　print(head);
    
34. 
    9 r* [' H8 Y: i$ e- p% e
35. 　　printf("请输入你要查找的人的姓名：");
    
36. 
    7 `  g6 ?) J0 ]8 u
37. 　　scanf("%s",studname);
    2 F1 u( y: \6 g- q2 `" X
38. 
    # O3 ?0 @, T1 _) ~* F, \
39. 　　searchpoint=search(head,studname);
    
40. 
    
41. 　　printf("你所要查找的人的姓名是：%s",*&searchpoint->name);
    + W/ \, M+ W$ a5 ], u7 v% c! {
42. 
    . [0 k$ U$ l$ D4 y/ X5 x- ^
43. 　　return 0;
    % q. r- u. m5 V7 |
44. 
    ! ?# i% X+ A8 `. j' H) `, k
45. 　　}
    
46. 
    , a% k8 \" |+ M  Y9 y, X: c1 Q
47. 　　STUD *creat(int n)
    - o3 |3 o$ u  }) R, ]2 m0 h
48. 
    
49. 　　{
    
50. 
    & v1 ?" z( }& W  N
51. 　　STUD *p,*h,*s;
    
52. 
    
53. 　　int i;
    
54. 
    
55. 　　if((h=(STUD *)malloc(sizeof(STUD)))==NULL)
    
56. 
    ' o0 }+ h9 \% H' J* O& ?* t4 i
57. 　　{
    
58. 
    4 z8 H2 c, k- H
59. 　　printf("不能分配内存空间");
    7 Z- f& q/ ^8 ]
60. 
    
61. 　　exit(0);
    * J5 d& l+ I  |
62. 
    9 I2 l) V' }. y: A% d
63. 　　}
    
64. 
    
65. 　　h->name[0]='\0';
    
66. 
    & Z2 V8 K  e5 R/ k5 p/ ?( ?* x
67. 　　h->llink=NULL;
    2 m% d2 ^- z9 T4 [" y/ [
68. 
    / h3 A, R% R' `2 F! n4 @. v; G9 U
69. 　　h->rlink=NULL;
    
70. 
    * x/ @: f7 m7 |) {+ H5 j( b5 q
71. 　　p=h;
      \5 t( ?. ?4 L+ O" w
72. 
    
73. 　　for(i=0;i
    
74. 
    + g$ m% v1 I. b, \+ G% ]; _6 n7 g
75. 　　{
    5 C) x, N7 O( r0 b' h4 y& V
76. 
    $ @2 a* [& D( D' d/ V: n: m6 ^8 p
77. 　　if((s=(STUD *)malloc(sizeof(STUD)))==NULL)
    ! O* Y9 M! W2 @4 m" f
78. 
    
79. 　　{
    
80. 
    
81. 　　printf("不能分配内存空间");
    
82. 
    5 b$ r( ?% E6 O5 Q% d- b
83. 　　exit(0);
    ) L6 }0 A' z  r$ y
84. 
    " T5 Q% o! j  _. w( y
85. 　　}
    
86. 
    
87. 　　p->rlink=s;
    + g4 i1 r7 P! P
88. 
    
89. 　　printf("请输入第%d个人的姓名",i+1);
    
90. 
      y. @) j, M5 u! u
91. 　　scanf("%s",s->name);
    % G4 R1 ~8 q" K* H' b; l4 L. e% N
92. 
    - N. e' F) k. |$ i
93. 　　s->llink=p;
    
94. 
    
95. 　　s->rlink=NULL;
    
96. 
    8 i% c0 s8 e* z: O1 S
97. 　　p=s;
    ( v( t6 X1 {  K
98. 
    
99. 　　}
    
100. 
     
101. 　　h->llink=s;
       {. z& J+ s$ m  D+ H- r& W+ j
102. 
     
103. 　　p->rlink=h;
     ' P  E4 e$ f) F+ U, S
104. 
     
105. 　　return(h);
     4 @. \8 [* `$ |; `, p1 F0 ?
106. 
     
107. 　　}void print(STUD *h)
     8 ]6 p  J* V" k) j( ^
108. 
     
109. 　　{
     
110. 
     
111. 　　int n;
     
112. 
     & F& h% T5 X: O& ]( c
113. 　　STUD *p;
     + [! M8 R7 ?7 G9 Y3 y5 l; X
114. 
     
115. 　　p=h->rlink;
     / V+ {2 q* l1 N5 l; E, l) f- v3 }
116. 
     
117. 　　printf("数据信息为：\n");
     
118. 
     
119. 　　while(p!=h)
     . t1 B5 C5 q# ]. d8 c
120. 
     
121. 　　{
     8 ^* |9 d, ]5 E" `3 e/ ~; O
122. 
     8 b/ ^$ I! u9 C5 H4 E: a7 A
123. 　　printf("%s ",&*(p->name));
     
124. 
     
125. 　　p=p->rlink;
     $ f3 Q& A1 Y+ N# a
126. 
     
127. 　　}
     
128. 
     
129. 　　printf("\n");
     
130. 
     
131. 　　}

复制代码

　　六、双向链表的元素查找
　　查找函数 STUD *search(STUD *,char *);
. y; f( @+ z6 g7 B* y. `" M+ R

' ~0 v" O# U5 F, h& F
8 t0 o7 P9 M: A7 b9 e) u  C

1. 　　STUD *search(STUD *h,char *x)
   $ j- C; k' J5 B9 h4 z- H" [; W
2. 
   
3. 　　{
   + G: L3 K" R4 p4 P) Z
4. 
     y' B7 t4 o  [+ E+ @$ q4 ]
5. 　　STUD *p;
   
6. 
   
7. 　　char *y;
   
8. 
   
9. 　　p=h->rlink;
   
10. 
    1 i& H* W, b" `8 ^
11. 　　while(p!=h)
    1 S1 d/ h) Q" W0 _2 V6 f
12. 
    
13. 　　{
    
14. 
    
15. 　　y=p->name;
    ! D8 D# C  _7 s$ _- g
16. 
    ! F/ v6 S, \$ h/ z' m7 [
17. 　　if(strcmp(y,x)==0)
    6 B( N( n7 d8 E( Q6 D* z2 p
18. 
    : j7 c% ~$ q  ~
19. 　　return(p);
    7 z9 |% D: w5 I
20. 
    3 }6 `6 @/ r, v4 A6 c1 N
21. 　　else
    
22. 
    ' p( `/ ?- g% h/ @8 L
23. 　　p=p->rlink;
    
24. 
    
25. 　　}
    - y3 r. L0 V0 |" _  x
26. 
    4 W8 T) {+ z1 _" p! c# I
27. 　　printf("没有查到该数据!");
    ' W( S: h. h$ j( w  d
28. 
    $ a. t, i& u+ N
29. 　　}

复制代码

% J- t  p) I% V4 q$ M( \; F
2 B+ e, o! Q+ S8 C0 b
0 o/ k, D/ `. l9 j- h3 R$ _　　七、循环链表的概念
　　类似于单链表，循环链表也是一种链式的存储结构，由单链表演化而来。
! o. V( q  x$ x; X　　单链表的最后一个结点的指针指向NULL，而循环链表的最后一个结点的指针指向链表头结点。
　　这样头尾相连，形成了一个环形的数据链。
　　循环链表的建立不需要专门的头结点。
　　判断循环链表是否为尾结点时，只需判断该节点的指针域是否指向链表头节点。
9 F! B) Q$ z. N9 a　　八、合并两个链表的实例
2 |) U! {3 B4 Z　　建立两个带头节点的学生链表，每个节点包含学号、姓名和成绩，链表都按学号升序排列，将它们合并为一个链表仍按学号升序排列。
) [9 B( d4 p1 |& C　　算法分析：
　　合并链表用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中，方能保持有序。
& i( W- B4 ]# g9 Y: S0 b
* N- Q# F' r5 D/ @! u, V


* z3 Q8 _' b$ s) k7 g

1. 　void merge(struct stud *La,struct stud *Lb)
   
2. 
   5 E- h4 y! B- |* B6 {
3. 　　{
   ! }0 W) n8 k, {& C- E1 w
4. 
   1 |2 B$ v! W* }/ a
5. 　　struct stud *a,*b,*c;
   
6. 
   
7. 　　c=La;
   
8. 
   
9. 　　a=La->next;/* 合并前 */
   
10. 
    
11. 　　b=Lb->next;
    $ M3 M7 Z* a) ~5 N
12. 
    
13. 　　while(a!=NULL && b!=NULL)/* La和Lb都没处理完 */
    9 ]: t' y1 j9 N& K' M' K! V  Q
14. 
    
15. 　　{
    
16. 
    
17. 　　if(a->num <= b->num)
    # i5 R; X% B3 p& c& j1 ?
18. 
    
19. 　　{
    
20. 
    
21. 　　c->next=a;
    4 T* L3 B- v7 G( j4 v
22. 
    - C& A" ?& {' Y: T' `
23. 　　c=a;
      E4 E/ K( M6 Y# x/ H/ g# I1 A" A& H  @
24. 
    
25. 　　a=a->next;
    : B4 m9 H) i5 e+ j
26. 
    
27. 　　}
    
28. 
    
29. 　　else
    8 u$ l% j+ L& |, Y
30. 
    4 }4 @+ w" Q+ b. w
31. 　　{
    , j7 Z8 N+ l4 p- S& e7 Y7 \2 V- w" \
32. 
    : U, B. r4 l: _/ h6 h
33. 　　c->next=b;
    
34. 
    
35. 　　c=b;
    
36. 
    ; P( ~# j3 I& W! b/ `5 C- D" l2 m
37. 　　b=b->next;
    
38. 
    & V9 n& |" X" o9 `  R9 K
39. 　　}
    
40. 
    ; w: P5 _# P) }9 T
41. 　　}
    
42. 
    
43. 　　if(a!=NULL)
    
44. 
    $ e) u4 ~! R" |5 {
45. 　　c->next=a;/* 若La没有处理完 */
    
46. 
    % A# w5 b  e; q4 `: K
47. 　　else
    
48. 
    
49. 　　c->next=b;/* 若Lb没有处理完 */
    
50. 
    
51. 　　free(Lb); /* 释放Lb的头结点 */
    
52. 
    # u$ C' h) Y% O4 Z/ V4 x, ^# C
53. 　　}

复制代码

  H' c4 G0 {: p

, ~* s* l. U" J# N; v