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

小样岁月

　　最近临近期末的C语言课程设计比平时练习作业一下难了不止一个档次，第一次接触到了C语言的框架开发，了解了View(界面层)、Service(业务逻辑层)、Persistence(持久化层)的分离和耦合，一种面向过程的MVC的感觉。
　　而这一切的基础就在于对链表的创建、删除、输出、写入文件、从文件读出......
3 R5 d5 |. e2 O/ A　　本篇文章在于巩固链表的基础知识(整理自《C语言程序设计教程--人民邮电出版社》第十章——指针与链表)，只对链表的概念及增删改查作出探讨，欢迎指教。
4 C/ c* b6 ~5 l6 F; E9 {, ]　　一、链表结构和静态/动态链表
　　二、单链表的建立与遍历
　　三、单链表的插入与删除
6 @8 c/ m0 Y5 d+ k* D+ R　　四、双向链表的概念
　　五、双向链表的建立与遍历
2 b/ m6 S1 ]/ B　　六、双向链表的元素查找
　　七、循环链表的概念
, B# A, g. i) V0 @; j6 q8 ?　　八、合并两个链表的实例
: q% q) _6 p( k! C. F- e　　九、链表实战
/ y+ T( Y) s. z: h$ z" q　　拓展思维、拉到最后去看看 (•̀ᴗ•́)و ̑̑
　　一、链表结构和静态/动态链表
　　链表是一种常见的数据结构——与数组不同的是：
  T- E8 U" Y: a  w5 i4 E) G6 s. l　　1.数组首先需要在定义时声明数组大小，如果像这个数组中加入的元素个数超过了数组的长度时，便不能正确保存所有内容;链表可以根据大小需要进行拓展。
　　2.其次数组是同一数据类型的元素集合，在内存中是按一定顺序连续排列存放的;链表常用malloc等函数动态随机分配空间，用指针相连。
8 L4 l8 H1 j7 n　　链表结构示意图如下所示：

　　

　　在链表中，每一个元素包含两个部分;数据部分和指针部分。数据部分用来存放元素所包含的数据，指针部分用来指向下一个元素。最后一个元素的指针指向NULL，表示指向的地址为空。整体用结构体来定义，指针部分定义为指向本结构体类型的指针类型。
0 D6 l' I+ [% w2 G% d$ G1 K5 U, S1 e　　静态链表需要数组来实现，即把线性表的元素存放在数组中。数组单元存放链表结点，结点的链域指向下一个元素的位置，即下一个元素所在数组单元的下标。这些元素可能在物理上是连续存放的，也有可能是不连续的，它们之间通过逻辑关系来连接——这就要涉及到数组长度定义的问题，实现无法预知定义多大的数组，动态链表随即出现。
　　动态链表指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点的数据，并建立起前后相连的关系。
  ]" l* ], t1 z. G7 M) `　　二、单链表的建立与遍历
　　单链表中，每个结点只有一个指针，所有结点都是单线联系，除了末为结点指针为空外，每个结点的指针都指向下一个结点，一环一环形成一条线性链。
$ p7 e6 j% Q* S8 A' F+ O6 ~, V　　链表的创建过程：
" f( o' [  i- c- w! O0 v, C

　　

9 c/ A( v, d7 X. f& g　　接下来在源码中建立并遍历输出一个单链表。

  r( N- o: r" u; w6 p
. L+ s8 k' }* a+ [  I% K

1. 　　#include
   
2. 
   
3. 　　#include
   
4. 
   5 p- f" ?+ L7 a9 B, o, i
5. 　　#include
   , F* j5 x, H( C  X1 f' y+ d# s
6. 
   
7. 　　/*单向链表*/
     o$ x0 X+ q" Q% `4 ?9 d
8. 
   : |. a3 w6 d6 N3 A
9. 　　struct Student/*建立学生信息结构体模型*/
   
10. 
    4 m7 G, ~9 O. |" w; n
11. 　　{
    
12. 
    : d' L, T9 ^  m
13. 　　char cName[20];/*学生姓名*/
    , `  v2 W) I! L4 Y) d2 d* Q
14. 
    
15. 　　int iNumber;/*学生学号*/
    2 H% n9 j! x" h# u" `
16. 
    % E. S" l8 ^* f2 E- {! ~" a7 }( x. R
17. 　　struct student *next;/*指向本结构体类型的指针类型*/
    
18. 
    4 [8 Y1 D" Q7 M
19. 　　};
    ' ]% J9 S2 T' n" K  O" o/ T' ?5 N
20. 
    4 s7 l, B1 E- c& ?2 j' }
21. 　　int iCount;/*全局变量表示链表长度*/
    - O5 R& {3 F+ d, n
22. 
    
23. 　　struct Student *Create();/*创建链表函数声明*/
    ; \7 S$ |, Z* p6 u- j
24. 
    
25. 　　void print(struct Student *);/*遍历输出链表函数声明*/
    
26. 
    3 y( x% m3 g  Z' w4 t" e
27. 　　int main()
    7 Y$ X" h9 o' f4 S
28. 
    
29. 　　{
    
30. 
    + q# y/ h4 U7 e$ c) x+ B
31. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
    & i, M" H3 K/ Y9 m+ Y+ E6 s
32. 
    ! p5 N6 G! g+ V# A3 {
33. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
    
34. 
    : L( ]$ D2 U7 `, X
35. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
    - ?4 C, o0 ^" L/ \
36. 
    $ b6 m3 |, d" z
37. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    
38. 
    
39. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    . w8 S- `( O# Z" h" y! L! N
40. 
    
41. 　　return 0;
    # ?* w2 I9 r3 m  N
42. 
    
43. 　　}
    
44. 
    1 C8 w  }6 L9 r  P8 V
45. 　　struct Student *Create()
    & Q6 W0 H3 l' I. s4 [2 S* u9 R
46. 
    
47. 　　{
    
48. 
    
49. 　　struct Student *pHead=NULL;/*初始化链表，头指针为空*/
    
50. 
    
51. 　　struct Student *pEnd,*pNew;
    
52. 
    
53. 　　iCount=0;/*初始化链表长度*/
    & L+ ]: Q/ S# D7 w1 O% w
54. 
    # ]" b9 @: X* `2 l( l- f
55. 　　pEnd=pNew=(struct Student *)malloc(sizeof(struct Student));/*动态开辟一个学生信息结构体类型大小的空间，使得pEnd和pNew同时指向该结构体空间*/
      o! T7 ~. b& W
56. 
    
57. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    ! e( i! X% @7 ]+ {
58. 
    : w3 p' t# Y$ [3 ?: |
59. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    
60. 
    
61. 　　while(pNew->iNumber!=0)/*设定循环结束条件——学号不为0时*/
    
62. 
    
63. 　　{
    ) @) ]2 N* ?/ A" y! M* j4 S+ k
64. 
    2 a* c2 O# W  S) ?
65. 　　iCount++;/*链表长度+1，即学生信息个数+1*/
    
66. 
    
67. 　　if(iCount==1)/*如果链表长度刚刚加为1，执行*/
    
68. 
    - T- G$ A* S4 m( D; L) Z
69. 　　{
    ! w0 I1 a1 [- M$ R0 F6 e" r0 i9 z
70. 
    
71. 　　pNew->next=pHead;/*使指针指向为空*/
    / P  ^& }, m& |7 h' w+ N
72. 
    : h* o, f2 r3 U4 Z3 S
73. 　　pEnd=pNew;/*跟踪新加入的结点*/
    5 Q; d0 r# s2 F
74. 
      }3 j9 Z  b' N" r( G) [
75. 　　pHead=pNew;/*头结点指向首结点*/
    % @& m) E9 l- I& O6 @* N+ E
76. 
    - k5 i+ G/ n; D) y
77. 　　}
    / U' P! w: L! x& y
78. 
    1 p' v7 k) B) L1 C
79. 　　else/*如果链表已经建立，长度大于等于2时，执行*/
    - s- f+ q( v' K5 k. T, E
80. 
    
81. 　　{
    
82. 
    $ V7 u# c2 K9 i
83. 　　pNew->next=NULL;/*新结点的指针为空*/
    , w3 W" [& R5 i, s" Z3 Y, z5 n
84. 
    , @7 d( k5 |  |9 J# h0 C3 A
85. 　　pEnd->next=pNew;/*原来的结点指向新结点*/
    3 z- @& g, U) A1 H+ L2 N
86. 
    # I9 E6 ~+ U& I. L
87. 　　pEnd=pNew;/*pEnd指向新结点*/
    9 d; K2 e+ w& L
88. 
    
89. 　　}
    ; O2 g- ]5 r  f' W4 K
90. 
    
91. 　　pNew=(struct Student *)malloc(sizeof(struct Student));/*再次分配结点的内存空间*/
    % Q! ?2 X. K7 |8 b2 n
92. 
    : ~& t  {3 {3 W8 J
93. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    
94. 
    
95. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    ; A' |8 ?! z. [
96. 
    ) L3 J7 g" i: ^
97. 　　}
    0 D5 |+ y+ \6 L
98. 
    
99. 　　free(pNew);/*释放结点空间*/
    8 O- p9 ~+ e! e2 s
100. 
     
101. 　　return pHead;/*返回创建出的头指针*/
     
102. 
     
103. 　　}
     % `, @" w+ f  f1 X$ X( m$ `6 ^
104. 
     0 p; _6 g4 E5 P7 c: T2 z
105. 　　void print(struct Student *pHead)
       S# ]) e1 i2 a& {
106. 
     $ U) |6 r  `3 b/ ~: L7 a
107. 　　{
     
108. 
     
109. 　　struct Student *pTemp;/*定义指向一个学生信息结构体类型的临时指针*/
     
110. 
     3 g1 ^) L5 Z6 K& m$ {; \: _& q- e# l
111. 　　int iIndex=1;/*定义并出事哈变量iIndex，用来标识第几个学生(信息)*/
     # X3 O7 A! {" v, O& A7 j; ]
112. 
     
113. 　　printf("总共%d个学生(信息)：\n",iCount);
     % t) {% S5 z- @7 e
114. 
     
115. 　　pTemp=pHead;/*指针得到首结点的地址*/
     1 }8 X4 x8 q8 O! R8 _. O9 Z
116. 
     
117. 　　while(pTemp!=NULL)/*当临时指针不指向NULL时*/
     9 m( m" d* L" z2 C* k: d; r
118. 
     
119. 　　{
     
120. 
     & K; y" t' E5 K2 n5 b
121. 　　printf("第%d个学生信息：\n",iIndex);
     ; G" n9 u  O7 x$ U5 a( r3 E
122. 
     : p; O* k" w- n2 E! W/ _
123. 　　printf("姓名：%s",pTemp->cName); /*输出姓名*/
     4 P+ D9 K; U3 S8 v# E; U
124. 
     
125. 　　printf("学号：%d",pTemp->iNumber);/*输出学号*/
     
126. 
     8 O8 D. |+ E; W' A: Y
127. 　　pTemp=pTemp->next;/*移动临时指针到下一个结点*/
     
128. 
     
129. 　　iIndex++;/*进行自加运算*/
     
130. 
     $ |& O$ V) @" d# r
131. 　　}
     4 n3 L/ F# L4 [) F  q0 F& K6 G6 N
132. 
     1 }! w6 W- x! e' a2 O7 n# M) j
133. 　　}

复制代码

: u4 Q# a" s' F
* h/ I& {% B4 u4 H+ `6 _  S2 C
* Y: x1 E# i4 a$ f5 P/ ]8 O) y　　三、单链表的插入与删除
7 F* ?6 D5 f2 d# M　　在本实例中，插入时根据传递来的学号，插入到其后。
　　删除时根据其所在链表的位置，删除并释放该空间。
  `) E1 B/ D& Z3 Z2 m' r　　主函数增加如下：

+ g7 ]) t* x4 {" \% \
: f5 G( W+ l# X) B1 h
4 ~6 `* q: X6 `. m- q

1. 　　int main()
   
2. 
   
3. 　　{
   5 \* Q" F+ ~# N8 i/ _- ?
4. 
   . h# c: A. P0 T9 |/ h
5. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
   
6. 
   
7. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
   : y$ i2 K$ y/ M  M/ t$ y8 w' h
8. 
   $ t0 t0 a! G( K4 u; }
9. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
   & w  k; \; m3 }& f6 H
10. 
    ! m, {: i1 s$ Y* P' c
11. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    
12. 
    
13. 　　pHead=Insert(pHead,insert_n);/*将指针pHead和要插入的结点数传递给插入函数*/
    ! M4 t( r  ~4 A2 P  P: J
14. 
    0 G% b, P3 R2 R- p* W8 C
15. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
16. 
    
17. 　　Delete(pHead,delete_n);/*将指针pHead和要删除的结点数传递给删除函数*/
    $ g- H% o. n. g# q0 B7 |/ ?2 I) u* W8 s
18. 
    
19. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
20. 
    ; q" p! A! j- T4 G; {( @
21. 　　return 0;
    - E' v) S! s# W! }; t
22. 
    
23. 　　}

复制代码

( k. m: L/ J$ S3 O+ I: r# ~

! E3 f/ ^: `' n1 i8 |0 K　　插入函数：


; j5 e. w' E! g' D

1. 　　struct Student *Insert(struct Student *pHead,int number)
   
2. 
   9 s" O! H/ g% J% U! u
3. 　　{
   
4. 
   
5. 　　struct Student *p=pHead,*pNew;/*定义pNew指向新分配的空间*/
   . f4 ~7 ^, p2 B
6. 
   
7. 　　while(p&&p->iNumber!=number)
   ; j% n# G5 ?7 a, {6 W* B7 e
8. 
   
9. 　　p=p->next;/*使临时结点跟踪到要插入的位置(该实例必须存在学号为number的信息，插入其后，否则出错)*/
   
10. 
    0 |0 P0 I9 I/ `
11. 　　printf("姓名和学号：\n");
    
12. 
    
13. 　　/*分配内存空间，返回该内存空间的地址*/
    3 Q) n/ L8 u! U, q7 T2 l
14. 
    ) d* t- Q) v- O0 T
15. 　　pNew=(struct Student *)malloc(sizeof(struct Student));
    
16. 
    
17. 　　scanf("%s",pNew->cName);
    
18. 
    ) C  R4 Y' M7 S! l5 b
19. 　　scanf("%d",&pNew->iNumber);
    
20. 
    " ?0 n0 }2 Z8 H; h# J# M
21. 　　pNew->next=p->next;/*新结点指针指向原来的结点*/
    
22. 
    / P4 n/ ?8 k: Y! M
23. 　　p->next=pNew;/*头指针指向新结点*/
    
24. 
    
25. 　　iCount++;/*增加链表结点数量*/
    . ~+ a7 o1 M% ]' j1 {
26. 
    
27. 　　return pHead;/*返回头指针*/
      ?& N& m* J. ?# z+ m
28. 
    ' E* A; p( a/ H9 B
29. 　　}

复制代码

" T: M4 J  q' I4 E

: `/ o4 c  R8 {. ]7 Z2 B! y
$ U: \2 w! m" R6 ?- H　　删除函数：



8 ?3 r. u0 \4 J3 R. ~4 E
- ^1 H; ~6 `. I$ N$ B' m

1. 　void Delete(struct Student *pHead,int number)
   
2. 
   
3. 　　{
   3 g* X+ Q2 {9 }
4. 
   
5. 　　int i;
   
6. 
   
7. 　　struct Student *pTemp;/*临时指针*/
   # j! X( C1 c$ I% d/ D# p/ k% z( L
8. 
   
9. 　　struct Student *pPre;/*表示要删除结点前的结点*/
   ; J9 ^8 C! p& F+ r5 D
10. 
    & i; D+ E3 \0 A- j# [0 R
11. 　　pTemp=pHead;/*得到链表的头结点*/
    # i' g" v0 ]- d' c
12. 
    
13. 　　pPre=pTemp;
    " W8 ~( X8 j1 y. E8 w" ^
14. 
    
15. 　　for(i=0;i
    # C; x5 _1 L& @2 @3 `- B( N" J
16. 
    
17. 　　{/*通过for循环使得Temp指向要删除的结点*/
    : ]' K, A- v  p
18. 
    : p3 N9 B4 z' u  i" d$ R4 D7 s+ }
19. 　　pPre=pTemp;
    0 L/ }9 O9 X* ^% X6 i4 G. F
20. 
    % y  f1 O. E: ~3 L# _8 w
21. 　　pTemp=pTemp->next;
    
22. 
    
23. 　　}
    " c6 H( ^1 b" I6 L9 o
24. 
    5 o3 P# n/ t5 D
25. 　　pPre->next=pTemp->next;/*连接删除结点两边的结点*/
    9 b* S: O; \) N3 F* A  P, K, ?
26. 
    
27. 　　free(pTemp);/*释放要删除结点的内存空间*/
    
28. 
    
29. 　　iCount--;/*减少链表中的结点个数*/
    ; y: v0 X! t: |. B9 n
30. 
    8 H: y) E; ~+ p) I
31. 　　}

复制代码

8 y# Y8 M4 Y: i: s

　　四、双向链表的概念
' A; O* ^9 a- i! e% b0 O　　双向链表基于单链表。单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。
4 `! i# w: Q+ ?; z) _　　在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点的地址，一般称为右链域;一个存储直接前驱结点地址，一般称之为左链域。
  ?  q6 v0 r+ s9 o, U* E, E　　双向链表结构示意图：

　　

2 o( ~! O/ |( h  f$ L3 z　　五、双向链表的建立与遍历
2 e( N/ _+ G9 I0 s) v　　双向链表的源码实战和单链表类似，只是多了第二个指针域的控制，这里直接贴上没有注释的源代码。
: k9 ?2 r" a( f3 Q0 ?5 M
6 E* m* N( K1 Y5 [5 v$ a" W
) ]8 O  _$ B4 f& M1 d

1. 　　#include #include
   
2. 
   " J5 @% }' s( V+ }7 Q' O( d
3. 　　#include
   : k' n% W* t/ q! \
4. 
   7 c# t5 w: T6 |1 z: h4 G7 K
5. 　　#define N 10
   
6. 
   8 y+ k* ]) z$ Y, S: e5 ?
7. 　　typedef struct Node
   
8. 
   
9. 　　{
   3 S; ?5 }8 o$ Y) `- o( t' W
10. 
    
11. 　　char name[20];
    , Z5 \; m+ T$ |" X
12. 
    - r% a$ c/ c6 T' l, H/ Y2 {
13. 　　struct Node *llink,*rlink;
    0 f$ H3 ?. b4 e! h2 S
14. 
    ! i1 h. `" C, o, t! a# s& }- z' Y# l
15. 　　}STUD;
    : W6 _. P, ?4 o
16. 
      W, y' @  |6 d- @4 s
17. 　　STUD *creat(int);void print(STUD *);
    
18. 
    
19. 　　int main()
    
20. 
    7 A6 ~7 {0 R# r% q
21. 　　{
    ( `" P. S6 N; a. K1 y3 i; d
22. 
    
23. 　　int number;
    ! O8 l. N8 c) s
24. 
      \- p( |) P; w" [3 o
25. 　　char studname[20];
    9 w2 I7 n8 O8 O
26. 
    
27. 　　STUD *head,*searchpoint;
    
28. 
    
29. 　　number=N;
    7 O3 a9 c3 T4 B6 T$ d
30. 
    
31. 　　head=creat(number);
    
32. 
    - j3 y! T) T" z5 g. u7 E8 t1 t
33. 　　print(head);
    7 ~, x- u6 j$ M; A# d
34. 
    . X& x* w' W$ V! Y6 L5 g$ W
35. 　　printf("请输入你要查找的人的姓名：");
      I5 F: F/ x, _$ S( Z( Z
36. 
    
37. 　　scanf("%s",studname);
    3 f$ e' o3 C1 D5 o' D3 O4 p4 S
38. 
    
39. 　　searchpoint=search(head,studname);
    % v1 b9 r% e0 B+ J3 i8 ~6 Q
40. 
    
41. 　　printf("你所要查找的人的姓名是：%s",*&searchpoint->name);
    7 Z+ _, X% V* ^  v; F/ v# T6 A9 R3 V
42. 
    " X/ q5 G& X6 }" P; k
43. 　　return 0;
    . f7 N9 x' t$ ]" y" J" p) Q
44. 
    * `3 W- g6 [* o6 O; F
45. 　　}
    
46. 
    
47. 　　STUD *creat(int n)
    0 `8 t6 e, B, H, ~; y+ E
48. 
    " E# ~1 K8 c, M3 x  q& q
49. 　　{
    , W9 l2 {) u* r: \$ w+ }
50. 
    # l) y. x$ f( ?) R# O
51. 　　STUD *p,*h,*s;
    
52. 
    ) O2 @8 k& A( |+ Q( T$ z9 C3 {3 P
53. 　　int i;
    ; `& |" s; M# ?% C7 f+ ]" w
54. 
    
55. 　　if((h=(STUD *)malloc(sizeof(STUD)))==NULL)
    2 w/ R6 G& ^) h6 |# ~0 u5 [
56. 
    
57. 　　{
    & \! q/ Q+ Q7 X' B6 m  P) Y
58. 
    , U) ]7 H: O0 v9 T
59. 　　printf("不能分配内存空间");
    ( x' l$ C! l; H1 [- o! x. n
60. 
    5 ^, `& ~! M6 E: B  [8 d) S
61. 　　exit(0);
    
62. 
    
63. 　　}
    
64. 
    ! r) V, q5 f0 H
65. 　　h->name[0]='\0';
    
66. 
    
67. 　　h->llink=NULL;
    
68. 
    " c( X) Y# Z  p. q& Q1 `1 U
69. 　　h->rlink=NULL;
    * D+ G1 K9 e) G% I9 ]
70. 
    + N9 f  @$ C- d- G3 z% a8 K  a2 c1 W. J
71. 　　p=h;
    ! o) N1 S! }* I- I, u
72. 
    
73. 　　for(i=0;i
    
74. 
    
75. 　　{
    / `" V& D! _7 j4 Q" Z+ [
76. 
    3 c; Z  n0 x6 r+ Y
77. 　　if((s=(STUD *)malloc(sizeof(STUD)))==NULL)
    
78. 
    " x+ r* [7 n' x# J) l7 c
79. 　　{
    8 Y; I6 z0 M% }# Q
80. 
    1 A7 c9 _4 \4 [5 U2 C" o
81. 　　printf("不能分配内存空间");
    
82. 
    
83. 　　exit(0);
    1 G" G( Y/ l1 q7 J
84. 
    . c0 U' d% t' {4 v
85. 　　}
    4 @0 S7 D8 j  `+ b
86. 
    7 X- s+ y# ]" p( F; ]- M
87. 　　p->rlink=s;
    
88. 
    5 T* F( B, @/ T7 n+ ?$ a$ _
89. 　　printf("请输入第%d个人的姓名",i+1);
    6 }: }& t, ]& e7 A3 {1 ^
90. 
    9 P$ t2 n6 ~2 K* A3 V
91. 　　scanf("%s",s->name);
    9 h8 M) X- X- M2 A4 |) W6 r
92. 
    
93. 　　s->llink=p;
    
94. 
    " T) A2 C  ^& |; u& k9 A3 p
95. 　　s->rlink=NULL;
    
96. 
    5 J/ ^$ h$ A4 F; B
97. 　　p=s;
    0 }% P+ t4 ^, q; w/ B3 l0 k% ?. u/ e8 A
98. 
    * ?9 w+ w. L7 G5 W. Q+ R6 I) i
99. 　　}
    
100. 
     4 K( B# ^, F( [5 ^* G( c
101. 　　h->llink=s;
     . j& X1 x$ B8 W5 o5 W+ f; r
102. 
     9 s9 H, K+ v0 Z
103. 　　p->rlink=h;
     
104. 
     
105. 　　return(h);
     1 @: K% ^0 \: k, J
106. 
     
107. 　　}void print(STUD *h)
     
108. 
     
109. 　　{
     
110. 
     
111. 　　int n;
     
112. 
     
113. 　　STUD *p;
     * ~! s$ S1 \3 O
114. 
     # j  F! I7 Z9 Q0 E" T/ i! z
115. 　　p=h->rlink;
     ' z4 M9 e* k. T8 f, S9 h: ?. w: P
116. 
     1 T; B8 @8 m( T: J# b3 e( f
117. 　　printf("数据信息为：\n");
     
118. 
     4 F* Z/ U0 j" c/ m) r! p1 @, i
119. 　　while(p!=h)
     ) x- T! T8 _# N' Z3 J# m
120. 
     7 v5 h" h% @7 b
121. 　　{
     
122. 
     + d; k) I8 I! Q- }, g
123. 　　printf("%s ",&*(p->name));
     ( b% n: u6 {2 j, ~
124. 
     
125. 　　p=p->rlink;
     
126. 
     
127. 　　}
     - ?* g  X0 i: b' K9 ^5 [
128. 
     
129. 　　printf("\n");
     
130. 
     
131. 　　}

复制代码

& `. P+ l; ^) m- q8 Q( i
6 G% e$ w3 T7 {! u6 K4 t4 q
　　六、双向链表的元素查找
　　查找函数 STUD *search(STUD *,char *);
6 F! L9 Q$ u9 [6 M# r# Z, t


  [7 O! G& f* B6 \4 Q! F' b' D

1. 　　STUD *search(STUD *h,char *x)
   : z  g8 a' \: X1 u2 d/ A/ M
2. 
   
3. 　　{
   . g  d% w- l) @& u
4. 
   & ^2 V: Y/ N$ [1 x; T/ y
5. 　　STUD *p;
   
6. 
   
7. 　　char *y;
   ! y& h: p4 p" V6 L
8. 
   
9. 　　p=h->rlink;
   6 o/ R6 Q6 g+ }; {  l0 j# }
10. 
    
11. 　　while(p!=h)
    , _0 a+ G4 O0 a! e+ |/ K
12. 
    6 ?# C& {& G  z" X( W- t: X2 N
13. 　　{
    3 \/ {2 A7 ]3 x4 \$ }
14. 
    
15. 　　y=p->name;
    , F& e# `  ?' G: P' G" S
16. 
    / S9 s+ S/ Q( |5 S
17. 　　if(strcmp(y,x)==0)
    : a8 c! i+ E4 ^1 _6 R# T
18. 
    6 k+ J' V; _" C$ ~
19. 　　return(p);
    
20. 
    
21. 　　else
    
22. 
    
23. 　　p=p->rlink;
    5 o( b8 K0 t# \% D1 O
24. 
    1 |* @! @- m, ]) a" w
25. 　　}
    
26. 
    
27. 　　printf("没有查到该数据!");
    - m( x" p" n$ U4 G: g
28. 
    2 m+ D  s" `$ t4 S
29. 　　}

复制代码

　　七、循环链表的概念
% g" z' c# T$ w( h0 |' z( n　　类似于单链表，循环链表也是一种链式的存储结构，由单链表演化而来。
　　单链表的最后一个结点的指针指向NULL，而循环链表的最后一个结点的指针指向链表头结点。
　　这样头尾相连，形成了一个环形的数据链。
　　循环链表的建立不需要专门的头结点。
　　判断循环链表是否为尾结点时，只需判断该节点的指针域是否指向链表头节点。
　　八、合并两个链表的实例
　　建立两个带头节点的学生链表，每个节点包含学号、姓名和成绩，链表都按学号升序排列，将它们合并为一个链表仍按学号升序排列。
　　算法分析：
　　合并链表用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中，方能保持有序。
, D& {# ?. L8 q: `- d
- K4 g3 i1 L9 O, p" C, a


# I; y. M1 k9 U8 Z4 y

1. 　void merge(struct stud *La,struct stud *Lb)
   
2. 
   4 X( o: l; s# I4 e% v; i# ^
3. 　　{
   ( k) z% O3 F4 |/ U% p
4. 
   
5. 　　struct stud *a,*b,*c;
   6 A+ b) c. D/ [6 d2 F( G* z
6. 
   ( p" C$ V. J. t0 Z8 m$ g( F
7. 　　c=La;
   8 R2 g: R8 G/ G# `
8. 
   : W* {+ q- P+ f0 Y/ p
9. 　　a=La->next;/* 合并前 */
   
10. 
    0 J+ D* ?& j7 I- m
11. 　　b=Lb->next;
    0 ?, k# l2 p# @# g; S1 T
12. 
    
13. 　　while(a!=NULL && b!=NULL)/* La和Lb都没处理完 */
    
14. 
    & T5 @: U8 L! I+ ]% k
15. 　　{
    4 }3 P7 I7 ?. ]1 ]" z8 O
16. 
    
17. 　　if(a->num <= b->num)
    3 \6 Z7 F7 A- q/ [5 y% J" d
18. 
    
19. 　　{
    
20. 
    
21. 　　c->next=a;
    : d! W8 V& r4 ]& ~+ e8 \
22. 
    , s9 }! q( S" J& P; R4 J$ c! A. |
23. 　　c=a;
    
24. 
    
25. 　　a=a->next;
    
26. 
    
27. 　　}
    
28. 
    
29. 　　else
    
30. 
    
31. 　　{
    6 f- k0 v8 b# c2 r* V4 @8 f
32. 
    
33. 　　c->next=b;
    2 d9 d9 w& s: _. M
34. 
    5 p5 o6 l# _6 I8 v2 M4 E
35. 　　c=b;
    3 N5 }0 |$ B- |
36. 
    
37. 　　b=b->next;
    3 W8 t" [9 b$ K9 I" v% f$ J
38. 
    / b( h+ v. i( N1 O; m% q5 l
39. 　　}
    
40. 
    
41. 　　}
    
42. 
    * {/ E# u3 s  k- X8 z, {
43. 　　if(a!=NULL)
    
44. 
    ( k9 U. _* c7 X% I9 G
45. 　　c->next=a;/* 若La没有处理完 */
    ( W2 L0 i2 y3 `! {0 z& X3 Z
46. 
    
47. 　　else
    & f9 G5 d" O  x: ]: \1 R/ w
48. 
    . V( Z3 ]3 i( s( R
49. 　　c->next=b;/* 若Lb没有处理完 */
    7 K6 X/ G# p8 R7 q- Q5 f# a
50. 
    ) P) C6 G3 n* }# W' Y5 q4 p" U' W6 w
51. 　　free(Lb); /* 释放Lb的头结点 */
    + f4 G1 z! k/ {8 c2 T. Z% C
52. 
    
53. 　　}

复制代码

* l3 T: ~$ z, ?+ [# f$ p) o