3、a∈ElemSet,i=1,2,...,n,n≥0}ii{称n为线性表的表长;称n=0时的线性表
4、为空表。}数据关系：R＝{
5、a,a∈D,i=2,...,n}i-1ii-1i{设线性表为(a，a,...，a，...，a),12in称i为a在线性表中的位序。}i数据结构第二章线性表基本操作：P19了解各种操作的功能即可初始化操作初始化操作InitList(L)销毁操作销毁操作DestoryList(L)InsList(L,i,e)加工型操作加工型操作DelList(L,i,e)ListLength(L)ListEmpty(L)引用型操作引用型操作GetData(L,i)Locate(L,e)ClearList(L)}ADTList数据结构
6、第二章线性表§§2.22.2线性表的顺序表示和实现线性表的顺序表示和实现逻辑结构上相邻的数据元素ÆÆ顺序分配：顺序分配：其物理位置也是相邻的∑定义：用一组地址连续的存储单元存放一个线性表叫~∑元素地址计算方法：òLOC(ai)=LOC(a1)+(i-1)*LòLOC(ai+1)=LOC(ai)+Lò其中：©L—一个元素占用的存储单元个数©LOC(ai)—线性表第i个元素的地址∑特点：ò实现逻辑上相邻—物理地址相邻ò实现随机存取数据结构第二章线性表V数组下标内存元素序号00a111a22n-1ann备用空间M-1数据元素可为简单类型时,也可定义结构体数
7、组数据结构第二章线性表ÆÆ顺序表的描述顺序表的描述∑采用静态数组直接定义#define#defineMAXSIZE100typedeftypedefstructstruct{{ElemTypeElemTypeelem[elem[MAXSIZE]]；；/*线性表占用的数组空间数组空间*/intintlengthlength；；/*线性表长度*/}}SeqListSeqList；；数据结构第二章线性表ÆÆ顺序表的基本操作顺序表的基本操作————插入∑∑定义定义：线性表的插入是指在第i（1≤i≤n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表(
8、a1,a2,LL,ai−1,ai,LLan)变成长度为n+1的线性表(a1,a2,LL,ai−1,x,ai,LLan)需将第i至第n个元素后移（n-i+1)次∑∑算法算法ò判断插入位置是否有效ò判断线性表长度是否有效ò第i个至表尾的元素后移ò将x插入到第i个位置，且表长+1数据结构第二章线性表V数组下标内存元素序号V数组下标内存元素序号0a110a111a221a22i-1aii步骤i-1xxin-i+1iai+1i+1iaii+1步骤n-iai+1步骤2n-1annn-1an-1n步骤1nn+1nann+1数据结构第二章线性表算法算法2.22.2在
9、顺序线性表在顺序线性表LL中第中第ii个元素之前插入新的元素个元素之前插入新的元素xxintInsList(SeqList*L,inti,ElemTypex){if((i<1)
10、
11、(i>L->length+1)){printf(“插入位置i值不合法”)；returnERROR;}if(L->length==maxsize-1){printf(“表已满无法插入”)；returnERROR;}for(j=L->length;j>=i;j--)L->elem[j+1]=L->elem[j];L->elem[i]=x;L->length++;returnOK
12、;}数据结构第二章线性表∑算法时间复杂度T(n)设P是在第i个元素之前插入一个元素的概率，则在长度为ni的线
