本文共 4026 字，大约阅读时间需要 13 分钟。
一、线性表的定义
线性表（List）：由零个或多个数据元素组成的有限序列。
TIPS:
1.线性表是一个序列，也就是说元素之间是有先来后到的。 2.若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他元素只有一个前驱和后继。 3.线性表是有限的。
用数学语言定义：
若将线性表记为（a1,a2,…ai-1,ai,ai+1,…an）则ai-1领先于ai，ai领先于ai+1,称ai-1为ai的前驱元素，ai+1是ai的直接后继元素。
所以线性表元素的个数n（n>0）定义为线性表长度，当n=0成为空表。 二、抽象数据类型
- 定义：
一组性质相同的值的集合及定义在此集合上的一些操作总称。
例：很多编程语言的整型，浮点型，字符型这些即为数据类型。 在计算机中，内容并非无限大，若计算1+1=2整型数字的加减乘除，不需要开辟很大空间。 若计算1.23456+2.78946这样带小数的就需要比较大的空间存放，故要对数据类型进行分类，分出多种类型来适合各种不同的计算条件差异。例如：
C语言中数据类型分为两类：原子类型：不可以再分解的基本类型，例如：整型，浮点型，字符型… 结构类型：由若干个类型组合而成，是可以再分解的，例如：整形数组是由若干个整形数据组成的
何为抽象：是指抽取出事物具有普遍性的本质，它要求抽出问题的特征而忽略非本质的细节，是对具体事物的一个概括。抽象是一种思考问题的方式。
- 抽象数据类型
是指一个数学模型及定义在该模型上的一组操作，它的定义取决于它的一组逻辑特性，而与其他计算机内部如何表示和实现无关。
- 为了方便讲解对抽象数据类型进行规范描述，我们给出了描述抽象数据类型进行规范描述，我们给出了描述抽象数据类型的标准格式。
ADT: 数据类型 DATA:数据元素之间的逻辑关系定义 OPERATION:操作
二、线性表的抽象数据类型
-
定义：
ADT：线性表（List）Data：线性表的数据对象集合为（a1,a2…an），每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个前驱元素，除了最后一个元素an外，每个元素有且只有一个后继元素。数据元素之间的关系是一对一的关系
Operation：
InitList(*L)：初始化操作，建立一个空的线性表LListEmpty(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的元素个数。
对于不同的应用，线性表的基本操作是不同的，上述为基础Operation，对于实际问题中涉及的关于线性表的更多复杂操作，完全可以用这些基本操作的组合来实现。
例题： 若实现两个线性表A，B的并集操作，即要是的集合A=AUB； 分析： 只要遍历集合B中的每个元素，判断当前元素是否存在A中，若不存在，则插入A中；所以我们需要用到上述的基本Operation。ListLength(L);GetElem(L,i,*e)；LocateElem(L,e);ListInsert(*L,i,e); 伪代码实践：void UnionL(List *La,list Lb){ int La_len,Lb_len,i; ElemType e; La_len = ListLength(*La); Lb_len = ListLength(Lb); for(int i = 1;i 三、线性表的顺序存储结构
-
引入：
线性表由两种物理存储结构：顺序存储结构和链式存储结构。在此介绍顺序存储结构。 -
顺序存储结构
是指用一段地址连续的存储单元依次存储线性表的数据元素。例如：数组。物理上的存储方式就是在内存中找个初始地址，然后通过占位的形式，把一定内存空间给占掉，然后把相同数据类型的数据元素一次放在这块空地上。（可以理解为一个团体共50人，在看电影时，第一位领头人，去第一排第一个位置占座，剩余的49人依次跟在领头人的后面。）
-
线性表顺序存储的结构代码
#define MAXSIZE 20 typedef int ElemType; typedef struct{ ElemType date[MAXSIZE]; int length;//线性表当前长度 }SqList;//对数组进行封装，增加了当前长度的变量 - 总结 顺序存储结构封装需要三个属性： ——存储空间的起始位置，数组data，它的存储位置就是线性表存储空间的存储位置 ——线性表的最大存储容量：数组的长度MaxSize. ——线性表的当前长度：length ——注意：数组的长度与线性表的当前长度需要进行区别：数组的长度时存放线性表的存储空间的总长度，一般初始化后长度不变（一些编程语言可以将数组长度变大，但一般情况下认为初始化长度不变）。而线性表的当前长度时线性表中的元素的个数，是会变化的。
四、地址计算方法
因为编程语言中我们的数组是从0开始进行遍历，但线性表一般从1开始遍历
Loc(ai+1) = Loc(ai)+c 所以对于第i个数据元素ai的存储位置可以由a1推算得出：
Loc（ai） = Loc（a1）+（i - 1）* c; 
通过公式，可以随时计算出线性表的任意位置的地址。不管是第一个还是最后一个都是相同的实践，它的存储实践性能为O(1)，我们通常成为随机存储结构。
五、线性表顺序存储结构之获得元素操作
-
分析：
实现GetElem的具体操作，即将线性表L中的第i个位置元素值返回。只需要把数组第i-1下标的值返回即可。 -
代码实践
#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; //Status 是函数的类型，它的值是函数结果状态代码，如OK等。 //初始条件：顺序线性表L已存在，i<= i<=ListLength(L) //操作结果：用e返回L中第i个数据元素的值 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;} 注意这里的Status是一个整型，约定返回1代表OK，返回0代表ERROR。其时间复杂度为O（1）
六、线性表顺序存储结构之插入元素操作
-
分析
——如果插入位置不合理，抛出异常 ——如果线性表长度大于等于数组长度，则抛出异常或动态增加数组容量。 ——从最后一个元素开始向前遍历到第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)//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;} 注意：ListInsert（*L,i,e）插入元素操作的时间复杂度为O(n);第i个位置插入新元素e
七、线性表顺序存储结构之元素删除操作
- 分析 ——删除位置不合理，抛出异常 ——取出删除元素 ——从删除元素位置开始遍历。最后一个元素位置，分别将他们都向前移动一个 ——表长-1
- 代码实践
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]; if( i < L->length){ for( k = i; k < L->length;k++){ L->data[k-1] =L->data[k]; }}L->length--;} 插入或删除的时间复杂度，最好的情况下为O（1），表示只需在尾部插入一个元素或者在尾部删除一个元素。最坏情况下，需要O（n）个时间复杂度，因为需要遍历循环线性表。两者进行平均可得时间复杂度O((n-1)/2）可以推出时间复杂度为O（n）
转载地址：http://wpxmj.baihongyu.com/