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

小样岁月

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

　　

4 M: r1 N! o# f: ^4 t# q  Y  B　　在链表中，每一个元素包含两个部分;数据部分和指针部分。数据部分用来存放元素所包含的数据，指针部分用来指向下一个元素。最后一个元素的指针指向NULL，表示指向的地址为空。整体用结构体来定义，指针部分定义为指向本结构体类型的指针类型。
　　静态链表需要数组来实现，即把线性表的元素存放在数组中。数组单元存放链表结点，结点的链域指向下一个元素的位置，即下一个元素所在数组单元的下标。这些元素可能在物理上是连续存放的，也有可能是不连续的，它们之间通过逻辑关系来连接——这就要涉及到数组长度定义的问题，实现无法预知定义多大的数组，动态链表随即出现。
3 w( d9 S9 G0 u, i' p4 j( m% J　　动态链表指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点的数据，并建立起前后相连的关系。
　　二、单链表的建立与遍历
3 J: n  n! k7 W. Y　　单链表中，每个结点只有一个指针，所有结点都是单线联系，除了末为结点指针为空外，每个结点的指针都指向下一个结点，一环一环形成一条线性链。
. a6 A, {& M$ a) V　　链表的创建过程：

　　

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


1 ?1 B9 N, G. a6 |+ I7 L6 u# ]/ b) S
. r5 ?0 }) l! B  l

1. 　　#include
   6 o( k# U! T. l0 ~' D: I
2. 
   
3. 　　#include
   - R4 k) Z! c& v# C" J* b
4. 
   . X! g# R1 J/ p6 D9 Q0 H+ C$ g7 z
5. 　　#include
   
6. 
   & l3 C2 A% y3 W; s! Y& a3 x
7. 　　/*单向链表*/
   ' A. Z# }# F$ B7 U
8. 
   
9. 　　struct Student/*建立学生信息结构体模型*/
   
10. 
    % |) v2 ?" h# ]3 f
11. 　　{
      Z* H9 _. c7 X
12. 
    
13. 　　char cName[20];/*学生姓名*/
    
14. 
    
15. 　　int iNumber;/*学生学号*/
    * Z7 s$ s4 y) k
16. 
    ( o: T5 {; N5 P, F6 ^( X
17. 　　struct student *next;/*指向本结构体类型的指针类型*/
      m9 U9 v+ |( z$ z
18. 
    $ e" o) E. a8 C  F' q' i
19. 　　};
    
20. 
    
21. 　　int iCount;/*全局变量表示链表长度*/
    3 v: Z5 s# ^5 s% U
22. 
    , ~+ C3 J+ Q4 c* }" p, U6 V
23. 　　struct Student *Create();/*创建链表函数声明*/
    
24. 
    
25. 　　void print(struct Student *);/*遍历输出链表函数声明*/
    
26. 
    7 K( B* E( M, ^, s7 |2 {! i+ {
27. 　　int main()
    " K4 h, t2 C; E0 p- s/ _  q* Z
28. 
    8 x5 L! U7 M3 V$ N: {: z
29. 　　{
    
30. 
    4 B! C" g3 q& J4 Z! [9 _2 x
31. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
    : L# L6 G" @/ a# l, m+ A. F
32. 
    
33. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
    ( O! O) r2 N; v4 {" g/ z3 y* A' X. Q3 S
34. 
    9 _4 |, ~7 v0 J
35. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
    9 q. E0 z7 n9 o$ q/ M( {% W! C
36. 
    3 f. S; a1 [+ ^
37. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    " V# g4 l: }) E- i: O7 Q
38. 
    
39. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
40. 
    
41. 　　return 0;
    
42. 
    $ w8 y, F1 {. |! P* U! r+ q
43. 　　}
    
44. 
    % B/ ^9 o5 C% q4 G2 r5 ]
45. 　　struct Student *Create()
    ; \! a# `6 k% k! O
46. 
    8 D4 |9 T0 o3 }5 J. b; d9 X
47. 　　{
    
48. 
    1 Z3 H7 A1 E% W$ r0 [  R
49. 　　struct Student *pHead=NULL;/*初始化链表，头指针为空*/
    ! p+ t  h5 u% x( J! p0 G' q
50. 
    
51. 　　struct Student *pEnd,*pNew;
    9 \+ I% N+ k/ d9 Z" e0 K
52. 
    / Q7 @5 }" p/ e% |9 R  L
53. 　　iCount=0;/*初始化链表长度*/
    / G4 {: l' {7 Y/ g
54. 
    
55. 　　pEnd=pNew=(struct Student *)malloc(sizeof(struct Student));/*动态开辟一个学生信息结构体类型大小的空间，使得pEnd和pNew同时指向该结构体空间*/
    
56. 
    % K! y& H7 Q$ Y+ g) Q
57. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    
58. 
    
59. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    / F8 e& A% i7 J) b
60. 
    2 X) `$ p/ {/ B
61. 　　while(pNew->iNumber!=0)/*设定循环结束条件——学号不为0时*/
    
62. 
    
63. 　　{
    
64. 
    8 X: {$ j/ \6 {
65. 　　iCount++;/*链表长度+1，即学生信息个数+1*/
    7 e1 J. u! D  Y0 V( t* V2 G. Q
66. 
    
67. 　　if(iCount==1)/*如果链表长度刚刚加为1，执行*/
    : ?8 T7 n: S- |$ C, l
68. 
    
69. 　　{
    
70. 
    6 a) k/ @, v% V, y" k5 [( u0 C7 I
71. 　　pNew->next=pHead;/*使指针指向为空*/
    9 P) f5 J! T! T
72. 
    
73. 　　pEnd=pNew;/*跟踪新加入的结点*/
    + k8 F. u- }2 M$ k2 ]
74. 
    # ]$ |$ s& T: `- a4 u
75. 　　pHead=pNew;/*头结点指向首结点*/
    5 l  R7 o* ~& A* Z' n
76. 
    9 Z4 b; A4 s# C9 G2 L0 @
77. 　　}
    $ e2 j9 w" t! h
78. 
    
79. 　　else/*如果链表已经建立，长度大于等于2时，执行*/
    % c0 F7 z( M8 Q  }& E1 d
80. 
    
81. 　　{
    
82. 
    
83. 　　pNew->next=NULL;/*新结点的指针为空*/
    : L! `# m: ^6 o, A, h
84. 
    
85. 　　pEnd->next=pNew;/*原来的结点指向新结点*/
    4 j4 G* G1 y0 Q5 |; J
86. 
    
87. 　　pEnd=pNew;/*pEnd指向新结点*/
    9 |9 t& q  o% D
88. 
    ! ]" {' m; m8 R
89. 　　}
    
90. 
    2 ]1 q- C: Z6 y, X7 ]% I9 D
91. 　　pNew=(struct Student *)malloc(sizeof(struct Student));/*再次分配结点的内存空间*/
    - g. W! O  y' ?) B
92. 
    7 G8 C: r+ z, y1 T
93. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    
94. 
    - d. Q7 `2 [1 Q, I% J
95. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    
96. 
    
97. 　　}
    5 n  W- f& m9 ~$ J: d* Z9 K& H
98. 
    
99. 　　free(pNew);/*释放结点空间*/
    
100. 
     
101. 　　return pHead;/*返回创建出的头指针*/
     , ~5 R/ @" T+ j5 D6 J
102. 
     $ ^% ~2 [( E2 F; W  Z
103. 　　}
     
104. 
     0 E) a% |  t) h% H* y* R# j
105. 　　void print(struct Student *pHead)
     
106. 
     
107. 　　{
     7 Q5 ^1 I/ p4 h% S
108. 
     
109. 　　struct Student *pTemp;/*定义指向一个学生信息结构体类型的临时指针*/
     " y2 _, U" S  Q& [
110. 
     
111. 　　int iIndex=1;/*定义并出事哈变量iIndex，用来标识第几个学生(信息)*/
     # @& ]1 S( w; v5 D9 x, s! `) W' X
112. 
     
113. 　　printf("总共%d个学生(信息)：\n",iCount);
     . T9 T0 c) n9 q* S4 d9 J8 D
114. 
     ( R$ @; L+ |" |2 J: y
115. 　　pTemp=pHead;/*指针得到首结点的地址*/
     
116. 
     
117. 　　while(pTemp!=NULL)/*当临时指针不指向NULL时*/
     9 x- k+ h4 O* p6 F! B* A4 k
118. 
     4 U" B0 }- @1 a- M9 r
119. 　　{
     ' N+ f9 J" T. c+ C! I9 F
120. 
     
121. 　　printf("第%d个学生信息：\n",iIndex);
     4 k. `: `& B/ V) l' S# G
122. 
     
123. 　　printf("姓名：%s",pTemp->cName); /*输出姓名*/
     2 a; u  ]- Y0 I$ \, g
124. 
     
125. 　　printf("学号：%d",pTemp->iNumber);/*输出学号*/
     
126. 
     7 X' A+ s4 u9 c' i! f
127. 　　pTemp=pTemp->next;/*移动临时指针到下一个结点*/
     
128. 
     ) B5 |% l5 M7 G$ y
129. 　　iIndex++;/*进行自加运算*/
     8 D0 _) C. S. M* D) M
130. 
     
131. 　　}
     
132. 
     
133. 　　}

复制代码

- N& P9 c' H  S0 X


" o- s9 ~8 z& k. w% B3 }& C5 \　　三、单链表的插入与删除
8 Z3 _) g! b% L+ p! ?& h　　在本实例中，插入时根据传递来的学号，插入到其后。
& {, K9 m8 F0 Q7 g　　删除时根据其所在链表的位置，删除并释放该空间。
　　主函数增加如下：
: P$ j' w# {5 |* S5 k# P
/ }) B3 B" t8 v6 K5 t0 f9 l$ g

; O( Q" I! ^  z2 P2 [

1. 　　int main()
   , V. E7 I$ J% M4 C! t! g" H4 V
2. 
   
3. 　　{
   : {! J, B& Q, F+ M1 e; S* g  k
4. 
   6 p' u# v: W8 K& s
5. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
   ) u" Z& U0 K) z
6. 
   
7. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
   
8. 
   
9. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
   
10. 
    
11. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    " E5 E1 Q; C( k+ z
12. 
    4 l9 ?- a8 v0 S
13. 　　pHead=Insert(pHead,insert_n);/*将指针pHead和要插入的结点数传递给插入函数*/
    
14. 
    + @' E8 a% L+ W3 z$ g4 E' ?
15. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
16. 
    - u  \6 B. E6 W5 |. w- [; n( M( i& }
17. 　　Delete(pHead,delete_n);/*将指针pHead和要删除的结点数传递给删除函数*/
    
18. 
    " X' z* J5 a+ U- r0 ~8 u! u) T
19. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
20. 
    
21. 　　return 0;
    $ E* L; ?0 o. u: O! j
22. 
    , Y8 k7 }7 h) O2 I) r, e
23. 　　}

复制代码

  z% z) q4 n; B. ]. P
+ P& w; u6 }8 D5 h

　　插入函数：


5 Y9 Y# i, O/ F! L1 a
6 Q+ ]7 T8 R* K3 h

1. 　　struct Student *Insert(struct Student *pHead,int number)
   
2. 
   8 ?* ?* N  ~& c
3. 　　{
   
4. 
     S8 _/ @# c' B, N' _
5. 　　struct Student *p=pHead,*pNew;/*定义pNew指向新分配的空间*/
   ) K/ U3 o0 }$ h
6. 
   
7. 　　while(p&&p->iNumber!=number)
   
8. 
   
9. 　　p=p->next;/*使临时结点跟踪到要插入的位置(该实例必须存在学号为number的信息，插入其后，否则出错)*/
   ' a# P* x7 M6 \
10. 
    
11. 　　printf("姓名和学号：\n");
    - E- h! p, m: w2 y# [5 _% O+ x- k
12. 
    # U7 G+ s; a8 j9 |% K
13. 　　/*分配内存空间，返回该内存空间的地址*/
    
14. 
    : R$ k* o% R- F& S* p0 c
15. 　　pNew=(struct Student *)malloc(sizeof(struct Student));
    
16. 
    # O5 F1 ^( S9 p- ^' U
17. 　　scanf("%s",pNew->cName);
    
18. 
    2 {0 n( p* F  R7 {% o/ a) |# @$ K
19. 　　scanf("%d",&pNew->iNumber);
    
20. 
    3 ^0 @1 i7 }2 U1 \6 f# _+ t
21. 　　pNew->next=p->next;/*新结点指针指向原来的结点*/
    
22. 
    6 B! ?7 T* {! \4 l8 G$ u! Q
23. 　　p->next=pNew;/*头指针指向新结点*/
    
24. 
    
25. 　　iCount++;/*增加链表结点数量*/
    
26. 
    2 B& u7 b& I% ]* P
27. 　　return pHead;/*返回头指针*/
    - o5 A; E# p& n
28. 
    ) s/ F0 M7 J5 k7 {+ x# q
29. 　　}

复制代码

/ v& @# d6 {1 _1 g' i. v, a' V
; L, J; J0 W& M+ m" T
! c; |( J6 n/ w5 ]3 R* i$ N
, C: K% Q7 b- p6 x9 t; H　　删除函数：
- i4 N  |* }8 t9 I

8 A& O5 }' l# i" F

1. 　void Delete(struct Student *pHead,int number)
   
2. 
   - o3 w; k- n' `- W2 n5 y8 s
3. 　　{
   
4. 
   
5. 　　int i;
   " W! C; m) Z4 ^
6. 
   ( |4 b4 V. g+ O- I9 Z- x; [' q
7. 　　struct Student *pTemp;/*临时指针*/
   , l! s3 t- j; x. v, P
8. 
   / a( E$ B' S2 j: a' ?2 O
9. 　　struct Student *pPre;/*表示要删除结点前的结点*/
   
10. 
    0 U  `) z) `0 v. t
11. 　　pTemp=pHead;/*得到链表的头结点*/
    
12. 
    8 x, G0 U" c0 V3 S1 b
13. 　　pPre=pTemp;
    
14. 
    
15. 　　for(i=0;i
    
16. 
    
17. 　　{/*通过for循环使得Temp指向要删除的结点*/
    
18. 
    / E# ?( W( ]6 d& o7 s
19. 　　pPre=pTemp;
    
20. 
    
21. 　　pTemp=pTemp->next;
    2 |# J. w8 Q& Y. j7 m" V6 w
22. 
    + b: Z: `4 [' U; w8 ?
23. 　　}
    ) t& Y* J# B( {! o3 z$ J) ]# S
24. 
    
25. 　　pPre->next=pTemp->next;/*连接删除结点两边的结点*/
    # o' l8 [( E% D  K: Y+ E8 S) [% e
26. 
    3 b% g+ i$ Y2 H. ^
27. 　　free(pTemp);/*释放要删除结点的内存空间*/
    . Z0 |, Z2 a8 h: W
28. 
    , Z3 p, X7 g2 q
29. 　　iCount--;/*减少链表中的结点个数*/
    
30. 
    
31. 　　}

复制代码

1 O8 T2 C) S; B
8 O6 S7 k0 m& J. k8 K" l　　四、双向链表的概念
　　双向链表基于单链表。单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。
# z4 L8 H" Z2 G# p　　在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点的地址，一般称为右链域;一个存储直接前驱结点地址，一般称之为左链域。
　　双向链表结构示意图：


3 I' X. G5 ~3 j$ ], t& h4 ~

　　

6 M9 ]5 a2 q( d( J　　五、双向链表的建立与遍历
9 q7 E& ^9 L6 s/ D% |3 |: D! R　　双向链表的源码实战和单链表类似，只是多了第二个指针域的控制，这里直接贴上没有注释的源代码。


; N7 a# L7 z  t/ r

1. 　　#include #include
     i% w/ {9 V! {; J; J
2. 
   3 V  ~$ U2 _5 r7 N. B! {: l
3. 　　#include
   
4. 
   
5. 　　#define N 10
   
6. 
   
7. 　　typedef struct Node
   ) D. C5 ?& x8 v- P* c
8. 
   
9. 　　{
   
10. 
    
11. 　　char name[20];
    
12. 
    
13. 　　struct Node *llink,*rlink;
    * x. s) Z- y2 x3 h+ b' {
14. 
    
15. 　　}STUD;
    $ d2 n. E+ _+ \+ y" Y  w
16. 
    6 C( [6 `3 [- m6 |5 M2 m4 n+ o
17. 　　STUD *creat(int);void print(STUD *);
    
18. 
    
19. 　　int main()
    
20. 
    # @7 V  Z+ b% u! M8 e6 v
21. 　　{
    6 L! v6 Z% g3 N. t; M; c2 }
22. 
    
23. 　　int number;
    
24. 
    
25. 　　char studname[20];
    
26. 
    3 `9 h  `. p* M# ^
27. 　　STUD *head,*searchpoint;
    
28. 
    
29. 　　number=N;
    6 X8 w% K5 x, V2 R
30. 
    
31. 　　head=creat(number);
    - i+ G9 ]+ a  b8 f& O
32. 
    
33. 　　print(head);
    
34. 
    1 G$ F: k9 x: ?2 h! ?. L
35. 　　printf("请输入你要查找的人的姓名：");
    
36. 
    7 C5 }; M- J1 @" U& V, R
37. 　　scanf("%s",studname);
    % I/ D* z- T: _# G( u
38. 
    ( z7 U  b* J2 B! M& X
39. 　　searchpoint=search(head,studname);
    6 _# g+ ?+ V, v* u
40. 
    
41. 　　printf("你所要查找的人的姓名是：%s",*&searchpoint->name);
    * a& a( b7 \: Z0 ~' \
42. 
    
43. 　　return 0;
    
44. 
    0 d8 C  b; G* v0 N8 w6 `* v$ B
45. 　　}
    
46. 
    
47. 　　STUD *creat(int n)
    ) ~0 c* ?* y8 T
48. 
    
49. 　　{
    
50. 
    4 S4 a$ P; _) P5 M; n$ w% `7 H
51. 　　STUD *p,*h,*s;
    3 F3 _3 |4 v6 G3 m7 E
52. 
    * }$ x8 B+ P, }/ k
53. 　　int i;
    
54. 
    : b3 @8 f, O4 l) o) S" O9 S
55. 　　if((h=(STUD *)malloc(sizeof(STUD)))==NULL)
    
56. 
    
57. 　　{
    0 l8 K1 d6 m4 T* {8 K  P
58. 
    
59. 　　printf("不能分配内存空间");
    ( f8 i+ P+ k: G+ O- e
60. 
    
61. 　　exit(0);
    ; s/ h( M9 V0 g7 e) s2 @; Y
62. 
    
63. 　　}
    ' L" ~( K7 q% j; v5 V: d6 {- Q
64. 
    ! V1 V0 H# s3 [+ ^' l$ g
65. 　　h->name[0]='\0';
    
66. 
    + P. @) g+ A. G4 h, Z. i+ m2 ~' t
67. 　　h->llink=NULL;
    
68. 
    
69. 　　h->rlink=NULL;
    
70. 
    2 W% F' J; `/ `% ]6 K  n; j
71. 　　p=h;
    
72. 
    
73. 　　for(i=0;i
    
74. 
    
75. 　　{
    
76. 
    ( v- j' w; {8 M" ^
77. 　　if((s=(STUD *)malloc(sizeof(STUD)))==NULL)
    4 {* E1 ~) E6 N/ B
78. 
    5 W  P1 ]' C0 c1 B2 O+ @
79. 　　{
    
80. 
    6 P* Y0 ~1 v. L" v1 ]% t
81. 　　printf("不能分配内存空间");
    
82. 
    , ~" E3 l, R2 u/ H" C
83. 　　exit(0);
    
84. 
    6 k  X/ q% T2 P( Q0 `: g
85. 　　}
    
86. 
    
87. 　　p->rlink=s;
    
88. 
    
89. 　　printf("请输入第%d个人的姓名",i+1);
    
90. 
    $ {! ~0 m' m7 U
91. 　　scanf("%s",s->name);
    
92. 
    
93. 　　s->llink=p;
    
94. 
    6 k: W. b8 Z+ J/ x; j: Y
95. 　　s->rlink=NULL;
    
96. 
    3 [. J! w& t$ t
97. 　　p=s;
    
98. 
    ' \1 p+ f4 ^! f& K- P  n  v
99. 　　}
    8 ^) Q9 |( X- g' U  h( w
100. 
     
101. 　　h->llink=s;
     4 x' U# v; \# R
102. 
     
103. 　　p->rlink=h;
     : b! m: Z% i1 K
104. 
     8 s! [2 B( i* H
105. 　　return(h);
     % o* P! ]1 h; n0 S4 b, A1 M: T
106. 
     
107. 　　}void print(STUD *h)
     1 o( y( O! @3 ~' Y- m5 \
108. 
     
109. 　　{
     
110. 
     ; O' G* M% Z& b& u7 s4 e# R5 _7 v
111. 　　int n;
     
112. 
     - k1 e, B% X6 R) f2 x. i
113. 　　STUD *p;
     $ i& Q6 J( b! G4 K
114. 
     - @4 A3 r# m9 n0 L
115. 　　p=h->rlink;
     & T9 r' a3 X# _5 V6 k; v  N. J& b
116. 
     4 v. x2 p: l! A- x
117. 　　printf("数据信息为：\n");
     
118. 
     - r! v/ Y# @7 P2 y' J& l' n
119. 　　while(p!=h)
     
120. 
     , y9 W" B% I; @& Q' q# Z
121. 　　{
     7 |5 w+ b/ T6 A7 u8 h* H: a
122. 
     
123. 　　printf("%s ",&*(p->name));
     
124. 
     
125. 　　p=p->rlink;
       V/ i% O* U$ ~' y" Y, W
126. 
     
127. 　　}
     4 f- S. c8 P- M
128. 
     ! `) e1 x1 l1 C2 I" p7 y, ~
129. 　　printf("\n");
     
130. 
     
131. 　　}

复制代码

* z9 u1 y8 T9 P0 I6 s- }

/ C' a3 L  N$ `% b/ q, K
　　六、双向链表的元素查找
; a' b6 c# a" o- h3 B# c　　查找函数 STUD *search(STUD *,char *);
) ~3 f' a6 V9 S" A0 [" Y2 G
: O7 |. @/ I5 k+ {& G! W

1. 　　STUD *search(STUD *h,char *x)
   
2. 
   
3. 　　{
   # V& l! @/ V! V3 G$ p+ L% K
4. 
   2 G& I7 R) v( n" M/ `  r  u: v
5. 　　STUD *p;
   
6. 
   
7. 　　char *y;
   2 [  ?& d! t3 E
8. 
   $ I9 u8 s( X3 p  e$ ]3 [+ d
9. 　　p=h->rlink;
   8 p$ P3 @7 d  Z% \( r8 A( f
10. 
    * F4 y% _# O7 w% m
11. 　　while(p!=h)
    
12. 
    9 L+ d7 B( c% L
13. 　　{
    / V$ o9 L7 X3 C0 A% q& p) X& W! z! x
14. 
    ) U0 G7 @9 c9 H# l& ~
15. 　　y=p->name;
    
16. 
    
17. 　　if(strcmp(y,x)==0)
    
18. 
    
19. 　　return(p);
    4 R: q& S% |6 s; c* B/ r% k
20. 
    
21. 　　else
    7 P8 \' f$ j+ X
22. 
    & O- }" {; {0 ~. a9 Q
23. 　　p=p->rlink;
    * k' y/ K* @5 `4 Z
24. 
    # L- z1 y; a) D4 Q
25. 　　}
    
26. 
    ' }' h8 ]9 ?- g4 g. E+ f
27. 　　printf("没有查到该数据!");
    . C' U  S. S! A1 h1 _
28. 
    5 U. h# m' V7 f/ n5 \; i) c
29. 　　}

复制代码

- a9 T/ e) Z$ h0 N* \! a; s5 g

　　七、循环链表的概念
　　类似于单链表，循环链表也是一种链式的存储结构，由单链表演化而来。
　　单链表的最后一个结点的指针指向NULL，而循环链表的最后一个结点的指针指向链表头结点。
& u  f: A/ B' K7 c$ e　　这样头尾相连，形成了一个环形的数据链。
　　循环链表的建立不需要专门的头结点。
　　判断循环链表是否为尾结点时，只需判断该节点的指针域是否指向链表头节点。
　　八、合并两个链表的实例
& q. {# h  W& l, b　　建立两个带头节点的学生链表，每个节点包含学号、姓名和成绩，链表都按学号升序排列，将它们合并为一个链表仍按学号升序排列。
　　算法分析：
4 I% f/ e$ |! G% ?2 q. l5 m　　合并链表用merge()函数实现。函数中定义3个工作指针a、b、c，其中a、b分别指向La链表、Lb链表的当前结点，C指向合并后的链表尾结点。合并后链表的头结点共用La链表的头结点。
　　①合并前，先让a和b分别指向两个链表的第一个结点，c指向La链表的头结点。
. w: |" _2 y% z/ j, {0 a; e　　②合并时应该分3种情况讨论，即La和Lb都没有处理完;La没处理完，但Lb处理完毕;Lb没处理完，但La处理完毕。
7 c/ U' @. c: U1 q1 `2 |# \　　③合并过程中应始终将La和Lb链表中较小的一个链接在Lc中，方能保持有序。
3 B* M9 Y+ r( ^+ y& a" p
: L7 ]9 W+ z3 v


9 W4 H+ M; N$ C- v- }

1. 　void merge(struct stud *La,struct stud *Lb)
   
2. 
   ' A- K4 s1 [* m) y4 O$ E
3. 　　{
   0 i) \9 j6 t3 ?9 G. F& Y! X
4. 
   
5. 　　struct stud *a,*b,*c;
   
6. 
   
7. 　　c=La;
   , h& X) e" Y& Z! ?) r) z
8. 
   ' b6 D7 Q' x6 ^5 E2 H- p6 @0 }
9. 　　a=La->next;/* 合并前 */
   
10. 
    ( o- |, |3 }# x5 P+ A" `# o" E
11. 　　b=Lb->next;
    
12. 
    
13. 　　while(a!=NULL && b!=NULL)/* La和Lb都没处理完 */
    
14. 
    
15. 　　{
    & z8 Q- C. `+ `% c9 t5 L3 C7 c0 P
16. 
    
17. 　　if(a->num <= b->num)
    7 f. h+ y8 g' @7 e% o
18. 
    
19. 　　{
    % Y% A0 c) D5 X8 \( q4 T$ v3 @9 E
20. 
    8 L/ l8 C" B" u: |- F$ E* m
21. 　　c->next=a;
    
22. 
    : h& r% L) |* ?- x
23. 　　c=a;
    
24. 
    . a% ?( ~/ P1 {1 c' B; q
25. 　　a=a->next;
    * w4 {. Z% D1 H8 a! y! S7 A
26. 
    
27. 　　}
    . g6 S; }1 ?0 {
28. 
    
29. 　　else
    
30. 
    
31. 　　{
    3 _/ U$ K! S: j1 V, O
32. 
    
33. 　　c->next=b;
    ! c/ V& T) V: M) q& w  W5 U' O
34. 
    ! w. w: C* s; u% m# t, Y( ~
35. 　　c=b;
    + m; T) j& z3 C+ v% j% v  ^
36. 
    
37. 　　b=b->next;
    
38. 
    
39. 　　}
    5 f! N/ p5 j% _
40. 
    # n& ^! v& J  G2 p! L
41. 　　}
    ' ?7 R, `2 R. h( b
42. 
    
43. 　　if(a!=NULL)
    
44. 
    ' ^8 ]+ y. g; Y+ a8 `
45. 　　c->next=a;/* 若La没有处理完 */
    ; w4 ]& M; \  K: K. a* q
46. 
    ' w( N4 A- C! i; V  C. L8 V
47. 　　else
    
48. 
    0 l- W: S( Q! ~6 b/ c
49. 　　c->next=b;/* 若Lb没有处理完 */
    
50. 
    
51. 　　free(Lb); /* 释放Lb的头结点 */
    
52. 
    9 W1 E8 g: E. l* o0 {: L9 M* r* h
53. 　　}

复制代码

, B6 q  a/ _/ J4 G5 B& w
, O) w1 s8 X/ u. V1 C# A  p+ p
1 F8 Z6 E' G/ b( T