- 在线时间
- 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年大象老师国赛优 |
& r, A h- f# [2 m
线性表顺序表示、链式表示实现方法及其异同点3 m7 B% }! |4 m$ f$ E1 y4 t- a
线性表是最常用且最简单的一种数据结构,按存储单元排列可分为顺序表示和链式表示两种方式。
& C+ \6 L, K, M( h$ m
$ Q5 b8 Y: @; ~* E1 b! q3 P( l本文采用C++实现两种表示方法。0 k$ H7 t8 u' U0 J
* p$ h$ m- t8 O# a8 B3 ^
目录
. C, b* ]) M/ R" K" I2 e
, u3 N. l' e3 B. w* k ]* Q1 w4 ?1 ?顺序表示和链式表示的区别:
- H/ k% M; o% Z3 j# Z
) f- _% ^$ l- [0 o+ z4 G+ P创建方式:# M) |# e+ P, Z$ J
$ c0 G1 J1 f7 C B R: f, O时间复杂度:+ s; {( k# B. {
3 K G% b" {0 ]4 B6 F }" V; \
顺序表示和链式表示的相同点:
& E$ d+ B+ W4 i5 `
# L7 o" ]2 Q7 v( Q删除内存空间:) _$ g; k# K* F$ ]" w
# Y2 O3 }. f1 M2 i! J代码实现:
3 z2 x& @ O% x5 f: @. m, t) S
" m* O5 z6 |5 r( q) r! a顺序表示方法:
2 }' j- V% a/ A! I7 i! R8 V9 t9 t4 l9 R( D. e: \. S- @
结构体定义
* L/ r; E% ?- v Y( M! ]4 v$ v9 D* n1 e# ?8 R' I- x( V, Z
初始化
/ x4 m& S6 _& Y) V& @" A" ]5 P: n* }2 k/ q1 T) ~8 {# h
增加元素
/ G. T# ^# z/ H" O7 Y
7 X' Z+ C! y5 x0 G" O+ [删除元素+ F# ?; D% u- n( h# y" b ^( O
" }. ^! u1 Y0 K4 E% W% \9 Q# _1 i
销毁列表' ]! ^, ]7 `+ Y8 T4 e D9 t' l
9 M4 i3 o" m/ z) f f0 g
链式表示方法
' d/ |# {. c7 y3 v3 `4 b$ p6 L: O9 ^5 u2 Y' c
结构体定义
3 l" \. v6 j: k+ h* a
: L$ \6 r" } ?/ p/ J初始化& [9 [4 C) m) Q
7 j4 |; @1 e1 o* F1 [4 `增加节点
# }& E9 O7 K) `% d
3 ~0 E. d" B& L- @4 R% \9 M4 D删除节点* B4 Q# C4 v& S5 p, c6 u
+ i8 p( d/ R4 u( X$ s% j$ N2 a% n, D
显示链表
6 Y% @$ Q# l8 Y) i1 N
) [- d' K8 f6 ^: Q. w! h( Q+ w ~销毁链表6 |! O: h' Q0 V" P8 e
E% E# Z6 }3 F3 _顺序表示和链式表示的区别:; k; u$ D. g8 i" S; W4 H+ ^
0 G' l# A$ q9 l创建方式:) w9 A* {$ J; u+ C7 q* z/ c; R5 K
8 t8 t4 J# K2 E; M# U- O# H
顺序表示方法单次创建多个存储单元,相邻的元素存放在连续的存储空间之中。
2 F1 E$ F6 ~; {4 P s3 }( r/ k1 D1 R$ G* H% E6 v( L
(PS:内存空间申请请参考https://blog.csdn.net/Baimax1/article/details/105954552)
, e- F, z% _# b; F2 c. K0 i
: H( f! D: Q% R" R0 I- P! l* {链式表示方法单次创建单个存储单元,存储单元之间地址不一定连续。存储单元包括数据部分和地址部分,数据部分存放需要保存的数据,地址部分保存下一个存储单元的地址(单链表,双向链表的地址部分同时也存放上一个存储单元的地址)。/ ~) A* o3 @+ g! A0 u0 j
0 Q F, t. }) {- {$ x: _0 m时间复杂度:3 p, X0 X8 C8 l: e/ S
. _0 e1 _: }1 e" P/ m! H, a* W$ B6 f
增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(1);(PS:在未知位置的元素前 / 后操作)
- e; C6 a% V' a: N; p+ X. R
8 j2 d" J5 P) t. }增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(n);(PS:在已知位置的元素前 / 后操作)# ]: w! l6 @9 W) v% r" g
( J R/ r- T- F5 p) C" t9 k, H- Z' b
PS:顺序表示需要将元素一一后移,链式存储结构需要查找该元素的位置。
1 C3 Q, ^% E' {7 ]" H" K' K
$ G" I, [- n8 w' C修改 元素操作:顺序表示方法 O(1);链式表示方法O(n);
2 W6 x5 C; y5 b/ C0 F6 t$ Q- t# ~ `
, [* ~( W4 m8 H3 F* a查询 元素操作:顺序表示方法 O(n);链式表示方法O(n);
. M% j, G' s; z" ]/ d+ V% Q; X7 G8 ~; u& X
顺序表示和链式表示的相同点:
0 O$ L' n% g" s3 C2 e
% i7 s" o4 q- ~删除内存空间:8 {& w7 W: Y! Y1 P0 u2 J
+ T& Z' l( @: [) R9 u( k! |* \内存空间的删除都需要对每一个存储单元单独释放空间。$ }! M! [) @/ |2 E) [% \9 M
) a$ w. N& o& N- a6 a' l- {: ]
代码实现:
) L2 v" D0 ?, n: D0 z; j4 {% c8 o7 I4 @& y
顺序表示方法:, H* Q6 b) a% ^9 d& N( C3 \
8 G9 n% J# }2 ~ ^结构体定义$ ^8 n; O f _8 S" W. e4 X( f
3 Q& P9 Z: b/ t( O& ^) ]typedef struct {
; o# l* Y" f2 F5 ^" U ElemType * elem;( ^/ V; f, V, J4 D
int length; // 线性表的现有长度
/ k6 R4 N) r \3 z int listSize; // 线性表的最大长度
- J) g& J% w1 F! a}SqList;9 Z, S; J# i9 e( ]* T
! O/ ?2 n' f6 n& T. \初始化% n2 ?5 ?3 ^ @1 ?
+ ^8 Z: c% \; P; n' j. ]+ P$ {void InitList(SqList *L){
, c5 B$ `; ]# t5 @' s! K L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)) ;: a* e) a; i- R% S
if(!L->elem) {
* ?* _. _9 j5 [1 m3 v1 P cout<<"申请空间失败!\n";
! ?" ?. D0 g- I0 u; S( W- P% ^ DestoryList(L);
0 i: e. {9 p: G/ D$ r }6 b/ |+ O! L0 t, ~
L->length = 0;
4 y2 F( a7 d+ {+ \3 c' Q L->listSize = LIST_INIT_SIZE;
, l/ _0 o4 c* |0 u2 e R cout<<"线性表初始化完成!\n";9 T& ^0 E# C* i m4 L8 o
}2 }5 i5 i9 M( w3 y% f) E# y& b u
8 p; s. D0 C; g$ ~- T增加元素
. ?1 I0 c7 {2 J/ y; ^3 Y+ c4 I0 V
6 e) j8 H* s( u7 E& X% b/ C* Bvoid ListAdd(SqList *L, ElemType e){ //在末尾直接增加元素
& v* a8 h2 p( c' K$ A% }3 b if(L->length>=L->listSize){% T/ r2 t* e5 |1 }
L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));3 i. c* Z5 G4 s$ f6 Y5 |$ k3 M
if(!L->elem){
! t5 k* w& K2 \% v- M' @3 m cout<<"增加空间失败!"<<endl;& J8 \- F5 F! h' g' H7 |3 \( I/ z
DestoryList(L);: ]7 j k4 _3 L( Y! K4 F
}
3 X9 ^( |; ] w }. V# L, N# `+ m' d( Y$ M1 v
* (L->elem+L->length) = e;7 F: Y9 ~/ E1 L5 Q; r7 u7 H' T
L->length ++; 8 _; g0 q( [" f" T7 j- v% A
}; Y$ ^/ O* k0 u2 b' X6 W k# D. m# f* c E
6 F3 t {( R# A5 }1 B0 K0 ^/ P" h0 svoid ListAddBefor(SqList *L, ElemType e,int e_where){ //在某位置前增加元素. j5 j! |8 ^, m
int i;
3 q0 j! M1 ~8 W5 N- v L->length++;
0 j! a* [7 @9 y- k" [ for(i=L->length;i>=e_where;i--){
4 O+ u8 e) J. m if(L->length>L->listSize){
+ x+ |* A) v4 M L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));" Y4 r- d% o1 h) F a: p7 O
if(!L->elem){# @0 S8 |# o" A/ [2 M6 Y( I- `
cout<<"增加空间失败!"<<endl;# B' p! D. c( P3 X* c$ }$ y5 G8 o
DestoryList(L);
5 z- S3 V5 `) i3 H5 b8 R }
5 |6 T: {( f# D u# e v }
3 s! ]( }! D0 o4 d# }) n) m4 `- O *(L->elem+i+1) = *(L->elem+i);
: b l7 b( E5 a* o |( K }* D0 r; I* ^. n* b5 }8 s8 y5 z
*(L->elem+e_where)=e;2 r& j# k7 l) v* e
cout<<"增加后的线性表如下:"<<endl;
$ P! H6 o) R! L1 y) J ListShow(L);
! o. {5 `$ A. Y5 X8 R}
9 F* {5 S# q$ Z5 X* q6 S$ \
; J4 }" {( @( d- d3 K6 \7 _void ListAddAfter(SqList *L, ElemType e,int e_where){ //在某位置后增加元素
6 l$ e; k% v7 l n, S4 A int i;0 ~4 c1 ~; e7 q% V o# z
L->length++;
' ^" k- e6 q6 i4 M: k! g2 p, a for(i=L->length;i>e_where;i--){6 M9 V# h/ H/ D, R- r
if(L->length>L->listSize){( q- y5 C6 A3 A' [
L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));6 ?0 D# h9 R/ n" R
if(!L->elem){
/ q9 c- o0 y5 ?& @ cout<<"增加空间失败!"<<endl;
3 S% |6 Q& p! l9 m! [ DestoryList(L); $ E3 p" O: N% b5 A% Q( i
}4 Q4 N: t1 s5 r" A# {; {7 B
}: }- A- j! [4 ~7 I6 Z+ {
*(L->elem+i+1) = *(L->elem+i);
- {$ ]7 S; C/ b7 P/ W9 Q8 f1 }! r/ C } U$ w& D4 Z! b9 s
*(L->elem+e_where+1)=e;
( b- R8 f% ? O8 r5 \, B9 o5 l Z cout<<"增加后的线性表如下:"<<endl;
" L; }% z q7 Y ListShow(L);
" K6 h, a D! F' U3 F}* K: N& i# a+ e! J' f7 m
& u# T4 Q* ^% v6 w! o9 W8 X
删除元素! m6 e! }* L1 q' Y% ~3 W7 ^% ^
8 k1 O' t7 z" e, i' dvoid ListDelete(SqList *L, int e_where){ //删除某位置元素 ; D9 e2 O1 Z% D9 Q6 a
L->length--;! }4 ]. `5 I/ n. U& y1 d5 W" a
for(int i=e_where;i<=L->length;i++){
9 I7 D: I0 f6 \! L4 L *(L->elem+i-1)=*(L->elem+i);$ E% b: t) B7 g" M6 P6 T
}
; S/ p7 y# T9 o; t1 L" Y cout<<"删除后的线性表如下:"<<endl; 2 Y9 s8 K2 S0 X& p2 _' d
ListShow(L);
% Y. Q+ {* g1 G* a}
7 e; A9 ?8 m6 D; O2 k* f
6 {7 W; e$ G; a销毁列表3 |+ n: C; {( T% S$ @; I# B4 |
+ d2 R8 r @# s9 V$ r& ]void DestoryList(SqList *L){
% T! v8 A6 I; v$ c8 ^" S int i=0;! `; s$ T% y6 ]
for(i=0;i<L->listSize;i++){
& W; V% Q& ~' w$ B# ?1 H free(L->elem);
]& T( @" f$ q L->elem++;% w* N, v: T2 p5 |
}
9 o) c: Z: \1 q. @- _5 B exit(0); 8 w; Y0 P7 d9 s5 v& s9 M
}
; x6 M+ a/ d) R
; L& n) @/ [* p( R" ? H1 g链式表示方法, e7 R9 M& D9 T% Y0 f& w4 t4 N
; u( w+ ~: T& L! S1 c
结构体定义2 R; r c+ G$ }
8 O2 e4 f2 {/ G' f) q
typedef struct L_Node{7 ]/ l ^+ s4 g9 o, A, ]6 ?
ElemType data;
7 P1 L0 \7 d( J2 \5 N struct L_Node *next;
& ]( ]. j8 M3 q% {3 \8 t5 D //struct L_Node *last; //增加可变成双向节点 0 X6 T9 r0 Q, b* H1 Q) |, D
}LNode;$ Q, _ k F1 S6 U; e
6 `. l( s2 E8 U. J& Y
初始化/ Z5 U/ O6 w0 M: l2 u; s( G4 D
. E# a- V A& A! z% I, A
void LinearNode::InitLNode(){
. T [+ c/ L8 l, C HeadList = (LNode *)malloc(sizeof(LNode));
, S8 Q9 b( E( L+ r f3 |; Q- H if(!HeadList){
$ i$ V/ P; S5 h6 m cout << "初始化链表失败!" << endl; * L! ^ {; l) y t% L
exit(0);
% W6 k5 h) ^# T- ]8 V8 x7 O }
: Y3 r; r3 J" e% s* ]8 m2 { EndList=HeadList;
8 v% W, k/ j! B8 p8 a5 U HeadList->next = NULL;
. u7 y% w o2 O( f: K" g, s cout<< "初始化链表成功! 初始地址为:" << HeadList << endl;
5 J! c* k# \( m) P Length = 0;& g1 n; S5 J# o( l1 w# t7 z: X, Q
e_where= 0;
% ^0 `# k% x2 f. V4 m/ Q _}
0 q! v4 f; k( d9 Y7 {/ p! g$ O y0 d. a" }
增加节点
. ?* j: c! T; I0 T
- p. ~$ A! k+ c" Bvoid LinearNode::AddNodeHead(ElemType num){ //头插法 4 Z3 M5 s$ [" j N( s
node = (LNode *)malloc(sizeof(LNode));! Q) d! S6 S1 H% e
if(!node){: q* |& D4 s3 p' j* P' l/ J
cout << "新建节点失败!" << endl; 0 g6 O; l1 g1 @8 j
return;
/ ]! l! M5 W2 v& ]# h7 b6 A }
, D% V2 U% i2 ^) z1 p6 u+ h, u node->data = num;) d& H- ?* L2 C9 g# \9 R7 p
cout << node->data <<" ";9 |5 n/ }1 h% y2 G; \
if(NULL==HeadList->next){
" U) |. I' J) E& M8 O9 e/ t node->next = NULL;' b8 P# r/ w, L9 S
HeadList->next = node;
4 ?- F7 k9 i( g7 [: k EndList=node;% `1 e8 N. ^' x9 g+ e
}* E m' d9 J- q; ^4 |
else{1 Y. J; r0 q& p$ ?
node->next = HeadList->next;
5 e# _ y- C, y9 Z9 k4 K# [ HeadList->next=node;* a0 Z& \! S O P2 I; s
} c& b9 c2 Y- j$ X
Length++; 1 V, r- w' R$ w
}; Y# v) A" Y4 @6 f
* g+ f& y7 z/ V- F+ H5 A9 u
void LinearNode::AddNodeEnd(ElemType num){ //尾插法 ! F8 w2 \% V( r! `( h2 `& Y
node = (LNode *)malloc(sizeof(LNode));
6 n5 s) v+ o& a. S' D, A1 j if(!node){' @9 g' ~" W* n) W2 _
cout << "新建节点失败!" << endl; # T) D5 v& c; B8 ~2 Y0 Z
return;
t$ ~4 p. X. c' K3 a }
, _# L6 s# C3 Z4 U$ Q+ v+ z node->data = num;( Y' e; R8 l8 x# ^( L0 ~+ A& z. K* k
cout << node->data <<" ";
4 H7 W" E0 C& V w' Z; Y* E5 k node->next = NULL;
3 G- n* g8 b! W8 ]9 q# b EndList->next = node;
0 ~5 C& a% n h% r# Y EndList = node;4 s& Y* G2 k; x$ O: V7 i/ x
Length++; 5 W( ^' e- K( Q) V9 l: n5 Q
}
1 l2 W4 ^* M; P7 y
3 q! ]0 O: ]' \+ D/ t" I4 C. o) `/ l删除节点1 j/ y- P; E; D2 G2 u1 {
- Y3 P$ O( E6 a n9 J9 g# J9 xvoid LinearNode: eleteNode(ElemType elem){4 W3 E. O) a" c: i! W
if(NULL==(HeadList->next)){' m# Z$ m. L! F) H" ?5 V8 G* E
cout<< "无节点"<<endl;- W C2 I8 r4 w& K; m1 d- U
return; , v( s4 _$ Y) s4 F% D# I- x6 V
}
# ]3 `* U7 s+ r+ M: ~ Node_cur = HeadList;$ L1 w+ D9 ?, u/ V2 l% b! u
while(NULL!=Node_cur->next){ r9 z6 m! r [# N! r% [0 Q
Node_temp = Node_cur->next; " B5 Y( R2 l$ ]
if(elem == Node_temp->data){
" u0 {) Z. ]. i" M+ b- X Node_cur->next=Node_temp->next;/ \. j% K3 ]$ D: W& ?% X* n
free(Node_temp);
L6 b. e' T, S# O; @ }
1 V) Y0 ^: s( {! E" g if(NULL!=Node_cur->next)' a9 y: t4 l8 b, \3 P7 ~- q: y
Node_cur=Node_cur->next;
, M9 \# }) ~8 j. Z) f }( Y R6 ~2 G2 k' e7 C: k
cout<< elem <<" 元素已删除!"<<endl; # G$ a! P O. d$ e0 C, ?
} ; `& w$ D n" s2 j c- Z) i
7 R- m5 X" b6 j- S( p3 H X1 w
显示链表% Y+ _, ^6 o0 L) x
! X% N' I+ z- }( _
void LinearNode::ShowLNode(){% O+ ]0 C# ~+ P5 W4 x+ G; _- ?8 I
if(NULL==(HeadList->next)){, Z* W1 d* P3 I) G/ }
cout<< "无节点"<<endl;, Y( A( o( n: z1 i7 ^% Q
return;
: P' l+ ^) W* p7 U1 I. |7 M }- t& I' c& ^1 B0 u2 z
Node_cur = HeadList->next;
/ ^4 l( F( ?( Y while(NULL!=(Node_cur->next)){
4 ?9 p* _% b6 a8 l, B/ U/ Q* d cout<< Node_cur->data << " ";: W9 L0 u$ J. y; _% N8 y
Node_cur = Node_cur->next;7 R! h9 n9 z. P6 G/ a; `
}" x/ ~6 b+ W. V0 i
cout<< Node_cur->data << " ";
3 }* f+ B$ x! Q- c cout<<"链表中的数据已显示!!"<<endl;, n2 F9 @5 r7 k% j
}& v. E. o6 f+ G! z- j* ~
/ {' T% @( y& s- @0 ?# x
销毁链表
3 p, o/ r" o- u+ ?7 Q5 e, ], k- W( y- ?, w" j( k" A& Q
void LinearNode: estoryLNode(){
3 _* n. i! s" |+ t Node_cur = HeadList->next; * g6 U! S1 G) R$ u
while(NULL!=(Node_cur->next)){( ?/ d3 C; v' r* P+ I' J* n
Node_temp = Node_cur->next;4 X, F2 E& `1 p7 L6 h: M
free(Node_cur);
. n. i1 f% ~/ d" ^; \ Node_cur = Node_temp;/ G2 o' V% t# j, h% {- v. [- {
}: S* O* r. w6 L4 [; X2 p
free(Node_temp);
/ _+ |5 L* s5 P& Z1 k) |$ K cout << "数据节点已完全释放!"<<endl; 3 ~; A; c/ h6 R/ p
free(HeadList); // 释放头节点
7 c$ z' T/ E7 { cout << "头节点已释放!"<<endl; ! l3 X5 |6 P1 S8 p6 ^3 x
————————————————
) M4 G3 o* L; G5 W$ Y3 u2 N版权声明:本文为CSDN博主「星河有鱼」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
4 u: b% N* r5 [; [$ x原文链接:https://blog.csdn.net/Baimax1/article/details/106036286
a7 b: j5 x0 ^" a( W8 a0 r( c, s. Q) T
/ h$ M w1 k8 u& k4 V" { |
zan
|