什么是线性表？

线性表（List）：由零个或多个数据元素组成的有限序列

• • 首先它是一个序列
  • 若元素存在多个，则第一个元素无前驱，而最后一个元素无后继，其他元素有且职友一个前驱和后继
  • 线性表强调是有限的
  • 线性表的个数n(n>=0)定义为线性表的长度，当n=0时，称为空表

 抽象数据类型

　　数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称

例如在C语言中按照取值不同，数据类型可以分为两类：

　　原子类型：不可以再分解的基本类型，例如整型，浮点型，字符型

　　结构类型：由若干个类型组合而成，是可以再分解的，例如整型数组

抽象：是指由取出事物具有的普遍性的本质，它要求抽出问题的特征而忽略非本质的细节，是对具体事务的一个概括

抽象数据类型：是指一个数学模型及定义在该模型上的一组操作

• • 我们对已有的数据类型进行抽象，就有了抽象数据类型
  • 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关
  • 例如我们定义一个坐标Vector3由x、y、z三个整型数据组合，那么Vector3就是一个抽象数据类型

描述抽象数据类型的标准格式：

ADT 抽象数据类型名
Data
    数据元素之间逻辑关系的定义
Operation
    操作
endADT

 线性表类型定义

ADT 线性表（List）
Data
    线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType
Operation
    InitList(*L):建立一个空的线性表L
    ListEmpty(L):判断线性表是否为空表，为空返回true,不为空返回false
    ClearList(*L):将线性表清空
    GetElem(L,i,*e):将线性表L中的第i个位置元素值返回给e
    LocateElem(L，e):在线性表L中查找与给定值e相等的元素，成功返回true,失败返回false
    ListInset(*L,i,e):在线性表L第i个位置插入元素e
    ListDelete(*L,i,*e):删除线性表L中第i个位置的元素并用e返回其值
    ListLength(L):返回线性表L的元素个数
endADT

线性表的顺序存储结构

线性表由两种物理存储结构：顺序存储结构和链式存储结构

 线性表的顺序存储结构定义：

　　指的是用一段地址连续的存储单元依次存储线性表的数据元素

• 线性表的第一个数据元素的存储位置称为起始位置或基地址
• 顺序表顺序存储结构必须占用一片连续的存储空间，只要知道某个元素的存储位置就可以知道其他元素的存储位置
• 地址计算方法
  • 假设线性表的每个元素需要c个存储单元，则第i+1个数据元素的存储位置和第i个数据元素的存储位置之间的关系满足：LOC(ai+1)=LOC(ai)+c
  • 所以对于第i个数据元素ai的存储位置可以由a1推算得出：LOC(ai)=LOC(a1)+(i-1)*c

【间隔i-1个存储单元,间隔(i-1)*c个地址】

线性表顺序存储的结构代码：

1 #define MAXSIZE 20
2 typedef int ElemType;
3 typedef struct
4 {
5     EleType data[MAXSIZE];
6     int length;  //线性表当前长度
7 } SqList;

 总结下，顺序存储结构封装需要三个属性：

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

线性表的基本操作

操作中用到的预定义常量和类型：

 1 //函数结果状态代码
 2 #define TRUE 1
 3 #define FALSE 0
 4 #define OK 1
 5 #define ERROR 0
 6 #define INFEASIBLE -1
 7 #define OVERFLOW -2
 8 
 9 //Status 是函数的类型，其值是函数结果状态代码，如OK等
10 //初始条件，顺序线性表L已存在，1 <= i <=ListLength(L)
11 
12 typedef int Status;
13 typedef char ElemType;

• 线性表L的初始化

  1 Status InitList_Sq(SqList &L){             //构造一个空的顺序表L
  2     L.elem=new ElemType[MAXSIZE];        //为顺序表分配空间
  3     if(!L.elem)exit(OVERFLOW);            //存储分配失败
  4     L.length=0;                            //空表长度为0
  5     return OK;
  6 }

• 销毁线性表

  1 void DestroyList(SqList &L){
  2     if(L.elem)
  3     {
  4         free(L.elem);//释放存储空间
  5     }
  6 }

• 获得元素操作

  1 //操作结果：用e返回L中第i个数据元素的值
  2 int GetElem(SqList L,int i,ElemType &e){
  3     if(i<1||i>L.length)   //判断i值是否合理，若不合理，返回ERROR
  4     retrun ERROR;
  5     else e = L.length[i-1]; //将i-1存储单元的数据给e
  6     return OK;
  7 }

• 清空线性表

  1 void ClearList(SqList &L){
  2     L.length=0; //将线性表的长度置为0
  3 }

• 求线性表的长度

  1 int GetLength(SqList L){
  2     return L.length; 
  3 }

• 判断线性表L是否为空

  1 int IsEmpty(SqList L){
  2     if(L.length==0)return 1;
  3     else return 0; 
  4 }

• 顺序表的查找（查找在L中与指定值e相同的数据元素的位置）

   1 int LocateElem(SqList L,ElemType e){
   2     //在线性表L中查找值为ｅ的数据元素，返回其序号（是第几个元素）
   3         for(i=0;i<L.length;i++)
   4         {
   5             if(L.elem[i]==e)
   6             {
   7                 return i+1;  //查找成功，返回序号
   8             }
   9             
  10         }
  11         return 0;  //查找失败，返回0
  12 }

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

    /*操作结果：在L中第i个位置之前插入新的数据元素e，L长度+1*/
    
    Status ListInsert(Sqlist *L, int i,ElemType e)
    {
        int k;
    
        if(L->length == MAXSIZE) //顺序线性表已经满了
        {
            return ERROR;
        }
        if (i<1 || i>L->length+1)//当i不在范围内时
        {
            return ERROR;
        }
        if(i <= L->length)//若插入数据位置不在表尾
        {
            /*将要插入位置后数据元素向后移动一位*/
            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；

    /* 操作结果：删除L的第i个数据元素，并用e返回其值，L长度-1 */
    
    Status ListDelete(Sqlist *L, int i,ElemType e)
    {
        int k;
    
        if(L->length == 0) //顺序线性表已经满了
        {
            return ERROR;
        }
        if (i<1 || i>L->length)//当i不在范围内时
        {
            return ERROR;
        }
    
        *e = L->data[i-1];//赋值给e指针，返回其值
    
        if(i <= L->length)//若删除数据位置不在表尾
        {
            /* 将删除位置后面的元素向前移动一位 */
            for ( k=i; k<L->length; k++)
            {
                L->data[k-1] = L->data[k];
            }
        }
    
        L->length--;//表长-1
    
        return OK;
    }

•  单链表的整表创建，思路：
  • 声明一结点p和计数器变量i
  • 初始化一空链表L
  • 让L的头结点的指针指向NULL，即建立一个带头结点的单链表
  • 循环实现后继结点的赋值和插入
• 头插法建立单链表，思路：
  • 先让新节点的next指向头节点之后
  • 然后让表头的next指向新节点

/* 头插法建立单链表示例 */
void CreateListHead(LinkList *L,int n)
{
    LinkList p;
    int i;

    srand(time(0));//初始化随机数种子
    //srand函数是随机数发生器的初始化函数

    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;

    for ( i = 0; i < n; i++)
    {
        p = (LinkList)malloc(sizeof(Node));//生成新结点

        p->data = rand()%100+1;
        /*  rand() 是产生一个容随机整数的函数，其分布范围是0到最大的整数，
            rand() %100 指和100取余，得到一个0到99整数
            rand() %100 +1 得到一个1到100的整数 */
            
        p->next = (*L)->next;//p指向下一个 
        (*L)->next = p;//再将p给单链表L的表头 
    }
    
}

• 尾插法建立单链表，思路：
  • 把新结点都插入到最后，这种算法称之为尾插法。
    （小甲鱼给这个算法想到一个容易记住的艺名，叫“菊花”）

    /* 尾插法建立单链表演示 */
    void CreateListTail(LinkList *L, int n)
    {
        LinkList p, r;
        int i;
    
        srand(time(0));
        *L = (LinkList)malloc(sizeof(Node));//开辟空间给*L
        r = *L;//把头结点赋给r
    
        for( i=0; i < n; i++ )
        {
            p = (Node *)malloc(sizeof(Node));//随机分配空间给p
            p->data = rand()%100+1;//给p随机赋值
            r->next = p;//让r指向p
            r = p;//让p赋给r
            //循环操作来看
        }
        r->next = NULL;//建表结束，让r->next指向空NULL
    }

• 单链表的整表删除，思路：
  • 声明结点p和q
  • 将第一个结点赋值给p，下一结点赋值给q
  • 循环执行释放p和将q赋值给p的操作

    Status ClearList(LinkList *L)
    {
        LinkList p, q;
    
        p = (*L)->next;
    
        while(p)
        {
            q = p->next;
            free(p);
            p = q;
        }
    
        (*L)->next = NULL;
    
        return OK;
    }

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

分别从存储分配方式、时间性能、空间性能三方面来做对比

• 存储分配方式：

  • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
  • 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

• 时间性能：

  • 查找
    • 顺序存储结构O(1)
    • 单链表O(n)
  • 插入和删除
    • 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
    • 单链表在计算出莫位置的指针后，插入和删除时间仅为O(1)

• 空间性能：

  • 顺序存储结构需要预分配存储空间，分大了，容易造成空间浪费，分小了，容易发生溢出
  • 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

• 综上所述：

  • 若线性表需要频繁查找，宜用顺序存储结构
  • 若需要平凡插入和删除，宜用单链表结构
  • 比如说游戏开发中，对于用户注册的个人信息，除了注册时插入数据外，绝大多数情况都是读取，所以应该考虑用顺序存储结构
  • 而游戏中的玩家的武器或者装备列表，随着玩家的游戏过程中，可能会随时增加或删除，单链表结构就可以大展拳脚了
  • 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题
  • 而如果事先知道线性表的大致长度，比如一年12个月，一周就是星期一至星期日共七天，这种用顺序存储结构效率会高很多

　　线性表的顺序存储结构和单链表结构各有其优缺点，不能简单的说哪个好，哪个不好，需要根据实际情况，来综合平衡采用哪种数据结构更能满足和达到需求和性能

动画回顾