数据结构教程（第3版）一ppt.ppt

数据结构教程（第3版）一,第1章 绪论,1.2 算法及其描述,1.1 什么是数据结构,1.3 算法分析,本章小结,1.4 数据结构算法程序,1.1.1 数据结构的定义,1.1.2 逻辑结构类型,1.1.3 存储结构类型,1.1.4 数据结构和数据类型,1.1 什么是数据结构,数据：是所有能被输入到计算机中,且能被计算机处理的符号的集合。它是计算机操作的对象的总称,也是计算机处理的信息的某种特定的符号表示形式。,数据元素：是数据(集合)中的一个“个体”,是数据的基本单位。,1.1.1 数据结构的定义,数据对象：是具有相同性质的若干个数据元素的集合。,例如,200402班为一个学生数据对象,而其中的“张三”是一个数据元素)。,数据结构：是指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据元素的集合。 因此,可时把数据结构看成是带结构的数据元素的集合。,数据结构包括如下几个方面： (1) 数据元素之间的逻辑关系,即数据的逻辑结构。 (2) 数据元素及其关系在计算机存储器中的存储方式,即数据的存储结构,也称为数据的物理结构。 (3) 施加在该数据上的操作,即数据的运算。,例1.1 有一个学生表如表1.1所示。这个表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓别、性别和班号)组成。,表1.1 学生表,该表中的记录顺序反映了数据元素之间的逻辑关系, 用学号标识每个学生记录,这种逻辑关系可以表示为： , 其中尖括号“”表示元素ai和ai+1之间是相邻的,即ai在ai+1之前,ai+1在ai之后。,数据在计算机存储器中的存储方式就是存储结构。 C/C+语言中，通常采用结构体数组和链表两种方式实现其存储结构。,存放学生表的结构体数组Stud定义为： struct int no; /*存储学号*/ char name8; /*存储姓名*/ char sex2; /*存储性别*/ char class4; /*存储班号*/ Stud7=1,“张斌”,“男”,“9901”, 5,“王萍“,“女“,“9901“;,结构体数组Stud各元素在内存中顺序存放,即第i(1i6)个学生对应的元素Studi存放在第i+1个学生对应的元素Studi+1之前,Studi+1正好在Studi之后。,存放学生表的链表的结点类型StudType定义为： typedef struct studnode int no; /*存储学号*/ char name8; /*存储姓名*/ char sex2; /*存储性别*/ char class4; /*存储班号*/ struct studnode *next; /*存储指向下一个学生的指针*/ StudType；,链表首结点地址head,1,张斌,男,9901,8,刘丽,女,9902,34,李英,女,9901,20,陈华,男,9902,12,王奇,男,9901,26,董强,男,9902,5,王萍,女,9901,学生表构成的链表如右图所示。其中的head为第一个数据元素的指针。,学生表构成的链表,对于“学生表”这种数据结构,可以进行一系列的运算,例如,增加一个学生记录、删除一个学生记录、查找性别为“女”的学生记录、查找班号为“9902”的学生记录等等。 从前面介绍的两种存储结构看到,同样的运算,在不同的存储结构中,其实现过程是不同的。,例如,查找学号为20的学生的姓名： 对于Stud数组,可以从Stud0开始比较,Stud0.no不等于20,再与Stud1.no比较,直到Stud3.no等于20,返回S。 对于head为首结点指针的链表,从head所指结点开始比较,head-no不等于20,从它的next得到下一个结点的地址,再与下一个结点的no域比较,直到某结点的no域等于20,返回其name域。,为了更确切地描述一种数据结构,通常采用二元组表示： B=(K,R) 其中,B是一种数据结构,它由数据元素的集合K和K上二元关系的集合R所组成。其中： K=ki| 1in,n0 R=rj| 1jm,m0,逻辑结构的描述或表示：,其中： ki表示集合K中的第i个结点或数据元素。 n为K中结点的个数,特别地,若n=0,则K是一个空集,因而B也就无结构可言,有时也可以认为它具有任一结构。 rj表示集合R中的第j个二元关系(后面均简称关系)。 m为R中关系的个数,特别地,若m=0,则R是一个空集,表明集合K中的元结点间不存在任何关系,彼此是独立的。,序偶(x,yK) x为第一结点,y为第二结点。 x为y的直接前驱结点(通常简称前驱结点) y为x的直接后继结点(通常简称后继结点)。 若某个结点没有前驱结点,则称该结点为开始结点；若某个结点没有后继结点,则称该结点为终端结点。,说明：表示有向关系，(x,y)表示无向关系。采用离散数学的表示方法。,例如,采用二元组表示例1.1的学生表。 学生表中共有7个结点,依次用k1k7表示,则对应的二元组表示为B=(K,R),其中： K=k1,k2,k3,k4,k5,k6,k7 R=r /只有一种关系 r=,又例如,有如下数据即一个矩阵：,对应的二元组表示为B=(K,R),其中： K=2,6,3,1,8,12,7,4,5,10,9,11 R=r1,r2 其中,r1表示行关系,r2表示列关系 r1=, , r2=, , ,一个二维数组,可以利用图形形象地表示逻辑结构。 例如，上述“学生表”数据结构用下图的图形表示。,学生表数据结构图示,(1) 线性结构 结点之间关系：一对一。 特点：开始结点和终端结点都是惟一的,除了开始结点和终端结点以外,其余结点都有且仅有一个前驱结点,有且仅有一个后继结点。顺序表就是典型的线性结构。,1.1.2 逻辑结构类型,(2) 树形结构 结点之间关系：一对多。 特点：开始结点惟一,终端结点不惟一。除终端结点以外,每个结点有一个或多个后续结点；除开始结点外，每个结点有且仅有一个前驱结点。,(3) 图形结构 结点之间关系：多对多。 特点：没有开始结点和终端结点，所有结点都可能有多个前驱结点和多个后继结点。,(2) 链式存储方法,(3) 索引存储方法,(4) 散列存储方法,1.1.3 存储结构类型,(1) 顺序存储方法,(1) 数据类型 高级程序语言中,一般须对程序中出现的每个变量、常量或表达式,明确说明它们所属的数据类型。不同类型的变量,其所能取的值的范围不同,所能进行的操作不同。 数据类型是一个值的集合和定义在此集合上的一组操作的总称。,1.1.4 数据结构和数据类型,如C/C+中的int就是整型数据类型。它是所有整数的集合(在16位计算机中为3276832767的全体整数)和相关的整数运算(如、等)。,(2) 抽象数据类型 抽象数据类型(Abstract Data Type简写为ADT)指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算,而不考虑计算机的具体存储结构和运算的具体实现算法。 抽象数据类型=数据元素集合抽象运算,例如,抽象数据类型复数的定义： ADT Complex 数据对象： D=e1,e2|e1,e2均为实数 数据关系： R1=| e1是复数的实数部分,e2 是复数的 虚数部分 ,e1e2i,基本操作： AssignComplex(&Z,v1,v2)：构造复数Z。 DestroyComplex(&Z):复数Z被销毁。 GetReal(Z,&real):返回复数Z的实部值。 GetImag(Z,&Imag):返回复数Z的虚部值。 Add(z1,z2,&sum):返回两个复数z1,z2的和。 ADT Complex,1.2 算法及其描述,1.2.1 什么是算法,1.2.2 算法描述,1.2.1 什么是算法 数据元素之间的关系有逻辑关系和物理关系,对应的操作有逻辑结构上的操作功能和具体存储结构上的操作实现。 通常把具体存储结构上的操作实现步骤或过程称为算法。,算法的五个重要的特性,(1) 有穷性:在有穷步之后结束。,(2) 确定性:无二义性。,(3) 可行性:可通过基本运算有限次执行来实现。,(4) 有输入,(5) 有输出,例1.2 考虑下列两段描述： (1) 描述一 void exam1() n2; while (n%20) nn+2; printf(“%dn“,n); ,华中科大考研题,(2) 描述二 void exam2() y=0; x=5/y; printf(“%d,%dn”,x,y); 这两段描述均不能满足算法的特征,试问它们违反了哪些特征？,解：(1)算法是一个死循环,违反了算法的有穷性特征。 (2)算法包含除零错误,违反了算法的可行性特征。,1.2.2 算法描述,本书中采用C/C+语言描述算法。 说明：C+语言中提供了一种引用运算符“&”,引用是个别名,当建立引用时,程序用另一个已定义的变量或对象(目标)的名字初始化它,从那时起,引用作为目标的别名而使用,对引用的改动实际就是对目标的改动。 注意：Turbo C不支持引用类型。,编写一个函数swap1(x,y)，当执行语句swap1(a,b)时,交换a和b的值。 void swap1(int x,int y) int tmp; tmp=x;x=y;y=tmp; 注意：a和b的值不会发生了交换。,为此，采用指针的方式来回传形参的值，需将上述函数改为： void swap2(int *x,int *y) int tmp; tmp=*x; /*将x的值放在tmp中*/ *x=*y; /*将x所指的值改为*y*/ *y=tmp； /*将y所指的值改为tmp*/ 上述函数的调用改为swap2(&a,&b)，显然远不如采用引用方式简洁。所以本书后面很多算法都采用引用形参。,引入“引用”的概念 例如： int a=4; /*a为普通的整型变量*/ int /*b是a的引用变量*/ 这里说明b变量是变量a的引用,b也等于4,之后这两个变量同步改变。当a改变时b也同步改变，同样，当b改变时a也同步改变。,难点,main() int a=2; int /*输出：a=4,b=4*/ ,引用常用于函数形参中,采用引用型形参时,在函数调用时将形参的改变回传给实参,例如,有如下函数(其中的形参均为引用型形参)： void swap(int y=tmp 当用执行语句swap(a,b)时,a和b的值发生了交换。,例1.3 编写一个算法, 读入三个整数x,y和z的值,要求从大到小输出这三个数。 解：依次输入x,y和z这三个整数,通过比较交换后,使得xyz,然后输出x,y,z。 在算法中应考虑对这三个元素作尽可能少的比较和移动,如下述算法在最坏的情况下只需进行3次比较和7次移动。,void Descending() printf(“输入x,y,z“); scanf(“%d,%d,%d“, ,1.3 算法分析,1.3.1 算法时间复杂度分析,1.3.2 算法空间复杂度分析,一个算法是由控制结构(顺序、分支和循环三种)和原操作(指固有数据类型的操作)构成的,则算法时间取决于两者的综合效果。,1.3.1 算法时间复杂度分析,控制语句1 原操作,控制语句n 原操作,一个算法,同一问题可以采用多种算法实现。如何比较算法执行效率？ 算法描述的语言不同 算法执行的环境不同 其他因素 所以不能用绝对执行时间进行比较,为了便于比较同一问题的不同算法,通常从算法中选取一种对于所研究的问题来说是基本运算的原操作(以下将基本运算的原操作简称为基本运算)。 算法执行时间大致为基本运算所需的时间与其运算次数(也称为频度)的乘积。 被视为算法基本运算的一般是最深层循环内的语句。,在一个算法中,进行基本运算的次数越少,其运行时间也就相对地越少；基本运算次数越多,其运行时间也就相对地越多。 所以,通常把算法中包含基本运算次数的多少称为算法的时间复杂度,也就是说,一个算法的时间复杂度是指该算法的基本运算次数。 算法中基本运算次数T(n)是问题规模n的某个函数f(n),记作： T(n)=O(f(n),记号“O”读作“大O”,它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。“O”的形式定义为： 若f(n)是正整数n的一个函数,则T(n)=O(f(n)表示存在一个正的常数M,使得当nn0时都满足： |T(n)|M|f(n)|,也就是只求出T(n)的最高阶,忽略其低阶项和常系数,这样既可简化T(n)的计算,又能比较客观地反映出当n很大时,算法的时间性能。 例如,T(n)=3n2-5n+10000=O(n2),本质上讲，是一种最高数量级的比较,一个没有循环的算法的基本运算次数与问题规模n无关,记作O(1),也称作常数阶。 一个只有一重循环的算法的基本运算次数与问题规模n的增长呈线性增大关系,记作O(n),也称线性阶。 其余常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。,各种不同数量级对应的值存在着如下关系： O(1)O(log2n)O(n)O(n*log2n)O(n2) O(n3)O(2n)O(n!),例1.4 求两个n阶方阵的相加C=A+B的算法如下,分析其时间复杂度。 #define MAX 20 /*定义最大的方阶*/ void matrixadd(int n,int AMAXMAX, int BMAXMAX,int CMAXMAX) int i,j; for (i=0;in;i+) for (j=0;jn;j+) Cij=Aij+Bij; ,该算法中的基本运算是两重循环中最深层的语句Cij=Aij+Bij,分析它的频度,即： T(n)= =O(n2),例1.5 分析以下算法的时间复杂度。 int fun(int n) int i,j,k,s; s=0; for (i=0;i=n;i+) for (j=0;j=i;j+) for (k=0;k=j;k+) s+; return(s); ,基本语句或基本操作,解：该算法的基本操作是语句s+,其频度： T(n)= =O(n3) 则该算法的时间复杂度为O(n3)。,例1.6 分析以下算法的时间复杂度。 void func(int n) int i=0,s=0; while (sn) i+; s=s+i; ,基本语句,解：对于while循环语句，设执行的次数为m，i从0开始递增1，直到m为止，有： s=0+1+2+m-1=m(m-1)/2， 并满足s=m(m-1)/2n，则有m 。 T(n)=O( ) 所以，该算法的时间复杂度为O( )。,例1.7 有如下算法： void fun(int a,int n,int k) /*数组a共有n个元素*/ int i; if (k=n-1) for (i=0;in;i+) printf(“%dn“,ai); else for (i=k;in;i+) ai=ai+i*i; fun(a,n,k+1); 调用上述算法的语句为fun(a,n,0)，求其时间复杂度。,解：设fun(a,n,0)的时间复杂度为T(n),则fun(a,n,k)的执行时间为T1(n,k)，由fun()算法可知： T1(n,k)=n 当k=n-1时 T1(n,k)= (n-k)+T1(n,k+1) 其他情况 则 T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2) =n+(n-1)+2+T1(n,n-1) =n+(n-1)+ +2+n =O(n2) 所以调用fun(a,n,0)的时间复杂度为O(n2)。,空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度,一般也作为问题规模n的函数,以数量级形式给出,记作： S(n) = O(g(n) 若所需额外空间相对于输入数据量来说是常数,则称此算法为原地工作。若所需存储量依赖于特定的输入,则通常按最坏情况考虑。,1.3.2 算法空间复杂度分析,返回,例1.8 分析例1.4和例1.5的空间复杂度。 解：由于这两个算法中临时变量的个数与问题规模n无关,所以空间复杂度均为O(1)。,1.4 数据结构算法程序,数据结构对算法的影响主要在两方面 （1）数据结构的存储能力 数据结构存储能力强、存储信息多算法将会较好设计（时间少），存储空间大。 时间和空间的平衡 （2）定义在数据结构上的操作 在数据结构上定义基本操作算法调用这些基本操作。,基本操作越完整，算法设计就越容易,算法,基本操作,基本算法,应用程序,应用程序是通过调用基本算法实现的,选择数据结构需要考虑的几个方面： （1）数据结构要适应问题的状态描述 （2）数据结构应与所选择的算法相适应 （3）数据结构的选择同时要兼顾程序设计的方便 （4）灵活应用已有知识,例如，有若干学生数据（学生数小于50），每个学生数据包含学号（每个学生学号是惟一的，但学生记录不一定按学号顺序存放）、姓名、班号和若干门课程成绩（每个学生所选课程数目可能不等，但最多不超过6门）。 要求设计一个程序输出每个学生的学号、姓名和平均分以及每门课程（课程编号从16）的平均分。,设计方案1：将学生的全部数据项放在一个表中，一个学生的全部数据对应一条记录。由于课程最多可选6门，对应的成绩项也应有6个。对应的数据结构如下： struct stud int no; /*学号*/ char name10; /*姓名*/ int bno; /*班号*/ int deg1; /*课程1分数*/ int deg2; /*课程2分数*/ int deg3; /*课程3分数*/ int deg4; /*课程4分数*/ int deg5; /*课程5分数*/ int deg6; /*课程6分数*/ ;,特点： 存储空间：中（若学生没有选该课程，对应空间仍存在） 算法时间：少 算法简洁性差：算法完全依赖数据结构,设计方案2：将学生的全部数据项放在一个表中，但一个学生的一门课程成绩对应一条记录。这样成绩项只需要一个，为了区分不同课程成绩，需增加一个课程编号项。对应的数据结构如下： struct stud int no; /*学号*/ char name10; /*姓名*/ int bno; /*班号*/ int cno; /*课程编号*/ int deg; /*课程分数*/ ;,特点： 存储空间：大 算法时间：多 算法简洁性：好,设计方案3：将学生的学号、姓名和班号放在一个表中，将成绩数据放在另一个表中，两者通过学号关联。前者一个学生对应一个记录，后者一门课程成绩对应一条记录。对应的数据结构如下： struct stud1 int no; /*学号*/ char name10; /*姓名*/ int bno; /*班号*/ ; struct stud2 int no; /*学号*/ int cno; /*课程编号*/ int deg; /*分数*/ ;,特点： 存储空间：少 算法时间：中 算法简洁性：好,数据结构,算法,数据类型,i,j,k,求解问题编写程序的代码：ijk种,优 选,最佳方案,本课程的目标,本章小结 本章介绍了数据结构的基本概念,主要学习要点如下： (1) 数据结构的定义,数据结构包含的逻辑结构、存储结构和运算三方面的相互关系。 (2) 各种逻辑结构即线性结构、树形结构和图形结构之间的差别。,(3) 数据结构和数据类型的差别和联系。 (4) 算法的定义及其特性。 (5) 算法的时间复杂度和空间复杂度分析。,练习题1： 习题3、习题5和习题6。 上机题： 熟悉VC+6.0环境,第2章 线性表,2.1 线性表的基本概念,2.2 线性表的顺序存储,2.3 线性表的链式存储,2.4 线性表的应用,本章小结,2.5 有序表,2.1 线性表的基本概念,2.1.1 线性表的定义,2.1.2 线性表的运算,2.1.1 线性表的定义 线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用n表示,n0。 当n=0时,表示线性表是一个空表,即表中不包含任何元素。设序列中第i(i表示位序)个元素为ai(1in)。 线性表的一般表示为: (a1,a2,ai,ai+1,an),其中a1为第一个元素,又称做表头元素,a2为第二个元素,an为最后一个元素,又称做表尾元素。 例如,在线性表 (1,4,3,2,8,10) 中,1为表头元素,10为表尾元素。,2.1.2 线性表的运算 线性表的基本运算如下: (1) 初始化线性表InitList(&L):构造一个空的线性表L。 (2) 销毁线性表DestroyList(&L):释放线性表L占用的内存空间。,(3) 判线性表是否为空表ListEmpty(L):若L为空表,则返回真,否则返回假。 (4) 求线性表的长度ListLength(L):返回L中元素个数。 (5) 输出线性表DispList(L):当线性表L不为空时,顺序显示L中各结点的值域。 (6) 求线性表L中指定位置的某个数据元素GetElem(L,i,&e):用e返回L中第 i(1iListLength(L)个元素的值。,(7) 定位查找LocateElem(L,e):返回L中第1个值域与e相等的位序。若这样的元素不存在,则返回值为0。 (8) 插入数据元素ListInsert(&L,i,e):在L的第i(1iListLength(L)+1)个元素之前插入新的元素e,L的长度增1。 (9) 删除数据元素ListDelete(&L,i,&e):删除L的第i(1iListLength(L)个元素,并用e返回其值,L的长度减1。,例2.1 假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示,即线性表中的数据元素即为集合中的成员。编写一个算法求一个新的集合C=AB,即将两个集合的并集放在线性表LC中。 解:本算法思想是:先初始化线性表LC,将LA的所有元素复制到LC中,然后扫描线性表LB,若LB的当前元素不在线性表LA中,则将其插入到LC中。算法如下:,void unionList(List LA,List LB,List ,for (i=1;i=lenb;i+) GetElem(LB,i,e); /*取LB中第i个数据元素赋给e*/ if (!LocateElem(LA,e) ListInsert(LC,+lenc,e); /*LA中不存在和e相同者,则插入到LC中*/ ,由于LocateElem(LA,e)运算的时间复杂度为O(ListLength(LA),所以本算法的时间复杂度为: O(ListLength(LA)*ListLength(LB)。,2.2 线性表的顺序存储,2.2.1 线性表的顺序存储顺序表,2.2.2 顺序表基本运算的实现,2.2.1 线性表的顺序存储顺序表 线性表的顺序存储结构就是:把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。 这样,线性表中第一个元素的存储位置就是指定的存储位置,第i+1个元素(1in-1)的存储位置紧接在第i个元素的存储位置的后面。 线性表 逻辑结构 顺序表 存储结构,假定线性表的元素类型为ElemType,则每个元素所占用存储空间大小(即字节数)为sizeof(ElemType),整个线性表所占用存储空间的大小为: n*sizeof(ElemType) 其中,n表示线性表的长度。,顺序表示意图,在定义一个线性表的顺序存储类型时,需要定义一个数组来存储线线表中的所有元素和定义一个整型变量来存储线性表的长度。 假定数组用dataMaxSize表示,长度整型变量用length表示,并采用结构体类型表示,则元素类型为通用类型标识符ElemType的线性表的顺序存储类型可描述如下:,typedef struct ElemType dataMaxSize; int length; SqList; /*顺序表类型*/ 其中,data成员存放元素,length成员存放线性表的实际长度。 说明：由于C/C+中数组的下标从0开始，线性表的第i个元素ai存放顺序表的第i-1位置上。为了清楚，将ai在逻辑序列中的位置称为逻辑位序，在顺序表中的位置称为物理位序。,2.2.2 顺序表基本运算的实现,一旦采用顺序表存储结构,我们就可以用C/C+语言实现线性表的各种基本运算。为了方便,假设ElemType为char类型,使用如下自定义类型语句: typedef char ElemType;,1. 建立顺序表 其方法是将给定的含有n个元素的数组的每个元素依次放入到顺序表中，并将n赋给顺序表的长度成员。算法如下： void CreateList(SqList * ,2. 顺序表基本运算算法 (1) 初始化线性表InitList(L) 该运算的结果是构造一个空的线性表L。实际上只需将length成员设置为0即可。 void InitList(SqList * 本算法的时间复杂度为O(1)。,顺序表,L,(2) 销毁线性表DestroyList(L) 该运算的结果是释放线性表L占用的内存空间。 void DestroyList(SqList * 本算法的时间复杂度为O(1)。,(3) 判定是否为空表ListEmpty(L) 该运算返回一个值表示L是否为空表。若L为空表,则返回1,否则返回0。 int ListEmpty(SqList *L) return(L-length=0); 本算法的时间复杂度为O(1)。,(4) 求线性表的长度ListLength(L) 该运算返回顺序表L的长度。实际上只需返回length成员的值即可。 int ListLength(SqList *L) return(L-length); 本算法的时间复杂度为O(1)。,(5) 输出线性表DispList(L) 该运算当线性表L不为空时,顺序显示L中各元素的值。 void DispList(SqList *L) int i; if (ListEmpty(L) return; for (i=0;ilength;i+) printf(“%c“,L-datai); printf(“n“); ,本算法中基本运算为for循环中的printf语句,故时间复杂度为: O(L-length)或O(n),(6) 求某个数据元素值GetElem(L,i,e) 该运算返回L中第 i(1iListLength(L)个元素的值,存放在e中。 int GetElem(SqList *L,int i,ElemType 本算法的时间复杂度为O(1)。,(7) 按元素值查找LocateElem(L,e) 该运算顺序查找第1个值域与e相等的元素的位序。若这样的元素不存在,则返回值为0。 int LocateElem(SqList *L, ElemType e) int i=0; while (ilength ,本算法中基本运算为while循环中的i+语句,故时间复杂度为: O(L-length)或O(n),(8) 插入数据元素ListInsert(L,i,e) 该运算在顺序表L的第i个位置(1iListLength(L)+1)上插入新的元素e。 思路：如果i值不正确,则显示相应错误信息；否则将顺序表原来第i个元素及以后元素均后移一个位置,腾出一个空位置插入新元素,顺序表长度增1。,int ListInsert(SqList * ,逻辑位序 1 i i+1 n MaxSize,对于本算法来说,元素移动的次数不仅与表长L.length=n有关,而且与插入位置i有关:当i=n+1时,移动次数为0；当i=1时,移动次数为n,达到最大值。在线性表sq中共有n+1个可以插入元素的地方。假设pi(= )是在第i个位置上插入一个元素的概率,则在长度为n的线性表中插入一个元素时所需移动元素的平均次数为: 因此插入算法的平均时间复杂度为O(n)。,(9) 删除数据元素ListDelete(L,i,e) 删除顺序表L中的第i(1iListLength(L)个元素。 思路：如果i值不正确,则显示相应错误信息；否则将线性表第i个元素以后元素均向前移动一个位置,这样覆盖了原来的第i个元素,达到删除该元素的目的,最后顺序表长度减1。,int ListDelete(SqList * ,逻辑位序 1 i i+1 n MaxSize,对于本算法来说,元素移动的次数也与表长n和删除元素的位置i有关:当i=n时,移动次数为0；当i=1时,移动次数为n-1。在线性表sq中共有n个元素可以被删除。假设pi(pi= )是删除第i个位置上元素的概率,则在长度为n的线性表中删除一个元素时所需移动元素的平均次数为: = 因此删除算法的平均时间复杂度为O(n)。,例2.2 设计一个算法,将x插入到一个有序(从小到大排序)的线性表(顺序存储结构即顺序表)的适当位置上,并保持线性表的有序性。 解:先通过比较在顺序表L中找到存放x的位置i,然后将x插入到L.datai中,最后将顺序表的长度增1。,void Insert(SqList * ,查找插入位置,元素后移一个位置,逻辑位序 1 i i+1 n MaxSize,例2.3 设计一个算法,将两个元素有序(从小到大)的顺序表合并成一个有序顺序表。 求解思路:将两个顺序表进行二路归并。,归并到顺序表r中 k记录r中元素个数 1(i=0) 2(j=0) 将1(i=1)插入r(k=1) 3(i=1) 2(j=0) 将2(j=1)插入r(k=2) 3(i=1) 4(j=1) 将3(i=2)插入r(k=3) 5(i=2) 4(j=1) 将4(j=2)插入r(k=4) 5(i=2) 10(j=2) 将5(j=3)插入r(k=5) 将q中余下元素插入r中。,顺序表p：1 3 5,i,顺序表q：2 4 10 20,j,顺序表r：1,k,SqList *merge(SqList *p, SqList *q) SqList *r; int i=0,j=0,k=0; r=(SqList *)malloc(sizeof(SqList); while (ilength ,while (ilength) r-datak=p-datai; i+;k+; while (jlength) r-datak=q-dataj; j+;k+; r-length=k; /*或p-length+q-length*/ return(r); ,例2.4 已知长度为n的线性表A采用顺序存储结构,编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素。 解:用k记录顺序表A中等于item的元素个数,边扫描A边统计k,并将不为item的元素前移k个位置,最后修改A的长度。对应的算法如下:,void delnode1(SqList /*顺序表A的长度等于k*/ ,算法1：类似于建顺序表,void delnode2(SqList /*顺序表A的长度递减*/ ,算法2,上述算法中只有一个while循环,时间复杂度为O(n)。算法中只用了i,k两个临时变量,空间复杂度为O(1)。,2.3 线性表的链式存储,2.3.1 线性表的链式存储链表,2.3.2 单链表基本运算的实现,2.3.3 双链表,2.3.4 循环链表,2.3.5 静态链表,2.3.1 线性表的链式存储链表 在链式存储中,每个存储结点不仅包含有所存元素本身的信息(称之为数据域),而且包含有元素之间逻辑关系的信息,即前驱结点包含有后继结点的地址信息,这称为指针域,这样可以通过前驱结点的指针域方便地找到后继结点的位置,提高数据查找速度。 一般地,每个结点有一个或多个这样的指针域。若一个结点中的某个指针域不需要任何结点,则仅它的值为空,用常量NULL表示。,由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素,即数据元素之间是一对一的逻辑关系,所以当进行链式存储时,一种最简单也最常用的方法是: 在每个结点中除包含有数据域外,只设置一个指针域,用以指向其后继结点,这样构成的链接表称为线性单向链接表,简称单链表；,带头结点单链表示意图,在线性表的链式存储中,为了便于插入和删除算法的实现,每个链表带有一个头结点,并通过头结点的指针惟一标识该链表。,在单链表中,由于每个结点只包含有一个指向后继结点的指针,所以当访问过一个结点后,只能接着访问它的后继结点,而无法访问它的前驱结点。,另一种可以采用的方法是:在每个结点中除包含有数值域外,设置有两个指针域,分别用以指向其前驱结点和后继结点,这样构成的链接表称之为线性双向链接表,简称双链表。,带头结点的双链表示意图,在双链表中,由于每个结点既包含有一个指向后继结点的指针,又包含有一个指向前驱结点的指针,所以当访问过一个结点后,既可以依次向后访问每一个结点,也可以依次向前访问每一个结点。,双链表的特点,在单链表中,假定每个结点类型用LinkList表示,它应包括存储元素的数据域,这里用data表示,其类型用通用类型标识符ElemType表示,还包括存储后继元素位置的指针域,这里用next表示。 LinkList类型的定义如下: typedef struct LNode /*定义单链表结点类型*/ ElemType data; struct LNode *next; /*指向后继结点*/ LinkList;,2.3.2 单链表基本运算的实现,1. 建立单链表 先考虑如何建立单链表。假设我们通过一个含有n个数据的数组来建立单链表。建立单链表的常用方法有如下两种: (1) 头插法建表 该方法从一个空表开始,读取字符数组a中的字符,生成新结点,将读取的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止。采用头插法建表的算法如下:,void CreateListF(LinkList * ,i=0,i=1,i=2,i=3,head,采用头插法建立单链表的过程,head,head,head,head,第1步:建头结点,第2步:i0,新建a结点,插入到头结点之后,第3步:i1,新建d结点,插入到头结点之后,第4步:i2,新建c结点,插入到头结点之后,第5步:i3,新建b结点,插入到头结点之后,(2) 尾插法建表 头插法建立链表虽然算法简单,但生成的链表中结点的次序和原数组元素的顺序相反。若希望两者次序一致,可采用尾插法建立。该方法是将新结点插到当前链表的表尾上,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。采用尾插法建表的算法如下:,void CreateListR(LinkList * /*终端结点next域置为NULL*/ ,b,c,d,a,i=0,i=1,i=2,i=3,head,头结点,a,d,c,采用尾插法建立单链表的过程,2. 插入结点运算 插入运算是将值为x的新结点插入到单链表的第i个结点的位置上。先在单链表中找到第i-1个结点,再在其后插入新结点。 单链表插入结点的过程如下图所示。,插入结点示意图,3. 删除结点运算 删除运算是将单链表的第i个结点删去。先在单链表中找到第i-1个结点,再删除其后的结点。删除单链表结点的过程如下图所示。,删除结点示意图,4. 线性表基本运算实现 (1) 初始化线性表InitList(L) 该运算建立一个空的单链表,即创建一个头结点。 void InitList(LinkList * ,(2) 销毁线性表DestroyList(L) 释放单链表L占用的内存空间。即逐一释放全部结点的空间。 void DestroyList(LinkList * ,(3) 判线性表是否为空表ListEmpty(L) 若单链表L没有数据结点,则返回真,否则返回假。 int ListEmpty(LinkList *L) return(L-next=NULL); ,(4) 求线性表的长度ListLength(L) 返回单链表L中数据结点的个数。 int ListLength(LinkList *L) LinkList *p=L;int i=0; while (p-next!=NULL) i+; p=p-next; return(i); ,(5) 输出线性表DispList(L) 逐一扫描单链表L的每个数据结点,并显示各结点的data域值。 void DispList(LinkList *L) LinkList *p=L-next; while (p!=NULL) printf(“%c“,p-data); p=p-next; printf(“n“); ,(6)求线性表L中指定位置的某个数据元素GetElem(L,i,&e) 思路：在单链表L中从头开始找到第 i个结点,若存在第i个数据结点,则将其data域值赋给变量e。,int GetElem(LinkList *L,int i,ElemType ,(7) 按元素值查找LocateElem(L,e) 思路：在单链表L中从头开始找第1个值域与e相等的结点,若存在这样的结点,则返回位置,否则返回0。 int LocateElem(LinkList *L,ElemType e) LinkList *p=L-next;int n=1; while (p!=NULL ,(8) 插入数据元素ListInsert( ,if (p=NULL) return 0; /*未找到位序为i-1的结点*/ else /*找到位序为i-1的结点*p*/ s=(LinkList *)malloc(sizeof(LinkList); /*创建新结点*s*/ s-data=e; s-next=p-next; /*将*s插入到*p之后*/ p-next=s; return 1; ,(9) 删除数据元素ListDelete( ,if (p=NULL) return 0; /*未找到位序为i-1的结点*/ else /*找到位序为i-1的结点*p*/ q=p-next; /*q指向要删除的结点*/ if (q=NULL) return 0; /*若不存在第i个结点,返回0*/ p-next=q-next; /*从单链表中删除*q结点*/ free(q); /*释放*q结点*/ return 1; ,例2.5 设C=a1,b1,a2,b2,an,bn为一线性表,采用带头结点的hc单链表存放,编写一个算法,将其拆分为两个线性表,使得: A=a1,a2,an,B=b1,b2,bn,解: 设拆分后的两个线性表都用带头结点的单链表存放。 先建立两个头结点*ha和*hb,它们用于存放拆分后的线性表A和B,ra和rb分别指向这两个单链表的表尾,用p指针扫描单链表hc,将当前结点*p链到ha未尾,p沿next域下移一个结点,若不为空,则当前结点*p链到hb未尾,p沿next域下移一个结点,如此这样,直到p为空。最后将两个尾结点的next域置空。 对应算法如下:,void fun(LinkList *hc, LinkList * /*rb始终指向hb的末尾结点*/,while (p!=NULL) ra-next=p;ra=p; /*将*p链到ha单链表未尾*/ p=p-next; if (p!=NULL) rb-next=p; rb=p; /*将*p链到hb单链表未尾*/ p=p-next; ra-next=rb-next=NULL; /*两个尾结点的next域置空*/ ,本算法实际上是采用尾插法建立两个新表。所以,尾插法建表算法是很多类似习题的基础！,例2.6 有一个带头结点的单链表head,其ElemType类型为char,设计一个算法使其元素递增有序。 解:若原单链表中有一个或以上的数据结点,先构造只含一个数据结点的有序表(只含一个数据结点的单链表一定是有序表)。扫描原单链表余下的结点*p(直到p=NULL为止),在有序表中通过比较找插入*p的前驱结点*q,然后将*p插入到*q之后(这里实际上采用的是直接插入排序方法)。,void Sort(LinkList * /*r保存*p结点后继结点的指针*/,q=head; while (q-next!=NULL /*扫描原单链表余下的结点*/ ,2.3.3 双链表 对于双链表,采用类似于单链表的类型定义,其DLinkList类型的定义如下: typedef struct DNode /*定义双链表结点类型*/ ElemType data; struct DNode *prior; /*指向前驱结点*/ struct DNode *next; /*指向后继结点*/ DLinkList;,在双链表中,有些操作如求长度、取元素值和查找元素等操作算法与单链表中相应算法是相同的,这里不多讨论。但在单链表中,进行结点插入和删除时涉及到前后结点的一个指针域的变化。而在双链表中,结点的插入和删除操作涉及到前后结点的两个指针域的变化。,双链表中插入结点示意图,归纳起来,在双链表中p所指的结点之后插入一个*s结点。其操作语句描述为: s-next=p-next;/*将*s插入到*p之后*/ p-next-prior=s; s-prior=p; p-next=s;,删除结点示意图,在双链表中删除一个结点的过程如右图所示:,归纳起来,删除双链表L中*p结点的后续结点。其操作语句描述为: p-next=q-next; q-next-prior=p;,2.3.4 循环链表 循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域不再是空,而是指向表头