找回密码
 注册
关于网站域名变更的通知
查看: 750|回复: 0
打印 上一主题 下一主题

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

[复制链接]

该用户从未签到

跳转到指定楼层
1#
发表于 2019-9-2 17:09 | 只看该作者 |只看大图 回帖奖励 |倒序浏览 |阅读模式

EDA365欢迎您登录!

您需要 登录 才可以下载或查看,没有帐号?注册

x
  最近临近期末的C语言课程设计比平时练习作业一下难了不止一个档次,第一次接触到了C语言的框架开发,了解了View(界面层)、Service(业务逻辑层)、Persistence(持久化层)的分离和耦合,一种面向过程的MVC的感觉。
' ]8 G4 q$ k7 T' b. I% v  而这一切的基础就在于对链表的创建、删除、输出、写入文件、从文件读出....../ k- l! }6 ]  Z' J/ w* k
  本篇文章在于巩固链表的基础知识(整理自《C语言程序设计教程--人民邮电出版社》第十章——指针与链表),只对链表的概念及增删改查作出探讨,欢迎指教。
& n2 _: e/ z2 R, R# A4 A8 v  一、链表结构和静态/动态链表
) M& O' C- K7 p% [  二、单链表的建立与遍历
9 l0 R3 O; F. o" D/ i  三、单链表的插入与删除
1 J* v1 q! g1 U4 U  四、双向链表的概念
; Q5 L+ P% U% @; B' ?1 ]- @/ C0 ^  五、双向链表的建立与遍历+ X6 E% k. l( H: X; q+ n: I7 O) y0 z( e
  六、双向链表的元素查找
% F. X. Q$ Z% H5 E7 C  七、循环链表的概念
1 @" h  L1 \6 f8 G* L  八、合并两个链表的实例
/ o7 O' r" w6 R) F! ~0 j2 J; I  九、链表实战
+ O* P2 O7 U, R9 Q7 R+ D. A  拓展思维、拉到最后去看看 (•̀ᴗ•́)و ̑̑: S2 P! c. |5 i
  一、链表结构和静态/动态链表7 e5 _6 v# {9 T3 }" O% J# ~
  链表是一种常见的数据结构——与数组不同的是:
8 \  b7 h0 o! o. Y8 K+ V  1.数组首先需要在定义时声明数组大小,如果像这个数组中加入的元素个数超过了数组的长度时,便不能正确保存所有内容;链表可以根据大小需要进行拓展。% W) a5 j( q. m" s' s. |$ t
  2.其次数组是同一数据类型的元素集合,在内存中是按一定顺序连续排列存放的;链表常用malloc等函数动态随机分配空间,用指针相连。
( R; C! I% O$ T; H# z  链表结构示意图如下所示:
1 }$ I1 {$ [9 P) w
  

1 D. V. ^) A4 R0 ~  在链表中,每一个元素包含两个部分;数据部分和指针部分。数据部分用来存放元素所包含的数据,指针部分用来指向下一个元素。最后一个元素的指针指向NULL,表示指向的地址为空。整体用结构体来定义,指针部分定义为指向本结构体类型的指针类型。
* g8 O5 Y1 l$ U. \$ n$ R8 I  静态链表需要数组来实现,即把线性表的元素存放在数组中。数组单元存放链表结点,结点的链域指向下一个元素的位置,即下一个元素所在数组单元的下标。这些元素可能在物理上是连续存放的,也有可能是不连续的,它们之间通过逻辑关系来连接——这就要涉及到数组长度定义的问题,实现无法预知定义多大的数组,动态链表随即出现。+ `7 J1 a9 Y# E8 C9 d, `1 @: w- s5 Y
  动态链表指在程序执行过程中从无到有地建立起一个链表,即一个一个地开辟结点和输入各结点的数据,并建立起前后相连的关系。
% I+ S0 M* ?- T6 v& ~  二、单链表的建立与遍历
8 H7 O& m* P1 {  单链表中,每个结点只有一个指针,所有结点都是单线联系,除了末为结点指针为空外,每个结点的指针都指向下一个结点,一环一环形成一条线性链。3 S  U) f) _! k& {2 p. h, D
  链表的创建过程:# O# c4 M3 P# h4 m8 A
  

- i" T2 C# U9 ^2 @  接下来在源码中建立并遍历输出一个单链表。5 i! i% K9 s- K8 W

1 d( J! `# h8 L3 X
, G8 v6 v2 |& [' s4 W" N7 X9 q+ V$ o% L: t- p
  1.   #include/ W% T" |/ {! W
  2. ) B2 c6 @  U& K9 K
  3.   #include* ]5 n# v& x  L
  4. * |% K, k/ v6 |$ A: Y1 g) w2 G
  5.   #include7 j3 C+ {+ m* `; S7 @
  6. ( H' r. [. F. L
  7.   /*单向链表*/
    $ i9 O7 \+ W2 @7 L) k

  8. ' d6 _  ~6 c6 }. R: i
  9.   struct Student/*建立学生信息结构体模型*/7 {+ v) H9 V9 R  Y* P2 z

  10. 5 o0 N, ], \$ ]* `1 T* Y4 u; S
  11.   {
    2 C0 J" o6 K" {- y+ n
  12. 2 s8 j0 q, K9 f- P- o
  13.   char cName[20];/*学生姓名*/
    # S/ k+ {6 V( K  _$ F: X' T
  14. ) l' t3 B5 I# C3 {3 P/ y
  15.   int iNumber;/*学生学号*/- O, \% |) ~! P% m' |+ [+ A
  16. # n0 C/ J# h; T4 p' T
  17.   struct student *next;/*指向本结构体类型的指针类型*/
    $ D4 Y. m. }1 T! [
  18. / x' G8 s; b1 `# g/ R8 H/ \& _" M% C
  19.   };, Z* `- V% x% u+ e, g
  20. : L& o! m  h. n2 S5 p5 ~
  21.   int iCount;/*全局变量表示链表长度*/
    6 F: |, U6 A' F  U! @1 n0 A1 u
  22. ) l1 M+ R1 ]# d3 V7 E
  23.   struct Student *Create();/*创建链表函数声明*/
    7 h0 }, @: x$ [& R; @( J

  24. % [# y3 D# @% f' Q% V  O
  25.   void print(struct Student *);/*遍历输出链表函数声明*/
    1 r) K/ f0 y3 z* V
  26. 6 V8 N0 I+ V) y# V1 A
  27.   int main()
    : ?. b; Y: g9 W0 ^8 h) M1 h

  28. 3 n2 S4 i' [+ B, _; r- X" ?# w
  29.   {
    4 ]3 y' G4 Q: t& ]" }2 G# B
  30. ' r2 f& H/ J- d9 v  n) j; j7 H
  31.   int insert_n=2;/*定义并初始化要插入的结点号*/
    0 q: w# x2 `- q

  32. 4 B& V# T) H; l- [1 F0 M
  33.   int delete_n=2;/*定义并初始化要删除的结点号*/+ L& R% [! c, q  T
  34. 8 n1 D6 }4 I# `" ^
  35.   struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/) g3 F/ p  k8 W( V! C
  36. 4 E, Y, E5 E) L  |; l3 w
  37.   pHead=Create();/*创建链表,返回链表的头指针给pHead*/: ?8 V; I$ Y- B# W/ q  B! E

  38. % d, E( n0 z: Q/ j) P5 A# J+ n
  39.   print(pHead);/*将指针pHead传入输出函数遍历输出*/. i1 Q0 H5 t1 h

  40. & n1 i  {% I& Z0 f* ^$ _2 U
  41.   return 0;
    / E5 g" W! U1 W6 s( n$ E

  42. ! q) o& _, e: j; L0 x2 B
  43.   }
    + |" I7 K7 a* d$ `, y

  44. ' @* }7 o. j+ f: e4 H) S7 f
  45.   struct Student *Create()
    1 R. n8 p3 ^& f; H7 y, Y- _5 e3 M

  46. 5 q# S+ i8 g7 H8 v
  47.   {
    2 I4 z8 H, r  ?2 ?
  48. ( W7 B0 F9 t& a' _# X
  49.   struct Student *pHead=NULL;/*初始化链表,头指针为空*/' n' P+ m9 U* S
  50. $ L2 y* j) p+ J1 p  {, Q
  51.   struct Student *pEnd,*pNew;0 E6 N% `, K7 R4 f1 U
  52. % j/ D* s: E9 d: l6 j
  53.   iCount=0;/*初始化链表长度*/1 n. w, }% j+ N

  54. % H3 S5 n" E- u# w0 ?
  55.   pEnd=pNew=(struct Student *)malloc(sizeof(struct Student));/*动态开辟一个学生信息结构体类型大小的空间,使得pEnd和pNew同时指向该结构体空间*/! V/ i& R# E+ y! a
  56. % S' h) R8 {0 d: f1 U7 ]
  57.   scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    0 }& b! x% X- w2 ~3 O7 m
  58. . s1 k6 j/ m  _: u# T
  59.   scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/8 m8 z: G. D! o# b3 _
  60. " _9 y* L) |. k1 h, D0 g% B+ Z
  61.   while(pNew->iNumber!=0)/*设定循环结束条件——学号不为0时*/
    - U4 G7 n# S/ F1 k

  62. 8 K% Y9 D% W, K7 B
  63.   {
    * v! ?! J* l) j

  64. ) x' U+ q3 L" k' T3 C+ I
  65.   iCount++;/*链表长度+1,即学生信息个数+1*/" O, R9 L1 h; V: b* r5 ^2 K* ^
  66. " N6 J" ?1 ?5 S' p+ q
  67.   if(iCount==1)/*如果链表长度刚刚加为1,执行*/
    # ]: f9 ^4 c  l9 f; a# W0 P

  68. " M1 c! e% b% N0 K8 r9 I6 ^
  69.   {* s( b& {2 i0 ?

  70. * @& g9 c( @3 V# k5 m$ n2 [! ]) J
  71.   pNew->next=pHead;/*使指针指向为空*/  I  ^0 @  _2 O: H, {& k: t

  72. 6 o" j7 T8 k( A5 R7 U& I
  73.   pEnd=pNew;/*跟踪新加入的结点*/
    ! a1 w, y& m; K5 M: W3 n. S1 [

  74. - |  \4 a, D  e* L# P* ~
  75.   pHead=pNew;/*头结点指向首结点*/7 V( b" M7 T( S( m7 V
  76. . x& K2 }- r  T4 n6 T; ]  D
  77.   }
    4 k/ d4 n  F9 _0 l7 X
  78. * Q% }6 o0 D+ d  \3 \  _
  79.   else/*如果链表已经建立,长度大于等于2时,执行*/
    ) @, u8 Q2 N7 n

  80. , b+ |5 G, r2 b6 F- W2 ?: A
  81.   {
    % L0 Z- P, b; L+ J
  82. 9 d9 K: [3 m9 z* Q/ Q  v
  83.   pNew->next=NULL;/*新结点的指针为空*/$ c$ f: h1 t- p% l
  84. : |" q1 S, I; T* C' }9 W4 _) o
  85.   pEnd->next=pNew;/*原来的结点指向新结点*/
    2 {9 t" k/ @2 W6 D2 u
  86. ' A8 L8 k# g- `$ L% s6 `
  87.   pEnd=pNew;/*pEnd指向新结点*/
    0 ~9 I$ u4 l+ [1 z# p
  88. 9 R4 o- m8 a- V' b: A5 y) @
  89.   }4 k+ V7 u6 q6 _. v, w' d: G, b$ w
  90. + ~/ S" [" X6 z
  91.   pNew=(struct Student *)malloc(sizeof(struct Student));/*再次分配结点的内存空间*/: `: j* E9 ^5 e& L$ T  O% u: Z
  92. . t% W6 w: @& ]# m9 x1 i
  93.   scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
    - g* o3 `0 h( n4 W
  94. 7 T* w* e/ m$ X3 P  w2 _% g$ l2 J  R
  95.   scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/4 b: \% O  Z8 e2 Z4 c

  96. 7 }. d$ a& F! x
  97.   }
    2 O- H! B8 \4 B1 T+ L  g' ]$ ~5 p4 O
  98. 1 d4 |6 d2 }( O5 i2 j5 |
  99.   free(pNew);/*释放结点空间*/& v: g* k4 i3 w1 V0 V* K. L9 F

  100. 3 z0 ^/ ^! C' @9 D
  101.   return pHead;/*返回创建出的头指针*/
    / X8 U; x1 }7 K+ `# S2 m
  102. ' f. u# B* W1 C5 e5 b/ Q
  103.   }) t' j5 }' X. t" J  v3 \

  104. % h, X! N! C  ^. u" ?9 u
  105.   void print(struct Student *pHead)
    ) N+ N8 L$ A" l, F; K2 }
  106. : A( P# j& ]& S( f4 \. J9 R2 m
  107.   {, a) F* r& Y* F; E# s& H, `4 E) ?
  108. 9 D( H( x; D6 k. I, t
  109.   struct Student *pTemp;/*定义指向一个学生信息结构体类型的临时指针*/
    3 r; z8 K" B( z4 N4 V2 w6 I! t; @
  110. " Z+ R! c( t! v& @& t
  111.   int iIndex=1;/*定义并出事哈变量iIndex,用来标识第几个学生(信息)*/
    + n7 X# A6 p6 ]; ?0 f% F* [
  112. 9 o# b+ l4 {, A% O, y6 O+ Z# r
  113.   printf("总共%d个学生(信息):\n",iCount);. N$ C9 ?% C0 J$ W8 z

  114. 1 d- Y4 u6 b9 l7 T( N/ _3 D
  115.   pTemp=pHead;/*指针得到首结点的地址*/
    . }8 D; @: c+ Z/ Y/ e2 C
  116. 1 K- f. C5 I+ R7 l9 T
  117.   while(pTemp!=NULL)/*当临时指针不指向NULL时*/8 ]% H& Z0 C2 N0 P! h, k! P

  118. ! t  x0 ^: T/ O. P) \
  119.   {
    4 a4 S+ J$ ?+ H( f8 a8 P" }. f4 e
  120. 9 p8 }2 h& V+ x# t4 _+ ~# ]
  121.   printf("第%d个学生信息:\n",iIndex);
      E1 D0 v# @3 _

  122. 1 S8 \" r+ _. l) d% c! i
  123.   printf("姓名:%s",pTemp->cName); /*输出姓名*/4 ?# w+ M4 C! ?1 u% q5 B5 ~3 @

  124. / i3 N. I" D- p
  125.   printf("学号:%d",pTemp->iNumber);/*输出学号*/
    - @2 t, f/ t" R! h; C
  126. . {0 T3 [2 l  `% l6 x1 }
  127.   pTemp=pTemp->next;/*移动临时指针到下一个结点*/1 V7 T9 J1 c: ^- A0 A& Z6 C8 W
  128. : K: Q9 ?+ [' p8 e
  129.   iIndex++;/*进行自加运算*/
    " m0 m9 ]$ `6 b7 }
  130. 3 }7 k/ m! {% `' e
  131.   }
    # J: l( f1 I  \3 r
  132. 3 ?2 o' _% `7 g
  133.   }
复制代码

$ R: t) y; c/ U- i& z& r, C% \5 Y6 M( B( @
- m) m& `" s) ^6 Q7 k/ @
; m6 {  |$ ~  ~& V6 K0 U$ j
  三、单链表的插入与删除
$ Z5 f5 h. B6 Q5 s. p8 K+ G1 |; T  在本实例中,插入时根据传递来的学号,插入到其后。
7 s. u& o- q( t. G8 o  删除时根据其所在链表的位置,删除并释放该空间。
# L4 B; Q* I8 y+ e  主函数增加如下:
7 n1 f# q' Z3 }# @5 l; I% F2 i7 O1 Y( |7 h2 X* L5 R( r

6 f6 F# w$ U6 `8 p1 e9 k% O2 A5 x3 a7 e4 p* X
  1.   int main()
    ; E" ~0 G' ~( Y2 g% g
  2. 9 p: s+ k2 y3 U  I/ I
  3.   {& X7 q( A* W; c* N: J/ e1 \
  4. * D5 @9 A' x- ]7 B" U7 F+ v) R# o
  5.   int insert_n=2;/*定义并初始化要插入的结点号*/
    2 \$ ^3 E! a* ^7 V8 Q

  6. % A  l; C2 C7 ?0 t1 P- I; b8 J
  7.   int delete_n=2;/*定义并初始化要删除的结点号*/* o6 X- k8 Q' a$ F5 h1 e1 J3 v
  8. - _: y$ a/ z2 e
  9.   struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
    : g. x4 Q9 w$ v  u5 G6 L# T$ E; i
  10. 4 O- ~' r; m4 Q$ O: U! b4 P
  11.   pHead=Create();/*创建链表,返回链表的头指针给pHead*/
    & Z- }" b* X; O5 P6 M
  12. ) }# ]+ E( u4 U* o, ]1 P6 i
  13.   pHead=Insert(pHead,insert_n);/*将指针pHead和要插入的结点数传递给插入函数*/
    " G  b% V7 I& `* u

  14. ) N6 n- F* i1 p4 ?) {' [* O
  15.   print(pHead);/*将指针pHead传入输出函数遍历输出*/& n( f/ A$ L$ g7 u5 Z, I( Z5 a# C

  16. + Z6 h. W1 g1 u4 ^1 I% ]
  17.   Delete(pHead,delete_n);/*将指针pHead和要删除的结点数传递给删除函数*/
    * N/ z' j# ~6 |( s

  18. & @' u) E7 t, A3 O/ k& a+ u
  19.   print(pHead);/*将指针pHead传入输出函数遍历输出*/' a8 @* q1 Q. c% y# T
  20. : k) G& p5 R, V; M1 _0 h, ?2 Y& B
  21.   return 0;. G3 i6 s5 V, Y6 f% M/ {
  22. * ^$ n, ^9 T7 p; q; j
  23.   }
复制代码

& d; e7 a2 q( l. R( M
2 ]5 {- M( j' T4 w$ e& k  k) D9 e, }9 a6 u" ]+ q. T
# d; p7 R7 g8 }  Y: J
  插入函数:3 N, f$ u, X+ S0 Q
9 O  T0 u% _6 @5 B# {

  b+ e! p" j) j1 w  V5 v7 f6 [( C  e7 s
8 ^. t1 G2 h1 ~0 n" A9 t, q1 h( h
  1.   struct Student *Insert(struct Student *pHead,int number)' U+ h7 y- t3 p

  2. - L4 e3 _( E# t2 [9 p* y( s
  3.   {$ \  c8 A4 p& P: w5 v  @& T/ d1 Q7 {

  4. 2 \; q% ^! P$ B: y* {4 r; k; z
  5.   struct Student *p=pHead,*pNew;/*定义pNew指向新分配的空间*/. w% r, l8 n/ ]3 @9 K; g: s
  6. 6 x3 |4 G) H# i/ D
  7.   while(p&&p->iNumber!=number)
    4 h: z& a5 B1 }+ K

  8. ( \. Q, i1 q- c
  9.   p=p->next;/*使临时结点跟踪到要插入的位置(该实例必须存在学号为number的信息,插入其后,否则出错)*/! x7 ^6 r$ t, }. x! Z
  10. 7 S- K; `! r9 k  Z
  11.   printf("姓名和学号:\n");
    7 B# H& c! _7 p# L

  12. 5 f  U0 r1 n  |, G. L5 P
  13.   /*分配内存空间,返回该内存空间的地址*/
    7 R& O$ p& W9 }8 _9 F% C/ m, v
  14. * G+ A: C& U! j  e3 {0 n
  15.   pNew=(struct Student *)malloc(sizeof(struct Student));
    ) i3 b8 N7 b$ c7 ?8 w

  16. / H2 o! U) J+ {% |
  17.   scanf("%s",pNew->cName);) r% V9 O2 L2 x  r  o4 k3 \
  18. + [( r# V* w! s
  19.   scanf("%d",&pNew->iNumber);
      K" I8 ?! f2 d4 M9 X4 ?8 ~' n6 n
  20. 9 E  R  Y1 J1 v# {: R1 r
  21.   pNew->next=p->next;/*新结点指针指向原来的结点*/
    1 [  u# y3 w# K* ~9 o- d0 `. ~" |

  22. 0 J* a; w0 c6 h* e0 R
  23.   p->next=pNew;/*头指针指向新结点*/7 Q- T% j8 @8 j0 k6 H3 m+ z$ s* `

  24. / k8 f; o% ?% b
  25.   iCount++;/*增加链表结点数量*/
    9 |5 y& f7 d4 q1 w4 t- `; o+ u
  26. 2 y7 e( a! n  F4 Z
  27.   return pHead;/*返回头指针*/
    : I2 }4 U) r+ E. N5 x
  28. 5 T' Z$ T$ A5 y' d; W
  29.   }
复制代码
% L! n$ z% [& D4 E# K$ q1 Y; h

8 `) B& I$ p3 o) E2 c5 k# H- q" P( ^, |3 a, o7 b$ _% t/ \
, V1 N5 Z% e, l% M* O9 O7 ]  B
  删除函数:' w8 A0 d0 Q9 B

: B; D# v' t2 k2 g1 D7 K6 B0 q/ O6 `6 V- [' |. u) ^+ Q: i- B

0 P3 T0 e  s( b, ]& s
& L- o7 @4 ^3 K
  1.  void Delete(struct Student *pHead,int number)" J, x$ L; E% j. B+ I) L+ `  @

  2. 6 X2 r, g  n2 w! z
  3.   {" B4 O. o6 P: R; E1 S

  4. " h; ~/ B' c0 K' k
  5.   int i;+ R5 F/ D* e. ~% _- u

  6. * k# t, t  y$ K/ n
  7.   struct Student *pTemp;/*临时指针*/
    + N4 ?* o2 ]1 u& X2 m
  8. 4 z) v/ U4 Z- g% _! k
  9.   struct Student *pPre;/*表示要删除结点前的结点*/
    7 I9 P+ O! u. E, L3 |
  10.   S% R) s1 K- V- F; b9 `
  11.   pTemp=pHead;/*得到链表的头结点*/
    % \3 {8 ~* h2 {" Y) @! l+ a" ~
  12. 1 _, T3 ~& J% |0 J% S% x* c* d
  13.   pPre=pTemp;4 y5 J2 Z' i- i' M, {' ]5 N( D
  14. , V2 _1 g4 \" q; L) A5 i4 A0 s
  15.   for(i=0;i
    0 e- u3 T, P& b6 G  o
  16.   h/ D9 M, L5 K- Z& K5 i
  17.   {/*通过for循环使得Temp指向要删除的结点*/4 {( y9 _0 ~' Z$ o) i+ j7 a$ m
  18. 8 O" Y+ I  z: F" K
  19.   pPre=pTemp;
    2 o2 h! k; j( V6 W9 u

  20. - }5 H! F* n5 ^3 ^6 O7 b. _8 g4 P4 v
  21.   pTemp=pTemp->next;" }& F/ O( o% x# F/ R) _( Q& l2 M- w

  22. , x. J1 t% C. u+ p4 v$ v* Y
  23.   }/ {2 }2 _+ ~# |7 G# `- p4 ]8 Q0 \

  24. 9 r7 B# p8 ?/ r; Z" A: C# e
  25.   pPre->next=pTemp->next;/*连接删除结点两边的结点*/
    9 A# T* i6 y6 ?2 m) h* H6 v8 V1 ]7 r

  26. ! F: t1 f% c6 ]1 F7 Z/ q
  27.   free(pTemp);/*释放要删除结点的内存空间*/
    8 l" C' [4 z6 s# J) g
  28.   i% z1 q5 ~6 }" X) K/ I$ c
  29.   iCount--;/*减少链表中的结点个数*/( \9 u; g9 L' [) A

  30. 6 [0 w3 _6 C7 z! j- V" b7 p  b1 H3 P. [
  31.   }
复制代码

1 F" L$ h" q0 ]' t0 u% T4 }8 H) g" q: `2 [( y# p

, y# F, a) E8 i/ H3 O; ?, Y  四、双向链表的概念, B+ z2 Y8 N+ j: g4 i: W
  双向链表基于单链表。单链表是单向的,有一个头结点,一个尾结点,要访问任何结点,都必须知道头结点,不能逆着进行。而双链表添加了一个指针域,通过两个指针域,分别指向结点的前结点和后结点。这样的话,可以通过双链表的任何结点,访问到它的前结点和后结点。
: B$ F, S, K5 T% S6 L0 f  在双向链表中,结点除含有数据域外,还有两个链域,一个存储直接后继结点的地址,一般称为右链域;一个存储直接前驱结点地址,一般称之为左链域。! ^$ _7 @; {: b9 ]! D. v3 ?
  双向链表结构示意图:2 c& s2 q6 L2 \. O3 W

9 z. I' u/ b0 m6 g  U6 [8 f. x
6 H; f  r6 K# u8 \
  
' b9 S1 G) P7 y0 z+ _" |  g
  五、双向链表的建立与遍历
, M, J, X# f! B  双向链表的源码实战和单链表类似,只是多了第二个指针域的控制,这里直接贴上没有注释的源代码。! z8 ^) d: V: {# X7 K+ Z

9 L+ X( `8 H. l; n% `" X6 U0 F# {! Q; K7 Y: g9 q

4 g0 Z7 K1 k% g0 J+ o
  1.   #include #include
    & U) k2 w1 n3 N* {( y; R' _
  2. , v- U8 ?1 U/ z
  3.   #include4 q% }, d+ i9 h
  4. / h( i. ~3 Y/ {! H8 n' \
  5.   #define N 109 Z2 Y$ z5 _0 G( ?2 x1 q* B2 d

  6. * I9 O4 O. {( g( e3 J* B7 F( v
  7.   typedef struct Node3 d% ^3 u% d% ~, ]# _4 w

  8. 9 ]- `- S& O8 x) {6 t, f
  9.   {
    9 `, m, y0 {& a; m, Q9 w

  10. % f9 t3 X) v  R8 z
  11.   char name[20];
    : ^9 v8 F3 a9 w5 x1 d& I

  12. - z9 y; n/ w  f/ U; u0 b* V  U! m3 D+ @" f+ T
  13.   struct Node *llink,*rlink;: r4 G1 W. ]. Q& G+ w# P
  14. ' v, P3 p6 ^# e5 s& t
  15.   }STUD;
    1 S/ C' Z9 f0 Y# V; h. L

  16. ; O4 k' Y) k& d  L8 d, V3 v. S
  17.   STUD *creat(int);void print(STUD *);3 B, j9 |1 d( J7 E" G
  18. 1 A: G; p* v( X2 E0 |$ l& p: v
  19.   int main()* m7 r9 q# |- z, @9 e/ L9 O
  20. 6 \- o! f4 z( q) U, D
  21.   {! b  g8 ~+ q6 m6 y

  22. ( H, J) O6 S! Z: Q) Z
  23.   int number;4 z9 U! r: I, C' p- Q/ @
  24. 0 R4 U$ T* [' K. v
  25.   char studname[20];8 E! `7 Q% v; z
  26. ) S7 g" d6 ~( e+ M
  27.   STUD *head,*searchpoint;
    0 g7 d% e- ^5 k7 S

  28. 9 S: K. V: A8 q, m$ _/ t
  29.   number=N;
    ; v! f5 v# O& R5 p' X

  30. # y* i; V, F6 @7 [6 n
  31.   head=creat(number);
    / T) K8 ~; r, h9 M
  32. & K' n3 ~) @6 T: J9 j
  33.   print(head);- u$ l5 A  F- w
  34. , Q! [$ x2 x- W% ~0 W
  35.   printf("请输入你要查找的人的姓名:");
    8 g. Q; o& Q$ \7 V) H- D6 ^

  36. 2 W1 b9 L7 U  r+ y$ \& ?
  37.   scanf("%s",studname);; F- [. x6 y" ~; z7 P: _1 A( J

  38. 4 Y" Y9 A% |; B( F/ E# }8 w1 o
  39.   searchpoint=search(head,studname);, x1 P. e3 a: r$ [  W% j9 j

  40. $ O% a( i3 {4 ?% c& Z0 U
  41.   printf("你所要查找的人的姓名是:%s",*&searchpoint->name);2 N' s2 ^& S% N  x

  42. & t  n& e* A) t2 e9 S* K. |
  43.   return 0;
    + j% Y4 G, n* b- `, `

  44. , N2 g3 l+ h4 ^4 N7 m
  45.   }# H  L5 U" o8 j. _1 [8 Q
  46. . k. _( W" S# ^2 A5 N0 Z
  47.   STUD *creat(int n)" i0 `- c/ V: C7 Q2 r; J

  48. 0 c  i" m% ~9 h0 I0 d
  49.   {; r8 p  a6 ^9 \! F. y

  50. 9 J- L0 x8 U2 K; G0 @1 ^3 N* d
  51.   STUD *p,*h,*s;
    : m2 n6 h! r: c5 a2 a
  52. ! H0 G& n9 D! ?) F, M: U
  53.   int i;7 V' `- q& G1 d- T

  54. & o% _! f$ O4 ~+ K0 L  X! k4 q
  55.   if((h=(STUD *)malloc(sizeof(STUD)))==NULL)
    ( `8 w) N  s. Z! S% v

  56.   t) f8 X) }" N
  57.   {
    3 e) C7 P6 k; K1 B

  58. ! h# N* z. V9 a% N
  59.   printf("不能分配内存空间");9 t5 M& X% W& v2 C
  60. - |6 `& x/ x: u+ c& {
  61.   exit(0);
    9 y) S" D: y8 [) r' p4 i$ j+ ]: c

  62. 3 E% N" ]3 |8 d: i$ A0 v3 m
  63.   }
    , M1 Q  \; V3 T$ w  z4 n3 }

  64. ! Y0 U8 s) \5 L, u. o" z8 d
  65.   h->name[0]='\0';
    2 F  ?, R1 O3 q0 o
  66. * a, M% P6 Q' {3 m1 }* n: |
  67.   h->llink=NULL;$ s( x* }8 g* F8 _7 p
  68. 6 ]; J9 i9 A, ~' N: `
  69.   h->rlink=NULL;
    + g. k, w/ v( s9 K( W

  70. 6 w. ]% N- B) e, d
  71.   p=h;3 z, T1 h3 }6 _( Q6 k

  72. * ~8 Z3 H0 l  K' O7 Z! Y
  73.   for(i=0;i+ X' z1 v4 r- n% ^5 l! x$ U

  74. & _( {$ p2 R* I; R
  75.   {
    # h6 n/ G( i( `  M1 s3 R
  76. 3 y$ t& O% w' Z
  77.   if((s=(STUD *)malloc(sizeof(STUD)))==NULL)
    , y6 l/ f! I* w$ T
  78. ( t8 m2 W9 Q; U' b% u0 x* a
  79.   {5 [; u- ^6 N! p+ L$ t4 v
  80. 1 @+ i, _5 i% X6 H1 v
  81.   printf("不能分配内存空间");
    9 l0 V5 F, l8 l" t4 J( Q& u
  82. & \4 c9 C8 V' P' o) v0 s
  83.   exit(0);
    * M2 D- o4 a7 u/ R
  84. & Z- |; w' y7 N. B! ?
  85.   }, c( T( z& r% c2 t

  86. , i; E: e/ q* O
  87.   p->rlink=s;- _1 g' {9 @" T; n

  88. , u1 G7 a( H+ \# \( Q1 E+ j
  89.   printf("请输入第%d个人的姓名",i+1);) o% ]/ Y6 B8 ?3 Q: T9 p6 n
  90. * m/ a" w# ?5 k: H  M. S) ~# ?8 g4 \
  91.   scanf("%s",s->name);
    6 X# t) @4 P5 Z# D

  92. ! L# F8 h# C- _; @
  93.   s->llink=p;/ z7 P5 N* t. }3 s0 C
  94. + w0 V7 F5 {0 y& S
  95.   s->rlink=NULL;
    , S; N# z7 C4 ?$ _

  96. ; F4 H% L) f, y$ p" X% e
  97.   p=s;
    , ~* X4 v6 [! d8 c. `" s

  98. 0 Q: y4 R. e9 _) L% [0 b2 c7 A# ?' p
  99.   }
    3 B" |1 ?1 c- n+ R1 _! N

  100. / M* n  M5 O+ T  [( F8 ?& X6 N  x
  101.   h->llink=s;8 k# }! C7 q  w4 j3 T! B8 A4 A% P. Q% [
  102. : F+ l1 M) ^# B* v1 q0 N  d
  103.   p->rlink=h;
    # w6 D4 P2 l5 b" f$ k& _. G, C3 P

  104. 3 u' O* C: y& r4 [  J4 I3 o) c$ U$ w
  105.   return(h);
    ( M7 h% ~: G) u* Q5 B
  106. 8 a, s7 O& \* P. \& a& K  ^' A
  107.   }void print(STUD *h)
    2 L, ~2 B) ~; J: w# _6 z

  108. 5 m/ _' s1 t% E/ D
  109.   {% U+ m; J- O$ H6 v1 O

  110. + A/ y) ^* \8 |* Q9 u
  111.   int n;
    8 c3 U1 v. W7 F$ m- y* ^

  112. 3 D, u" U' A! P! x, r. ~0 y
  113.   STUD *p;. r- w* Q5 }# S! C8 k6 D
  114. , L9 ?% `' t" W4 k! t! Y
  115.   p=h->rlink;
    - ]; x9 B- q1 z$ r2 M" v
  116. & n( v  `0 E* c
  117.   printf("数据信息为:\n");: ~. U3 A. f3 X
  118. 2 d6 R! X. u& b+ s
  119.   while(p!=h)( b; M! K4 w& G  J, G

  120. 7 Y' V) c% P, z$ g0 v9 s/ Y
  121.   {
    " ?3 |7 n7 u. q  `
  122. 9 l7 m! N3 e, W3 `# i
  123.   printf("%s ",&*(p->name));
    % k% g: j. a" p, `% p  B
  124. , _$ w5 T6 r+ {. ~- p" }8 n  f
  125.   p=p->rlink;4 m# L  n  e: O/ o) {

  126.   f' ?8 ^* W: s( Q% y$ _/ \
  127.   }
    / d$ W/ ]0 T, B5 j9 M* n. N5 \

  128. + }4 ?5 [' a8 I/ `: v
  129.   printf("\n");5 V( K% l+ q9 P+ n5 Z. Z# W5 l

  130. % A1 R- Y# i; F: E. o6 C
  131.   }
复制代码
9 [  }! B2 h) b$ F6 V! q
$ B$ H0 K! M& l! I( u

; \. u8 E, n2 T$ Y! ?& x% @" _( {9 \
  六、双向链表的元素查找
3 Q6 W+ r  x2 {" s$ O  查找函数 STUD *search(STUD *,char *);
  s! l4 i% Y8 i- d6 }& |9 T
1 p0 s% V/ [1 Y4 [. n$ D' U9 O( a9 M; c9 V6 ?5 L' U

1 C* G4 r8 J3 `
  1.   STUD *search(STUD *h,char *x): J; b6 ^' s5 c1 j, w+ n: D3 C

  2. $ @/ v7 q6 ^3 b3 f' s8 K# `
  3.   {% H! @7 W7 F0 N, {* w: D) A5 ~3 |

  4. 9 j) y  Q; {. w8 V" t1 Z; P
  5.   STUD *p;) M% e& h" P3 I" W' R, {  o: u$ Z# I
  6. - F. {/ K; p4 a3 Y9 p
  7.   char *y;4 A3 Q& O; {8 t- `  h6 X! f
  8. 5 a- U# H, u; i, L4 U
  9.   p=h->rlink;
    8 [5 k6 z( m/ t4 A) X% E
  10. 1 v+ e. T, R0 e% D5 t. p# o; r
  11.   while(p!=h)7 p& r/ z- w, R: ]  O/ v& q

  12. 1 g  r1 u, [' t
  13.   {% ?+ o2 M# ^# H. ?8 C+ q% j  x5 H' Q
  14. 4 h) K! L1 |% v0 X) H  l2 {
  15.   y=p->name;
    6 f9 @5 i% Y4 _% Y! M, O2 I) t! z
  16. 8 v5 {3 k3 _' j) l2 z
  17.   if(strcmp(y,x)==0)! T! V! Z, o6 O
  18.   d' J3 {/ ~: B0 f1 l* }
  19.   return(p);
    9 C, Q3 y. b- T/ n4 o! B+ k8 j

  20. % K1 d- ~' t) k- l
  21.   else$ L$ z0 n. E7 f

  22. ; p' c6 h2 K4 v# z" D/ L, e! p5 F- E
  23.   p=p->rlink;
    6 z8 A' o5 _* Z, P% S% Y# Y; L

  24. ! Y0 D- p( I& l( M1 F9 y4 Z
  25.   }
    ! R5 s$ \6 U+ V- ^

  26. " L  j  b& f" b
  27.   printf("没有查到该数据!");' I# x6 H$ C4 y: B* c0 _8 E

  28. ! P* l% l% J- V, M$ ?
  29.   }
复制代码
6 ~% \, `$ O- p( c$ {, U& [9 W

1 _' h( D' m) f  q  Z1 m$ V4 S' f3 B
6 {2 }( q3 _& V' g5 o7 ^, D" }5 K
  七、循环链表的概念1 C# k. C4 V/ A( [, @4 n
  类似于单链表,循环链表也是一种链式的存储结构,由单链表演化而来。
& L( c1 E, K' a0 N  `) O  单链表的最后一个结点的指针指向NULL,而循环链表的最后一个结点的指针指向链表头结点。: c, X/ E1 V0 t# }% @4 b
  这样头尾相连,形成了一个环形的数据链。
  U* I6 L" x+ B0 E* G' P5 h& O  循环链表的建立不需要专门的头结点。1 f, P; ~+ A) N+ z4 J3 t& k; h! ?
  判断循环链表是否为尾结点时,只需判断该节点的指针域是否指向链表头节点。% A5 e' D: ?" v* M5 A
  八、合并两个链表的实例
: R5 V* c- S8 @% r2 n  建立两个带头节点的学生链表,每个节点包含学号、姓名和成绩,链表都按学号升序排列,将它们合并为一个链表仍按学号升序排列。# H; s3 X  D; n; h
  算法分析:
# w8 @* P( b  h8 S  合并链表用merge()函数实现。函数中定义3个工作指针a、b、c,其中a、b分别指向La链表、Lb链表的当前结点,C指向合并后的链表尾结点。合并后链表的头结点共用La链表的头结点。2 R, G' d7 O+ Z4 B6 w
  ①合并前,先让a和b分别指向两个链表的第一个结点,c指向La链表的头结点。/ S$ f2 i7 \3 y; {$ O" t) r
  ②合并时应该分3种情况讨论,即La和Lb都没有处理完;La没处理完,但Lb处理完毕;Lb没处理完,但La处理完毕。) ~/ V/ a1 u9 b4 ?) b
  ③合并过程中应始终将La和Lb链表中较小的一个链接在Lc中,方能保持有序。- A6 t' n6 Q! a  n

3 a& Y7 D8 G; x2 Q& w6 w: v0 s3 s% \4 w& ~- }8 w" {9 b. P* V8 ~
# l# P; N5 v9 U/ l2 n' t. p
3 T- H- K! j& c( N$ |+ `6 F0 J
  1.  void merge(struct stud *La,struct stud *Lb)8 ~( H# @, T. B; O2 k9 g2 Y( q
  2. - W& N  ~$ d( \& l2 F
  3.   {1 |9 k+ c! |4 x" N+ L, N5 }% c4 g) S
  4. 2 C1 S  s. n8 N+ L2 G/ `% ^8 u- h8 ?
  5.   struct stud *a,*b,*c;
    4 D3 g. X' \7 Q% O

  6. 3 o8 P+ U; k( G( @! m* @  m: v
  7.   c=La;  c( A2 ?; T0 g$ J3 t5 m
  8. 0 [( C& f% C# C7 ]
  9.   a=La->next;/* 合并前 */
    + B9 e/ J* X4 c9 j6 {# y- n

  10. 0 m7 U4 T* x/ h/ M
  11.   b=Lb->next;& j1 U9 Y. c  |- B  R9 d) Y8 B3 a

  12. ; h$ g; H( C- ]
  13.   while(a!=NULL && b!=NULL)/* La和Lb都没处理完 */
    ; s3 q2 u9 E3 B/ V- }  C5 Y- d
  14. " P9 e) I' e: s& d$ g0 H1 F+ i
  15.   {
    ! G# J2 J  x0 O' v9 }* E# k4 |( \
  16. ( }7 C2 G, i6 j
  17.   if(a->num <= b->num)0 `! i! E$ w3 b. T7 S& N) i

  18. , q) ~6 k  x4 t& w
  19.   {
    / F- ]5 x$ B0 m& t6 E3 J
  20. , q; Q3 G7 T$ `( Q' m/ ]" b
  21.   c->next=a;9 j7 o3 {% K$ s  w! `" J: v
  22. , I9 t$ ]+ ?1 R) r$ s% V
  23.   c=a;
    , `/ H2 ?" y8 c8 n
  24. ' R8 q# T4 L; b( b
  25.   a=a->next;. l$ N4 E8 q0 W- B6 ~5 K

  26. / z, C/ H" k5 z5 }
  27.   }
    & w. E$ I6 E- _4 w3 Z& ?
  28. 5 F2 W8 `6 p3 q3 p3 c
  29.   else, [( F5 T4 P; @
  30. ( w( \; H# w- v+ u% \7 P
  31.   {! g* o4 M( w4 e
  32. 5 f3 j, i: e7 n
  33.   c->next=b;
    % ]4 S2 ~9 l# U6 l4 u) ~

  34. + [& P4 T8 ?+ j, `* V$ n6 F
  35.   c=b;
    , S9 S. y8 O4 p  C9 S

  36. 8 ^# }& ]3 D3 Y- J
  37.   b=b->next;
    6 V1 I; w" p+ o. n' O/ i3 |
  38. 4 d7 d9 ?- M7 X8 l
  39.   }6 \# P, g  r2 l5 x  h: n! x* S

  40. 1 u5 _' q: |+ J4 g
  41.   }
    + w0 E; B3 F5 K" Y
  42. # m* [0 {& ~7 w9 ~. z0 C
  43.   if(a!=NULL)- X4 ^! x4 o; V( h0 z. L* ~
  44. 6 \, N" b/ p7 T1 X5 A
  45.   c->next=a;/* 若La没有处理完 */5 @% X; H; G! t2 O

  46. 7 K! h6 L8 ~" u# `6 S0 R
  47.   else
    % L) k6 H; B, X9 |" M! @9 a
  48. 0 |6 J6 |2 q. S3 ~) {; }* L2 o) ?
  49.   c->next=b;/* 若Lb没有处理完 */* `9 b6 i6 |& e% a
  50. 0 [! Q5 O, B+ _& ?- h. f
  51.   free(Lb); /* 释放Lb的头结点 */
    * [  S0 f- C" `- U
  52. 2 y& @8 p* v3 m  u
  53.   }
复制代码
( W3 |- B; T9 R9 v& E8 ]! Y

5 D7 c0 L/ \: ~" H; E7 c4 o/ O; m! E" s% \
您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

推荐内容上一条 /1 下一条

EDA365公众号

关于我们|手机版|EDA365电子论坛网 ( 粤ICP备18020198号-1 )

GMT+8, 2025-10-31 07:15 , Processed in 0.203125 second(s), 28 queries , Gzip On.

深圳市墨知创新科技有限公司

地址:深圳市南山区科技生态园2栋A座805 电话:19926409050

快速回复 返回顶部 返回列表