通知
此博客运行在jpress系统上,如果你喜欢此博客模板,请加QQ群:1061691290(whimurmur模板/jpress插件),免费下载使用

数据结构第一章 线性表

1861人浏览 / 0人评论 | 作者:whisper  | 分类: 数据结构  | 标签: 数据结构  | 

作者:whisper

链接:http://proprogrammar.com:443/article/dataStructure_chapter1

声明:请尊重原作者的劳动,如需转载请注明出处


    说明:该章主要讲了线性表的定义和基本操作,线性表的实现(顺序存储,链式存储),线性表的应用(顺序表,单链表,循环链表,双向链表,静态链表)

    四个名词:前插,后插,头插,尾插

    线性表的逻辑结构

    线性表是一种最简单的线性结构

    线性结构的基本特征:线性结构是一个数据元素的有序(次序)

    (1)集合中必存在唯一的一个“第一元素”;

    (2)集合中必存在唯一的一个“最后元素”;

    (3)除最后元素在外,均有唯一的后继;

    (4)除第一元素之外,均有唯一的前驱。

    抽象数据类型线性表的定义如下:

    ADT List {

        数据对象

        D={ aᵢ | aᵢ ∈ElemSet, i=1,2,...,n, n≥0 } { n 为线性表的表长; n=0 时的线性表为空表}

        数据关系

        R1={ |aᵢ₋₁ ,aᵢ∈D, i=2,...,n } { 设线性表为 (a1a2, . . . ai. . . an), i ai 在线性表中的位序}

        基本操作

        结构初始化操作;结构销毁操作;引用型操作;加工型操作

    } ADT List

    初始化操作 InitList( &L )

    操作结果:构造一个空的线性表 L

    结构销毁操作 DestroyList( &L )

    初始条件:线性表 L 已存在

    操作结果:销毁线性表 L

    引用型操作:

    ListEmpty( L ),ListLength( L ),PriorElem( L, cur_e, &pre_e ) ,NextElem( L, cur_e, &next_e )GetElem( L, i, &e )LocateElem( L, e, compare( ) )

    ListTraverse(L, visit( ))(遍历线性表)

    初始条件:线性表 L 已存在。Visit( ) 为某个访问函数。

    操作结果:依次对 L 中每个元素调用函数 visit( )。一旦 visit( )失败,则操作失败。

    注:引用型操作不改变线性表本身,没有引用操作符(&)

    加工型操作:

    ClearList( &L )PutElem( &L, i, &e )ListInsert( &L, i, e )ListDelete(&L, i, &e)

    注:加工型操作会改变线性表本身,有引用操作符(&)

    利用上述定义的线性表类型可以实现其它更复杂的操作

   1 假设:有两个集合 A B 分别用两个线性表 LA LB 表示,即:线性表中的数据元素即为集合中的成员。现要求一个新的集合 AAB

   上述问题可演绎为:

    要求对线性表作如下操作:扩大线性表 LA,将存在于线性表 LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。

    例 1 操作步骤:

    (1)从线性表 LB 中依次察看每个数据元素;

    GetElem(LB, i)e

    (2)依值在线性表 LA 中进行查访;

    LocateElem(LA, e, equal( ))

    (3)若不存在,则插入之。

    ListInsert(LA, n+1, e)( n 表示线性表 LA 当前长度)

​    void union(List &La, List Lb) {

       La_len = ListLength(La); //求线性表的长度

       Lb_len = ListLength(Lb);

       for (i = 1; i <= Lb_len; i++) {

            GetElem(Lb, i, e);//取 Lb 第 i 个数据元素赋给 e

            if (!LocateElem(La, e, equal( )))

                ListInsert(La, ++La_len, e); // La 中不存在和 e 相同的数据元素,则插入之

        }//for

    }//union

​

    有序表

    若线性表中的数据元素相互之间可以比较,并且数据元素在表中依值非递减或非递增有序排列,即 aᵢ≥aᵢ₋₁ 或 aᵢ≤aᵢ₋₁(i = 2,3,…, n),则称该为有序表。

   2:归并两个“其数据元素按值非递减有序排列”的有序表 LA LB,求得有序LC 也具有同样特性。

   设 La = (a1, , ai, , an),

   Lb = (b1, …, bj, …, bm)

    求得 Lc = (c1, , ck, , cm+n)且已由(a1, , ai-1)(b1, ,bj-1)归并得 (c1, , ck-1) ,k = 1, 2, …, m+n

    则

   

    基本操作

    (1)初始化 LC 为空表;

    (2)分别从 LA LB 中取得当前元素 ai bj

    (3)aibj,则将 ai 插入到 LC 中,否则将 bj 插入到 LC 中;

    (4)重复 2 3 两步,直至 LA LB 中元素被取完为止;

    (5)LA 表或 LB 表中剩余元素复制插入到 LC 表中。

void MergeList(List La, List Lb, List &Lc) { // 将非递减有序表 La 和 Lb 归并为 Lc 
    InitList(Lc); // 构造空的线性表 Lc
    i = j = 1; k = 0; aj; bj;// i = j = 1, k = 0
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);

    while ((i <= La_len) && (j <= Lb_len)){ // La 和 Lb 均不空
        GetElem(La, i, ai); 
        GetElem(Lb, j, bj);
        if (ai <= bj) { // 将 ai 插入到 Lc 中
            ListInsert(Lc, ++k, ai); ++i; 
        }else { // 将 bj 插入到 Lc 中
            ListInsert(Lc, ++k, bj); ++j; 
        }
    }

    while (i <= La_len) { // 当 La 不空时
        GetElem(La, i++, ai); 
        ListInsert(Lc, ++k, ai);
    } // 插入 La 表中剩余元素

    while (j <= Lb_len) { // 当 Lb 不空时
        GetElem(Lb, j++, bj);
        ListInsert(Lc, ++k, bj);
    } // 插入 Lb 表中剩余元素   
} // merge_list

      线性表的顺序存储结构

     顺序映象

    以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系最简单的一种顺序映象方法是:令 y 的存储位置和 x 的存储位置相邻。 用一组地址连续的存储单元依次存放线性表中的数据元素。

    线性表的起始地址,称作线性表的基地址

    以“存储位置相邻”表示有序对,aᵢ> 即:LOC(aᵢ) = LOC(aᵢ₋₁) + C(C为一个数据元素所占存储量)

    所有数据元素的存储位置均取决于第一个数据元素的存储位置。

    LOC(aᵢ) = LOC(a₁) + (i-1)×C (LOC(a1)为基地址)

    注意:

    存取结构:与存储结构是两个不同的概念。 存取结构是在一个数据结构上对查找操作的时间性能的一种描述。通常有两种存取结构:随机存取结构和顺序存取结构。

    随机存取结构是指在一个数据结构上进行查找的时间性能是 O(1),即查找任意一个数据元素的时间是相等的,均为常数时间,例如顺序表是一种随机存取结构。

    顺序存取结构是指在一个数据结构上进行查找的时间性能是 O(n),即查找一个数据元素的时间复杂度是线性的,与该元素在结构中的位置有关,例如单链表是一种顺序存取结构。

    顺序映象的 C 语言描述

    线性表的静态分配顺序存储结构

#define LISTSIZE 100 //存储空间最大分配量
    typedef struct{
    ElemType elem[LISTSIZE];
    int length; //当前长度
}Sqlist;

    在线性表的静态分配顺序存储结构中,线性表的最多数据元素个数为 LISTSIZE元素数量不能随意增加,这是以数组方式描述线性表的缺点。

    为了实现线性表最大存储数据元素数可随意变化,可以使用一个动态分配的数组来取代上面的固定长度数组,如下描述。

    线性表的动态分配顺序存储结构

#define LIST_INIT_SIZE 100 //初始分配量
#define LISTINCREMENT 10 //分配增量
typedef struct {
    ElemType *elem; // 存储空间基址
    int length; // 当前长度
    int listsize; // 当前分配的存储容量
     // (以 sizeof(ElemType)为单位)
} SqList; // 俗称 顺序表

    线性表的基本操作在顺序表中的实现

InitList(&L); // 结构初始化
LocateElem(L, e, compare()) ; // 查找
ListInsert(&L, i, e);// 插入元素
ListDelete(&L, i) ; // 删除元素 

    1)线性表操作InitList(&L)的实现:构造一个空表,这对表是一个加工型的运算,因此,将 L设为引用参数,首先动态分配存储空间,然后,将 length 置为 0

表示表中没有数据元素。

int InitList (SqList &L){
    L.elem = (ElemType * )malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L.elem) exit (OVERFLOW); //存储分配失败
    L.length=0;
    L.listsize = LIST_INIT_SIZE; //初始存储容量
    return OK;
}
    (2)线性表操作LocateElem(L, x, compare())

    线性表中的按值查找是指在线性表中查找与给定值 x 相等的数据元素。

    顺序表中完成该运算最简单的方法是:从第一个元素 a1 起依次和 x 比较,直到找到一个与 x 相等的数据元素,则返回它在顺序表中的存储下标或序号(二者差 1);或者查遍整个表都没有找到与 x 相等的元素,返回 ERROR

int LocateElem (SqList L, ElemType x){ 
    i=0;
    while(i<=L.length-1 && L.elem[i]!= x)
    i++;
    if (i>L.length-1) return ERROR;
    else return i; //返回的是存储位置
}

    本算法的主要运算是比较,显然比较的次数与 x 在表中的位置有关,也与表长有关。当 a1=x 时,比较 1 次成功,当 an=x 时比较 n 次成功,按值查找的平均比较次数为(n+1/2,时间性能为 O(n)

    3)线性表操作ListInsert(&L, i, e)的实现:

    首先分析:插入元素时,线性表的逻辑结构发生什么变化? (a1, , ai-1, ai, , an) 改变为(a1, …, ai-1, e, ai, …, an)

 

Status ListInsert_Sq(SqList &L, int i, ElemType e) {// 在顺序表 L 的第 i 个元素之前插入新的元素 e,i 的合法范围为 1≤i≤L.length+1
    if (i < 1 || i > L.length+1) 
        return ERROR; // 插入位置不合法
    if (L.length >= L.listsize) 
        return OVERFLOW; // 当前存储空间已满
    q = &(L.elem[i-1]); // q 指示插入位置
    for (p = &(L.elem[L.length-1]); p >= q; --p) 
        *(p+1) = *p; // 插入位置及之后的元素右移
    *q = e; // 插入 e
    ++L.length; // 表长增 1
    return OK;
} // ListInsert_Sq

    算法时间复杂度为: O( ListLength(L) )

    考虑移动元素的平均情况:

    假设在第 i 个元素之前插入的概率为 pi, 则在长度为 n 的线性表中插入一个元素所需移动元素次数的期望值为:

   

    若假定在线性表中任何一个位置上进行插入的概率都是相等的,则移动元素的期望值为:

   

    例如:

ListInsert_Sq(L, 5, 66)

q = &(L.elem[i-1]); // q 指示插入位置

for (p = &(L.elem[L.length-1]); p >= q; --p)
 *(p+1) = *p;// 从后向前依次向后移动一位

    4)线性表操作ListDelete(&L, i, &e)的实现:

    首先分析:删除元素时,线性表的逻辑结构发生什么变化?

     (a1, , ai-1, ai, ai+1, , an) 改变为(a1, …, ai-1, ai+1, …, an)

   

Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
    if ((i < 1) || (i > L.length)) return ERROR; // 删除位置不合法
    p = &(L.elem[i-1]); // p 为被删除元素的位置
    e = *p; // 被删除元素的值赋给 e
    q = L.elem+L.length-1; // 表尾元素的位置
    for (++p; p <= q; ++p) *(p-1) = *p; // 被删除元素之后的元素左移
    --L.length; // 表长减 1
    return OK;
} // ListDelete_Sq

    算法时间复杂度为: O( ListLength(L))

    考虑移动元素的平均情况:

    假设删除第 i 个元素的概率为 qi,则在长度为 n 的线性表中删除一个元素所需移动元素次数的期望值为:

   

    若假定在线性表中任何一个位置上进行删除的概率都是相等的,则移动元素的期望值为:

 

    例如:

ListDelete_Sq(L, 5, e)

p = &(L.elem[i-1]);

q = L.elem+L.length-1;

for (++p; p <= q; ++p) *(p-1) = *p;//从前向后依次左移一位

   

    线性表的链式存储结构

    (一)单链表

    概念: 用一组地址任意的存储单元存放线性表中的数据元素。

    以元素(数据元素的映象) + 指针(指示后继元素存储位置)=结点(表示数据元素或数据元素的映象)

    以“结点的序列”表示线性表——称作链表。

   

    以线性表中第一个数据元素 a₁ 的存储地址作为线性表的地址,称作线性表的头指

    有时为了操作方便,在第一个结点之前虚加一个“头结点”,以指向头结点的指针为链表的头指针。

    头指针:

    1)头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针;

    2)头指针具有标识作用,所以常用头指针冠以链表的名字;

    3)头指针是链表的必要元素。

    头结点:

    1)头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义(也可存放链表的长度);

    2)有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其他结点的操作就统一了;

    3)头结点不一定是链表的必要元素。

     结点和单链表的 C 语言描述

typedef struct LNode {
    ElemType data; // 数据域
    struct LNode *next; // 指针域
} LNode, *LinkList;
    LinkList L// L 为单链表的头指针

    单链表操作的实现

GetElem(L, i, e) // 取第 i 个数据元素
ListInsert(&L, i, e) // 插入数据元素
ListDelete(&L, i, e) // 删除数据元素
ClearList(&L) // 重新置为一个空表
CreateList(&L, n) // 生成含 n 个数据元素的链表

    1)线性表的操作 GetElem(L, i, &e)

    在单链表中的实现:

   

    单链表是一种顺序存取的结构,为找第 i 个数据元素,必须先找到第 i-1 个数据元素。因此,查找第 i 个数据元素的基本操作为:移动指针,比较 ji。令指针 p 始终指向线性表中第 j 个数据元素。

Status GetElem_L(LinkList L, int i, ElemType &e) {// L 是带头结点链表的头指针,e 返回第 i 个元素
    p = L->next; j = 1; // p 指向第 1 个结点,j 为计数器
    while (p && j<i) { p = p->next; ++j; } // 顺指针向后查找,直到 p 指向第 i 个元素或 p 为空
    if ( !p || j>i )
        return ERROR; // 第 i 个元素不存在
    e = p->data; // 取得第 i 个元素
    return OK;
} // GetElem_L

    算法时间复杂度为: O(ListLength(L))

    (2)线性表的操作ListInsert(&L, i, e)

    在单链表中的实现:有序对 <ai-1, ai>改变为 <ai-1, e> 和<e, ai>

   

    可见,在链表中插入结点只需要修改指针。但同时,若要在第 i 个结点之前插入元素,修改的是第 i-1 个结点的指针。

    因此,在单链表中第 i 个结点之前进行插入的基本操作为: 找到线性表中第 i-1 结点,然后修改其指向后继的指针。这是一种后插节点
Status ListInsert_L(LinkList &L, int i, ElemType e) {
// L 为带头结点的单链表的头指针,本算法
// 在链表中第 i 个结点之前插入新的元素 e
    p = L; j = 0;
    while (p && j < i-1) 
    { p = p->next; ++j; } // 寻找第 i-1 个结点

    if (!p || j > i-1)
        return ERROR; // i 大于表长或者小于 1

    s = new LNode; // 生成新结点

    if ( s == NULL) return ERROR;

    s->data = e; 
    s->next = p->next; p->next = s; // 插入
    return OK;
} // LinstInsert_L

    前插结点:设p指向链表中某结点,s指向待插入的值为 x 的新结点,将*s 插入*p 的前面,与后插不同的是:首先要找到*p 的前驱*q,然后再完成在*q 之后插入*s,设单链表头指针为 L

    操作如下:   

    ①q=L;

     while (q->next!=p) q=q->next; //*p 的直接前驱

    ②s->next=q->next;

    ③q->next=s;

    前插操作因为要找*p 的前驱,时间性能为 O(n)

    改进的前插:其实前插操作可以用后插操作来实现,即仍然可以将 *s 插入到 *p 的后面,然后将p->data s->data 交换即可。这样即满足了逻辑关系,也能使得时间复杂度为 O(1)

    (3)线性表的操作 ListDelete (&L, i, &e)

    在链表中的实现: 有序对<ai-1, ai> 和 <ai, ai+1> 改变为 <ai-1, ai+1>

    在单链表中删除第 i 个结点的基本操作为:找到线性表中第 i-1 个结点,修改其指向后继的指针。

q = p->next; p->next = q->next; 
e = q->data; delete(q);

 

Status ListDelete_L(LinkList &L, int i, ElemType &e) {
// 删除以 L 为头指针(带头结点)单链表中第 i 个结点
    p = L; j = 0;
    while(p->next && j < i-1) {p = p->next; ++j; } // 寻找第 i 个结点,并令 p 指向其前趋

    if (!(p->next) || j > i-1) 
        return ERROR; // 删除位置不合理

    q = p->next; p->next = q->next; // 删除并释放结点
    e = q->data; delete(q);
    return OK;
} // ListDelete_L

 

    算法的时间复杂度为: O(ListLength(L))

    4)操作ClearList(&L)

    在链表中的实现:

void ClearList(&L) {
// 将单链表重新置为一个空表
    while (L->next) {
        p=L->next; L->next=p->next;
        delete(p);
    }
} // ClearList

    算法时间复杂度:O(ListLength(L))

    5)如何从线性表得到单链表? 头插法尾插法

    链表是一个动态的结构,它不需要予分配空间,因此生成链表的过程是一个结点“逐个插入” 的过程。

    头插法:逆位序输入 n 个数据元素的值,建立带头结点的单链表。

   

    操作步骤:

    一、建立一个“空表”;

    二、输入数据元素 an,建立结点并插入;

    三、输入数据元素 an-1,建立结点并插入;

    四、依次类推,直至输入 a1为止。
void CreateList_L(LinkList &L, int n) {
// 头插法建立带头结点的单链表
    L = new LNode; L->next = NULL; // 先建立一个带头结点的单链表
    for (i = n; i > 0; --i) {
        p = new LNode;
        scanf(&p->data); // 输入元素值
        p->next = L->next; L->next = p; // 插入
    }
} // CreateList_L

     注:头插法可以实现倒序的效果

    算法的时间复杂度为: O(Listlength(L))

    尾插法:正序输入 n 个数据元素的值,建立不带头结点的单链表。

LinkList Create_LinkList2( ){ 
    LinkList L=NULL; LNode *s,*r=NULL;//r尾指针,s活动指针
    int x; scanf("%d",&x); //设数据元素的类型为 int

    while (x!=flag) {
        s=(LNode *)malloc(sizeof(LNode)); s->data=x;

        if (L==NULL) L=s; //第一个结点的处理
        else r->next=s; //其它结点的处理

        r=s; //r 指向新的尾结点
        scanf("%d",&x);
    }

    if ( r!=NULL) r->next=NULL; //非空表最后结点的指针域为空
    return L;
}

     尾插法:建立带头结点的单链表。

LinkList Create_LinkList2( ){ 
    LinkList L=(LNode *)malloc(sizeof(LNode));
    L->next=NULL; LNode *s,*r=L; //空表,r尾指针,s活动指针
    int x; scanf("%d",&x);

    while (x!=flag) {//flag结束标志
       s=(LNode *)malloc(sizeof(LNode)); s->data=x;
        r->next=s; 
        r=s; //r 指向新的尾结点
        scanf("%d",&x);
    }

    r->next=NULL; 
    return L;
}

    头结点两个优点:

    a、由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致,无需进行特殊处理;

    b、无论链表是否为空,其头指针是指向头结点的非空指针(空表中头结点的指针域为空),因此空表非空表的处理也就统一了。

    (二)其它形式的链表

    循环链表

    最后一个结点的指针域的指针又指回第一个结点的链表。

   

    和单链表的差别仅在于,判别链表中最后一个结点的条件不再是“后继是否为空”,而是“后继是否为头结点”。

    特点:

    1)对于单链表只能从头结点开始遍历整个链表,而对于单循环链表则可以从表中任意结点开始遍历整个链表。

    (2)有时对链表常做的操作是在表尾、表头进行,此时可以改变一下链表的标识方法,不用头指针而用一个指向尾结点的指针 R 来标识,可以使得操作效率得以提高。

    (3)在做链表合并和分裂时,如果不是必须从链表头开始,则可以直接在链表指针处合并,时间复杂度可达 O(1)

     双向链表

typedef struct DuLNode {
    ElemType data; // 数据域
    struct DuLNode *prior; // 指向前驱的指针域
    struct DuLNode *next;  // 指向后继的指针域
} DuLNode, *DuLinkList;

     双向循环链表

    双向链表的操作特点: 

   “查询” 和单链表相同;

   “插入” 和“删除”时需要同时修改两个方向上的指针。

      插入:

  
 
s->next = p->next; p->next = s;
s->next->prior = s; s->prior = p;

    注:已知p和s,注意不要丢失掉p的直接后继的信息

    删除:

p->next = p->next->next;
p->next->prior = p;

    特点:

    1)从某个结点出发到其直接前趋结点或直接后继结点,时间复杂度均为 O(1)

    (2)查找第 i 个结点、向第 i 个结点插入或删除第 i 个结点,都要区分是哪个方向。

    (3)如果是双向循环链表,修改指针要同时考虑在前趋环链和后继环链上的修改。

    (4)某个结点的直接前趋的直接后继,或它的直接后继的直接前趋,即为该结点本身。

    静态链表

    借助数组来描述线性表的链式存储结构,结点也有数据域 data 和指针域 next,与前面所讲的链表中的指针不同的是,这里的指针是结点的相对地址(数组的下标),称之为静态指针。

    线性表的静态单链表存储结构:

#define MAXSIZE 1000
typedef struct {
    ElemType data;
    int next;
}component,SLinkList[MAXSIZE];

    静态链表适用于不支持“指针”的高级语言,或者最大元素数固定但插入、删除操作频繁的链表应用中。有关基于静态链表上的线性表的操作基本与动态链表相同,除了一些描述方法有些区别外,算法思路是相同的。

    特点:

  (1)所有数据元素均存储在一个连续的空间段,但是相邻两个元素不一定处于相邻的空间;

  2)修改指针域即可完成插入和删除操作,不需要移动数据元素,但是也不能随机访问静态链表中的元素;

 3)一次性分配所有存储空间,插入、删除时无需再向操作系统申请或释放空间,但也限制了最大表长。

    顺序表和链表的比较

    顺序表和链表各有优缺点。

    顺序存储优点:

    (1)方法简单,各种高级语言中都有数组,容易实现。

    (2)不用为表示结点间的逻辑关系而增加额外的存储开销。

    (3)顺序表具有按元素序号随机访问的特点。

    缺点:

    (1)在顺序表中做插入删除操作时,平均移动大约表中一半的元素,因此对 n 较大的顺序表效率低。

    (2)需要预先分配足够大的存储空间,估计过大,可能会导致顺序表后部大量闲置;预先分配过小,又会造成溢出。

    链表的优缺点恰好与顺序表相反。

     在实际中怎样选取存储结构

    (1)基于存储的考虑

    顺序表在程序执行之前必须明确规定它的存储规模,也就是说事先对MAXSIZE”要有合适的设定,过大造成浪费,过小造成溢出。可见对线性表的长度或存储规模难以估计时,不宜采用顺序表;链表不用事先估计存储规模,但链表的存储密度较低。显然链式存储结构的存储密度(数据长度/节点长度)是小于1的。

    (2)基于运算的考虑

    在顺序表中按序号访问 aᵢ 的时间性能时 O(1),而链表中按序号访问的时间性能O(n),所以如果经常做的运算是按序号访问数据元素,显然顺序表优于链表;而在顺序表中做插入、删除时平均移动表中一半的元素,当数据元素的信息量较大且表较长时,这一点是不应忽视的;在链表中作插入、删除,虽然也要找插入位置,但操作主要是比较操作,从这个角度考虑显然后者优于前者。

   (3)基于环境的考虑

     顺序表容易实现,任何高级语言中都有数组类型,链表的操作是基于指针的,相对来讲前者简单些,也是用户考虑的一个因素。

    总之,两种存储结构各有长短,选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储,而频繁做插入删除的即动态性较强的线性表宜选择链式存储。

    本章学习重点

    1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系,在计算机中表示这种关系的两类不同的存储结构顺序存储结构链式存储结构

    2.熟练掌握这两类存储结构的描述方法,以及线性表的各种基本操作的实现。重点掌握:初始化、查找、插入、删除、遍历、逆置、合并、分解(8种基本操作)等操作。

    3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!