资源描述：
《数据结构与算法(Python语言描述)课件2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章线性表2016Fall《数据结构》内容提要线性结构线性表的类型定义线性表的顺序表示和实现线性表的链式表示和实现线性结构学生信息表通讯录短信、聊天记录邮件列表购物清单账单何处用到线性结构？？？首元素相邻的元素组成前驱与后继关系线性表线性表的逻辑结构尾元素线性表线性表是n个数据元素的有限序列。一般形式：(a1,…,ai-1,ai,ai+1,…,an)直接前驱、直接后继长度：表中元素的个数n(n=0时称为空表)非空表中，每个元素都有一个确定的位置结构+操作结构的创建、结构的销毁：构造与析构引用型（
2、访问型）：get加工型（改变型）：set线性表抽象数据类型？ADTList{数据对象：D＝{ai
3、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
4、ai-1,ai∈D,i=2,...,n}基本操作：InitList(&L)//初始化操作结果：构造一个空的线性表L。CreatList(&L,n)//创建操作结果：构造一个含n个元素的线性表L。DestroyList(&L)//结构销毁初始条件：线性表L已存在。操作结果：销毁线性表L。线性表类型//引用型操作L
5、istLength(L)//求线性表的长度初始条件：线性表L已存在。操作结果：返回L中元素个数。ListEmpty(L)//判断线性表是否为空初始条件：线性表L已存在。操作结果：若L不空，返回true，否则为false。PriorElem(L,cur_e,&pre_e)//求数据元素的前驱初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)//求数据元素的后继初始条件
6、：线性表L已存在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。GetElem(L,i,&e)//取线性表中第i个数据元素初始条件：线性表L已存在，且1≤i≤LengthList(L)。操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare())//定位函数初始条件：线性表L已存在，e为给定值，compare()是元素判定函数。操作结果：返回第1个与e满足compare关系的元素的位序。若这样的元素不存
7、在，则返回值为0。ListTraverse(L,visit())//遍历线性表初始条件：线性表L已存在，visit()为某个访问函数。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。//加工型操作：&L!!!ClearList(&L)//线性表置空初始条件：线性表L已存在。操作结果：将L重置为空表ListInsert(&L,i,e)//插入数据元素初始条件：线性表L已存在，且1≤i≤LengthList(L)+1。操作结果：在L的第i个元素之前插入新的元素e
8、，L的长度增1。ListDelete(&L,i,&e)//删除数据元素初始条件：线性表L已存在且非空，1≤i≤LengthList(L)。操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTList题目：假设利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。方法：只要从LB中依次取出每个数据元素，并依值在LA中进行查访，若不存在，则插入。线性表类型的应用——求集合的并集voidunionSet(List&La,ListLb){La_len=ListLen
9、gth(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,EQUAL))InsertList(La,++La_len,e);}}线性表类型的应用——求集合的并集题目：已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。方法：设置两个指针分别指向LA和LB的当前元素，将数值较小的元素插入LC中。线性
10、表类型的应用——归并操作voidMergeList(ListLa,ListLb,List&Lc){ClearList(Lc);//这里假定Lc已经做过InitList操作，//ClearList之后表的空间还在！i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=La_len)&&(j<=Lb_len)){GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListIn
