- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 81
- 收听数
- 1
- 能力
- 120 分
- 体力
- 541086 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 167704
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5324
- 主题
- 5250
- 精华
- 18
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
6 q* i5 g& |2 ]/ R3 u线性表顺序表示、链式表示实现方法及其异同点
7 f7 w0 `2 B7 {# q" w线性表是最常用且最简单的一种数据结构,按存储单元排列可分为顺序表示和链式表示两种方式。2 h+ P+ c) G3 _1 c1 S
" Q- I6 Z* _, J/ H! P$ o本文采用C++实现两种表示方法。
x" h' \- x8 U5 @9 n/ z; z+ p Y8 @) {0 v3 D: I# N3 u
目录& {7 R' P) O3 G, W, S$ y
2 U2 U/ b7 c6 H, h' P$ H6 j2 `' W顺序表示和链式表示的区别:
; [5 m# k9 c2 r) B/ T+ \
+ p+ e/ Q0 x' q- ]! H i创建方式:8 h, {2 ]: U5 x7 d- G7 k; f
/ g- c" j) L4 {时间复杂度:
5 h9 @ O* s+ s2 i4 ^9 B. n+ t: S! F5 a" `$ }; v/ g
顺序表示和链式表示的相同点:
) O, z4 I, h2 z+ N" L' s0 K! T$ J, t, y7 a
删除内存空间:
6 U: y6 r7 T4 J- s! {
* z5 n# I8 _& T+ m2 D* z代码实现:" {3 I6 r3 E% S" ^# w
+ t3 e u0 S6 F7 [
顺序表示方法:0 l/ _( @$ E" E4 H" H) V, m% M
4 Z5 g3 y$ z; U& E结构体定义
/ k$ f0 V+ V! g" Q b/ c
* H( R) l5 w E. N0 i+ K初始化
' }0 z: A! c5 k) S' u4 j& t2 y; R0 N) x2 L$ o0 \+ Y
增加元素- x9 R2 b( j/ S( [1 U7 W7 v0 w
; I8 w! B5 S+ ~6 a% g- D
删除元素. y. d- ^$ R% K" h
! o( p. |: @7 V
销毁列表* `1 L, k& X7 h$ ]% M6 E" r. m6 t, {
3 ?( u" L% M; e; i
链式表示方法8 n D8 y3 _' t; t0 S4 m
- Y# K$ Q4 u: `( X3 n8 p1 U结构体定义
7 u, k- p* j6 R" C/ I. d7 a) t! z% D9 w! l5 M8 z# K$ F* I- c
初始化8 l( w0 N& U, T6 @! u0 Q0 k0 E% H
3 g j$ I( ~, y5 y" t. q/ d1 U增加节点
' e' @3 `6 ~7 C9 J4 H3 s: s* ]. O& y l( P) g& K' K+ t
删除节点
- y0 F8 M9 Z- K! A) e* h9 n- y& j& x
- |) s G4 u5 l显示链表8 @% }, i/ A' i
2 m6 }. g& S6 t% [. T% x
销毁链表' H! ^4 {2 z( d/ @ s) U
/ t( W7 e0 x1 W0 c0 d. k顺序表示和链式表示的区别:. V+ X, D* R2 N0 M2 `/ O5 a
5 t0 U' f1 a W# `& A1 D创建方式:
) k. G% C+ G( p. b& M! R1 {( w9 L2 f" m) z
顺序表示方法单次创建多个存储单元,相邻的元素存放在连续的存储空间之中。
0 u7 ]/ C: \5 L0 s$ @7 T$ N; v3 _6 _1 D
(PS:内存空间申请请参考https://blog.csdn.net/Baimax1/article/details/105954552)
/ F' g( a7 m; N# C- z8 O
, r% w& u; E, v2 U链式表示方法单次创建单个存储单元,存储单元之间地址不一定连续。存储单元包括数据部分和地址部分,数据部分存放需要保存的数据,地址部分保存下一个存储单元的地址(单链表,双向链表的地址部分同时也存放上一个存储单元的地址)。% e7 W7 |$ V5 N+ T5 o5 S" B
2 y9 i! k9 L. d( G
时间复杂度: S! m' V8 x7 o" Z/ z
, S: E+ \# D. w/ l: L+ M增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(1);(PS:在未知位置的元素前 / 后操作)3 [0 a7 ]0 H! M9 L/ W2 o( D1 Q
3 e }; o( d, T% s2 [, g
增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(n);(PS:在已知位置的元素前 / 后操作)3 D. G! X- B+ ?) u' a B0 q8 c9 K
' U" W. v# b% m6 c! C$ A
PS:顺序表示需要将元素一一后移,链式存储结构需要查找该元素的位置。0 _; s2 p7 h4 g+ K5 H
. b( {0 i: A5 K修改 元素操作:顺序表示方法 O(1);链式表示方法O(n);
8 s e- A, S- J4 o1 S# N! }% q8 |# P) }3 Q# x& I- x
查询 元素操作:顺序表示方法 O(n);链式表示方法O(n);& a6 l8 G) n1 l6 j0 F5 O
2 f* r3 ~; ]) l$ w, p2 T: i
顺序表示和链式表示的相同点:
' W5 O) o" Q. Q9 {0 F6 `* U0 P% ?0 L$ m( ~6 A
删除内存空间:
, e( ?8 a$ e0 d$ s1 _; K0 a: o" I0 v1 |. D' E
内存空间的删除都需要对每一个存储单元单独释放空间。
% [9 P7 l& Z: t- _! F# u0 F
" e+ Y% m5 [4 E. B* ]代码实现:' v/ w: q( i1 p) w
" t9 {) Q9 ~ O$ O顺序表示方法:. b/ q8 u+ f7 F. h! o; ?0 p
0 z/ e+ N. X& x- T6 u7 k( R
结构体定义
9 i; h3 A/ Q1 n* b
+ H ^4 A4 {! i- htypedef struct {
: y; m* ^. Q/ ~& C; j p. n4 I ElemType * elem; D! K+ ~8 h2 e) e8 u7 j i
int length; // 线性表的现有长度 ; H6 H9 O b2 }' g. d
int listSize; // 线性表的最大长度
9 J* d( V* j) U# R' A}SqList;3 b5 L2 X4 d$ S* b- B* D
; N3 e& }9 Y3 k6 K5 S0 `. L8 j; F初始化
7 k% ^' _& B! ?
3 v) O% E7 d; _& u3 l K9 ?' q2 fvoid InitList(SqList *L){
$ {& N8 F& v0 j" ], j8 v# |' `- o L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)) ;
' ^5 y/ k+ P# P/ S0 k/ C if(!L->elem) {+ \6 e% Y( S9 S7 U
cout<<"申请空间失败!\n";9 D5 q3 r7 s$ K; f x
DestoryList(L);, J) g$ v: M( P
}
8 N9 U. a6 U, S/ h L->length = 0;
% z* Y7 N6 U% G1 T L->listSize = LIST_INIT_SIZE;
; R# z' L& A" V+ b0 \! l8 b cout<<"线性表初始化完成!\n";
2 X8 [3 P m; U}
2 Q/ O! F6 k. ^( F2 I6 b$ K' x5 K. d/ B
增加元素) |- Z! T& c: Z7 I( P
% `' S* q3 I4 ~. `) dvoid ListAdd(SqList *L, ElemType e){ //在末尾直接增加元素% l0 n6 w/ ]: N
if(L->length>=L->listSize){
* T, c9 W ]" r0 L* R% p$ E L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));
) Q7 D: H. k/ V7 T1 g' _ if(!L->elem){
. S7 ^7 I8 Z, O; ?' y) G, ~' Z$ u cout<<"增加空间失败!"<<endl;" ~3 R2 S+ H$ z
DestoryList(L);4 C! W& X- V' |+ t
}
; W8 `; t) j% d8 E }
: T6 \4 }& o: ^. R' J+ a, V" i * (L->elem+L->length) = e;
; ]- u+ S G: r& f4 h$ | L->length ++;
3 e, _* }, f7 S: q6 {: h& h: k}
/ ^$ O, w. N& X! R0 I5 P# U2 g" T$ a6 d# b# C, T
void ListAddBefor(SqList *L, ElemType e,int e_where){ //在某位置前增加元素
* \' w# `. E/ i( A* x F& ]; ] int i;
+ I4 D1 h, k3 t: h9 ^! q6 Z L->length++;4 \) t4 K4 D- v! Y
for(i=L->length;i>=e_where;i--){+ [. V& s0 S9 U- \) ^
if(L->length>L->listSize){7 N" m+ R3 b- a r& {8 z6 o6 v
L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));$ |9 q) r! e4 M& a" N2 V/ a/ B
if(!L->elem){
: Y7 V: f# Q/ r3 H cout<<"增加空间失败!"<<endl;
f* R) k9 f6 ]8 J; s/ E _, e( w9 p DestoryList(L); 2 E }0 }' D% Y) I" F9 k
}( t7 m) M5 h% [ O% x
}$ p% j' X4 {( \" }; O. ]
*(L->elem+i+1) = *(L->elem+i);
3 \6 d! p% M: Q7 Q* `8 y" N1 u }
, Z P f1 y! d" B5 ~5 g *(L->elem+e_where)=e;
' a2 w/ }) m# a cout<<"增加后的线性表如下:"<<endl;
) ~& g5 _. p5 A g, ^. ]& A ListShow(L);1 H/ k* t! R6 y% Z# P, ]
}
6 t z: E- i9 k0 b: t
3 O% A' r0 O/ C! a8 `void ListAddAfter(SqList *L, ElemType e,int e_where){ //在某位置后增加元素+ x# J) z6 |' l8 N$ E) l
int i;0 \+ w8 g# B% x5 |
L->length++;: }0 f+ w% e0 O
for(i=L->length;i>e_where;i--){; K' H, Y/ j; S L8 v0 ]% a
if(L->length>L->listSize){( w0 k9 X% E8 q" I. d
L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));' @# G3 t- L( i( a- t. A# R* \
if(!L->elem){
4 O+ [3 I# x3 g9 c cout<<"增加空间失败!"<<endl;
' `- `- i) B4 z& |2 C; Q7 S9 a/ k DestoryList(L);
! q& k% E/ L6 [6 X" a }2 V9 I0 n; O, o, G
}0 J, p& V0 i- r R7 L8 F+ D
*(L->elem+i+1) = *(L->elem+i); + H+ S- q% x$ k1 l
}
( @2 y( P: S2 @0 f. K; v" G *(L->elem+e_where+1)=e;
- l; B& Q& `" B. k cout<<"增加后的线性表如下:"<<endl;
$ k$ k1 R) F4 ?( Q, e/ @6 m ListShow(L);3 G& s" Y' @- |2 E( W
}
& X+ C9 ]! p& ]1 z
1 }) I( N$ Y. ]; S9 x删除元素- V$ g6 _; {# w% c. o2 a* K
6 S2 I) ~+ u% z+ p% @0 i
void ListDelete(SqList *L, int e_where){ //删除某位置元素 0 u2 S' Y' d2 {" s! `( b
L->length--;
3 ?! H! r% @# ^0 G( i for(int i=e_where;i<=L->length;i++){
5 T& p z* F6 \' k1 t *(L->elem+i-1)=*(L->elem+i);. O2 Q7 B0 k, B
}) K2 g/ E/ u3 M) `$ u7 R
cout<<"删除后的线性表如下:"<<endl;
; b% w/ E& h: B1 `/ x4 R; f ListShow(L);
/ H1 s# B$ |- t x7 M- U* A {}
/ M4 g/ ^1 s! }
* H2 u1 O( p* H; ?3 g* u$ }$ y销毁列表, @2 }8 G. O! W S+ x
! L& k1 O+ _, k( W) R& ~& y* Qvoid DestoryList(SqList *L){7 o$ z! L, l) y- R; C
int i=0;
8 k2 G# R# Q8 n/ j for(i=0;i<L->listSize;i++){
" {$ U) e) C6 i! c9 E& J free(L->elem);) b: C6 ]& G; o1 {
L->elem++;0 l7 C* n' N- M, A3 R3 z
}8 G T( M% O0 v9 c- H1 E5 p
exit(0);
* }9 T8 a8 Q! H) U: q4 z}
! N% O9 E& A; X+ s$ q5 ^0 l: l5 ^! b
链式表示方法
$ M4 e$ ?+ \# h% ?& ?/ E3 X4 w
& P1 _, c+ J8 b$ V9 _结构体定义( x/ P7 M8 p( K) f1 M
2 W# @* Q! @$ K) A) K% [0 I
typedef struct L_Node{
! k6 K* ?( B6 a3 ` ElemType data;5 m" h' a+ M- C$ q; y$ T
struct L_Node *next;
: E0 H1 ^+ ^3 P) p9 ]+ U- C //struct L_Node *last; //增加可变成双向节点
$ T7 b* X }9 M: ~$ U: E}LNode;
' R, y' A3 l; p/ u) t7 A
$ m" B$ P1 K: @# \) D$ X) |- p初始化
/ ~: y) `0 o( x. ?. h" S* v
; p a6 Z* Q* ?. T3 O3 Mvoid LinearNode::InitLNode(){
: h; H" g" O6 U. i' k: M3 h( @ HeadList = (LNode *)malloc(sizeof(LNode));. i' K& t1 |0 X, V7 U5 ?/ M# j" B$ J
if(!HeadList){* C5 [: `0 Z4 I8 V: w b
cout << "初始化链表失败!" << endl; ( S: C7 {1 X2 s% k5 g1 m
exit(0); ! U: E$ Z1 |3 }1 m" @
}
3 q8 o) G/ k x1 Z1 e" w EndList=HeadList;
+ W" ?3 c( ?% S1 l# y* z HeadList->next = NULL;2 ?7 @/ g# W. w: n' |
cout<< "初始化链表成功! 初始地址为:" << HeadList << endl;6 y2 U* u( y' [7 ~# j1 x/ @
Length = 0;& \& Z7 I- P; P9 C4 g6 h1 B; @
e_where= 0;
5 t1 C, c, y) |' V}/ A# \, y( r2 r4 {8 O) U2 Z/ X( M6 u
5 ^) V0 X; J9 @7 O$ r3 y增加节点
6 H+ K9 y% l. j7 k5 L3 V |/ f9 k2 p8 R h: a5 m
void LinearNode::AddNodeHead(ElemType num){ //头插法 + e& ^! j) y( q5 E
node = (LNode *)malloc(sizeof(LNode));4 x' e; t. j9 Z. _% J
if(!node){# M# _; Z1 k- }& I" ~- ]
cout << "新建节点失败!" << endl; " D6 H" l& L7 c) q, t
return;
9 s) z0 U# F& f4 [5 R3 p; f7 D- | } % E- t; |5 r1 O
node->data = num;& G0 U2 X4 {$ j! e: z; }# y
cout << node->data <<" ";1 U1 \+ V$ S" L8 h+ n$ p
if(NULL==HeadList->next){
; } C0 ?' y9 j7 E: R4 g% H node->next = NULL;
3 X/ T+ e9 @9 A U8 N3 f, C* D HeadList->next = node;
" Z! f. R5 I M EndList=node;
' o; K1 Z- n5 v- w$ I9 w4 Y5 o }: q3 k; S* g) w
else{! s p9 j6 g+ G7 ]. T
node->next = HeadList->next;1 X7 ] R+ E' Z; k( j
HeadList->next=node;/ t( ~7 R4 Z; {1 {
}
? r; _8 s+ a% G) v3 N, `% c Length++;
3 `/ n9 d: ?7 E( T T3 [( r}" E* I% d& Q3 B* C6 g
& `. |$ \) e/ W' c1 \4 i1 \% Svoid LinearNode::AddNodeEnd(ElemType num){ //尾插法
4 @: ^, c1 o1 m/ o0 Z node = (LNode *)malloc(sizeof(LNode)); j' ?/ \8 z* [
if(!node){
: W) S2 @; R2 d; y cout << "新建节点失败!" << endl; # ^& R% Y2 D0 Z% \3 |0 R i
return; 6 M4 l& [# i. D
} 4 h( b j# M' N t' E2 c
node->data = num;
4 J; X- D$ K6 b+ {5 s6 n cout << node->data <<" ";
% d! b+ ~( L; [4 I9 R+ M node->next = NULL;
- j, O& W6 S6 s; c EndList->next = node;9 {" r; _- V# U: ?# r1 _
EndList = node;; O. j1 T# Q' {* |" Q; j; P8 z$ c
Length++; 1 D; f" x& Z# L% R' h% t( E
}
- X4 i* i a* L' h1 @. M
; A% c9 x/ `( [( o) |删除节点- }% T$ k8 X1 F& `: @: Y
9 ~" }+ I% y3 M3 Q$ v$ z4 h
void LinearNode:eleteNode(ElemType elem){
: \. k2 M; O7 e+ g if(NULL==(HeadList->next)){0 J# Y/ F6 l1 O6 |* A1 _
cout<< "无节点"<<endl; @1 D$ q. m% _0 B. n- ?, w
return; 0 C- ]' X- W/ e: }& Y# \0 u/ \
}5 @4 r$ C& n, V1 L- u) E. S4 N0 n3 Y
Node_cur = HeadList;2 ~+ u1 P0 Y4 Q6 Q+ G4 Z
while(NULL!=Node_cur->next){
& L5 D4 l( y$ K" @0 ?% O. O Node_temp = Node_cur->next; 0 d, v( X- G2 G) ^8 m
if(elem == Node_temp->data){4 b& \% R# v( @3 y3 E& C' u% b, X
Node_cur->next=Node_temp->next;
. `5 r& t1 l. I* K! Q/ u: \ free(Node_temp);
$ w6 f R' v; h/ u3 f8 d' S }
: @0 c! G- I3 v if(NULL!=Node_cur->next)# u! j) m- h$ m; l8 N, [: G
Node_cur=Node_cur->next;
" q8 f4 f, \& M; u, R }( k0 q7 j5 j: D
cout<< elem <<" 元素已删除!"<<endl;
# X: X6 D9 I5 e, u" X# _# \} . u4 K3 y. b& e4 U4 i) d
$ Q: [& R- y/ i: u; C" E% U
显示链表. P- I L9 e' d
Z: x, f% v2 i; V6 A ~void LinearNode::ShowLNode(){
! I( {8 i( s& B: w6 ^6 S if(NULL==(HeadList->next)){: J/ ^" E" [, h Y& F$ e v
cout<< "无节点"<<endl;2 ~# W3 \/ V- E& w' Y
return; . C3 b( Z/ F2 _- l7 E/ N9 c1 M C( C
}& q- X4 M4 @& g& v
Node_cur = HeadList->next; 1 s. s5 C' {- N/ A4 S
while(NULL!=(Node_cur->next)){
& }9 Y( |* }( K cout<< Node_cur->data << " ";5 V6 }! d1 k2 R F1 p* ^
Node_cur = Node_cur->next;, \8 S2 Z+ T, p" Z; g9 V
}
. w9 N. ]: Y; p+ ]0 X+ c. v cout<< Node_cur->data << " ";, u- b$ ]7 D: p2 W1 z) |, I! ]
cout<<"链表中的数据已显示!!"<<endl;
7 H! k5 h" Z" Q! t, l2 ~}5 A3 W: `7 g* t5 z
- C! G( z( x' W销毁链表
& P# Y7 U( z) E8 d- {! P" j$ H* W5 R; c: G% z; f
void LinearNode:estoryLNode(){7 T7 D9 u- o; w/ x
Node_cur = HeadList->next; * p! |0 K9 C+ Q3 L# L+ R9 q/ w
while(NULL!=(Node_cur->next)){ v" {; W# G# Z9 a: ?/ O8 ~! z4 U
Node_temp = Node_cur->next;( K$ F) i: X0 K+ c
free(Node_cur);, U5 |) ? C) z
Node_cur = Node_temp;$ A& ~1 E3 J, [) K; V% h
}3 A' T. E+ p1 Z! H; [4 N
free(Node_temp);4 {# W7 A0 l+ r: Y
cout << "数据节点已完全释放!"<<endl;
! y2 H9 C; R% R% p5 _ free(HeadList); // 释放头节点
0 k) N- v, L& j, f- r; E1 C cout << "头节点已释放!"<<endl;
k) z: Y0 k- v2 `$ x/ l————————————————
. `* R% o8 H7 o. H版权声明:本文为CSDN博主「星河有鱼」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
0 Y" h4 h: J8 M% i2 S, i原文链接:https://blog.csdn.net/Baimax1/article/details/106036286
6 f' \+ Q# c V5 o8 i6 {" T4 F$ n! _* C1 j2 {* G
/ _- S) T" I3 L' J$ e0 t( o9 W/ l4 E |
zan
|