第02讲-线性表的ADT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二讲,算法和算法分析,线性表,上节回顾：,1.基本的数据结构有哪些？,2.存储结构有哪些？分类依据是什么?,3.从哪些方面描述一个抽象数据类型？,为什么要定义抽象数据类型？,4.算法等同程序吗？为什么？,算法是一个指令序列，用来描述求解问题的步骤。其中每一条指令表示一个或多个基本操作。,1有穷性 2确定性 3可行性,4有输入 5有输出,一、算法,一个算法必须满足以下,五,个重要特性：,例如：变量互换操作,二、算法设计的原则,1,正确性,2,.可读性,3,健壮性,4,高效率与低存储量需求,/,以二维数组存储矩阵元素，,c,为,a,和,b,的乘积,for,(i=1;i=n;+i),for,(j=1;j=n;+j),ci,j=0;,for,(k=1;k=n;+k),ci,j+=ai,k*bk,j;,基本操作:？,重复执行次数：?,例1：两个nn的矩阵相乘,一般情况下，算法中基本操作重复执行的次数是问题规模,n,的某个函数,f(n,),，算法的时间量度记作：,T(n,)=O(,f(n,),它表示随着问题规模,n,的增长，算法执行时间的增长率和,f(n,),的增长率相同,称作算法的,(,渐近,),时间复杂度,。,基本操作：最深层循环内语句中的原操作。它的执行次数，和包含它的,语句的频度,相同。,例2：分析下列程序段中包含x自增的语句频度,及该程序段的时间复杂度。,x+;s=0;,for(i=1;i=n;i+)+x;s+=x;,for(j=1;j=n;+j),for(k=1;k=n;+k)+x;s+=x;,算法还可能呈现的时间复杂度有对数阶,O(logn,),、指数阶,O(2,n,),等，如图,1.7,所示，分析其性能变化。,例3：分析下列程序段中包含x自增的语句频度,及该程序段的时间复杂度。,for(i=2;i=n;+i),for(j=2;j1,&,change,;-i),change=FALSE;,/change 为元素进行交换标志,for,(j=0;j aj+1),aj,aj+1;change=TRUE;,/一趟起泡,/bubble_sort,很多情况下，算法的基本操作重复次数还与问题的输入数据集有关。,引入平均时间复杂度、最坏情况下的时间复杂度。,抽象数据类型线性表的定义如下：,ADT List,数据对象：,D a,i,|a,i,ElemSet,i=1,2,.,n,n0,数据关系：,R1|a,i-1,a,i,D,i=2,.,n,基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作,ADT,List,结构销毁操作,DestroyList(&L),初始条件：,操作结果：,线性表,L,已存在。,销毁线性表,L,。,ListEmpty(L),ListLength(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,&pre_e),初始条件：,操作结果：,线性表,L,已存在。,若,cur_e,是,L,的元素，则用,pre_e,返回它的前驱，否则操作失败，,pre_e,无定义。,（求数据元素的前驱）,GetElem(L,i,&e),初始条件：,操作结果：,线性表,L,已存在，,用,e,返回,L,中第,i,个元素的值。,（求线性表中某个数据元素）,且,1iLengthList(L),LocateElem(L,e,compare(),初始条件：,操作结果：,线性表,L,已存在，,e,为给定值，,compare(),是元素判定函数。,返回,L,中第,1,个与,e,满足关系,compare(),的元素的,位序,。,若这样的元素不存在，则返回值为,0,。,（定位函数）,加工型操作,ClearList(&L),ListInsert(&L,i,e),ListDelete(&L,i,&e),ClearList(&L),初始条件：,操作结果：,线性表,L,已存在。,将,L,重置为空表。,（线性表置空）,ListDelete(&L,i,&e,),初始条件：,操作结果：,线性表,L,已存在且非空，,删除,L,的第,i,个元素，并用,e,返回其值，,L,的长度减,1,。,（删除数据元素）,1iLengthList(L),利用上述定义的抽象数据类型线性表，可以进行一些更复杂的操作。,例1：线性表LA和LB分别表示集合A和B,求A=AB.,1,从线性表 LB 中依次察看每个数据元素;,2,依值在线性表 LA 中进行查访;,3,若不存在，则插入之。,GetElem(LB,i),e,LocateElem(LA,e,equal(),ListInsert(LA,n+1,e),(n 表示线性表 LA 当前长度),操作步骤：,作业：,利用线性表提供的基本操作，编写一个函数从一个递增有序的线性表中删除元素值在x到y之间的所有元素。,