前言

废话不多，数据结构必须学！ 每天更新一章，一篇写不完的话会分成两篇来写~

资料获取

三、线性表

3.1 线性表的定义

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

有几个点要注意： 首先它是一个序列，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且仅有一个前驱和后继。

线性表强调的是有序的

如图所示：

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

3.1.1实例

当然是，星座通常都是用白羊座打头，双鱼座收尾，当中的星座都有前驱和后继，而且一共也只有十二个，所以它完全符合线性表的定义。

班级里的点名册，是不是线性表呢？

是，这和友谊关系，爱情关系都不同，它是有限序列，而且它也满足类型相同的特点。

点名册中，每个学生除了学生的学号外，还可以有同学的姓名，性别、出生年月什么的，这些其实就是之前说的数据项。在较复杂的线性表中，一个数据元素可以由若干个数据项组成

3.2线性表的抽象数据类型

把排好的队解散重新排--这是一个线性表重置为空表的操作

ADT 抽象数据类型名
 Data
     线性表的数据对象集合为{a1,a2,....,an},每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
 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的并集操作。即要使得集合A=A∪B。说白了，就是把存在集合B中但并不存在A中的数据元素插入到A中即可。 仔细分析一下这个操作，发现我们只要循环集合B中的每个元素，判断当前元素是否存在A中，若不存在，则插入到A中即可。思路应该是很容易想到的。我们假设La表示集合A, Lb表示集合B,则实现的代码如下:

/*将所有的在线性表Lb中但不在La中的数据元素插入到La中*/
 void union (List *La,List Lb )
 {
     int La_len, Lb_len,i;
     ElemType e;
     /*声明与La和Lb相同的数据元素e*/
     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) ) /*La中不存在和e相同数据元素*/
             ListInsert (La, ++La len,e) ; /*插入*/
     }
 }

这里，我们对于union操作，用到了前面线性表基本操作ListLength、 GetElem、LocateElem、ListInsert 等，可见，对于复杂的个性化的操作，其实就是把基本操作组合起来实现的。

3.3 线性表的顺序存储结构

3.3.1 顺序存储定义

说这么多的线性表，我们来看看线性表的两种物理结构的第一种顺序存储结构。

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

3.3.2顺序存储方式

线性表的顺序存储结构，说白了，和刚才的例子一样，就是在内存中找了块地儿，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据元素的类型都相同，所以可以用C语言(其他语言也相同)的一维数组来实现顺序存储结构，即把第一一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

为了建立一个线性表，要在内存中找块地，于是这块地的第一个 位置就非常关键，它是存储空间的起始位置。

代码比较简单就不写出来了，截图好了。

这里，我们就发现描述顺序存储结构需要三个属性:

存储空间的起始位置: 数组data,它的存储位置就是存储空间的存储位置。

线性表的最大存储容量:数组长度MaxSize。

线性表的当前长度: length。

3.3.3数据长度与线性表长度区别

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

线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行， 这个量是变化的。  在任意时刻，线性表的长度应该小于等于数组的长度。

3.3.4 地址计算方法

由于我们数数都是从1开始数的，线性表的定义也不能免俗，起始也是1,可C 语言中的数组却是从0开始第一个 下标的，于是线性表的第i个元素是要存储在数组下标为i-1的位置，即数据元素的序号和存放它的数组下标之间存在对应关系

其实，内存中的地址，就和图书馆或电影院里的座位一样，都是有编号的。存储器中的每个存储单元都有自己的编号,这个编号称为地址。当我们占座后，占座的第一个位置确定后，后面的位置都是可以计算的。 试想一下， 我是班级成绩第五名，我后面的10名同学成绩名次是多呢?当然是6, 7, ...15，因为5 +1，5+2, .，. 5+ 10。由于每个数据元素，不管它是整型、实型还是字符型，它都是需要占用一定的存储单元空间的。假设占用的是c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系(LOC表示获得存储位置的函数)。

LOC(ai)= LOC(ai)+c

所以对于第i个数据元素a的存储位置可以由a1推算得出: LOC(ai)= LOC(ai)+(i-1)*c

用图更好理解呢！

通过这个公式，你可以随时算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么我们对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数， 因此用我们算法中学到的时间复杂度的概念来说，它的存取时间性能为0(1)。 我们通常把具有这一特 点的存储结构称为随机存取结构。