数据结构c语言版严蔚敏PPT.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法与数据结构,教材,：,数据结构,(C,语言版,),。严蔚敏，吴伟民 编 著。清华大学出版社。,参考文献,：,1,数据结构,。张选平，雷咏梅 编，严蔚敏 审。机械工业出版社。,2,数据结构与算法分析,。,Clifford A.Shaffer,著，张 铭，刘晓丹 译。电子工业出版社。,3 ,数据结构习题与解析,(C,语实言版,),。李春葆。,清华大学出版社。,4 ,数据结构与算法,。夏克俭 编著。国防工业出版社。,第,1,章 绪 论,目前，计算机已深入到社会生活的各个领域，其应用已不再仅仅局限于科学计算，而更多的是用于控制，管理及数据处理等非数值计算领域。计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的,表示,，信息的,处理,。,信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题的不断复杂，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，必须分析待处理问题中的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。,编写解决实际问题的程序的一般过程,：,如何用数据形式描述问题,?,即由问题抽象出一个适当的数学模型,;,问题所涉及的数据量大小及数据之间的关系,;,如何在计算机中存储数据及体现数据之间的关系,?,处理问题时需要对数据作何种运算,?,所编写的程序的性能是否良好,?,上面所列举的问题基本上由数据结构这门课程来回答。,计算机求解问题的一般步骤,1.1,数据结构及其概念,算法与数据结构,是计算机科学中的一门综合性专业基础课。是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。,1.1.1,数据结构的例子,姓名,电话号码,陈海,13612345588,李四锋,13056112345,。,。,例,1,：电话号码查询系统,设有一个电话号码薄，它记录了,N,个人的名字和其相应的电话号码，假定按如下形式安排：,(a,1,b,1,),，,(a,2,b,2,),，,(a,n,b,n,),，,其中,a,i,b,i,(i=1,，,2n),分别表示某人的名字和电话号码。,本问题是一种典型的表格问题,。,如表,1-1,，数据与数据成简单的一对一的,线性关系,。,表,1-1,线性表结构,例,2,：磁盘目录文件系统,磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推,：,本问题是一种典型的树型结构问题，如图,1-1,，数据与数据成一对多的关系，是一种典型的非线性关系结构,树形结构,。,图,1-1,树形,结构,例,3,：交通网络图,从一个地方到另外一个地方可以有多条路径。本问题是一种典型的,网状结构,问题，数据与数据成多对多的关系，是一种非线性关系结构。,佛山,惠州,广州,中山,东莞,深圳,珠海,图,1-2,网状结构,数据,(,Data,),：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。,数据元素,(,Data Element,),：是数据的基本单位，在程序中通常,作为一个整体,来进行考虑和处理。,一个数据元素可由若干个,数据项,(,Data Item,),组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。,数据对象,(,Data Object,),：是性质相同的数据元素的集合，是数据的一个子集。如字符集合,C=A,B,C,。,1.1.2,基本概念和术语,数据结构,(,Data Structure,),：是指相互之间具有,(,存在,),一定联系,(,关系,),的数据元素的集合。元素之间的相互联系,(,关系,),称为,逻辑结构,。数据元素之间的逻辑结构有四种基本类型，如图,1-3,所示。,集合,：结构中的数据元素除了“同属于一个集合”外，没有其它关系。,线性结构,：结构中的数据元素之间存在一对一的关系。,树型结构,：结构中的数据元素之间存在一对多的关系。,图状结构或网状结构,：结构中的数据元素之间存在多对多的关系。,数据结构的形式定义是一个二元组：,Data-Structure=(D,，,S),其中：,D,是数据元素的有限集，,S,是,D,上关系的有限集。,例,2,：设数据逻辑结构,B=,（,K,，,R,）,K=k,1,k,2,k,9,R=,，,，,，,，,，,，,，,，,，,，,画出这逻辑结构的图示，并确定那些是起点，那些是终点,1.1.3,数据结构的形式定义,图,1-3,四类基本,结构图,1.1.4,数据结构的存储方式,数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种,自然或人为定义的,“关系”,称为数据元素之间的,逻辑关系,，相应的,结构,称为,逻辑结构,。,数据结构在计算机内存中的存储包括,数据元素的存储,和,元素之间的关系的表示,。,元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示,。,由此得出两种不同的存储结构：,顺序存储结构,和,链式存储结构,。,顺序存储结构,：,用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构,(,关系,),。,链式存储结构,：,在每一个数据元素中增加一个存放另一个元素地址的指针,(pointer),，用该指针来表示数据元素之间的逻辑结构,(,关系,),。,例：,设有数据集合,A=3.0,2.3,5.0,-8.5,11.0,，两种不同的存储结构。,顺序结构：数据元素存放的,地址是连续的,；,链式结构：数据元素存放的,地址是否连续没有要求,。,数据的逻辑结构和物理结构是密不可分的两个方面，一个,算法的设计取决于,所选定的,逻辑结构,，而,算法的实现依赖于,所采用的,存储结构,。,在,C,语言中，用,一维数组,表示顺序存储结构,；,用,结构体类型,表示链式存储结构。,数据结构的三个组成部分：,逻辑结构,：,数据元素之间逻辑关系的描述,D_S=,（,D,，,S,）,存储结构,：,数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。,数据操作,：,对数据要进行的运算。,本课程中将要讨论的三种逻辑结构及其采用的存储结构如图,1-4,所示。,数据的逻辑结构,非线性结构,集合,图状结构,有向图,无向图,树形结构,一般树,二叉树,线性结构,一般线性表,线性表推广,广义表,数组,串,受限线性表,栈和队列,图,1-5,数据逻辑结构层次关系图,图,1-4,逻辑结构与所采用的存储结构,线性表,树,图,顺序存储结构,链式存储结构,复合存储结构,逻辑结构,物理结构,数据类型,(,Data Type,),：指的是,一个值的集合,和定义在,该值集上的一组操作,的总称。,数据类型是和数据结构密切相关的一个概念。在,C,语言中数据类型有：基本类型和构造类型。,数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。,1.1.5,数据类型,数据结构的主要运算包括：,建立,(Create),一个数据结构；,消除,(Destroy),一个数据结构；,从一个数据结构中删除,(Delete),一个数据元素；,把一个数据元素插入,(Insert),到一个数据结构中；,对一个数据结构进行访问,(Access),；,对一个数据结构,(,中的数据元素,),进行修改,(Modify),；,对一个数据结构进行排序,(Sort),；,对一个数据结构进行查找,(Search),。,1.1.6,数据结构的运算,抽象数据类型,(,Abstract Data Type,，简称,ADT,),：是指一个数学模型以及定义在该模型上的一组操作。,ADT,的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论,ADT,的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。,ADT,的形式化定义是三元组：,ADT=(D,，,S,，,P),其中：,D,是,数据对象,，,S,是,D,上的,关系集,，,P,是对,D,的,基本操作集,。,1.2,抽象数据类型,ADT,的一般定义形式是：,ADT,数据对象：,数据关系：,基本操作：,ADT,其中数据对象和数据关系的定义用伪码描述。,基本操作的定义是：,(),初始条件：,操作结果：,初始条件：描述操作执行之前数据结构和参数应满足的条件,;,若不满足，则操作失败，返回相应的出错信息。,操作结果：描述操作正常完成之后，数据结构的变化状况和 应返回的结果。,1.3.1,算法,算法,(,Algorithm,),：是对特定问题求解方法,(,步骤,),的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。,算法具有以下五个特性,有穷性,：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。,确定性,：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。,可行性,：一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。,1.3,算法分析初步,输入,：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。,输出,：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。,一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述。,算法和程序是两个不同的概念,。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。,在本门课程的学习、作业练习、上机实践等环节，算法都用,C,语言来描述。在上机实践时，为了检查算法是否正确，应编写成完整的,C,语言程序。,评价一个好的算法有以下几个标准,正确性,(,Correctness,),：算法应满足具体问题的需求。,可读性,(,Readability,),：算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。,健壮性,(,Robustness,),：算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。,通用性,(,Generality,),：算法应具有一般性，即算法的处理结果对于一般的数据集合都成立。,1.3.2,算法设计的要求,算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：,事后统计,：计算机内部进行执行时间和实际占用空间的统计。,问题：必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖算法本身的优劣；没有实际价值。,事前分析,：求出该算法的一个时间界限函数。,1.3.3,算法效率的度量,效率与存储量需求,：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。,与此相关的因素有：,依据算法选用何种策略；,问题的规模；,程序设计的语言；,编译程序所产生的机器代码的质量；,机器执行指令的速度；,撇开软硬件等有关部门因素，可以认为一个特定算法“,运行工作量,”的大小，只依赖于问题的规模（通常用,n,表示），或者说，它,是问题规模的函数,。,算法分析应用举例,算法中,基本操作重复执行的次数,是问题规模,n,的某个函数，其时间量度记作,T(n)=O(f(n),，称作算法的渐近时间复杂度,(,Asymptotic Time complexity,),，简称,时间复杂度,。,一般地，常用,最深层循环内,的语句中的原操作的,执行频度,(,重复执行的次数,),来表示。,“,O”,的定义：若,f(n),是正整数,n,的一个函数，则,O(f(n),表示,M,0,，使得当,n,n,0,时，,|f(n)|,M,|f(n,0,)|,。,表示,时间复杂度,的阶有：,O(1),：常量时间阶,O(n),：线性时间阶,O(n),：对数时间阶,O(nn),：线性对数时间阶,O(n,k,),：,k,2,，,k,次方时间阶,例 两个,n,阶方阵的乘法,for(i=1,，,i=n;+i),for(j=1;j=n;+j),cij=0;,for(k=1;k=n;+k),cij+=aik*bkj;,由于是一个三重循环，每个循环从,1,到,n,，则总次数为：,nnn=n,3,时间复杂度为,T(n)=O(n,3,),例,+x;s=0;,将,x,自增看成是基本操作，则语句频度为，即时间复杂度为,(1),。,如果将,s=0,也看成是基本操作，则语句频度为，其时间复杂度仍为,(1),，即常量阶。,例,for(i=1;i=n;+i),+x;s+=x;,语句频度为：,2n,，其时间复杂度为：,O(n),，即为线性阶。,例,for(i=1;i=n;+i),for(j=1;j=n;+j),+x;s+=x;,语句频度为：,2n,2,，其时间复杂度为：,O(n,2,),，即为平方阶。,定理,：,若,A(n)=a,m,n,m,+a,m-1,n,m-1,+a,1,n+a,0,是一个,m,次多项式，则,A(n)=O(n,m,),例,for(i=2;i=n;+i),for(j=2;j=i-1;+j),+x;ai,j=x;,语句频度为：,1+2+3+,+n-2=(1+n-2)(n-2)/2,=(n-1)(n-2)/2=n,2,-3n+2,时间复杂度为,O(n,2,),，即此算法的时间复杂度为平方阶。,一个算法时间为,O(1),的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为,O(n,2,),的算法则由一个二次多项式来限界。,以下六种计算算法时间的多项式是最常用的。其关系为：,O(1)O(n)O(n)O(nn)O(n,2,)O(n,3,),指数时间的关系为：,O(2,n,)O(n!)sqrt(n),printf(“&d,是一个素数,n”,n);,else,printf(“&d,不是一个素数,n”,n);,嵌套的最深层语句是,i+,；其频度由条件,(n%i)!=0&i*1.0 sqrt(n),决定，显然,i*1.01 -i),for(j=0;jaj+1),aj aj+1;change=TURE;,最好情况：,0,次,最坏情况：,1+2+3+,+n-1=n(n-1)/2,平均时间复杂度为：,O(n,2,),1.3.4,算法的空间分析,空间复杂度,(,Space complexity,),：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作：,S(n)=O(f(n),其中：,n,为问题的规模,(,或大小,),该存储空间一般包括三个方面：,指令常数变量所占用的存储空间,;,输入数据所占用的存储空间,;,辅助,(,存储,),空间。,一般地，算法的,空间复杂度,指的是,辅助空间,。,一维数组,an,：空间复杂度,O(n),二维数组,anm,：空间复杂度,O(n*m),习 题 一,1,简要回答术语：数据，数据元素，数据结构，数据类型。,2,数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？,3,数据结构的主要运算包括哪些？,4,算法分析的目的是什么？算法分析的主要方面是什么？,5,分析以下程序段的时间复杂度，请说明分析的理由或原因。,Sum1(int n),int p=1,sum=0,m;,for(m=1;m=n;m+),p*=m;sum+=p;,return(sum);,Sum2(int n),int sum=0,m,t;,for(m=1;m=n;m+),p=1;,for(t=1;t=m;t+)p*=t;,sum+=p;,return(sum);,递归函数,fact(int n),if(n0,时，将非空的线性表记作：,(a,1,，,a,2,，,a,n,),a,1,称为线性表的,第一个,(,首,),结点，,a,n,称为线性表的,最后一个,(,尾,),结点。,2.1.1,线性表的定义,a,1,，,a,2,，,a,i-1,都是,a,i,(2,i,n),的,前驱,，其中,a,i-1,是,a,i,的,直接前驱,;,a,i+1,，,a,i+2,，,a,n,都是,a,i,(1,i,n-1),的,后继,，其中,a,i+1,是,a,i,的,直接后继,。,2.1.2,线性表的逻辑结构,线性表中的数据元素,a,i,所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。,线性表中的,结点,可以是,单值元素,(,每个元素只有一个数据项,),。,例,1:26,个英文字母组成的字母表：,(A,，,B,，,C,、,、,Z,）,例,2,：某校从,1978,年到,1983,年各种型号的计算机拥有量的变化情况：,(6,，,17,，,28,，,50,，,92,，,188,）,例,3,：一副扑克的点数,(2,，,3,，,4,，,，,J,，,Q,，,K,，,A),线性表中的,结点,可以是,记录型,元素，每个元素含有多个数据项，每个项称为结点的一个域。每个元素有一个可以唯一标识每个结点的,数据项组,，称为,关键字,。,例,4,：某校,2001,级同学的基本情况：,(2001414101,，张里户，男，,06/24/1983),，,(2001414102,，张化司，男，,08/12/1984),，,(2001414102,，李利辣，女，,08/12/1984),若线性表中的结点是,按值,(,或按关键字值,),由小到大,(,或由大到小,),排列,的，称线性表是有序的。,2.1.3,线性表的抽象数据类型定义,ADT List,数据对象：,D=a,i,|a,i,ElemSet,i=1,2,n,n,0,数据关系：,R=|a,i-1,a,i,D,i=2,3,n,基本操作：,InitList(&L),操作结果：构造一个空的线性表,L,；,线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。,对线性表的数据元素可以访问、插入和删除。,ListLength(L),初始条件：线性表,L,已存在；,操作结果：若,L,为空表，则返回,TRUE,，否则返回,FALSE,；,.,GetElem(L,i,&e),初始条件：线性表,L,已存在，,1,i,ListLength(L),；,操作结果：用,e,返回,L,中第,i,个数据元素的值；,ListInsert(L,i,&e),初始条件：线性表,L,已存在，,1,i,ListLength(L),；,操作结果：在线性表,L,中的第,i,个位置插入元素,e,；,ADT List,2.2,线性表的顺序存储,顺序存储,：把线性表的结点,按逻辑顺序,依次存放在一组地址连续的存储单元,里。用这种方法存储的线性表简称顺序表。,顺序存储,的线性表的,特点,：,线性表的逻辑顺序与物理顺序一致,;,数据元素之间的关系是以元素在计算机内“,物理位置相邻,”来体现。,设有非空的线性表：,(a,1,，,a,2,，,a,n,),。顺序存储如图,2-1,所示。,2.2.1,线性表的顺序存储结构,在具体的机器环境下,：设线性表的每个元素需占用,l,个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第,i+1,个数据元素的存储位置,LOC(a,i+1,),和第,i,个数据元素的存储位置,LOC(a,i,),之间满足下列关系：,LOC(a,i+1,)=LOC(a,i,)+,l,线性表的第,i,个数据元素,a,i,的存储位置为：,LOC(a,i,)=LOC(a,1,)+(i-1)*,l,a,1,a,2,a,i,a,n,Loc(a,1,),Loc(a,i,)+(i-1)*,l,图,2-1,线性表的顺序存储表示,在高级语言,(,如,C,语言,),环境下,：数组具有随机存取的特性,，因此，借助数组来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。,#define OK 1,#define ERROR -1,#define MAX_SIZE 100,typedef int Status;,typedef int ElemType;,typedef struct sqlist,ElemType Elem_arrayMAX_SIZE;,int length;,SqList;,2.2.2,顺序表的基本操作,顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等,。,以下将对几种主要的操作进行讨论,。,1,顺序线性表初始化,Status Init_SqList(SqList*L),L-elem_array=(ElemType*)malloc(MAX_SIZE*sizeof(ElemType);,if(!L-elem_array)return ERROR;,else L-length=0;return OK;,2,顺序,线性表的插入,在线性表,L=(a,1,，,a,i-1,，,a,i,，,a,i+1,，,，,a,n,),中,的第,i(1in),个位置上插入一个新结点,e,，使其成为线性表,：,L=(a,1,，,a,i-1,，,e,，,a,i,，,a,i+1,，,，,a,n,),实现步骤,(1),将线性表,L,中的,第,i,个至第,n,个结点后移一个位置。,(2),将结点,e,插入到结点,a,i-1,之后,。,(3),线性表长度加,1,。,算法描述,Status Insert_SqList(Sqlist*L,，,int i,，,ElemType e),int j;,if (iL-length-1)return ERROR;,if (L-length=MAX_SIZE),printf(“,线性表溢出,!n”);return ERROR;,for (j=L-length1;j=i-1;-j),L-Elem_arrayj+1=L-Elem_arrayj;,/*i-1,位置以后的所有结点后移 *,/,L-Elem_arrayi-1=e;,/*,在,i-1,位置插入结点 *,/,L-length+;,return OK;,时间复杂度分析,在线性表,L,中的,第,i,个,元素之前插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。,设,在线性表,L,中的,第,i,个,元素之前插入结点的概率为,P,i,，不失一般性，设各个位置插入是等概率，则,P,i,=1/(n+1),，而插入时移动结点的次数为,n-i+1,。,总的平均移动次数：,E,insert,=,p,i,*(n-i+1),(1in),E,insert,=n/2,。,即,在顺序表上做插入运算，平均要移动表上一半结点。当表长,n,较大时，算法的效率相当低。因此算法的平均时间复杂度为,O(n),。,3,顺序线性表的删除,在线性表,L=(a,1,，,a,i-1,，,a,i,，,a,i+1,，,，,a,n,),中删除结点,a,i,(1in),，使其成为线性表,：,L=(a,1,，,a,i-1,，,a,i+1,，,，,a,n,),实现步骤,(1),将线性表,L,中的,第,i+1,个至第,n,个结点依此向前移动一个位置。,(2),线性表长度减,1,。,算法描述,ElemType Delete_SqList(Sqlist*L,，,int i),int k;ElemType x;,if (L-length=0),printf(“,线性表,L,为空,!n”);return ERROR;,else if(iL-length),printf(“,要删除的数据元素不存在,!n”);,return ERROR;,else x=L-Elem_arrayi-1;,/*,保存结点的值*,/,for(k=i;klength;k+),L-Elem_arrayk-1=L-Elem_arrayk;,/*i,位置以后的所有结点前移 *,/,L-length-;return(x);,时间复杂度分析,删除线性表,L,中的,第,i,个,元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。,设,在线性表,L,中,删除第,i,个,元素的概率为,P,i,，不失一般性，设删除各个位置是等概率，则,P,i,=1/n,，而删除时移动结点的次数为,n-i,。,则总的平均移动次数：,E,delete,=,p,i,*(n-i),(1in),E,delete,=(n-1)/2,。,即,在顺序表上做删除运算，平均要移动表上一半结点。当表长,n,较大时，算法的效率相当低。因此算法的平均时间复杂度为,O(n),。,4,顺序线性表的查找定位删除,在线性表,L=(a,1,，,a,2,，,，,a,n,),中删除值为,x,的第一个结点,。,实现步骤,(1),在线性表,L,查找值为,x,的第,一个数据元素。,(2),将从找到的位置至最后一,个结点依次向前移动一个位置。,(3),线性表长度减,1,。,算法描述,Status Locate_Delete_SqList(Sqlist*L,，,ElemType x),/*,删除线性表,L,中值为,x,的,第,一个,结点,*,/,int i=0,k;,while (ilength),/*,查找值为,x,的,第,一个,结点,*,/,if (L-Elem_arrayi!=x)i+;,else,for(k=i+1;klength;k+),L-Elem_arrayk-1=L-Elem_arrayk;,L-length-;break;,if (iL-length),printf(“,要删除的数据元素不存在,!n”);,return ERROR;,return OK;,时间复杂度分析,时间主要耗费在数据元素的比较和移动操作上。,首先，,在线性表,L,中查找值为,x,的,结点是否存在,;,其次，若,值为,x,的,结点存在，且在,线性表,L,中的位置为,i,，则在,线性表,L,中删除,第,i,个,元素。,设,在线性表,L,删除,数据元素概率为,P,i,，不失一般性，设各个位置是等概率，则,P,i,=1/n,。,比较的平均次数,：,E,compare,=,p,i,*i,(1in),E,compare,=(n+1)/2,。,删除时平均移动次数,：,E,delete,=,p,i,*(n-i),(1in),E,delete,=(n-1)/2,。,平均时间复杂度：,E,compare,+,E,delete,=n,，,即为,O(n),2.3,线性表的链式存储,2.3.1,线性表的链式存储结构,链式存储,：,用,一组任意的存储单元存储,线性表中的数据元素。用这种方法存储的线性表简称,线性链表,。,存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。,链表中结点的逻辑顺序和物理顺序不一定相同。,为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的地址,(,或位置,),，称为指针,(pointer),或链,(link),，这两部分组成了链表中的结点结构，如图,2-2,所示。,链表是通过每个结点的指针域将线性表的,n,个结点按其逻辑次序链接在一起的。,每一个结只包含一个指针域的链表，称为单链表。,为操作方便，总是在链表的第一个结点之前附设一个头结点,(,头指针,),head,指向第一个结点。头结点的数据域可以不存储任何信息,(,或链表长度等信息,),。,data next,图,2-2,链表结点结构,data,：数据域，存放结点的值。,next,：指针域，存放结点的直接后继的地址。,3695,head,fat,1100,bat,1300,cat,1305,eat,3700,hat,NULL,1100,3700,1300,1305,bat,cat,eat,fat,hat ,head,图,2-3,带头结点的单链表的逻辑状态、物理存储方式,单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。,例,1,、线性表,L=(bat,，,cat,，,eat,，,fat,，,hat),其带头结点的单链表的逻辑状态和物理存储方式如图,2-3,所示。,1,结点的描述与实现,C,语言中用,带指针的结构体类型,来描述,typedef struct Lnode,ElemType data;,/*,数据域，保存结点的值*,/,struct Lnode *next;,/*,指针域*,/,LNode;,/*,结点的类型*,/,2,结点的实现,结点是通过动态分配和释放来的实现,，即需要时分配，不需要时释放。实现时是分别使用,C,语言提供的标准函数：,malloc(),，,realloc(),，,sizeof(),，,free(),。,动态分配,p=(LNode*)malloc(sizeof(LNode);,函数,malloc,分配了一个类型为,LNode,的结点变量的空间，并将其首地址放入指针变量,p,中。,动态释放,free(p);,系统回收由指针变量,p,所指向的内存区。,P,必须是最近一次调用,malloc,函数时的返回值。,3,最常用的基本操作及其示意图,结点的赋值,LNode *p;,p=(LNode*)malloc(sizeof(LNode);,p-data=20;p-next=NULL;,p,20,NULL,常见的指针操作,q=p,;,p,a,操作前,p,a,q,操作后,q=p-next,;,b,p,a,操作前,操作后,q,b,p,a,p=p-next,;,b,p,a,操作前,操作后,p,b,a,q-next=p,;,c,p,b,q,a,操作前,操作后,q,b,a,c,p,(a),q-next=p-next,;,(a),x,y,p,b,q,a,操作前,操作后,q,b,a,x,y,p,操作前,y,p,x,b,q,a,操作后,y,p,x,b,q,a,(b),操作前,y,p,x,b,q,a,操作后,y,p,x,b,q,a,(b),2.3.2,单线性链式的基本操作,1,建立单链表,假设线性表中结点的数据类型是整型，以,32767,作为结束标志。动态地建立单链表的常用方法有如下两种：,头插入法,，,尾插入法,。,头插入法建表,从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。即,每次插入的结点都作为链表的第一个结点,。,算法描述,LNode *create_LinkList(void),/*,头插入法创建单链表,链表的头结点,head,作为返回值 *,/,int data;,LNode*head,*p;,head=(LNode *)malloc(sizeof(LNode);,head-next=NULL;,/*,创建链表的表头结点,head */,while(1),scanf(“%d”,if(data=32767)break;,p=(LNode *)malloc(sizeof(LNode);,pdata=data;,/*,数据域赋值 *,/,pnext=headnext;headnext=p;,/*,钩链,，新创建,的结点总是作为第一个结点 *,/,return(head);,(2),尾插入法建表,头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将,新结点插入到当前链表的表尾，使其成为当前链表的尾结点,。,算法描述,LNode *create_LinkList(void),/*,尾插入法创建单链表,链表的头结点,head,作为返回值,*,/,int data;,LNode*head,*p,*q;,head=p=(LNode *)malloc(sizeof(LNode);,p-next=NULL;,/*,创建单链表的表头结点,head */,while(1),scanf(“%d”,if(data=32767)break;,q=(LNode *)malloc(sizeof(LNode);,qdata=data;,/*,数据域赋值 *,/,qnext=pnext;pnext=q;p=q;,/*,钩链,，新创建,的结点总是作为最后一个结点*,/,return(head);,无论是哪种插入方法，如果要插入建立的单线性链表的结点是,n,个，算法的时间复杂度均为,O(n),。,对于单链表，无论是哪种操作，只要涉及到钩链,(,或重新钩链,),，如果,没有明确给出直接后继,，钩链,(,或重新钩链,),的次序必须是,“,先右后左,”,。,2,单链表的查找,(,1),按序号查找,取单链表中的第,i,个元素。,对于单链表，不能象顺序表中那样直接按序号,i,访问结点，而只能从链表的头结点出发，沿链域,next,逐个结点往下搜索，直到搜索到第,i,个结点为止。因此，,链表不是随机存取结构,。,设单链表的长度为,n,，要查找表中第,i,个结点，仅当,1in,时，,i,的值是合法的。,算法描述,ElemType Get_Elem(LNode*L,，,int i),int j;LNode*p;,p=L-next;j=1;,/*,使,p,指向第一个结点 *,/,while (p!=NULL&jnext;j+;,/*,移动指针,p,j,计数 *,/,if (j!=i)return(-32768);,else return(p-data);,/*p,为,NULL,表示,i,太大,;ji,表示,i,为,0 */,移动指针,p,的频度：,in,：,n,次。,时间复杂度,:,O(n),。,(2),按值查找,按值查找是在链表中，查找是否有结点值等于给定值,key,的结点,?,若有，则返回首次找到的值为,key,的结点的存储位置；否则返回,NULL,。查找时从开始结点出发，沿链表逐个将结点的值和给定值,key,作比较。,算法描述,LNode,*Locate_Node(LNode*L,，,int key),/*,在以,L,为头结点的单链表中查找值为,key,的第一个结点 *,/,LNode*p=Lnext;,while (p!=NULL,if (pdata=key)return p;,else,printf(“,所要查找的结点不存在,!n”);,retutn(NULL);,算法的执行与形参,key,有关，平均时间复杂度为,O(n),。,3,单链表的插入,插入运算是将值为,e,的新结点插入到表的第,i,个结点的位置上，即插入到,a,i-1,与,a,i,之间。因此，必须首先找到,a,i-1,所在,的结点,p,，然后生成一个数据域为,e,的新结点,q,，,q,结点作为,p,的直接后继结点。,算法描述,void Insert_LNode(LNode*L,，,int i,，,ElemType e),/*,在以,L,为头结点的单链表的第,i,个位置插入值为,e,的结点*,/,int j=0;LNode*p,，*,q;,p=Lnext;,while (p!=NULL&jnext;j+;,if (j!=i-1)printf(“i,太大或,i,为,0!n”);,else,q=(LNode*)malloc(sizeof(LNode);,qdata=e;qnext=pnext;,pnext=q;,设链表的长度为,n,，合法的插入位置是,1in,。算法的时间主要耗费,移动指针,p,上，故时间复杂度亦为,O(n),。,4,单链表的删除,按序号删除,删除单链表中的第,i,个结点。,为了删除第,i,个结点,a,i,，必须找到结点的存储地址。该存储地址是在其直接前趋结点,a,i-1,的,next,域中，因此，必须首先找到,a,i-1,的存储位置,p,，然后令,pnext,指向,a,i,的直接后继结点，即把,a,i,从链上摘下。最后释放结点,a,i,的空间，将其归还给,“,存储池,”,。,设单链表长度为,n,，则删去第,i,个结点仅