线性表 7月8日 【今日算法】

线性表的定义：

由零个或多个数据元素组成的有限序列

注意：

• 首先它是一个序列，也就是说元素之间是有先来后到之分。
• 若元素存在多个，则第一个元素无前驱，而最后一个元素无后继，其他元素都有且只有一个前驱和后继。
• 线性表强调是有限的，事实上无论计算机发展到多强大，他所能处理的元素都是有限的。

线性表的形式化定义：

模拟考题：

1. 请问公司的组织架构是否属于线性关系？

   分析：一般公司的总经理管理几个总监，每个总监管理几个经理，每个经理都有各自的下属和员工。

   那这样的组织架构当然不是线性关系了，事实上后面你就会知道，这是一个树状结构。

   注意线性关系的条件是如果存在多个元素，则”第一个元素无前驱，而最后一个元素无后继，其他元素都有且只有一个前驱和后继。“

2. 那么班里同学之间的友谊是否属于线性关系？

   当然也不是了，因为每个人都会跟许多同学建立纯纯的友谊关系。

3. 情侣之间的爱情关系呢？

   哈哈，当然是扯淡，这要是线性关系，也就不会有所谓的第三者插足了。。。你们的爱情关系定会是线性关系！

4. 最后一题，一个班级的点名册，是不是线性表？

   是啦，看下表：

线性表的分类：

抽象数据类型

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

例如很多编程语言的整型，浮点型，字符型这些指的就是数据类型

1. 当年那些设计计算机语言的人，为什么会考虑到数据类型呢？

   比如，大家需要住房子，也都希望房子越大越好。但显然，没有多少钱的话考虑房子是没啥意义的。于是商品房出现了各种各样的房型，有别墅的，有错层的，有单层的，甚至在北京还出现了胶囊公寓--只有两平米的房间。这样子就满足了大家的不同需求。

   同样，在计算机中，内存也不是无限大的，你要计算1+1=2这样的整型数字的加减乘除运算，显然不需要开辟很大的内存空间。而如果要计算1.23456789+2.987654321这样带大量小数的，就需要开辟比较大的空间才能存放的下。于是，计算机的研究者们就考虑，要对数据类型进行分类，分出多种数据类型来适应各种不同的计算条件差异。

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

2. • 原子类型：不可以再分解的基本类型，例如整型、浮点型、字符型等等。
   • 结构类型：由若干个类型组合而成，是可以再分解的，例如整型数组是由若干整型数据组成的。

抽象：是指抽取出事物具有的普遍性的本质。他要求抽出问题的特征而忽略非本质的细节，是对具体事物的一个概括。抽象是一种思考问题的方式，它隐藏了繁杂的细节。

抽象数据类型（Abstract Data Type，ADT） 是指一个数据模型及定义在该模型上的一组操作，就相当于高级语言当中类的概念。

抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

比如1+1=2这样的一个操作，在不同CPU的处理上可能不一样，但由于其定义的数学特性相同，所以在计算机编程者看来，它们都是相同的。

“抽象” 的意义在于数据类型的数学抽象特性。而且，抽象数据类型不仅仅指那些已经定义并实现的数据类型，还可以是计算机编程者在设计软件程序时自己定义的数据类型（类等）。

例如一个3D游戏中，要定位角色的位置，那么总会出现x,y,z三个整型数据组合在一起的坐标。我们就可以定义一个point的抽象数据类型，他拥有x,y,z三个整型变量，这样我们就可以方便的对一个角色的位置进行操作。

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

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

线性表的抽象数据类型

所谓抽象数据类型就是把数据类型和相关操作捆绑在一起。

线性表的抽象数据类型定义：

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

实现两个线性表A、B的并集操作，即要使得集合

• 其实仔细思考一下，我们只需要循环遍历集合B中的每一个元素，判断当前元素是否在A中存在，若不存在，则插入A中即可。

• 综合分析，我们需要运用几个基本的操作组合即可：

• • ListLength(L);
  • GetElem(L,i,*e);
  • LocateElem(L,e);
  • ListInsert(*L,i,e);

• 参考代码实现：

//union.c
void unionL(List *La, list Lb)
{
    int La_len, Lb_len, i;
    ElemType e;
    La_len=ListLength(*La);
    Lb_len=ListLength(Lb);
    for( i=1; i <= Lb_len; i++)
    {
        GetElem(Lb, i, &e);
        if( !LocateElem(*La, e)){
            ListInsert(La, ++La_len, e);
        }
    }
}

线性表的顺序存储结构

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

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

物理上的存储方式事实上就是在内存中找个初始地址，然后通过占位的形式，把一定的内存空间给占了，然后把相同数据类型的数据元素依次放在这块空地中。

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

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

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

• • 存储空间的起始位置，数组data，她的存储位置就是线性表存储空间的起始位置（电影院某个厅所在位置）。
  • 线性表的最大存储容量：数组的长度MAXSIZE（电影院某个厅内的座位总数）
  • 线性表的当前长度：length。（电影院某个厅当前看电影的人数）

• 注意，数组的长度和线性表的当前长度需要区分一下：数组长度是存放线性表的存储空间的总长度，一般初始化后不变。而线性表的当前长度是线性表中元素的个数，是会变化的。

• 习惯上数组是从0开始的计算方法

  假设ElemType占用的是c个存储单元（字节），那么线性表中第i+1个数据元素和第i个数据元素的存储位置的关系是（LOC表示获得存储位置的函数）：

• 地址计算方法：对于第 i 个数据元素的存储位置可以由推算得出：

• 通过上面的公式，我们就可以随时计算出线性表中任意位置的地址，不管他是的第一个还是最后一个，都是相同的时间。那么它的存储时间醒醒当然就是O(1)，我们通常称为随机存储结构。

获取一个元素

//getElem.c
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

Status GetElem(SqList L, int i, ElemType *e)
{
    if( L.length==0 || i<1 || i>L.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 ( i<1 || i>L->Length+1)
    {
        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;
}

** **

删除操作

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

Status ListDelete(SqList *L, int i, ElemType *e) {
    int k;
    
    if( L->length == 0){
        return ERROR;
    }
    if( i < 1 || i > L->length){
        return ERROR;
    }
    
    *e = L->data[i-1]; //e用于保存第i个位置的值，并返回
    if( i < L->Length){
        for( k=i; k < L->length; k++){
            L->data[k-1]=L->data[k];
        }
    }
    
    L->length--;
    
    return OK;
}

插入和删除的时间复杂度：

最好的情况：插入和删除操作刚好要求在最后一个位置操作，因为不需要移动任何元素，所以此时的时间复杂度为O(1)

最坏的情况： 如果插入和删除的位置是第一个元素，那就意味着要移动所有的元素向后或者向前，所以这个时间复杂度为O(n)

平均情况： 去取中值

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

• 线性表的顺序存储结构，在存、读数据时，不管是那个位置，时间复杂度都是 ，而在插入或删除时，时间复杂度都是 .
• 也就是说，顺序存储结构适合元素个数比较稳定，不经常插入和删除元素，而更多的操作是存取数据的应用。
• 优点：
• • 无须为表中元素之间的逻辑关系而增加额外的存储空间。
• • 可以快速存取表中任意位置的元素
• 缺点：
• • 插入和删除操作需要移动大量元素。
• • 当线性表长度变化较大时，难以确定存储空间的容量。
• • 容易造成存储空间的 "碎片"，浪费存储空间。因为线性表申请内存空间是一整块一整块申请的，那么中间就会造成很多的 ”碎片空间“，而无法使用。

内存碎片：

• 外部碎片指的是那些还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请空内存空间的新进程的内存空闲区域。外部碎片处于任何已分配区域或者页面外部的空闲存储块。这些存储块的总和可以满足当前申请的长度要求，但是由于他们的地址不连续或其他原因，使得系统无法满足当前申请。

• 内部碎片就是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间；内部碎片是处于区域内部或者页面内部的存储块，占有这些区域或页面的进程并不适用这个存储块。而在进行占有这块存储块时，系统无法利用它，直到进程释放它，或者进行结束时，系统才有可能利用这个存储空间。

来源 | 景禹

作者 | 景禹