cha2 线性表.ppt

第二章线性表?简介:最简单、最常用的数据结构,?线性表的顺序表示和实现?线性表的链式表示和实现?线性表的应用实例---一元多项式的表示和运算?重点:?线性表的基本概念和术语?线性表的顺序表示和链式表示方法及其上的基本操作?相关算法的时间复杂度分析?难点:线性表的链式表示和基本操作线性结构的特点?存在惟一的一个被称作"第一个"的数据元素;?存在惟一的一个被称作"最后一个"的数据元素;?相邻数据元素之间存在序偶关系,若将线性表记为(a1,a2,…,ai-1,ai,ai+1,…,an)?表中ai-1领先于ai, 称 ai-1是ai的直接前驱元素;? ai+1是ai的直接后继元素。?除第一个之外,线性表中的每个数据元素均只有一个直接前驱;?除最后一个之外,线性表中每个数据元素均只有一个直接后继; 线性表类型定义?线性表(Linear List):n个数据元素的有限序列。?如(3,5,56,67,88),(a,b,c,d,e,f)都是线性表,更复杂的线性表中,一个数据元素(记录)可以由若干个数据项组成,含有大量记录的线性表称为文件。?如:学生健康情况表:?总之:?线性表的数据元素可由若干数据项组成。?同一线性表中的元素必定具有相同特性姓名王小林陈红……..关非学号790631790632……..790632性别男女…….女年龄 18 20……. 20数学9878….78线性表术语?线性表的长度:线性表中元素的个数(n);?空表:n=0时,称为空表;?位序:在非空的线性表中,每个元素都有一个确定的位置,如(a1, a2, …, ai , …, an)中,i 为数据元素ai在线性表中的位序。?线性表上的操作:构造、销毁、置空、判断是否为空表、求线性表的长度、取第i个数据元素、求某个值在表中的位序、求前驱/后继、插入/删除一个数据元素、遍历等线性表的操作:例2-1?需求:线性表LA和LB分别表示集合A和B,求A=A∪B。?解决方案:把存在于LB且不存在于LA的元素插入LA。?算法描述:void union(List &La,List Lb) { La_len=ListLength(La) ; Lb_len=ListLength(Lb); for(i=1;i<=lb_len;i++) { //①从Lb中依次取得每一个元素//②与La的每一个元素比较 //③如不存在,则插入之 } }//union void union(List &La,List Lb) { La_len=ListLength(La) ; Lb_len=ListLength(Lb); for(i=1;i<=lb_len;i++) { GetElem(Lb,i,e) if(!LocateElem(La,e,equal); ListInsert(La,++La_len,e); } }//union时间复杂度为O(ListLength(LA)×ListLength(LB))无序线性表合并的算法?需求:线性表LA和LB的数据元素按值非递减有序,归并LA和LB为LC,LC元素仍按值非递减有序排列。?解决方案:设指针i和j分别指向LA和LB的元素,比较i和j所指当前元素ai和bj,选min(ai,bj)插入为LC的元素?算法框架:void MergeList(List La,List Lb,List &Lc) { InitList(Lc); La_len=ListLength(La) ; Lb_len=ListLength(Lb); while((i<=la_len)&&(j<=lb_len)) { //①分别获取LA和LB的元素比较,将值小的插入LC} //②将LA或LB的剩余数据元素,插入LC中。 }//MergeList线性表应用:例2-2有序线性表合并的算法 void MergeList(List La,List Lb,List &Lc) { InitList(Lc); 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)//L