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

小样岁月

　　最近临近期末的C语言课程设计比平时练习作业一下难了不止一个档次，第一次接触到了C语言的框架开发，了解了View(界面层)、Service(业务逻辑层)、Persistence(持久化层)的分离和耦合，一种面向过程的MVC的感觉。
4 o! E& Y  ^1 Z/ z/ H/ X8 L+ ^　　而这一切的基础就在于对链表的创建、删除、输出、写入文件、从文件读出......
" F; \4 ^9 ]  p4 C& q1 ]　　本篇文章在于巩固链表的基础知识(整理自《C语言程序设计教程--人民邮电出版社》第十章——指针与链表)，只对链表的概念及增删改查作出探讨，欢迎指教。
; t) f: x" b; K, W$ l& T# y9 d+ v7 X　　一、链表结构和静态/动态链表
3 m" w7 u+ q# I　　二、单链表的建立与遍历
　　三、单链表的插入与删除
+ k/ p; R' c7 s6 J7 K+ h　　四、双向链表的概念
) D+ P' J4 s! u6 j+ u　　五、双向链表的建立与遍历
　　六、双向链表的元素查找
; g' E2 q/ w8 Q: y　　七、循环链表的概念
　　八、合并两个链表的实例
2 A7 l8 `0 Z! K$ y　　九、链表实战
- n2 f2 ^) _1 P( x- A5 u! Z# E6 Q　　拓展思维、拉到最后去看看 (•̀ᴗ•́)و ̑̑
: }7 m# w; I/ [  [9 s9 J　　一、链表结构和静态/动态链表
0 d' q9 X( n+ U! S　　链表是一种常见的数据结构——与数组不同的是：
: v# ]& a( q+ x, {3 G6 Q6 b　　1.数组首先需要在定义时声明数组大小，如果像这个数组中加入的元素个数超过了数组的长度时，便不能正确保存所有内容;链表可以根据大小需要进行拓展。
9 I( J  f) n0 [9 x" }　　2.其次数组是同一数据类型的元素集合，在内存中是按一定顺序连续排列存放的;链表常用malloc等函数动态随机分配空间，用指针相连。
　　链表结构示意图如下所示：

　　

　　在链表中，每一个元素包含两个部分;数据部分和指针部分。数据部分用来存放元素所包含的数据，指针部分用来指向下一个元素。最后一个元素的指针指向NULL，表示指向的地址为空。整体用结构体来定义，指针部分定义为指向本结构体类型的指针类型。
# _7 `; e( W- |. {, G　　静态链表需要数组来实现，即把线性表的元素存放在数组中。数组单元存放链表结点，结点的链域指向下一个元素的位置，即下一个元素所在数组单元的下标。这些元素可能在物理上是连续存放的，也有可能是不连续的，它们之间通过逻辑关系来连接——这就要涉及到数组长度定义的问题，实现无法预知定义多大的数组，动态链表随即出现。
, k" @6 G; g( m1 Y( t/ O　　动态链表指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点的数据，并建立起前后相连的关系。
5 D6 u6 \; ~6 O( \, P& x) B  X　　二、单链表的建立与遍历
　　单链表中，每个结点只有一个指针，所有结点都是单线联系，除了末为结点指针为空外，每个结点的指针都指向下一个结点，一环一环形成一条线性链。
　　链表的创建过程：
' D& T- c9 E9 C9 o

　　

　　接下来在源码中建立并遍历输出一个单链表。
, E( y5 _, W, p7 W$ F8 n$ o* D

1. 　　#include
   & [: Y8 p( n- B, {! v: ]
2. 
   7 C* O1 m4 T4 a# [  b' Z
3. 　　#include
   
4. 
   
5. 　　#include
   
6. 
   
7. 　　/*单向链表*/
   # T( ?' h" R8 U3 E3 ]
8. 
   
9. 　　struct Student/*建立学生信息结构体模型*/
   8 @+ |4 e* h0 H4 y: I
10. 
    $ p, p; l- v0 K& z
11. 　　{
    & w+ q/ \# }8 A2 Y* }( |
12. 
    
13. 　　char cName[20];/*学生姓名*/
    4 j8 ~- G  c- Y% O& M
14. 
    
15. 　　int iNumber;/*学生学号*/
    : R4 i0 I+ |8 b+ H: B: ?3 S
16. 
    
17. 　　struct student *next;/*指向本结构体类型的指针类型*/
    
18. 
    
19. 　　};
    
20. 
    # y: v0 a& X: h8 Q( i% Z' |: H- E
21. 　　int iCount;/*全局变量表示链表长度*/
    ' H+ i" n6 Z' E2 p
22. 
    $ Z9 N! |! Y; Q& K* P3 i" v
23. 　　struct Student *Create();/*创建链表函数声明*/
    
24. 
    9 E! O3 H# ^9 _9 H  y  x2 a
25. 　　void print(struct Student *);/*遍历输出链表函数声明*/
    " G: R* S+ S: h1 N$ t. t% \# Y
26. 
    
27. 　　int main()
    
28. 
    0 k. y% d5 u) K0 H# w/ w# F; N
29. 　　{
    
30. 
    
31. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
    8 w( H. J; O; b  h7 Z4 g+ r
32. 
    3 \9 R) _8 b; {3 T
33. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
    
34. 
    
35. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
    
36. 
      J2 g# {  I3 R( }* z9 x" C2 b
37. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    
38. 
    3 ]0 u- l& M+ M& q/ j( t$ ]% {
39. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    3 n& @1 T) y5 v4 m! \
40. 
    9 g! ?( Z& P) P: n+ h/ E
41. 　　return 0;
    
42. 
    & Y, a1 n; W" P+ G0 v9 X+ R
43. 　　}
    * s4 _) f  T& m) ~
44. 
    
45. 　　struct Student *Create()
    # c& q$ K% H/ E
46. 
    
47. 　　{
    
48. 
    
49. 　　struct Student *pHead=NULL;/*初始化链表，头指针为空*/
    ; o  `/ f. ], M( \* S) L
50. 
    
51. 　　struct Student *pEnd,*pNew;
    
52. 
    0 ^# H# }. z4 P6 D0 L) T% d; E3 B
53. 　　iCount=0;/*初始化链表长度*/
    
54. 
    / M! M; @  p) f5 T5 [% W
55. 　　pEnd=pNew=(struct Student *)malloc(sizeof(struct Student));/*动态开辟一个学生信息结构体类型大小的空间，使得pEnd和pNew同时指向该结构体空间*/
    4 c8 Y# {0 {2 ]2 Q
56. 
    / _+ _5 o5 s% a( G' e3 A: E1 e
57. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    
58. 
    & _% m* Q  r0 e5 R) W
59. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    
60. 
    
61. 　　while(pNew->iNumber!=0)/*设定循环结束条件——学号不为0时*/
    
62. 
    # s! l, q1 a1 Q
63. 　　{
    
64. 
    
65. 　　iCount++;/*链表长度+1，即学生信息个数+1*/
    
66. 
    
67. 　　if(iCount==1)/*如果链表长度刚刚加为1，执行*/
    
68. 
    ( z8 Q  G6 r5 B, ?
69. 　　{
    
70. 
    
71. 　　pNew->next=pHead;/*使指针指向为空*/
    
72. 
    ' f9 e% n$ u! ~
73. 　　pEnd=pNew;/*跟踪新加入的结点*/
    1 B, W/ _( w+ B8 w; E4 L6 q
74. 
      @% d9 n5 s2 g7 k
75. 　　pHead=pNew;/*头结点指向首结点*/
    
76. 
    ! U! E0 m6 y, v( x: j; y
77. 　　}
    / k% F* {( `/ t
78. 
    % Z+ Q8 Q* l7 z# j
79. 　　else/*如果链表已经建立，长度大于等于2时，执行*/
    : \$ i  M8 q& ^" h6 }+ R
80. 
    
81. 　　{
    . @  F- V9 F/ G9 s; e+ w( ?" u" j7 u4 n
82. 
    + p5 v' N2 ~4 s" r9 g
83. 　　pNew->next=NULL;/*新结点的指针为空*/
    
84. 
    
85. 　　pEnd->next=pNew;/*原来的结点指向新结点*/
    4 |/ T: {9 X; N5 d0 A
86. 
    ( [, R& v7 y+ d3 F& j# l
87. 　　pEnd=pNew;/*pEnd指向新结点*/
    7 k, \: Z$ q5 h' E8 z
88. 
    
89. 　　}
    
90. 
    # a* f* C$ ?( m3 Y" x
91. 　　pNew=(struct Student *)malloc(sizeof(struct Student));/*再次分配结点的内存空间*/
    
92. 
    
93. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    ) X" x: }; X" p( |9 A
94. 
    
95. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    
96. 
    : x: K. X9 M  z" t' R2 c
97. 　　}
    / M) L: n6 i. a( X& g
98. 
    1 J- K9 W. c, o! h& O
99. 　　free(pNew);/*释放结点空间*/
    6 G  u1 a7 Y" ~9 n  i
100. 
     
101. 　　return pHead;/*返回创建出的头指针*/
       [( d/ p% Y4 i$ N7 M7 e1 e
102. 
     
103. 　　}
     ) r  c. ?7 X' C: @$ b8 G
104. 
     
105. 　　void print(struct Student *pHead)
     3 @9 w' }8 D( {+ ~9 j8 Z  w
106. 
     
107. 　　{
     
108. 
     : Y% v; f, d0 ~9 e
109. 　　struct Student *pTemp;/*定义指向一个学生信息结构体类型的临时指针*/
     
110. 
     $ j# u8 L0 H! d, W
111. 　　int iIndex=1;/*定义并出事哈变量iIndex，用来标识第几个学生(信息)*/
     ( N4 C. ~2 r* n" w# r
112. 
     
113. 　　printf("总共%d个学生(信息)：\n",iCount);
     3 J& q" T% t9 c5 g& p
114. 
     8 T2 F9 A: Q7 E# u* O
115. 　　pTemp=pHead;/*指针得到首结点的地址*/
     4 d: g* n1 |( ~
116. 
     
117. 　　while(pTemp!=NULL)/*当临时指针不指向NULL时*/
     
118. 
     
119. 　　{
     
120. 
     
121. 　　printf("第%d个学生信息：\n",iIndex);
     
122. 
     8 p6 W% I2 a$ C1 E: B2 `
123. 　　printf("姓名：%s",pTemp->cName); /*输出姓名*/
     , M+ C. _& g1 y6 U
124. 
     " v6 a% f5 V0 n" P8 u; `
125. 　　printf("学号：%d",pTemp->iNumber);/*输出学号*/
     / E9 G9 A. w: V9 L
126. 
     ) F" t- D! a& t* l; F9 B) n
127. 　　pTemp=pTemp->next;/*移动临时指针到下一个结点*/
     1 L+ h9 t! g: j- N" \) x
128. 
       H; S# a6 o2 @( @; u2 Q! {
129. 　　iIndex++;/*进行自加运算*/
     4 \% P. R0 W. T" {4 x# n
130. 
     $ J! ^- u; M  g1 P* T/ A' K, n
131. 　　}
     
132. 
     & T9 D! J7 n4 t0 ~  `5 b  F" i
133. 　　}

复制代码

4 k. y5 M3 {7 c. b! E3 M
+ |' [6 e' n9 z# a7 }
　　三、单链表的插入与删除
% g/ V+ C6 _: z6 Z$ c1 w5 O　　在本实例中，插入时根据传递来的学号，插入到其后。
, Q% k6 S4 `# R9 Z( f　　删除时根据其所在链表的位置，删除并释放该空间。
$ T( u- p% p7 r/ w+ D　　主函数增加如下：
. }2 U5 [! F* [  C9 J

; l2 a( d* q; b

1. 　　int main()
   
2. 
   
3. 　　{
   
4. 
   
5. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
   : m8 ~0 X. C) V% m7 x3 M4 |
6. 
   
7. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
   ! c3 _, s; G0 o! q0 K
8. 
   
9. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
   
10. 
    
11. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    : e1 s( m; \& T8 j: Q. X  A
12. 
    
13. 　　pHead=Insert(pHead,insert_n);/*将指针pHead和要插入的结点数传递给插入函数*/
    ( i, u! G* o7 E+ o
14. 
    
15. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
16. 
    * D/ h. x, ~4 P5 L6 P1 W
17. 　　Delete(pHead,delete_n);/*将指针pHead和要删除的结点数传递给删除函数*/
    
18. 
    ' s: }1 h7 J  A! l8 k
19. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    ! t+ T  I, @% e2 `" y4 ~+ D
20. 
    % u& V7 u; ^, {! J) V: V
21. 　　return 0;
    
22. 
    2 Y$ p+ _5 O4 G) a" K* k/ r
23. 　　}

复制代码

4 M$ W- J2 X- v9 ]9 s2 s, q
& Q. o5 R7 e3 M$ l) w* K) W
　　插入函数：

  _( D* f' c1 I: d/ c7 g! ]3 E" M
' ?! x/ [: [1 v$ |6 C' H
/ Y& u8 ]/ _% }9 z

1. 　　struct Student *Insert(struct Student *pHead,int number)
   
2. 
   6 t8 w4 ~# u6 [# ?. y* A
3. 　　{
   0 U4 k- u2 ]# ~; J5 V. I
4. 
   ' [0 h. [) V* r9 Z+ w
5. 　　struct Student *p=pHead,*pNew;/*定义pNew指向新分配的空间*/
   ) p: \9 V% P3 |3 w
6. 
   / {: N" k' Z" R; l' O; ]0 C) `
7. 　　while(p&&p->iNumber!=number)
   + ~' _5 ]# W! Y, n3 A1 u
8. 
   
9. 　　p=p->next;/*使临时结点跟踪到要插入的位置(该实例必须存在学号为number的信息，插入其后，否则出错)*/
   
10. 
      L% d- x5 c7 G& J- C$ t# x
11. 　　printf("姓名和学号：\n");
    3 M" ~/ T- R: e
12. 
    ( J* c# T0 Y* V- A9 w) @
13. 　　/*分配内存空间，返回该内存空间的地址*/
    * y) }$ }  n  ^% X4 ?9 ]( J% Z
14. 
    7 B  L* p9 S- D$ {1 L
15. 　　pNew=(struct Student *)malloc(sizeof(struct Student));
    
16. 
    
17. 　　scanf("%s",pNew->cName);
    
18. 
    & Q4 Q/ F7 ?4 j& c
19. 　　scanf("%d",&pNew->iNumber);
    
20. 
    
21. 　　pNew->next=p->next;/*新结点指针指向原来的结点*/
    3 z/ ^" v6 R+ N0 D
22. 
    7 K( P7 m/ V! c! ?5 `
23. 　　p->next=pNew;/*头指针指向新结点*/
    ' b8 t9 n6 L: @& J% K
24. 
    % @) A0 @( J3 b/ h6 E9 R
25. 　　iCount++;/*增加链表结点数量*/
    9 k4 x' K0 [, H: v- [5 A
26. 
    . v; @/ I. V! m- H4 p: O, m
27. 　　return pHead;/*返回头指针*/
    1 p2 [2 z" O0 q2 y# N# }
28. 
    
29. 　　}

复制代码

" O. c+ n( ?" Q( U# p5 j* u( Z
" s/ q8 r. H& `/ z
& a/ d$ ^" ?/ u% @　　删除函数：

+ L: ~6 R, |4 Q% X6 b5 ]7 \

1 d7 D( Z2 p7 B2 f" W4 ^

1. 　void Delete(struct Student *pHead,int number)
   
2. 
   / Y' Y, F3 Q. u$ {0 l; L
3. 　　{
   9 |& Y9 Q7 w8 }% {; h9 k
4. 
   & i3 c' `% K# ~/ t2 m
5. 　　int i;
   " X+ R$ X) J8 j! L) }
6. 
   
7. 　　struct Student *pTemp;/*临时指针*/
   9 x9 l7 Y/ N( m- `: I! C
8. 
   
9. 　　struct Student *pPre;/*表示要删除结点前的结点*/
   + I: A$ W, }# \1 y; {( N$ J5 D; F
10. 
    * l8 X0 V! ?6 Y) h/ E
11. 　　pTemp=pHead;/*得到链表的头结点*/
    
12. 
    1 K' Z/ N. E# z5 ~7 v
13. 　　pPre=pTemp;
    2 y" [5 r5 }3 Z6 Z1 D  B
14. 
    
15. 　　for(i=0;i
    ) _3 l  y1 E* ~/ H( `
16. 
    
17. 　　{/*通过for循环使得Temp指向要删除的结点*/
    1 ?' z; u" [" B2 M' ~, y4 g+ s
18. 
      v1 f& _: B5 r$ p" C8 V7 N4 a
19. 　　pPre=pTemp;
      ]9 O% M8 k0 ]: g
20. 
    - p: f7 m5 T, O( d' {3 h
21. 　　pTemp=pTemp->next;
    
22. 
    
23. 　　}
    
24. 
    0 ^& w: P2 n* i; s* U
25. 　　pPre->next=pTemp->next;/*连接删除结点两边的结点*/
    
26. 
    * r: r! K' w0 B# M) n9 d: w
27. 　　free(pTemp);/*释放要删除结点的内存空间*/
    * k9 l5 B3 ~4 ?# l( y& i
28. 
    
29. 　　iCount--;/*减少链表中的结点个数*/
    ) |$ ]1 \- S! S  J4 r- J, M
30. 
    
31. 　　}

复制代码

7 E1 x1 [; K& w4 U6 k( f

# U$ _' V4 j( G　　四、双向链表的概念
4 q5 Z+ f7 N- d' z6 K* f% C　　双向链表基于单链表。单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。
　　在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点的地址，一般称为右链域;一个存储直接前驱结点地址，一般称之为左链域。
) S, k7 _$ M, a4 i　　双向链表结构示意图：

" c* a9 e& B$ m! ]: y
; V$ B  D, k& ]* m8 y+ F( g

　　

9 i9 b, m1 P5 L7 L& f( U3 Y　　五、双向链表的建立与遍历
　　双向链表的源码实战和单链表类似，只是多了第二个指针域的控制，这里直接贴上没有注释的源代码。


* u1 @) k+ s0 `
1 _: {( z% Z2 u7 c9 I" p

1. 　　#include #include
   + M, i2 w/ ~5 Q% v$ g* Y
2. 
   
3. 　　#include
   / S# W! _% ]7 I! n/ a
4. 
   
5. 　　#define N 10
   
6. 
   
7. 　　typedef struct Node
   
8. 
   
9. 　　{
   % i! @; v; ~/ ?6 _3 O) h
10. 
    
11. 　　char name[20];
    
12. 
    1 D( ^7 A# f( ~( A2 o( S
13. 　　struct Node *llink,*rlink;
    9 V0 H. [- r. O
14. 
    . b6 L, U  a( ?0 }" o
15. 　　}STUD;
    
16. 
    
17. 　　STUD *creat(int);void print(STUD *);
    9 j, l. C" M6 @  S: f9 z+ E* x
18. 
    : O& }/ s0 B1 B! K% o. k+ _
19. 　　int main()
    4 f  t) t4 N+ |% f5 S! w+ P
20. 
    : c' s6 O" X# r7 |! x! T; P
21. 　　{
    . W3 @2 @3 Z4 _
22. 
    
23. 　　int number;
    
24. 
    2 ]. V0 m3 t+ p, Z' W  _3 d
25. 　　char studname[20];
    
26. 
    
27. 　　STUD *head,*searchpoint;
    
28. 
    $ ^6 T, ?/ t6 Q- Y
29. 　　number=N;
    2 X' S4 @( K& e! ]! Q
30. 
    2 m8 t; X+ I' I6 Z& r
31. 　　head=creat(number);
    2 A" d( u$ H5 p& b- x* F
32. 
    2 x/ w3 L" o4 W' F6 j
33. 　　print(head);
    ; m& Q' h: b6 ^
34. 
    
35. 　　printf("请输入你要查找的人的姓名：");
    
36. 
    
37. 　　scanf("%s",studname);
    / B2 H5 e: o- ]. ]
38. 
    
39. 　　searchpoint=search(head,studname);
    2 }/ R& e% L9 S7 z( n
40. 
    
41. 　　printf("你所要查找的人的姓名是：%s",*&searchpoint->name);
    
42. 
    
43. 　　return 0;
    ; L1 p# r* h2 a- Q6 c. J4 V
44. 
    
45. 　　}
    
46. 
    
47. 　　STUD *creat(int n)
    
48. 
    * d4 ?2 \- S% f+ H# y
49. 　　{
    : g* @" |3 w2 ~
50. 
    
51. 　　STUD *p,*h,*s;
    % c& x5 ~+ \: r6 P+ t- n8 \# L* `
52. 
    2 c/ r* V. P$ F, `' p
53. 　　int i;
    
54. 
    
55. 　　if((h=(STUD *)malloc(sizeof(STUD)))==NULL)
    & L+ a) G! q5 N+ }/ |- t# ~! Q$ _3 z
56. 
    
57. 　　{
    
58. 
    : @8 s5 I' c1 l/ _6 b4 i
59. 　　printf("不能分配内存空间");
    
60. 
    4 u. S8 V; B' s( n7 ^4 l$ E/ r
61. 　　exit(0);
    ! ~" i; _* r* w* P/ E7 R( k; T
62. 
    
63. 　　}
    & V' I* I0 Y0 i8 D2 [0 Q
64. 
    8 F4 u6 J& }$ I6 Z$ _
65. 　　h->name[0]='\0';
    2 K0 ?. A6 V6 I5 z; ~( w% f1 [1 ?
66. 
    $ _! D. z; N) E
67. 　　h->llink=NULL;
    % K# l3 k& I2 }0 J
68. 
    . j5 l2 L  E* @9 I; P9 e/ Y) X
69. 　　h->rlink=NULL;
    
70. 
    
71. 　　p=h;
    
72. 
    
73. 　　for(i=0;i
    3 X7 m' a3 b- W- |9 K, K, P# x/ X( H
74. 
    6 ~& u6 v/ ^' h% C& L
75. 　　{
    8 ^' S" z' \! s
76. 
    
77. 　　if((s=(STUD *)malloc(sizeof(STUD)))==NULL)
    
78. 
    
79. 　　{
    # z& Z9 O' P/ f' q' d
80. 
    
81. 　　printf("不能分配内存空间");
    
82. 
    
83. 　　exit(0);
    
84. 
    + V7 K5 K" ~# K! X3 V! K1 Q6 u, i
85. 　　}
    
86. 
    
87. 　　p->rlink=s;
    
88. 
    5 m# q/ [$ j4 X$ d; q- p1 R
89. 　　printf("请输入第%d个人的姓名",i+1);
    5 W( v) y- }3 r" d/ R8 |# \6 l
90. 
    
91. 　　scanf("%s",s->name);
    ; v, N0 w* z$ R: X0 n) H- ^
92. 
    1 a$ @$ e5 z( j, A, E# n- i. }! N
93. 　　s->llink=p;
    
94. 
    4 O1 o9 E( \# @
95. 　　s->rlink=NULL;
    & F. B/ o# R( S& {4 [. _0 o/ }% h
96. 
    
97. 　　p=s;
    7 z: b' z# y0 m& p4 T% V$ P
98. 
    4 H- H) z3 E" N5 O
99. 　　}
    
100. 
     
101. 　　h->llink=s;
       o, l8 Y5 q4 A% ^
102. 
     
103. 　　p->rlink=h;
     
104. 
     
105. 　　return(h);
     
106. 
     
107. 　　}void print(STUD *h)
     . o& p* e/ B3 ^4 ~+ ]
108. 
     
109. 　　{
     
110. 
     : g6 }- e# Z7 K- F; G' o
111. 　　int n;
     ! X2 t6 j, O/ n5 ]" r
112. 
     , m5 q) z3 F' h. |  m
113. 　　STUD *p;
     
114. 
     ! @( {1 n- D- P5 K: s' x4 V( {  x
115. 　　p=h->rlink;
     * ~. ^1 e  {' k1 m7 g( `3 g
116. 
     
117. 　　printf("数据信息为：\n");
     & u$ K" K( d3 S* A9 z( l
118. 
     
119. 　　while(p!=h)
     
120. 
     # |& R2 i# \$ v
121. 　　{
     
122. 
     
123. 　　printf("%s ",&*(p->name));
     
124. 
     
125. 　　p=p->rlink;
     
126. 
     ' Q  ~# y( M- t  T5 Q
127. 　　}
     
128. 
     
129. 　　printf("\n");
     
130. 
     
131. 　　}

复制代码

- l$ F* D1 Q2 @. e' \4 \
/ |( R, @) i: B- g. ?  n( R
. ^9 K" M7 z; Y4 D$ h　　六、双向链表的元素查找
& b4 W8 g% L( }7 E: N　　查找函数 STUD *search(STUD *,char *);
% s1 ^; c4 p6 ?
3 Q. B1 [2 T6 i0 n/ |2 d1 `

; y6 I7 P  P- p+ d! V* o

1. 　　STUD *search(STUD *h,char *x)
   
2. 
   
3. 　　{
   - z; X6 C2 o0 {( }* {
4. 
   2 j, F! C% f; Y5 F* @
5. 　　STUD *p;
   + S2 _3 O# |. @
6. 
   
7. 　　char *y;
   / J# m" G% `9 j2 c! n% B: J
8. 
   # L9 t6 f' j3 \. a# z9 Z
9. 　　p=h->rlink;
   ) k! U9 ]4 i$ k6 V" z7 |  P
10. 
    0 E. K7 K, g, _
11. 　　while(p!=h)
    1 b" T/ F( ]4 ~8 z6 g3 A
12. 
    
13. 　　{
    , {+ R/ E4 T! Z% R1 D( Y
14. 
    
15. 　　y=p->name;
    : n2 H- j; t- Z& o) z- {
16. 
    * C  S! x2 [/ Q9 m+ y
17. 　　if(strcmp(y,x)==0)
    ' N. i# R4 Y7 B
18. 
    
19. 　　return(p);
    
20. 
    
21. 　　else
    
22. 
    
23. 　　p=p->rlink;
    
24. 
    : b# f% L. |$ h1 V2 O
25. 　　}
    $ y0 |. }, t/ l* U' c
26. 
    
27. 　　printf("没有查到该数据!");
    
28. 
    
29. 　　}

复制代码

. Q8 O% k  \. c8 C
* A" c+ `! ?& I; p% p# b! F
8 z* `1 g2 v1 P+ r1 P: \: X　　七、循环链表的概念
% C+ u) {1 W2 X4 ?! F　　类似于单链表，循环链表也是一种链式的存储结构，由单链表演化而来。
　　单链表的最后一个结点的指针指向NULL，而循环链表的最后一个结点的指针指向链表头结点。
8 ]' E/ D4 G- j$ k2 J　　这样头尾相连，形成了一个环形的数据链。
　　循环链表的建立不需要专门的头结点。
　　判断循环链表是否为尾结点时，只需判断该节点的指针域是否指向链表头节点。
1 }# ^- x. `% j4 y　　八、合并两个链表的实例
　　建立两个带头节点的学生链表，每个节点包含学号、姓名和成绩，链表都按学号升序排列，将它们合并为一个链表仍按学号升序排列。
6 H2 J4 B) k* y8 @/ w　　算法分析：
! X4 g$ Y- c: A) L: [　　合并链表用merge()函数实现。函数中定义3个工作指针a、b、c，其中a、b分别指向La链表、Lb链表的当前结点，C指向合并后的链表尾结点。合并后链表的头结点共用La链表的头结点。
　　①合并前，先让a和b分别指向两个链表的第一个结点，c指向La链表的头结点。
　　②合并时应该分3种情况讨论，即La和Lb都没有处理完;La没处理完，但Lb处理完毕;Lb没处理完，但La处理完毕。
3 u( ~* p1 M; [　　③合并过程中应始终将La和Lb链表中较小的一个链接在Lc中，方能保持有序。
, }! Y! b+ X+ A" `
# z8 ^; v  E* E' h. v% U

  p$ G5 O- e# m7 z

1. 　void merge(struct stud *La,struct stud *Lb)
   
2. 
   
3. 　　{
   7 ?. j* x% _% B% Q" {: J( J
4. 
   
5. 　　struct stud *a,*b,*c;
   ! K/ j+ L, U( Y. g/ ?
6. 
     y# ^& g& Q+ `& L! {: W
7. 　　c=La;
   
8. 
   3 d. C) R( b( h
9. 　　a=La->next;/* 合并前 */
   
10. 
    1 B0 n& k8 ?  T5 t/ h: w
11. 　　b=Lb->next;
    
12. 
    
13. 　　while(a!=NULL && b!=NULL)/* La和Lb都没处理完 */
    
14. 
    . ?; j/ l% y# [6 K# ?5 U! q4 l/ L) d9 ~
15. 　　{
    ( U. V3 }* f  a# Y& D
16. 
    
17. 　　if(a->num <= b->num)
    
18. 
    
19. 　　{
    
20. 
    
21. 　　c->next=a;
    6 _$ K2 A6 s% f% K, y' D' i
22. 
    
23. 　　c=a;
    
24. 
    # {6 s+ c" X* }+ j& }6 b
25. 　　a=a->next;
    
26. 
    : m8 o/ _6 ~( \" b2 v8 w, C+ x3 O+ R
27. 　　}
    % p5 z- S5 K* @9 V/ Q( U* q! ]
28. 
    ; `5 F; O& z# M) C, `) P8 c; R
29. 　　else
    % n2 W* p) d1 @+ A
30. 
    7 o' Y' ^1 P4 u6 o
31. 　　{
    4 B: u4 W" G3 P# o- W2 F
32. 
    
33. 　　c->next=b;
    ! M% D4 K& h6 w/ e# k* ]
34. 
    $ c2 L4 f1 Q0 X) p
35. 　　c=b;
    
36. 
    
37. 　　b=b->next;
    " f9 B! L- t. n5 S; {/ B" x
38. 
    8 a1 u. A% L: e4 U1 `
39. 　　}
    
40. 
    ; k  p, Y! Q) d0 N2 b! L8 j# S3 ~
41. 　　}
    
42. 
    
43. 　　if(a!=NULL)
    
44. 
    ) J0 E3 N4 y& D1 A4 H- i! ^
45. 　　c->next=a;/* 若La没有处理完 */
    - ]; s, A, V! ?
46. 
    
47. 　　else
    
48. 
    
49. 　　c->next=b;/* 若Lb没有处理完 */
    * ?$ B& ^* a. T5 L8 R5 `
50. 
    " k5 ^4 s5 v5 T4 U+ u1 W" r
51. 　　free(Lb); /* 释放Lb的头结点 */
    8 Q8 i( p* J, \6 q' t3 F2 k9 Z
52. 
    
53. 　　}

复制代码

& ?6 K" o* {) P) L( U( T