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

小样岁月

　　最近临近期末的C语言课程设计比平时练习作业一下难了不止一个档次，第一次接触到了C语言的框架开发，了解了View(界面层)、Service(业务逻辑层)、Persistence(持久化层)的分离和耦合，一种面向过程的MVC的感觉。
9 q2 I3 ~9 r$ ^) \　　而这一切的基础就在于对链表的创建、删除、输出、写入文件、从文件读出......
　　本篇文章在于巩固链表的基础知识(整理自《C语言程序设计教程--人民邮电出版社》第十章——指针与链表)，只对链表的概念及增删改查作出探讨，欢迎指教。
　　一、链表结构和静态/动态链表
　　二、单链表的建立与遍历
+ e- Z6 Q3 x! v9 h8 W8 W, M7 ^9 V　　三、单链表的插入与删除
, x+ G0 B  U& E9 m) U. Z　　四、双向链表的概念
　　五、双向链表的建立与遍历
: ]- ]- A  [6 f/ Q7 }　　六、双向链表的元素查找
% T$ {, @, ^6 ?7 X7 K% A　　七、循环链表的概念
　　八、合并两个链表的实例
, [( J" i% Q( m2 A8 l0 ^7 E. h9 r　　九、链表实战
　　拓展思维、拉到最后去看看 (•̀ᴗ•́)و ̑̑
　　一、链表结构和静态/动态链表
4 s& G" W0 ?: `" u2 U　　链表是一种常见的数据结构——与数组不同的是：
　　1.数组首先需要在定义时声明数组大小，如果像这个数组中加入的元素个数超过了数组的长度时，便不能正确保存所有内容;链表可以根据大小需要进行拓展。
  \4 [% u, L2 G+ w3 b. f　　2.其次数组是同一数据类型的元素集合，在内存中是按一定顺序连续排列存放的;链表常用malloc等函数动态随机分配空间，用指针相连。
　　链表结构示意图如下所示：

　　

　　在链表中，每一个元素包含两个部分;数据部分和指针部分。数据部分用来存放元素所包含的数据，指针部分用来指向下一个元素。最后一个元素的指针指向NULL，表示指向的地址为空。整体用结构体来定义，指针部分定义为指向本结构体类型的指针类型。
　　静态链表需要数组来实现，即把线性表的元素存放在数组中。数组单元存放链表结点，结点的链域指向下一个元素的位置，即下一个元素所在数组单元的下标。这些元素可能在物理上是连续存放的，也有可能是不连续的，它们之间通过逻辑关系来连接——这就要涉及到数组长度定义的问题，实现无法预知定义多大的数组，动态链表随即出现。
; d5 _7 h" ~# I　　动态链表指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点的数据，并建立起前后相连的关系。
1 \+ X+ t8 W# H( g* n7 }0 q8 @! T& H　　二、单链表的建立与遍历
; ~, [  `( q" w: Y9 M　　单链表中，每个结点只有一个指针，所有结点都是单线联系，除了末为结点指针为空外，每个结点的指针都指向下一个结点，一环一环形成一条线性链。
　　链表的创建过程：
$ e% o  i/ E$ c8 |* ~& |& G9 H+ Q

　　

　　接下来在源码中建立并遍历输出一个单链表。

3 l* M3 q; M" u1 |" E  k1 _8 v0 Q
6 P& I  W0 t- ~) H
/ g2 [* B% D1 E" r

1. 　　#include
   - b; Z% Q4 O% s
2. 
   ( d9 j( o" q% U9 x* C
3. 　　#include
   ! l4 h2 e- X# I
4. 
   0 R$ g: X' N& v5 A
5. 　　#include
   + C( x5 M: j, B+ R" {
6. 
   
7. 　　/*单向链表*/
   2 [+ j* h) t1 P' b
8. 
   
9. 　　struct Student/*建立学生信息结构体模型*/
   
10. 
    ( j- ]5 \+ e: Y3 I; k" M/ ~0 U6 g4 z
11. 　　{
    
12. 
    / V4 O9 r0 u  U3 ]$ W8 ?
13. 　　char cName[20];/*学生姓名*/
    
14. 
    
15. 　　int iNumber;/*学生学号*/
    
16. 
    
17. 　　struct student *next;/*指向本结构体类型的指针类型*/
    
18. 
    
19. 　　};
    
20. 
    % L- u. ~) _  {/ ?
21. 　　int iCount;/*全局变量表示链表长度*/
    $ E+ a% K+ ^$ j, F$ G4 d" u
22. 
    
23. 　　struct Student *Create();/*创建链表函数声明*/
    0 m  L* I) O. a
24. 
    " K4 M9 l$ v' r. ], T" O3 `& J
25. 　　void print(struct Student *);/*遍历输出链表函数声明*/
    
26. 
    . u; ?+ ]) n/ C/ y2 ?
27. 　　int main()
    + }/ ?# P, ?' z7 N
28. 
    
29. 　　{
    ! _; ^' {# K" r3 o6 t0 }( U
30. 
    / }# J8 ?, ]* X- {! i! l
31. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
    ! y$ ^; {1 p: x# A" `, i
32. 
    2 ?# `( h+ c( S
33. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
      q4 P7 O7 ?+ ~5 U2 f
34. 
    / }. k, J# |" n6 v( \
35. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
    
36. 
    
37. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    4 ~! f. G) C6 L+ f
38. 
    ' w- X1 N. Q& ~! e
39. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    - s3 s( L8 M" Z. A& z
40. 
    
41. 　　return 0;
    
42. 
    - R$ Q, s& S: y, C2 a
43. 　　}
    
44. 
    
45. 　　struct Student *Create()
    
46. 
    
47. 　　{
    4 U+ d! c; d& m! Q6 G  B) B* V$ l
48. 
    
49. 　　struct Student *pHead=NULL;/*初始化链表，头指针为空*/
    9 g# a/ l  f% A" k5 z9 g
50. 
    
51. 　　struct Student *pEnd,*pNew;
    
52. 
    8 j& N% I0 T9 x. a1 S) S# n3 ]+ v
53. 　　iCount=0;/*初始化链表长度*/
    
54. 
    
55. 　　pEnd=pNew=(struct Student *)malloc(sizeof(struct Student));/*动态开辟一个学生信息结构体类型大小的空间，使得pEnd和pNew同时指向该结构体空间*/
    
56. 
    % x) J6 M: [+ ~
57. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    ! J# ~5 e; j. i: X* M4 D/ g
58. 
    
59. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    2 X( h: e  y7 e1 U8 l& }  |
60. 
    & i: E6 O" N# \  Z- W4 v) L& R
61. 　　while(pNew->iNumber!=0)/*设定循环结束条件——学号不为0时*/
    
62. 
    
63. 　　{
    : W" T: `5 r2 c9 r) u
64. 
    0 r* g6 Q3 U8 G9 v+ K/ ^% z  w0 m
65. 　　iCount++;/*链表长度+1，即学生信息个数+1*/
    
66. 
    / |  I, k. Z2 O
67. 　　if(iCount==1)/*如果链表长度刚刚加为1，执行*/
    
68. 
    - u: o, r4 v% D& Z1 P1 [
69. 　　{
    
70. 
    4 W6 @- H4 x& E# g) A1 D* i
71. 　　pNew->next=pHead;/*使指针指向为空*/
    ) g% G' J. ~8 E* u
72. 
    
73. 　　pEnd=pNew;/*跟踪新加入的结点*/
    
74. 
    # x4 V/ U- v' ~* \
75. 　　pHead=pNew;/*头结点指向首结点*/
    ' X$ Y% p  D/ @1 s/ k5 ?
76. 
    % Q6 p" R0 a$ _3 }
77. 　　}
    : n+ n9 U; d( y- s* K# e' z, e8 V
78. 
    
79. 　　else/*如果链表已经建立，长度大于等于2时，执行*/
    - d, B, v+ |5 w3 ~) J
80. 
    5 P( [; ~3 j0 U- ~4 A! R" B! B, ?
81. 　　{
    : _. X2 r% o& @* \: Y' n4 d
82. 
    
83. 　　pNew->next=NULL;/*新结点的指针为空*/
    " K/ i% k( i; F2 z1 B9 M" W( M+ e
84. 
    
85. 　　pEnd->next=pNew;/*原来的结点指向新结点*/
    ( j& R' K' M* ~: L
86. 
    + |1 P  w9 I: n3 y$ u% M
87. 　　pEnd=pNew;/*pEnd指向新结点*/
    
88. 
    
89. 　　}
    8 [0 G3 s/ _. u) y5 ]+ B7 M* ?
90. 
    ; _* H7 j4 X: b" `
91. 　　pNew=(struct Student *)malloc(sizeof(struct Student));/*再次分配结点的内存空间*/
    
92. 
    1 t: ~/ X1 t& |( |# G/ Y# J4 Z
93. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    ' k* |8 X, k: \% m- J+ d
94. 
      k1 \. D+ O  S: x' y3 i
95. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    
96. 
    ) Z) I: ]# K. O! {! S; G
97. 　　}
    3 F/ F" z" y+ [0 M; V: g: Z
98. 
    
99. 　　free(pNew);/*释放结点空间*/
    8 i" X' z4 l$ n! [
100. 
     * A/ C- [8 P+ k( f) p, P9 g+ W
101. 　　return pHead;/*返回创建出的头指针*/
     
102. 
     
103. 　　}
     
104. 
     2 T. [$ M: ]# W
105. 　　void print(struct Student *pHead)
     
106. 
     
107. 　　{
     
108. 
     
109. 　　struct Student *pTemp;/*定义指向一个学生信息结构体类型的临时指针*/
       m/ q# w- L# e" H) y
110. 
     ( p% H3 C) `2 J; d3 A. T- Y  J
111. 　　int iIndex=1;/*定义并出事哈变量iIndex，用来标识第几个学生(信息)*/
     3 E1 ]9 b' q# M9 ~3 N3 V" l
112. 
     $ U0 ^* k: X9 {( d- r& n0 t& F
113. 　　printf("总共%d个学生(信息)：\n",iCount);
     
114. 
     
115. 　　pTemp=pHead;/*指针得到首结点的地址*/
     
116. 
     
117. 　　while(pTemp!=NULL)/*当临时指针不指向NULL时*/
     
118. 
     
119. 　　{
     
120. 
     
121. 　　printf("第%d个学生信息：\n",iIndex);
     
122. 
     
123. 　　printf("姓名：%s",pTemp->cName); /*输出姓名*/
     
124. 
     / h/ ?, a) _: Z0 {# J9 k: n9 s; y
125. 　　printf("学号：%d",pTemp->iNumber);/*输出学号*/
     ; D$ ~& w4 ?% }) k. j
126. 
     
127. 　　pTemp=pTemp->next;/*移动临时指针到下一个结点*/
       A& U# x5 B! Q
128. 
     " C5 C9 @9 B7 S( F
129. 　　iIndex++;/*进行自加运算*/
     ' S6 n2 u" i( c/ l2 u4 f7 ~# k7 i& _
130. 
     : _8 K2 h# [- Z7 U9 X
131. 　　}
     ! s, F( G+ _, G" T9 q. ?( A
132. 
     
133. 　　}

复制代码

* C" Y) x5 ^- T- V% |


　　三、单链表的插入与删除
　　在本实例中，插入时根据传递来的学号，插入到其后。
- x" U* k$ K+ I* i  b. d　　删除时根据其所在链表的位置，删除并释放该空间。
　　主函数增加如下：
5 C& \/ B! Q+ Y" i% s
! \4 T% m, J+ }3 C! F! w: K
) Q8 \8 u7 Y4 Y7 Q1 ^

1. 　　int main()
   # E6 q, G" Q( o0 M
2. 
   
3. 　　{
   * K* g6 d$ @& c/ R. c
4. 
   0 \- A8 p, v8 G; V* Y
5. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
   
6. 
   % r6 F: F4 i3 D+ J# q, x/ C
7. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
   7 N% U$ X- w; R% q
8. 
   
9. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
   
10. 
    
11. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    - I+ M. v' U# S  G- ]* w
12. 
    
13. 　　pHead=Insert(pHead,insert_n);/*将指针pHead和要插入的结点数传递给插入函数*/
    
14. 
    , p* \7 V- H% R; \  ~3 u# X
15. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
16. 
    9 a4 d9 L3 `0 {1 i
17. 　　Delete(pHead,delete_n);/*将指针pHead和要删除的结点数传递给删除函数*/
    1 C; Q: K: @6 U% `- L
18. 
    
19. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
20. 
    
21. 　　return 0;
    $ l6 E$ ?4 Z/ J* L0 J
22. 
    
23. 　　}

复制代码

. J+ J7 N- h! n2 c

/ h# }* F% W& G; x# W　　插入函数：



" M4 N$ S  X, ]; y; [1 M

1. 　　struct Student *Insert(struct Student *pHead,int number)
   3 T1 e0 {7 A5 r4 ?! ~' p
2. 
   $ O3 e, L2 ~# q0 L# D( W
3. 　　{
   $ S8 C9 h% Y/ U+ ~5 F+ ]9 ~
4. 
   0 J9 h5 }! c# i. t
5. 　　struct Student *p=pHead,*pNew;/*定义pNew指向新分配的空间*/
   " i& j& X) Q5 D+ M+ d
6. 
   
7. 　　while(p&&p->iNumber!=number)
   * s4 t7 Y! ~+ b# Z& x
8. 
   
9. 　　p=p->next;/*使临时结点跟踪到要插入的位置(该实例必须存在学号为number的信息，插入其后，否则出错)*/
   
10. 
    ! k% B% x( F- |8 V+ K0 z9 r/ T' t# I
11. 　　printf("姓名和学号：\n");
    ; \, l0 A3 H  l! @) D3 Q; L
12. 
    4 r3 n8 _1 M0 u. p
13. 　　/*分配内存空间，返回该内存空间的地址*/
    
14. 
    ) ?% D2 E( K' ?0 W( J1 [7 g
15. 　　pNew=(struct Student *)malloc(sizeof(struct Student));
    1 K7 Q2 \) f8 K. E
16. 
    
17. 　　scanf("%s",pNew->cName);
    9 Q4 A/ c# q3 C* I8 Z( C6 n
18. 
    
19. 　　scanf("%d",&pNew->iNumber);
    1 o, Z' z9 w/ o  p
20. 
    ( h  ^' q& X5 f7 X
21. 　　pNew->next=p->next;/*新结点指针指向原来的结点*/
    " y- Z4 b2 S8 a0 I
22. 
    1 T  \/ t* U. X2 [
23. 　　p->next=pNew;/*头指针指向新结点*/
    3 q) |  I& t- Q7 F- @5 J
24. 
    0 Y6 r% I0 H# U: E* J1 X
25. 　　iCount++;/*增加链表结点数量*/
    ! t5 O  W7 G, T
26. 
    
27. 　　return pHead;/*返回头指针*/
    
28. 
    
29. 　　}

复制代码

0 _* A, G3 l% I) V  J$ V' E8 l  ]　　删除函数：
/ l( d5 g( t% Y8 T1 ?5 e7 A
" ^, G7 x! L' Z  i
8 A3 c+ E0 y  C, y3 k

1. 　void Delete(struct Student *pHead,int number)
   % ?& j" Y7 n4 m# D# m. y2 e
2. 
   
3. 　　{
   
4. 
   ( k5 g* B; ]% a" C- ]8 {
5. 　　int i;
   
6. 
   * f6 y( T4 e# P& |9 C
7. 　　struct Student *pTemp;/*临时指针*/
   
8. 
   $ f( Y: @- u$ }' K& B
9. 　　struct Student *pPre;/*表示要删除结点前的结点*/
   
10. 
    # h; S* t4 i' t8 m3 d, x
11. 　　pTemp=pHead;/*得到链表的头结点*/
    
12. 
    
13. 　　pPre=pTemp;
    1 T# `/ ^6 D$ d% e- N- {+ S9 [
14. 
    ; V2 A  A) h% U
15. 　　for(i=0;i
    ) o7 [7 G% v& x4 x2 L7 `
16. 
    
17. 　　{/*通过for循环使得Temp指向要删除的结点*/
    0 [0 `$ W- W' g& D
18. 
    
19. 　　pPre=pTemp;
    : U0 N- T4 X5 I
20. 
    
21. 　　pTemp=pTemp->next;
    # ?' @$ ~0 c  m. T
22. 
    * `: T6 T) T& k0 }: d
23. 　　}
    
24. 
    0 S" z1 I7 d" W+ X7 t# w  {- ?
25. 　　pPre->next=pTemp->next;/*连接删除结点两边的结点*/
    : M$ N0 L' x1 Z+ q' l  X" b
26. 
    
27. 　　free(pTemp);/*释放要删除结点的内存空间*/
    # a. y6 _, x% H& k; D
28. 
    
29. 　　iCount--;/*减少链表中的结点个数*/
    . L' [, }; P" X5 K4 \, o/ G( h
30. 
    ( K! f0 d9 ~5 [% N- O3 ~/ h& {
31. 　　}

复制代码

$ B/ I# Y5 T! A+ B1 d
6 s4 W. i4 Z$ C5 N, @4 c
3 [9 D' S4 E0 i$ k  D5 @　　四、双向链表的概念
4 d0 k6 ~+ i- K. M　　双向链表基于单链表。单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。
9 d5 P3 ?7 Q2 f1 F　　在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点的地址，一般称为右链域;一个存储直接前驱结点地址，一般称之为左链域。
　　双向链表结构示意图：

# ^7 Q) B: n. C. |$ Z

　　

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



" K6 e1 e# `% s/ ^* X

1. 　　#include #include
   # N" [. ^; n. o
2. 
   / \5 j( m0 t" x3 d- K; w( E; l
3. 　　#include
   5 O, s( L3 t  E6 g8 V2 G
4. 
   
5. 　　#define N 10
   # Y$ Q3 B) O+ R% B
6. 
   3 c  z+ x3 e$ N& X
7. 　　typedef struct Node
   8 ~  ~; u/ C: Y7 i9 i$ W
8. 
   ' `9 q9 m! o4 s' G3 V0 E+ U, g
9. 　　{
   . s& H5 Y: ]' C! ]( Y! I
10. 
    
11. 　　char name[20];
    ) q5 {8 {! v$ k; y
12. 
    
13. 　　struct Node *llink,*rlink;
    : l$ _' g$ O: V9 _% q
14. 
    
15. 　　}STUD;
    7 H8 |2 c& H% h& p' F' \8 `1 W, g
16. 
    
17. 　　STUD *creat(int);void print(STUD *);
    ' L3 l& G, {. c) k1 N* |
18. 
      E# _3 ?; f, l. a+ B9 P. x
19. 　　int main()
    - t% B+ h" D8 H5 Y
20. 
    * y8 j) ^* J1 n* V5 [0 L/ ~" h
21. 　　{
    
22. 
    
23. 　　int number;
    
24. 
    0 J6 [* J0 e" d  h2 p/ Z
25. 　　char studname[20];
    % D# R4 W4 J8 V8 v. ~* Q! p
26. 
    
27. 　　STUD *head,*searchpoint;
    
28. 
    + {  u1 `9 |3 \% ~; j
29. 　　number=N;
    
30. 
    
31. 　　head=creat(number);
    ( R5 G2 k$ q0 X5 d8 I/ F  w/ U
32. 
    
33. 　　print(head);
    
34. 
    - T8 I4 H1 Z3 Z* u' K& W
35. 　　printf("请输入你要查找的人的姓名：");
    ( ?+ S$ ?5 A5 {) m* b& ~
36. 
    ( V* h# s' r% C: H
37. 　　scanf("%s",studname);
    * v1 C# V. ?3 O# _8 f5 `- u
38. 
    1 n6 k0 q% v, f
39. 　　searchpoint=search(head,studname);
    + m# z" N* v* P; X- |" Z$ d
40. 
    
41. 　　printf("你所要查找的人的姓名是：%s",*&searchpoint->name);
    % n9 S0 L. _3 l
42. 
    6 V: r: U1 `: E- d+ n# j7 J0 U9 K
43. 　　return 0;
    ; P* j/ q, g% c* t
44. 
    ! \$ E5 K' @) t9 t8 q6 Q8 r4 T
45. 　　}
    
46. 
    
47. 　　STUD *creat(int n)
    . l. j' N! ^3 |. G* h
48. 
    9 X, K# q4 ^" D) n8 i
49. 　　{
    . r( E2 r% c7 K' o* g
50. 
      X" E1 t4 ?. y) U3 r6 X% A
51. 　　STUD *p,*h,*s;
    
52. 
    % w" c! U/ ]  q; b& v9 @
53. 　　int i;
    
54. 
    
55. 　　if((h=(STUD *)malloc(sizeof(STUD)))==NULL)
    8 c5 _/ d; ]- Y7 M9 q, k6 ~- K/ g: W/ [
56. 
    
57. 　　{
    
58. 
    % U( t  L1 k6 w6 a
59. 　　printf("不能分配内存空间");
    : T" ?+ Z6 r1 i  W8 Q! r
60. 
    : q0 c0 @' S: l  C
61. 　　exit(0);
    & |! \* A9 _9 u0 V- ]
62. 
    
63. 　　}
    5 Z' t: l0 ^: C& ~
64. 
    2 x9 i1 c  m. A, L6 C+ t
65. 　　h->name[0]='\0';
    
66. 
    
67. 　　h->llink=NULL;
    : K& i( P- P' e! Z. d$ _" `/ r
68. 
    1 V: L: S1 S4 t- w: d/ u0 T1 o
69. 　　h->rlink=NULL;
    ( l8 \0 v! U8 G& L& w1 r5 d
70. 
    ' i( I: C3 O( u1 e  r4 x. {
71. 　　p=h;
    
72. 
    
73. 　　for(i=0;i
    7 J) g7 e2 D" G
74. 
    2 v( m3 p2 `+ n' S3 ^0 l4 d
75. 　　{
    
76. 
    + u5 h, K1 p$ t7 Y, [1 n" O" [# P, _
77. 　　if((s=(STUD *)malloc(sizeof(STUD)))==NULL)
    
78. 
    ; F% G4 @) v2 a
79. 　　{
    
80. 
    
81. 　　printf("不能分配内存空间");
    + L3 F" o* J, j, W
82. 
    % @6 n7 _! W4 l6 x: S! ?. [
83. 　　exit(0);
    7 y! s, B# h! X9 V
84. 
    
85. 　　}
    4 D3 j/ [6 y" z( f7 Y! A0 V0 D
86. 
    5 e" e# X) ?! }, ?5 x- u
87. 　　p->rlink=s;
    / k) X' L: K& c# T( y+ s
88. 
    7 W; p, L& Z) Q  m$ G' x
89. 　　printf("请输入第%d个人的姓名",i+1);
    + u3 p1 G: o0 t+ h9 T7 X9 x
90. 
    9 t# M2 k0 n2 _1 ~
91. 　　scanf("%s",s->name);
    
92. 
    3 p" U8 G! Y$ }8 I: x9 l5 a0 a
93. 　　s->llink=p;
    
94. 
    
95. 　　s->rlink=NULL;
    
96. 
    9 K" U+ x2 E8 h2 t' `" Q: `
97. 　　p=s;
    0 W' M' j; c0 ?/ J$ \
98. 
    
99. 　　}
    
100. 
     ! h& G. T& F9 Y# F% C( ]2 d$ V
101. 　　h->llink=s;
     
102. 
     ) Y$ `. U" \+ _. o: X1 S# q- ]2 Q3 t- n
103. 　　p->rlink=h;
     
104. 
     
105. 　　return(h);
     
106. 
     - @& \1 b( p* Z! o6 S
107. 　　}void print(STUD *h)
     + ~$ z5 W5 H, e- p7 m' h
108. 
     
109. 　　{
     
110. 
     ) w! e7 F3 A  ^- u1 F
111. 　　int n;
     
112. 
     ' L7 g5 ~6 F* R' A
113. 　　STUD *p;
     
114. 
     
115. 　　p=h->rlink;
     
116. 
     + b0 U5 H  K- J5 A: M
117. 　　printf("数据信息为：\n");
     % M' [% W9 z" K- M7 a: x: }+ w' d
118. 
     # T% S- t+ |$ T* e- V, H  w2 u% a
119. 　　while(p!=h)
     
120. 
     
121. 　　{
     
122. 
     
123. 　　printf("%s ",&*(p->name));
     
124. 
     ) U+ V! E& i& t6 K
125. 　　p=p->rlink;
     
126. 
     , g% s) z0 ~% u7 y
127. 　　}
     5 L8 M! d* l- G: Y9 ~  ?: v
128. 
     
129. 　　printf("\n");
     ' `  b* L4 h4 t+ T
130. 
     
131. 　　}

复制代码

　　六、双向链表的元素查找
　　查找函数 STUD *search(STUD *,char *);
1 D5 v. S7 O9 k0 z  c; |. T
& a/ ~4 j7 E8 f( P. t

2 g+ V/ O% U2 m( b0 g0 G! Z1 [6 m

1. 　　STUD *search(STUD *h,char *x)
   " G0 c5 j6 `3 k2 g" X8 ^
2. 
   0 B5 k) N/ \7 s% i# P5 I
3. 　　{
   
4. 
   " q  U- g( O) n- h3 w' z+ o) U
5. 　　STUD *p;
   
6. 
   
7. 　　char *y;
   
8. 
   
9. 　　p=h->rlink;
   8 m+ M% G! c. R% a1 F. H: t5 @
10. 
    ' S% X% ]9 Q3 h6 i6 ?
11. 　　while(p!=h)
    - s, c( y  v& A
12. 
    
13. 　　{
    
14. 
    
15. 　　y=p->name;
    % R. H; D' M& t
16. 
    8 W  u6 @9 b/ B" O3 x" ?9 ^0 Q
17. 　　if(strcmp(y,x)==0)
    & U6 D9 M: j1 u
18. 
    9 z. X0 r7 L" Z# T
19. 　　return(p);
    : x$ A0 n5 T: W! ?' Z( u% m
20. 
    " r* d0 {! F) ~: a$ I
21. 　　else
    
22. 
    
23. 　　p=p->rlink;
    
24. 
    , p$ i$ z* e* s3 a* q) l/ A
25. 　　}
    
26. 
    " d- k: i# S* n6 }
27. 　　printf("没有查到该数据!");
    9 a0 X' m1 d/ P8 S) \
28. 
    ( w7 \& l  s% e3 ?
29. 　　}

复制代码

% V, u3 K' K9 I/ u7 N  @
% z) p3 @! V9 k8 B　　七、循环链表的概念
　　类似于单链表，循环链表也是一种链式的存储结构，由单链表演化而来。
　　单链表的最后一个结点的指针指向NULL，而循环链表的最后一个结点的指针指向链表头结点。
　　这样头尾相连，形成了一个环形的数据链。
$ P( m6 o5 F4 E6 ~+ G+ |' a　　循环链表的建立不需要专门的头结点。
( [/ K: J8 w' r0 `9 i% {( l  i　　判断循环链表是否为尾结点时，只需判断该节点的指针域是否指向链表头节点。
　　八、合并两个链表的实例
4 P% M* c: n, \( {6 P# A4 C& Z　　建立两个带头节点的学生链表，每个节点包含学号、姓名和成绩，链表都按学号升序排列，将它们合并为一个链表仍按学号升序排列。
　　算法分析：
　　合并链表用merge()函数实现。函数中定义3个工作指针a、b、c，其中a、b分别指向La链表、Lb链表的当前结点，C指向合并后的链表尾结点。合并后链表的头结点共用La链表的头结点。
/ M5 z) c3 x# J  c6 u* j　　①合并前，先让a和b分别指向两个链表的第一个结点，c指向La链表的头结点。
0 q5 y7 F% Z- X: X: B/ S　　②合并时应该分3种情况讨论，即La和Lb都没有处理完;La没处理完，但Lb处理完毕;Lb没处理完，但La处理完毕。
4 ^) J; k4 R6 h　　③合并过程中应始终将La和Lb链表中较小的一个链接在Lc中，方能保持有序。
  H% n7 A8 |3 g5 O  b; h: y


  H; A: c" {1 M/ F7 d  r

1. 　void merge(struct stud *La,struct stud *Lb)
   
2. 
   ) {5 w3 }9 k" o
3. 　　{
   ( e3 t4 p5 A1 n9 k% y
4. 
   6 V( x+ [9 P( T1 n0 Q% L7 o. s4 U
5. 　　struct stud *a,*b,*c;
   # S5 j4 k' c$ t4 r7 J
6. 
   , \) C3 A6 W! f% D5 u
7. 　　c=La;
   2 a& M. T1 P: g9 x7 n* x0 ~: z6 s
8. 
   
9. 　　a=La->next;/* 合并前 */
   ( R# ?" _0 f0 M2 Q( [
10. 
    
11. 　　b=Lb->next;
    
12. 
    
13. 　　while(a!=NULL && b!=NULL)/* La和Lb都没处理完 */
    6 D% T7 f1 w3 L
14. 
    ) m7 b3 Z3 H" i5 M. }9 o5 K; l6 U
15. 　　{
    
16. 
    
17. 　　if(a->num <= b->num)
    
18. 
    
19. 　　{
    
20. 
    9 y! O% ^* F0 V; X) H0 e; e+ V
21. 　　c->next=a;
    
22. 
    
23. 　　c=a;
    
24. 
    
25. 　　a=a->next;
    
26. 
    ! u) [1 D5 i& O5 ?  y5 v
27. 　　}
    
28. 
    
29. 　　else
    
30. 
    
31. 　　{
    9 f4 }8 y1 z' }: _
32. 
      }0 n5 h8 u' d( e
33. 　　c->next=b;
    
34. 
      o! u6 O9 }  v" q" L; C( o6 p
35. 　　c=b;
    
36. 
    
37. 　　b=b->next;
    / ^7 k/ _2 O5 k
38. 
      S% a- R! g& L, F* \
39. 　　}
    ! q7 g& w, F5 ~+ y: r
40. 
    
41. 　　}
    " z6 D' ?% R% b$ M# Z
42. 
    4 m  ^+ ]' m0 d/ k2 x2 }1 S
43. 　　if(a!=NULL)
    
44. 
    
45. 　　c->next=a;/* 若La没有处理完 */
    
46. 
    0 P* {4 w9 r- J" W4 N& W
47. 　　else
    6 v9 g# j0 w0 j( S6 d
48. 
    2 T5 V2 q5 Z; U. q0 l7 M8 T; x+ z6 a
49. 　　c->next=b;/* 若Lb没有处理完 */
      p# K: Q- D" S+ C
50. 
    
51. 　　free(Lb); /* 释放Lb的头结点 */
    ( y* A6 b+ e+ M* A% e4 b
52. 
    ; c/ C2 [4 \( i% w2 G
53. 　　}

复制代码