02

线性表的定义

���性表（List）：零个或多个数据元素的有限序列

强调几个关键地方

• 序列：也就是说，元素之间是有顺序的
• 有限：线性表强调是有限的（实时上计算机处理的对象都是有限的，无限只存在于数学的概念中）

  线性表元素的个数n( n ≥ 0 n \geq 0 n≥0)，定义为线性表的长度，当n=0时，称为空表

  线性表的抽象数据类型

  ADT 线性"' (List)Data线性在的数据对象集合为 {a1,a2,..,an} ，每个元素的类型均为 DataType。 其中，除第一个元素a1外,每一个元素有且只有一个直接前驱元素，除最后一个元素an 外， 每一个元素有且只有一个直接后驱元素。数据元素之间的关系是一对一的关系 。OperationInitList (*L) : 初始化操作，建立一个空的线性表L。ListEmpty (L) : 若线性表为空，返回 true ，否则返回 false。ClearList (*L) : 将线性表清空.GetElem (L,i,*e) :将线性表L中的第i个位置元素值返回给e。LocateElem (L,e) :在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功;否则.返回0表示失败。Listlnsert (*L,i,e) : 在线性表 L 中的第 1 个位置输入新元素e。ListDelete (*L,i,*e ) :删除线性表 L 中第i个位置元素，并用 e 返回其值。ListLength (L) : 返回线性表 L 的元素个数。endADT

  线性表的顺序存储结构

  线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

  顺序存储方式

  #define MAXSIZE 20typedef int ElemType;typedef struct{    ElemType data[MAXSIZE];    int length;}SqList;

  • 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
  • 线性表的最大存储容量：数组长度MAXSIZE。
  • 线性表的当前长度：length。

    数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般是不变的。

    线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。

    在任意时刻，线性表的长度应该小于等于数组的长度。

    地址计算方法

    数据元素的序号和存放它的数组下标之间存在对应关系：

    线性表的第 i 个元素是要存储在数组下标为 i-1 的位置。

    其实，内存中的地址，就和图书馆或电影院里的座位一样，都是有编号的。 存储器中的每个存储单元都有自 己的编号 ，这个编号称为地址。当我们占座后，占座的第一个位置确定后，后面的位置都是可以计算的 。

    假设占用的是 c 个存储单元，那么线性表中第 i+1 个数据元素的存储位置和第i 个数据元素的存储位置满足下列关系( LOC 表示获得存储位置的函数)。

    L O C ( a i + 1 ) = L O C ( a i ) + c LOC(a_{i+1}) = LOC(a_i)+c LOC(ai+1​)=LOC(ai​)+c

    所以对于第 i 个数据元素 ai 的存储位置可以由 a1 推算得出:

    L O C ( a i ) = L O C ( a i ) + ( i − 1 ) ∗ c LOC(a_i) = LOC(a_i)+(i-1)*c LOC(ai​)=LOC(ai​)+(i−1)∗c

    线性表顺序存储结的存取时间性能为O(1) 。我们通常把具有这一特点的存储结构称为随机存取结构。

    顺序存储结构的插入与删除

    获取元素操作

    实现GetElem 操作，即将线性表L中的第i 个位置元素值返回

    #define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Statue;Statue GetElem (SqList L ,in i ,ElemType *e){    if(L.length ==0 ||| iL.length)        return ERROR;    *e = L.data[i-1];    return OK;}

    插入操作

    插入算法的思路：

    • 如果插入位置不合理，抛出异常；
    • 如果线性表长度大于等于数组长度，则抛出异常或者动态增加容量；
    • 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
    • 将要插入元素填入位置i处；
    • 表长加1。

      Status ListInsert(SqList *L,int i,ElemType e){    int k;    if(L->length == MAXSIZE) return ERROR;    if(iL->length+1) return ERROR;    if(ilength){        for(k=L->length-1;k>i-1;k--)            L->data[k+1]=L->data[k];    }    L->data[i-1] = e;    L->length++;    return OK}

      删除操作

      删除算法的思路：

      • 如果删除位置不合理，抛出异常
      • 取出删除元素
      • 从删除元素的位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置
      • 表长减1

        Status ListDelete(SqList *L,int i,ElemType *e){    int k;    if(L->length == 0) return ERROR;    if(iL->length) return ERROR;    *e = L->data[i-1];    if(ilength){        for(k=i;klength;k++)            L->data[k-1]=L->data[k];    }    L->length--;    return OK}

        线性表顺序存储结构的优缺点

        • 优点
          • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
          • 可以快速地存取表中任一位置的元素
          • 缺点
            • 插入和删除操作需要移动大量元素
            • 当线性表长度变化较大肘，难以确定存储空间的容量
            • 造成存储空间的"碎片"

              线性表的链式存储结构

              线性表链式存储结构定义

              线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。

              为了表示每个数据元素 a i a_i ai​与其直接后继数据元素 a i + 1 a_{i+1} ai+1​之间的逻辑关系 ， 对数据元素 a i a_i ai​来说 ， 除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域 ， 把存储直接后继位置的域称为指针域 。 指针域中存储的信息称做指针或链 。 这两部分信息组成数据元素 a i a_i ai​ 的存储映像，称为结点(Node) 。

              n 个结点( a i a_i ai​的存储映像) 链结成一个链衰，即为线性表( a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1​,a2​,...,an​) 的链式存储结构，因为此链表的每个结点中只包含一个指针域 ，所以叫做单链表 。

              对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针

              在单链表的第一个结点前附设一个结点，称为头结点 。头结点的数据域可以不存储任何信息

              头指针与头结点的异同

              • 头指针
                • 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
                • 头指针具有标识作用，所以常用头指针冠以链表的名字
                • 无论链表是否为空，头指针均不为空。头指针是链表的必要元素
                • 头结点
                  • 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义
                  • 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
                  • 头结点不一定是链表必须要素

                    线性表链式存储结构代码描述

                    若钱’性表为空袭，则头结点的指针域为"空"

                    若带有头结点的单链表

                    /*线性表的单链表存储结构*/typedef struct Node{    ElemType data;    struct Node *next;} Node;typedef struct Node * LinkList;

                    从结构定义中可以看出，结点由存放数据元素的数据域、存放后继结点地址的指针域组成。

                    单链表的读取

                    获得链表第i个数据的算法思路

                    • 声明一个节点p指向链表第一个节点，初始化j从1开始；
                    • 当 j
                    • 若到链表末尾p为空，则说明第 i 个元素不存在；
                    • 否则查找成功，返回节点p的数据

                      /*初始条件：顺序线性表L已存在，1    int j;    LinkList p;    p = L-next;    j=1;    while(p && j        p=p-next;        ++j;    }    if(!p || ji)        return ERROR;    *e = p->data;    return OK;}

                      单链表的插入与删除

                      单链表插入

                      单链表第i个数据插入结点的算法思路：

                      • 声明一结点p指向链表第一个结点，初始化j从1开始；
                      • 当j
                      • 若到链表末尾p为空，则说明第 i 个元素不存在；
                      • 否则查找成功，在系统中生成一个空结点 s;
                      • 将数据元素 e 赋值给 s->data;
                      • 单链表的插入标准语句：s->next=p->next； p->next=s ;

                        /*初始条件：顺序线性表L已存在，1    int j;    LinkList p,s;    p = *L;    j=1;    while(p && j        p=p-next;        ++j;    }    if(!p || ji)        return ERROR;    s = (LinkList)malloc(sizeof(Node)); // 生成新结点    s-data = e;    s->next = p->next;    p->next = s;    return ok}

                        单链表删除

                        单链表第i个数据删除节点的算法思路：

                        • 声明一结点p指向链表第一个结点，初始化j从1开始；
                        • 当j
                        • 若到链表末尾p为空，则说明第 i 个元素不存在；
                        • 否则查找成功，将要删除的结点p->next赋值给q；
                        • 单链表的删除标准语句 p->next = q->next;
                        • 将去节点中的数据赋值给e，作为返回；
                        • 释放q节点

                          /*初始条件：顺序线性表L已存在，1    int j;    LinkList p,q;    p = *L;    j = 1;    while(p-next && j        p=p-next;        ++j;    }    if(!(p-next) || j>i)        return ERROR;    q = p->next;    p->next = q->next;    *e = q->data;    free(q);    return ok;}

                          单链表结构与顺序存储结构优缺点

                          • 存储分配方式
                            • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
                            • 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
                            • 时间性能
                              • 查找
                                • 顺序存储结构O(1)
                                • 单链表O(n)
                                • 插入和删除
                                  • 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
                                  • 单链表在找出某个位置的指针后，插入和删除时间为O(1)
                                  • 空间性能
                                    • 顺序存储结构需要预分配存储空间，分大了，浪费，分小了已发生上溢
                                    • 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

                                      其他线性表

                                      静态链表

                                      在早期高级编程语言（Basic，Fortran等）没有指针，通过数组模拟指针，来描述单链表。

                                      循环链表

                                      将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表

                                      双向链表

                                      双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。