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

小样岁月

　　最近临近期末的C语言课程设计比平时练习作业一下难了不止一个档次，第一次接触到了C语言的框架开发，了解了View(界面层)、Service(业务逻辑层)、Persistence(持久化层)的分离和耦合，一种面向过程的MVC的感觉。
* p) }& S% r; ]' a9 y　　而这一切的基础就在于对链表的创建、删除、输出、写入文件、从文件读出......
7 i) K& q7 o9 C1 C2 U; y　　本篇文章在于巩固链表的基础知识(整理自《C语言程序设计教程--人民邮电出版社》第十章——指针与链表)，只对链表的概念及增删改查作出探讨，欢迎指教。
$ ^  L3 v1 g( P! o( T  T8 @　　一、链表结构和静态/动态链表
　　二、单链表的建立与遍历
　　三、单链表的插入与删除
　　四、双向链表的概念
- w( g2 P9 e# b/ B0 G9 y　　五、双向链表的建立与遍历
5 V9 E9 O0 R/ f1 c  k9 k　　六、双向链表的元素查找
# {7 O2 a2 j4 Y+ `. K　　七、循环链表的概念
: C3 A! a, q" H　　八、合并两个链表的实例
- \+ E1 c* C, P& W+ R  ]　　九、链表实战
　　拓展思维、拉到最后去看看 (•̀ᴗ•́)و ̑̑
9 b5 F( B% x. J　　一、链表结构和静态/动态链表
1 S& w; F, V- P' U. f: z% i　　链表是一种常见的数据结构——与数组不同的是：
( g4 M# n% n0 O8 a5 o　　1.数组首先需要在定义时声明数组大小，如果像这个数组中加入的元素个数超过了数组的长度时，便不能正确保存所有内容;链表可以根据大小需要进行拓展。
$ m% B0 W* w' R9 x3 d5 `" n% Q　　2.其次数组是同一数据类型的元素集合，在内存中是按一定顺序连续排列存放的;链表常用malloc等函数动态随机分配空间，用指针相连。
% \, t* U% A8 t: e- D. `! i; O　　链表结构示意图如下所示：
; V" t2 s# i7 ~

　　

6 V. h+ e0 G1 h! t0 D5 A　　在链表中，每一个元素包含两个部分;数据部分和指针部分。数据部分用来存放元素所包含的数据，指针部分用来指向下一个元素。最后一个元素的指针指向NULL，表示指向的地址为空。整体用结构体来定义，指针部分定义为指向本结构体类型的指针类型。
2 b; \$ i+ p: ~+ d( R- v& \, D　　静态链表需要数组来实现，即把线性表的元素存放在数组中。数组单元存放链表结点，结点的链域指向下一个元素的位置，即下一个元素所在数组单元的下标。这些元素可能在物理上是连续存放的，也有可能是不连续的，它们之间通过逻辑关系来连接——这就要涉及到数组长度定义的问题，实现无法预知定义多大的数组，动态链表随即出现。
　　动态链表指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点的数据，并建立起前后相连的关系。
: o7 `" J6 r9 l8 e　　二、单链表的建立与遍历
+ [$ C4 y* w- _; N　　单链表中，每个结点只有一个指针，所有结点都是单线联系，除了末为结点指针为空外，每个结点的指针都指向下一个结点，一环一环形成一条线性链。
　　链表的创建过程：
2 ]3 |" A- L2 M8 K6 R  ^! }$ A

　　

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

: q' {5 e) H" U+ v2 D

1. 　　#include
     j( k. U0 r/ f: K% `& R7 A
2. 
   
3. 　　#include
   
4. 
   
5. 　　#include
   
6. 
   ' `- a- O  _5 S  L
7. 　　/*单向链表*/
   
8. 
   7 y2 U# U$ e0 L6 H4 r' m! y/ a0 v
9. 　　struct Student/*建立学生信息结构体模型*/
   ; n4 z$ W( S) W4 I1 C
10. 
    6 L( S$ @6 u7 s+ w. J7 s) _: x
11. 　　{
    
12. 
    : e6 i2 f  f- D8 \, T- s) v4 w9 T
13. 　　char cName[20];/*学生姓名*/
    
14. 
    8 S" k! ?* n; h  F
15. 　　int iNumber;/*学生学号*/
    
16. 
    
17. 　　struct student *next;/*指向本结构体类型的指针类型*/
    
18. 
    
19. 　　};
    , l" |+ Q, z0 [3 L6 J
20. 
    " f3 z; {7 [: o; ?8 O" e
21. 　　int iCount;/*全局变量表示链表长度*/
    
22. 
    1 e& w. C& w" G5 q
23. 　　struct Student *Create();/*创建链表函数声明*/
    * c. ?7 Q5 H8 ]) m
24. 
    
25. 　　void print(struct Student *);/*遍历输出链表函数声明*/
    
26. 
    , G6 l+ j" G, q- ?) }7 W1 |
27. 　　int main()
    
28. 
    
29. 　　{
    - y, ^% k4 b  f  s7 o( ^
30. 
    % R( }' |$ m, R" \9 T) R8 \
31. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
    
32. 
    1 @& I- F! q( J) N
33. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
    
34. 
    ' k& f/ ]/ C8 q' R8 |0 m+ U- t
35. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
    
36. 
    1 w# u. C+ J# e) R5 M; \+ E4 W3 I
37. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    
38. 
    2 ]! v. v& m; @. ~
39. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
40. 
    
41. 　　return 0;
    
42. 
    
43. 　　}
    : C4 |4 c8 R6 B0 s8 {7 s1 y
44. 
    " G8 G8 @9 [% u4 p
45. 　　struct Student *Create()
    5 S- d5 e, z2 K! B) M
46. 
    ; m% c  Z# l" w# T' a$ u1 D
47. 　　{
    $ q# P) h! ^6 j
48. 
    . u) f+ n* z6 V
49. 　　struct Student *pHead=NULL;/*初始化链表，头指针为空*/
    
50. 
    / D/ X! _. o* @1 T
51. 　　struct Student *pEnd,*pNew;
    
52. 
    ) R; B' v: [9 a+ V
53. 　　iCount=0;/*初始化链表长度*/
    
54. 
    
55. 　　pEnd=pNew=(struct Student *)malloc(sizeof(struct Student));/*动态开辟一个学生信息结构体类型大小的空间，使得pEnd和pNew同时指向该结构体空间*/
    
56. 
    
57. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    - D; R: Z% Y9 R" j/ a
58. 
    
59. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    0 O; N3 ]1 d& I- s/ X: M
60. 
    
61. 　　while(pNew->iNumber!=0)/*设定循环结束条件——学号不为0时*/
    ' P( g6 L' @" W9 S
62. 
    
63. 　　{
    , f. D4 h& M$ ^- z5 e% L6 j5 _
64. 
    4 M# @, m3 ]4 t) K
65. 　　iCount++;/*链表长度+1，即学生信息个数+1*/
    
66. 
    
67. 　　if(iCount==1)/*如果链表长度刚刚加为1，执行*/
    
68. 
    , y6 [. V, y; i
69. 　　{
    
70. 
    
71. 　　pNew->next=pHead;/*使指针指向为空*/
    
72. 
    
73. 　　pEnd=pNew;/*跟踪新加入的结点*/
    ! q: {$ y; E2 o/ s
74. 
    
75. 　　pHead=pNew;/*头结点指向首结点*/
    
76. 
    
77. 　　}
    9 ]$ G4 A9 @1 Q0 N6 C( s3 S$ T
78. 
    9 S& r6 W4 k! A; }+ ~9 Q
79. 　　else/*如果链表已经建立，长度大于等于2时，执行*/
    
80. 
    
81. 　　{
    
82. 
    
83. 　　pNew->next=NULL;/*新结点的指针为空*/
    
84. 
    
85. 　　pEnd->next=pNew;/*原来的结点指向新结点*/
    ' c6 H; R" F0 ]# [( u
86. 
    6 z3 S2 Z, D6 }4 H6 Y  m! L
87. 　　pEnd=pNew;/*pEnd指向新结点*/
    
88. 
    
89. 　　}
    + l4 s' }, p! K3 v7 \. H. \
90. 
    
91. 　　pNew=(struct Student *)malloc(sizeof(struct Student));/*再次分配结点的内存空间*/
    9 ^5 E+ |- W% P7 A7 W) V. C7 U
92. 
    0 W+ y! o; H  n1 S: U, w5 S! r
93. 　　scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    
94. 
    
95. 　　scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/
    
96. 
    0 J: h/ v4 b: @+ f/ k
97. 　　}
    
98. 
    , }! Q* U# Z7 T+ S. V5 R
99. 　　free(pNew);/*释放结点空间*/
    
100. 
     ! r" q! G8 G3 Y. k
101. 　　return pHead;/*返回创建出的头指针*/
     % C3 S7 r) _2 T( M2 x
102. 
     ! h  {. U; D2 [% r% d1 m
103. 　　}
     
104. 
     8 @$ m, k% P) d. d% w, y
105. 　　void print(struct Student *pHead)
     ; n4 Z4 y9 `7 S' B9 h( ~: @
106. 
     
107. 　　{
     ( D; E% m5 l* [' X
108. 
     % f# p( D, U7 B1 `
109. 　　struct Student *pTemp;/*定义指向一个学生信息结构体类型的临时指针*/
     
110. 
     ( A8 N; Q. c- z9 q% H
111. 　　int iIndex=1;/*定义并出事哈变量iIndex，用来标识第几个学生(信息)*/
     
112. 
     
113. 　　printf("总共%d个学生(信息)：\n",iCount);
     % i% G: ~5 r1 [
114. 
     
115. 　　pTemp=pHead;/*指针得到首结点的地址*/
     . z1 w# d( G- ~3 `) z/ t
116. 
     * w3 a# A' t2 ^! w7 D
117. 　　while(pTemp!=NULL)/*当临时指针不指向NULL时*/
     
118. 
     
119. 　　{
     ' z# J! Z, B& D  q* k& V
120. 
     
121. 　　printf("第%d个学生信息：\n",iIndex);
     
122. 
     
123. 　　printf("姓名：%s",pTemp->cName); /*输出姓名*/
     
124. 
     
125. 　　printf("学号：%d",pTemp->iNumber);/*输出学号*/
     % ~/ w( \! R7 H' s5 j; }$ v
126. 
     ! |$ v" O  P5 i: `$ {$ w3 O2 c% p+ I
127. 　　pTemp=pTemp->next;/*移动临时指针到下一个结点*/
     
128. 
     , K" r. [5 |$ r) E
129. 　　iIndex++;/*进行自加运算*/
     & n8 F! ~+ m1 z+ ]2 C
130. 
     6 d2 ]: B5 g# b" a+ R
131. 　　}
     
132. 
     . V; ]) N* O* d6 d2 |2 L
133. 　　}

复制代码

# k( r7 U5 y3 x( c  R- X

2 p* X5 G  t5 u; `" |　　三、单链表的插入与删除
　　在本实例中，插入时根据传递来的学号，插入到其后。
　　删除时根据其所在链表的位置，删除并释放该空间。
　　主函数增加如下：
( K! q9 @- m5 k3 H0 X" ^6 C( H

1. 　　int main()
   
2. 
   # j  m, J% |" X$ x3 x( K; V
3. 　　{
   
4. 
   
5. 　　int insert_n=2;/*定义并初始化要插入的结点号*/
   
6. 
   
7. 　　int delete_n=2;/*定义并初始化要删除的结点号*/
   
8. 
   
9. 　　struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
   0 z! o; G; r+ K: e, B
10. 
    
11. 　　pHead=Create();/*创建链表，返回链表的头指针给pHead*/
    ) M+ A/ M4 B  @: m# T5 G
12. 
    
13. 　　pHead=Insert(pHead,insert_n);/*将指针pHead和要插入的结点数传递给插入函数*/
      m. d1 L( r9 u0 A- r
14. 
    
15. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    + K9 N" o$ G' E0 i) b
16. 
    , S. ^+ j- {. q6 j# [2 P
17. 　　Delete(pHead,delete_n);/*将指针pHead和要删除的结点数传递给删除函数*/
    * \& W0 p& g' E- _5 ~
18. 
    
19. 　　print(pHead);/*将指针pHead传入输出函数遍历输出*/
    
20. 
    2 |+ ]$ P( t0 C8 t& R
21. 　　return 0;
    2 v+ N6 D# b" i4 `
22. 
    : ]- u$ }; a  t2 P; o- w
23. 　　}

复制代码

3 O  q" F9 J1 e3 l. b6 H  h
: R7 |- i- C2 J7 v　　插入函数：

! Z4 v- K7 V4 D* c' I

1. 　　struct Student *Insert(struct Student *pHead,int number)
   
2. 
   ( w6 x) i# R* o6 z, K" C6 ~3 d+ R$ h
3. 　　{
   
4. 
   ' [+ q5 G7 C* w6 L: X
5. 　　struct Student *p=pHead,*pNew;/*定义pNew指向新分配的空间*/
   0 K1 R$ {- d% G
6. 
   ; e$ }& v0 f+ t/ Y, z) l6 G) `
7. 　　while(p&&p->iNumber!=number)
   
8. 
   2 M  m4 ?# m3 c
9. 　　p=p->next;/*使临时结点跟踪到要插入的位置(该实例必须存在学号为number的信息，插入其后，否则出错)*/
   
10. 
    ; S1 O, |3 `! P
11. 　　printf("姓名和学号：\n");
    $ g' @) @; a8 T8 O
12. 
    5 g0 t3 m2 F0 _% p; G
13. 　　/*分配内存空间，返回该内存空间的地址*/
    
14. 
    * B4 M0 s& w6 ^/ _/ }% q: E' d- D
15. 　　pNew=(struct Student *)malloc(sizeof(struct Student));
    + z* m% Y3 l3 q' x1 F
16. 
    3 z: C& O; ]) Z- o! D5 M
17. 　　scanf("%s",pNew->cName);
    # g$ p1 r7 [- X& v: ?
18. 
    
19. 　　scanf("%d",&pNew->iNumber);
    ( H) l. R9 G) b( O4 N8 C$ G
20. 
    
21. 　　pNew->next=p->next;/*新结点指针指向原来的结点*/
    
22. 
    1 L8 M5 j2 \8 a0 E- X4 `
23. 　　p->next=pNew;/*头指针指向新结点*/
    
24. 
    
25. 　　iCount++;/*增加链表结点数量*/
    
26. 
    
27. 　　return pHead;/*返回头指针*/
    % A, I) @0 Y2 u7 N& C( O
28. 
    
29. 　　}

复制代码

  V0 Z  g) ~( Y% a( }( }
; ]$ A  H8 X6 {) Y
, G- I; }  |% r
! ^! I. C, v0 z. [+ U, d　　删除函数：

, `% f. _- H8 {

1. 　void Delete(struct Student *pHead,int number)
   0 E% |1 p" W: u" J# G+ z" _
2. 
   ' o" x, A+ Z0 T  }/ J" y* u' x
3. 　　{
   
4. 
   
5. 　　int i;
   2 V* q& R: ^0 T2 E# \8 f& i* r
6. 
   
7. 　　struct Student *pTemp;/*临时指针*/
   - \' d" A3 v1 A3 x, l1 t/ [& k( N
8. 
   1 ^9 F6 E1 i4 i  e+ Q5 ~
9. 　　struct Student *pPre;/*表示要删除结点前的结点*/
   : U; z1 N4 X; A8 X" U
10. 
    & v+ l; r5 w$ P0 h3 W8 t4 \; k
11. 　　pTemp=pHead;/*得到链表的头结点*/
    
12. 
    
13. 　　pPre=pTemp;
    
14. 
    % ]- G) P- [& B$ T- g
15. 　　for(i=0;i
    : u" ^2 U- S: b, B( s
16. 
      O% M4 F' m7 }5 o
17. 　　{/*通过for循环使得Temp指向要删除的结点*/
    2 P1 [0 p) L% C0 Z
18. 
    
19. 　　pPre=pTemp;
    
20. 
    
21. 　　pTemp=pTemp->next;
    
22. 
    $ q1 p  M$ r  j9 D: o, q
23. 　　}
    
24. 
    
25. 　　pPre->next=pTemp->next;/*连接删除结点两边的结点*/
    3 f# v. u7 x8 a& o# j
26. 
    
27. 　　free(pTemp);/*释放要删除结点的内存空间*/
    4 j& d% O" I& H2 L: A$ R0 Z
28. 
    9 V! o- [* A/ g! X' K
29. 　　iCount--;/*减少链表中的结点个数*/
    " _0 C" \$ h3 |
30. 
    
31. 　　}

复制代码

　　四、双向链表的概念
　　双向链表基于单链表。单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。
　　在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点的地址，一般称为右链域;一个存储直接前驱结点地址，一般称之为左链域。
　　双向链表结构示意图：

　　

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

  I$ O0 g# ?: ^3 y' g3 `

1. 　　#include #include
   
2. 
   
3. 　　#include
   * k4 e3 K1 ?' n% X' P' G
4. 
   9 H9 z7 d$ Q/ c6 b
5. 　　#define N 10
   " y. T3 V$ F$ F2 @/ F
6. 
   
7. 　　typedef struct Node
   
8. 
   
9. 　　{
     A6 |0 O$ C9 J* L$ g2 f1 `# d
10. 
    
11. 　　char name[20];
    
12. 
    
13. 　　struct Node *llink,*rlink;
    
14. 
      ~6 w1 l+ w9 H+ a' h" Q
15. 　　}STUD;
    
16. 
    & U" W! ^7 v4 L6 ~, H5 L6 h
17. 　　STUD *creat(int);void print(STUD *);
    ' U( I3 x$ o' |$ \4 D( H3 Y2 f
18. 
    : Z" M. O/ D3 X0 ]( n
19. 　　int main()
    $ Z/ a" |" N! u; g6 O8 z: z! w
20. 
    - ~! p; h' H4 C' q: \
21. 　　{
    
22. 
    
23. 　　int number;
    % S% N; L! D+ w: L  g1 F9 N; M
24. 
    % @1 l! ]  t6 v- j' e4 T) C  |
25. 　　char studname[20];
    
26. 
    ' ?: ]' ?" I& V7 u* K  s! I
27. 　　STUD *head,*searchpoint;
    & F( I4 V6 b# v
28. 
    
29. 　　number=N;
    
30. 
    
31. 　　head=creat(number);
    
32. 
    
33. 　　print(head);
    
34. 
    ) `1 H) U. l( `5 Q* T' J- o9 `
35. 　　printf("请输入你要查找的人的姓名：");
    - W1 M0 S' J! r2 h
36. 
    & m$ ?( a2 q  J  E9 n( T+ \
37. 　　scanf("%s",studname);
    + J1 c, a; Z; {3 W+ o, U
38. 
    ' P: `4 j8 g0 g- Q
39. 　　searchpoint=search(head,studname);
    & i5 p$ y$ M' x% m( y' W
40. 
    
41. 　　printf("你所要查找的人的姓名是：%s",*&searchpoint->name);
    & B. f$ S1 c0 i7 v1 U+ `
42. 
    & H- R6 _' G+ ]! F% i3 r
43. 　　return 0;
    
44. 
    ! n# Z, C, J9 `! A( z
45. 　　}
    
46. 
    
47. 　　STUD *creat(int n)
    
48. 
    9 h. D- ?, f0 `/ j  m' V2 ?
49. 　　{
    ; W* q& K9 j( Y6 _9 r5 y+ \
50. 
    
51. 　　STUD *p,*h,*s;
    
52. 
    
53. 　　int i;
    # F, u) w+ a! x4 C
54. 
    " P: F+ v4 z# ]+ N1 P
55. 　　if((h=(STUD *)malloc(sizeof(STUD)))==NULL)
    % P( v/ s9 s" O- n
56. 
    . W$ [$ k/ ^6 S4 i. A
57. 　　{
    7 g! ]- O8 D0 J/ v# e
58. 
    : ^! Q1 U# w5 U: f8 B
59. 　　printf("不能分配内存空间");
    & T; Q- h; t# S4 g
60. 
    0 ]( T" A- C1 X. I- B
61. 　　exit(0);
    * n) g8 A5 X$ |8 c
62. 
      {5 _& m  t8 X7 z1 g1 M. v
63. 　　}
    
64. 
    
65. 　　h->name[0]='\0';
      Z+ m* j/ L8 f- N# n$ m
66. 
    ! C: c8 h* K9 S' u1 }2 j
67. 　　h->llink=NULL;
    
68. 
    
69. 　　h->rlink=NULL;
    
70. 
    0 ~# i9 Q( H. p
71. 　　p=h;
    
72. 
    6 p% K6 Y; v( L: j3 ~; q
73. 　　for(i=0;i
    
74. 
    ( j/ E" Y6 [5 _- h6 N
75. 　　{
    # [! V+ |  J( r
76. 
    : o6 e" U8 i* H5 B3 A* Q
77. 　　if((s=(STUD *)malloc(sizeof(STUD)))==NULL)
    - X  k& G& c# p3 i
78. 
    
79. 　　{
    & m# k6 h; {- T' \
80. 
    % A/ J/ K+ n( L. m; i
81. 　　printf("不能分配内存空间");
    & n" d7 C# b" P) r
82. 
    * _7 ]# [) j; j* P" M, N
83. 　　exit(0);
    # E$ L4 j1 n! l. z, P, l
84. 
    4 k4 J, @8 n3 k2 E" |  x& A
85. 　　}
    
86. 
    
87. 　　p->rlink=s;
    
88. 
    ' g( B- u# K# v2 U2 L* x) O" g5 L
89. 　　printf("请输入第%d个人的姓名",i+1);
    
90. 
    
91. 　　scanf("%s",s->name);
    
92. 
    + }! u: h" {6 _, g% d
93. 　　s->llink=p;
    
94. 
    
95. 　　s->rlink=NULL;
    
96. 
    
97. 　　p=s;
    + y- b+ ?: J4 I3 T
98. 
    ) [+ P2 O  j; r8 a7 k$ w/ t
99. 　　}
    
100. 
       i! W6 y. r8 u5 i0 c& ?9 \
101. 　　h->llink=s;
       B4 {& L8 g8 G" N' H' h
102. 
     ( w1 P5 t4 v0 |% N* V
103. 　　p->rlink=h;
       R  {7 h% A" ^" M6 d
104. 
     , f# @8 b+ [0 m3 y( e
105. 　　return(h);
     ( ^5 v% M$ R: D
106. 
       s4 J2 l0 a2 b- R* ]; W
107. 　　}void print(STUD *h)
     
108. 
     
109. 　　{
     
110. 
     
111. 　　int n;
     
112. 
     5 c0 {7 i  c8 T" H8 G* y
113. 　　STUD *p;
     & Y0 Z" A2 @! w3 o7 c
114. 
     5 }8 s( L4 l( p& Z$ i* K1 E  w
115. 　　p=h->rlink;
     0 H  ?, V, G: W. c, j2 @0 j$ C
116. 
     
117. 　　printf("数据信息为：\n");
     ' a8 ]" s+ O" T9 X% v1 k3 M2 O
118. 
     3 c8 w. [  Z+ I2 a
119. 　　while(p!=h)
     
120. 
     # P, z( ~0 v$ B6 p$ S" |3 f
121. 　　{
     8 C% r, ~2 Z4 z0 a" h' t
122. 
     2 Q: B$ q0 y! d/ I% l
123. 　　printf("%s ",&*(p->name));
     
124. 
     
125. 　　p=p->rlink;
     
126. 
     
127. 　　}
     
128. 
     
129. 　　printf("\n");
     
130. 
     . z3 d) g% k- |5 K
131. 　　}

复制代码

4 k* ~6 f. P9 _4 i" @* H' l
/ r+ w: d9 V8 v
6 L" u0 q2 H8 f; [1 \: j* K6 Z
$ u  G3 G0 [4 g6 p$ [* c- U3 z　　六、双向链表的元素查找
　　查找函数 STUD *search(STUD *,char *);

( ?9 _, }. n) U4 x4 K+ }: \
' G. h1 C9 n: i5 A" ~: k# W) [

1. 　　STUD *search(STUD *h,char *x)
   
2. 
   
3. 　　{
   * P/ V/ H! w. y" o5 p
4. 
   
5. 　　STUD *p;
   9 b3 H$ X7 _5 F+ ?  s3 p
6. 
   
7. 　　char *y;
   
8. 
   " T. A: y% d/ e, c
9. 　　p=h->rlink;
   ' D& A+ O, E# s5 B# q& B: }0 j0 Y/ N
10. 
    " j" v0 k3 _) a8 _; R* L( b( j' a2 I
11. 　　while(p!=h)
    
12. 
      z. \" Y. {; O; K4 u! ^
13. 　　{
    
14. 
    
15. 　　y=p->name;
    
16. 
    
17. 　　if(strcmp(y,x)==0)
    6 T! @4 j  j! Y% s
18. 
    % D: q' }0 v; n; I% c
19. 　　return(p);
    
20. 
    
21. 　　else
    
22. 
    2 c/ k9 I- @; x
23. 　　p=p->rlink;
    ( ^! e8 E2 o; B4 i; Z: M! c
24. 
    
25. 　　}
    ! `+ h' F2 g2 c) Q8 r" g: @
26. 
    % w( O: ~+ C' _: o; g
27. 　　printf("没有查到该数据!");
    
28. 
    / e: k  S1 Y' M3 `/ O
29. 　　}

复制代码

; n/ o0 _7 Q8 ^

4 o% l" u0 E' r* N: r" f& k' M
+ |# I2 I$ _  V# b9 i" @  j3 A$ P　　七、循环链表的概念
　　类似于单链表，循环链表也是一种链式的存储结构，由单链表演化而来。
; i+ s# E+ J/ J- ~　　单链表的最后一个结点的指针指向NULL，而循环链表的最后一个结点的指针指向链表头结点。
& p( U/ h# B  @( m1 f+ j; e　　这样头尾相连，形成了一个环形的数据链。
　　循环链表的建立不需要专门的头结点。
　　判断循环链表是否为尾结点时，只需判断该节点的指针域是否指向链表头节点。
; |! N7 u# \! R& D. ?　　八、合并两个链表的实例
2 u, A" Q- B3 }8 R. [　　建立两个带头节点的学生链表，每个节点包含学号、姓名和成绩，链表都按学号升序排列，将它们合并为一个链表仍按学号升序排列。
( ~4 L, n3 L" l) ^; C+ J; K' S! {　　算法分析：
5 |% [# }9 a/ x3 H/ r' f3 `8 O& E　　合并链表用merge()函数实现。函数中定义3个工作指针a、b、c，其中a、b分别指向La链表、Lb链表的当前结点，C指向合并后的链表尾结点。合并后链表的头结点共用La链表的头结点。
　　①合并前，先让a和b分别指向两个链表的第一个结点，c指向La链表的头结点。
　　②合并时应该分3种情况讨论，即La和Lb都没有处理完;La没处理完，但Lb处理完毕;Lb没处理完，但La处理完毕。
  V( s$ s, R* Y　　③合并过程中应始终将La和Lb链表中较小的一个链接在Lc中，方能保持有序。
  C/ L4 t% @/ M$ ^, Q* h

1 d3 M7 ?$ a5 z# @5 a
6 g1 y6 V6 k$ \7 ]4 g+ |) h" C
6 j- R% T4 ]5 ?- K  F9 j. v

1. 　void merge(struct stud *La,struct stud *Lb)
   
2. 
   2 G  R2 |8 U& w4 a( {
3. 　　{
   
4. 
   
5. 　　struct stud *a,*b,*c;
   % C, c! b; f8 s* E6 D5 R
6. 
   
7. 　　c=La;
   
8. 
   
9. 　　a=La->next;/* 合并前 */
   6 U5 G8 F: f) X( u: H
10. 
    
11. 　　b=Lb->next;
    
12. 
    
13. 　　while(a!=NULL && b!=NULL)/* La和Lb都没处理完 */
    2 G; ]+ C% r7 O# R
14. 
    
15. 　　{
    
16. 
    % U* w( U0 h# S% y8 t, B
17. 　　if(a->num <= b->num)
    
18. 
    2 }6 [. I/ X9 S. \- T, t4 k
19. 　　{
    6 b* t1 n+ c" X! j
20. 
    8 u6 X, ~! h+ u) Y; K6 R0 F
21. 　　c->next=a;
    
22. 
    1 e' Y' Y8 ?  ]) p
23. 　　c=a;
    & f7 y5 C4 ^9 N+ D7 ]+ h: i
24. 
    
25. 　　a=a->next;
    
26. 
      R! c9 c* F7 M: H5 V8 L
27. 　　}
    
28. 
    
29. 　　else
    , x* `- ^- x# l2 l% T
30. 
    
31. 　　{
    : F) f$ t/ V: D6 I9 Y1 _
32. 
    
33. 　　c->next=b;
    
34. 
    
35. 　　c=b;
    
36. 
    # P4 e# p7 l' S- R7 o
37. 　　b=b->next;
    
38. 
    
39. 　　}
    
40. 
    0 y' p# O: n1 h  ~: q8 E
41. 　　}
    ! I$ x. O3 q/ [) F9 i! ]1 N
42. 
    % \8 O& p3 U) C( ^( x# U. T7 {+ }! N
43. 　　if(a!=NULL)
    
44. 
    & y4 \) m2 [% C, T5 y
45. 　　c->next=a;/* 若La没有处理完 */
    
46. 
    
47. 　　else
    & o9 I# C+ p/ Z! d6 I& Y
48. 
    ; v+ i2 F7 n4 ]" k; u
49. 　　c->next=b;/* 若Lb没有处理完 */
    ) a; b* @/ U$ h2 J) S8 j0 ?2 E( Q
50. 
    , A- G! ], \2 O0 J  K0 P; M
51. 　　free(Lb); /* 释放Lb的头结点 */
    
52. 
    + z) J7 @" @9 o* e' o$ t2 }; |) p
53. 　　}

复制代码

! e! S3 _' f9 \( S% F7 B