- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 563406 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174245
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
4 E7 a; R* D7 P: a( z
线性表顺序表示、链式表示实现方法及其异同点# k8 v, B' }9 q; J: b
线性表是最常用且最简单的一种数据结构,按存储单元排列可分为顺序表示和链式表示两种方式。
( n/ @! j O* T
9 U) F5 m7 E m0 b" V( Q. x本文采用C++实现两种表示方法。* i/ \& a& }( _( L& @- w
2 p. n7 b( q w$ ?. T- R! W目录
8 R* u" o1 \& n
% c2 V0 F9 _' {顺序表示和链式表示的区别:" G8 D, D: c1 i8 C v5 V
( ?. j! p( l6 c创建方式:
) ?& F H0 |2 O: s3 h# m
0 [% u- a' s+ A" C4 k' H时间复杂度:
% ^9 K) P$ V* ], B2 R2 _. r9 X6 ~* p/ _4 |! N, ]1 U) t) M& ^: [
顺序表示和链式表示的相同点:& U# v' H0 x# r: E7 p
" J- _- |3 W! O
删除内存空间:
. ?$ r6 ]' N$ O r+ v
N. ]! P# ]/ O3 D代码实现:
' I6 a! J3 l# H! U1 K+ [. H
! f% x0 i- d p* Q N: X+ c; o顺序表示方法:
9 Z( q2 v+ ^, {% K
3 \0 [* z& q3 H6 X- z结构体定义$ b" F& R X3 V, y4 f/ \
1 v! D/ X& s, p! e. s初始化) o/ p! I4 x" r4 S9 O# f, r
E+ H" s- l3 u# V& h5 I增加元素" I6 U7 Z U% b- H- }$ Y$ V
3 V* r9 H* S1 N- {4 r6 P; p5 s
删除元素, J* h$ l: ]' i/ j9 y3 d o1 ]0 B
* [# w, e- [) ~' l) F销毁列表/ J: Q# N; Y7 l' T
$ Y$ ?2 u* V; u" U8 P链式表示方法
# }8 x; X8 z7 h2 \4 X
% J/ h$ ~2 S6 u1 U1 g# w. F' {. ]结构体定义3 r$ j: H+ f; e% ~0 c
P' D* t U5 d' J5 M: |3 m, U初始化$ ?$ `1 P. e" a, f
7 o0 e/ R" T0 `7 z增加节点
3 `& q- V* y# P- X
+ D7 I/ v7 Y( v, i2 E0 m3 z删除节点+ {! Y( E) W% L$ m/ D
8 A% Q; u/ I# q
显示链表
3 h0 k4 {9 k) x* ^5 G' O$ W, K3 b9 {, y% n
销毁链表
* q( X/ D/ h1 p8 k/ o; z$ s+ b) S, C, u0 O/ l
顺序表示和链式表示的区别:# d, e7 @1 K% `. M
4 _- l8 w2 o; z9 S创建方式:- R, ^: D' V6 w4 H: G
0 y& Y# X8 w& w0 X1 s
顺序表示方法单次创建多个存储单元,相邻的元素存放在连续的存储空间之中。
4 A p S& D; b% u. D" ^4 P6 b8 r" b' _! H
(PS:内存空间申请请参考https://blog.csdn.net/Baimax1/article/details/105954552)
# }7 h6 @9 z3 X6 G8 R' n; \1 ^) L* ^! X' K2 ^. ^8 ~9 l. M
链式表示方法单次创建单个存储单元,存储单元之间地址不一定连续。存储单元包括数据部分和地址部分,数据部分存放需要保存的数据,地址部分保存下一个存储单元的地址(单链表,双向链表的地址部分同时也存放上一个存储单元的地址)。$ @# `, k$ v" Q9 ]- W j
0 L! Q- E5 Q1 U' _+ t
时间复杂度:
/ r# a/ \% c$ P( \
) A4 S( F) d3 V( H增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(1);(PS:在未知位置的元素前 / 后操作)0 L* F, ]- a5 G) U3 ~- i' B. D
D# ^. T# A( J" a/ {8 J
增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(n);(PS:在已知位置的元素前 / 后操作)2 a+ i" V' c" C5 V9 p, K6 e1 k4 m
9 i, g" ?8 K/ N9 k# p
PS:顺序表示需要将元素一一后移,链式存储结构需要查找该元素的位置。1 K3 L% O! N G% o% M$ s
1 K4 z2 R5 {* t# z2 n# |$ ^修改 元素操作:顺序表示方法 O(1);链式表示方法O(n);
# c5 o( ]) K' N; _
6 O! F( W8 Z* K查询 元素操作:顺序表示方法 O(n);链式表示方法O(n);# {- |/ A+ h$ W8 w6 b) Y3 z3 a# w
; ~9 F% m8 v* `; q# R9 \. y顺序表示和链式表示的相同点:
' i0 l/ j L8 I" K% I3 t9 d5 N7 Z0 W$ F0 x
删除内存空间:
6 [ q4 ?2 G& M0 [7 s
) L1 m) `" }* i% G( |, y内存空间的删除都需要对每一个存储单元单独释放空间。9 ?6 @ O0 c5 T0 y- x9 o, g6 }
* R. {" o" U0 W" w1 g代码实现:, F2 n; A" L3 ^% ]
) B( n: F! ^! R& S6 m
顺序表示方法:
) p- K$ x7 O& `! g: M: V6 d0 A% h
! ~% f6 ^7 u( `' n( f. _" g0 I结构体定义% V* ~/ Q5 U- a5 s4 w
9 q, s% W; C& R2 _$ }! I- e3 z
typedef struct {/ B+ | V. J) s0 {) i9 N
ElemType * elem;
9 T9 F4 o7 M/ [. I int length; // 线性表的现有长度 # a: f. F# S& `1 A' ?4 {
int listSize; // 线性表的最大长度1 V. d; D2 f! A5 V' N
}SqList;1 ~0 M" D! O4 R( W
, J( |" _7 E( t ?
初始化% s9 d4 T/ _4 L- I W
1 U7 y' E l' l; x- Jvoid InitList(SqList *L){, Q. ^7 N/ s* c% X R
L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)) ;
, E0 t3 Z, Y" J$ q& d if(!L->elem) {7 I; Y$ y( r2 H/ V* R0 V
cout<<"申请空间失败!\n";
. r6 I. g9 G( u( I DestoryList(L);
# k2 s" r* A5 J4 \2 V }
* V% m9 k( d" i0 w L->length = 0;) v3 V3 |! E) j0 X( e6 F3 |
L->listSize = LIST_INIT_SIZE;# B z3 W$ J/ K7 m
cout<<"线性表初始化完成!\n";
$ ?5 V9 [/ n2 {) y) n5 r& j1 m}1 L8 h' D7 C: _
4 Y5 C6 R& ~7 W, K增加元素8 j$ d9 D- |" e' b; G
) d* n6 P$ F, R, P6 ]
void ListAdd(SqList *L, ElemType e){ //在末尾直接增加元素: e/ t2 ^" L- e' S7 i8 s
if(L->length>=L->listSize){( ]2 c: y: R8 a5 M$ U b! j
L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));
( b" N8 j4 O1 p- G! d if(!L->elem){
) l. B& E5 x. n/ M3 @ cout<<"增加空间失败!"<<endl;4 b4 R! [5 n, y/ n
DestoryList(L);: y6 a/ b6 L: b) D$ d* G& b
}
" p- ?6 |2 `+ `$ W) Z7 H2 s, y }5 V9 ?1 b: s+ w* B
* (L->elem+L->length) = e;/ @. o, I v8 M( i" ]- i2 |$ J: R
L->length ++; 8 {# n# Q" ^7 X8 a- G
}
* @" g/ R8 [7 I- j; X( a4 Y/ q( L. g* s2 r
void ListAddBefor(SqList *L, ElemType e,int e_where){ //在某位置前增加元素2 S, e5 {" Z* T: [( `
int i;4 s* |6 ^+ A7 s4 E4 z4 t
L->length++;5 B4 h/ ^- |$ t4 W9 z; G
for(i=L->length;i>=e_where;i--){6 B. g# M% e. |& ^
if(L->length>L->listSize){
9 v" b( m S3 |7 X L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));
8 @2 R; I# E$ U4 b+ n* o if(!L->elem){
8 ?1 |/ v6 y1 v cout<<"增加空间失败!"<<endl;7 q9 Y2 G7 N+ P0 C) E
DestoryList(L); 8 L0 I! H& I' B
}
8 O9 `# y' s2 m: W }
/ L7 C1 k% P( {) `1 X; c# R9 v *(L->elem+i+1) = *(L->elem+i); & n& g! J. x) v7 r, b
}
8 D4 @0 A2 ?% d! G: K *(L->elem+e_where)=e;2 o8 Q! T3 ?& f5 @ \
cout<<"增加后的线性表如下:"<<endl;
! Z9 T1 e5 N5 Q% c- ~ ListShow(L);
% L( o+ F! a- o' {: p, L- r5 P} ( y& P8 B1 F6 R* u& m
3 t3 u% Z' S. _9 b9 w4 @$ {5 [void ListAddAfter(SqList *L, ElemType e,int e_where){ //在某位置后增加元素
# o$ x9 v( }! h8 ]7 u8 C int i;
3 y* l# M% K- w. R. ` L->length++;
3 Q0 R! Y% U! a1 h+ m$ K for(i=L->length;i>e_where;i--){
0 a t* o7 n, q; e if(L->length>L->listSize){
: N& v d4 a( `8 \! c" R L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));: ] {* H# }5 `+ n& N t% Y/ w) k/ y
if(!L->elem){
" r: ]' \8 r- k2 i. i. ] cout<<"增加空间失败!"<<endl;- L( E: D( h9 e" ]" L1 `5 i' Z# n( L
DestoryList(L);
" ^$ N, z; R+ o2 @ }
* m! D( w" F) [* y }- M" O2 V( J& w& Q' _
*(L->elem+i+1) = *(L->elem+i); / G6 E0 F4 p% `6 x* n
}& {' W6 F$ w' ^$ ~* z5 o
*(L->elem+e_where+1)=e; J6 b5 `1 ~, m" H/ W
cout<<"增加后的线性表如下:"<<endl;
1 J( M3 X- U4 b& ^ ListShow(L);
* ?; \. v* p& m2 k0 k. i}5 g) u: r( E8 f9 d, o+ Z' Q
8 B! u& w8 t1 T$ q" w
删除元素
$ t0 ~; Y! S7 i& u2 X6 ~+ \' `; J" U- a
void ListDelete(SqList *L, int e_where){ //删除某位置元素 & B4 J l7 _2 T% n
L->length--;
* V3 l" W/ E4 T8 h' I3 ^* A for(int i=e_where;i<=L->length;i++){7 p& @" G/ V# s, E0 z4 m- E ?
*(L->elem+i-1)=*(L->elem+i);, J0 c9 g$ J5 N5 a
}
) v y: t( Z4 I; C; q N: e" h cout<<"删除后的线性表如下:"<<endl; 5 w; T, Y; g- H/ e2 }* \& K7 T1 }
ListShow(L);. f$ K' V9 {& `$ \9 E9 T; |: o, ~
}
! }% B! {- G) I8 d# E/ u( m0 G+ [) H9 H$ c, a; x7 \# _
销毁列表5 y) t- @! k6 I2 h& _
" T, e/ y8 y, b' f5 M. h" C
void DestoryList(SqList *L){2 z# _, }% u! [- w
int i=0;" k# Y3 }% ?- I7 L$ U6 P, T
for(i=0;i<L->listSize;i++){3 B$ N+ e3 `- P6 t
free(L->elem);
7 e0 D7 @' Z- O4 I5 c) T( g L->elem++;
+ h. k4 j- ]; a7 ] }, H8 n' s0 j$ i" {
exit(0);
, ]6 H) \7 L5 N: _6 @* B}* d. Z* @5 I" ~0 T# R
+ T8 q% `! R# ~5 b7 }
链式表示方法9 j0 I5 l# m" E# X* ^
" m! M) J% L+ T; ]. ^$ L3 T结构体定义
5 |. d, Y2 k {) I0 ]. Y
! n3 P% k- N- j" I6 o# [, {typedef struct L_Node{; c& ^$ ^% U3 s5 p. O3 g
ElemType data;& c. U- V6 f' G; W2 z
struct L_Node *next;
* b. m( ~. M0 ]6 G //struct L_Node *last; //增加可变成双向节点 8 F7 x+ q' q' V k8 x# x
}LNode;
' r5 B: W( G8 ^6 K' b1 c2 `% }2 p
: n! e) N- R+ r5 X6 q$ _; C0 K初始化
/ S+ M2 V8 r" b! p( |! j& t* x! i) I4 T5 y" a/ s/ A8 v
void LinearNode::InitLNode(){
z \" P3 g+ V HeadList = (LNode *)malloc(sizeof(LNode));2 [" j/ c3 k# P, H! S
if(!HeadList){
7 N4 i8 j) D0 d cout << "初始化链表失败!" << endl;
0 l8 V# A* ~" P: j exit(0); ! S+ A: V1 O, I7 M1 ?
}
" T! B9 M9 P8 K6 I1 u+ `' D3 N1 ~" n1 l EndList=HeadList;5 b7 g* K; S; z
HeadList->next = NULL;
5 ]7 W! t% t# d1 q" x, u cout<< "初始化链表成功! 初始地址为:" << HeadList << endl;6 y# l- `- t+ _% |7 o
Length = 0;8 b0 l' x0 j" k1 J: O/ R
e_where= 0;
' b' a4 p* {5 _! S& N! d: G( H}/ d' Z3 M7 l2 b
- P0 g5 `- r5 i6 Z' U增加节点
+ ^. \3 J9 F+ Q: r! t. @9 |- h5 Z/ n( {1 y9 q8 t4 o- F
void LinearNode::AddNodeHead(ElemType num){ //头插法 # k2 m6 n/ |. c& U* [
node = (LNode *)malloc(sizeof(LNode));
& X* y( ^# C5 G F j; f3 k if(!node){
0 {: Z' y2 C( d6 h cout << "新建节点失败!" << endl;
% h6 u9 [$ [) m* r" b return; 7 h9 I' n' [0 J5 u6 h
} . {/ g8 l) e$ C
node->data = num;
8 _7 D3 F4 u* Y6 F% Z# x+ ^* K. N cout << node->data <<" ";
W2 m; h" {# m5 ?$ y if(NULL==HeadList->next){
& u' ~# `/ e: T. `1 C8 f; t6 k node->next = NULL;& j2 N0 v- y4 Q: i# ^9 b7 Q
HeadList->next = node;
\+ ~' Y6 z# A+ j m8 q EndList=node;
" e: n- P5 r; q) F }3 z- P2 c1 r ~! n
else{
g: Z. E$ i, \& Z4 j node->next = HeadList->next;) m0 G( }6 g& [+ s
HeadList->next=node;( M% u* t7 X* L0 p, I# W3 Q) G
}
' J& C; S2 r" @& v Length++;
5 z9 O$ D9 j& D- m) e" L5 C}
# F( O3 ]; Q% r8 i5 h8 }
! C0 d- A: `' Bvoid LinearNode::AddNodeEnd(ElemType num){ //尾插法 & h& ? e/ H/ R w3 ?) \7 O: f
node = (LNode *)malloc(sizeof(LNode));
: c% C. w' e3 P8 t$ X8 J' l if(!node){
! v7 U" X' y$ r cout << "新建节点失败!" << endl; ' G, D8 |6 _7 D3 h7 M6 G
return; & t9 j) _% h0 N; s$ D$ e
}
+ ~! [0 S. w! k) R node->data = num;* C4 l W+ p7 U/ T9 h& _/ M1 G" b
cout << node->data <<" ";
5 U) R$ i8 ?& G. L node->next = NULL;' C) K) T8 W1 ^9 W
EndList->next = node;
n/ g8 q Z+ v' a4 m EndList = node;
+ x5 ^' Z# Q" N0 r8 N5 I5 ^9 B Length++;
3 g. \3 D/ R8 N3 q7 P! N}1 t. V* D9 D9 i- Q
. G7 e, H4 t+ x! W, y8 E* G9 v
删除节点
$ `. z: W# K1 O2 ?+ o- f" S! X) r. W% l* u9 s
void LinearNode: eleteNode(ElemType elem){+ h; u. U# J( @
if(NULL==(HeadList->next)){7 y" _# F+ i1 }: H8 s4 [& G. c* y
cout<< "无节点"<<endl;
$ Y* R: z3 C$ [ return;
I- T3 J' C- r6 d% r; C5 p }
( C' r! ?# [0 _ Node_cur = HeadList;1 G( S% \: O3 W( b$ ]7 [/ k
while(NULL!=Node_cur->next){
4 G" H" Z. P4 d! Z2 m Node_temp = Node_cur->next;
. s5 _2 q2 j" h+ {8 a) A- E if(elem == Node_temp->data){
# |! j0 {8 ^& h Node_cur->next=Node_temp->next;& o# _( m' j1 Z: b6 x
free(Node_temp);. m; P! b" @" C
}
' p8 J. Z, G f# ^; i if(NULL!=Node_cur->next)# ?3 x$ M0 _. K
Node_cur=Node_cur->next;
7 M: ~& N; U) r4 M2 M& ?( f }1 i" g, l3 c9 K. L! i9 ~7 V' E
cout<< elem <<" 元素已删除!"<<endl;
( |/ i; ]! s, n5 L: V$ a; q}
7 A8 \2 p2 Y6 l, Q4 p \: s4 s! q6 y M8 t) H# w
显示链表
4 I2 j4 } `! `8 t! U. I2 e: t' ~/ n. V* s; b
void LinearNode::ShowLNode(){
6 _! X) r( B: P! y3 U if(NULL==(HeadList->next)){4 P- L/ d/ M- \7 y* ^
cout<< "无节点"<<endl;
( d+ l& Q8 L: m return;
, }1 V% s, ]4 G$ H }3 q2 y4 n: C& K' p" k2 C' K
Node_cur = HeadList->next; . }% l& t% B" P; l1 i! O. g2 X3 K
while(NULL!=(Node_cur->next)){; f H2 R) k' ?4 T) C! b* U m
cout<< Node_cur->data << " ";0 u" ] T" ~0 q6 @ i0 p
Node_cur = Node_cur->next;
) u& y, G6 i" K; R0 {1 c0 d }
" n9 m: x% S4 @4 \& [ cout<< Node_cur->data << " ";6 O- p* s. Y: x& V a* Y F
cout<<"链表中的数据已显示!!"<<endl;
; [3 `1 V% `4 S; H' t) G}
( k* T8 { ^4 m; Q, m: R0 A K0 B8 P6 {0 }2 f6 s
销毁链表
" e9 ^# k* ~/ q- r2 P3 }1 M. T1 A6 Q: B* r( ]. F5 |
void LinearNode: estoryLNode(){+ E# V8 a, i9 U# D0 L; V# |" L
Node_cur = HeadList->next; ; @* M6 m4 g, o# X
while(NULL!=(Node_cur->next)){
2 d% t# S8 u' u* D+ W Node_temp = Node_cur->next;
2 `; _+ K" |. b0 I/ l u free(Node_cur);# z* I' d$ ~. O
Node_cur = Node_temp;
! o/ D; _# S2 S3 ~5 r' b5 Y+ R }
6 X l$ i" n7 l7 \0 Z free(Node_temp);
6 O2 h0 V* k" K5 A. V cout << "数据节点已完全释放!"<<endl; ! k( J2 r- M X/ V1 i |, o/ s
free(HeadList); // 释放头节点 ) M4 A/ _4 _9 P
cout << "头节点已释放!"<<endl; ! i$ ]0 L/ E7 g7 U1 p {+ l
————————————————
\) s4 ]0 [% [6 K- _版权声明:本文为CSDN博主「星河有鱼」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
$ Y7 H) f$ h A! z6 G$ j原文链接:https://blog.csdn.net/Baimax1/article/details/106036286! [, i1 @- f6 x2 X; t9 M5 Y
$ `2 ^( U/ o8 y( T6 s
2 D* F( A7 b/ D2 [, b* M6 C' x |
zan
|