- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 563412 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174246
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
`) H, q8 a) r: ]5 o# P线性表顺序表示、链式表示实现方法及其异同点
2 L! K0 [& d9 j& y- {( D4 {线性表是最常用且最简单的一种数据结构,按存储单元排列可分为顺序表示和链式表示两种方式。( @/ S) B$ O# d J
/ S% T$ s; V1 ^/ T& ] a
本文采用C++实现两种表示方法。. x! w5 j- \" B7 i; R" M) s% Y" i
8 |" X6 B3 M5 _. P2 `: G4 Y7 ]" Y
目录
& o: }- r0 A$ a3 f# B- t& D4 A1 w% p. M! ?% r# i! ?
顺序表示和链式表示的区别:. K7 x3 A9 Q/ m, A0 p1 ^
- I! w; |' G, _0 {4 Y5 B
创建方式:
0 r; ^, J% u' c; ` s$ y! W, I# m( n4 @- q. J: S
时间复杂度:, n+ _+ M6 [( r4 g
8 s1 z" u- G" l. L! Q7 Q3 F
顺序表示和链式表示的相同点:
; `1 j) L' K2 }1 s- b$ [+ g
) ]) f( J/ C8 r删除内存空间:
3 _# X" o. o- i, [& ~
' g$ }' {) k, }, `2 p; h3 R代码实现:1 ~% `+ D' N& q) c! Y4 X
) v; R) u4 B2 X1 r顺序表示方法:
' A" H: h! q! b2 `: G9 |
- y& k7 q) I; q3 q7 l6 z9 ~" K: H结构体定义
& a# e0 V- ]1 ?3 k# L9 q! Z0 G; u: S: R, a6 ^5 l
初始化
* f- i5 O( j% k
4 E% ?5 W' I4 m增加元素
+ z! q4 X: v% ^- p. P m5 w- ~' |* v! C1 e. {
删除元素
4 b6 l: O: j: ~- B
* N! i. I/ ?; b' V销毁列表
% F& u# _1 U! `# E3 q- Y9 Q7 S9 a& B; G6 `. n
链式表示方法 r e! m5 d! @7 x
h. w4 A8 S j. D2 p结构体定义, g# Z7 F c/ p
" X4 @3 q# f% `, b+ g, \$ {% X2 H8 h
初始化
J3 C! x1 T$ J( o ?4 {9 s( h5 y* g& l3 }
增加节点
' A; A3 H+ o) B1 v4 r: t. g: t) N. {" C
删除节点6 H1 W+ p5 ?" l! a7 {7 o! Q: S
, x# `" z. h: j显示链表0 c$ U$ R4 o" E, F' I/ t/ y
* j% @5 `: L; V" ?; z- }销毁链表
3 h6 X [4 C* X/ B
: G0 S% f t6 N- j顺序表示和链式表示的区别:, o8 M- S6 f% w$ z6 x/ q u
8 d& m% ?5 e1 f! P! u# L: P+ i# O
创建方式:
7 V% g& N1 Q: @
/ G6 b) o; R; @9 i- E7 M2 ?顺序表示方法单次创建多个存储单元,相邻的元素存放在连续的存储空间之中。
; |/ {+ F- \$ f) W Q' z6 _: R q+ h4 h: ?: k. k
(PS:内存空间申请请参考https://blog.csdn.net/Baimax1/article/details/105954552)
: _- y) r6 w: E7 l9 z9 b" R/ I) v5 Y' V9 M
链式表示方法单次创建单个存储单元,存储单元之间地址不一定连续。存储单元包括数据部分和地址部分,数据部分存放需要保存的数据,地址部分保存下一个存储单元的地址(单链表,双向链表的地址部分同时也存放上一个存储单元的地址)。
; D. k0 d9 _+ r8 a7 l8 |2 V$ z! o; o) P* g2 g5 |2 s8 P4 V
时间复杂度: \" g$ ^8 i/ D
. L7 }3 p) ]8 J! x* G+ f, S
增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(1);(PS:在未知位置的元素前 / 后操作)
5 j3 _/ Z# k G7 e) q8 @; U5 S* O5 G" L/ X
增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(n);(PS:在已知位置的元素前 / 后操作)
2 d9 N# L8 J8 K+ h& t( g I/ h- S, P! Y+ I
PS:顺序表示需要将元素一一后移,链式存储结构需要查找该元素的位置。
4 ~& ]; l3 r& n3 D( S% H2 O9 ?5 ^* l1 Q
修改 元素操作:顺序表示方法 O(1);链式表示方法O(n);
" h, R4 K! P( ^* Q7 z( I" J9 l6 |+ ^7 Q) H4 f# `* R
查询 元素操作:顺序表示方法 O(n);链式表示方法O(n);
- _, m1 k( g7 m/ x' K. ]
; W% P/ F7 ^$ o) s9 \顺序表示和链式表示的相同点:" C6 c, N3 K- ~1 e, z% p/ I
) z6 h1 M `! l8 }
删除内存空间:/ j6 b( K u% {; ?2 O( h# d
( k" L: [# }- u8 [1 ~
内存空间的删除都需要对每一个存储单元单独释放空间。# |2 H" J$ {* p; I; O# v
! N+ R" Q7 q- e8 r2 g& \
代码实现:
: g' `& ]' \" O/ W5 O' |9 U
" |) D B- `7 s- ]% |2 P% H( C9 P顺序表示方法:. w, U: T- ?; P! t# b& w! g. U
- m3 v3 Y/ x# s$ Q# Z+ L" [0 }
结构体定义+ S, v- o; m" E5 ~* i* ~
]2 D, N/ q3 f5 qtypedef struct {
- O4 G4 H/ ]; V3 S* r# U ElemType * elem;
+ D( K6 d% M: z int length; // 线性表的现有长度 # O( \' ~" [( Z# ]# ]
int listSize; // 线性表的最大长度6 n, z8 L* K8 t
}SqList;
; L; |& W9 i% H- H! v7 |& a4 R6 s% j) d. D
2 D! |! s- @' O) X' b3 \7 f' d! e初始化
k% B# O( @, V6 O+ x# u6 }$ ?2 x
! z3 Y( e, j' Q! Avoid InitList(SqList *L){3 K. D3 Y i; k6 z ^. P; v
L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)) ;
5 [+ g" q7 n8 k if(!L->elem) {
. F$ L0 n4 G# Q1 B. j cout<<"申请空间失败!\n";
' J* J# @, J @0 F" V N- n DestoryList(L);' H( [5 x5 J) c+ a5 p: b
}6 t: Q3 I( C# b( R
L->length = 0;
1 L! q. L J" C3 i: H. \ z L->listSize = LIST_INIT_SIZE;2 o z6 Y) n# J( X) N) F
cout<<"线性表初始化完成!\n";
) @* h* M, ?; `8 ?: V- Q2 f3 B}( [6 V/ _7 O/ E- C. q# L: {* ^ J
4 j6 L5 P# s) ]
增加元素. U# f7 s( `9 n) i, Y, b
4 J- j- J* W- s* {7 n" O% J1 P3 w7 t' m, p
void ListAdd(SqList *L, ElemType e){ //在末尾直接增加元素
1 ]3 n& S( q' z+ a! a" ?6 O if(L->length>=L->listSize){
( \0 g" X6 V2 {1 ]2 o6 n# O L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));! X1 X7 p' l1 S7 _) p
if(!L->elem){
1 ?- Y5 w5 h' Q3 c# Q cout<<"增加空间失败!"<<endl;+ h. k" A4 h, i5 n6 _
DestoryList(L);
0 A' Q2 M9 Q! L! ]- A# v# e6 | }( B+ Z- w) i5 D, v) X* ], D8 g5 p
}
3 O" J3 R) Q" X! E/ p * (L->elem+L->length) = e;" L/ B( C* F1 v; O
L->length ++; 3 h/ Y6 T/ M* }9 Q0 v- l/ S
}" z s9 g0 y% s9 ^
( H) h: J1 l% _* q8 e0 q' xvoid ListAddBefor(SqList *L, ElemType e,int e_where){ //在某位置前增加元素) A0 Y$ E- G! Z7 W" C
int i;
' _ i( W& i- ]( o* F L->length++;
4 L9 e5 M, X, y2 \% D& h for(i=L->length;i>=e_where;i--){: x( `# R( [9 \5 q- y3 s' d
if(L->length>L->listSize){% U8 b% w3 a( ^8 l& a* r5 [
L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));
2 O8 r$ W, r* C+ y1 f5 e if(!L->elem){
. N4 k6 c) `' t! J cout<<"增加空间失败!"<<endl;6 D. r/ w- o- `9 u, W8 L3 D% e4 M
DestoryList(L);
+ D6 a* O7 a) M9 v9 S; L }. H3 f& t. G3 Z, B6 K3 k
}
5 a @& r7 _# ~4 Z- |5 Q6 u *(L->elem+i+1) = *(L->elem+i);
3 R: E. R; |! a: A9 x/ |* I }/ \) q X4 Y; L
*(L->elem+e_where)=e;& d1 I$ A5 r$ Z' d& f% t. X$ t- }% \# Y
cout<<"增加后的线性表如下:"<<endl; " A2 {3 Q0 D- \9 W+ D( v, \
ListShow(L);( A8 P" d4 U; X. y
} 2 ^- S" w/ N/ h! z R8 A9 y) H
9 q! S0 h$ d6 ]4 d# h2 a
void ListAddAfter(SqList *L, ElemType e,int e_where){ //在某位置后增加元素4 O1 m9 v8 E+ V4 ^9 W, \
int i;% ~% A* B5 e5 f/ {- D4 J
L->length++;* N% T/ r" M6 K) H+ ~' U
for(i=L->length;i>e_where;i--){
8 n( I' n1 \) V if(L->length>L->listSize){; E+ |5 |' B: X6 i; l2 U
L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));0 k3 z+ v. u+ C. d8 ~/ {
if(!L->elem){9 i7 m" I; k: Q. I6 }5 v
cout<<"增加空间失败!"<<endl;' ^: B _& Q# C) r6 s: A
DestoryList(L); ) L" \- l4 f% e# ~ p0 j
}/ f r5 @% Z! h# w J) L
}% V, O- z2 l" \, `
*(L->elem+i+1) = *(L->elem+i); & v9 o0 Z' x) r9 w1 |4 H, U' K
}
8 e9 D/ _ {! r( R0 n; u$ j0 } *(L->elem+e_where+1)=e;+ C* d7 h# _6 { d6 q5 U
cout<<"增加后的线性表如下:"<<endl;
/ T/ r: J7 B3 _1 c3 R ListShow(L);
. w7 O6 N$ c5 B2 l! {9 R1 Y) l}! w5 R/ v! B, }$ k/ m/ i( e2 Q
6 w$ S2 D0 k. B9 ^6 _" Q
删除元素8 q' y0 x! l1 h7 n& I: L$ e8 w5 t) W- t
5 Y7 Z1 g! V$ @* g8 o
void ListDelete(SqList *L, int e_where){ //删除某位置元素
9 @. V% U# m) W; r6 x0 x0 A L->length--;) j. S. H8 l$ H! K
for(int i=e_where;i<=L->length;i++){3 W/ U; ^1 o8 Z2 H
*(L->elem+i-1)=*(L->elem+i);
2 t6 h" A6 h9 V8 n Z5 D2 w$ M$ y }
% \: L8 c; q# U1 t cout<<"删除后的线性表如下:"<<endl;
7 _, c8 [4 B' g- d1 o ListShow(L);
2 k+ N/ q# F( m- t}' a: l5 Q; T' a( V2 o
8 P# ]! j- ] ]5 T2 p" M$ n! Z销毁列表* D9 P$ Q( Y# Q9 Q% z
) u& {( r( A* a6 s" [( D& T% H" P; Cvoid DestoryList(SqList *L){
0 K0 B! ^6 a# L3 V, k, ` int i=0;
2 {6 k* ~. y8 M7 h1 K for(i=0;i<L->listSize;i++){
. F7 W, m. v' r" r. _ free(L->elem);
) a) L# v4 T4 k! R; a3 w5 }, {0 h L->elem++;
" ^5 ^+ M4 B s }2 h( m" z2 z. F3 b8 u& \
exit(0); ( C# G3 o- ?; {1 O' ]* L/ u0 J: w
}
8 ~) P8 k7 j! T1 t
3 n6 t. Q9 z" w9 d& s- k k9 I链式表示方法) b0 w2 c$ H) l% J8 i* Y' J
( o3 `, u0 ~( J9 `6 Y& f, a7 h结构体定义
/ |" F" B2 j, {) u% \% c" x$ v' h1 Q& ?9 S- h
typedef struct L_Node{
4 I4 {0 l$ Y5 }# ? ElemType data;, f6 E/ h8 H V6 `- O6 e
struct L_Node *next;
) n- b" z4 A- J, C+ e7 m //struct L_Node *last; //增加可变成双向节点
Y0 b, e1 g9 c( U. g% S Y {}LNode;
2 a6 B: h/ l$ U' K( ~1 Q
! x Q6 P6 z x- O0 Y0 Q初始化( ?7 ~/ M% o6 a3 e2 u
" A8 N" e. \, C) d2 U# S& G. c! R
void LinearNode::InitLNode(){
8 l2 _! j; |, t1 G3 Q HeadList = (LNode *)malloc(sizeof(LNode));
1 q1 y0 ?. G% m- n9 @$ p) F if(!HeadList){
T' A( d& B3 W( [ cout << "初始化链表失败!" << endl;
0 F; h \) R1 a/ n5 i6 Y7 t7 y exit(0);
: ^* s0 F' u! v" _ } 6 D" M9 R* `7 Z/ G: T, L( f; l: e& m
EndList=HeadList;
+ Z0 R& {: n9 z6 d; [5 E' _ HeadList->next = NULL;) Q# S' i, k$ D4 f2 R5 G
cout<< "初始化链表成功! 初始地址为:" << HeadList << endl;
: e" [* G U) |# [& @. V/ J8 H0 e Length = 0;/ U6 u9 X6 m" C% S* |9 X7 `. N; o* D
e_where= 0;
% \: d7 [5 M% T}* c& N3 v2 }6 u. @% s T! N
) C, H: o9 E5 r) e$ t% {) ^4 W增加节点; @3 k0 G: A3 I" b( }: w
* ~1 X4 R; m( a2 _2 Y$ ~
void LinearNode::AddNodeHead(ElemType num){ //头插法 0 ]3 _0 l% V2 J. j; I( {
node = (LNode *)malloc(sizeof(LNode));. e" f2 R( Q8 M: T& Q
if(!node){
6 V% w6 }5 ^- x# l) u# V5 X' O cout << "新建节点失败!" << endl;
) N0 N" k$ ?% H, C return; 3 c, a; U, A; ^& z8 R* `
} ; }, c. w* q0 b1 o, y
node->data = num;1 q" F3 V$ o) \# i
cout << node->data <<" ";; V* i; [6 W% w9 G3 m
if(NULL==HeadList->next){
: @4 G- \! T! e1 t% ] node->next = NULL;& A$ ]1 \4 N: ], L1 G, _ P5 f/ V
HeadList->next = node;, j1 x$ i" }2 q. i
EndList=node; i3 B* b9 ~; I3 \" N
}' b4 ]6 j+ _( t+ b
else{2 m5 n) B8 R# V! H. l3 W% S+ r
node->next = HeadList->next;+ `+ h# x* V% `' ^$ {$ a
HeadList->next=node;
: m" l& \" a2 ]- u& `, v% W3 F6 L }+ z$ m+ |3 e; X0 F. |3 Y* k- l
Length++; 9 M a* v4 C4 w8 @* w' R* _
}
' o# O5 o6 J+ l' F4 n/ D: c$ i/ {. J# j, U
void LinearNode::AddNodeEnd(ElemType num){ //尾插法
' k" _1 o# }' ~( m node = (LNode *)malloc(sizeof(LNode));9 W9 s% L4 ?7 ^0 d1 y
if(!node){# ~2 Q: Z3 P. G. M* D5 }' j* ]
cout << "新建节点失败!" << endl;
+ n/ g0 \+ c0 r w5 Y B& S return; 8 M8 S" W$ H4 I1 L6 m+ }* x" A
}
, _$ ^' v( M* F3 @1 e" t5 O node->data = num;/ c! Z$ r& [* n2 A8 x
cout << node->data <<" ";4 g# n/ p' L! U4 v* D* h" O; o
node->next = NULL;
* N3 s, `) B8 [* T. U0 ` EndList->next = node;: j* D" S- s6 i$ {) C S8 \
EndList = node;
1 k3 k) s% D* p( f; g; Z0 W. o Length++;
r G+ c/ P, G1 J}& h: J$ s1 j* u1 r& o
7 X& Y: I+ |+ J, l( B' ^( h0 D7 Y删除节点( m i. U. J' |* k& F% N6 Q
( m9 t8 k# F0 Tvoid LinearNode: eleteNode(ElemType elem){# g( X8 i0 A7 l& R
if(NULL==(HeadList->next)){
6 R7 a8 n8 Z2 y, P cout<< "无节点"<<endl;' n1 t2 u! A; W
return; * O8 o2 z9 b" K3 ]; U
}( J: c+ b$ z" }5 F, w# _
Node_cur = HeadList;5 g- L$ j' d1 g" } z3 }
while(NULL!=Node_cur->next){
7 J) q/ c# S6 ?. R7 g+ w, r Node_temp = Node_cur->next;
9 p% ` r5 ?/ u8 g) \4 R if(elem == Node_temp->data){
7 A3 k/ A1 Y% Z+ G; b Node_cur->next=Node_temp->next;
6 L# K9 w+ V& ?! G e# R free(Node_temp);
1 B7 ?: E% ^3 @ }& A2 S) z$ F( n! D. p4 Y
if(NULL!=Node_cur->next)
4 B: T: R0 L# ~& O Node_cur=Node_cur->next;) ?7 M/ r! C% X( \0 H1 \
}: E) d5 w" b- [0 Y3 R9 d
cout<< elem <<" 元素已删除!"<<endl; ! m. T6 i1 u, ^. c! ~
}
4 t1 E( R; w$ \6 K8 q7 J8 W
9 T4 S& r# T, q; \3 {显示链表- Z9 y8 M# V4 x" `' X. O
8 u0 p; w$ n: y+ m* m$ v
void LinearNode::ShowLNode(){
" j' g& E; V8 \ if(NULL==(HeadList->next)){) s+ E- [$ U5 w, E
cout<< "无节点"<<endl;4 B0 H. {7 ~) Z7 P" ?/ o( k
return; ( d* t1 N& g4 F, x" F" }( N3 \
}
$ ]/ k5 w/ V( l# \: [* g Node_cur = HeadList->next;
+ g1 {9 F6 g$ \) y8 A8 Y a& d: S while(NULL!=(Node_cur->next)){
0 ~% b" F0 X. ]; P' R cout<< Node_cur->data << " ";
$ Q# d1 F: M) i h; R, }5 y Node_cur = Node_cur->next;
) t% d3 E# f( H0 T }# P9 M" w: N) J2 S) {! C
cout<< Node_cur->data << " ";/ |# z: P1 o) Z' l# u
cout<<"链表中的数据已显示!!"<<endl;
* I: E# ^" |9 n. D/ O: n}
5 r5 K- r$ N8 v
- F) M' G8 I' `8 _& g$ z! D+ [销毁链表4 ? N+ o! p( Q
4 c- w3 t" F t0 xvoid LinearNode: estoryLNode(){. x+ K8 y0 z$ k' \. }# v
Node_cur = HeadList->next; 0 R# p; J+ A$ K; k) X2 P. H
while(NULL!=(Node_cur->next)){
9 {, e" U$ z" M+ D$ \' f Node_temp = Node_cur->next;
7 P1 j" @7 a! u0 [0 | free(Node_cur);- n2 c- j$ O7 c% P% I
Node_cur = Node_temp;
+ h' b4 t) U4 R/ ]/ P4 i }% S# C/ E- L4 u! ]5 f, n
free(Node_temp);3 q: B# g+ N1 V( C- d
cout << "数据节点已完全释放!"<<endl; + O6 r" m8 ]5 a+ ^
free(HeadList); // 释放头节点 & `: f$ u9 ?& P3 ~- F
cout << "头节点已释放!"<<endl;
5 J/ h* c, f, L. H$ Z————————————————
! I& s9 y9 O$ a" C. q: Z- |8 M) M版权声明:本文为CSDN博主「星河有鱼」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
( t1 i5 u& z7 X6 ^" [: v原文链接:https://blog.csdn.net/Baimax1/article/details/1060362869 I; u' f8 }. }8 R7 U5 K+ j# M
2 g, g5 f* \1 u% {' r. E! h0 N8 H* T
|
zan
|