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

小样岁月

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

　　

+ N. T7 r' W! O, W2 w　　在链表中，每一个元素包含两个部分;数据部分和指针部分。数据部分用来存放元素所包含的数据，指针部分用来指向下一个元素。最后一个元素的指针指向NULL，表示指向的地址为空。整体用结构体来定义，指针部分定义为指向本结构体类型的指针类型。
( D" u! N1 }- w5 B, d, o& H/ v% s/ L　　静态链表需要数组来实现，即把线性表的元素存放在数组中。数组单元存放链表结点，结点的链域指向下一个元素的位置，即下一个元素所在数组单元的下标。这些元素可能在物理上是连续存放的，也有可能是不连续的，它们之间通过逻辑关系来连接——这就要涉及到数组长度定义的问题，实现无法预知定义多大的数组，动态链表随即出现。
' `/ C3 E; _% J" E( _　　动态链表指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点的数据，并建立起前后相连的关系。
　　二、单链表的建立与遍历
　　单链表中，每个结点只有一个指针，所有结点都是单线联系，除了末为结点指针为空外，每个结点的指针都指向下一个结点，一环一环形成一条线性链。
　　链表的创建过程：
8 E" F* B+ P! w4 N4 q

　　

2 Z; P/ ^+ h; }- P　　接下来在源码中建立并遍历输出一个单链表。
. Q( M/ \% I- d( ?

1 Z; E. p$ R* g2 \$ o

1. 　　#include
   " y9 y6 G( u! \7 w( f: K
2. 
   $ Y- s8 n1 M4 v. T  J0 m! V8 P; S
3. 　　#include
   $ a. [8 k# f$ M) y$ {* [/ w+ e
4. 
   % ~2 G, l; Y) B) l5 Q; }' b1 n* a
5. 　　#include
   4 E: N) X4 h) E5 F( C
6. 
   6 b, e1 o1 f2 {6 X& k/ F
7. 　　/*单向链表*/
   % N: [: m; ^+ u) p% p
8. 
   ; i# `' k  L% z/ b$ V
9. 　　struct Student/*建立学生信息结构体模型*/
   
10. 
    1 |9 N- Q' w1 H5 Q4 _8 V" ^( `
11. 　　{
    
12. 
      Y$ C5 r9 K# {) ^  f- ~3 A
13. 　　char cName[20];/*学生姓名*/
    $ S5 b# b/ ^* G( B& `! l
14. 
    ; r5 W" H0 g. V$ x  R" G4 H
15. 　　int iNumber;/*学生学号*/
    # W4 n6 g% f' F8 O( V! t) ]
16. 
    1 ^* N# f) L5 A8 n' o
17. 　　struct student *next;/*指向本结构体类型的指针类型*/
    
18. 
    
19. 　　};
    0 E' K4 j9 H* `
20. 
    
21. 　　int iCount;/*全局变量表示链表长度*/
    # y+ t8 Z, X$ N: E6 Y& w2 I
22. 
    & s9 d5 P# g+ n6 _9 D0 }" P
23. 　　struct Student *Create();/*创建链表函数声明*/
    ; U# B* x# f$ P% S0 _9 n! {- r
24. 
    
25. 　　void print(struct Student *);/*遍历输出链表函数声明*/
    
26. 
    
27. 　　int main()
    
28. 
    
29. 　　{
    0 z& X7 S9 f- |4 x4 {
30. 
    
31. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
    9 U0 R0 l5 A/ E/ c# R
32. 
    
33. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
    1 M9 A$ A" ^) ]! _9 x+ U7 ]/ ]0 ]
34. 
    # @1 O- ^, X( `* l6 O( p5 C
35. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
    - b+ K" b* ]$ }+ W# m9 b% E/ U3 Q. s
36. 
    * `& _- e4 R+ ^( b
37. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    
38. 
    8 d$ b8 T  A' h! f
39. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    2 G8 m0 v% o2 ^0 p* w0 k
40. 
    
41. 　　return 0;
    
42. 
    ' _4 k. v* j+ T$ k
43. 　　}
    ( t$ w# Z7 e* x5 m3 W
44. 
    0 b, Y7 \) G* |4 n: L* ^
45. 　　struct Student *Create()
    
46. 
    
47. 　　{
    / m& d9 Q, ?- E4 p
48. 
    
49. 　　struct Student *pHead=NULL;/*初始化链表，头指针为空*/
    
50. 
    
51. 　　struct Student *pEnd,*pNew;
    & B: @0 F' c& m: `- I
52. 
    
53. 　　iCount=0;/*初始化链表长度*/
    + E* Z% U- E7 A# u5 B! S! v7 W
54. 
    3 u; x/ _3 d( R# ]' n. L+ L
55. 　　pEnd=pNew=(struct Student *)malloc(sizeof(struct Student));/*动态开辟一个学生信息结构体类型大小的空间，使得pEnd和pNew同时指向该结构体空间*/
    
56. 
    ( |- W' d: h3 T) _# j
57. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    + K/ C6 q& f$ ]1 ^5 `
58. 
    
59. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    & N5 ]8 p* v8 K+ y8 c/ j$ o
60. 
    
61. 　　while(pNew->iNumber!=0)/*设定循环结束条件——学号不为0时*/
    
62. 
    ) u  S4 T/ U6 V9 ]
63. 　　{
    
64. 
    
65. 　　iCount++;/*链表长度+1，即学生信息个数+1*/
    4 \7 q& K& M( W. H2 f
66. 
    " F8 C) d( i" X% @
67. 　　if(iCount==1)/*如果链表长度刚刚加为1，执行*/
    ' n1 ^4 l' M8 H; u4 A
68. 
    
69. 　　{
    % t+ v' p$ Y; x* g9 R
70. 
    
71. 　　pNew->next=pHead;/*使指针指向为空*/
    
72. 
    
73. 　　pEnd=pNew;/*跟踪新加入的结点*/
    ) j, F/ `1 f; e5 [! b( l* f& I  F
74. 
    * j: A: D# |2 O8 B
75. 　　pHead=pNew;/*头结点指向首结点*/
    
76. 
    
77. 　　}
    
78. 
    
79. 　　else/*如果链表已经建立，长度大于等于2时，执行*/
    
80. 
    / L' Z$ h9 _' T$ f* \$ F' e" V
81. 　　{
    
82. 
    3 i- V! _( ]6 h# P$ s" A
83. 　　pNew->next=NULL;/*新结点的指针为空*/
    
84. 
    
85. 　　pEnd->next=pNew;/*原来的结点指向新结点*/
    
86. 
    
87. 　　pEnd=pNew;/*pEnd指向新结点*/
    
88. 
    
89. 　　}
    ) U4 j% o" r$ q* [
90. 
    4 a" t/ w2 S" ~- N$ t! I# I
91. 　　pNew=(struct Student *)malloc(sizeof(struct Student));/*再次分配结点的内存空间*/
    
92. 
    
93. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    ! s; \- Z/ d2 P. K
94. 
    
95. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    
96. 
    
97. 　　}
    2 Y/ B$ b9 L6 W" H/ c. G) `
98. 
    " o9 f) r5 A' I
99. 　　free(pNew);/*释放结点空间*/
    " n7 K8 \& l) o! |( K
100. 
     
101. 　　return pHead;/*返回创建出的头指针*/
     + d( F% T$ K7 ~: z) K1 h* y' N
102. 
     ) q: v3 X1 g5 A7 J: Y9 L& ?' A
103. 　　}
     ! O4 ^$ ?5 H; S& C5 P
104. 
     
105. 　　void print(struct Student *pHead)
     8 F! ^. F: U6 |! j1 B! z
106. 
     5 ^% E& I5 W+ ^1 d6 }& p
107. 　　{
     
108. 
     ( ^% N7 [/ ?; l  m) s
109. 　　struct Student *pTemp;/*定义指向一个学生信息结构体类型的临时指针*/
     , Z8 R7 W! v5 v$ ^! V3 E
110. 
     0 I" b5 I( x6 L( g
111. 　　int iIndex=1;/*定义并出事哈变量iIndex，用来标识第几个学生(信息)*/
     
112. 
     1 J3 T  S; X& {$ b5 B! j5 Y9 p
113. 　　printf("总共%d个学生(信息)：\n",iCount);
     8 w: o7 y) ]- e6 N' L: V+ f" j
114. 
       a7 i! ?' d2 l5 b$ T1 a
115. 　　pTemp=pHead;/*指针得到首结点的地址*/
     1 \$ M7 ~- _) D9 {- y# i& X
116. 
     # |( C7 l( L, R* ?' y
117. 　　while(pTemp!=NULL)/*当临时指针不指向NULL时*/
     
118. 
     
119. 　　{
     
120. 
     
121. 　　printf("第%d个学生信息：\n",iIndex);
     
122. 
     , z$ w5 X; P' i% R* y4 X) T
123. 　　printf("姓名：%s",pTemp->cName); /*输出姓名*/
     . [% h8 f8 P- r9 P& l: [
124. 
     
125. 　　printf("学号：%d",pTemp->iNumber);/*输出学号*/
     4 O' `# r) m, y% w. y2 t) A3 g0 Z
126. 
     
127. 　　pTemp=pTemp->next;/*移动临时指针到下一个结点*/
     ) T+ U; @, c; a% o4 V4 i
128. 
     
129. 　　iIndex++;/*进行自加运算*/
     
130. 
     
131. 　　}
     
132. 
     
133. 　　}

复制代码

: f& z2 D, v! W/ U8 k

& v: D" w! T5 k2 s) p# @3 f　　三、单链表的插入与删除
　　在本实例中，插入时根据传递来的学号，插入到其后。
　　删除时根据其所在链表的位置，删除并释放该空间。
2 K" g& E2 T1 K　　主函数增加如下：

6 a+ M! Y# O# ]8 a' f6 X# X
5 x' B" `) U, s/ X' i

1. 　　int main()
   
2. 
   & ]9 |* f. Y+ S" k, u! \
3. 　　{
   
4. 
   1 H% ~. g: A4 I" X: H1 k/ n  z
5. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
   ! c# r4 h, H9 t) M
6. 
   . y0 _) i. ?0 Z+ ~. u% P$ B) ^! U
7. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
   
8. 
   4 Y- k, O2 G4 f* C: n9 ^
9. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
   
10. 
    
11. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    
12. 
    , j7 O' `. x* q5 y$ d  C
13. 　　pHead=Insert(pHead,insert_n);/*将指针pHead和要插入的结点数传递给插入函数*/
    
14. 
    
15. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
16. 
    
17. 　　Delete(pHead,delete_n);/*将指针pHead和要删除的结点数传递给删除函数*/
    
18. 
    
19. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
20. 
    
21. 　　return 0;
    
22. 
    
23. 　　}

复制代码

3 O2 U/ N  V" I- A( b


5 L  r  x9 {7 D8 c9 m1 {　　插入函数：
; f- l0 M9 ~# P0 y

5 ^% }3 G# @$ X8 h6 @$ Z

1. 　　struct Student *Insert(struct Student *pHead,int number)
   
2. 
   
3. 　　{
   
4. 
   . @! j, f# y6 N7 L
5. 　　struct Student *p=pHead,*pNew;/*定义pNew指向新分配的空间*/
   : Q, W" b& I1 \- Z! k
6. 
   & T" B' d! a5 {. f2 O  y& X
7. 　　while(p&&p->iNumber!=number)
   1 o+ A% H# q' U% l6 ~
8. 
   
9. 　　p=p->next;/*使临时结点跟踪到要插入的位置(该实例必须存在学号为number的信息，插入其后，否则出错)*/
   ) u( S$ C3 P; f/ O
10. 
    
11. 　　printf("姓名和学号：\n");
    9 F! E/ J) d" h2 _0 I
12. 
    6 R  i! E2 _$ l5 l; j$ U3 ~6 q
13. 　　/*分配内存空间，返回该内存空间的地址*/
    
14. 
    
15. 　　pNew=(struct Student *)malloc(sizeof(struct Student));
    
16. 
    , N" E, U1 S8 m& ]
17. 　　scanf("%s",pNew->cName);
    
18. 
    0 g( o9 c% D, e, F. Q$ o# c
19. 　　scanf("%d",&pNew->iNumber);
    
20. 
    9 o1 i" ^* Y4 m% h& W5 {3 `
21. 　　pNew->next=p->next;/*新结点指针指向原来的结点*/
    
22. 
    
23. 　　p->next=pNew;/*头指针指向新结点*/
    
24. 
    
25. 　　iCount++;/*增加链表结点数量*/
    
26. 
    4 E& q# q% U/ m7 N" Q8 L
27. 　　return pHead;/*返回头指针*/
    & U5 t% W+ _# |/ U# l1 {1 s' c0 u) W
28. 
    
29. 　　}

复制代码

: l, Y( g! Z7 c& [( \, n$ [' a


　　删除函数：
7 r4 U2 L8 X3 G1 U
/ J/ E/ L* s0 b

$ d7 i9 k$ i8 s& o7 t9 t# V; h; G
# L/ o5 o( q$ i: J) v# j6 ?

1. 　void Delete(struct Student *pHead,int number)
   
2. 
   2 W+ I5 v, L- v- E
3. 　　{
   : M* ~4 C3 u8 A8 l+ s' g* m
4. 
   # m1 |0 M2 U* K, G- c
5. 　　int i;
   ; `' n' F% ^& x$ i+ t9 s' [
6. 
   4 t, s3 {; X; r' T1 @! M4 m7 w
7. 　　struct Student *pTemp;/*临时指针*/
   / _2 T. s3 j9 p8 s  N) g3 ^, U
8. 
   - j) t" X3 s, p, E7 u8 T- \$ X0 }
9. 　　struct Student *pPre;/*表示要删除结点前的结点*/
   ' \& ?0 T$ W( e1 T" U1 g
10. 
    
11. 　　pTemp=pHead;/*得到链表的头结点*/
    
12. 
      X8 s% j5 O6 m) Q; e, D
13. 　　pPre=pTemp;
    , a4 C: ]- u- {; F
14. 
    
15. 　　for(i=0;i
    3 v. y  H& v( o  {6 o
16. 
    
17. 　　{/*通过for循环使得Temp指向要删除的结点*/
    & Z! R( h1 q+ M9 ^( {7 g) C* o5 a
18. 
    
19. 　　pPre=pTemp;
    
20. 
    $ V  I+ |# I, p& t
21. 　　pTemp=pTemp->next;
    
22. 
    ) a* e: r# v! O& s$ J) ~( |
23. 　　}
    0 v' l9 O# i2 b' j' z9 m& _
24. 
    " L, p7 q- N1 B! g
25. 　　pPre->next=pTemp->next;/*连接删除结点两边的结点*/
    
26. 
    
27. 　　free(pTemp);/*释放要删除结点的内存空间*/
    
28. 
    
29. 　　iCount--;/*减少链表中的结点个数*/
    : r. N. K: w5 b0 h; y  p
30. 
    
31. 　　}

复制代码

- T" G9 L+ X% T4 Y/ b
9 o4 p- j1 D) v8 y　　四、双向链表的概念
6 h6 C  L; W6 W& c0 l6 Z8 P　　双向链表基于单链表。单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。
　　在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点的地址，一般称为右链域;一个存储直接前驱结点地址，一般称之为左链域。
　　双向链表结构示意图：

　　

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

1. 　　#include #include
   
2. 
   ) R1 @8 ]: n$ ]
3. 　　#include
   
4. 
   
5. 　　#define N 10
   
6. 
   " ^( t: b% [! i# F
7. 　　typedef struct Node
   
8. 
   
9. 　　{
   ( n5 a7 p3 H0 I) t
10. 
    6 l- {& a6 [$ L
11. 　　char name[20];
    
12. 
    
13. 　　struct Node *llink,*rlink;
    
14. 
    9 \: D* W4 _, s4 A
15. 　　}STUD;
    ) E) I+ n9 r8 I1 [# `" z8 O
16. 
    , j- y$ E! n2 |) @
17. 　　STUD *creat(int);void print(STUD *);
    6 D4 ?' V' K5 q
18. 
    % ?+ I! D8 `2 |, X) Z
19. 　　int main()
    8 _/ v" h  M) b3 ]& P/ i* I
20. 
    
21. 　　{
    
22. 
    
23. 　　int number;
    
24. 
    3 N+ p  F7 y1 F4 B& ?. ?
25. 　　char studname[20];
    8 y% v. D8 C% G$ o
26. 
    5 g/ ~$ {3 t1 O" i. Z, h+ D
27. 　　STUD *head,*searchpoint;
    
28. 
    
29. 　　number=N;
    
30. 
    ' n4 O5 A' p/ R; ~, P
31. 　　head=creat(number);
    
32. 
    5 P1 a0 q3 v  _( s/ M- l& M) g
33. 　　print(head);
    & n$ r1 }* Z2 [: t" b* E" _1 \
34. 
    
35. 　　printf("请输入你要查找的人的姓名：");
    
36. 
    
37. 　　scanf("%s",studname);
    7 Q# w5 g8 s/ u8 z0 i4 s
38. 
    
39. 　　searchpoint=search(head,studname);
    : t% q) S% o6 Z1 V& v7 N
40. 
    " S& ?2 @7 t& M" V1 p
41. 　　printf("你所要查找的人的姓名是：%s",*&searchpoint->name);
    . h1 J6 Q6 H; v9 q5 R  w) p! x! w
42. 
    
43. 　　return 0;
    
44. 
    ' r5 [8 q) _* t
45. 　　}
    $ w2 ]- A  x' H: ~+ l7 b
46. 
      {( O0 z7 I1 w! k+ e
47. 　　STUD *creat(int n)
    1 W' @; h5 D# u5 N: g, h
48. 
    ( |' Y& g$ b7 Z2 l/ t) ^0 y( X. i
49. 　　{
    ! Z: C2 Q5 K% |/ @7 o
50. 
    
51. 　　STUD *p,*h,*s;
    
52. 
    3 J- q9 w2 E8 s; w; Z  I/ J
53. 　　int i;
    
54. 
    & O% h3 @+ K2 S  |* M2 j/ A' q4 Y
55. 　　if((h=(STUD *)malloc(sizeof(STUD)))==NULL)
    0 W9 }1 m3 x: [4 A. j4 `; |+ a) A
56. 
    9 h- S6 I3 D( k0 n$ n! {, ?) ]
57. 　　{
    8 R& O, L4 \3 n. X8 l
58. 
    
59. 　　printf("不能分配内存空间");
    
60. 
    % b( |3 Y! Y3 H' g
61. 　　exit(0);
    
62. 
    & V9 Y" P- H- ?" |
63. 　　}
    * }( h. I. }* k1 W" e6 b, g4 `% J
64. 
    9 g$ l6 f2 H" R0 F0 G5 H
65. 　　h->name[0]='\0';
    % p% N1 O2 ^5 R3 [8 D. \
66. 
    
67. 　　h->llink=NULL;
    5 H7 z7 P9 H5 l2 O5 `& i3 x1 d4 a
68. 
    4 a! s# G, b! V$ ~1 y
69. 　　h->rlink=NULL;
    - o+ d/ L. J8 w# }) V
70. 
      W% k. I3 F2 h( q
71. 　　p=h;
    , w! Z, G5 Y/ i5 Q/ D: i
72. 
      A+ \! \4 Z; x* n5 E% @9 J
73. 　　for(i=0;i
    
74. 
    ' j6 l* X/ p) Q2 j% }$ k8 p/ m2 C
75. 　　{
    2 w! R8 F5 e2 K- S! e
76. 
    2 V" f) R& F+ Z' q$ r9 d  A3 _
77. 　　if((s=(STUD *)malloc(sizeof(STUD)))==NULL)
    6 @+ w  w) y/ D) f( v6 ^0 e% x  H
78. 
    
79. 　　{
    
80. 
    ' }0 k6 T' A% f+ c
81. 　　printf("不能分配内存空间");
    
82. 
    
83. 　　exit(0);
    1 o" r6 O; j$ n4 e) W
84. 
    
85. 　　}
    . U5 M" ]! N$ T0 t0 V; p
86. 
    & {3 J5 {2 y) ]* G) u9 w# }
87. 　　p->rlink=s;
      z: F8 F6 w- s) J- s: P
88. 
    + Z# G! N$ T8 E. U! j  h) o
89. 　　printf("请输入第%d个人的姓名",i+1);
    ' o' J# M' Z. T- W9 L4 s3 |
90. 
    # G1 d5 z7 o: L6 z
91. 　　scanf("%s",s->name);
    
92. 
    : W6 p5 Q" Q# h. u0 ]1 A
93. 　　s->llink=p;
    
94. 
    * x+ W& ]2 \; N5 W0 a* x
95. 　　s->rlink=NULL;
    
96. 
    " U2 R2 Q& A( Q& K; N
97. 　　p=s;
    
98. 
    
99. 　　}
    : S/ l. O1 n% v& C% E  M
100. 
     
101. 　　h->llink=s;
     2 t. p- [8 F% P) S
102. 
     2 S3 G" P- y+ A' b
103. 　　p->rlink=h;
     1 W( T5 T" R  o: N' `6 L  `. x
104. 
     - }% `1 Q. w' @
105. 　　return(h);
     8 h; D& d% o' C, ]0 `7 q5 u
106. 
     
107. 　　}void print(STUD *h)
     9 a  _6 J9 S" D- S# t! ^
108. 
     ( C3 G# M5 x6 T4 Y9 j8 r+ r! d& ?
109. 　　{
     
110. 
     6 Z5 n9 R! ]1 S# R3 l, c& @
111. 　　int n;
     9 Y3 H" e) D2 q3 A' p
112. 
     
113. 　　STUD *p;
     
114. 
     , Q% }: n% I8 C9 v
115. 　　p=h->rlink;
     
116. 
     & \( K$ V2 c& s6 u2 r
117. 　　printf("数据信息为：\n");
     
118. 
     9 `4 P% R* T7 Q" O
119. 　　while(p!=h)
     
120. 
     4 b5 e- K$ m+ s5 Z  Y. V9 q9 i
121. 　　{
     
122. 
     
123. 　　printf("%s ",&*(p->name));
     ' v- T# A6 m# d' ~
124. 
     
125. 　　p=p->rlink;
     
126. 
     ; A! o5 t7 R/ k  K
127. 　　}
     
128. 
     + T. _7 a/ V7 H; }5 m1 R! \3 C( Y
129. 　　printf("\n");
     . v! r* E! L: |4 m
130. 
     
131. 　　}

复制代码

: ~- ~" ]+ z; T" Q& J* |; c8 l. \
4 ]% V) J# M" u0 h# C) t* S6 d
7 C; e. b( a2 ]/ K* x( [+ t5 N3 `6 T
　　六、双向链表的元素查找
　　查找函数 STUD *search(STUD *,char *);



$ C3 M6 H6 M( ~+ k- q

1. 　　STUD *search(STUD *h,char *x)
   # ]8 A7 p; y* b+ @6 h- g% B
2. 
   
3. 　　{
   1 n% b3 l; p8 P0 k; H
4. 
   
5. 　　STUD *p;
   
6. 
   
7. 　　char *y;
   
8. 
   
9. 　　p=h->rlink;
   
10. 
    
11. 　　while(p!=h)
    
12. 
    
13. 　　{
    
14. 
    
15. 　　y=p->name;
    
16. 
    
17. 　　if(strcmp(y,x)==0)
    
18. 
    
19. 　　return(p);
    : E4 D* `. J& T
20. 
    
21. 　　else
    
22. 
    
23. 　　p=p->rlink;
    * V  T# o: _" }: G
24. 
    
25. 　　}
    
26. 
    
27. 　　printf("没有查到该数据!");
    
28. 
    
29. 　　}

复制代码

4 z( O* I5 V1 n6 v6 t
8 h0 q9 V  B# [- I
　　七、循环链表的概念
) l4 k& y% P7 J- w: r3 z　　类似于单链表，循环链表也是一种链式的存储结构，由单链表演化而来。
　　单链表的最后一个结点的指针指向NULL，而循环链表的最后一个结点的指针指向链表头结点。
　　这样头尾相连，形成了一个环形的数据链。
# L: |- _8 m- @　　循环链表的建立不需要专门的头结点。
# |) w7 r* r2 l- f  p　　判断循环链表是否为尾结点时，只需判断该节点的指针域是否指向链表头节点。
/ C2 U1 y! l1 G# C6 Y- Z% \1 P　　八、合并两个链表的实例
　　建立两个带头节点的学生链表，每个节点包含学号、姓名和成绩，链表都按学号升序排列，将它们合并为一个链表仍按学号升序排列。
/ K/ `2 V7 h8 J1 q, Z  g8 a　　算法分析：
% O& [6 g8 q# \$ m　　合并链表用merge()函数实现。函数中定义3个工作指针a、b、c，其中a、b分别指向La链表、Lb链表的当前结点，C指向合并后的链表尾结点。合并后链表的头结点共用La链表的头结点。
. g5 ^  S: \: m9 o　　①合并前，先让a和b分别指向两个链表的第一个结点，c指向La链表的头结点。
7 R: m( F. _+ S1 D4 I( l　　②合并时应该分3种情况讨论，即La和Lb都没有处理完;La没处理完，但Lb处理完毕;Lb没处理完，但La处理完毕。
　　③合并过程中应始终将La和Lb链表中较小的一个链接在Lc中，方能保持有序。



; g  G" R& c5 h, [

1. 　void merge(struct stud *La,struct stud *Lb)
   
2. 
   $ i5 g3 A1 E5 t- w
3. 　　{
   
4. 
   
5. 　　struct stud *a,*b,*c;
   
6. 
   
7. 　　c=La;
   
8. 
   , ~) R( ^" c/ V4 L' f
9. 　　a=La->next;/* 合并前 */
   
10. 
    3 d3 `! O- V7 o9 p% O
11. 　　b=Lb->next;
    
12. 
    
13. 　　while(a!=NULL && b!=NULL)/* La和Lb都没处理完 */
    
14. 
    7 y# o( z4 W1 c% L7 s5 T7 G: \& q
15. 　　{
    ( q: x3 R! }( V% k2 ~$ ]) E
16. 
    
17. 　　if(a->num <= b->num)
    ) u3 Z2 S2 J8 W+ |7 q' R% k
18. 
    
19. 　　{
    
20. 
    & j0 V+ b7 Q# g( \
21. 　　c->next=a;
    9 b' ]" x& g# ^# L7 b
22. 
    
23. 　　c=a;
    
24. 
    + F% Z: y9 X9 s2 F# t, W1 j9 X0 n
25. 　　a=a->next;
    
26. 
    9 y; M% ^8 @( p& d
27. 　　}
    
28. 
    
29. 　　else
    
30. 
    6 B3 `8 S- x. I& ]
31. 　　{
    
32. 
    
33. 　　c->next=b;
    ( P. p: R& `- M- [; T8 C+ r
34. 
    . \8 s+ i0 B; r$ _
35. 　　c=b;
    
36. 
    $ s2 W3 c1 C7 W3 P" L/ b5 y3 S
37. 　　b=b->next;
    
38. 
    
39. 　　}
    
40. 
    . E0 x) p/ t. n" n1 G
41. 　　}
    
42. 
    9 _2 M+ |* t- t- d- p4 i7 \
43. 　　if(a!=NULL)
    
44. 
    
45. 　　c->next=a;/* 若La没有处理完 */
    
46. 
    
47. 　　else
    
48. 
    
49. 　　c->next=b;/* 若Lb没有处理完 */
    
50. 
    ; ?& W& T3 I, `: u) i/ w3 k% m
51. 　　free(Lb); /* 释放Lb的头结点 */
    
52. 
    " C! {, \: f& d7 A& _+ `* O
53. 　　}

复制代码

: f7 H, T! Y- Q
9 _( f% C, c" b5 ^" f
1 _' P& k* ^2 Z$ T