资源描述：
《第2章 线性表1-定义与顺序表示ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章线性表数据结构课程的内容逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构集体中必存在唯一的一个第一个元素;集合中必存在唯一的一个最后一个元素;除最后元素在外,均有唯一的后继;除第一个元素在外,均有唯一的前驱;线性结构是:一个数据元素的有序集。可表示为：（a1,a2,……,an）线性结构的特点：2.1线性表的类型定义ADTList{数据对象：D={ai
2、ai∈Elemset,i=1,2,…,n,n≥0}{n称为线性表的表长n=0的线性表称为空表}数据关系：R1={
3、ai-1,ai∈D,i=2,…,n}{设线性表为(a1,a2,…,ai,…,an)称i为
4、ai在线性表中的位序}抽象数据类型的定义基本操作：{创建线性表}InitList(&L)操作结果：构造一个空的线性表L{销毁线性表}DestroyList(&L)初始条件：线性表L已存在操作结果：销毁线性表L{引用型操作}ListEmpty(L)ListLenght(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)GetElem(L,i,&e)LocateElem(L,e,equal())ListTraverse(L,visit())ListEmpty(L)初始条件：线性表L已存在操作结果：若L为空表，返回TRUE，否则
5、返回FALSEPriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在操作结果：若cur_e是L的元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义NextElem(L,cur_e,&next_e)初始条件：线性表L已存在操作结果：若cur_e是L的元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义ListLenght(L)初始条件：线性表L已存在操作结果：返回线性表L数据元素个数GetElem(L,i,&e)初始条件：线性表L已存在（1≤i≤ListLenght(L)）操作结果：用e返回线性表L
6、中第i个数据元素的值LocatElem(L,e,equal())初始条件：线性表L已存在，comare()是数据元素判定函数操作结果：返回线性表L中第1个与e满足关系comare()的数据元素的位序ListTraverse(L,visit())初始条件：线性表L已存在操作结果：依次对线性表L的每个数据元素调用visit()函数，一旦visit()失败，则操作失败{加工型操作}ClearList(&L)PutElem(&L,i,&e)ListInsert(&L,i,e)ListDelete(&L,i,&e)ClearList(&L)初始条件:线性表L已存在操作结果:将L重置为空
7、表PutElem(&L,i,&e)初始条件:线性表已存在（1≤i≤ListLenght(L)+1）操作结果:L中第i个元素赋值同e的值ListInsert(&L,i,e)初始条件：线性表已存在（1≤i≤ListLenght(L)+1）操作结果：在线性表L中第i个数据元素之前插入新元素e，L长度加1ListDelete(&L,i,&e)初始条件：线性表已存在（1≤i≤ListLenght(L)）操作结果：删除线性表L中第i个数据元素，用e返回其值，L长度减1}ADTList例2-1假设有两个集合A和B分别用两个线性表LA和LB表示（即线性表中的数据元素即为集合的成员）。现要求一
8、个新的集合A=A∪B利用上述线性表的定义，可以完成其他更复杂的操作。此问题可演绎为，要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据插入到线性表LA中去。1，从线性表LB中依次取得每个数据元素2，依值在线性表LA中进行查访3，若不存在，则插入之GetElem(LB,i,&e)LocateElem(LA,e,equal())ListInsert(&LA,n+1,e)voidUnionList(List&La,ListLb){}La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb
9、_len;i++){GetElem(Lb,i,&e);if(!Locate(La,e,equal()))ListInsert(&La,++La_len,e);}例2-2已知一个非纯集合B,试构造一个纯集合A,使A中只包含B中所有值各不相同的数据元素。voidpurse(List&La,ListLb){InitList(&La);La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,&e);if(!L
