第2章:线性表2.1线性表的逻辑结构线性表的抽象数据类型定义：ADTLinearList数据元素:D={ai|ai∈D0,i=1,2,…,n,n≥0,D0为某一数据对象}关系:S={<ai,ai+1>|ai,ai+1∈D0,i=1,2,…,n-1}线性表的特点：同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性：线性表中表中相邻数据元素之间存在着序偶关系<ai,ai+1>。2.1.2线性表的基本操作线性表的基本运算如下:1)线性表初始化Init_List(L)：构造一个空的线性表L。2)求线性表的长度Length_List(L)：返回L中元素个数。3)取表元Get_List(L,i)：用e返回L中第i(1≤i≤ListLength(L))个元素的值。4)按值查找Locate_List(L,x)：返回L中第1个值域与e相等的位序。若这样的元素不存在,则返回值为0。5)插入操作Insert_List(L,i,x)：在L的第i(1≤i≤ListLength(L)+1)个元素之前插入新的元素e,L的长度增1。6)删除操作Delete_List(L,i)：删除L的第i(1≤i≤ListLength(L))个元素,并用e返回其值,L的长度减1。2.2.1线性表的顺序存储—顺序表线性表的顺序存储结构:指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。采用顺序存储结构的线性表通常称为顺序表。线性表逻辑结构顺序表存储结构通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。线性表中第一个元素的存储位置就是指定的存储位置,第i+1个元素(1≤i≤n-1)的存储位置紧接在第i个元素的存储位置的后面。相邻两个数据元素的存储位置计算公式：LOC(ai+1)=LOC(ai)+L假定线性表的元素类型为ElemType,则每个元素所占用存储空间大小(即字节数)为sizeof(ElemType),整个线性表所占用存储空间的大小为:n*sizeof(ElemType),其中,n表示线性表的长度。假设线性表中有n个元素，每个元素占L个单元，第一个元素的地址为LOC(a1)，第j个元素的地址为LOC(aj),则可以计算出第i(i>j)个元素的地址LOC(ai)：LOC(ai)=LOC(a1)+(i-1)×LLOC(ai)=LOC(aj)+(i-j)×L2.2线性表的顺序存储2.2线性表的顺序存储2.2.2顺序表基本操作的实现Typedefstruct{datatypedata[MAXSIZE];intlast;}SeqList;1.顺序表的初始化SeqList*init_SeqList(){SeqList*L;L=malloc(sizeof(SeqList));L->last=-1;returnL;}2.插入操作插入操作:该运算在顺序表L的第i个位置(1≤i≤ListLength(L)+1)上插入新的元素x。思路：如果i值不正确,则显示相应错误信息；否则将顺序表原来第i个元素及以后元素均后移一个位置,腾出一个空位置插入新元素,顺序表长度增1。算法2.1:在线性表L中第i个数据元素之前插入数据元素XintInsert_SeqList(SeqList*L，inti，datatypex){intj;if(L->last==MAXSIZE－1){printf(＂表满＂);return(-1);}/*表空间已满，不能插入*/if(i<1||i>L->last+2)/*检查插入位置的正确性*/{printf(＂位置错＂);return(0);}for(j=L->last;j>=i-1;j--)L->data[j+1]=L->data[j];/*结点移动*/L->data[i-1]=x;/*新元素插入*/L->last++;/*last仍指向最后元素*/return(1);/*插入成功，返回*/}对于本算法来说,元素移动的次数不仅与表长n有关,而且与插入位置i有关:当i=n+1时,移动次数为0；当i=1时,移动次数为n,达到最大值。因此若要在表中的第i个元素前(后)插入新元素,需要移动元素n-i+1(n-i)个。在线性表中共有n+1个可以插入元素的地方。假设pi(=)是在第i个位置上插入一个元素的概率,则在长度为n的线性表中插入一个元素时所需移动元素的平均次数为:因此插入算法的平均时间复杂度为O(n)。3.删除操作删除操作:删除顺序表L中的第i(1≤i≤ListLength(L))个元素。思路：