资源描述：
《南信大数据结构第二章课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表线性结构的基本特征:1．集合中必存在唯一的一个“第一元素”2．集合中必存在唯一的一个“最后元素”3．除最后元素之外，均有唯一的后继4．除第一元素之外，均有唯一的前驱线性结构是一个数据元素的有序（次序）集2.1线性表的类型定义2.3线性表类型的实现链式映象2.4一元多项式的表示2.2线性表类型的实现顺序映象ADTList{数据对象：D＝{ai
2、ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系：R1＝{
3、ai-1,a
4、i∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),称i为ai在线性表中的位序。}基本操作：结构初始化操作结构销毁操作引用型操作加工型操作}ADTList{结构初始化}InitList(&L)操作结果：构造一个空的线性表L。CreateList(&L,A[],n)初始条件：A[]中存在线性表的n个数据元素。操作结果：构造一个含n个数据元素的线性表L。{销毁结构}DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ListEmpty(L)ListLen
5、gth(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)GetElem(L,i,&e)LocateElem(L,e,compare())ListTraverse(L,visit()){引用型操作}ListEmpty(L)（线性表判空）初始条件：操作结果：线性表L已存在。若L为空表，则返回TRUE，否则FALSE。ListLength(L)（求线性表的长度）初始条件：操作结果：线性表L已存在。返回线性表L中元素个数。PriorElem(L,cur_e,&p
6、re_e)（求前驱）初始条件：操作结果：线性表L已存在。若cur_e是L中的元素，则以pre_e带回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)（求后继）初始条件：操作结果：线性表L已存在。若cur_e是L中的元素，则以next_e带回它的后继，否则操作失败，next_e无定义。GetElem(L,i,&e)（求线性表中某个元素）初始条件：操作结果：线性表L已存在以e带回L中第i个数据元素值。LocateElem(L,e,compare())（定位函数）初始条件
7、：操作结果：线性表L已存在,compare()为判定函数。返回L中第1个与e满足关系compare()的元素的位序，若不存在这样的元素，则返回0。且1≤i≤LengthList(L)。ListTraverse(L,visit())（遍历线性表）初始条件：操作结果：线性表L已存在,visit()为数据元素的访问函数。依次对L的每个数据元素调用函数visit()，一旦visit()失败，则遍历操作失败。ClearList(&L)(线性表置空)ListInsert(&L,i,e)(插入数据元素)PutElem(&L
8、,i,e)(改变数据元素的值)ListDelete(&L,i,&e)(删除数据元素){加工型操作}ClearList(&L)（清除线性表内容）初始条件：操作结果：线性表L已存在。将L重置为空表。PutElem(&L,i,e)初始条件：操作结果：L中第i个元素赋值和e相同。线性表L已存在，且1≤i≤LengthList(L)。ListInsert(&L,i,e)初始条件：操作结果：线性表L已存在在L的第i个元素之前插入新的元素e,L的长度增1。ListDelete(&L,i,&e)初始条件：操作结果：线性表L已
9、存在删除L中第i个元素，并以e带回其值,L的长度减1。,1≤i≤LengthList(L)+1。,1≤i≤LengthList(L)。例2-1假设有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。即:需对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。1．取得线性表LB中一个数据元素;2．依值在线性表LA中进行查访;3．若不存在，则插入线性表LA中。GetElem(LB,i,&e)L
10、ocateElem(LA,e,equal());ListInsert(LA,n+1,e);(n表示线性表LA当前长度)操作步骤：GetElem(LB,i,&e)//取Lb中第i个数据元素赋给e，逗号的运算方向为左至右一步步执行。if(!LocateElem(La,e,equal()))ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之La_len=Lis
