2、i是ai-1的后继元素。a1ai-1aia2an第1个数据元素最后1个数据元素抽象数据类型线性表的定义如下：ADTLinearList{数据对象：D＝{ai
3、ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系：R1＝{
4、ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),称i为ai在线性表中的位序。}基本操作：setnull(L)：置空表操作，将线性表L置为空表。length(L)：求长度操作，计算线性表L中数据元素的个数。get(L,
5、i)：取元素操作，取出线性表L中第i个数据元素；要求i≤length(L)。prior(L,x)：取前趋操作，取出线性表L中值为x的元素的前趋元素；要求x的位序大于1。next(L,x)：取后继操作，取出线性表L中值为x的元素的后继元素；要求x的位序小于length(L)。locate(L,x)：定位序操作，确定元素x在线性表L中的位置，并给出位置序号；若L中无x返回0。insert(L,x,i)：插入操作，在线性表L中第i个位置上插入值为x的新元素，使表长增1；要求1≤i≤length(L)+1。delete(L,i)：删除操作，删除线性表L中的第i个元素
6、，使表长减1；要求1≤i≤length(L)。}ADTLinearList利用上述定义的线性表可以实现其它更复杂的操作：如线性表的分拆、合并、逆置等例2-1(合并)假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。例2-1要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。上述问题可演绎为：1．从线性表LB中依次查看每个数据元素;2．依值在线性表LA中进行查访;3．若不存在，则插入之。get(LB,i)→elocate(LA
7、,e)insert(LA,e,n+1)操作步骤：2.2线性表的顺序表示和实现顺序映像最简单的一种顺序映像方法是：令y的存储位置和x的存储位置相邻。顺序映像——以x的存储位置和y的存储位置之间某种关系表示逻辑关系。用一组地址连续的存储单元依次存放线性表中的数据元素a1a2…ai-1ai…an线性表的起始地址称作线性表的基地址以“存储位置相邻”表示有序对即：LOC(ai)=LOC(ai-1)+C一个数据元素所占存储量↑所有数据元素的存储位置均取决于第一个数据元素的存储位置LOC(ai)=LOC(a1)+(i-1)×C↑基地址顺序映像
8、的C语言描述typedefstruct{}sequenlist;//俗称顺序表elemtypedata[MAXSIZE];intlast;//最后一个元素位置#defineMAXSIZE500线性表的基本操作在顺序表中的实现locate(L,x)//定位序insert(L,x,i)//插入元素delete(L,i)//删除元素例如：顺序表定位操作23754138546217L->lastx=38iiiiii12341850i可见，基本操作是：将顺序表中的元素逐个和给定值x相比较。intlocate(sequenlist*L,elemtypex)/*确定元素x
9、在顺序表L中的位置序号*/{inti=1;while((i<=L->last)&&(L->data[i]!=x))i++;if(i>L->last)return0;/*未找到值为x的元素返回0*/elsereturni;/*找到值为x的元素返回它的位序i*/}/*locate*/locate(L,x)定位序O(n)算法的时间复杂度为：线性表操作insert(L,x,i)的实现：首先分析:插入元素时，线性表的逻辑结构发生什么变化？(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,x,ai,…,an)a1a2…ai-1ai…ana1a2…ai-1
10、…aixan,
