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

小样岁月

　　最近临近期末的C语言课程设计比平时练习作业一下难了不止一个档次，第一次接触到了C语言的框架开发，了解了View(界面层)、Service(业务逻辑层)、Persistence(持久化层)的分离和耦合，一种面向过程的MVC的感觉。
1 f; t: k5 |  V5 N' g- R2 ~　　而这一切的基础就在于对链表的创建、删除、输出、写入文件、从文件读出......
　　本篇文章在于巩固链表的基础知识(整理自《C语言程序设计教程--人民邮电出版社》第十章——指针与链表)，只对链表的概念及增删改查作出探讨，欢迎指教。
　　一、链表结构和静态/动态链表
　　二、单链表的建立与遍历
/ Q% Y, M8 I3 N" X9 i* K　　三、单链表的插入与删除
* g8 M" P2 U8 w+ d" N5 ^6 d　　四、双向链表的概念
/ D& q5 t& Q% V0 T$ h6 P. H& R　　五、双向链表的建立与遍历
) l6 J1 e- d6 ~( t. D# P　　六、双向链表的元素查找
) Q3 T9 Y; K0 I3 \( E7 e8 U　　七、循环链表的概念
% h& k5 r: M3 f, I, U6 A6 o　　八、合并两个链表的实例
; t7 x: d& a& n# n　　九、链表实战
/ G9 F, A- g$ v' `' y, w9 J5 C　　拓展思维、拉到最后去看看 (•̀ᴗ•́)و ̑̑
0 ^6 `, ?( f/ }  w6 K　　一、链表结构和静态/动态链表
, k% `$ o3 {1 J) f% C　　链表是一种常见的数据结构——与数组不同的是：
+ K# H+ C. P% E; `! d7 j; {　　1.数组首先需要在定义时声明数组大小，如果像这个数组中加入的元素个数超过了数组的长度时，便不能正确保存所有内容;链表可以根据大小需要进行拓展。
　　2.其次数组是同一数据类型的元素集合，在内存中是按一定顺序连续排列存放的;链表常用malloc等函数动态随机分配空间，用指针相连。
1 t" ^3 v7 O* l1 f- ^7 [　　链表结构示意图如下所示：
3 N$ X1 R3 M0 K

　　

　　在链表中，每一个元素包含两个部分;数据部分和指针部分。数据部分用来存放元素所包含的数据，指针部分用来指向下一个元素。最后一个元素的指针指向NULL，表示指向的地址为空。整体用结构体来定义，指针部分定义为指向本结构体类型的指针类型。
　　静态链表需要数组来实现，即把线性表的元素存放在数组中。数组单元存放链表结点，结点的链域指向下一个元素的位置，即下一个元素所在数组单元的下标。这些元素可能在物理上是连续存放的，也有可能是不连续的，它们之间通过逻辑关系来连接——这就要涉及到数组长度定义的问题，实现无法预知定义多大的数组，动态链表随即出现。
　　动态链表指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点的数据，并建立起前后相连的关系。
* J  d7 A2 ?$ Q' H' g$ U& Y　　二、单链表的建立与遍历
2 t4 Q- P% _2 Q7 Y; n' V& p. N" M　　单链表中，每个结点只有一个指针，所有结点都是单线联系，除了末为结点指针为空外，每个结点的指针都指向下一个结点，一环一环形成一条线性链。
1 c) D2 F$ {- `　　链表的创建过程：
" E0 U( b& Q8 {$ R5 {1 {% n

　　

　　接下来在源码中建立并遍历输出一个单链表。
  N6 h/ P- `7 ]# ]- Q
; A( m2 T' I+ q, V; l/ y5 F
* E4 G. K. q" f/ d

1. 　　#include
   
2. 
   
3. 　　#include
   : \! s9 G* J! M4 S( e0 ?
4. 
   * Y* V7 `  [5 [" s0 ?
5. 　　#include
   
6. 
   + q8 q* I; m5 W* K
7. 　　/*单向链表*/
   , g8 ^, M) }1 w* s3 [
8. 
   
9. 　　struct Student/*建立学生信息结构体模型*/
   9 h# {  V, b7 T  F- W$ O6 q
10. 
    # }: c# @$ c1 \( y1 k4 t
11. 　　{
    & e0 T, b: z1 r9 e' R+ Q
12. 
    
13. 　　char cName[20];/*学生姓名*/
    
14. 
    ) A/ i( e& q6 M4 k
15. 　　int iNumber;/*学生学号*/
    
16. 
    5 p0 h0 V5 Y3 k* f; R/ p! d
17. 　　struct student *next;/*指向本结构体类型的指针类型*/
    
18. 
    4 n6 g1 l$ |' ?, X1 @$ r; |& F* B
19. 　　};
    5 A' w- k6 Q" g2 Q  o
20. 
    
21. 　　int iCount;/*全局变量表示链表长度*/
    4 s/ ^, U" c( H/ x: p
22. 
    
23. 　　struct Student *Create();/*创建链表函数声明*/
    
24. 
    + ~( j0 z; W7 O0 p5 S4 X3 h
25. 　　void print(struct Student *);/*遍历输出链表函数声明*/
    9 ?5 h* R" A8 v8 E7 Y+ h
26. 
    " F# f: f- p! d
27. 　　int main()
    
28. 
    8 |7 R3 ~6 l# b5 L" Q: j3 F, H: _" |
29. 　　{
    
30. 
    
31. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
    
32. 
    / q2 Y* J) n  D' h% r* v. y
33. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
    
34. 
    
35. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
    
36. 
    3 O& u5 H+ r' E( n
37. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    
38. 
    0 I, h1 j( W+ [  e) J& n
39. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
40. 
    
41. 　　return 0;
    
42. 
    
43. 　　}
    0 B& ]5 h9 K2 R" p
44. 
    
45. 　　struct Student *Create()
    
46. 
    0 z$ o. ]7 ]/ A' T8 U
47. 　　{
    7 @3 u1 H  C: g  [4 c
48. 
    ' R+ z& @" T5 i1 @* x6 U% v$ m
49. 　　struct Student *pHead=NULL;/*初始化链表，头指针为空*/
    
50. 
    % p- ]* j6 M/ o! N
51. 　　struct Student *pEnd,*pNew;
    
52. 
    
53. 　　iCount=0;/*初始化链表长度*/
    & D  M  `  t- l5 T
54. 
    
55. 　　pEnd=pNew=(struct Student *)malloc(sizeof(struct Student));/*动态开辟一个学生信息结构体类型大小的空间，使得pEnd和pNew同时指向该结构体空间*/
    
56. 
    
57. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    9 T- V0 U; K, A6 W
58. 
    
59. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    5 k( F2 c, |6 o2 {! }0 o! V
60. 
    
61. 　　while(pNew->iNumber!=0)/*设定循环结束条件——学号不为0时*/
    . Y0 S4 a) A( P/ t. ^, e
62. 
    
63. 　　{
    
64. 
    ) P- Q* s5 ?/ v* v) ]8 X/ ]! s% O
65. 　　iCount++;/*链表长度+1，即学生信息个数+1*/
    : a0 _- j% P3 M: P
66. 
    ! [" J/ k; _8 {- i. X
67. 　　if(iCount==1)/*如果链表长度刚刚加为1，执行*/
    5 T. r7 c! J6 ^3 Q
68. 
    
69. 　　{
    ! f7 {) M' U7 s$ O, \5 j: [
70. 
    . P" \- T% p* V9 {* K
71. 　　pNew->next=pHead;/*使指针指向为空*/
    ; z. X1 G1 T# t- \/ R
72. 
    
73. 　　pEnd=pNew;/*跟踪新加入的结点*/
    
74. 
      \; G0 \# I0 e, ?# f* I9 |
75. 　　pHead=pNew;/*头结点指向首结点*/
    ! _. A6 x+ P7 ]- X$ z$ K
76. 
    ; u8 `6 ~. m, H) H1 Q: [
77. 　　}
    
78. 
    
79. 　　else/*如果链表已经建立，长度大于等于2时，执行*/
    
80. 
    3 `5 M, M/ Q" k  v! g
81. 　　{
    
82. 
    8 W. J* K+ b" a' s
83. 　　pNew->next=NULL;/*新结点的指针为空*/
    
84. 
    4 K" F. ~  B6 i, ?8 S1 A
85. 　　pEnd->next=pNew;/*原来的结点指向新结点*/
    , P3 y% t! S; N6 V% x! |
86. 
    
87. 　　pEnd=pNew;/*pEnd指向新结点*/
    * r( O- J# \4 ^! _8 \3 I& L8 r( h/ H
88. 
    6 }; z) A0 T8 R
89. 　　}
    . J5 n6 t* z8 K9 p
90. 
    
91. 　　pNew=(struct Student *)malloc(sizeof(struct Student));/*再次分配结点的内存空间*/
    
92. 
    , E' f6 T6 z& R" S0 K7 V( K
93. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    * E! D6 a1 }' S, g# ~2 v
94. 
    
95. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    
96. 
      I% D/ V; g+ c8 ~! g
97. 　　}
    
98. 
    2 d0 y. M- w& g$ w5 p6 V/ @
99. 　　free(pNew);/*释放结点空间*/
    
100. 
     
101. 　　return pHead;/*返回创建出的头指针*/
     & ?5 i, i$ i) a) ]( J( b
102. 
     - {6 b  e4 a/ g/ F' I& i) m
103. 　　}
     # |1 ?+ d9 [& e2 s) E
104. 
     
105. 　　void print(struct Student *pHead)
     
106. 
     ; c; S; L/ Y1 _+ m/ b7 y
107. 　　{
     
108. 
     
109. 　　struct Student *pTemp;/*定义指向一个学生信息结构体类型的临时指针*/
     
110. 
     7 |1 [" X) |+ a" L
111. 　　int iIndex=1;/*定义并出事哈变量iIndex，用来标识第几个学生(信息)*/
     
112. 
     * v5 m7 ]9 p. c
113. 　　printf("总共%d个学生(信息)：\n",iCount);
     5 D0 \& ]/ J, |3 E# u2 o
114. 
     
115. 　　pTemp=pHead;/*指针得到首结点的地址*/
     / [* C3 |1 @5 W) v* T8 Z
116. 
     4 l% b& `6 g% R) q7 w
117. 　　while(pTemp!=NULL)/*当临时指针不指向NULL时*/
     
118. 
     
119. 　　{
     7 z5 S$ ~8 f9 K8 K& L
120. 
     1 _% P- Y' V7 q: p$ L5 `. t
121. 　　printf("第%d个学生信息：\n",iIndex);
     7 A  c1 I" b! z% }/ D5 F
122. 
     3 L3 X, _+ D& k6 [5 A
123. 　　printf("姓名：%s",pTemp->cName); /*输出姓名*/
     
124. 
     * P1 z$ N3 s! l! ^' r
125. 　　printf("学号：%d",pTemp->iNumber);/*输出学号*/
     + \" ?5 [8 w/ i, m2 |& l, E( s2 h- r% G
126. 
     4 T8 _% Z5 k! Q) y5 |7 e% D
127. 　　pTemp=pTemp->next;/*移动临时指针到下一个结点*/
     
128. 
     
129. 　　iIndex++;/*进行自加运算*/
     
130. 
     - P2 V2 s8 p; `- M# J& E" D# M
131. 　　}
     
132. 
     
133. 　　}

复制代码

　　三、单链表的插入与删除
　　在本实例中，插入时根据传递来的学号，插入到其后。
/ t( H& m) y; z" f/ |$ D　　删除时根据其所在链表的位置，删除并释放该空间。
9 }) I+ m1 z& n　　主函数增加如下：
0 O# Q3 L( T2 D3 u$ v# ~
- o( O5 [8 W$ L+ t

5 g$ Y% y5 w; s; O! C4 m/ W

1. 　　int main()
   
2. 
   - J$ y2 [- g8 v5 l
3. 　　{
   
4. 
   
5. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
   & `4 {$ y) z' m: |
6. 
   7 I# r/ L9 C( u- \. a/ y0 l
7. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
   
8. 
   1 j8 f; E! y% G7 ^1 t2 x9 i
9. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
   + [+ h2 N1 i- T. r, i
10. 
    
11. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    # p& h/ i( \+ y; {( {. M
12. 
    
13. 　　pHead=Insert(pHead,insert_n);/*将指针pHead和要插入的结点数传递给插入函数*/
    9 v$ ^2 k' {" Y$ |& J; B4 }( X# ^
14. 
    9 K4 d! r/ w* Y" X
15. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    / a" f! ?& l/ \2 E1 U& k1 I
16. 
    
17. 　　Delete(pHead,delete_n);/*将指针pHead和要删除的结点数传递给删除函数*/
    
18. 
    0 w8 O/ l* \; V
19. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    ' Y+ M, _0 ~$ r6 ~! V$ P! E
20. 
    6 d% |# a; _. t3 W8 C* F* H
21. 　　return 0;
    
22. 
    & n: J1 D! m3 T, f$ F4 n
23. 　　}

复制代码

' a& Q0 o) l' [% n9 {- J


, B; W3 M1 c. G/ D　　插入函数：
3 [* L0 V% o1 }/ ]

1. 　　struct Student *Insert(struct Student *pHead,int number)
   
2. 
   % J# d' D% u* r* H  i
3. 　　{
   
4. 
   
5. 　　struct Student *p=pHead,*pNew;/*定义pNew指向新分配的空间*/
   1 Y# B% _# R1 T
6. 
   " D: Y; t- y# [" \! @
7. 　　while(p&&p->iNumber!=number)
   
8. 
   
9. 　　p=p->next;/*使临时结点跟踪到要插入的位置(该实例必须存在学号为number的信息，插入其后，否则出错)*/
   ) F  _* f9 d. _1 s/ W1 Q7 z2 E! p- u
10. 
    4 }7 g( T5 H! N$ H
11. 　　printf("姓名和学号：\n");
    , b% {$ ?' L* S# m
12. 
    
13. 　　/*分配内存空间，返回该内存空间的地址*/
    
14. 
    
15. 　　pNew=(struct Student *)malloc(sizeof(struct Student));
    $ F1 b, J8 E2 _$ W3 S
16. 
    
17. 　　scanf("%s",pNew->cName);
    
18. 
    
19. 　　scanf("%d",&pNew->iNumber);
    - q+ t+ Q' \4 w7 M% n
20. 
    * W% `, T& k2 D8 o5 r+ O0 X5 Q
21. 　　pNew->next=p->next;/*新结点指针指向原来的结点*/
    
22. 
      T- I! F$ ]( Q1 A/ |4 n
23. 　　p->next=pNew;/*头指针指向新结点*/
    
24. 
    
25. 　　iCount++;/*增加链表结点数量*/
    
26. 
    5 c7 ?) |% {8 k0 M1 P- S' a& A2 K  @
27. 　　return pHead;/*返回头指针*/
    " G. L# ^1 O) f7 e9 W
28. 
    
29. 　　}

复制代码

, U! h* o! d% l/ I' F1 o


' X/ |) L1 u: k　　删除函数：

# C% o: k9 x( }

7 q$ }: q! u5 [9 T1 j

1. 　void Delete(struct Student *pHead,int number)
   3 A( I& T6 R5 t( S+ {4 {0 Q
2. 
   
3. 　　{
   
4. 
   . x/ S2 M8 Y. [
5. 　　int i;
   * H  [: O1 f1 ~
6. 
   9 n( g% ]$ P. I, p5 N+ p  @
7. 　　struct Student *pTemp;/*临时指针*/
   
8. 
   
9. 　　struct Student *pPre;/*表示要删除结点前的结点*/
   
10. 
    
11. 　　pTemp=pHead;/*得到链表的头结点*/
    
12. 
    / g5 [7 R. h# F0 o
13. 　　pPre=pTemp;
    ; `$ r+ {6 [9 Q. ~: K
14. 
    , v: ^8 |* `! d
15. 　　for(i=0;i
    
16. 
    ) C' q  {- c! u: I! j7 o2 S
17. 　　{/*通过for循环使得Temp指向要删除的结点*/
    / K" I6 N+ T: I; r9 ^9 L# J
18. 
    
19. 　　pPre=pTemp;
    
20. 
    % j0 p9 x2 Q8 n$ s$ ^, A4 f4 G
21. 　　pTemp=pTemp->next;
    & D1 T  ?4 g( F+ Q7 x; Z
22. 
    % M6 E5 \3 i$ B* E' M8 @
23. 　　}
    5 p7 s) r! z" D# a7 h  e
24. 
    * H( N1 |, `" G( ]+ I
25. 　　pPre->next=pTemp->next;/*连接删除结点两边的结点*/
    
26. 
    
27. 　　free(pTemp);/*释放要删除结点的内存空间*/
    
28. 
    % H) {: _( A$ A/ X" l+ A! l/ g
29. 　　iCount--;/*减少链表中的结点个数*/
    
30. 
    ' u5 h# x' Y# U$ D* O' ]
31. 　　}

复制代码

- X+ Z' p  q) y" d& |

　　四、双向链表的概念
　　双向链表基于单链表。单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。
　　在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点的地址，一般称为右链域;一个存储直接前驱结点地址，一般称之为左链域。
+ N: i1 K8 F1 q9 p　　双向链表结构示意图：

　　

7 R# b: N# d  J/ m- ?2 G/ z; s9 Q) M　　五、双向链表的建立与遍历
' a2 r# Y9 l& _+ l　　双向链表的源码实战和单链表类似，只是多了第二个指针域的控制，这里直接贴上没有注释的源代码。


0 x9 x+ t% y- \' {- e& M
0 E" e7 p3 B7 _" x! B1 c

1. 　　#include #include
   
2. 
   # G+ {/ W, x0 Z: Q9 }. w  c
3. 　　#include
   
4. 
   ) }* W; d6 K$ j5 C! [2 I# y% J
5. 　　#define N 10
   ) F6 L/ Q+ n5 k; v2 B+ a
6. 
   ( R) W8 w  F3 ?/ J, O
7. 　　typedef struct Node
   5 ]( [( [( e1 t
8. 
   - W! z, I: d7 z0 A" Z, h2 A
9. 　　{
   ) {/ L/ X  m7 w: i( o, F
10. 
    
11. 　　char name[20];
    
12. 
    " q8 }+ V" F. J. ?. N3 u. e
13. 　　struct Node *llink,*rlink;
    
14. 
    / e) S4 n2 \) O3 c! w/ H1 d3 z
15. 　　}STUD;
    
16. 
    3 [: U  A9 }9 T( c2 J& @; H
17. 　　STUD *creat(int);void print(STUD *);
    / d4 n6 b; I0 p2 W9 F6 |* p6 `* a4 B
18. 
    
19. 　　int main()
    
20. 
    % p2 A  E+ x6 j5 L
21. 　　{
    1 s. k( h2 C  r
22. 
    
23. 　　int number;
    
24. 
    
25. 　　char studname[20];
    
26. 
    - l' \+ ]  g5 k" I( [! [8 z
27. 　　STUD *head,*searchpoint;
    ; S- A5 Z- J* q7 e) O2 c
28. 
    , Q' @0 z# z" ~4 Q$ M- P
29. 　　number=N;
    
30. 
    0 |4 s; E: E/ n) t) U( }
31. 　　head=creat(number);
    - i0 \4 |* m  `4 S
32. 
    
33. 　　print(head);
    % y/ C9 H3 W# o  `# |
34. 
    % G% `. E7 S' F! @6 J+ k
35. 　　printf("请输入你要查找的人的姓名：");
    
36. 
    4 }) ]4 J, p% Z' S
37. 　　scanf("%s",studname);
    
38. 
    9 p7 W9 ?+ l( _% W3 f$ w  o! r
39. 　　searchpoint=search(head,studname);
    
40. 
    8 v5 K2 V. C+ G0 C9 u* P
41. 　　printf("你所要查找的人的姓名是：%s",*&searchpoint->name);
    - W" L0 E2 Z* C. d/ o4 l
42. 
    
43. 　　return 0;
    
44. 
    
45. 　　}
    
46. 
    0 [2 L( M9 `- E7 J# s, [6 F( s/ L
47. 　　STUD *creat(int n)
    : Q/ E% v6 j$ u# J
48. 
    0 V( l& I1 B1 ^7 N( L, O! B, r  c9 A
49. 　　{
    
50. 
    0 \3 H$ @2 T, H
51. 　　STUD *p,*h,*s;
    3 a2 y- X# r0 ~* Y
52. 
    " r* ?6 o3 S# W* I! y6 h( V7 ^
53. 　　int i;
    
54. 
    9 D+ Q0 O: d/ Y/ |
55. 　　if((h=(STUD *)malloc(sizeof(STUD)))==NULL)
    * d& `! ?( C/ S$ f
56. 
    : n. H) c5 x& A
57. 　　{
    
58. 
    4 G- }3 w% l" I, r- W- `+ [' W1 {
59. 　　printf("不能分配内存空间");
    3 h9 r- Z( Y4 h0 a# `" Y5 T' N% u
60. 
    
61. 　　exit(0);
    ; u1 z3 A" v' x
62. 
    
63. 　　}
    & H% I; f5 X4 W. U1 ?4 m
64. 
    
65. 　　h->name[0]='\0';
    2 u8 E9 X' b  B' h7 M
66. 
    
67. 　　h->llink=NULL;
    
68. 
    
69. 　　h->rlink=NULL;
    
70. 
    
71. 　　p=h;
    9 g: S: S. g' b
72. 
    ) E4 o9 @6 i% }; _7 j
73. 　　for(i=0;i
    
74. 
    7 T; V& a* B! O: z3 K  U
75. 　　{
    ; d' F8 R6 N) }/ z
76. 
    5 R7 _6 O7 Z0 p6 {0 I2 ?/ ]
77. 　　if((s=(STUD *)malloc(sizeof(STUD)))==NULL)
    
78. 
    
79. 　　{
    
80. 
    $ W/ Y6 ^& F3 c- R2 U
81. 　　printf("不能分配内存空间");
    
82. 
    6 R! ^% ]' |: g1 Z% e; |6 O
83. 　　exit(0);
    * k+ D+ ?! G! `# h6 x
84. 
    $ l9 t/ _% l! q9 ?3 t3 m
85. 　　}
    7 i8 `8 a. S7 ~* a5 W
86. 
      E, w8 `* @& |5 N
87. 　　p->rlink=s;
    . x3 Z& a; l% y" M
88. 
    
89. 　　printf("请输入第%d个人的姓名",i+1);
    ! d* U0 h% b8 D- H
90. 
    - B: i# \% A8 m6 @% Z
91. 　　scanf("%s",s->name);
    * u9 H- |( `" {  c; l
92. 
    
93. 　　s->llink=p;
    
94. 
    4 w. e" p* g" |& T- x& h
95. 　　s->rlink=NULL;
    
96. 
    
97. 　　p=s;
    
98. 
    
99. 　　}
    9 c+ ~+ ?( n2 E( f
100. 
     ) E2 C+ R' y! ]' l' ~/ `
101. 　　h->llink=s;
     % _% ?/ `0 g1 s- E3 n$ q
102. 
     
103. 　　p->rlink=h;
     
104. 
     $ s2 H+ k) W1 S/ F7 G
105. 　　return(h);
     / f( @) {; N$ y, F) P8 k5 W; o
106. 
     5 l, W3 O1 U+ x8 E1 m
107. 　　}void print(STUD *h)
       L" ]8 Q6 l. }+ f; Q
108. 
     
109. 　　{
     
110. 
     1 u$ L  W% g3 W& b' P
111. 　　int n;
     1 R  `* G- B0 C: `0 O# l: B: I
112. 
     
113. 　　STUD *p;
     8 \: t0 @3 s) j# E# l2 J, I+ y7 c% A
114. 
       b% X9 e  y% V; b: ~& y* E  F
115. 　　p=h->rlink;
     
116. 
     : D# I. O3 R7 x! R
117. 　　printf("数据信息为：\n");
     
118. 
     3 ?$ G) U0 H$ ]
119. 　　while(p!=h)
     
120. 
     
121. 　　{
     
122. 
     
123. 　　printf("%s ",&*(p->name));
     3 r! X3 ?" C2 _8 K3 a6 ~
124. 
     
125. 　　p=p->rlink;
     / a; H( X% A$ i
126. 
     $ u/ R. h* \# E
127. 　　}
     & C. O1 a) n: g% |; {
128. 
     : }" V! W2 J# @: a  v# }& I9 r
129. 　　printf("\n");
     
130. 
     $ f- l& o0 m& O5 f! }
131. 　　}

复制代码

6 G6 M* j: b  |5 I2 b8 j# y+ [& s+ [
0 _% O& |. {$ U* F
　　六、双向链表的元素查找
　　查找函数 STUD *search(STUD *,char *);


' f  l2 ?* k$ q
. B8 L7 g, P, {) b) ?2 w

1. 　　STUD *search(STUD *h,char *x)
   # x# D0 D. N# V% v* _
2. 
   6 n' h$ D5 H: d8 R1 n% c
3. 　　{
   
4. 
   
5. 　　STUD *p;
   
6. 
   ( `, l0 h  u- m* L' W1 [$ v" S
7. 　　char *y;
   
8. 
   
9. 　　p=h->rlink;
   # I& T( d3 L# j8 u7 N: D6 ^  q7 l; J, i
10. 
    
11. 　　while(p!=h)
    
12. 
    
13. 　　{
    
14. 
    ) A0 {5 y5 s8 j( B
15. 　　y=p->name;
    
16. 
    
17. 　　if(strcmp(y,x)==0)
    . ?. b7 _0 v' n& n- {" F- r9 I
18. 
    
19. 　　return(p);
    
20. 
    5 w4 s3 l3 `- b' l/ i' @0 q
21. 　　else
    8 J' Y3 ~4 r% `& S" V
22. 
    
23. 　　p=p->rlink;
    
24. 
    : v( m8 d. J5 P: A. T7 a6 ~& Q
25. 　　}
    
26. 
    . x- M/ U& |  y" D4 K. z
27. 　　printf("没有查到该数据!");
    ) X( B" G- A5 S+ m! v. a
28. 
    
29. 　　}

复制代码

& v: ~; `: F3 }) P' v/ ~


! n4 Y' K/ T4 X# l　　七、循环链表的概念
4 e$ v# X5 X5 _5 D' \　　类似于单链表，循环链表也是一种链式的存储结构，由单链表演化而来。
5 ~3 o2 x  B) O3 |+ L9 F　　单链表的最后一个结点的指针指向NULL，而循环链表的最后一个结点的指针指向链表头结点。
# e; K7 M& y, J1 `5 m/ p2 w" d　　这样头尾相连，形成了一个环形的数据链。
　　循环链表的建立不需要专门的头结点。
　　判断循环链表是否为尾结点时，只需判断该节点的指针域是否指向链表头节点。
% H/ J$ q8 ]% H0 @1 \　　八、合并两个链表的实例
　　建立两个带头节点的学生链表，每个节点包含学号、姓名和成绩，链表都按学号升序排列，将它们合并为一个链表仍按学号升序排列。
/ Y3 [5 K3 r& o+ g+ }+ `9 j　　算法分析：
( Z8 o# A* B6 v# b4 h* a　　合并链表用merge()函数实现。函数中定义3个工作指针a、b、c，其中a、b分别指向La链表、Lb链表的当前结点，C指向合并后的链表尾结点。合并后链表的头结点共用La链表的头结点。
　　①合并前，先让a和b分别指向两个链表的第一个结点，c指向La链表的头结点。
- \; a  Y( S' o: K　　②合并时应该分3种情况讨论，即La和Lb都没有处理完;La没处理完，但Lb处理完毕;Lb没处理完，但La处理完毕。
　　③合并过程中应始终将La和Lb链表中较小的一个链接在Lc中，方能保持有序。
3 x0 _5 D9 E  P

0 |- @8 ^  i  k9 R7 M" t( e; t
3 g5 P8 m5 C# Q( K

1. 　void merge(struct stud *La,struct stud *Lb)
   
2. 
   
3. 　　{
   
4. 
   0 n8 _0 p8 Z. n5 f) P( a7 ?
5. 　　struct stud *a,*b,*c;
   
6. 
   % `/ u2 _: g( t9 p
7. 　　c=La;
   1 y+ ^8 e% o  D9 p/ V) N
8. 
   : l# g/ o* G* t2 E; b9 \
9. 　　a=La->next;/* 合并前 */
   0 [0 H. k. I4 B. u- M+ C+ X( Z5 @
10. 
    ) ~, O4 H( E1 t' g& Z: g) r" ^
11. 　　b=Lb->next;
    7 e- ]3 J/ A6 M2 y$ }. a9 P8 M; D
12. 
    + K& `# h; {: R' n
13. 　　while(a!=NULL && b!=NULL)/* La和Lb都没处理完 */
    4 v6 D0 ]9 k& X/ h
14. 
    
15. 　　{
    
16. 
    
17. 　　if(a->num <= b->num)
    & Q+ I1 f, V! W1 p
18. 
    
19. 　　{
    " c6 `0 k4 C5 \6 H
20. 
    
21. 　　c->next=a;
    8 z1 u$ R3 z- }% a( b
22. 
    , x) }! x. w, m5 b9 D8 |
23. 　　c=a;
    0 k2 \* [; u' X3 h  x5 \  l/ e
24. 
    
25. 　　a=a->next;
    
26. 
    
27. 　　}
    
28. 
    
29. 　　else
    
30. 
    
31. 　　{
    
32. 
    
33. 　　c->next=b;
    - X! M5 Q3 [/ @# W
34. 
    / ^! b; t4 S8 C8 P. Y. x/ @" |: ~
35. 　　c=b;
      [2 Z  O6 v9 Z& G: e: J" e
36. 
    
37. 　　b=b->next;
    ) u0 @) W& l% ?3 A
38. 
    4 Y1 X2 ^5 {0 |
39. 　　}
    
40. 
    
41. 　　}
    * O! w5 i/ b& p& J5 i9 O
42. 
    
43. 　　if(a!=NULL)
    
44. 
    
45. 　　c->next=a;/* 若La没有处理完 */
    - U" d- L( q5 y  u
46. 
    0 V  }8 a" _* k5 T, m6 Z( }
47. 　　else
    7 E& ^. j3 ?: l7 x- Y
48. 
    . {# |+ L3 L  w+ t
49. 　　c->next=b;/* 若Lb没有处理完 */
    3 _) e3 h8 K; k( w" L
50. 
    
51. 　　free(Lb); /* 释放Lb的头结点 */
    
52. 
    9 _* z0 Q% J& b  F. C2 Y
53. 　　}

复制代码

4 o" i# j1 F+ L! `9 _; y* V