数学建模社区-数学中国

标题: 线性表顺序表示、链式表示实现方法及其异同点 [打印本页]

作者: 杨利霞    时间: 2020-5-10 16:11
标题: 线性表顺序表示、链式表示实现方法及其异同点

3 ?. W2 x! X4 q线性表顺序表示、链式表示实现方法及其异同点- t4 t1 u+ D7 \! U
线性表是最常用且最简单的一种数据结构,按存储单元排列可分为顺序表示和链式表示两种方式。
! u9 u$ s: p' M' W$ E0 k
1 Q; g. _5 V7 p8 E# d本文采用C++实现两种表示方法。
$ o% M& P: P( C* k& w& D; v) h% y6 l: N, E
目录
6 w6 n* K+ Q3 w) p  z) @9 t) G$ T& L
( R( Q3 g" H( [. [: \0 }$ q顺序表示和链式表示的区别:# h  [8 |! x- D, S
, h" V/ o2 e: w& H, z' Y
创建方式:
2 O+ X% A/ L0 n3 C/ R/ Q1 F( j1 m  G! O
时间复杂度:5 m1 G( E3 Y& Z6 ]

2 X3 _; d- V# D9 @! [. @! {- ~顺序表示和链式表示的相同点:
0 ?$ Q) y& P1 e7 z; G' Z8 k8 d, a* O- G% P. X# q6 V* i
删除内存空间:
, I4 Y  w, v" g. m: y& `' K- y
$ m2 o  w3 Q& F' p6 d代码实现:7 ~+ z0 ]0 y( K/ s6 t6 |4 C- x& q
* Z0 i% Z# W3 ^  F( f' l
顺序表示方法:; b4 R! h0 H9 Z( j9 M* X- S

- k, @) _5 L3 t& C. l$ c结构体定义4 C6 K3 t1 |3 X  K1 I% }
6 A8 X! M# Q1 K
初始化
. l% \6 E. b; d- E- H5 X  ~8 j( @; x
增加元素
! X' ^/ R$ N1 b% F' B( K& A, x
& C+ i7 n, f. p5 D. ?. a9 t' h3 a删除元素
/ k, T. a' c+ c
% h3 k" G8 X! h" d! ?销毁列表
0 {* Q4 x/ \# \, A# w
. ^2 Z8 o* y- I0 y3 B- n链式表示方法) G+ V7 C* R# X1 ^
% S( v/ @) p& ?  K, x! @' P2 ?: u( C7 E
结构体定义" _0 y: q7 M. j" S0 e( A+ V8 F# q1 s
& w  x$ D0 W. Q- a  @! N
初始化
, `( X6 N5 C! t' f8 ]  i# Z  ^6 x! Y7 e; V
增加节点/ p; w4 G7 h6 ~3 ~5 c$ j7 Y3 [

6 ~$ ?% b+ }; x7 T, D# \5 @删除节点4 G# w/ s5 Y/ |6 P! b2 b3 }$ g

" I0 q3 ]- o/ A+ E; b& ]+ E. d" }4 T显示链表
, B% z, v1 f. U2 T7 {" b  l; T0 F3 N- s. _
销毁链表
2 r9 R, ~2 P7 }7 r2 L6 C3 e  o, b+ i4 K+ c2 a, R9 H# I
顺序表示和链式表示的区别:' e1 ~& r) i3 G: S. w8 p

2 C- P5 f0 B+ l7 x. ]创建方式:/ f2 J6 K! O. o5 F& k  M9 G

+ s5 U' }8 R, R' I顺序表示方法单次创建多个存储单元,相邻的元素存放在连续的存储空间之中。; O7 v1 H. W3 ]6 w6 H* F: ?2 i

& A' C' x- L! j: y# {) \4 E(PS:内存空间申请请参考https://blog.csdn.net/Baimax1/article/details/105954552)+ m% c9 m9 [7 U/ ]' u

6 C' J- p  j% V' E3 m4 z链式表示方法单次创建单个存储单元,存储单元之间地址不一定连续。存储单元包括数据部分和地址部分,数据部分存放需要保存的数据,地址部分保存下一个存储单元的地址(单链表,双向链表的地址部分同时也存放上一个存储单元的地址)。
. u) S  J2 B/ i$ U9 A
% g+ }) N1 G' E8 g6 v- U$ x时间复杂度:
! B; V2 k' e! U1 l5 \# {) j" y7 m$ J1 v2 F. ~& d
增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(1);(PS:在未知位置的元素前 / 后操作)
7 s3 c; L2 i3 G5 K4 R, m/ O+ U+ e/ n$ E  c. |' q8 W
增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(n);(PS:在已知位置的元素前 / 后操作)  K. ]4 q0 [/ [+ U$ H3 r9 K# ~( O

1 V* e* A7 [# T- y9 B/ H2 t& MPS:顺序表示需要将元素一一后移,链式存储结构需要查找该元素的位置。
! d& u, f$ f- r2 K3 _' q. m3 @( q' b# T  a/ x: R% A
修改 元素操作:顺序表示方法 O(1);链式表示方法O(n);
, N: _- Y. y5 o8 ]" G  L7 N! U* ~2 l: a& U
查询 元素操作:顺序表示方法 O(n);链式表示方法O(n);
$ N; ]) v8 Y9 u, M) Z# B* X( c( a
0 I4 J5 {; x' i顺序表示和链式表示的相同点:
& z! w; N7 ~  X2 l  Q( S; j) u& ]& @% y& j" F
删除内存空间:5 s. O. [- `  Q
# K) j) z, h% [' x2 C5 h1 Q* m
内存空间的删除都需要对每一个存储单元单独释放空间。; J4 E' K; k; R& v3 w5 n

; s) ~) ]/ q* z2 h% K# L& q代码实现:
, o( \2 N7 ]4 X6 e/ M& D# O" \& u% A8 j
顺序表示方法:& _% ]4 B2 M" ]! Y
7 w; c% i. r- M- f& `7 I
结构体定义- V/ X, G8 [* V
4 X& v1 @, `8 a9 I
typedef struct {- D0 u! ]9 e$ I
    ElemType * elem;
% I# w; M( H5 p3 Q9 b    int     length;        // 线性表的现有长度
( f; q6 S' v+ T" o- P+ j3 T5 X    int        listSize;    // 线性表的最大长度
& T4 D3 R1 |2 ~& l  l4 m& [}SqList;; P$ u" Y/ q" O: [/ w9 G: c, B; W

+ k1 V. N% Y3 R2 y初始化; `  d; o9 S3 `/ ^; z( F% y9 U+ G

5 h, G4 K$ f) J8 {# p9 x2 Fvoid InitList(SqList *L){; f$ G8 ?. n, S2 ^
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)) ;
; A  c* x9 Z2 x    if(!L->elem) {8 _! O# I+ \1 C1 }
        cout<<"申请空间失败!\n";
7 Z( ~& P6 g- f( O3 d; X, x' w        DestoryList(L);" ]9 i, Z3 E  H7 Q7 Z$ S7 F" n9 ?
    }
' l2 r; M9 F+ @    L->length = 0;
3 L+ [% e& M/ }) U8 b  f: `4 c    L->listSize = LIST_INIT_SIZE;
7 r+ `' Z. l4 V6 K+ [( [8 K# G    cout<<"线性表初始化完成!\n";! \0 ^- Z! c/ o2 K; n0 c
}1 ?: I  c/ I  m. e5 N$ L

& O0 f7 F- [4 k& k2 |& }增加元素2 G- q0 H( M/ h3 u. }
5 s  \! K0 j$ K  \2 `1 O
void ListAdd(SqList *L, ElemType e){  //在末尾直接增加元素
! b/ a' Y. X/ m8 k7 w% d# K    if(L->length>=L->listSize){
! l$ Z# h/ D! \' {5 l        L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));
. D. n  Z' R# ]5 F  t9 k0 ^        if(!L->elem){
2 _+ ]9 e2 H% u& c            cout<<"增加空间失败!"<<endl;
- Y6 S/ ]( V0 H% g& e            DestoryList(L);
. T. }* f1 x) Y4 ^        }
- K0 V5 p& @7 B$ {" L9 m0 G1 H- u    }0 Z) i4 r4 h6 e1 m" J$ m
    * (L->elem+L->length) = e;
7 m1 M& O- T1 t2 L    L->length ++;   
8 c  D2 Y" s% d; {}
/ u* w: W' g+ E7 e/ ?$ {2 b+ f5 s$ ^! O' v) p# q4 I- p9 Y" u" }7 Z, j
void ListAddBefor(SqList *L, ElemType e,int e_where){     //在某位置前增加元素
. u/ {) F; X, t' T+ v+ E0 F3 K    int i;
; |+ L4 j: u+ e) T# L    L->length++;7 i( v' r9 f! P1 f# I) f/ }; F
    for(i=L->length;i>=e_where;i--){
" K; Z( b) J' R' i& d        if(L->length>L->listSize){/ V- U; J6 x% {
            L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));" G* Q. [: x  M0 Y0 p
            if(!L->elem){  V) u) z" T; ?/ F1 }0 T
                cout<<"增加空间失败!"<<endl;( y' L: M$ A7 ]+ [/ k# R/ Z
                DestoryList(L);
0 c( t0 M' ?+ k9 i  e5 o* M            }+ Y* T2 W) C3 |
        }
* e0 a' M3 M( W' \4 M4 g        *(L->elem+i+1) = *(L->elem+i);        . H' W4 N% i7 i. Z6 q; R
    }4 R, @% J1 ]+ Z
    *(L->elem+e_where)=e;: ?0 g5 ?# }& {' T* M  F
    cout<<"增加后的线性表如下:"<<endl; 7 l) C4 q8 @5 h( {" k
    ListShow(L);
/ s, L' J! n6 f9 _4 h}
$ i. j7 c9 x: @& y6 I8 |4 r
1 _& E- v9 B- w( d# j1 Uvoid ListAddAfter(SqList *L, ElemType e,int e_where){     //在某位置后增加元素% F% L( i& V& s# Y3 ~* m9 i* L5 g
    int i;
9 N: R' H) c( l) w2 M8 {% P    L->length++;+ B# T9 i+ l. q/ \" J! ^; j
    for(i=L->length;i>e_where;i--){
8 l" B% l: _( j2 I0 j  M        if(L->length>L->listSize){
! @1 K# [! o" s( E9 h% M8 M            L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));8 y, T% I9 Q* ?) z; X
            if(!L->elem){
2 C' b# h) K, ~  ]3 H) _& M, A' H                cout<<"增加空间失败!"<<endl;0 k0 q5 b, n% u
                DestoryList(L);
$ D3 |$ V$ {. m1 Q( w            }: t( ^* j/ a6 W$ o; z0 N
        }
$ D1 d- f% [7 A; Q        *(L->elem+i+1) = *(L->elem+i);        
2 U1 F+ S; y  r- ^4 \8 C    }
; ^$ r7 F# S+ H0 c! p; M    *(L->elem+e_where+1)=e;
, C" E6 @" f$ X/ z, H& \! {    cout<<"增加后的线性表如下:"<<endl;
0 X9 e/ k4 r  G9 E- r* o) x    ListShow(L);
2 H# l4 u: O6 V, |}
2 s4 R) u; G/ E9 }' D0 @2 Y* ]& b
删除元素
  i) z: N1 }/ G# U0 H+ {; _8 G1 I
/ P" i: ~: Z# s. g' M! Zvoid ListDelete(SqList *L, int e_where){    //删除某位置元素 6 p( p% v- G; p" Z6 O' Q3 O% a8 Q
    L->length--;
% M  c/ V3 J2 t8 E5 I: k    for(int i=e_where;i<=L->length;i++){
* ]& K. j7 Q, x  \# W+ D        *(L->elem+i-1)=*(L->elem+i);* l" ]+ ~" D1 {) P- A
    }" j8 }2 [7 b" T4 j
    cout<<"删除后的线性表如下:"<<endl; 3 @' u) r6 j' Z6 u5 T6 j/ B
    ListShow(L);
& T( s4 [6 a( v+ J/ C  O}/ m/ X' [2 W' G% R1 a" x

5 s/ \0 b5 K7 Q销毁列表  I* r) M5 U; |; t) O& _$ ?

$ \* v; G: g' Q6 t8 Q1 ]1 jvoid DestoryList(SqList *L){8 ]) @0 z1 h$ ^5 |, S7 Y. ]2 s
    int i=0;7 q: ?3 K. s2 L* a- [- p# `7 H
    for(i=0;i<L->listSize;i++){
! F' Z+ e/ z3 l% B        free(L->elem);; m: h6 c: H/ {& n/ q7 Z
        L->elem++;
# T% {5 f- D/ s+ I6 \    }
6 H. W7 B0 W- c' P5 l! f    exit(0);        . J( ]* d9 s# N2 E
}) [8 D5 d* Q" Y
% ?( F6 z" s7 m4 D& m- w( Q' I5 J
链式表示方法
$ h/ N6 B& u1 Q8 s; _& o. P# X' K) f& I" z
结构体定义1 }1 q+ X6 D( j+ T5 D5 m
* E( ]2 S' R$ \7 o* P- Z2 U  a
typedef struct L_Node{
, b' K* `7 ^# K& }# m" g    ElemType data;
) F6 U3 N$ A. P" G8 i4 _    struct L_Node *next;+ e' a* N' ^; p4 v" _) Z7 `8 ?2 o8 y
    //struct L_Node *last;    //增加可变成双向节点 / i5 a0 ]6 b4 K& Q
}LNode;
, R* H. ~5 n0 _/ i: C) W
4 {9 ^( a- `5 R* [0 D0 j初始化
+ S$ ~9 h% r2 }- ^2 H; \; g9 d7 l0 ?. Y
void LinearNode::InitLNode(){
, p% ?" b- Z" @    HeadList = (LNode *)malloc(sizeof(LNode));
& m+ P9 V, ~3 Y) k    if(!HeadList){/ R: ?; u0 p3 Z9 f& i% \7 d% D
        cout << "初始化链表失败!" << endl;
3 B4 Q9 d; c2 \8 q. S! j- M9 k        exit(0);
! R- `' m% F9 [1 ?8 w    } 7 N" l* u& K! Y3 k( c, G( n
    EndList=HeadList;
( a: [) Q5 C$ R# Y5 }9 w    HeadList->next = NULL;# k& H2 o  i3 R: C! c8 f
    cout<< "初始化链表成功! 初始地址为:" << HeadList << endl;; E) M. z1 U  J7 U; @; z/ ?) i! i
    Length = 0;
# X; F/ L  s( r4 n6 O    e_where= 0;4 @$ r/ c( G" i) \4 L! E
}
! {( P& k7 c2 Q4 N, z1 `. S) I$ i. Y3 Y
增加节点
1 B: M/ q' _1 S) Y8 _9 _& I' ?
8 l$ A8 |2 h# H; Z6 g) Y- Svoid LinearNode::AddNodeHead(ElemType num){    //头插法
- F$ T7 d; ^$ ^    node = (LNode *)malloc(sizeof(LNode));
+ {( k2 W. K2 ]7 r    if(!node){
1 o/ @4 [; \0 [* C6 _        cout << "新建节点失败!" << endl; 4 ]- y7 ^) e6 m4 n; J9 N
        return; - ]0 l, P4 C& s0 n4 E0 v
    } + x( d4 i' O2 e# B% X/ {" ~
    node->data = num;
( ^6 H1 ~& R9 S0 e' i4 b& t% c, g    cout << node->data <<"   ";
; C2 S. o9 ~" O  U    if(NULL==HeadList->next){# E( V) f( l0 u
        node->next = NULL;1 h/ h8 E& ^6 T3 g- p
        HeadList->next = node;3 s) ?; A0 [% ?7 W5 H; ~
        EndList=node;
8 y  |0 y/ _" G9 B$ i8 A    }
7 i% ]. K* v1 z* s6 q    else{
9 z! T" h! C6 a$ y' S6 p7 P% L        node->next = HeadList->next;
" ~6 o  ?2 R0 g# Y! }8 }; C        HeadList->next=node;
! z! h# G' ]! _* {3 ?7 J! |2 G    }4 z2 t; O1 P  G& B4 {* b
    Length++; ! f: E6 {6 z0 T4 {0 P' |9 {
}
! U' q  `+ @6 }  `9 K) u8 X5 q  x- r
void LinearNode::AddNodeEnd(ElemType num){    //尾插法
" d& r7 P: i5 S+ N: g    node = (LNode *)malloc(sizeof(LNode));% L) V  S% l3 E' n# {4 i- B
    if(!node){
. s# M! W) D, h: O  x" M) [/ [        cout << "新建节点失败!" << endl;
5 |  S3 y# W, x        return; ) t; [: |) I" [  {
    } 3 q; i8 l( ~1 b: ]$ i
    node->data = num;* ~( q6 H6 A# {6 |
    cout << node->data <<"   ";$ p$ d$ v% ^# u8 b' [- P
    node->next = NULL;7 S. q4 D$ I8 z; u
    EndList->next = node;
5 T1 B" n7 Z9 C. B: D. w    EndList = node;+ k, x# m0 n, k% `  H
    Length++; ( |! u+ U8 |1 \: u
}
2 P7 H# n+ f1 A; J/ G: c1 u- x8 x" l: L1 b) n; g; t$ U) a
删除节点& o7 t8 h5 ~# L8 l/ [( l* e
0 w* f% _9 e& e( l8 j, r# F' N
void LinearNode:eleteNode(ElemType elem){1 W5 C& Q4 x" u% Z
    if(NULL==(HeadList->next)){
. A) G  _9 ^  G- s  m% N9 ]        cout<< "无节点"<<endl;- W0 S* M# _  U5 A" G
        return;
8 v: L$ N/ P" X1 C    }3 |6 r5 F4 p, `) U" H4 n7 u- C, y
    Node_cur = HeadList;5 T5 _9 r( C8 }# H" O8 @
    while(NULL!=Node_cur->next){
2 I, d4 y% y. s' m        Node_temp = Node_cur->next;
$ b- E' T8 C, @# m' K% |        if(elem == Node_temp->data){5 t% c, w. T$ ^  ]& ^+ T
            Node_cur->next=Node_temp->next;1 s: M) T; j8 a" g: l
            free(Node_temp);
; E& m5 l5 m2 S. m! U$ u9 |        }. ]% J0 C2 W8 u9 z
        if(NULL!=Node_cur->next)
$ t9 K0 o% o0 y6 F- w        Node_cur=Node_cur->next;
  X  \" W9 Z" @, l1 V7 b! w    }; h: l: y+ |9 ^- }: Y
    cout<< elem <<" 元素已删除!"<<endl;
3 _, a; F( x, e9 B( K: i* M} 9 e( Y8 `) ?: c9 R/ {6 m" T7 I

$ s  Z( T. ^. @2 X; [$ l显示链表
( p& G/ [8 H' o4 A2 Y) A9 I& t$ d1 k. ^5 e3 [
void LinearNode::ShowLNode(){
9 D! Q' A7 H- \; V    if(NULL==(HeadList->next)){- Z* F4 F1 m; F- X5 u
        cout<< "无节点"<<endl;
2 o. i) N6 P; V" q) k+ B+ ?8 ~        return;
2 L- v+ t/ E0 K+ ^6 g    }
8 h0 N$ E; [* G. T& f    Node_cur = HeadList->next; , G  B2 U/ ?* h" v  N
    while(NULL!=(Node_cur->next)){
6 r$ B5 L7 J4 ^8 j' n, N0 S! ]        cout<< Node_cur->data << "   ";
* X" L$ G8 a  ?        Node_cur = Node_cur->next;
4 o0 n; k& k# t( }+ h$ a    }
5 W$ i! G3 |( s- n5 g0 I! W( }    cout<< Node_cur->data << "   ";
& q4 \# I  x' ^# g) l' Z    cout<<"链表中的数据已显示!!"<<endl;
1 A# A- f4 j+ |% v9 [! I9 }}
9 W9 o! r  q. K# O7 x. u  d- ^2 k  ?) j3 e  z
销毁链表
9 A7 G2 d! v: s+ @1 P
' I) p8 e7 p( q1 J0 p# L0 b: H( wvoid LinearNode:estoryLNode(){' F6 I0 n4 N4 [2 h7 A! t
    Node_cur = HeadList->next;
. ~" `5 C' `% x5 J3 q! S    while(NULL!=(Node_cur->next)){2 `- K0 T  S- [! s  p
        Node_temp = Node_cur->next;
$ u& S9 G. N" ^' |' u; w        free(Node_cur);
; `2 q5 i9 b/ B) _& B/ d. u! W3 p        Node_cur = Node_temp;
2 o3 a; H1 G* m0 C7 u8 p, t. S! I    }
5 L( h- M% i* m0 `  V* b    free(Node_temp);
, o' ]% f# t5 [7 `3 r' U    cout << "数据节点已完全释放!"<<endl;
5 M* F( Q5 H0 p4 b2 u7 T- r% r/ }    free(HeadList);    // 释放头节点
2 o  I3 Y) e1 l6 x. R    cout << "头节点已释放!"<<endl; , E# V. v. W& F
————————————————
3 d! a, t. ]' P版权声明:本文为CSDN博主「星河有鱼」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。, E$ b  j4 V$ Z9 S: K+ A
原文链接:https://blog.csdn.net/Baimax1/article/details/106036286
. Z' Z/ ]5 V& J; H( u- N. E) X8 \

  d0 I+ v: F8 I- K: i8 d8 E) k, X




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5