数学建模社区-数学中国

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

作者: 杨利霞    时间: 2020-5-10 16:11
标题: 线性表顺序表示、链式表示实现方法及其异同点
8 Q/ [( }8 j1 t( m6 I
线性表顺序表示、链式表示实现方法及其异同点
  ?5 _! ]1 q9 G, I% Z) v& a线性表是最常用且最简单的一种数据结构,按存储单元排列可分为顺序表示和链式表示两种方式。
6 f7 w+ z0 ^2 Q, ]  Y& i
, v1 i+ s, Q$ b% z1 A本文采用C++实现两种表示方法。
  P8 t7 H. J$ N& a; d
1 R* D, M1 S2 n目录' [, N" Z% K0 p  j& J0 g3 ^( q
8 Y" Z' t, ~- o# w4 ~+ @7 P3 @
顺序表示和链式表示的区别:7 c7 s6 j4 n" G& g( ?" J" Z/ M
  ]3 ~8 r* p' C2 x2 O7 R
创建方式:" {, d" ~0 c4 x8 K4 ~& @

5 X1 W( \* U+ L0 z& M; X0 n4 f时间复杂度:8 x, a1 s  ?$ F& z' M/ P4 g
( J, k/ G7 U% p, |
顺序表示和链式表示的相同点:
. f+ v4 @- u7 M7 F3 R3 F1 h  W+ y+ P3 L7 G, s
删除内存空间:
' f4 O( m' V; e! H4 x/ x1 D3 ]# p8 C
代码实现:
* f7 _; t3 r7 k9 o0 ?3 Y) w) e7 x9 O1 b
顺序表示方法:
) o& {1 R( |0 T* u; ^8 B
# X6 ]" s- s& O, [7 j结构体定义: h2 n5 d! S) s! p
% k  X* ~% `6 @8 C6 ^1 s
初始化6 D) r& R0 B( f' m: s
" |& |* Q+ l/ @5 D
增加元素9 j0 g. W3 D( N/ F

& C& R! ~" Y0 h0 R0 k删除元素
5 o3 i) X( Q, H$ T1 W- Y
$ W  w) }* ?7 w) D5 g1 R$ y  @3 \销毁列表' X8 `$ x; R7 s8 G$ @6 W

5 S2 E5 m7 D& o# D8 X& s链式表示方法6 B& E. m" A8 m, O

3 [  ^* C7 U( U' V. l9 I结构体定义
0 ~  L. G) Y( O; v
  L% o: }2 ^' z  g9 J+ k( \" p初始化
( X' q3 @" ?- H, \; `- V
& P/ h# X) W- e) F- D/ J7 k; X增加节点
: c9 T! a: ]" w& @* G
" F, ]5 r0 f! w9 L9 N删除节点
* n& y( L: p$ w. j* K4 l+ J
" \) h& m, q1 w3 s, N2 `0 |& y显示链表* ~/ {; B6 o5 O

0 z* {0 D8 K- U+ y销毁链表
/ U$ I0 }( k8 T# x' c7 S& N( W0 T2 I( E- e7 u; r& |
顺序表示和链式表示的区别:2 Q4 Z) I( a( [4 J1 W! j1 E
- J  p6 u! K( G7 f
创建方式:
; S7 v0 z. I; N, F  ?; ?# }/ ~& H
# e5 f. P  r. \. m顺序表示方法单次创建多个存储单元,相邻的元素存放在连续的存储空间之中。
4 k4 ~0 C" |* x
8 ]9 K, {. z0 z7 H$ e) W4 X(PS:内存空间申请请参考https://blog.csdn.net/Baimax1/article/details/105954552)7 a  ^8 H: w8 D/ m# r" p, n" Q

; k- u9 Z  V; Y! ^/ d# L+ [$ S链式表示方法单次创建单个存储单元,存储单元之间地址不一定连续。存储单元包括数据部分和地址部分,数据部分存放需要保存的数据,地址部分保存下一个存储单元的地址(单链表,双向链表的地址部分同时也存放上一个存储单元的地址)。! d6 {3 @  ^& {) G
# ^$ [$ n+ l% X, D1 @4 h
时间复杂度:
/ _1 k2 f+ f1 l, C5 J+ D# C7 ?+ y, L- E$ v
增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(1);(PS:在未知位置的元素前 / 后操作)
/ L0 g; H5 x6 h0 ~4 V" G
  W% w) p  [& A: T增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(n);(PS:在已知位置的元素前 / 后操作)+ V9 e: {3 u5 G! o( I" V
( z  ]8 H! w+ l' d+ a7 _
PS:顺序表示需要将元素一一后移,链式存储结构需要查找该元素的位置。
7 j% {7 `+ @+ y) [$ d2 j+ V  O$ k: h) f! N& d2 \1 ?
修改 元素操作:顺序表示方法 O(1);链式表示方法O(n);
6 s$ h: O: A2 Y7 J: `& P
* B* `& e0 E( O查询 元素操作:顺序表示方法 O(n);链式表示方法O(n);
* k4 c/ {# r/ G7 X' r( Q+ H
' N3 n; ]. P% Z# ]5 g: M顺序表示和链式表示的相同点:9 z+ g8 G( B5 J3 D) J  i: i
; ?8 E+ v1 G6 _9 y: R2 T
删除内存空间:  q/ _" A* w4 B6 ^* F

' g1 \6 Z3 l1 `7 s  f3 a( y内存空间的删除都需要对每一个存储单元单独释放空间。
+ I1 k  l% m5 w/ D3 i  m. X' v) g! V! ]
代码实现:( q# B% c2 @) j; n* }2 T
2 w  x1 }3 [7 x  S
顺序表示方法:' z5 p" v) a' @) G$ i# V+ z

1 n) E& _- y& [9 D) C4 H3 T结构体定义
9 i' r5 G7 W# ?2 \/ \1 d1 p2 a% F$ B$ X8 w: E4 M
typedef struct {0 x5 i" K8 g5 ~4 @
    ElemType * elem;
* l, x+ i2 }6 j/ S  f' o    int     length;        // 线性表的现有长度 2 @5 R+ @9 O1 W# `" ~% p
    int        listSize;    // 线性表的最大长度0 c8 R' j' q) p, V- p9 ~( \
}SqList;  a  F# D2 ]& A6 S9 a2 t  f1 [+ }

' _0 o4 U3 f/ l9 a! F初始化+ V% J4 f: }* b$ ~' d  ^' @

; z5 @  |4 j, Q8 Q8 t( H* T* ?1 x) [void InitList(SqList *L){8 u( D% {8 `! |  X, T# z
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)) ;
' ~* \( r$ p4 W( M    if(!L->elem) {# B, i  X! C, @; K
        cout<<"申请空间失败!\n";9 Z  K; B. V5 K; A: a& \
        DestoryList(L);
/ Y6 E' R9 M0 |( v. _. z& B    }
$ B0 X1 ]) L* c* A6 e# U4 o  u    L->length = 0;
- ]- `3 Q; H; b/ s( L5 k( J# p9 y4 P1 i    L->listSize = LIST_INIT_SIZE;3 k! k8 k. s( a% C
    cout<<"线性表初始化完成!\n";$ X/ u7 N9 `9 [+ S: r/ W. P
}7 B$ d4 \" V$ Y7 W0 v" w

! {* u& C" F6 H# }增加元素
$ z& p! Y/ R# i# `7 C
8 `2 U( t/ B6 `2 dvoid ListAdd(SqList *L, ElemType e){  //在末尾直接增加元素/ m1 \( g' o: ?# \8 U) K* t  }$ y
    if(L->length>=L->listSize){
# l- h5 K& S0 s7 s* |) s        L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));0 J; N& ~7 `2 d4 Y* a+ ~  j
        if(!L->elem){1 O7 D# F% @4 l, I9 o0 m4 Q
            cout<<"增加空间失败!"<<endl;; y: B6 G0 O8 }8 |/ m0 u: t! {% {4 }  v
            DestoryList(L);
& s3 a. G' S0 T& z3 s3 G! h        }
9 d+ B) Y2 ]' o    }8 z2 w  d- M/ U. X( R9 g- L
    * (L->elem+L->length) = e;* H! t% V, D) W4 M- ]1 V" D8 X1 E
    L->length ++;   
  i2 ]2 @  I, k. F( R/ V4 V}
6 u7 E8 @( D- j4 Y8 D$ g7 Z
% I( t- f  v* p  b$ Uvoid ListAddBefor(SqList *L, ElemType e,int e_where){     //在某位置前增加元素
, L; R. U0 q9 O$ V6 ?    int i;
! k  q5 s+ C4 I  ~1 w" H2 B7 u    L->length++;
3 j2 F+ z  ]  {$ a# D* D    for(i=L->length;i>=e_where;i--){
& H0 a+ s5 R1 `4 C9 _* a# \        if(L->length>L->listSize){
" O' P# }% }+ }& b            L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));; O) U/ N4 I5 ?4 A  M3 D+ `/ J
            if(!L->elem){
0 b/ i) Y- u$ r3 l                cout<<"增加空间失败!"<<endl;
) b1 c8 H2 r  b( v, n6 b# m                DestoryList(L); - Z0 M6 i3 G) p6 S. i' k
            }0 E6 g+ _% E4 O
        }
* `, k- \) H+ o) U" m) y, S0 r        *(L->elem+i+1) = *(L->elem+i);        2 X0 R: m* d& R
    }
" H8 i) i/ `# ?$ L    *(L->elem+e_where)=e;
2 o4 V0 d9 h" S* [, y% W5 b    cout<<"增加后的线性表如下:"<<endl;
! T% b; e1 s" t# N2 ^    ListShow(L);
+ M2 w, D8 C7 n$ R4 U, L$ ~}
# Z( q' ~* G# e; q& u
1 s1 l/ ]+ }; C# y, `void ListAddAfter(SqList *L, ElemType e,int e_where){     //在某位置后增加元素/ y" t# V" {, g  y' O, Q3 C1 |
    int i;, k0 `& c$ T/ ]% w
    L->length++;/ a5 c8 M8 N4 \; @3 X! J8 {
    for(i=L->length;i>e_where;i--){
, B3 ]5 h0 I  H        if(L->length>L->listSize){; p9 [  K% n* G/ L* z+ ]# Z4 B* a
            L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));
: H$ n, B' }+ @6 o            if(!L->elem){
0 ~/ R* B. Z: z1 o/ B                cout<<"增加空间失败!"<<endl;" o- `$ T6 _- h* u# v4 M: i) K
                DestoryList(L);
% A+ x& x4 L4 M+ r            }
& a8 w+ x/ E: ]6 g        }& ~4 F5 t' x# E# [- M' `) B2 R3 b
        *(L->elem+i+1) = *(L->elem+i);        
0 ^( G8 n9 M) c' u; |3 u    }
- j4 D) u5 t0 @: {0 \9 J    *(L->elem+e_where+1)=e;6 W  C3 Q: @6 o) p- E
    cout<<"增加后的线性表如下:"<<endl;
6 g6 x+ s3 A* C    ListShow(L);
& q/ M* R* o, f& n. d* D3 ?: I) |}
( O9 z4 |5 J* y. X! C  l  C/ M2 y$ V0 E
删除元素; J# C1 f; t9 f2 l" r' e

6 u+ |, `1 B( w# b5 wvoid ListDelete(SqList *L, int e_where){    //删除某位置元素
0 @4 }" r" J4 ~# t. _  G    L->length--;! t1 ~8 h# }. v' ?
    for(int i=e_where;i<=L->length;i++){
8 f' W% h: C7 m; U. U6 w8 N2 K        *(L->elem+i-1)=*(L->elem+i);9 Q) Z) }' Z# D& a
    }6 g" o# ?# I1 b5 v6 v5 K5 V
    cout<<"删除后的线性表如下:"<<endl; ( x) v7 J2 s& P+ O$ m+ ^* b
    ListShow(L);
9 q: m) [+ x; K( s( k}, ?$ d2 j( ~5 a: m. y
2 S2 z; \' S' x% m$ Q
销毁列表
! q2 P" y( s. ^/ [. V8 j# l5 S$ ]  m& W0 ]: ?! `9 c. K4 i" d& w
void DestoryList(SqList *L){( G) _( R, W+ g# v  N
    int i=0;
1 _+ ^! a4 V9 g, B$ g    for(i=0;i<L->listSize;i++){4 P' S- E+ ~2 g
        free(L->elem);9 X4 G: @& Y' r3 M4 T# L
        L->elem++;1 \5 }+ m) N! ?6 c* }
    }
9 e& k0 T$ w; {7 F  x. h    exit(0);        
$ h! o+ L* s+ q/ m: I( c% |}
" o* r  [5 `# y  X5 }! T
" h8 C' X& H2 I- j- U5 b链式表示方法
- n! b% x; s+ U0 k8 E1 C  e4 i4 l) Y% }( r6 E  W9 ~8 J2 j
结构体定义
* M  k: J. }) q$ o" {& d, i% s$ [9 |, s  I6 y/ f5 i( n; s2 N
typedef struct L_Node{; G; s+ ]' V  z& @, v* z; G6 [+ s
    ElemType data;
/ f5 y. ~8 u& g, k0 w4 B% h    struct L_Node *next;0 L! q) }: G  f) l4 k9 s, _6 O
    //struct L_Node *last;    //增加可变成双向节点
. G$ ]- `6 ^0 ?- @% X1 v; G4 @}LNode;
8 R: W9 b+ Q" P& o0 `$ @! ?/ ^4 w. v8 T/ v7 }8 ~+ d
初始化8 d' M2 `) m4 k( i7 X

7 S& [8 I0 m; e4 D" V! o& Fvoid LinearNode::InitLNode(){: Q2 d6 R8 f) h1 b$ L0 \; P4 j
    HeadList = (LNode *)malloc(sizeof(LNode));5 n; j& l+ R: B, Z. l7 L( c
    if(!HeadList){
/ h3 o; d% h/ x% ^        cout << "初始化链表失败!" << endl; ! B* C; g/ Q3 W% V: O) J
        exit(0); ( W% ^/ C2 c: |: V3 G
    } 5 y& b0 p3 N* O0 c, g4 s
    EndList=HeadList;, ~# S+ f- j' ^+ n! y
    HeadList->next = NULL;
/ s4 |/ D! O+ g  }6 a" s    cout<< "初始化链表成功! 初始地址为:" << HeadList << endl;
! n3 L. W1 n( Y$ G! `) m    Length = 0;# h6 h8 q; v5 r# X
    e_where= 0;
' c9 p& E: O5 P7 V# ?# T}) O) ?' Q- Q" z; }5 p8 ~
) F3 Y5 C6 ?  W) I" n+ A. J
增加节点
7 z' U" \& x! D; T. s$ J
4 ?, h8 ^% k5 r5 b% _void LinearNode::AddNodeHead(ElemType num){    //头插法
4 z: d, m3 r& ?  D- j! Z    node = (LNode *)malloc(sizeof(LNode));
' b% d4 e3 G# l    if(!node){' \7 Q2 y0 {3 V0 D8 j& Q& `
        cout << "新建节点失败!" << endl; 4 X2 ~* H9 _* ~* J# }
        return;
: J# s* i- ]$ L" M6 `6 D% ^  K    }
( g$ p8 c3 U* w& Z* O$ w6 S    node->data = num;
1 {! |, O5 S: S    cout << node->data <<"   ";
% f8 i+ j5 i$ _7 t" v! f9 Q    if(NULL==HeadList->next){4 T' b) p# r2 ?$ r9 T2 t' [: W
        node->next = NULL;3 s2 ?5 F  N2 Q. d' q
        HeadList->next = node;
! T; P) r: y4 W# H; x4 r        EndList=node;
; l7 Q2 U$ `9 p. [- K2 v2 @    }
  @+ Z  Y  P$ q- T$ l- l    else{7 J5 S/ P( g0 P% V
        node->next = HeadList->next;! _9 L5 S: t6 G
        HeadList->next=node;3 w$ B2 l! I+ f: Z
    }
) `, A# k* r5 X( p: u- p  {    Length++; & H- i) V, [/ p* S
}
* N/ s- p" q9 N  P6 T' L9 ^( m- w. o9 g( U* v1 T4 F
void LinearNode::AddNodeEnd(ElemType num){    //尾插法
3 [2 G6 v* `6 c: g0 d' c9 L    node = (LNode *)malloc(sizeof(LNode));
: R( ?; {: v2 E0 p$ n5 e; L; d    if(!node){( d! g+ G* K6 O. ~7 K% v
        cout << "新建节点失败!" << endl; " ^0 _  ?; E2 W, [9 M4 n! P+ `
        return; 1 T2 i' P# M! H* n7 l; [9 U
    }
; C% K- A, |, u: N    node->data = num;& M3 y9 W; k5 Y: j
    cout << node->data <<"   ";
7 H" F- K/ V& n8 V4 U$ N) j& R    node->next = NULL;  O5 N3 d* c8 v
    EndList->next = node;1 v9 N: R  ~) s% b4 M1 \
    EndList = node;
8 o" [2 t/ m6 F5 W/ `$ m    Length++;
9 X7 m) B  m0 w# C% {" s0 D}
' h7 `* T( s: I  U, T: I7 y( v
* l, c0 b; d6 E, H5 l* w删除节点
* _+ i3 T1 I; N: @+ a- ^6 L. A( ~( z' e/ m5 A9 Z
void LinearNode:eleteNode(ElemType elem){
( B1 ~) \' |) K; x( \    if(NULL==(HeadList->next)){
- l) p5 t7 U* _# U" g        cout<< "无节点"<<endl;6 M/ Z3 R: n, s" I8 T
        return;
( w( Z4 g8 i( V$ {) g    }
( ~/ O; g# @2 [    Node_cur = HeadList;
4 ~4 N3 T" o8 _/ @/ q; e/ [    while(NULL!=Node_cur->next){
' F, D. v7 x8 e9 M0 u; g. ~" I        Node_temp = Node_cur->next; ( q, g' _2 _. w! Y; b7 e2 I4 c
        if(elem == Node_temp->data){
. s: \8 G0 L3 X+ x9 @9 u& e: m. c            Node_cur->next=Node_temp->next;/ z" e' M: I* W  ?  F
            free(Node_temp);9 S+ w, A8 W/ U" j9 }
        }
: W7 \/ L: P0 R  W$ }3 F( o        if(NULL!=Node_cur->next)
1 e9 ~7 e* ^+ Z& P1 R# c; w, f$ T        Node_cur=Node_cur->next;
  \6 y# {# N! [' L    }5 r2 j+ P4 y1 p" d7 L
    cout<< elem <<" 元素已删除!"<<endl;
% q  p4 @4 `* R/ G, P9 r0 C} 1 T8 @" i  L+ |6 O
; W/ V2 Y9 r' i3 ]2 _1 J
显示链表' g  ^5 u& ]  }; V. m  |
' ^- V! e5 P, L( ]# m
void LinearNode::ShowLNode(){: |, }. Z/ z. |0 n* ~
    if(NULL==(HeadList->next)){
3 X% G7 U8 v2 i        cout<< "无节点"<<endl;
& q3 X! p! }% E5 O: ?3 L! s        return; 6 s. V$ [; F' ~& _% I# Q
    }, l6 v  m* B: {  c' I
    Node_cur = HeadList->next; # E7 k' @1 j3 z1 K" y0 }6 w' ~
    while(NULL!=(Node_cur->next)){% X* U8 u4 }( u! q4 _
        cout<< Node_cur->data << "   ";" T$ b0 G9 L! D' ^4 E
        Node_cur = Node_cur->next;
/ T2 e" J- X3 J: {# g8 c    }& S3 i( u" s" H  o9 Y' O
    cout<< Node_cur->data << "   ";
5 x2 C. y# p8 v& f3 ^" w8 w5 @4 B    cout<<"链表中的数据已显示!!"<<endl;
7 I3 r" S; O( o}! p" F' Q! ^& |/ V3 \7 p' j

' ]8 C  A3 j" }9 d; p1 F销毁链表- L5 h$ G; E( u) _5 Z! R
+ w$ x. W6 ^" k5 `3 B/ v: Y' Q. e
void LinearNode:estoryLNode(){
0 l4 a4 W# r& L    Node_cur = HeadList->next; . {) ~2 b# F0 L+ X  `- Z
    while(NULL!=(Node_cur->next)){7 e  c: S# O. d! a3 |
        Node_temp = Node_cur->next;/ l( M3 C2 _; @
        free(Node_cur);# w; @0 \- D  p1 W% L
        Node_cur = Node_temp;
9 x- @. ^# `+ B% f5 a; w4 N8 [    }7 b3 K' I4 k8 D3 ^" E- u; _
    free(Node_temp);
: z3 W# y/ z6 d( x    cout << "数据节点已完全释放!"<<endl;
, E% `. E! v5 N+ k2 B* M    free(HeadList);    // 释放头节点 / I7 [1 ^* @* C& m
    cout << "头节点已释放!"<<endl; 8 w& \/ u8 l8 d! k
————————————————
" B% X7 {1 Y$ c" }2 E3 U3 y版权声明:本文为CSDN博主「星河有鱼」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。# O" h, M) L3 R; A+ @. s
原文链接:https://blog.csdn.net/Baimax1/article/details/1060362866 D4 L8 u1 ?6 K/ V# T( t. G% w
& p; l( |2 A9 H4 T- m9 r

2 U* I: M. m% d7 W5 w) q8 U: x




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