在线时间 1630 小时 最后登录 2024-1-29 注册时间 2017-5-16 听众数 81 收听数 1 能力 120 分 体力 541094 点 威望 12 点 阅读权限 255 积分 167707 相册 1 日志 0 记录 0 帖子 5324 主题 5250 精华 18 分享 0 好友 163
TA的每日心情 开心 2021-8-11 17:59
签到天数: 17 天
[LV.4]偶尔看看III
网络挑战赛参赛者
网络挑战赛参赛者
自我介绍 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
群组 : 2018美赛大象算法课程
群组 : 2018美赛护航培训课程
群组 : 2019年 数学中国站长建
群组 : 2019年数据分析师课程
群组 : 2018年大象老师国赛优
& g: I; S2 y/ k* `/ |7 }5 D7 F 线性表顺序表示、链式表示实现方法及其异同点 ! h/ ~* u/ i$ @3 ~+ K" Q" _! x
线性表是最常用且最简单的一种数据结构,按存储单元排列可分为顺序表示和链式表示两种方式。
1 ?- ]' k% ]" \5 |2 g* H ; M2 J7 x* C& h6 f
本文采用C++实现两种表示方法。5 G8 @' J/ K. c e% Y
, F/ L6 o6 I) z% J* a3 g* V
目录
/ Y& D5 m( a+ ^, \- a% P
9 L: J1 h, t9 Q+ P 顺序表示和链式表示的区别:, L5 ^: Y- q4 G; _, O3 T# j
% m& l. g2 E& Q& i4 F. `
创建方式:
& N3 @1 Q4 [+ a; u) e
# O0 I _! a# _ 时间复杂度:
4 g% m9 Z4 m8 P# w9 [" C" j 8 v8 }1 w2 q6 I4 `6 L6 c3 V! b
顺序表示和链式表示的相同点:! m8 g: C" t5 z( o
8 ]: l5 D* U4 c/ p; m
删除内存空间:& D$ L1 d% v- g+ _ y
; _) s# v+ z$ g, i$ g* ] 代码实现: B# f$ n {0 q- V5 `
, C: N. ?8 H6 E" L: {3 ^ 顺序表示方法:! y9 o) p1 g A, e: m9 J- u2 g
7 z8 m5 m4 B" t1 v$ T7 W
结构体定义% Y8 \: r# {% J$ Q* ?3 N0 f
& D4 c2 i3 ~; {- T
初始化5 X: U- A, B# }5 c W" A. c: P4 `. @9 {; R
( O% f! E& r- d1 t: j3 n6 `( t 增加元素" |3 U! o! p1 n K7 O6 d" z; `
' G. ~. ~4 K9 a x0 `
删除元素/ O2 M! n# Q8 |: }9 ?
# v- W' V1 u( t1 i; j" o0 ^! Z3 u
销毁列表' G; r) l# b' m
9 `4 P5 E9 h( z) |. V1 h ]
链式表示方法5 V( p+ x7 d2 g: U+ B
6 M8 o+ e8 S! |& |5 x! V. `# b 结构体定义
P& k4 Q( z7 R% f( Q " I8 j+ x6 b' v, O0 a: l
初始化% p# T% e) `' T6 P
: g+ H# m! i4 l$ J2 P) H$ M* \ 增加节点9 H8 k3 Z# H4 B* A4 H! h4 d* X
2 Q& ^, r" R* `! d( H, m
删除节点7 E& @: \2 c6 I' A/ w6 h& E
( M% S& f5 o# p" P# P" V; z
显示链表
7 ]3 S |/ p- F) w" \+ x * S% N) j1 b: v9 k
销毁链表9 [- Z& G! _+ V
$ k3 [/ ]; F ?7 s9 t# w# t$ ^
顺序表示和链式表示的区别:
3 p6 g2 b5 M" Y% p( P4 c# ] % v: M9 p# t- E- M$ b3 N8 d
创建方式:1 E3 z5 l9 r+ M" G$ I* N% r
- ?* T* D& y+ v* p# x) o) C; _
顺序表示方法单次创建多个存储单元,相邻的元素存放在连续的存储空间之中。
( P) d8 X. j8 S. e) P, s/ I
" J/ g" S3 c/ }: B/ ^3 R8 y4 b4 F; s (PS:内存空间申请请参考https://blog.csdn.net/Baimax1/article/details/105954552)0 c6 l1 Z, I& W u1 o; z p! O
6 Z, ?2 u9 M) K% p0 J# r" y# g, L2 U3 i
链式表示方法单次创建单个存储单元,存储单元之间地址不一定连续。存储单元包括数据部分和地址部分,数据部分存放需要保存的数据,地址部分保存下一个存储单元的地址(单链表,双向链表的地址部分同时也存放上一个存储单元的地址)。
2 Z# ]! c5 r$ F( q3 d 3 Y: L, l, _& m' W' z
时间复杂度:
( n( [5 B. T3 q2 W ( t3 S* s c9 H% G# {1 e
增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(1);(PS:在未知位置的元素前 / 后操作)
2 n2 @, h, w$ C2 O; Z
/ F* o8 ^2 K4 D1 }5 d# P 增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(n);(PS:在已知位置的元素前 / 后操作)' X) f8 o6 C# Z$ K( J" q
' Q& L! Y8 a7 B. ]
PS:顺序表示需要将元素一一后移,链式存储结构需要查找该元素的位置。
2 Y B" s) F4 M, n( } ( X3 S0 r, _5 n0 _' }
修改 元素操作:顺序表示方法 O(1);链式表示方法O(n);4 h5 W$ S+ K# \7 c$ n
% c/ b& p; b! I V0 ] 查询 元素操作:顺序表示方法 O(n);链式表示方法O(n);8 q: Y" p6 m/ W# @+ ]% S6 a
2 F! L3 G* Z$ P+ l8 I, w$ k8 e3 W* }9 y8 k
顺序表示和链式表示的相同点:
! h9 |+ O6 o6 B: B; m. ~) S" G ! `1 D; G; {# A5 p& v3 [
删除内存空间:" H" [7 |0 c2 o# I8 D
" H# M2 w' U$ {9 Z9 c; m
内存空间的删除都需要对每一个存储单元单独释放空间。+ y- }5 J; @* `8 \+ a0 a
$ V }9 m0 H" y+ t1 t3 {
代码实现:
8 }( ^! X; g/ \' M! J6 n! A3 E
5 `5 G1 G+ o! a- s$ E 顺序表示方法:
) W! [ w5 @1 f8 [" {
! ^+ g( D! |! w4 V 结构体定义- E9 D' E1 \# x: T+ G
' p2 |. X% _4 m( u7 d typedef struct {/ W" c) a9 r9 x0 @' l
ElemType * elem; n9 Q0 B% k# ~& Q* F1 l
int length; // 线性表的现有长度 ; M/ ]$ W2 C C3 j
int listSize; // 线性表的最大长度
5 Q5 z, D- t6 R- C: r }SqList;
) O/ w9 p+ V6 S8 c! A& K8 w2 M" x; O 9 Z, T1 V4 K$ Z6 ?) {( H" r
初始化! b, Z5 J9 R9 L; L _! }
1 R; e9 S }2 ^ void InitList(SqList *L){8 T, L, j' K) H/ W# B3 c) o4 ^: o
L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)) ;
. x- [' ]! F6 x- t# I if(!L->elem) {
2 y+ a! \0 c& ^# { cout<<"申请空间失败!\n";
- c/ B$ u4 K5 Q2 g s8 d" U DestoryList(L);* A% {& d: A. p9 W
}
1 H3 F- Z2 U6 _) g5 M% T! d- ~2 S L->length = 0;/ s7 {! C) |, Q) ?5 c
L->listSize = LIST_INIT_SIZE;6 |$ b5 z+ ? @8 y( z" }
cout<<"线性表初始化完成!\n";
' z1 M3 S2 ^ v) \1 Z+ e( x' z }- Y0 K2 X# d# ]% I$ n, _) `
' R8 S6 P; P9 g- h 增加元素
! N7 d. S7 I* }2 y& H0 J2 E. S
) n! f$ p9 j8 m. _, k$ B0 | void ListAdd(SqList *L, ElemType e){ //在末尾直接增加元素
1 R* |; H1 E- o( k$ x* s) } if(L->length>=L->listSize){1 J" b; j, h# H" W
L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));! b8 m6 T1 ?' N: y+ Z5 h; Y
if(!L->elem){
9 G4 ]; S% `. j; E cout<<"增加空间失败!"<<endl;
' C8 O2 D) {5 n5 H! T3 H DestoryList(L);
, T1 w. p: |4 y- v }
' q0 L; ?0 q: M4 W+ B% V }0 ^( P/ M, s/ u* g; h9 g' D) H
* (L->elem+L->length) = e;* F* r Q- h% L! {: |
L->length ++;
: t) t, f9 h7 i: a. }0 c7 W* u }) M* m: }' O6 b
6 h$ X/ p/ @: v- u
void ListAddBefor(SqList *L, ElemType e,int e_where){ //在某位置前增加元素
6 O- ^$ d9 [! X; J9 o6 s int i;
. b( D2 [. ]) Y L->length++;
. z: W |" i: N- a; G for(i=L->length;i>=e_where;i--){5 G, S& i6 l! O( j) h9 R
if(L->length>L->listSize){
( v! i# r! }0 c2 Q1 n$ q6 d L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));' `$ {0 j* X4 K* j; y
if(!L->elem){
4 }# Z; o& ^+ F, I: E cout<<"增加空间失败!"<<endl;1 X# Q: a V2 H
DestoryList(L);
2 g4 ~' n0 z, ~ }% b* O) n6 V, c/ K0 P6 U& ?
}$ s y8 F1 ~6 H8 v" c
*(L->elem+i+1) = *(L->elem+i);
$ R8 n# q+ a! [3 O" o. v% _( H9 a }2 {' v, q- J" A6 e
*(L->elem+e_where)=e;
6 c( x9 O. [! K& X( q3 z6 a: i/ r cout<<"增加后的线性表如下:"<<endl;
+ I- ?2 G7 F1 d" T ListShow(L);
- a+ _& S) K+ X' X' ]9 ~; L) K3 p) C } . v+ ^: a9 R- @# c
9 d# I. y& p0 V" x% S( e8 ?
void ListAddAfter(SqList *L, ElemType e,int e_where){ //在某位置后增加元素: |9 u" \) y" D: u
int i;
- X/ a. u! b3 E2 Q+ \& s L->length++;
5 C2 w; H/ P% l. a$ U for(i=L->length;i>e_where;i--){
0 ^+ g5 a# v5 }+ J& J if(L->length>L->listSize){2 ?- o8 y0 A1 H, o& ?
L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));
4 O! f# A: A" o) q if(!L->elem){
1 ?: c* `* m: j! {+ p" E0 X( K) U cout<<"增加空间失败!"<<endl;
5 x$ X* U8 B* O DestoryList(L);
" b$ G/ Y- Z" p- z4 d9 z4 [2 l" c }
+ o0 ~6 X! z9 W) V! R }. V/ B& L. \$ o& y4 a
*(L->elem+i+1) = *(L->elem+i); % M% i9 g( J6 f4 g7 M" A" x/ u7 F
}* k/ Z; I& y5 N; d
*(L->elem+e_where+1)=e;: y7 Y* z2 r# D. b6 @
cout<<"增加后的线性表如下:"<<endl;
8 c: K ~5 O5 P |/ \ ListShow(L);
# G5 g2 |$ d+ p' c }& \) R( G1 R! [2 f3 k8 ~/ S2 l# U
: f7 h! r! w: \7 |9 t
删除元素
; Q: B% u w: A1 e) O: c) a & p# X# K5 J6 y5 g4 ~
void ListDelete(SqList *L, int e_where){ //删除某位置元素 5 P5 U' W/ } y5 i- t+ ]
L->length--;
5 z( Q: s6 U% ~/ |8 D for(int i=e_where;i<=L->length;i++){! @! L9 N- K, f; l. z
*(L->elem+i-1)=*(L->elem+i);
& k$ y7 }" ~& Y1 ^- x/ L! G+ W }
) ~6 u3 I" _) h' X- {( E% P( x% v2 ] cout<<"删除后的线性表如下:"<<endl;
9 o' O |9 U( N. e ListShow(L);& v1 m/ h# R5 B
}
! i' I5 X4 ^! m , S O; s, M7 P& t+ p) K
销毁列表
8 Q+ _) s* R9 G* `, z) [ 2 D6 `( x% s0 b6 E8 s1 D5 ?
void DestoryList(SqList *L){
; `# a4 u4 @1 z. u9 U! H: N8 t h int i=0;$ d2 a9 u6 S5 K& Q$ I
for(i=0;i<L->listSize;i++){
& d' R/ ]3 I" w# g! | D free(L->elem);
! A6 g8 ^/ ^# p0 M& u. x L->elem++;
) O4 d; b! h. R( s2 d }
# p0 _+ ?2 U2 ?, ` exit(0);
( E* i" G5 n/ ~6 l }/ ^3 K1 a. h7 ]; o5 v0 V( ^
% V) U m" k( \ 链式表示方法- o1 s& d5 ~1 b' Q* H
" c! B4 o$ Y: o0 u 结构体定义
) F. C& ?7 D$ y" u 9 N# L9 _+ u3 a8 b0 g* y: v
typedef struct L_Node{- f/ q1 |9 r7 l
ElemType data;' g2 a7 F% U4 {
struct L_Node *next;7 i; L1 ^9 ]6 @
//struct L_Node *last; //增加可变成双向节点
- |4 ]4 d2 `( r) e& ~3 N+ h }LNode;
7 ], w) n5 i$ q3 [* V
$ d+ ]. N+ B1 A4 E h 初始化
5 H t+ z5 C8 a0 M
) {0 K, ~2 m) Q( G7 P void LinearNode::InitLNode(){
$ Q! y- B# V) _ HeadList = (LNode *)malloc(sizeof(LNode));
- M8 I! X- I4 B$ L3 F$ q if(!HeadList){
{/ o3 b- v% J e( F. c1 x9 e0 @& a! [ cout << "初始化链表失败!" << endl;
' R9 T5 I9 ?0 q' {& N9 K exit(0);
+ E* u& q q# a' [1 d } ( u$ ^) {/ [- d6 x+ A
EndList=HeadList;8 q. u2 ^8 [$ L; K: w/ ?! P
HeadList->next = NULL;- w+ E6 I" u- @0 w* c: X$ [
cout<< "初始化链表成功! 初始地址为:" << HeadList << endl;
/ ^7 k" {9 N& @( M5 A& a Length = 0;7 j' z8 ]2 a( X' w
e_where= 0;* F/ ~" M) { a- Q& e9 U
}
& B# b8 Z7 Y7 g+ t
: L+ i1 f: E9 m# C+ G& C9 {+ f 增加节点( k% J4 P; c: e9 i _5 p4 V/ j
, r& q0 V/ b; b2 o; n9 d/ y/ S void LinearNode::AddNodeHead(ElemType num){ //头插法 / \, W1 s2 Z. ?3 S
node = (LNode *)malloc(sizeof(LNode));
- K9 @) a P- w: R4 N) n0 a8 W if(!node){
2 n6 B$ M- F# o- j' k& h0 F3 U2 v cout << "新建节点失败!" << endl; - R6 c* s, Z; S% p) B
return;
1 I9 F' L4 K7 S }
: ?7 C1 z! ]- M9 H4 f4 o6 q% P5 b node->data = num;( t& z2 v; A- h6 C2 X# a
cout << node->data <<" ";0 k8 G o$ `6 G; }: a' W
if(NULL==HeadList->next){
# F8 R, A: u9 q% F3 H5 d" n8 ~ node->next = NULL;- w! A% k1 c% G5 S7 x4 w& v
HeadList->next = node;+ o0 x- S0 I! m1 M& n
EndList=node;) U3 j1 |- r* M: W9 J
}5 ^" @- _1 D7 H( R C- E6 _. W! w
else{
( S2 \1 K1 T0 Y3 V, C, O0 S node->next = HeadList->next;
, b J# H8 x1 u0 v HeadList->next=node;9 N- H6 _' ~7 i4 f+ J. m$ Q$ g( ~
}3 W: p5 V" R2 c1 q8 E
Length++;
) r4 A4 U& W% g9 E5 T, s' r }
% K* J8 \% H& e% a5 b " E+ M/ n3 H4 @! a0 E
void LinearNode::AddNodeEnd(ElemType num){ //尾插法
1 k8 G$ I K( C+ c, ]+ ? node = (LNode *)malloc(sizeof(LNode));* v0 B: F8 `6 a9 p- r+ l* C8 s
if(!node){0 |3 t) T" ?% w, G& { K
cout << "新建节点失败!" << endl;
; Z/ X* {- O& _( o5 C return;
5 O" }0 ]7 G* s1 S# W6 h; [0 [+ F } 5 Q/ B. f0 S5 Q0 Y+ p
node->data = num;2 s2 d+ [. R: z1 k4 l( z
cout << node->data <<" ";, K: g7 i5 W7 F; ]2 S" ]2 P
node->next = NULL;" A( c5 o' B2 {) {! s$ m
EndList->next = node;. @+ [. T4 ?# U0 d# J3 p3 D3 v
EndList = node; M# ~. H- ]$ b
Length++; O) J& Y: N3 r8 c
}
) K9 L1 L4 G' Q8 g u+ M* O- q+ ~ 7 W- m% c9 ?/ c; [5 G7 j
删除节点5 z. Q% _# H9 G
C4 w2 h% h7 Z void LinearNode: eleteNode(ElemType elem){" W1 c/ ^, _& ^1 Q! J4 r2 H! j
if(NULL==(HeadList->next)){
$ K9 U9 H8 e, y; q+ j cout<< "无节点"<<endl;
& f' A7 W# h2 ]& O' c5 ? return;
, h$ w- ]" R9 E$ o/ m }1 u' V1 m/ ]8 \; Y% S0 \2 p ^4 r
Node_cur = HeadList;. h7 B! A6 W, Z% [+ T+ `$ I# m3 u' r
while(NULL!=Node_cur->next){
' b& |, {5 m- g( Y Node_temp = Node_cur->next; 8 _! T0 \$ }# D" G$ a
if(elem == Node_temp->data){8 P5 g0 n( j4 U: T( ^( d; L
Node_cur->next=Node_temp->next;
: k) i* o5 t- b0 X. r [ free(Node_temp);
: {) S, u5 A, W9 ]9 c }
W% X- H5 S$ t* A2 U/ J if(NULL!=Node_cur->next)
9 z. b5 K) k& ]& { Node_cur=Node_cur->next;
- M" o5 i1 z0 y2 C- [0 I }1 }2 A4 V# E6 |2 Y& R
cout<< elem <<" 元素已删除!"<<endl; $ `1 j+ R1 Z9 \5 l" L9 a
}
$ m8 J/ b* C7 n5 {) e) E 8 a7 K2 X1 X0 X4 j+ H. H! p" l1 N' Z0 c6 K
显示链表
( h' _7 S5 _# u7 ^1 e
/ b. q4 S4 R1 K# u. U void LinearNode::ShowLNode(){7 g0 X7 A8 t' x( R% z
if(NULL==(HeadList->next)){- u7 g h' y' i3 ^2 u
cout<< "无节点"<<endl;
' a' C( s( X& K% @ B Q* @ return;
3 A- w, v1 ` c( Z }
I" }( ~) D$ m$ M Node_cur = HeadList->next; 5 A6 ^% e8 N, l0 {& T& ?
while(NULL!=(Node_cur->next)){7 x+ F/ i8 t F5 R
cout<< Node_cur->data << " ";* |, `1 j+ P+ q- ?& o. Z
Node_cur = Node_cur->next;
" e, z3 ] P) h: }! ~- u }
. q3 z& \/ K( Q, h5 h9 c cout<< Node_cur->data << " ";* k, \5 S: H! K3 k9 v" E
cout<<"链表中的数据已显示!!"<<endl;
$ Q% N& d5 B: T5 ? W5 ^( o }4 c& R3 ]9 D& K
% F {$ I5 D8 F5 J
销毁链表; u! V4 Q' @ t& q1 J- {% ^
( u) b! n3 p, L& ~ t void LinearNode: estoryLNode(){
1 a( ]& M6 X( [7 G+ C Node_cur = HeadList->next;
# ~! k8 P; E8 r( A9 w* @4 J while(NULL!=(Node_cur->next)){
. t9 N7 c# P5 T h; d$ ~ Node_temp = Node_cur->next;1 n: x0 _: s2 Y4 I
free(Node_cur);6 W: F) y9 D; |/ }7 s
Node_cur = Node_temp;0 M$ g' j( q- B) f4 ]: K' D6 g
}3 F' p" Q; W1 X; a6 e4 a
free(Node_temp);- ?3 {+ _' Q6 N, W' {0 ?: x4 g
cout << "数据节点已完全释放!"<<endl; + }0 ]& h" E0 o9 O' I" c: L9 {
free(HeadList); // 释放头节点 7 p) q6 I* N; q3 ?: ~9 E) w9 t g
cout << "头节点已释放!"<<endl;
9 B$ \% s7 R' w ————————————————
( H2 s% q& H8 A' G4 X 版权声明:本文为CSDN博主「星河有鱼」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
! ^7 \- G% n* w/ f& n8 I 原文链接:https://blog.csdn.net/Baimax1/article/details/106036286) P8 B2 Q" Q, M
/ k, [3 A0 z x0 D1 b) ?2 i % v( d. R% j' N9 G8 ]& d7 Z/ ?! r0 l% Z
zan