三、线性表（一）

一、定义：

线性表是具有像线一样的性质的表，是一个序列，元素间是有顺序的，如果存在多个元素的话，第一个元素无前驱，后一个元素无后继，其他每个元素都有且只有一个前驱和后继，线性表强调有限性。

线性表的元素个数n（n>=0）定义为线性表的长度，当n=0时，成为空表。

非空表中每个元素都有一个确定的位置，如果a1是第一个元素，a7是第七个元素，1成为a1元素在线性表中的位序。

线性表最典型的例子就是星座和生肖了。星座中都是白羊座第一，双鱼座收尾，当中的每个星座有且仅有一个前驱和后继，而且个数是有限的12个；生肖中以鼠开头以猪结尾。每个星座和生肖的位置（位序）是固定的，白羊座和鼠是1，金牛座和牛是2......

要成为线性表中的元素比较有相同的数据类型，不同的数据类型是不能组成线性表的。人和衣服就不能组成线性表。

复杂的线性表允许每个元素有若干个数据项组成，例如按照学号排序的学生组成了一个线性表，每个学生都可以有姓名，性别，出生年月等多个数据项。

二、线性表的抽象数据类型

2.1什么是线性表

线性表的数据对象元素为{a1,a2,a3,......,an}，每个元素的类型均为DataType。其中，除了第一个元素a1外，每个元素都有前驱；除了最后一个元素an外，每个元素都有后继。数据元素间的关系是一对一的关系。

幼儿园的小朋友按照固定的顺序排队，并且长期使用这个顺序，每个小朋友就对应一个元素，所以小朋友组成的顺序队列就叫线性表。

2.2线性表的操作

• InitList（*L）：

初始化操作，建立一个空的线性表。

老师让小朋友按照一定顺序排队的过程就是线性表的创建与初始化的过程。

• ListEmpty（L）：

若线性表为空，返回true，否则返回false。

• ClearList（L）：

将线性表清空。

没经验的小朋友排好队后，老师发现有高有矮很不整齐，队伍很难看，于是让小朋友解散重新排列，这就是一个线性表重置为空的操作。

• GetElem（L,i,*e）:

将线性表L中的第i个元素值返回给e。

• LocateElem（L,e）：

在线性表中查找与e相等的元素，如果查找成功返回该元素的序号，查找失败返回0；

• ListInsert（*L,i,e）:

在线性表第i个位置插入新元素e

• ListDelete（*L,i,e）:

删除线性表第i个位置，并用e返回

• ListLength（L）:

获取线性表元素个数

使用以上几个基本操作实现求 线性表A和线性表B的并集，思路大致为，查找B中的每个元素判断是否在A中，如果不在则插入。

void unionL(List *La,List Lb){
    int La_length,Lb_length,i;
    //声明相同的数据元素e
    ElemType e;
    La_length = ListLength(La);
    Lb_length = ListLength(Lb);
    //遍历Lb所以元素，在La中查找，没有就插入
    for(i=1; i<=Lb_length; i++){
        //取出Lb中第i个元素给e
        GetElem(Lb,i,e);
        //Lb中如果没找到e就插入
        if(!LocateElem(La,e)){
            ListInsert(La, ++La_length, e);
        }
    }
}

三、线性表的物理结构---顺序存储结构

3.1 定义

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

3.2存储方式

线性表的顺序存储结构，就是在内存中找了快地方，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素一次存放在这块空地中。想象下C的一维数组，里面的每个元素数据类型都相同，下标0存放线性数组第一个元素，接着把线性表相邻 元素存储在数组汇总相邻的位置。
如果线性表的个数小于它的最大存储容量，这个时候是可以往线性表里面添加元素的，随着数据的插入，线性表的长度慢慢增大，但是不能超过它的最大存储容量。

顺序存储的结构代码：

#define MAXSIZE 20
typedef struct
{
    ElemType data[MAXSIZE];  //存储数据元素的数组，最大容量为MAXSIZE
    int length;  //当前线性表的长度
}

描述顺序存储需要三个属性：

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

NOTE：两个概念的比较：数组的长度和线性表的长度。数组的长度是指存放线性表的存储空间的长度，存储分配后这个量一般是不变的（高级语言中可以通过编程手动实现动态分配数组长度，不过这个会带来性能损耗）；线性表的长度是线性表中的数据元素的个数，随着线性表的插入和删除而改变。任何时刻，线性表长度应小于等于数组长度

3.3地址的计算方法

地址：存储器中的每个存储单元都有自己的编码，这个编码成为地址。

使用LOC表示获取存储位置的函数，每个元素占据的存储单元个数为c，那么第i个元素与第i+1个元素的地址关系可以表示为：

LOC(i+1) = LOC(i) + c

相应的，我们可以很快得出第i个元素与第一个元素的地址关系为：

LOC(i) = LOC(1) + (i-1)*c

通过这个公式，我们可以随时算出线性表中任一一个元素的位置，而且时间是固定的，这个对于计算机来说也是一样，每次都用同样的时间就能取出任一位置的元素，同时这个时间是一个常数，从时间复杂度的角度来说，它的存取性能为O(1)，我们把具有这一特点的存储结构称之为随机存取结构。

3.4 线性表元素的获取、插入、删除

• 获取元素：
  这个和获取数组中的某个位置的元素的原理相似，先判断数组长度是否为0，该位置是否合法，然后取出元素，这里需要注意的是线性表的下标起始是从1开始，因此第i个元素对应数组中的下标为i-1。

 status GetElem(sqList L, int i,ElemType *e){
    /*判断i是否合法*/
    if(L.length == 0 || i < 1 || i > L.length) return ERROR;
    *e = L.data[i-1];
    return OK;
  }

• 插入元素
  步骤：
  1、判断插入的位置是否合法。
  2、找到合适的位置后该位置开始到最后一个元素，每个元素都向后移动一个位置，
  3、插入元素
  4、线性表的长度增加1

用代码实现为：

status ListInsert(Sqlist L, int i, ElemType e){
     int k;
    /*线性表已满*/
    if (L.length == MAXSIZE) return ERROR;
    /*插入位置不合法*/
    if (i < 1 || i > L.length+1) return ERROR;
    //从后向前遍历，所以元素向后移动一个位置
    if (i <= L.length) {
        for(k = L.length; k >= i；k--){
            L.data[k+1] = L.data[k];
        }
    }
    L.data[i] = e;
    L.length ++;
    return OK;
}

• 删除元素
  步骤：
  1、判断要删除位置是否合法
  2、删除该元素，用e返回其值
  3、遍历线性表，该元素以后的每个元素向前移动一个位置
  4、线性表的长度-1

status (SqList L, int i, ElemType *e){
    int k;
    if (L.length == 0 || i < 1 || i > L.length) return ERROR;
    /*取出待删除元素，用e返回*/
    *e = L.data[i];
    /*i以后的每个元素向前移动一个位置*/
    for(k = i; k < L.length; k --){
        L.data[k-1] = L.data[k];  
    }
    /*线程表的长度-1*/
    L.length--;
    return OK;
}

• 顺序存储的优缺点
  优点：
  1、无需为表中元素之间的逻辑关系而增加额外的存储空间
  2、可以快速地存取表中任一位置的元素

  缺点：
  1、插入和删除操作需要移动大量元素。
  2、当线性表长度变化较大时，难以确定存储空间的容量。
  3、容易造成存储空间的碎片。