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

小样岁月

　　最近临近期末的C语言课程设计比平时练习作业一下难了不止一个档次，第一次接触到了C语言的框架开发，了解了View(界面层)、Service(业务逻辑层)、Persistence(持久化层)的分离和耦合，一种面向过程的MVC的感觉。
- s9 R) |& k+ j　　而这一切的基础就在于对链表的创建、删除、输出、写入文件、从文件读出......
　　本篇文章在于巩固链表的基础知识(整理自《C语言程序设计教程--人民邮电出版社》第十章——指针与链表)，只对链表的概念及增删改查作出探讨，欢迎指教。
　　一、链表结构和静态/动态链表
　　二、单链表的建立与遍历
　　三、单链表的插入与删除
　　四、双向链表的概念
% X+ I! A- t$ Y/ r( V. U; e' l　　五、双向链表的建立与遍历
　　六、双向链表的元素查找
　　七、循环链表的概念
- }# x6 W9 U  R$ }. Y# J　　八、合并两个链表的实例
2 x- E) `1 l0 ?; W( y　　九、链表实战
4 m; P2 k8 j0 u; P5 F+ J$ l　　拓展思维、拉到最后去看看 (•̀ᴗ•́)و ̑̑
9 O: T' [# O" _  _2 O" H, s1 B　　一、链表结构和静态/动态链表
　　链表是一种常见的数据结构——与数组不同的是：
8 c  x/ q- E6 I# v2 U　　1.数组首先需要在定义时声明数组大小，如果像这个数组中加入的元素个数超过了数组的长度时，便不能正确保存所有内容;链表可以根据大小需要进行拓展。
8 _5 u4 o, j' G5 `& |　　2.其次数组是同一数据类型的元素集合，在内存中是按一定顺序连续排列存放的;链表常用malloc等函数动态随机分配空间，用指针相连。
　　链表结构示意图如下所示：
. F1 A2 A5 ]6 O. K2 j2 S+ d

　　

　　在链表中，每一个元素包含两个部分;数据部分和指针部分。数据部分用来存放元素所包含的数据，指针部分用来指向下一个元素。最后一个元素的指针指向NULL，表示指向的地址为空。整体用结构体来定义，指针部分定义为指向本结构体类型的指针类型。
/ F4 J* M/ A5 E+ x  U9 Z　　静态链表需要数组来实现，即把线性表的元素存放在数组中。数组单元存放链表结点，结点的链域指向下一个元素的位置，即下一个元素所在数组单元的下标。这些元素可能在物理上是连续存放的，也有可能是不连续的，它们之间通过逻辑关系来连接——这就要涉及到数组长度定义的问题，实现无法预知定义多大的数组，动态链表随即出现。
$ S1 y4 H: }6 O# w6 D% I$ ?% I  ?　　动态链表指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点的数据，并建立起前后相连的关系。
　　二、单链表的建立与遍历
. @8 n" g( r( y! b4 |/ K6 [　　单链表中，每个结点只有一个指针，所有结点都是单线联系，除了末为结点指针为空外，每个结点的指针都指向下一个结点，一环一环形成一条线性链。
4 e% Z  \& w7 y+ _/ X" N9 A* I! e　　链表的创建过程：
" D: E! Z" E! G' u7 W1 z1 s

　　

! h5 c  ]( X1 b　　接下来在源码中建立并遍历输出一个单链表。


! x2 d- F0 s6 f; V- X
# m. ]1 K9 d; h/ R6 u# B

1. 　　#include
   3 [- K$ u( n3 z' X: O% s, m
2. 
   
3. 　　#include
   
4. 
   : I4 q3 b; w  o2 p+ z* B# I
5. 　　#include
   5 @% U; f4 S5 x
6. 
   
7. 　　/*单向链表*/
   $ t5 \6 X9 ?1 W" J+ k+ c$ q$ r
8. 
   . G  N) y4 {- f2 Y' w  {
9. 　　struct Student/*建立学生信息结构体模型*/
   ) Q" ?* J) Q* [+ s. s
10. 
    ' l2 t* n7 C9 W/ T/ e: n2 Q
11. 　　{
    , y* W) k2 q0 L0 y) E# z$ X3 I
12. 
    
13. 　　char cName[20];/*学生姓名*/
    
14. 
    
15. 　　int iNumber;/*学生学号*/
    3 ^; X' G# b' w: @7 {$ u
16. 
    9 z9 h4 B' u1 q4 L
17. 　　struct student *next;/*指向本结构体类型的指针类型*/
    
18. 
    
19. 　　};
    9 j; I1 W" D: N; P
20. 
    ( J; A1 L3 P" @5 T! B' b) y4 ~  f5 k
21. 　　int iCount;/*全局变量表示链表长度*/
    3 u1 Z6 Q% |+ @5 e
22. 
    ; [2 {, u8 L' X) L' E; x/ s' g
23. 　　struct Student *Create();/*创建链表函数声明*/
    * ~9 x4 |0 D- I$ \3 w. N& e
24. 
    & M9 _$ ]0 J" d, w
25. 　　void print(struct Student *);/*遍历输出链表函数声明*/
    
26. 
    " d/ W5 C0 e( e; P& D- I9 l$ C1 Y1 s! `" y
27. 　　int main()
    
28. 
    * r* B% I8 V4 V$ w1 `# {
29. 　　{
    ) e( o: ]1 U. F8 A9 Y1 H$ f% u
30. 
    
31. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
    
32. 
    - p9 _- s! R/ S4 y, l0 J
33. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
    / [- h6 g$ l  m5 p: [3 @
34. 
    6 s% S5 j1 ?$ X+ X' j" i: t/ u
35. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
    / j# G: k# \# v  C' C" ]
36. 
    
37. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    
38. 
    # H/ O' w3 n  t7 h2 x  E
39. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
40. 
    
41. 　　return 0;
    
42. 
    
43. 　　}
    
44. 
    ( _1 R' G1 z4 X# q
45. 　　struct Student *Create()
    
46. 
    
47. 　　{
    - s) O; Z" i/ E: M: I3 F1 W) u
48. 
    / n# n) o% t' }' B0 v. m
49. 　　struct Student *pHead=NULL;/*初始化链表，头指针为空*/
    ! z$ j7 {* [) U: p0 o0 R+ t3 C4 E
50. 
    ; d: h8 N) G1 g3 ]; L
51. 　　struct Student *pEnd,*pNew;
    
52. 
    
53. 　　iCount=0;/*初始化链表长度*/
    
54. 
    
55. 　　pEnd=pNew=(struct Student *)malloc(sizeof(struct Student));/*动态开辟一个学生信息结构体类型大小的空间，使得pEnd和pNew同时指向该结构体空间*/
    7 C( p/ k' z% w/ c
56. 
    . t! R. _( b* K( d- k$ }& N
57. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    ' g$ b  o+ B1 C) Q/ {8 _4 I5 c
58. 
    
59. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    
60. 
    
61. 　　while(pNew->iNumber!=0)/*设定循环结束条件——学号不为0时*/
    - P! i5 t$ V; t( @% y
62. 
    & {/ N" N* Z5 Z: h: ^
63. 　　{
      x- C. j  B4 D7 U
64. 
    
65. 　　iCount++;/*链表长度+1，即学生信息个数+1*/
    
66. 
    
67. 　　if(iCount==1)/*如果链表长度刚刚加为1，执行*/
    ! [' D9 V! }4 U1 ]0 A$ ?. o+ ^
68. 
    . D8 c+ e: }: y$ b1 I% g: ]
69. 　　{
    $ r1 y: T5 r2 T! c. L- u2 @
70. 
    1 U7 L2 X& Q/ W% l+ s, B' L
71. 　　pNew->next=pHead;/*使指针指向为空*/
    8 D$ Q; `9 U/ G4 T0 K& `/ n  Y3 ?
72. 
    
73. 　　pEnd=pNew;/*跟踪新加入的结点*/
    
74. 
    
75. 　　pHead=pNew;/*头结点指向首结点*/
    
76. 
    
77. 　　}
    
78. 
    
79. 　　else/*如果链表已经建立，长度大于等于2时，执行*/
    6 U7 E9 p$ g8 }  d; z4 G
80. 
    
81. 　　{
    
82. 
    
83. 　　pNew->next=NULL;/*新结点的指针为空*/
    
84. 
    
85. 　　pEnd->next=pNew;/*原来的结点指向新结点*/
    ; t) @4 u+ c; o# b
86. 
    0 @( g1 @, E) x/ {/ e. w" [% p  T2 T
87. 　　pEnd=pNew;/*pEnd指向新结点*/
    
88. 
    ' V  s6 `9 _; E& X! Y9 i, n
89. 　　}
    . X* G6 R# G$ F* a! ~9 S, ]
90. 
    
91. 　　pNew=(struct Student *)malloc(sizeof(struct Student));/*再次分配结点的内存空间*/
    
92. 
    
93. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    
94. 
    
95. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    
96. 
    ' ~* r3 A# t' I+ \
97. 　　}
    0 f- o* @5 c! ?, r
98. 
    
99. 　　free(pNew);/*释放结点空间*/
    
100. 
     9 _) v- H% r9 p0 X
101. 　　return pHead;/*返回创建出的头指针*/
     
102. 
     6 `/ L2 M- x$ \+ Q0 i! H
103. 　　}
     5 M! ]1 v1 |3 o
104. 
     7 C5 U! }, C  M) d
105. 　　void print(struct Student *pHead)
     
106. 
     
107. 　　{
     
108. 
     
109. 　　struct Student *pTemp;/*定义指向一个学生信息结构体类型的临时指针*/
     % ?# v1 n: k" s! V' E+ {4 Q
110. 
     4 E! Y* c/ [& x! f5 C8 F0 V
111. 　　int iIndex=1;/*定义并出事哈变量iIndex，用来标识第几个学生(信息)*/
     " m4 o- r0 d  k0 P
112. 
     / n0 d% t- @* v! z! Q( t
113. 　　printf("总共%d个学生(信息)：\n",iCount);
     
114. 
       L/ a5 {2 e  [7 o0 ]
115. 　　pTemp=pHead;/*指针得到首结点的地址*/
     
116. 
     ! L% t( ?0 f! P7 `1 |( Z8 F/ X1 r4 K- j
117. 　　while(pTemp!=NULL)/*当临时指针不指向NULL时*/
     
118. 
     & T( r" {' X/ i  ^+ v) K% \
119. 　　{
     
120. 
     ' }; @+ K' w* S/ E* o. R% Y
121. 　　printf("第%d个学生信息：\n",iIndex);
     
122. 
     
123. 　　printf("姓名：%s",pTemp->cName); /*输出姓名*/
     
124. 
     0 l' I3 g+ M5 b; j
125. 　　printf("学号：%d",pTemp->iNumber);/*输出学号*/
     
126. 
     + D9 g) @+ S- x. j
127. 　　pTemp=pTemp->next;/*移动临时指针到下一个结点*/
     
128. 
     
129. 　　iIndex++;/*进行自加运算*/
     
130. 
     
131. 　　}
     9 [( S) W8 ~, i4 f8 Z6 A/ e$ y
132. 
     
133. 　　}

复制代码

1 C* o$ v0 ]! P9 V& E0 h

" L$ _+ d/ H7 d1 V% l　　三、单链表的插入与删除
+ ]3 Y1 f' E6 `  q　　在本实例中，插入时根据传递来的学号，插入到其后。
; Z- F# e  o9 B: Q! }; S　　删除时根据其所在链表的位置，删除并释放该空间。
) q% ~) [; B% E+ i. _& E  b- L　　主函数增加如下：
/ r2 ?3 q* j' M3 E. C& C6 V7 E: S
( V; L* k, i3 K% _5 u' b! N8 ~

1. 　　int main()
   
2. 
   
3. 　　{
   
4. 
   6 }: w9 z; Q6 U) G. D" g. T
5. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
   
6. 
   1 U$ E* K( t  {# l% T
7. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
   / z/ X$ x( H7 A, G% ?. b9 E
8. 
   
9. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
   9 u- p0 ^4 W% H; ~( J: K
10. 
    ) t" Z3 U- k# ]* n
11. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    3 ?. h( b9 @1 `& H/ s
12. 
    2 g; i% a. K# u2 H& w- b
13. 　　pHead=Insert(pHead,insert_n);/*将指针pHead和要插入的结点数传递给插入函数*/
    
14. 
    
15. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    9 p3 S: E5 j# t$ V% J
16. 
    6 \! M" T) w- D: U+ z) w  U
17. 　　Delete(pHead,delete_n);/*将指针pHead和要删除的结点数传递给删除函数*/
    
18. 
    # D2 S' V" _  V" {& @! n. Z, G
19. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    ' }1 S& `! H+ ]! n, T$ v% c
20. 
    ) f6 G& s6 p! o& D3 Q
21. 　　return 0;
    ) `9 a. f9 I. }3 m
22. 
    
23. 　　}

复制代码

4 m3 ?" h' d& L$ I
! z$ u' l* |2 N; M" A+ g5 f8 p  @　　插入函数：

1. 　　struct Student *Insert(struct Student *pHead,int number)
   
2. 
   
3. 　　{
   
4. 
   
5. 　　struct Student *p=pHead,*pNew;/*定义pNew指向新分配的空间*/
   
6. 
   
7. 　　while(p&&p->iNumber!=number)
   ! {2 \5 C& y8 A$ u6 a6 k9 q- N
8. 
   , v' X8 |3 E* Z+ [# c
9. 　　p=p->next;/*使临时结点跟踪到要插入的位置(该实例必须存在学号为number的信息，插入其后，否则出错)*/
   
10. 
    
11. 　　printf("姓名和学号：\n");
    8 E3 R# p1 ?" w1 ~# R4 m% W
12. 
    
13. 　　/*分配内存空间，返回该内存空间的地址*/
    8 D3 M: c: j" x& k' \7 j
14. 
    
15. 　　pNew=(struct Student *)malloc(sizeof(struct Student));
    3 m. p  f9 Y2 n' `9 n  J
16. 
    
17. 　　scanf("%s",pNew->cName);
    ! g9 p" L* G: y7 ]) q8 x
18. 
    ! M. k8 u, b8 }( |2 Z$ ]' ^0 a6 L
19. 　　scanf("%d",&pNew->iNumber);
    
20. 
    
21. 　　pNew->next=p->next;/*新结点指针指向原来的结点*/
    + S% b, E5 B+ k; J$ c- S9 {
22. 
    6 W5 M- [% S& B3 M3 W. S8 ]* D4 [
23. 　　p->next=pNew;/*头指针指向新结点*/
    
24. 
    ( ~4 \% `) C- w0 A
25. 　　iCount++;/*增加链表结点数量*/
    9 Z6 M( j/ z! d8 }
26. 
    
27. 　　return pHead;/*返回头指针*/
    
28. 
    
29. 　　}

复制代码

& d4 `: J9 A" @9 a
4 E" [. ^' H& I2 I
　　删除函数：
. q; @0 C# Z' O  {. ?0 a6 I

. N0 F5 S+ G' i; y! i8 S+ K4 c

1. 　void Delete(struct Student *pHead,int number)
   
2. 
   
3. 　　{
   3 a8 z7 s, F6 R* F$ Y% @8 M1 p3 f
4. 
   
5. 　　int i;
   
6. 
   1 b; |1 N! Z: l7 T. t! B0 V( y
7. 　　struct Student *pTemp;/*临时指针*/
   5 J2 V6 ^; O4 w% b5 F6 w+ E
8. 
   
9. 　　struct Student *pPre;/*表示要删除结点前的结点*/
   ( h2 I/ c$ U7 A% U1 p' f0 o
10. 
    1 i! n- N2 g2 o: ?+ i- P
11. 　　pTemp=pHead;/*得到链表的头结点*/
    ! s" Z1 D7 S2 I; L0 F
12. 
    ' F' V/ Y' H$ M7 X" P
13. 　　pPre=pTemp;
    
14. 
    
15. 　　for(i=0;i
    
16. 
    
17. 　　{/*通过for循环使得Temp指向要删除的结点*/
    
18. 
    
19. 　　pPre=pTemp;
    
20. 
    
21. 　　pTemp=pTemp->next;
    9 @0 e9 x2 \, |4 u8 u3 \9 P8 I* O8 j
22. 
    / H5 d6 t8 |5 v
23. 　　}
    9 b" J& r  g4 D2 j2 b
24. 
    
25. 　　pPre->next=pTemp->next;/*连接删除结点两边的结点*/
    + ^0 q$ K2 Q" L, q7 E2 R5 t
26. 
    
27. 　　free(pTemp);/*释放要删除结点的内存空间*/
    
28. 
    & S5 v5 V6 x( C4 b
29. 　　iCount--;/*减少链表中的结点个数*/
    + s5 L5 X( q; f1 s; d; r
30. 
    
31. 　　}

复制代码

1 g- C' a+ A; x2 w6 Q0 A
  C0 D  J! e7 d9 W& F
　　四、双向链表的概念
3 G% {& N& b5 O! N, Q5 F　　双向链表基于单链表。单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。
　　在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点的地址，一般称为右链域;一个存储直接前驱结点地址，一般称之为左链域。
, n. ~2 ]* Y( _- D# ?+ g　　双向链表结构示意图：


. K' E0 E: Z+ M7 N( l6 p  z9 i

　　

, K# s% c" O; o1 V　　五、双向链表的建立与遍历
- R2 h; j; b; A　　双向链表的源码实战和单链表类似，只是多了第二个指针域的控制，这里直接贴上没有注释的源代码。
& z* q+ I, F9 u
/ I! o  F+ D- E& _: ~, q) |

1. 　　#include #include
   
2. 
   " b: G  Q9 d2 A0 U
3. 　　#include
   
4. 
   ; w$ k6 b4 x) r# R
5. 　　#define N 10
   
6. 
   0 V2 T$ H, N+ \
7. 　　typedef struct Node
   / ]2 y: U" s! G- N9 X
8. 
   
9. 　　{
   
10. 
    ) x3 T* _8 ^8 ?4 k
11. 　　char name[20];
    
12. 
    
13. 　　struct Node *llink,*rlink;
    
14. 
    - y6 d6 m- _  L
15. 　　}STUD;
    
16. 
    
17. 　　STUD *creat(int);void print(STUD *);
    % [/ d' W, @4 K  {- ?( P# \
18. 
    & ]3 ^0 V  L; F' w  P7 y
19. 　　int main()
    
20. 
    0 Q  r2 D! |8 {% x5 y
21. 　　{
    
22. 
    
23. 　　int number;
    6 Y3 H, ?4 K; X+ Q7 W
24. 
    8 S8 \* W9 I# ?9 F3 o
25. 　　char studname[20];
    , ?3 J0 B, P, _6 k+ ^
26. 
    5 f( V0 M# ]( V+ b( G( F  n
27. 　　STUD *head,*searchpoint;
    ! p; o( i/ V* B- ?
28. 
    4 P! T, p3 w6 S4 S$ u6 h
29. 　　number=N;
    
30. 
    3 k+ p3 a' _) b% [/ t! z
31. 　　head=creat(number);
    9 R9 g+ _4 o' `9 x4 N
32. 
    7 Y, x# F/ n) P1 }$ I: u. h! d- i& t
33. 　　print(head);
    * r: P/ O# h8 m( U( L+ g# M
34. 
    
35. 　　printf("请输入你要查找的人的姓名：");
    7 J# n4 D$ W3 ~3 `
36. 
    
37. 　　scanf("%s",studname);
    
38. 
    
39. 　　searchpoint=search(head,studname);
    6 p4 O, T/ ^  _5 a
40. 
    ) A! P0 Q* K$ D  }2 Q  N( c" M6 F
41. 　　printf("你所要查找的人的姓名是：%s",*&searchpoint->name);
    
42. 
    8 X: q7 R! R, W$ v/ i( @* a  H) l
43. 　　return 0;
    7 ^$ ?# ?: m, [1 o( o, \: n
44. 
    
45. 　　}
    
46. 
    : t  K4 B9 u" Y* g
47. 　　STUD *creat(int n)
    # u, V7 Z  v5 e
48. 
    
49. 　　{
    & I3 H( f7 a# O3 v8 I6 L) ?7 ~9 v
50. 
    
51. 　　STUD *p,*h,*s;
    . a3 g1 I& K# W& y" K( w' K
52. 
    4 G& H5 A- ~0 k- K1 L5 }
53. 　　int i;
    
54. 
    7 i: U- p3 N, a0 J+ Z
55. 　　if((h=(STUD *)malloc(sizeof(STUD)))==NULL)
    
56. 
    " |) o! P1 z* m. z' d4 P
57. 　　{
    " T& e" b: F4 P* n) t# d1 J
58. 
    5 U/ i+ w8 b: x( ?
59. 　　printf("不能分配内存空间");
    
60. 
    9 d7 K5 [; a; k: w
61. 　　exit(0);
    
62. 
    
63. 　　}
    
64. 
    " y) f: j' Q% K# k6 ~# A
65. 　　h->name[0]='\0';
    
66. 
    
67. 　　h->llink=NULL;
    . v8 Y4 g( d0 I* u$ f6 @( Q
68. 
    % R- h9 ^2 d* C# C# y3 s
69. 　　h->rlink=NULL;
    ( z9 L6 E) I$ p
70. 
    : K5 v1 L* s7 X( T# i* G! m
71. 　　p=h;
    . j9 f5 N9 V0 R! M6 `
72. 
    
73. 　　for(i=0;i
    
74. 
    
75. 　　{
    9 ^3 H5 I  Q( Z9 `
76. 
    
77. 　　if((s=(STUD *)malloc(sizeof(STUD)))==NULL)
    
78. 
    4 x+ Y( ]- z7 W0 l- v
79. 　　{
    0 P+ k, [/ e- P4 q
80. 
    
81. 　　printf("不能分配内存空间");
    / c; Q0 g! v5 ^. G* \/ S6 k
82. 
    
83. 　　exit(0);
    
84. 
    
85. 　　}
    
86. 
    
87. 　　p->rlink=s;
    
88. 
    7 o  r3 W! A7 X! n( C
89. 　　printf("请输入第%d个人的姓名",i+1);
      {, C) p; n" \! b1 G# y+ f* B
90. 
    2 n) h; F" l$ A, L5 E9 x& y& ]
91. 　　scanf("%s",s->name);
    
92. 
    
93. 　　s->llink=p;
    
94. 
    4 B" J- h8 t+ J% P
95. 　　s->rlink=NULL;
    6 W0 i8 p( L) N& s9 t  c3 V
96. 
    
97. 　　p=s;
    : c% j0 m; n2 m1 N2 C* i2 I! @
98. 
    
99. 　　}
    
100. 
     
101. 　　h->llink=s;
     " Z$ n% {4 Y, |7 b, {& c) v
102. 
     ! T8 Y5 q1 [+ t* g, x
103. 　　p->rlink=h;
     ( B. L  ^  F! q/ `
104. 
     $ A1 N0 w6 w+ W! l! j7 w% ]3 ]
105. 　　return(h);
     
106. 
     1 b! g# C+ h* ]7 Q8 z; z6 N! a+ q
107. 　　}void print(STUD *h)
     5 J# s8 X2 X: ]: U+ \0 C
108. 
     
109. 　　{
     
110. 
     
111. 　　int n;
     5 [* d. r  S( m) ?( D
112. 
     2 y' u! b9 |! m6 F
113. 　　STUD *p;
     
114. 
     $ U" C9 |5 V& @) L- w" y
115. 　　p=h->rlink;
     7 N' t3 L6 ]- J9 s' q
116. 
     % D7 R0 D, D0 m& s
117. 　　printf("数据信息为：\n");
     6 o0 }5 Z& |( a
118. 
     
119. 　　while(p!=h)
     1 Y+ O9 K0 L) O+ C
120. 
     + f5 d# d: d* h* H& Y- X
121. 　　{
     
122. 
     0 u0 M7 i. y  x8 n# Z2 m. N
123. 　　printf("%s ",&*(p->name));
     
124. 
     
125. 　　p=p->rlink;
     
126. 
     
127. 　　}
     2 W5 O9 S2 a0 i) T
128. 
     2 A3 ~! u% e0 I2 d
129. 　　printf("\n");
     
130. 
     
131. 　　}

复制代码

5 ~" L7 }1 W) }5 w8 I8 {7 f) n) W2 m

5 v( I7 }% W2 \+ z( a7 N: O; H
; j) S, _. _$ n& h0 L# J& B　　六、双向链表的元素查找
- V+ T% g/ R9 }/ S　　查找函数 STUD *search(STUD *,char *);
8 ]. o# s/ }$ W


. v% p, h$ t  S: R7 W. D4 r

1. 　　STUD *search(STUD *h,char *x)
   
2. 
   5 J( Z1 o. l5 A9 N- J0 f! ?
3. 　　{
     u# U  h: Z5 p7 y8 M4 A1 [, k
4. 
   # \) S. S6 U- v( A7 }, U7 k, J
5. 　　STUD *p;
   
6. 
   
7. 　　char *y;
   ; v4 [# Z4 h9 }" H+ C
8. 
   & I. B! x- Z2 A! b* D9 r  t
9. 　　p=h->rlink;
   , Y4 r* `% ~, n# D4 r; u
10. 
    6 ]( D+ J: Y/ f* x& Z0 I
11. 　　while(p!=h)
    ( W2 _: {/ ?6 c# O, t4 \( q0 q
12. 
    2 [( W+ t# F7 i/ ^! W
13. 　　{
    ( H% P# x" v' ?! B) F3 h9 z
14. 
    9 z! E$ [8 W- J* z9 `
15. 　　y=p->name;
    6 E/ B. Y9 S. a1 O0 w, }
16. 
    , [5 Z& w  m1 i0 f  n5 r
17. 　　if(strcmp(y,x)==0)
    + L4 ]+ P+ e$ s, O( W1 a7 ?
18. 
    % ?- v; B+ U, H% Z& V
19. 　　return(p);
    ' I  F3 E4 w' Q/ x
20. 
    
21. 　　else
    
22. 
    
23. 　　p=p->rlink;
    + q1 c2 S8 I: i% R
24. 
    
25. 　　}
    
26. 
    $ H* q( Y, I& H4 V
27. 　　printf("没有查到该数据!");
    5 F5 `( L! U6 n% f# q- T
28. 
    
29. 　　}

复制代码

　　七、循环链表的概念
6 @" f$ `% B% C  O/ H3 s( Q! S　　类似于单链表，循环链表也是一种链式的存储结构，由单链表演化而来。
　　单链表的最后一个结点的指针指向NULL，而循环链表的最后一个结点的指针指向链表头结点。
( @/ \4 G' g( @- g/ }　　这样头尾相连，形成了一个环形的数据链。
5 W6 Q) l5 J9 x+ L8 K! G; |6 V　　循环链表的建立不需要专门的头结点。
　　判断循环链表是否为尾结点时，只需判断该节点的指针域是否指向链表头节点。
" Z( |) T7 l& o4 C! L$ M　　八、合并两个链表的实例
* G$ P1 [% S. ?1 ?　　建立两个带头节点的学生链表，每个节点包含学号、姓名和成绩，链表都按学号升序排列，将它们合并为一个链表仍按学号升序排列。
　　算法分析：
　　合并链表用merge()函数实现。函数中定义3个工作指针a、b、c，其中a、b分别指向La链表、Lb链表的当前结点，C指向合并后的链表尾结点。合并后链表的头结点共用La链表的头结点。
　　①合并前，先让a和b分别指向两个链表的第一个结点，c指向La链表的头结点。
3 g! @+ T8 g& p) U' Y2 z4 D! R　　②合并时应该分3种情况讨论，即La和Lb都没有处理完;La没处理完，但Lb处理完毕;Lb没处理完，但La处理完毕。
　　③合并过程中应始终将La和Lb链表中较小的一个链接在Lc中，方能保持有序。

1. 　void merge(struct stud *La,struct stud *Lb)
   
2. 
   8 l: C4 P0 q  [
3. 　　{
   * q) K5 R: r& B1 I" x* T
4. 
   " n1 W) q- `0 N& O' z/ K6 R
5. 　　struct stud *a,*b,*c;
   
6. 
   - }) ?& y5 M& E0 m6 M: H
7. 　　c=La;
   - o" n! k! t1 w
8. 
   
9. 　　a=La->next;/* 合并前 */
   & w9 ?+ [# D* T$ M
10. 
    
11. 　　b=Lb->next;
    
12. 
    7 O- W1 O$ e; n: [2 y$ U8 R+ r
13. 　　while(a!=NULL && b!=NULL)/* La和Lb都没处理完 */
    
14. 
      o( ?3 r. x% g5 @  Q( e
15. 　　{
    ) l  G$ x' o3 X, {
16. 
    
17. 　　if(a->num <= b->num)
    " A: g' @- R5 H. ]; i2 C0 ?6 x6 r  E
18. 
    
19. 　　{
    % h# K: S8 [, d5 M5 ^6 [
20. 
    . v. R( r% a: y3 H/ g
21. 　　c->next=a;
    * R8 h* J7 `$ X2 J
22. 
      O0 d1 Z+ K0 S5 H, }6 Y
23. 　　c=a;
    
24. 
    
25. 　　a=a->next;
    
26. 
    : \. k- w% o& m8 v
27. 　　}
      M, i+ ^( z* K2 |) E# ^
28. 
    
29. 　　else
    
30. 
    
31. 　　{
    
32. 
    0 y% g  S) F+ r; d
33. 　　c->next=b;
    6 N- e  N5 k) E# o0 \6 P7 y. l
34. 
    % G. g8 Z# A8 Y, [2 C0 I
35. 　　c=b;
    
36. 
    * \- f( f2 y" p- f, y! L
37. 　　b=b->next;
    
38. 
    . x/ q* x6 c4 k1 G- a' i* y
39. 　　}
    : d4 _$ |. T0 a3 X
40. 
    
41. 　　}
    $ c; l/ K' k1 X) h
42. 
    
43. 　　if(a!=NULL)
    / A, N- Y" S7 j) I5 Y+ ~+ @, r* m
44. 
    , j6 }8 [5 P2 {% Q& n
45. 　　c->next=a;/* 若La没有处理完 */
    ) ^3 q$ J4 M* d  v
46. 
    3 N0 D  ^0 E) U& d. V6 T
47. 　　else
    " m, ~5 P8 N) j5 w- G
48. 
    
49. 　　c->next=b;/* 若Lb没有处理完 */
    , a2 S- j9 \6 h9 ^  ^
50. 
    ) I' D! ]- e+ D3 J" {3 A( i8 d
51. 　　free(Lb); /* 释放Lb的头结点 */
    
52. 
    
53. 　　}

复制代码

. g6 r6 g) S# Q- n6 y, E1 z