QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1530|回复: 0
打印 上一主题 下一主题

线性表顺序表示、链式表示实现方法及其异同点

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2020-5-10 16:11 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    5 t' O% G3 j+ T, b
    线性表顺序表示、链式表示实现方法及其异同点
    ' t+ Y, v7 o) c2 h: e- Z  @) V& r线性表是最常用且最简单的一种数据结构,按存储单元排列可分为顺序表示和链式表示两种方式。
    $ ~0 `. a( m+ B8 Y4 @$ F) Y
    2 b+ v/ U8 T& w6 K+ ]2 U% n本文采用C++实现两种表示方法。
    7 K! ^0 w% l# P+ x) E/ Z! a, f0 T* |$ E
    目录
    ; k% x- E3 w, u9 z: D' e$ A
    8 U1 O$ I4 m! h! _( j0 t顺序表示和链式表示的区别:
    ; Q' p* v. l1 i/ h+ A* G+ G8 n  R% F) |7 W* k
    创建方式:. L; f' J. ^8 w* s0 V1 {$ V5 {- `

    8 j8 P1 V$ d7 [7 B. P时间复杂度:
    $ b; i  U. n( h5 z+ @$ M- }* _1 x  Q9 [* o4 G+ N8 h
    顺序表示和链式表示的相同点:
    * g" @% f) y* @# {% z2 l
    5 p  M9 f8 |1 B: O; {删除内存空间:
    ; B$ ]$ Z/ d/ y. n# u1 O. A" `7 \' c  s- P, |
    代码实现:& K2 e; Y9 i* S7 o6 N, k( g
    9 ?1 R! z8 {. Z- T3 Y% k
    顺序表示方法:
    / K. e8 h/ b1 k2 u$ U7 w! z& O4 V' R
    结构体定义
    9 Y9 s, f, t, p# `1 F) T
    2 W! m7 j$ f% M+ N$ {% ^初始化
    3 \7 S0 h7 l7 E; j& G! l- l1 P! F& c4 `
    增加元素
    3 |- ?2 f( Z% o8 `4 G; N- O/ m8 l9 ?, h9 e* p
    删除元素: ~* ^7 q  z$ u& l; W7 L

    5 `% V, }3 o5 \& O6 b3 N销毁列表, i+ T& ?5 w4 k8 M  I: T
    0 o. I5 s- m9 w, l6 f0 z, a- `
    链式表示方法
    ( s. S, b4 h  Y6 b8 e5 R/ u# n/ t
    结构体定义3 a7 P/ A; d% d( d( Q

    + N, L1 ^  v/ b初始化6 F+ A: S' ]+ O
    * k; V7 c5 r& [9 S2 C3 i
    增加节点
    5 C: ~% U' G# _) t- ?) C3 c' i1 B% K/ Y
    删除节点$ m& U/ s  h! g) }

    ' {0 y9 ~" z9 M% A2 A) ^显示链表$ H" T7 Z: S- n

    2 b# b( W" Q- h# ^$ C销毁链表/ R+ S- w$ V; A4 c# d% [0 L6 A

    + M' Q$ C( {: k2 {- G: c顺序表示和链式表示的区别:
      b+ F6 ^; S6 m
    / V+ }( F* w3 j9 v  F创建方式:
    4 @- n0 ?0 v( r/ t4 k% F4 K1 B# u1 l. A1 J
    顺序表示方法单次创建多个存储单元,相邻的元素存放在连续的存储空间之中。
    & Q. S$ P( k, ?! Z1 d: ?4 ~8 s6 L- h3 o( J. ?4 n
    (PS:内存空间申请请参考https://blog.csdn.net/Baimax1/article/details/105954552)
    , C1 o; c& _/ l  ?" }4 ^! w, `& Q
    2 N, n) V9 _7 @- m6 D3 L链式表示方法单次创建单个存储单元,存储单元之间地址不一定连续。存储单元包括数据部分和地址部分,数据部分存放需要保存的数据,地址部分保存下一个存储单元的地址(单链表,双向链表的地址部分同时也存放上一个存储单元的地址)。# t- B6 b! |/ b/ l2 @$ k& G

    ) S7 ^& i  V, W; Q5 a% `# e1 e时间复杂度:9 x' A% _# Q0 H

    ' ~9 S5 H' _) ?; y增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(1);(PS:在未知位置的元素前 / 后操作)/ E; i- _) n7 i4 v5 K7 z; W
    5 Y4 {# k) t5 s
    增加 / 删除元素操作:顺序表示方法 O(n);链式表示方法O(n);(PS:在已知位置的元素前 / 后操作)
    # o. x; I' U9 }' t7 R( ]
    / [1 E6 \9 \/ ~9 XPS:顺序表示需要将元素一一后移,链式存储结构需要查找该元素的位置。
    ' o+ z+ ~. a3 p0 X0 A3 M" X; c
    ! C* Q( E( q) s, Q; j# B( S6 P修改 元素操作:顺序表示方法 O(1);链式表示方法O(n);. j9 f4 U! g. S$ e
    8 y: \, `4 ]% z+ v7 O) }0 c0 ]
    查询 元素操作:顺序表示方法 O(n);链式表示方法O(n);
    # O) W" R1 z" `* Q+ R" Y, P9 k, z7 @# l3 r
    顺序表示和链式表示的相同点:# ]; O( J+ g7 L3 E: N6 J9 f- C

    8 H& S1 ~" w5 T. W删除内存空间:$ D: b, Q, M! u" k/ {5 i

    : B$ ?7 E$ B8 L5 x+ \) D内存空间的删除都需要对每一个存储单元单独释放空间。- N, D2 m% \$ g) N: ~
    3 z/ j. [8 z7 Z5 ]$ Q& d) y+ \  z' C5 p
    代码实现:
    ; m. z' p# N2 ?6 L6 z5 l2 r9 d. ~$ V( H. i6 E
    顺序表示方法:2 A/ L( Y/ E8 Y- ~# w

    - _8 ]2 Z, {# }1 ?( N4 E结构体定义
    ; l; ^' [+ f& H- U) F: G& s: X& u7 O! u6 W  I( K
    typedef struct {
    8 r: n) p/ E) W1 d- n# S    ElemType * elem;
    * j( I8 G! k/ z' v4 N; f    int     length;        // 线性表的现有长度 ; V5 B- q( k9 E3 b
        int        listSize;    // 线性表的最大长度: W5 p# S, S9 x8 S
    }SqList;; {' b) g+ U" p+ e

    ; R1 a7 [) J1 x8 ~# e初始化/ h) _4 {" L# X& Y( z* `. P+ f
    / C- a6 Q  d/ @" B5 k) @
    void InitList(SqList *L){
    ) i% I8 U" _. z3 D    L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)) ;$ R. P5 w' \3 M0 \
        if(!L->elem) {
    + F5 M. [# {( Z+ @- T" \        cout<<"申请空间失败!\n";* N7 F" ~& o% C4 J- Q# P6 C
            DestoryList(L);; S% i) `6 e; I! _0 k6 F
        }
      W5 v4 K9 R0 @% z) a    L->length = 0;, q9 U! g9 B% G  P  L9 Q
        L->listSize = LIST_INIT_SIZE;. [; J9 V! b! [( i) Q: n7 p* h
        cout<<"线性表初始化完成!\n";
    . P8 P# J: I: h}* n9 L' C! O( b
    2 x$ L( f' Y- x. E3 T% I" S7 ?% y
    增加元素, M7 F' L1 i) X7 J
    * j& Y+ |; e3 a& n
    void ListAdd(SqList *L, ElemType e){  //在末尾直接增加元素
    : d% p" }: `0 o" ]( i# C1 }: D    if(L->length>=L->listSize){
    4 P6 J/ T, m/ y! [- N        L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));8 l8 b8 l& @1 g6 {, u
            if(!L->elem){& J2 |7 {, P3 @2 y3 v- `
                cout<<"增加空间失败!"<<endl;% e( w3 Q, f. i
                DestoryList(L);+ q' u9 @: s6 g! D$ H: q) o
            }
    9 ?( d7 }' j+ a- J4 o5 M4 j/ _    }0 r; `. L* V5 [6 u
        * (L->elem+L->length) = e;
    & H3 E0 ^4 o5 o' z    L->length ++;   
    ! x' f' k; i$ g  P" `}
    ' T: I6 g$ Y' u' A! g) r3 g
    % _6 ~0 E" _* W) V% x0 K% n" q, h, vvoid ListAddBefor(SqList *L, ElemType e,int e_where){     //在某位置前增加元素
    : G$ b" E" i" r7 N# X- |    int i;: H4 m; D/ s: [7 j8 Q
        L->length++;
    ! I! u, F: t9 ~4 F) L8 ^; K" W, T! E    for(i=L->length;i>=e_where;i--){
    " y' p9 h9 n# s* y2 _% P6 ]( C& d        if(L->length>L->listSize){
    1 |6 W, H: F( w; a( g2 }' k            L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));% Q' u1 a  L7 h7 F, K
                if(!L->elem){8 j7 G( H/ h$ B. X: F
                    cout<<"增加空间失败!"<<endl;
    8 D1 p' r2 v, R) N% S5 }: \                DestoryList(L); * }( g6 t5 V, \7 D+ t
                }# l& Q. E  E  t! o
            }# Y& s  r  i6 S1 k
            *(L->elem+i+1) = *(L->elem+i);        9 ^4 \, r& Y; r( ~. }$ X9 L( g
        }
    3 @& B) l3 s" {0 t    *(L->elem+e_where)=e;
    ! K1 P1 p. J  t( T) ]2 e0 P    cout<<"增加后的线性表如下:"<<endl;
    2 U0 F8 }/ r! e    ListShow(L);, \- t1 O+ ]  T9 N: Q/ E: f
    }
    * X0 I$ N3 j# F( P0 w: A5 U) N; J0 \/ T1 ^: s2 K, b/ B1 |; _
    void ListAddAfter(SqList *L, ElemType e,int e_where){     //在某位置后增加元素" j$ h! P; G/ Z9 s7 `2 a; y
        int i;
    + X3 s9 [' \& V0 {! d    L->length++;
    , n4 {( P3 ]! m0 x* g$ g$ Y' m7 [    for(i=L->length;i>e_where;i--){+ P/ z0 P' o- t; d# J! D
            if(L->length>L->listSize){
    ( @! B  W; x" v7 ?# B$ V            L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));+ a' @+ ?1 I1 j
                if(!L->elem){
      n3 ~# x- L5 r: {/ T2 h, A1 ?                cout<<"增加空间失败!"<<endl;: C& N8 Y# S% T, f2 _+ Q# F
                    DestoryList(L); ! w, n0 W: d+ y! ]
                }
    ) D2 z& y! Y: V+ [        }' Z. A9 M: |  o& Y+ q" M0 m
            *(L->elem+i+1) = *(L->elem+i);        7 o7 x: i9 Z- c' G8 ]
        }% ]! v& h+ R) G$ y
        *(L->elem+e_where+1)=e;3 k/ q& Z: H( E# W# i5 A) H% a
        cout<<"增加后的线性表如下:"<<endl;
    ( L4 i) N- ?% S0 |! u6 [    ListShow(L);& @$ k9 y  l- l. S: I& e
    }
    0 a: u" W& L! c) @+ o3 L$ J# T( `* E' G! j
    删除元素
    3 T+ j3 P9 M( S+ E$ |5 K& ~, q7 Q# n% {0 R" W1 z& X( k
    void ListDelete(SqList *L, int e_where){    //删除某位置元素 1 B! g! |8 |0 S
        L->length--;% I) j2 [& l$ ~+ n# [
        for(int i=e_where;i<=L->length;i++){' a3 e5 w- N& x' w
            *(L->elem+i-1)=*(L->elem+i);3 j4 L8 j/ J6 c; h- _
        }
    # k  z) Y" D$ ~) ?* W    cout<<"删除后的线性表如下:"<<endl; 9 @' [) M4 P, A# H* \( i! H
        ListShow(L);" t0 u( v' k- I4 ^$ e7 V5 ]2 ?
    }
    / R1 Z8 A2 ^; Z3 [6 d0 q8 Y$ u$ Z& }
    销毁列表
    4 U* ^' V: A1 d6 q- _7 G8 P$ e) G" v' K* r. F7 _2 g
    void DestoryList(SqList *L){+ G6 l; p  y4 ?9 L2 _. W( D
        int i=0;/ o" Q% {$ N3 L4 k0 B
        for(i=0;i<L->listSize;i++){3 M4 r' b) T$ x9 q6 A
            free(L->elem);
    " G0 H; r$ C5 Y4 Y6 H$ P0 P        L->elem++;
      U1 e) p, Z- l- y6 [( G& z    }
    ! i2 a7 \- u2 g7 t: M5 g  u' G    exit(0);        2 K( r! k/ q) W* U6 K
    }
    ( d( f: ?1 x* y# t7 M3 y
    : o8 K; n# I: z链式表示方法( H  @6 P  N5 r: k9 Q
    8 C& g& K* h5 O7 l
    结构体定义
    * B3 i: ^/ J/ |) |& p0 {0 m% A  M5 b- s& |
    typedef struct L_Node{
    : A, e4 L+ z: x! b    ElemType data;
    2 W4 j4 K1 @1 H/ C    struct L_Node *next;
    ) V1 Z' l3 L8 x$ V' C    //struct L_Node *last;    //增加可变成双向节点
    # k9 z6 r' V) s) h5 O}LNode;
    - l' k) _6 ?& m+ p3 N7 Q, `4 F* Z7 }' Z$ o
    初始化) H. F1 p4 h4 l
    2 W0 p* j. ]' {1 V& e- `4 v
    void LinearNode::InitLNode(){
    6 T5 U* I$ C4 n- K    HeadList = (LNode *)malloc(sizeof(LNode));
    2 H' {- [& h% k" b    if(!HeadList){
    ( d2 d" V- l' ?/ A3 j4 I! n- i        cout << "初始化链表失败!" << endl; : r0 E/ U% x. D$ _1 }: f
            exit(0); + f) O9 k/ ^  L% }
        } : n& c1 D( C" V
        EndList=HeadList;
    $ A/ h6 y; Z/ e. Y. [, q    HeadList->next = NULL;
    6 h# t. Q; _! ~- J4 {( _    cout<< "初始化链表成功! 初始地址为:" << HeadList << endl;
    . H( b+ R! ~7 d8 M$ t" R    Length = 0;+ x7 J/ n/ @/ x' K& l* A" ^& s
        e_where= 0;9 Y+ v5 x+ Z* F' w
    }2 G# V, B- k0 R0 s
    + g* I! G9 o; a% F( b; U% Y
    增加节点
    $ Q9 |/ v6 I- C/ v! K1 M+ A- j- r' r/ P3 Z4 o
    void LinearNode::AddNodeHead(ElemType num){    //头插法
      l, {4 C6 P1 }0 B; B3 c0 u    node = (LNode *)malloc(sizeof(LNode));
    % R, _# h( y) e; S5 N/ P    if(!node){6 d9 ^% n# r$ i2 N6 T7 W
            cout << "新建节点失败!" << endl;
    5 L9 i4 S8 }0 Q5 d( X! A" w        return;
    ' B5 g7 b8 ?4 Y/ ?# L. K    }
    % T1 R, S$ n) Y, o, ?    node->data = num;
    % p2 q6 p( B7 ?$ |" ]" X7 g$ n    cout << node->data <<"   ";+ W* y# T/ i+ {/ u) K- i" f5 [* a# k0 q
        if(NULL==HeadList->next){
    " h  s, G5 z* [8 F        node->next = NULL;* v4 V! ?$ r- x
            HeadList->next = node;
    1 h8 D) C! N+ Z9 G; b        EndList=node;& M; Y9 p/ u$ {3 ?! M1 \6 t: O& `
        }$ x/ d0 G) U! G8 V" X9 i
        else{
    . l. }6 p" \. B( J        node->next = HeadList->next;
    4 W2 l# @: X4 K7 I: q) c9 b& C/ l        HeadList->next=node;
    # P* R0 U  ]6 \+ ~; ]    }7 D) }, h0 W0 t- ~2 m3 `
        Length++; . V' \4 n. [7 L/ R- A
    }
    % [1 k$ x0 f, J
    7 x+ ?, U# e  n/ P8 ]6 Q+ V+ ^void LinearNode::AddNodeEnd(ElemType num){    //尾插法 ) m" M5 W* I6 u. G& ~3 S
        node = (LNode *)malloc(sizeof(LNode));# z$ Y, _1 Q8 m' u" O4 c
        if(!node){+ ]9 B# t7 D# b- k! d
            cout << "新建节点失败!" << endl; 7 {: A2 c+ S" ^2 g  w# w. f
            return; ) x9 T6 n8 J' K+ o( V
        }
    ; `0 u' r, N2 [    node->data = num;' m2 T* c$ N; N' t
        cout << node->data <<"   ";
    + ?- P2 m% r; g1 t2 I    node->next = NULL;# w% |5 N! p. C4 {- I" q1 l
        EndList->next = node;- m. r# _# y) o  |/ F
        EndList = node;
    + J5 O4 \. n' G( q+ w    Length++;
    6 B/ _: P6 b2 T3 u- U}
    + Z4 @$ E8 w5 A/ G5 q. z) ?% K" \' f& q' f0 Z. X: z
    删除节点
    " P$ U! O0 W# M& v# @7 {# q2 ?! O$ A. |. b# t
    void LinearNode:eleteNode(ElemType elem){
    + {9 N% C6 F) ?, I) k3 A# c/ H) v    if(NULL==(HeadList->next)){- l* w5 W& Y& M, r( o. i8 P6 D
            cout<< "无节点"<<endl;/ ^4 z8 r$ f+ ]0 g
            return; 0 R* ]" V0 h3 v9 [" w. D* D
        }
    . T0 l0 V  p1 Z! P9 E    Node_cur = HeadList;/ |# X: ^7 G1 x5 o. V/ e9 u7 n
        while(NULL!=Node_cur->next){
    . y, n! m9 @3 Z$ _. x. j. V! i        Node_temp = Node_cur->next; 4 L$ q: c5 l; e; k
            if(elem == Node_temp->data){0 @8 L4 z4 e* ?
                Node_cur->next=Node_temp->next;0 u* L! i# F* m/ l5 z/ e
                free(Node_temp);
    + b8 b% Z6 W/ w: ~! Z- G        }( n* J/ Z; W; X6 i) u" X. Q8 V
            if(NULL!=Node_cur->next)2 o8 `5 ?# A8 d* T9 o
            Node_cur=Node_cur->next;
    7 v" ~! {; H3 j; [; l7 w, m    }1 V, T& `) }+ N( Y! b
        cout<< elem <<" 元素已删除!"<<endl;
    . s, b! U/ Z7 n6 }5 r/ i} 7 P6 D, X. d" ]7 ]
    . L2 C8 W  W( R3 N
    显示链表6 X: t' x2 c7 ?9 b" ?1 ~
    4 ~# \; X3 `5 [5 f' t. t
    void LinearNode::ShowLNode(){
    * z, V2 H9 I) k2 `, c1 \6 z    if(NULL==(HeadList->next)){
    ) _. X6 `! R' _& |        cout<< "无节点"<<endl;
    ! D2 |0 z& _% |, w$ t8 Z. q5 _        return;
    / U/ K8 Z2 K& _    }- x* n& }, ]6 r2 l
        Node_cur = HeadList->next;
    . |4 z* d" Q+ n5 T0 n6 Y) g    while(NULL!=(Node_cur->next)){
    1 s+ H7 J$ a  _5 l        cout<< Node_cur->data << "   ";6 `* M5 |) c2 _# y* }4 E
            Node_cur = Node_cur->next;
    ; @+ W/ k/ K0 J' I    }
    & f; u5 x' L- M& J5 r0 T: X    cout<< Node_cur->data << "   ";1 W& j2 X/ S6 Y7 X
        cout<<"链表中的数据已显示!!"<<endl;
    . r3 N) d0 W  X" z$ j% A, t}
    6 |" ?1 w* d( [5 `9 m) B$ ]' R: m+ z2 H8 p! L+ n
    销毁链表
    ' X7 a/ ^2 x: V) p6 A% e, ]
    4 j% K4 c& K' H* k7 |- Evoid LinearNode:estoryLNode(){
    7 Q; F9 O7 _" \9 |    Node_cur = HeadList->next;
    8 p* o. R) g9 L/ N. O9 j: W    while(NULL!=(Node_cur->next)){* k. p/ ]  y0 T! m1 m9 V' w
            Node_temp = Node_cur->next;8 s6 E( A- m: N) E' r
            free(Node_cur);+ r$ J4 ^2 f% A) L; V8 d( Q
            Node_cur = Node_temp;& J! W$ s+ ]" g" l3 l# R
        }
      _6 m0 j# X9 J1 c# F. W, C    free(Node_temp);, W6 y* s) ?- R  o! \, m1 {
        cout << "数据节点已完全释放!"<<endl;
    2 S/ k# r% y* y8 u    free(HeadList);    // 释放头节点
    4 H. g& e: P: n6 g% G$ R* S    cout << "头节点已释放!"<<endl; ' I2 R; f* J. ?+ T8 x
    ————————————————
    ) Y7 a# o% j8 V+ w" \4 n% Z: u版权声明:本文为CSDN博主「星河有鱼」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    5 h& Q$ \$ U! J5 d9 X  ~原文链接:https://blog.csdn.net/Baimax1/article/details/1060362867 v, Y) M8 H  B3 J8 i
    0 s" i% E' F4 A
    ' Z0 s( j* d7 l
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-4-20 19:38 , Processed in 0.435954 second(s), 51 queries .

    回顶部