资源描述：
《数据结构第二章 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现线性结构是一个数据元素的有序（次序）集线性结构的基本特征:1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”；3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。2.1线性表的类型定义线性表（linear_list）是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。例如：（A,B,C,D,……Z）（6,17,28,50,92,188）在线性表
2、中，一个数据元素可以由若干数据项（item）组成。在这种情况下，常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。抽象数据类型线性表的定义如下：ADTList{数据对象：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,....，an),称i为ai在线性表中的位序。}基本操作：InitList(&L
5、)结构初始化操作结果：构造一个空的线性表L。DestroyList(&L)销毁结构初始条件：线性表L已存在。操作结果：销毁线性表L。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。Next
6、Elem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。GetElem(L,cur_e,&next_e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若
7、这样的元素不存在，则返回值为0。ListTraverse(L,visit())初始条件：线性表L已存在。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem(L,i,&e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：L中第i个元素赋值同e的值。ListInsert(&L,i,e)初始条件：线性表L已存在，1≤i≤LengthList(L)+1操作结果：
8、在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤LengthList(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTList例2-1假设有两个集合A和B分别用两个线性表LA和LB表示（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合A＝A∪B。上述问题可演绎为，要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。1．从线性表L
9、B中依次取得每个数据元素;GetElem(LB,i)→e2．依值在线性表LA中进行查访;LocateElem(LA,e,equal())3．若不存在，则插入之。ListInsert(LA,n+1,e)voidunion(List&La,ListLb){//将所有在线性表Lb中但不在La中的数据元素插入到La中La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第
10、i个数据元素赋给eif(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之}}//union2.2线性表类型的实现--顺序映象用一组地址连续的存储单元依次存放线性表中的数据元素线性表的起始地址，称作线性表的基地址以“存储位置相邻”表示有序对即：所有数据元素的存储位置均取决于第一个数据元素的存储位置顺序映像的C语言描述//----
