数据结构(清华大学完整)ppt课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,第一章,绪 论,1,.,1.1 数据结构讨论的范畴,1.2 与数据结构相关的概念,1.3 算法和算法的量度,2,.,软件开发的过程:,系统分析,系统实现,系统维护,系统设计,系统设计,确定系统所要达到的目标,确定实现方案并生成系统,实地安装调试,系统修整完善,3,.,Niklaus Wirth,Algorithm,+Data Structures=Programs,程序设计:,算法,:,数据结构,:,为计算机处理问题编制,一组指令集,处理问题的策略,问题的数学模型,4,.,例如:,鸡兔同笼问题,二元一次代数方程组,结构静力分析问题,全球天气预报,高次线性代数方程组,球面坐标系下的环流模式方程,5,.,非数值计算的程序设计问题,例一,求一组(n个),整数,中的最大值,例二,交叉路口的交通管制问题,例三,煤气管道的铺设问题,例四,数据库中表格管理问题,6,.,概括地说，,数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。,7,.,8,.,一、基本概念和术语,二、数据结构,三、数据类型和抽象数据类型,9,.,所有能,被输入,到计算机中，且能被计算机,处理的符号(数字、字符等),的集合。,数据,是,计算机操作的对象,的总称。,是计算机处理的,信息的,某种特定的符号,表示形式,。,10,.,是数据（集合）中的一个“,个体,”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的,基本单位,。,数据元素,例如，整数“,5,”,字符“,N,”等。,-是不可分割的“,原子,”,11,.,它是数据结构中讨论的,最小,单位,。,又如,描述一个学生的数据元素由多个款项构成，其中每个款项称为一个,“,数据项,”。,称之为,组合项,年 月 日,姓 名学 号班 号性别出生日期入学成绩,原子项,12,.,关键字,能识别一个或几个数据元素的数据项。若能起唯一识别作用，则被称为“,主,”关键字，否则称为“,次,”关键字。,数据对象,具有相同特性的数据元素的集合。,如:整数、实数等。,13,.,数据结构,带,结构,的数据元素的集合,有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的,关系,，则称为一个数据结构。,指的是数据元素之间存在的,关系,14,.,例如，可用,三个,4,位的十进制数,表示一个含,12,位数的“,长整数,”。,3214,6587,9345,a1,(3214),a2,(6587),a3,(9345),对长整数进行运算的程序中的操作对象是一个含三个数据元素a1,a2,a3的集合，且三者之间存在下列,“次序”关系:,a1,a2,、,a2,a3,。,15,.,又如，在,2,行,3,列的二维数组,中六个元素,a1,a2,a3,a4,a5,a6,之间存在着两个关系:,“行”的次序关系,:,row=,col=,“列”的次序关系,:,a1,a2,a3,a4,a5,a6,16,.,在含,6 个数据元素a1,a2,a3,a4,a5,a6 的集合上存在如下的,次序关系,:,|i=1,2,3,4,5,“,数据结构,”,是,相互之间存在着某种逻辑关系的数据元素的,集合,。,可见，不同的“,关系,”构成不同的“,结构,”,则构成“,一维数组,”,。,17,.,可用如下的数据结构描述“班集体”:,班主任，班长1，班长2，舍长1，舍长p,学生1，学生2，学生n,，,，,，,，,班主任,班长1,班长2,舍长1,舍长k,舍长k+1,舍长p,学,生,1,学,生,2,学,生,3,学,生,4,学,生,n-3,学,生,n-2,学,生,n-1,学,生,n,18,.,数据结构的形式定义描述,为:,数据结构,是一个二元组,Data_Structures=,(D,S),其中:,D,是,数据元素的有限集,，,S,是,D,上,关系的有限集,。,19,.,从,关系,或,结构,分,，数据结构,可归结为以下,四,类:,线性,结构,树形,结构,图状,结构,集合,结构,20,.,数据结构包括“,逻辑结构,”,和“,物理结构,”两个方面(层次):,逻辑结构,是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示;,物理结构,是逻辑结构在计算机中的表示和实现，故又称“,存储结构,”。,21,.,存储结构,是,逻辑结构在存储器中的,映象,“数据元素”的映象？,“关系”的映象？,用二进制位(bit)的位串表示数据元素,(321),10,=(501),8,=(101000001),2,A =(101),8,=(001000001),2,22,.,“关系”的两种映象方法：,（,表示,x,y,的方法,）,顺序映象,以 x 和 y 之间相对的存储位置表示后继关系,例如:,令 y 的存储位置和 x 的存储位置之间相差一个预设常量 C，而 C 是一个隐含值，,存储结构中只包含数据元素本身的信息,x y,23,.,链式映象,以附加信息(指针)表示后继关系,需要用一个和 x 绑定在一起的,附加信息(指针),指示 y 的存储位置,y x,以“由数据元素 x 的存储映象和附加的,指针,合成的,结点,”表示数据元素,。,24,.,存储结构的描述方法随编程环境的不同而不同，,当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。,typedef int,Long_int 3,例如，当以“顺序映象”表示长整数时，可定义,为:,25,.,定义“日期”,为:,typedef struct,int,y;/,年号 Year,int,m;/月号 Month,int,d;/日号 Day,DateType;/日期类型,定义“学生”,为:,typedef struct,char,id8;/学号,char,name16;/姓名,char,sex;/性别M/F:男/女,DateType bdate;/出生日期,Student;/学生类型,26,.,何谓“数据类型”？,在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，,明确说明,它们所,属的,数据类型,。,例如，,C+,语言中的,基本数据类型,有:,逻辑型,bool、,字符型,char、,整型,int 和,实型,(浮点型 float和双精度型 double),27,.,数据类型,是一个“,值,”的集合和定义在此集合上的“,一组操作,”的总称。,对程序员而言，各种语言中的整数类型都是一样的，因为它们的数学特性相同。,从这个意义上可称“整数”是一个,抽象数据类型,。,抽象数据类型和数据类型的实质相同，范畴更广，不局限于语言中的数据类型。,28,.,抽象数据类型,(,A,bstract,D,ata,T,ype,简称,ADT),是指一个数学模型以及定义在该模型上的一组操作。,通常称语言中已经实现的数据类型为,固有数据类型,。,抽象数据类型,有两个重要特征:,“数据抽象”和“数据封装”,29,.,数据抽象,数据封装,用,ADT,描述程序处理的实体时，强调的是其,本质的特征,、,其所能完成的功能,以及它和,外部用户的接口,（即,外界使用它的方法,）。,将实体的,外部特性和其内部实现细节分离,，并且,对外部用户隐藏,其内部实现细节,30,.,抽象数据类型的描述方法,ADT=（D，S，P）,其中:,D,是数据对象，,S,是,D,上的关系集，,P,是对,D,的基本操作集。,数据对象,是特性相同的数据元素的集合，是数据的一个子集。,31,.,例如,抽象数据类型“,复数,”的定义:,R1,|e1,是复数的实数部分,|e2,是复数的虚数部分,ADT Complex,数据对象：,De1,e2e1,e2RealSet ,数据关系：,32,.,基本操作：,AssignComplex(&Z,v1,v2),操作结果：构造复数 Z,其实部和虚部,分别被赋以参数 v1 和 v2 的值。,DestroyComplex(&Z),操作结果：复数 Z 被销毁。,GetReal(Z,&realPart),初始条件：复数 Z 已存在。,操作结果：用,realPart,返回复数 Z 的实部值。,33,.,GetImag(Z,&ImagPart),初始条件：复数已存在。,操作结果：用,ImagPart,返回复数 Z 的虚部值。,Add(z1,z2,&sum),初始条件：,z1,z2,是复数。,操作结果：用,sum,返回两个复数,z1,z2,的和值。,ADT Complex,34,.,#include,#include,complex.h,void main,(),35,.,complex z1,z2,z3,z4,z;,float RealPart,ImagPart;,InitComplex(z1,8.0,6.0);,InitComplex(z2,4.0,3.0);,Add(z1,z2,z3);,Multiply(z1,z2,z4);,if(Division(z4,z3,z),GetReal(z,RealPart);,GetImag(z,ImagPart);,/if,36,.,ADT,抽象数据类型名,数据对象：,数据对象的定义,数据关系：,数据关系的定义,基本操作：,基本操作的定义,ADT,抽象数据类型名,其中基本操作的定义格式为:,基本操作名,（,参数表,）,初始条件：,初始条件描述,操作结果,：,操作结果描述,37,.,赋值参数,只为操作提供输入值；,引用参数,以,&,打头，除可提供输入值外，,还将返回操作结果。,初始条件,描述操作执行之前的数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。,操作结果,说明在操作正常完成之后，数据结构的变化状况和应返回的结果。,初始条件可以为空，并可省略。,38,.,抽象数据类型的表示和实现,抽象数据类型需要通过,固有数据类型,(高级编程语言中已实现的数据类型)来实现。,例如，对之前定义的复数类型,39,.,typedef struct,float,realpart；,float,imagpart；,complex；,/-存储结构的定义,/-基本操作的函数原型说明,void,Assign(complex,&,Z,float,realval,float,imagval)；,/,构造复数 Z,其实部和虚部分别被赋以参数,/realval,和,imagval,的值,40,.,float,GetReal(cpmplex Z)；,/,返回复数 Z 的实部值,float,Getimag(cpmplex Z)；,/,返回复数 Z 的虚部值,void,add(complex z1,complex z2,complex&sum)；,/以 sum,返回两个复数,z1,z2,的和,41,.,/-基本操作的实现,void,add(complex z1,complex z2,complex,&,sum),/以 sum,返回两个复数,z1,z2,的和,sum.realpart=z1.realpart+z2.realpart;,sum.imagpart=z1.imagpart+z2.imagpart;,42,.,一、算法的定义,二、算法设计的原则,三、算法效率的衡量方法和准则,四、算法的存储空间需求,43,.,是为了解决某类问题而规定的一个有限长的,操作序列,。,3,可行性,一个算法必须满足以下,五,个重要,特性,：,算法,1,有穷性,2,确定性,5,有输出,4,有输入,44,.,有穷性,对于任意一组合法输入值，在执行,有穷步骤,之后一定能结束。算法中的每个步骤都能在,有限时间,内完成。,确定性,对于,每种情况,下所应执行的操作，在算法中都有,确切,的规定，使算法的执行者或阅读者都能明确其含义及如何执行。,并且,在任何条件下，算法都只有一条执行路径。,45,.,可行性,算法中的所有操作都必须,足够基本,，都可以通过已经实现的基本操作运算有限次实现之。,有输入,作为算法,加工对象,的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。,46,.,有输出,它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的,结果,，这种确定关系即为算法的功能。,47,.,设计算法时，通常应考虑达到以下目标：,1,正确性,2,.,可读性,3,健壮性,4,高效率与低存储量需求,48,.,正确性,首先，,算法应当,满足,以特定的,“规格说明”,方式给出的,需求,。,其次，,对算法是否,“,正确,”的,理解可以有以下,四个层次,：,a,不含语法错误；,b,对于,某几组输入数据,能够得出满足要求的结果；,49,.,c程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；,通常以,第,c,层,意义的正确性作为衡量一个算法是否合格的标准。,d,程序对于一切合法的输入数据都能得出满足要求的结果；,50,.,可读性,算法主要是为了人的,阅读与交流,，,其次才是为计算机执行。因此算法应该,易于,人的,理解,；,另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；,51,.,健壮性,当,输入的数据,非法,时，算法应当恰当地,作出反映或,进行相应处理,，而不是产生莫名奇妙的输出结果。并且，,处理出错的方法,不应是中断程序的执行，而应是,返回,一个,表示错误或错误性质的值,，以便在更高的抽象层次上进行处理。,52,.,高效率与低存储量需求,存储量,指的是算法执行过程中,所需的最大存储空间,。,两者都与问题的规模有关。,效率,指的是,算法执行时间,；,53,.,通常有,两种,衡量算法效率的方法:,事后统计法,事前分析估算法,缺点：,1,.,必须执行程序,2,.,其它因素掩盖算法本质,优点：,可以预先比较各种算法，以便,均衡利弊从中选优。,54,.,和算法执行,时间,相关的,因素,：,1,算法,选用,的策略,2,问题的规模,3,编写程序的语言,4,编译,程序产生的机器代码,的质量,5,计算机,执行指令,的速度,算法,选用,的策略,问题的规模,55,.,一个特定,算法的,“,运行工作量,”的大小，只依赖于,问题的规模,（通常用整数量,n,表示），或者说，它,是问题规模的函数,。,假如，随着问题规模 n 的增长，,算法执行时间的增长率和 f(n)的增长率相同,，则可记作：,T(n)=O(f(n),称,T(n),为算法的,(渐近),时间复杂度,56,.,如何估算,算法的时间复杂度？,57,.,算法=控制结构+原操作,（固有数据类型的操作）,算法的执行时间,=,(,原操作(i)的执行次数原操作(i)的执行时间,),算法的执行时间,与,原操作执行次数之和,成正比,58,.,从算法中选取一种对于所研究的问题来说是,基本操作,的原操作，以该基本操作,在算法中重复执行的次数,作为算法运行时间的衡量准则。,“,基本操作,”指的是，该操作重复执行次数和算法的运行时间成正比。,59,.,例,一,两,个,矩,阵,相,乘,void,mult(,int,a,int,b,int&,c),/,以二维数组存储矩阵元素，,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;,/for,/mult,基本操作:,乘法,操作,时间复杂度:,O(n,3,),for,for,for,*,60,.,void,select_sort(,int&,a,int,n),/,将 a 中整数序列重新排列成自小至大有序的整数序列,。,/select_sort,for,(i=0;i n-1;,+,i),例,二,选,择,排,序,基本操作:,比较,(数据元素),操作,时间复杂度:,O(n,2,),j=i;,/,选择第 i 个最小元素,for,(k=i+1;k n;,+,k),if,(,ak,1,&,change;-i),/bubble_sort,基本操作:,赋值,操作,时间复杂度:,O(n,2,),change=FALSE;,/change 为元素进行交换标志,for,(j=0;j aj+1),aj,aj+1;change=TRUE;,/一趟起泡,for,for,62,.,算法的,空间复杂度定义为:,表示随着问题规模 n 的增大，,算法运行所需存储量的增长率,与 g(n)的增长率相同。,S(n)=O(g(n),63,.,算法的存储量,包括:,1,输入数据,所占空间,2,程序本身,所占空间；,3,辅助变量,所占空间。,64,.,若,输入数据,所占空间只取决与问题本身，,和算法无关,，则只需要,分析除输入和程序之外的,辅助变量,所占,额外空间,。,若所需额外空间相对于输入数据量来说是个常量，则称此算法为,原地工作,。,若所需存储量依赖于特定的输入，,则通常按最坏情况考虑。,65,.,1.,熟悉各名词、术语的含义，掌握基本概念。,2.,理解算法五个要素的确切含义。,本章学习要点,3.掌握计算语句频度和估算算法时间复杂度的方法。,66,.,提几点要求:,1.课前预习，了解本堂课内容,;,2.课后复习，在理解教学内容的基础上,做练习题,;,3.独立完成作业,;,4.勤答疑，多问,“,为什么,”。,67,.,(n-1)+(n-2)+1=n(n-1)/2=n,2,/2+n/2,3,1,2,5,9,7,1,3,2,3,5,7,9,1,2,3,5,7,5,1,9,7,3,2,1,5,9,7,9,3,9,1,5,2,9,7,3,7,2,7,1,5,3,5,2,5,1,3,2,3,1,2,9,7,5,3,2,68,.,第二章,线性表,69,.,线性结构的基本特征:,1集合中必存在唯一的一个“第一元素”,2集合中必存在唯一的一个“最后元素”,3除最后元素在外，均有 唯一的后继,4除第一元素之外，均有 唯一的前驱,线性结构 是,一个数据元素的有序（次序）集,70,.,2.1,线性表的类型定义,2.3 线性表类型的实现,链式映象,2.4,一元多项式的表示,2.2 线性表类型的实现,顺序映象,71,.,ADT List,数据对象,：,D a,i,|a,i,ElemSet,i=1,2,.,n,n0,称,n,为线性表的,表长,;,称,n=0,时的线性表为,空表,。,数据关系,：,R1|a,i-1,a,i,D,i=2,.,n,设线性表为(a,1,，a,2,.，a,i,，.，a,n,),称 i 为 a,i,在线性表中的,位序,。,72,.,基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作,ADT,List,73,.,结构初始化,InitList(,&,L),操作结果：,构造,一个空的线性表 L。,CreateList(,&,L,A,n),初始条件：A中存在线性表的 n 个,数据元素。,操作结果：,构造,一个含 n 个数据元素,的线性表 L。,74,.,销毁结构,DestroyList(,&,L),初始条件：线性表 L 已存在。,操作结果：,销毁,线性表 L。,75,.,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(),引用型操作,76,.,ListEmpty(L)（线性表判空）,初始条件：,操作结果：,线性表,L,已存在。,若,L,为空表，则返回,TRUE,，否则,FALSE,。,ListLength(L)（求线性表的长度）,初始条件：,操作结果：,线性表,L,已存在。,返回线性表,L,中元素个数。,77,.,PriorElem(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,无定义。,78,.,GetElem(L,i,&e)（求线性表中某个元素）,初始条件：,操作结果：,线性表,L,已存在,以,e,带回,L,中,第,i,个,数据元素值,。,LocateElem(L,e,compare()（定位函数）,初始条件：,操作结果：,线性表,L,已存在,compare()为判定函数,。,返回 L 中,第 1 个,与 e,满足关系,compare()的元素的,位序,，若不存在这样的元素，则返回,0,。,且,1iLengthList(L),。,79,.,ListTraverse(L,visit()（遍历线性表）,初始条件：,操作结果：,线性表,L,已存在,visit()为数据元素的访问函数。,依次对,L,的每个数据元素调用函数,visit()，一旦 visit()失败，则遍历操作失败,。,80,.,ClearList(&L),(线性表置空),ListInsert(&L,i,e),(插入数据元素),PutElem(&L,i,&e),(改变数据元素的值),ListDelete(&L,i,&e),(删除数据元素),加工型操作,81,.,ClearList(&L),初始条件：,操作结果：,线性表,L,已存在。,将 L 重置为空表。,PutElem(&L,i,e),初始条件：,操作结果：,L 中第 i 个元素赋值和 e 相同,。,线性表,L,已存在，,且,1iLengthList(L),。,82,.,ListInsert(&L,i,e),初始条件：,操作结果：,线性表,L,已存在,在,L 的第 i 个元素之前插入新的元素e,L 的长度增 1,。,ListDelete(&L,i,e),初始条件：,操作结果：,线性表,L,已存在,删除,L 中第 i 个元素，并以 e 带回其值,L 的长度减 1,。,1iLengthList(L)+1,。,1iLengthList(L),。,83,.,例,2-1,假设有两个,集合,A 和 B,分别用两个,线性表 LA 和 LB,表示，即：线性表中的数据元素即为集合中的成员。,现要求一个新的集合,AAB,。,即:需对线性表作如下操作：,扩大线性表,LA,，将,存在于线性表,LB,中,而,不存在于线性表,LA 中,的数据元素,插入到线性表 LA,中,去。,84,.,1取得,线性表 LB 中一个数据元素;,2,依值在线性表 LA 中进行查访;,3,若不存在，则插入之。,ListDelete(Lb,1,e);,LocateElem(LA,e,equal();,ListInsert(LA,n+1,e);,(n 表示线性表 LA 当前长度),操作步骤：,85,.,ListDelete(Lb,1,e);,/,删除Lb中第1个数据元素赋给e,if,(,!,LocateElem(La,e,equal(),ListInsert(La,+La_len,e);,/,La中不存在和 e 相同的数据元素，则插入之,La_len=ListLength(La);,/,求线性表La的长度,while,(!ListEmpty(Lb),/,while,/union,void,union(List,&,La,List Lb),/将线性表Lb中所有在线性表La中不存在的数据元素,/插入到线性表La中,86,.,例,2-2,已知一个“非纯集合”B，试,构造,一个纯集合A，使 A 中只包含 B 中所有值各不相同的数据元素。,若仍然以线性表表示集合，则,算法的策略应该和例一基本相同,差别是什么？,1,.,集合 A 的初态是“空集”,2,.不破坏,集合 B,87,.,void,purge(List,&,La,List Lb),La_len=0;Lb_len=ListLength(Lb);,/pugre,GetElem(Lb,i,e);,/,取Lb中第 i 个数据元素赋给 e,if,(,!,LocateElem(La,e,equal(),ListInsert(La,+La_len,e);,/,La中不存在和 e 相同的数据元素，则插入之,for,(i=1;i=Lb_len;i+),/for,InitList(La);,/,构造(空的)线性表,LA,88,.,例,2-3,判别两个集合是否相等。,集合相等的条件是:两者所含元素个数相同，且所有对应元素都相等。,仍以线性表表示集合，并假设这两个集合是“纯集合”。,则算法的策略为:在两个线性表的长度相等的前提下，只要判别一个表中的元素在另一个表中都存在即可。,89,.,bool,isEqual(List LA,List LB),/若线性表LA和LB不仅长度相等，且所含数据,/元素也相同，则返回 TRUE,否则返回 FALSE,/isEqual,La_len=Listlength(LA);,Lb_len=Listlength(LB);,if,(La_len!=Lb_len),return FALSE,;/两表的长度不等,else,90,.,while,(i=La_len,&,found),/while,return,found;,GetElem(LA,i,e);/取得LA中一个元素,if,(LocateElem(LB,e,equal(),i+;/依次处理下一个,else,found=,FALSE,;,/LB中没有和该元素相同的元素,i=1;found=,TRUE,;,91,.,一,、,顺序表,-线性表的顺序映象,二、顺序表中基本操作的实现,三,、,顺序表的其它操作举例,92,.,最简单的一种顺序映象方法是：,令 y 的存储位置和 x 的存储位置相邻,。,顺序映象,以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系,93,.,用一组,地址连续,的存储单元,依次存放,线性表中的数据元素,线性表的,起始地址,，,称作线性表的,基地址,a,1,a,2,a,i-1,a,i,a,n,94,.,以“,存储位置相邻,”表示有序对,即：LOC(a,i,)=LOC(a,i-1,)+C,一个数据元素所占存储量,所有数据元素的存储位置均取决于,第一个数据元素的存储位置,LOC(a,i,)=,LOC(a,1,),+(i-1),C,基地址,95,.,顺序表的 C 语言描述,/存储结构,typedef struct,SqList;/俗称,顺序表,ElemType,*elem,;/,存储空间基址,int,length,;/,当前长度,int,listsize,;/,当前分配的存储容量,/(以sizeof(ElemType)为单位),/基本操作接口,96,.,void,purge(SqList,&,La,SqList Lb),/构造顺序表La，使其只包含Lb中所有值不,/相同的数据元素,算法不改变顺序表Lb,bool,b;,int,Lb_len=Listlength(Lb);/求线性表Lb的长度,InitList(La,Lb_len);/创建一个空的线性表La,int,La_len=0;,for,(i=1;i=Lb_len;i+),/依次处理Lb中每个元素,/for,/purge,97,.,b=GetElem(Lb,i,e);,/取Lb中第i个数据元素赋给e,if,(,!,LocateElem(La,e,equal(),+La_len;,b=ListInsert(La,La_len,e);,/当 La中不存在和 e 值相同的数据,/元素时进行插入,98,.,线性表的基本操作在顺序表中的实现,InitList(&L)/结构初始化,LocateElem(L,e,compare()/查找,ListInsert(&L,i,e)/插入元素,ListDelete(&L,i)/删除元素,99,.,Status,InitList(SqList,&,L,int,maxsize),/构造一个最大容量为 maxsize 的顺序表,/InitList,算法,时间复杂度,：,O(1),L.elem=new ElemTypemaxsize;,/,为顺序表分配大小为,maxsize,的数组空间,if,(,!,L.elem),exit,(OVERFLOW);,L.length=0;,L.listsize=maxsize;,return,OK;,100,.,例如：顺序表,23 75 41 38 54 62 17,L.elem,L.length=7,L.listsize,假设,e=,38,p,p,p,p,p,i=,1,2,3,4,1,8,50,p,可见，基本操作是，,将顺序表中的元素,逐个和给定值 e,相比较。,101,.,int,LocateElem(SqList L,ElemType e,Status,(*compare)(ElemType,ElemType),/,在顺序表中查询第一个满足判定条件的数据元素，,/,若存在，则返回它的位序，否则返回 0,/LocateElem,O(ListLength(L),if,(i=L.length),return,i;,else return,0;,算法的,时间复杂度,为：,i=1;,/,i 的初值为第 1 元素的位序,p=L.elem;,/,p 的初值为第 1 元素的存储位置,while,(,i=L.length,&,!,(*compare)(*p+,e),)+i;,(*compare)(*p+,e),/找到满足条件的元素,/没有找到满足条件的元素,102,.,线性表操作,ListInsert(&L,i,e),的实现：,首先分析:,插入元素时，,线性表的,逻辑结构,发生什么变化,？,103,.,(a,1,a,i-1,a,i,a,n,)改变为,a,1,a,2,a,i-1,a,i,a,n,a,1,a,2,a,i-1,a,i,e,a,n,表的长度增加,(a,1,a,i-1,e,a,i,a,n,),104,.,Status,ListInsert(SqList,&,L,int i,ElemType e),/,在顺序表,L,的第,i,个元素之前插入新的元素e,/i 的合法范围为 1iL.length+1,/ListInsert,算法时间复杂度,为:,for,(j=L.length-1;j=pos-1;-j),L.elemj+1=L.elemj;,/插入位置及之后的元素右移,L.elempos-1=e;/插入e,+L.length;/表长增1,return TRUE,;,O(ListLength(L),元素右移,105,.,考虑移动元素的平均情况:,假设在第,i,个元素之前插入的概率为,p,i,，,则在长度为,n,的线性表中,插入一个元素所需移动元素次数的期望值,为：,若,假定,在线性表中任何一个位置上进行,插入的概率,都是,相等,的，则,移动元素的期望值,为,：,106,.,if,(L.length=L.listsize),return,OVERFLOW;,/当前存储空间已满,if,(i L.length+1),return,ERROR;,/,插入位置不合法,107,.,21 18 30 75 42 56 87,21 18 30 75,例如：ListInsert(L,5,66),L.length-1,0,j,87,56,42,66,for,(j=L.length-1;j=pos-1;-j),L.elemj+1=L.elemj;,4,j,j,108,.,线性表操作,ListDelete(&L,i,&e),的实现：,首先分析：,删除元素时，,线性表的逻辑结构发生什么变化？,109,.,(a,1,a,i-1,a,i,a,i+1,a,n,)改变为,a,i+1,a,n,表的长度减少,a,1,a,2,a,i-1,a,i,a,i+1,a,n,a,1,a,2,a,i-1,(a,1,a,i-1,a,i+1,a,n,),110,.,Status,ListDelete,(SqList,&,L,int,i,ElemType,&,e),/ListDelete,算法时间复杂度,为:,O(ListLength(L),for,(j=pos;jL.length;+j),L.elemj-1=L.elemj;,/被删除元素之后的元素左移,-L.length;/,表长减1,return,TRUE,;,if,(i L.length),return,ERROR;,/,删除位置不合法,元素左移,111,.,考虑移动元素的平均情况:,假设删除第 i 个元素的概率为 q,i,则在长度为,n,的线性表中删除一个元素所需,移动元素次数的期望值,为：,若假定在线性表中任何一个位置上进行删除的,概率,都是,相等,的，则,移动元素的期望值,为：,112,.,21 18 30 75 42 56 87 63,21 18 30 75,L.length-1,0,j,87,56,for,(j=pos;jL.length;+j),L.elemj-1=L.elemj;,例如：ListDelete(L,5,e),63,5,j,j,113,.,试设计一个算法，用尽可能少的辅助空间将顺序表中前 m 个元素和后 n 个元素进行互换，即将线性表,(a,1,a,2,a,m,b,1,b,2,b,n,)改变成,(b,1,b,2,b,n,a,1,a,2,a,m,)。,从,b,1,开始，从原地删除之后插入到,a,1,之前直至,b,n,。,例,2-4,算法,1,进行三次“,逆转顺序表,”的操作。,算法,2,114,.,a,b,c,d,e,f,g,1,2,3,4,5,1,g,g,g,f,f,f,e,e,e,d,d,d,c,c,c,b,b,b,a,a,a,2,3,1,2,3,j,i,j,i,j,i,a,b,c,d,e,f,g,1,2,3,4,5,a,b,c,d,e,e,f,f,g,1,2,3,4,4,5,c,b,g,a,2,5,1,115,.,void,invert(ElemType,&,R，,int,s，,int,t),/本算法将数组 R 中下标自 s 到 t 的元素逆置，,/即将（R,s,R,s+1,R,t-1,R,t,）,/改变为（R,t,R,t-1,R,s+1,R,s,）,void,exchange(SqList,&,A;,int,m),/本算法实现顺序表中前 m 个元素,/和后 n 个元素的互换,n=A.length,m;,invert(A.elem,0,A.length);,invert(A.elem,0,n-1);,invert(A.elem,n,m+n-1);,/exchange,算法的时间复杂度为:O(m,+n),116,.,void,exchange(SqList,&,A,int,m),/实现顺序表 A 中前 m 个元素和后 n 个元素互换,exchange,for(i=0;,j=m;,ji;k-),A.elemj=A.elemj-1;,A.elemi=x;,算法的时间复杂度,为:O(m,n),117,.,试编写算法，删除顺序表中“多余”的数据元素。,例,2-5,从,a,1,开始，检查在它之后的数据元素，如有和它相等的，则从表中删除之。,算法,1,回顾例2-2的算法，试按“构造”一个新的顺序表的思想来进行，设想这两个表“共享”一个存储空间。,算法,2,118,.,5,2,5,3,3,4,2,5,7,5,4,3,i,j,3,3,4,2,5,5,7,4,3,7,5,4,3,j,j,3,i,4,L.length-1,L.length-1,L.length-1,L.length-1,j,5,2,5,3,3,4,2,5,7,5,4,3,k,i,5,2,3,i,i,i,i,i,i,i,i,i,i,i,k,k,k,k,4,7,k,i,119,.,void purge(SqList&L),/删除顺序表 L 中冗余元素,for