|
|
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
- #include/ W% T" |/ {! W
- ) B2 c6 @ U& K9 K
- #include* ]5 n# v& x L
- * |% K, k/ v6 |$ A: Y1 g) w2 G
- #include7 j3 C+ {+ m* `; S7 @
- ( H' r. [. F. L
- /*单向链表*/
$ i9 O7 \+ W2 @7 L) k
' d6 _ ~6 c6 }. R: i- struct Student/*建立学生信息结构体模型*/7 {+ v) H9 V9 R Y* P2 z
5 o0 N, ], \$ ]* `1 T* Y4 u; S- {
2 C0 J" o6 K" {- y+ n - 2 s8 j0 q, K9 f- P- o
- char cName[20];/*学生姓名*/
# S/ k+ {6 V( K _$ F: X' T - ) l' t3 B5 I# C3 {3 P/ y
- int iNumber;/*学生学号*/- O, \% |) ~! P% m' |+ [+ A
- # n0 C/ J# h; T4 p' T
- struct student *next;/*指向本结构体类型的指针类型*/
$ D4 Y. m. }1 T! [ - / x' G8 s; b1 `# g/ R8 H/ \& _" M% C
- };, Z* `- V% x% u+ e, g
- : L& o! m h. n2 S5 p5 ~
- int iCount;/*全局变量表示链表长度*/
6 F: |, U6 A' F U! @1 n0 A1 u - ) l1 M+ R1 ]# d3 V7 E
- struct Student *Create();/*创建链表函数声明*/
7 h0 }, @: x$ [& R; @( J
% [# y3 D# @% f' Q% V O- void print(struct Student *);/*遍历输出链表函数声明*/
1 r) K/ f0 y3 z* V - 6 V8 N0 I+ V) y# V1 A
- int main()
: ?. b; Y: g9 W0 ^8 h) M1 h
3 n2 S4 i' [+ B, _; r- X" ?# w- {
4 ]3 y' G4 Q: t& ]" }2 G# B - ' r2 f& H/ J- d9 v n) j; j7 H
- int insert_n=2;/*定义并初始化要插入的结点号*/
0 q: w# x2 `- q
4 B& V# T) H; l- [1 F0 M- int delete_n=2;/*定义并初始化要删除的结点号*/+ L& R% [! c, q T
- 8 n1 D6 }4 I# `" ^
- struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/) g3 F/ p k8 W( V! C
- 4 E, Y, E5 E) L |; l3 w
- pHead=Create();/*创建链表,返回链表的头指针给pHead*/: ?8 V; I$ Y- B# W/ q B! E
% d, E( n0 z: Q/ j) P5 A# J+ n- print(pHead);/*将指针pHead传入输出函数遍历输出*/. i1 Q0 H5 t1 h
& n1 i {% I& Z0 f* ^$ _2 U- return 0;
/ E5 g" W! U1 W6 s( n$ E
! q) o& _, e: j; L0 x2 B- }
+ |" I7 K7 a* d$ `, y
' @* }7 o. j+ f: e4 H) S7 f- struct Student *Create()
1 R. n8 p3 ^& f; H7 y, Y- _5 e3 M
5 q# S+ i8 g7 H8 v- {
2 I4 z8 H, r ?2 ? - ( W7 B0 F9 t& a' _# X
- struct Student *pHead=NULL;/*初始化链表,头指针为空*/' n' P+ m9 U* S
- $ L2 y* j) p+ J1 p {, Q
- struct Student *pEnd,*pNew;0 E6 N% `, K7 R4 f1 U
- % j/ D* s: E9 d: l6 j
- iCount=0;/*初始化链表长度*/1 n. w, }% j+ N
% H3 S5 n" E- u# w0 ?- pEnd=pNew=(struct Student *)malloc(sizeof(struct Student));/*动态开辟一个学生信息结构体类型大小的空间,使得pEnd和pNew同时指向该结构体空间*/! V/ i& R# E+ y! a
- % S' h) R8 {0 d: f1 U7 ]
- scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
0 }& b! x% X- w2 ~3 O7 m - . s1 k6 j/ m _: u# T
- scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/8 m8 z: G. D! o# b3 _
- " _9 y* L) |. k1 h, D0 g% B+ Z
- while(pNew->iNumber!=0)/*设定循环结束条件——学号不为0时*/
- U4 G7 n# S/ F1 k
8 K% Y9 D% W, K7 B- {
* v! ?! J* l) j
) x' U+ q3 L" k' T3 C+ I- iCount++;/*链表长度+1,即学生信息个数+1*/" O, R9 L1 h; V: b* r5 ^2 K* ^
- " N6 J" ?1 ?5 S' p+ q
- if(iCount==1)/*如果链表长度刚刚加为1,执行*/
# ]: f9 ^4 c l9 f; a# W0 P
" M1 c! e% b% N0 K8 r9 I6 ^- {* s( b& {2 i0 ?
* @& g9 c( @3 V# k5 m$ n2 [! ]) J- pNew->next=pHead;/*使指针指向为空*/ I ^0 @ _2 O: H, {& k: t
6 o" j7 T8 k( A5 R7 U& I- pEnd=pNew;/*跟踪新加入的结点*/
! a1 w, y& m; K5 M: W3 n. S1 [
- | \4 a, D e* L# P* ~- pHead=pNew;/*头结点指向首结点*/7 V( b" M7 T( S( m7 V
- . x& K2 }- r T4 n6 T; ] D
- }
4 k/ d4 n F9 _0 l7 X - * Q% }6 o0 D+ d \3 \ _
- else/*如果链表已经建立,长度大于等于2时,执行*/
) @, u8 Q2 N7 n
, b+ |5 G, r2 b6 F- W2 ?: A- {
% L0 Z- P, b; L+ J - 9 d9 K: [3 m9 z* Q/ Q v
- pNew->next=NULL;/*新结点的指针为空*/$ c$ f: h1 t- p% l
- : |" q1 S, I; T* C' }9 W4 _) o
- pEnd->next=pNew;/*原来的结点指向新结点*/
2 {9 t" k/ @2 W6 D2 u - ' A8 L8 k# g- `$ L% s6 `
- pEnd=pNew;/*pEnd指向新结点*/
0 ~9 I$ u4 l+ [1 z# p - 9 R4 o- m8 a- V' b: A5 y) @
- }4 k+ V7 u6 q6 _. v, w' d: G, b$ w
- + ~/ S" [" X6 z
- pNew=(struct Student *)malloc(sizeof(struct Student));/*再次分配结点的内存空间*/: `: j* E9 ^5 e& L$ T O% u: Z
- . t% W6 w: @& ]# m9 x1 i
- scanf("%s",pNew->cName);/*从输入流获取第一个学生姓名*/
- g* o3 `0 h( n4 W - 7 T* w* e/ m$ X3 P w2 _% g$ l2 J R
- scanf("%d",&pNew->iNumber);/*从输入流获取第一个学生学号*/4 b: \% O Z8 e2 Z4 c
7 }. d$ a& F! x- }
2 O- H! B8 \4 B1 T+ L g' ]$ ~5 p4 O - 1 d4 |6 d2 }( O5 i2 j5 |
- free(pNew);/*释放结点空间*/& v: g* k4 i3 w1 V0 V* K. L9 F
3 z0 ^/ ^! C' @9 D- return pHead;/*返回创建出的头指针*/
/ X8 U; x1 }7 K+ `# S2 m - ' f. u# B* W1 C5 e5 b/ Q
- }) t' j5 }' X. t" J v3 \
% h, X! N! C ^. u" ?9 u- void print(struct Student *pHead)
) N+ N8 L$ A" l, F; K2 } - : A( P# j& ]& S( f4 \. J9 R2 m
- {, a) F* r& Y* F; E# s& H, `4 E) ?
- 9 D( H( x; D6 k. I, t
- struct Student *pTemp;/*定义指向一个学生信息结构体类型的临时指针*/
3 r; z8 K" B( z4 N4 V2 w6 I! t; @ - " Z+ R! c( t! v& @& t
- int iIndex=1;/*定义并出事哈变量iIndex,用来标识第几个学生(信息)*/
+ n7 X# A6 p6 ]; ?0 f% F* [ - 9 o# b+ l4 {, A% O, y6 O+ Z# r
- printf("总共%d个学生(信息):\n",iCount);. N$ C9 ?% C0 J$ W8 z
1 d- Y4 u6 b9 l7 T( N/ _3 D- pTemp=pHead;/*指针得到首结点的地址*/
. }8 D; @: c+ Z/ Y/ e2 C - 1 K- f. C5 I+ R7 l9 T
- while(pTemp!=NULL)/*当临时指针不指向NULL时*/8 ]% H& Z0 C2 N0 P! h, k! P
! t x0 ^: T/ O. P) \- {
4 a4 S+ J$ ?+ H( f8 a8 P" }. f4 e - 9 p8 }2 h& V+ x# t4 _+ ~# ]
- printf("第%d个学生信息:\n",iIndex);
E1 D0 v# @3 _
1 S8 \" r+ _. l) d% c! i- printf("姓名:%s",pTemp->cName); /*输出姓名*/4 ?# w+ M4 C! ?1 u% q5 B5 ~3 @
/ i3 N. I" D- p- printf("学号:%d",pTemp->iNumber);/*输出学号*/
- @2 t, f/ t" R! h; C - . {0 T3 [2 l `% l6 x1 }
- pTemp=pTemp->next;/*移动临时指针到下一个结点*/1 V7 T9 J1 c: ^- A0 A& Z6 C8 W
- : K: Q9 ?+ [' p8 e
- iIndex++;/*进行自加运算*/
" m0 m9 ]$ `6 b7 } - 3 }7 k/ m! {% `' e
- }
# J: l( f1 I \3 r - 3 ?2 o' _% `7 g
- }
复制代码
$ 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
- int main()
; E" ~0 G' ~( Y2 g% g - 9 p: s+ k2 y3 U I/ I
- {& X7 q( A* W; c* N: J/ e1 \
- * D5 @9 A' x- ]7 B" U7 F+ v) R# o
- int insert_n=2;/*定义并初始化要插入的结点号*/
2 \$ ^3 E! a* ^7 V8 Q
% A l; C2 C7 ?0 t1 P- I; b8 J- int delete_n=2;/*定义并初始化要删除的结点号*/* o6 X- k8 Q' a$ F5 h1 e1 J3 v
- - _: y$ a/ z2 e
- struct Student *pHead;/*声明一个指向学生信息结构体的指针作pHead为头结点传递*/
: g. x4 Q9 w$ v u5 G6 L# T$ E; i - 4 O- ~' r; m4 Q$ O: U! b4 P
- pHead=Create();/*创建链表,返回链表的头指针给pHead*/
& Z- }" b* X; O5 P6 M - ) }# ]+ E( u4 U* o, ]1 P6 i
- pHead=Insert(pHead,insert_n);/*将指针pHead和要插入的结点数传递给插入函数*/
" G b% V7 I& `* u
) N6 n- F* i1 p4 ?) {' [* O- print(pHead);/*将指针pHead传入输出函数遍历输出*/& n( f/ A$ L$ g7 u5 Z, I( Z5 a# C
+ Z6 h. W1 g1 u4 ^1 I% ]- Delete(pHead,delete_n);/*将指针pHead和要删除的结点数传递给删除函数*/
* N/ z' j# ~6 |( s
& @' u) E7 t, A3 O/ k& a+ u- print(pHead);/*将指针pHead传入输出函数遍历输出*/' a8 @* q1 Q. c% y# T
- : k) G& p5 R, V; M1 _0 h, ?2 Y& B
- return 0;. G3 i6 s5 V, Y6 f% M/ {
- * ^$ n, ^9 T7 p; q; j
- }
复制代码
& 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- struct Student *Insert(struct Student *pHead,int number)' U+ h7 y- t3 p
- L4 e3 _( E# t2 [9 p* y( s- {$ \ c8 A4 p& P: w5 v @& T/ d1 Q7 {
2 \; q% ^! P$ B: y* {4 r; k; z- struct Student *p=pHead,*pNew;/*定义pNew指向新分配的空间*/. w% r, l8 n/ ]3 @9 K; g: s
- 6 x3 |4 G) H# i/ D
- while(p&&p->iNumber!=number)
4 h: z& a5 B1 }+ K
( \. Q, i1 q- c- p=p->next;/*使临时结点跟踪到要插入的位置(该实例必须存在学号为number的信息,插入其后,否则出错)*/! x7 ^6 r$ t, }. x! Z
- 7 S- K; `! r9 k Z
- printf("姓名和学号:\n");
7 B# H& c! _7 p# L
5 f U0 r1 n |, G. L5 P- /*分配内存空间,返回该内存空间的地址*/
7 R& O$ p& W9 }8 _9 F% C/ m, v - * G+ A: C& U! j e3 {0 n
- pNew=(struct Student *)malloc(sizeof(struct Student));
) i3 b8 N7 b$ c7 ?8 w
/ H2 o! U) J+ {% |- scanf("%s",pNew->cName);) r% V9 O2 L2 x r o4 k3 \
- + [( r# V* w! s
- scanf("%d",&pNew->iNumber);
K" I8 ?! f2 d4 M9 X4 ?8 ~' n6 n - 9 E R Y1 J1 v# {: R1 r
- pNew->next=p->next;/*新结点指针指向原来的结点*/
1 [ u# y3 w# K* ~9 o- d0 `. ~" |
0 J* a; w0 c6 h* e0 R- p->next=pNew;/*头指针指向新结点*/7 Q- T% j8 @8 j0 k6 H3 m+ z$ s* `
/ k8 f; o% ?% b- iCount++;/*增加链表结点数量*/
9 |5 y& f7 d4 q1 w4 t- `; o+ u - 2 y7 e( a! n F4 Z
- return pHead;/*返回头指针*/
: I2 }4 U) r+ E. N5 x - 5 T' Z$ T$ A5 y' d; W
- }
复制代码 % 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- void Delete(struct Student *pHead,int number)" J, x$ L; E% j. B+ I) L+ ` @
6 X2 r, g n2 w! z- {" B4 O. o6 P: R; E1 S
" h; ~/ B' c0 K' k- int i;+ R5 F/ D* e. ~% _- u
* k# t, t y$ K/ n- struct Student *pTemp;/*临时指针*/
+ N4 ?* o2 ]1 u& X2 m - 4 z) v/ U4 Z- g% _! k
- struct Student *pPre;/*表示要删除结点前的结点*/
7 I9 P+ O! u. E, L3 | - S% R) s1 K- V- F; b9 `
- pTemp=pHead;/*得到链表的头结点*/
% \3 {8 ~* h2 {" Y) @! l+ a" ~ - 1 _, T3 ~& J% |0 J% S% x* c* d
- pPre=pTemp;4 y5 J2 Z' i- i' M, {' ]5 N( D
- , V2 _1 g4 \" q; L) A5 i4 A0 s
- for(i=0;i
0 e- u3 T, P& b6 G o - h/ D9 M, L5 K- Z& K5 i
- {/*通过for循环使得Temp指向要删除的结点*/4 {( y9 _0 ~' Z$ o) i+ j7 a$ m
- 8 O" Y+ I z: F" K
- pPre=pTemp;
2 o2 h! k; j( V6 W9 u
- }5 H! F* n5 ^3 ^6 O7 b. _8 g4 P4 v- pTemp=pTemp->next;" }& F/ O( o% x# F/ R) _( Q& l2 M- w
, x. J1 t% C. u+ p4 v$ v* Y- }/ {2 }2 _+ ~# |7 G# `- p4 ]8 Q0 \
9 r7 B# p8 ?/ r; Z" A: C# e- pPre->next=pTemp->next;/*连接删除结点两边的结点*/
9 A# T* i6 y6 ?2 m) h* H6 v8 V1 ]7 r
! F: t1 f% c6 ]1 F7 Z/ q- free(pTemp);/*释放要删除结点的内存空间*/
8 l" C' [4 z6 s# J) g - i% z1 q5 ~6 }" X) K/ I$ c
- iCount--;/*减少链表中的结点个数*/( \9 u; g9 L' [) A
6 [0 w3 _6 C7 z! j- V" b7 p b1 H3 P. [- }
复制代码
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- #include #include
& U) k2 w1 n3 N* {( y; R' _ - , v- U8 ?1 U/ z
- #include4 q% }, d+ i9 h
- / h( i. ~3 Y/ {! H8 n' \
- #define N 109 Z2 Y$ z5 _0 G( ?2 x1 q* B2 d
* I9 O4 O. {( g( e3 J* B7 F( v- typedef struct Node3 d% ^3 u% d% ~, ]# _4 w
9 ]- `- S& O8 x) {6 t, f- {
9 `, m, y0 {& a; m, Q9 w
% f9 t3 X) v R8 z- char name[20];
: ^9 v8 F3 a9 w5 x1 d& I
- z9 y; n/ w f/ U; u0 b* V U! m3 D+ @" f+ T- struct Node *llink,*rlink;: r4 G1 W. ]. Q& G+ w# P
- ' v, P3 p6 ^# e5 s& t
- }STUD;
1 S/ C' Z9 f0 Y# V; h. L
; O4 k' Y) k& d L8 d, V3 v. S- STUD *creat(int);void print(STUD *);3 B, j9 |1 d( J7 E" G
- 1 A: G; p* v( X2 E0 |$ l& p: v
- int main()* m7 r9 q# |- z, @9 e/ L9 O
- 6 \- o! f4 z( q) U, D
- {! b g8 ~+ q6 m6 y
( H, J) O6 S! Z: Q) Z- int number;4 z9 U! r: I, C' p- Q/ @
- 0 R4 U$ T* [' K. v
- char studname[20];8 E! `7 Q% v; z
- ) S7 g" d6 ~( e+ M
- STUD *head,*searchpoint;
0 g7 d% e- ^5 k7 S
9 S: K. V: A8 q, m$ _/ t- number=N;
; v! f5 v# O& R5 p' X
# y* i; V, F6 @7 [6 n- head=creat(number);
/ T) K8 ~; r, h9 M - & K' n3 ~) @6 T: J9 j
- print(head);- u$ l5 A F- w
- , Q! [$ x2 x- W% ~0 W
- printf("请输入你要查找的人的姓名:");
8 g. Q; o& Q$ \7 V) H- D6 ^
2 W1 b9 L7 U r+ y$ \& ?- scanf("%s",studname);; F- [. x6 y" ~; z7 P: _1 A( J
4 Y" Y9 A% |; B( F/ E# }8 w1 o- searchpoint=search(head,studname);, x1 P. e3 a: r$ [ W% j9 j
$ O% a( i3 {4 ?% c& Z0 U- printf("你所要查找的人的姓名是:%s",*&searchpoint->name);2 N' s2 ^& S% N x
& t n& e* A) t2 e9 S* K. |- return 0;
+ j% Y4 G, n* b- `, `
, N2 g3 l+ h4 ^4 N7 m- }# H L5 U" o8 j. _1 [8 Q
- . k. _( W" S# ^2 A5 N0 Z
- STUD *creat(int n)" i0 `- c/ V: C7 Q2 r; J
0 c i" m% ~9 h0 I0 d- {; r8 p a6 ^9 \! F. y
9 J- L0 x8 U2 K; G0 @1 ^3 N* d- STUD *p,*h,*s;
: m2 n6 h! r: c5 a2 a - ! H0 G& n9 D! ?) F, M: U
- int i;7 V' `- q& G1 d- T
& o% _! f$ O4 ~+ K0 L X! k4 q- if((h=(STUD *)malloc(sizeof(STUD)))==NULL)
( `8 w) N s. Z! S% v
t) f8 X) }" N- {
3 e) C7 P6 k; K1 B
! h# N* z. V9 a% N- printf("不能分配内存空间");9 t5 M& X% W& v2 C
- - |6 `& x/ x: u+ c& {
- exit(0);
9 y) S" D: y8 [) r' p4 i$ j+ ]: c
3 E% N" ]3 |8 d: i$ A0 v3 m- }
, M1 Q \; V3 T$ w z4 n3 }
! Y0 U8 s) \5 L, u. o" z8 d- h->name[0]='\0';
2 F ?, R1 O3 q0 o - * a, M% P6 Q' {3 m1 }* n: |
- h->llink=NULL;$ s( x* }8 g* F8 _7 p
- 6 ]; J9 i9 A, ~' N: `
- h->rlink=NULL;
+ g. k, w/ v( s9 K( W
6 w. ]% N- B) e, d- p=h;3 z, T1 h3 }6 _( Q6 k
* ~8 Z3 H0 l K' O7 Z! Y- for(i=0;i+ X' z1 v4 r- n% ^5 l! x$ U
& _( {$ p2 R* I; R- {
# h6 n/ G( i( ` M1 s3 R - 3 y$ t& O% w' Z
- if((s=(STUD *)malloc(sizeof(STUD)))==NULL)
, y6 l/ f! I* w$ T - ( t8 m2 W9 Q; U' b% u0 x* a
- {5 [; u- ^6 N! p+ L$ t4 v
- 1 @+ i, _5 i% X6 H1 v
- printf("不能分配内存空间");
9 l0 V5 F, l8 l" t4 J( Q& u - & \4 c9 C8 V' P' o) v0 s
- exit(0);
* M2 D- o4 a7 u/ R - & Z- |; w' y7 N. B! ?
- }, c( T( z& r% c2 t
, i; E: e/ q* O- p->rlink=s;- _1 g' {9 @" T; n
, u1 G7 a( H+ \# \( Q1 E+ j- printf("请输入第%d个人的姓名",i+1);) o% ]/ Y6 B8 ?3 Q: T9 p6 n
- * m/ a" w# ?5 k: H M. S) ~# ?8 g4 \
- scanf("%s",s->name);
6 X# t) @4 P5 Z# D
! L# F8 h# C- _; @- s->llink=p;/ z7 P5 N* t. }3 s0 C
- + w0 V7 F5 {0 y& S
- s->rlink=NULL;
, S; N# z7 C4 ?$ _
; F4 H% L) f, y$ p" X% e- p=s;
, ~* X4 v6 [! d8 c. `" s
0 Q: y4 R. e9 _) L% [0 b2 c7 A# ?' p- }
3 B" |1 ?1 c- n+ R1 _! N
/ M* n M5 O+ T [( F8 ?& X6 N x- h->llink=s;8 k# }! C7 q w4 j3 T! B8 A4 A% P. Q% [
- : F+ l1 M) ^# B* v1 q0 N d
- p->rlink=h;
# w6 D4 P2 l5 b" f$ k& _. G, C3 P
3 u' O* C: y& r4 [ J4 I3 o) c$ U$ w- return(h);
( M7 h% ~: G) u* Q5 B - 8 a, s7 O& \* P. \& a& K ^' A
- }void print(STUD *h)
2 L, ~2 B) ~; J: w# _6 z
5 m/ _' s1 t% E/ D- {% U+ m; J- O$ H6 v1 O
+ A/ y) ^* \8 |* Q9 u- int n;
8 c3 U1 v. W7 F$ m- y* ^
3 D, u" U' A! P! x, r. ~0 y- STUD *p;. r- w* Q5 }# S! C8 k6 D
- , L9 ?% `' t" W4 k! t! Y
- p=h->rlink;
- ]; x9 B- q1 z$ r2 M" v - & n( v `0 E* c
- printf("数据信息为:\n");: ~. U3 A. f3 X
- 2 d6 R! X. u& b+ s
- while(p!=h)( b; M! K4 w& G J, G
7 Y' V) c% P, z$ g0 v9 s/ Y- {
" ?3 |7 n7 u. q ` - 9 l7 m! N3 e, W3 `# i
- printf("%s ",&*(p->name));
% k% g: j. a" p, `% p B - , _$ w5 T6 r+ {. ~- p" }8 n f
- p=p->rlink;4 m# L n e: O/ o) {
f' ?8 ^* W: s( Q% y$ _/ \- }
/ d$ W/ ]0 T, B5 j9 M* n. N5 \
+ }4 ?5 [' a8 I/ `: v- printf("\n");5 V( K% l+ q9 P+ n5 Z. Z# W5 l
% A1 R- Y# i; F: E. o6 C- }
复制代码 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 `- STUD *search(STUD *h,char *x): J; b6 ^' s5 c1 j, w+ n: D3 C
$ @/ v7 q6 ^3 b3 f' s8 K# `- {% H! @7 W7 F0 N, {* w: D) A5 ~3 |
9 j) y Q; {. w8 V" t1 Z; P- STUD *p;) M% e& h" P3 I" W' R, { o: u$ Z# I
- - F. {/ K; p4 a3 Y9 p
- char *y;4 A3 Q& O; {8 t- ` h6 X! f
- 5 a- U# H, u; i, L4 U
- p=h->rlink;
8 [5 k6 z( m/ t4 A) X% E - 1 v+ e. T, R0 e% D5 t. p# o; r
- while(p!=h)7 p& r/ z- w, R: ] O/ v& q
1 g r1 u, [' t- {% ?+ o2 M# ^# H. ?8 C+ q% j x5 H' Q
- 4 h) K! L1 |% v0 X) H l2 {
- y=p->name;
6 f9 @5 i% Y4 _% Y! M, O2 I) t! z - 8 v5 {3 k3 _' j) l2 z
- if(strcmp(y,x)==0)! T! V! Z, o6 O
- d' J3 {/ ~: B0 f1 l* }
- return(p);
9 C, Q3 y. b- T/ n4 o! B+ k8 j
% K1 d- ~' t) k- l- else$ L$ z0 n. E7 f
; p' c6 h2 K4 v# z" D/ L, e! p5 F- E- p=p->rlink;
6 z8 A' o5 _* Z, P% S% Y# Y; L
! Y0 D- p( I& l( M1 F9 y4 Z- }
! R5 s$ \6 U+ V- ^
" L j b& f" b- printf("没有查到该数据!");' I# x6 H$ C4 y: B* c0 _8 E
! P* l% l% J- V, M$ ?- }
复制代码 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
- void merge(struct stud *La,struct stud *Lb)8 ~( H# @, T. B; O2 k9 g2 Y( q
- - W& N ~$ d( \& l2 F
- {1 |9 k+ c! |4 x" N+ L, N5 }% c4 g) S
- 2 C1 S s. n8 N+ L2 G/ `% ^8 u- h8 ?
- struct stud *a,*b,*c;
4 D3 g. X' \7 Q% O
3 o8 P+ U; k( G( @! m* @ m: v- c=La; c( A2 ?; T0 g$ J3 t5 m
- 0 [( C& f% C# C7 ]
- a=La->next;/* 合并前 */
+ B9 e/ J* X4 c9 j6 {# y- n
0 m7 U4 T* x/ h/ M- b=Lb->next;& j1 U9 Y. c |- B R9 d) Y8 B3 a
; h$ g; H( C- ]- while(a!=NULL && b!=NULL)/* La和Lb都没处理完 */
; s3 q2 u9 E3 B/ V- } C5 Y- d - " P9 e) I' e: s& d$ g0 H1 F+ i
- {
! G# J2 J x0 O' v9 }* E# k4 |( \ - ( }7 C2 G, i6 j
- if(a->num <= b->num)0 `! i! E$ w3 b. T7 S& N) i
, q) ~6 k x4 t& w- {
/ F- ]5 x$ B0 m& t6 E3 J - , q; Q3 G7 T$ `( Q' m/ ]" b
- c->next=a;9 j7 o3 {% K$ s w! `" J: v
- , I9 t$ ]+ ?1 R) r$ s% V
- c=a;
, `/ H2 ?" y8 c8 n - ' R8 q# T4 L; b( b
- a=a->next;. l$ N4 E8 q0 W- B6 ~5 K
/ z, C/ H" k5 z5 }- }
& w. E$ I6 E- _4 w3 Z& ? - 5 F2 W8 `6 p3 q3 p3 c
- else, [( F5 T4 P; @
- ( w( \; H# w- v+ u% \7 P
- {! g* o4 M( w4 e
- 5 f3 j, i: e7 n
- c->next=b;
% ]4 S2 ~9 l# U6 l4 u) ~
+ [& P4 T8 ?+ j, `* V$ n6 F- c=b;
, S9 S. y8 O4 p C9 S
8 ^# }& ]3 D3 Y- J- b=b->next;
6 V1 I; w" p+ o. n' O/ i3 | - 4 d7 d9 ?- M7 X8 l
- }6 \# P, g r2 l5 x h: n! x* S
1 u5 _' q: |+ J4 g- }
+ w0 E; B3 F5 K" Y - # m* [0 {& ~7 w9 ~. z0 C
- if(a!=NULL)- X4 ^! x4 o; V( h0 z. L* ~
- 6 \, N" b/ p7 T1 X5 A
- c->next=a;/* 若La没有处理完 */5 @% X; H; G! t2 O
7 K! h6 L8 ~" u# `6 S0 R- else
% L) k6 H; B, X9 |" M! @9 a - 0 |6 J6 |2 q. S3 ~) {; }* L2 o) ?
- c->next=b;/* 若Lb没有处理完 */* `9 b6 i6 |& e% a
- 0 [! Q5 O, B+ _& ?- h. f
- free(Lb); /* 释放Lb的头结点 */
* [ S0 f- C" `- U - 2 y& @8 p* v3 m u
- }
复制代码 ( W3 |- B; T9 R9 v& E8 ]! Y
5 D7 c0 L/ \: ~" H; E7 c4 o/ O; m! E" s% \
|
|