数据结构与算法课件

大学大学计算机基算机基础 第第6 6章章 数据结构与算法数据结构与算法 程序是什么？程序是什么？程序程序=数据结构数据结构+算法！算法！大学计算机基础第6章数据结构与算法1算法与数据结构一览表 DS算法算法算法定义、特性算法定义、特性算法分析算法分析时间复杂度时间复杂度T(n)空间复杂度空间复杂度D(n)逻辑结构逻辑结构线性结构线性结构树型结构树型结构网状结构网状结构存储结构存储结构链式存储链式存储索引存储索引存储顺序存储顺序存储散列存储散列存储查询查询DS上的运算上的运算插入插入删除删除更新更新算法与数据结构一览表DS算法算法定义、特性算法分析时间复杂例：某校对100个学生进行奖励，学生信息存在磁盘文件“file.dat”中，条件是其三门成绩全部在90分以上才能进行奖励，打印出被奖励学生的学号。o以C语言为例，程序代码如下：#include Void main()struct stu /*数据类型*/int num;float score3;a100;/*定义变量*/FILE *fp；Int I,j;fp=fopen(“file.dat”,”r”);/*打开文件file.dat*/for(i=0;i100;i+)Fread(&ai,sizeof(struct stu),1,fp);/*从文件中读取数据*/for(j=0;j3;j+)if(ai.scorej=3)/*如果符合条件，输出其学号*/printf(“num:%d”,ai.num);Fclose(fp);由此可见，程序包括：对数据的描述，在程序中要指定数据的类型和数据的组织形式。由此可见，程序包括：对数据的描述，在程序中要指定数据的类型和数据的组织形式。对操作的描述，即对数据的操作处理步骤对操作的描述，即对数据的操作处理步骤例：某校对100个学生进行奖励，学生信息存在磁盘文件“fil 第第6 6章章 数据数据结构与算法构与算法数据结构数据结构（data structure）：对数据的描述。即在程序中要指定数据的类型和数据的组织形式。对数据的描述。即在程序中要指定数据的类型和数据的组织形式。算法算法（algorithm）：）：对操作的描述。即对数据的操作处理步骤。对操作的描述。即对数据的操作处理步骤。程序：程序：就是用计算机语言表示的数据结构和算法。就是用计算机语言表示的数据结构和算法。程序设计：程序设计：用计算机语言编写程序的过程。两个基本步骤：用计算机语言编写程序的过程。两个基本步骤：1、设计数据结构和算法。、设计数据结构和算法。2、用一种计算机语言表示出来。、用一种计算机语言表示出来。因此，数据结构与算法是程序设计的基础。因此，数据结构与算法是程序设计的基础。第6章数据结构与算法数据结构（datas6.1 算算 法法 6.1.1 算法的基本概念算法的基本概念 算法算法（algorithm）：）：对操作的描述。即对数据的操作处理对操作的描述。即对数据的操作处理步骤。步骤。算法的表示方法：算法的表示方法：自然语言、流程图、自然语言、流程图、N-S流程图、伪代码、计算机语言流程图、伪代码、计算机语言6.1算法6.1.1算法的基本概念案例：计算sum=1+2+3+n的算法一、用自然语言描述一、用自然语言描述1、输入n，即数据个数；2、设置累加器sum，初始制为0；设置计数器i，初始值为1。3、当i小于或等于n时，做累加，即将sum与i相加，其和再放入sum中。计数器i取下一个数，即i等于i+1，直到i大于n时终止。4、输出累加和sum。案例：计算sum=1+2+3+n的算法一、用自然语言描二、流程图描述：sum=1+2+3+n的算法开始输入nSum0i 1i=nSum sum+Ii i+1输出sum结束否是二、流程图描述：sum=1+2+3+n的算法开始输入n三、N-S图描述：sum=1+2+3+n的算法 N-SN-S图是美国学者图是美国学者I.NassiI.Nassi和和B.ShneidermanB.Shneiderman在在19731973年提出的一种流程图，年提出的一种流程图，其主要特点是不带有流程线，整个算法完全写在一个大的矩形框中。其主要特点是不带有流程线，整个算法完全写在一个大的矩形框中。当i=n时，做输入nSum=0，i=1Sum=sum+Ii=i+1输出sum的值N-S图方式三、N-S图描述：sum=1+2+3+n的算法四、伪代码描述：四、伪代码描述：sum=1+2+3+n的算法的算法 就是用文字和符号的方式来描述算法。在实际应用中，人们往往就是用文字和符号的方式来描述算法。在实际应用中，人们往往用接近于某种程序语言的代码形式作为伪代码。这样可以方便编程用接近于某种程序语言的代码形式作为伪代码。这样可以方便编程。伪代码方式Input n sum=0 i=1 for i=1 to n do sum=sum+i print sumend四、伪代码描述：sum=1+2+3+n的算法五、计算机语言描述：程序五、计算机语言描述：程序用C语言描述sum=1+2+3+n的算法main()int n;int sum=0,i=1;scanf(“%d”,&n);for(i=1;i=n;i+)sum=sum+i;printf(“sum=%dn”,sum);五、计算机语言描述：程序用C语言描述sum=1+2+一、算法的一、算法的5个基本特征个基本特征 1、可行性、可行性 2、确定性、确定性 3、有穷性、有穷性 4、有零个或多个输入、有零个或多个输入 5、有一个或多个输出、有一个或多个输出二、算法的二、算法的2个基本要素个基本要素 1 1、对数据的、对数据的运算和操作运算和操作 2 2、算法的、算法的控制结构控制结构。一、算法的5个基本特征 算法的基本要素之一：对数据的算法的基本要素之一：对数据的运算和操作运算和操作 在计算机系统中，基本的运算和操作有以下四类：在计算机系统中，基本的运算和操作有以下四类：算术运算：算术运算：主要包括加、减、乘、除等运算。主要包括加、减、乘、除等运算。逻辑运算：逻辑运算：主要包括主要包括“逻辑与逻辑与”、“逻辑或逻辑或”、“逻辑非逻辑非”等运算。等运算。关系运算：关系运算：主要包括主要包括“大于大于”、“大于或等于大于或等于”、“小于小于”、“小于或等于小于或等于”、“等于等于”、“不等于不等于”等运算。等运算。数据传输：数据传输：主要包括赋值、输入、输出等操作。主要包括赋值、输入、输出等操作。算法流程图例子算法流程图例子算法的基本要素之一：对数据的运算和操作在计算 算法的基本要素之二：算法的算法的基本要素之二：算法的控制结构控制结构 控制结构控制结构-算法中各种操作步骤之间的执行顺序。算法中各种操作步骤之间的执行顺序。顺序结构顺序结构选择结构选择结构循环结构循环结构三种基本三种基本控制结构控制结构算法流程图例子算法流程图例子算法的基本要素之二：算法的控制结构控制结构-算法中各三、算法设计的基本方法三、算法设计的基本方法 六种：列举法、归纳法、递推、六种：列举法、归纳法、递推、递归、减半递推技术、回溯法。递归、减半递推技术、回溯法。1、列举法、列举法 列举法就是根据所要解决的问题，把所有可列举法就是根据所要解决的问题，把所有可 能的情况都一一列举出来，并用问题中给定的条能的情况都一一列举出来，并用问题中给定的条 件来检验哪些是需要的，哪些是不需要的。件来检验哪些是需要的，哪些是不需要的。三、算法设计的基本方法六种：列举法、归纳法、递推、2、归纳法、归纳法 归纳法的基本思想是通过列举少量的特殊情况，经过分析，归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。最后找出一般的关系。可以看出，归纳法可以解决列举量为无限的问题。可以看出，归纳法可以解决列举量为无限的问题。3、迭代法（递推法）、迭代法（递推法）递推是指从已知的初始条件出发，逐步推出所要求的结果。递推是指从已知的初始条件出发，逐步推出所要求的结果。2、归纳法3、迭代法（递推法）4、递归、递归 在解决某些复杂问题时，为了降低问题的复杂程度（如问题的在解决某些复杂问题时，为了降低问题的复杂程度（如问题的规模等），可以将问题逐层分解，最后归结为一些最简单的问题。规模等），可以将问题逐层分解，最后归结为一些最简单的问题。例例8.2 8.2 有有5 5个人坐在一起，问第个人坐在一起，问第5 5个人多少岁个人多少岁?他说比第他说比第4 4个个人大人大2 2岁。问第岁。问第4 4个人的岁数，他说比第个人的岁数，他说比第3 3个人大个人大2 2岁。问第岁。问第3 3个人，又说比第个人，又说比第2 2个人大个人大2 2岁。问第岁。问第2 2个人，说比第个人，说比第1 1个人大个人大2 2岁。最后问第岁。最后问第1 1个人，他说是个人，他说是1010岁。请问第岁。请问第5 5个人多大？个人多大？4、递归 用递归方法求解，递归过程如下：用递归方法求解，递归过程如下：age age（5 5）ageage（4 4）十）十2 2 age age（4 4）=age=age（3 3）十）十2 2 age age（3 3）ageage（2 2）十）十2 2 age age（2 2）ageage（1 1）十）十2 2 age age（l l）1010用递归方法求解，递归过程如下：5、减半递推技术、减半递推技术 “减半减半”是指将问题的规模减半，而问题的性质不变；是指将问题的规模减半，而问题的性质不变；“递推递推”是指重复是指重复“减半减半”的过程。的过程。例例8.3 8.3 设设方方程程f f（x x）=0=0在在区区间间 aa，bb上上有有实实根根，且且f f（a a）与与f f（b b）符符号号相相反反，即即f f（a a）f f（b b）00。利利用用二二分分法法求求该该方方程程在在区区间间 aa，bb上的一个实根。上的一个实根。用二分法求方程实根的减半递推过程如下：用二分法求方程实根的减半递推过程如下：首首先先计计算算区区间间的的中中点点c=c=（a+ba+b）/2/2，然然后后计计算算函函数数在在中中点点c c的的值值f f（c c），并并判判断断f f（c c）是是否否为为0 0。若若f f（c c）=0=0，则则说说明明c c就就是是所所求求的的根根，求求解解过过程结束；如果程结束；如果f f（c c）00，则根据以下原则将原区间减半，则根据以下原则将原区间减半：5、减半递推技术例8.3设方程f（x）=0在 若若f f（a a）f f（c c）00，则取原区间的前半部分，；，则取原区间的前半部分，；若若f f（b b）f f（c c）00，则取原区间的后半部分。，则取原区间的后半部分。最最后后根根据据计计算算精精度度 的的要要求求，判判断断减减半半后后的的区区间间长长度度是是否否已经很小：已经很小：若若|ab|ab|，则过程结束，取（，则过程结束，取（a+ba+b）/2/2为根的近似值；为根的近似值；若若|ab|ab|，则重复上述的减半过程。，则重复上述的减半过程。若f（a）f（c）0，则取原区间的前半部分，6、回溯法、回溯法 对对于于某某些些问问题题，一一种种有有效效的的方方法法是是“试试”，即即通通过过对对问问题题的的分分析析，找找出出一一个个解解决决问问题题的的线线索索，然然后后沿沿着着这这个个线线索索逐逐步步试试探探，对对于于每每一一步步的的试试探探，若若试试探探成成功功，就就得得到到问问题题的的解解，若若试试探探失失败败，就就逐逐步步回回退退，换换别别的的路路线线再再进进行行试试探探。这这种种方方法法称称为为回回溯溯法法。回回溯溯法法在在处处理理复复杂杂数数据据结结构构方方面面有有着着广广泛泛的的应用。应用。6、回溯法 6.1 算算 法法 6.1.1 算法的基本概念算法的基本概念 一、一、算法的基本特征算法的基本特征 1、可行性、可行性 2、确定性、确定性 3、有穷性、有穷性 4、有零个或多个输入、有零个或多个输入 5、有一个或多个输出、有一个或多个输出 二、算法的基本要素二、算法的基本要素 1 1、对数据的运算和操作、对数据的运算和操作 2 2、算法的控制结构、算法的控制结构 三、算法设计的基本方法三、算法设计的基本方法 列举法、归纳法、递推、递归、减半递推技术、回溯法列举法、归纳法、递推、递归、减半递推技术、回溯法 小结：小结：6.1算法6.1.选选用用算算法法首首先先考考虑虑正正确确性性，还还要要考考虑虑执执行行算算法法所所耗耗费费的的时时间间和和存存储储空空间间，同同时时算算法法应应易易于于理解、编码、调试等。理解、编码、调试等。算算法法的的复复杂杂度度可可分分为为时时间间复复杂杂度度和和空空间间复复杂度杂度，是衡量算法优劣的度量。，是衡量算法优劣的度量。8.1 算法算法8.1.2 算法的复杂度算法的复杂度8.1算法 一、一、算法的时间复杂度算法的时间复杂度 算法的时间复杂度：执行算法所需要的算法的时间复杂度：执行算法所需要的计算工作量计算工作量。算法的算法的计算工作量：计算工作量：用算法所执行的用算法所执行的基本运算次数基本运算次数来度量，来度量，基本运算次数基本运算次数：是问题规模的函数。：是问题规模的函数。则：算法的计算工作量则：算法的计算工作量=f（n），其中），其中n是问题的规模。是问题的规模。一、算法的时间复杂度（1）平均性态平均性态（Average Behavior）平平均均性性态态分分析析是是指指用用各各种种特特定定输输入入下下的的基基本本运运算算次次数数的的加加权权平平均均值值来来度度量量算算法法的的工工作作量量。假假设设x是是所所有有可可能能输输入入中中的的某某个个特特定定输输入入，用用p（x）表表示示x出出现现的的概概率率（即即输输入入为为x的的概概率率），用用t（x）表表示示算算法法在在输输入入为为x时时所所执执行行的的基基本本运运算算次次数数，则则算算法法的的平均性态定义为平均性态定义为 在在分分析析一一个个给给定定问问题题算算法法的的时时间间复复杂杂度度时时，可可以以采采用用下面两种方法来分析算法的工作量。下面两种方法来分析算法的工作量。其中其中Dn表示当规模为表示当规模为n时，算法执行时所有可能输入的集合。时，算法执行时所有可能输入的集合。（1）平均性态（AverageBehavior）在（2）最坏情况复杂性（）最坏情况复杂性（Worst-Case Complexity）最坏情况分析是指在规模为最坏情况分析是指在规模为n时，算法所执行的基本运算的最大次时，算法所执行的基本运算的最大次数。它定义为数。它定义为 其中，其中，Dn和和t（x）的含义同上。可以看出，最坏情况分析）的含义同上。可以看出，最坏情况分析W（n）的计算要比平均性态分析）的计算要比平均性态分析A（n）的计算方便得多。）的计算方便得多。实际上，实际上，W（n）给出了估计算法工作量的一个上界，因此，它比）给出了估计算法工作量的一个上界，因此，它比A（n）更具有实用价值，是分析算法的时间复杂度常用的一个方法。）更具有实用价值，是分析算法的时间复杂度常用的一个方法。（2）最坏情况复杂性（Worst-CaseComplexi算法的执行时间依赖于具体的软硬件环境，所以，不能用执行时间算法的执行时间依赖于具体的软硬件环境，所以，不能用执行时间的长短来衡量算法的时间复杂度，而要通过基本语句执行次数的数的长短来衡量算法的时间复杂度，而要通过基本语句执行次数的数量级来衡量。量级来衡量。求解算法的时间复杂度的具体步骤是：求解算法的时间复杂度的具体步骤是：找出算法中的基本语句；找出算法中的基本语句；算法中执行次数最多的那条语句就是基本语句，通常是最内层算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。循环的循环体。计算基本语句的执行次数的数量级；计算基本语句的执行次数的数量级；只需计算基本语句执行次数的数量级，这就意味着只要保证基只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。在最重要的一点上：增长率。用大用大记号表示算法的时间性能。记号表示算法的时间性能。将基本语句执行次数的数量级放入大将基本语句执行次数的数量级放入大记号中。记号中。时间复杂度计算步骤：时间复杂度计算步骤：算法的执行时间依赖于具体的软硬件环境，所以，不能用执行时间的26如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：for(i=1;i=n;i+)x+;for(i=1;i=n;i+)for(j=1;j=n;j+)x+;第一个for循环的时间复杂度为(n)，第二个for循环的时间复杂度为(n2)，则整个算法的时间复杂度为(n+n2)=(n2)。算法时间复杂度举例：算法时间复杂度举例：如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如常见的算法时间复杂度：o常见的算法时间复杂度由小到大依次为：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)(n!)(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是(1)。(log2n)、(n)、(nlog2n)、(n2)和(n3)称为多项式时间，而(2n)和(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称为P类问题，而把后者称为NP问题。常见的算法时间复杂度：常见的算法时间复杂度由小到大依次为：“如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。”Temp=i;i=j;j=temp;总共由3条语言,每条的频度均为1,每条的频度可认为都是O(1),那么T(n)=O(1)+O(1)+O(1)=O(1)。下面4条语句:scanf(“%d”,&n);i=n;for(i=0,in;i+)i=i*1;(这也只算是一句)for(将j=0,jn*n;j+)i=i*1;(同上)前两条频度均为1;后两条分别频度为n和n*n那么总频度均为O(1)+O(1)+O(n)+O(n*n)=O(n*n)“如果算法的执行时间不随着问题规模n的增加而增长，即使算法中1.交换i和j的内容sum=0；（一次）for(i=1;i=n;i+)（n次）for(j=1;j=n;j+)（n2次）sum+；（n2次）解：T(n)=2n2+n+1=O(n2)2.for(i=1;in;i+)y=y+1;for(j=0;j=(2*n);j+)x+;解：语句1的频度是n-1语句2的频度是(n-1)*(2n+1)=2n2-n-1f(n)=2n2-n-1+(n-1)=2n2-2该程序的时间复杂度T(n)=O(n2).a=0;b=1;for(i=1;in;i+)s=a+b;b=a;a=s;解：语句1的频度：2,语句2的频度：n,语句3的频度：n-1,语句4的频度：n-1,语句5的频度：n-1T(n)=2+n+3(n-1)=4n-1=O(n).1.交换i和j的内容sum=0；2算法的空间复杂度算法的空间复杂度 -执行这个算法所需要的内存空间。执行这个算法所需要的内存空间。类似算法的时间复杂度，空间复杂度作为算法所类似算法的时间复杂度，空间复杂度作为算法所需存储空间的度量。需存储空间的度量。2算法的空间复杂度6.1 算法课堂练习题算法课堂练习题考题考题(2005_4):(11)算法具有五个特性算法具有五个特性,以下选项中不属于算法特性的是以下选项中不属于算法特性的是(A)有穷性有穷性(B)简洁性简洁性(C)可行性可行性(D)确定性确定性 答案：答案：B 考题（考题（2005_4）5.问题处理方案的正确而完整的描述称为问题处理方案的正确而完整的描述称为_答案：答案：算法算法6.1算法课堂练习题考题(2005_4):(11)算法考题（考题（2005_9）（）（1）算法复杂度主要包括时间复杂度和_复杂度。答案：空间考题（2005_9）（1）算法复杂度主要包括时间复杂度和_6.2 数据结构数据结构数据结构主要研究三个问题数据结构主要研究三个问题:1 1、数数据据集集合合中中各各数数据据元元素素之之间间所所固固有有的的逻逻辑辑关关系，即系，即数据的逻辑结构数据的逻辑结构；2 2、在在对对数数据据进进行行处处理理时时，各各数数据据元元素素在在计计算算机机中的存储关系，即中的存储关系，即数据的存储结构数据的存储结构；3 3、对各种数据结构进行的、对各种数据结构进行的运算运算。6.2数据结构数据结构主要研究三个问题:6.2.1 什么是数据结构？什么是数据结构？例例6.5 6.5 无序表的顺序查找与有序表的对分查找。无序表的顺序查找与有序表的对分查找。6.2.1什么是数据结构？例6.5无序表的顺序查找与现实世界中存在的一切个体都可以是数据元素。现实世界中存在的一切个体都可以是数据元素。例如：例如：“春、夏、秋、冬春、夏、秋、冬”，可以作为季节的数据元素；，可以作为季节的数据元素；“26 “26、5656、6565、73 73、2626、”，可以作为数值的数据元素；，可以作为数值的数据元素；“父亲、儿子、女儿父亲、儿子、女儿”，可以作为家庭成员的数据元素。，可以作为家庭成员的数据元素。在数据处理领域中，每一个需要处理的对象都可以抽象成在数据处理领域中，每一个需要处理的对象都可以抽象成数据元素。数据元素一般简称为数据元素。数据元素一般简称为元素元素。现实世界中存在的一切个体都可以是数据元素。在具有相同特点的数据元素集合中，各个数据元素之间存在着在具有相同特点的数据元素集合中，各个数据元素之间存在着某种关系（即联系），这种关系反映了数据元素所固有的一种某种关系（即联系），这种关系反映了数据元素所固有的一种结构。结构。在在数数据据处处理理中中，通通常常把把数数据据元元素素之之间间这这种种固固有有的的关关系系简简单单地地用用前后件关系前后件关系（或直接前驱与直接后继关系）来描述。（或直接前驱与直接后继关系）来描述。例如：例如：在在“春、夏、秋、冬春、夏、秋、冬”中，中，“春春”是是“夏夏”前件，前件，。一般来说，数据元素之间的任何关系都可以用一般来说，数据元素之间的任何关系都可以用前后件关系前后件关系来来描述。描述。在具有相同特点的数据元素集合中，各个数据元素之间存在着1数据的逻辑结构数据的逻辑结构数据结构是指带有结构的数据元素的集合数据结构是指带有结构的数据元素的集合。这里所说的结构实际上就是指数据元素之间的前后件关系。这里所说的结构实际上就是指数据元素之间的前后件关系。由此可见，一个数据结构应包含如下两种信息：由此可见，一个数据结构应包含如下两种信息：表示数据元素的信息；表示数据元素的信息；表示各数据元素之间的前后件关系。表示各数据元素之间的前后件关系。数据元素之间的前后件关系是指它们的逻辑关系，这与它们在计数据元素之间的前后件关系是指它们的逻辑关系，这与它们在计算机中的存储位置无关。算机中的存储位置无关。数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。1数据的逻辑结构由前面的叙述可以看出，数据的逻辑结构有两个基本要素：由前面的叙述可以看出，数据的逻辑结构有两个基本要素：一是数据元素的集合，通常记为一是数据元素的集合，通常记为D；二二是是D上上的的关关系系，它它反反映映了了D中中各各数数据据元元素素之之间间的的前前后后件件关关系系，通通常记为常记为R。因因此此，一一个个数数据据的的逻逻辑辑结结构构可可以以表表示示成成 B=（D，R），其其中中B表表示数据的逻辑结构。示数据的逻辑结构。由前面的叙述可以看出，数据的逻辑结构有两个基本要素：例例 一年四季的数据逻辑结构可以表示成一年四季的数据逻辑结构可以表示成 B=B=（D D，R R）D=D=春，夏，秋，冬春，夏，秋，冬 R=R=（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬）例例 家庭成员的数据逻辑结构可以表示成家庭成员的数据逻辑结构可以表示成 B=B=（D D，R R）D=D=父亲，儿子，女儿父亲，儿子，女儿 R=R=（父亲，儿子），（父亲，女儿）（父亲，儿子），（父亲，女儿）例一年四季的数据逻辑结构可以表示成2数据的存储结构数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。储结构（也称数据的物理结构）。在数据的存储结构中，不仅要存放各数据元素的信息，还需在数据的存储结构中，不仅要存放各数据元素的信息，还需 要存放各数据元素之间的前后件关系的信息。要存放各数据元素之间的前后件关系的信息。一种数据的逻辑结构可以表示成多种存储结构。一种数据的逻辑结构可以表示成多种存储结构。常用的存储结构有常用的存储结构有顺序、链接、索引顺序、链接、索引等存储结构。等存储结构。对于一种数据的逻辑结构，如果采用不同的存储结构，则数据对于一种数据的逻辑结构，如果采用不同的存储结构，则数据处理的效率是不同的。因此，在进行数据处理时，选择合适的处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是非常重要的。存储结构是非常重要的。2数据的存储结构6.2.2 数据结构的图形表示数据结构的图形表示数据结构除了可以用前面的所述的二元关系表示外，数据结构除了可以用前面的所述的二元关系表示外，还可以用图形来表示。还可以用图形来表示。6.2.2数据结构的图形表示o例例 n维向量维向量 X=(x1,x2,xn)也是一种数据结构。即也是一种数据结构。即X=(D,R)，其中数据元素的，其中数据元素的集合为：集合为：D=x1,x2,xn 关系为：关系为：R=(x1,x2),(x2,x3),(xn 1,xn)例n维向量o例如，mn的矩阵的矩阵例如，mn的矩阵omn的矩阵是一个数据结构。在这个数据结构中，是一个数据结构。在这个数据结构中，矩阵的每一行矩阵的每一行 Ai=(ai1，ai2，ain)，i=1,2,mo可以看成是它的一个数据元素。即这个数据结构的可以看成是它的一个数据元素。即这个数据结构的数据元素的集合为：数据元素的集合为：D=A1，A2，AmoD上的一个关系为：上的一个关系为：R=(A1，A2)，(A2，A3)，(Ai，Ai+1)，(Am 1，Am)mn的矩阵是一个数据结构。在这个数据结构中，矩阵的每一行o显然，数据结构显然，数据结构A中的每一个数据元素中的每一个数据元素Ai（i=1,2,m）又是另一个数据结构，即数据元素的集合为：）又是另一个数据结构，即数据元素的集合为：Di=ai1，ai2,，ainoDi上的一个关系为：上的一个关系为：Ri=(ai1，ai2)，(ai2，ai3)，(aij,ai,j+1)，(ai,n 1，ain)o一个数据结构除了用二元关系表示外，还可以直观地一个数据结构除了用二元关系表示外，还可以直观地用图形表示。用图形表示。显然，数据结构A中的每一个数据元素Ai（i=1,2,o例例 用图形表示数据结构用图形表示数据结构B=（D，R），其中），其中 D=di|1i7=d1，d2，d3，d4，d5，d6，d7 R=(d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5)这个数据结构的图形表示如图所示。这个数据结构的图形表示如图所示。例用图形表示数据结构B=（D，R），其中6.2.3 线性结构与非线性结构线性结构与非线性结构根据数据结构中各数据元素之间前后件关系的复杂程度，根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类：一般将数据结构分为两大类：线性结构与非线性结构线性结构与非线性结构。如果一个非空的数据结构满足下列条件：如果一个非空的数据结构满足下列条件：（1）有且只有一个根结点；有且只有一个根结点；（2）有且只有一个终端结点；有且只有一个终端结点；（3）除根结点外，其他结点均只有一个前件；除根结点外，其他结点均只有一个前件；（4）除终端结点外，其他结点均只有一个后件。除终端结点外，其他结点均只有一个后件。则称该数据结构为则称该数据结构为线性结构线性结构。线性结构又称。线性结构又称线性表线性表。6.2.3线性结构与非线性结构如果一个非空的数据结构满足下oo例如，如图所示的数据结构显然是满足上述例如，如图所示的数据结构显然是满足上述两个条件的，但它不属于线性结构这个类型，两个条件的，但它不属于线性结构这个类型，因为如果在这个数据结构中删除结点因为如果在这个数据结构中删除结点A后，后，就不满足上述的条件就不满足上述的条件。例如，如图所示的数据结构显然是满足上述两个条件的，但它不属于o一个数据结构不是线性结构，则称之为非线性结一个数据结构不是线性结构，则称之为非线性结构。构。o线性结构与非线性结构都可以是空的数据结构。线性结构与非线性结构都可以是空的数据结构。o如果对该数据结构的运算是按线性结构的规则来如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。处理的，则属于线性结构；否则属于非线性结构。一个数据结构不是线性结构，则称之为非线性结构。课堂练习：课堂练习：6.2 数据结构的基本概念数据结构的基本概念考题（考题（2005_4）:(1)数据的存储结构是指数据的存储结构是指(A)存储在外存中的数据存储在外存中的数据(B)数据所占的存储空间量数据所占的存储空间量(C)数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式(D)数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示答案：答案：D课堂练习：6.2数据结构的基本概念考题（2005考题（考题（2005_9）:(4)下列叙述正确的是()。A)一个逻辑数据结构只能有一种存储结构B)数据的逻辑结构属于线性结构，存储结构属于非线性结构C)一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D)一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率答案：D考题（2005_9）:(4)下列叙述正确的是()。数据的逻辑结构数据的逻辑结构非线性结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列图1-5 数据逻辑结构层次关系图数据逻辑结构层次关系图图图1-4 逻辑结构与所采用的存储结构逻辑结构与所采用的存储结构线性表线性表树树图图顺序存储结构顺序存储结构链式存储结构链式存储结构复合存储结构复合存储结构逻辑结构逻辑结构物理结构物理结构数据的逻辑结构非线性结构集合图状结构有向图无向图树形结构一般o一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的。o数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。数据的存储结构数据的存储结构一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑o在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。o常用的存储结构有顺序、链接、索引、散列等存储结构。在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各o顺序存储结构主要用于线性结构。在这种存储方式中，把逻辑上相邻的数据元素结点存储在物理上相邻的存储单元中，各结点之间的关系由存储单元的邻接关系来体现。o右图是将线性结构(K1，K2)，(K2，K3)，(K3，K4)，(K4，K5)，(K5，K6)，(K6，K7)顺序地存放在存储单元中的示意图。（1）顺序存储结构）顺序存储结构顺序存储结构主要用于线性结构。在这种存储方式中，把逻辑上相邻o在链接存储结构中，每个存储结点要有两部分组成：一部分用于存放数据信息，另一部分用于存放指针。o其中指针用于指向该结点的前件或后件。（2）链接存储结构）链接存储结构在链接存储结构中，每个存储结点要有两部分组成：一部分用于存放数据结构与算法课件o利用链接存储方式也可以存储非线性结构。o下图（a）和（b）分别为一棵二叉树的逻辑结构与链接存储结构的示意图。利用链接存储方式也可以存储非线性结构。数据结构与算法课件6 6.3.3 线性表及其顺序存储结构线性表及其顺序存储结构6 6.3.1.3.1 线性表的基本概念线性表的基本概念 线线性性表表（Linear Linear ListList）是是最最简简单单、最最常常用用的的一一种种数数据据结结构构。所所谓谓线线性性表表，是是指指n n个个数数据据元元素素的的有限序列。有限序列。线性性表表可可以以表表示示为 （a a1 1，a a2 2，a ai i，a an n），其其中中a ai i是是属属于于数数据据对象象的的元元素素，通通常常也也称称其其为线性表中的一个性表中的一个结点。点。当当n=0n=0时，称，称为空表。空表。6.3线性表及其顺序存储结构6.3.1线性表的基本概念6 6.3.2.3.2 线性表的顺序存储结构线性表的顺序存储结构 在在计计算算机机中中存存放放线线性性表表，一一种种最最简简单单的的方方法法是是顺顺序序存存储储。其其特特点如下：点如下：（1）线性表中所有元素所占的存储空间是连续的；线性表中所有元素所占的存储空间是连续的；（2）线线性性表表中中各各数数据据元元素素在在存存储储空空间间中中是是按按逻逻辑辑顺顺序序依依次次存存放的。放的。6.3.2线性表的顺序存储结构在计算机中存放线性表，一种 对于线性表的顺序存储结构，可以进行各种处理。对于线性表的顺序存储结构，可以进行各种处理。下下面面主主要要讨讨论论线线性性表表在在顺顺序序存存储储结结构构下下的的插插入入与与删删除除运算。运算。下下面面通通过过一一个个例例子子来来说说明明如如何何在在顺顺序序存存储储结结构构的的线线性性表表中插入一个新元素。中插入一个新元素。对于线性表的顺序存储结构，可以进行各种处理。例例 下下图图（a）是是为为一一个个长长度度为为5的的线线性性表表顺顺序序存存储在长度为储在长度为8的存储空间中。的存储空间中。例下图（a）是为一个长度为5的线性 例例 图图（a）是是一一个个长长度度为为7的的线线性性表表顺顺序序存存储储在在长长度度为为8的的存储空间中。现在要求删除表中的第存储空间中。现在要求删除表中的第2个元素（即删除元素个元素（即删除元素23）。）。例图（a）是一个长度为7的线性表顺序考题（考题（2005_4）(5)下列对于线性表的描述中正确的是下列对于线性表的描述中正确的是 A)存储空间不一定是连续存储空间不一定是连续,且各元素的存储顺序是任意的且各元素的存储顺序是任意的 B)存储空间不一定是连续存储空间不一定是连续,且前件元素一定存储在后件元素的前且前件元素一定存储在后件元素的前面面 C)存储空间必须连续存储空间必须连续,且各前件元素一定存储在后件元素的前面且各前件元素一定存储在后件元素的前面 D)存储空间必须连续存储空间必须连续,且各元素的存储顺序是任意的且各元素的存储顺序是任意的答案：答案：A课堂练习：6.3 线性表及其顺序存储结构考题（2005_4）(5)下列对于线性表的描述中正确的是课6 6.4.4 栈和队列栈和队列6.4.1 6.4.1 栈及其基本运算栈及其基本运算 1栈的基本概念栈的基本概念 栈栈（stack）是是限限定定仅仅在在一一端端进进行行插插入入和和删除运算的线性表删除运算的线性表。在在栈栈中中，允允许许插插入入与与删删除除的的一一端端称称为为栈栈顶顶，而不允许插入与删除的另一端称为而不允许插入与删除的另一端称为栈底栈底。6.4栈和队列6.4.1栈及其基本运算 1栈的基本概念栈的基本概念栈的顺序存储结构如图所示。栈的顺序存储结构如图所示。1栈的基本概念6 6.4.1 .4.1 栈及其基本运算栈及其基本运算 1栈的基本概念栈的基本概念 2栈的基本运算栈的基本运算栈的基本运算有三种：栈的基本运算有三种：入栈、退栈与读栈顶元素入栈、退栈与读栈顶元素。（1）入栈运算入栈运算入栈运算是指在栈顶位置插入一个新元素。入栈运算是指在栈顶位置插入一个新元素。这个运算有两个基本操作：这个运算有两个基本操作：首首先先将将栈栈顶顶指指针针进进一一，然然后后将将新新元元素素插插入入到到栈栈顶顶指指针针指指向的位置；向的位置；6.4.1栈及其基本运算1栈的基本概念6 6.4.1 .4.1 栈及其基本运算栈及其基本运算 （2）退栈运算退栈运算退栈运算是指取出栈顶元素并赋给某个变量。退栈运算是指取出栈顶元素并赋给某个变量。这个运算有两个基本操作：这个运算有两个基本操作：首首先先将将栈栈顶顶元元素素赋赋给给一一个个指指定定的的变变量量，然然后后将将栈栈顶顶指针退一。指针退一。6.4.1栈及其基本运算（2）退栈运算706 6.4.1 .4.1 栈及其基本运算栈及其基本运算 （3）读栈顶元素读栈顶元素读读栈栈顶顶元元素素是是指指将将栈栈顶顶元元素素赋赋给给一一个个指指定定的的变变量量。在在这这个运算中，栈顶指针不会改变。个运算中，栈顶指针不会改变。6.4.1栈及其基本运算（3）读栈顶元素例例 在下图中，设在下图中，设toptop为指向栈顶元素的指针。（为指向栈顶元素的指针。（a a）为容量为为容量为8 8的栈顺序存储空的栈顺序存储空间，栈中已有间，栈中已有4 4个元素；（个元素；（b b）与图（）与图（c c）分别为入栈与退栈后的状态。）分别为入栈与退栈后的状态。例在下图中，设top为指向栈顶元素的指针。（a）为容量为考题（考题（2005_4）(2)下列关于栈的描述中错误的是下列关于栈的描述中错误的是(A)栈是先进后出的线性表栈是先进后出的线性表(B)栈只能顺序存储栈只能顺序存储(C)栈具有记忆作用栈具有记忆作用(D)对栈的插入和删除操作中，不需要改变栈底指针对栈的插入和删除操作中，不需要改变栈底指针答案：答案：B分析：栈：特殊的线性表。限定只在一端进行插入与删除的线性表，这一端称为栈顶，另一端称为栈底。栈是按照“先进后出”或“后进先出”的原则组织数据的。栈具有记忆作用。考题（2005_4）(2)下列关于栈的描述中错误的是6 6.4.2.4.2 队列及其基本运算队列及其基本运算1队列的基本概念队列的基本概念队队列列（queue）是是限限定定仅仅在在表表的的一一端端进进行行插插入入，而而在表的另一端进行删除的线性表在表的另一端进行删除的线性表。在队列中，允许插入的一端称为在队列中，允许插入的一端称为队尾队尾，允许删除的一端称为允许删除的一端称为队头队头。队队列列又又称称为为“先先进进先先出出”或或“后后进进后后出出”的的线线性性表表。在在队队列列中中，通通常常用用指指针针front 指指向向队队头头，用用rear指向队尾，如图所示。指向队尾，如图所示。6.4.2队列及其基本运算1队列的基本概念1队列的基本概念队列的基本概念1队列的基本概念下图是在队列中进行插入与删除的示意图。下图是在队列中进行插入与删除的示意图。下图是在队列中进行插入与删除的示意图。考题（考题（2005_9）（）（3）以下关于栈的描述正确的是()。A)在栈中只能插入元素而不能删除元素B)在栈中只能删除元素而不能插入C)栈是特殊的线性表，只能在一端插入或删除元素D)栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素答案：C考题（2005_9）（3）以下关于栈的描述正确的是(考题（考题（2005_9）（）（5）数据结构分为逻辑结构和存储结构，循环队列属于_结构。答案：存储考题（2005_9）（5）数据结构分为逻辑结构和存储结构，循6.6 树与二叉树树与二叉树 6.6.1 树的基本概念树的基本概念树（树（tree）是一种非线性结构。在树这种数据结构中，所有）是一种非线性结构。在树这种数据结构中，所有数据元素之间的关系具有明显的层次特点。下图表示了数据元素之间的关系具有明显的层次特点。下图表示了一棵一般的树。一棵一般的树。图6.22树的结构图6.6树与二叉树6.6.1树的基本概念图6.22树的实际上，能用树结构表示的例子有许多。例如，下图中的树实际上，能用树结构表示的例子有许多。例如，下图中的树表示了学校行政关系结构。表示了学校行政关系结构。图8.23学校行政层次结构树实际上，能用树结构表示的例子有许多。例如，下图中的树表示了学80在树结构中，每一个结点只有一个前件，称为在树结构中，每一个结点只有一个前件，称为父结点父结点，没有前件的，没有前件的结点只有一个，称为结点只有一个，称为根结点根结点（简称（简称根根）。例如，在下图中，结）。例如，在下图中，结点点A是树的根结点。是树的根结点。在树结构中，每一个结点可以有多个后件，它们都称为该结点在树结构中，每一个结点可以有多个后件，它们都称为该结点的的子结点子结点。没有后件的结点称为。没有后件的结点称为叶子结点叶子结点。例如，在下图中，。例如，在下图中，结点结点E、F、G、H、I、J均为叶子结点。均为叶子结点。在树结构中，在树结构中，个结点所拥有的后件的个数称为该个结点所拥有的后件的个数称为该结点的度结点的度。例如，在下图中，根结点例如，在下图中，根结点A的度为的度为3；结点；结点B的度为的度为2；结点；结点C的的度为度为1；叶子结点的度为；叶子结点的度为0。在树结构中，所有结点中的最大的度称为在树结构中，所有结点中的最大的度称为树的度树的度。例如，下图。例如，下图所示的树的度为所示的树的度为3。下面介绍树这种数据结构中的一些基本特征和基本术语下面介绍树这种数据结构中的一些基本特征和基本术语在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结81由于树结构具有明显的层次关系，即树是一种层次结构，由于树结构具有明显的层次关系，即树是一种层次结构，所以在树结构中，一般按如下原则分层：所以在树结构中，一般按如下原则分层：根结点在第根结点在第1层。同一层上所有结点的所有子结点都在下一层。同一层上所有结点的所有子结点都在下一层。例如，在下图中，根结点层。例如，在下图中，根结点A在第在第1层；结点层；结点B、C、D在在第第2层；结点层；结点E、F、G、H、I、J在第在第3层。层。树的最大层数称为树的最大层数称为树的深度树的深度。例如，下图所示的树的深度。例如，下图所示的树的深度为为3。由于树结构具有明显的层次关系，即树是一种层次结构，所以在树结82 在树结构中，以某结点的一个子结点为根构成的树称为在树结构中，以某结点的一个子结点为根构成的树称为该结点的一棵该结点的一棵 子树子树。例如，在下图中：根结点。例如，在下图中：根结点A有有3棵棵子树，它们分别以子树，它们分别以B、C、D为根结点；结点为根结点；结点B有有2棵子棵子树，它们分别以树，它们分别以E、F为根结点。在树结构中，叶子结为根结点。在树结构中，叶子结点没有子树。点没有子树。在树结构中，以某结点的一个子结点为根构成的树称为该结836.6.2 6.6.2 二叉树及其基本运算二叉树及其基本运算1二叉树的基本概念二叉树的基本概念 二叉树（二叉树（binary tree）是一种非常用的非线性）是一种非常用的非线性数据结构。二叉树与前面介绍的树结构不同，但它数据结构。二叉树与前面介绍的树结构不同，但它与树结构很相似，并且，有关树结构的所有术语都与树结构很相似，并且，有关树结构的所有术语都可以用到二叉树这种数据结构上。可以用到二叉树这种数据结构上。6.6.2二叉树及其基本运算1二叉树的基本概念二叉树具有以下两个特点：二叉树具有以下两个特点：非空二叉树只有一个根结点；非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分每一个结点最多有两棵子树，且分别称为该结点的别称为该结点的左子树左子树与与右子树右子树。右图所示是一颗二叉树，根结点为右图所示是一颗二叉树，根结点为A，其左子树包含结点，其左子树包含结点B、D、G、H，右子树包含结点，右子树包含结点C、E、F、I、J。根。根A的的左子树又是一颗二叉树，其根结点为左子树又是一颗二叉树，其根结点为B，有非空的左子树，有非空的左子树（由结点（由结点D、G、H组成）和空的右子树。根组成）和空的右子树。根A的右子树也的右子树也是一颗二叉树，其根结点是一颗二叉树，其根结点C，有非空的左子树（由结点，有非空的左子树（由结点E、I、J组成）和右子树（由结点组成）和右子树（由结点F组成）。组成）。二叉树具有以下两个特点：右图所示是一颗二叉树，根结点85 在二叉树中，一个结点可以只有左子树而没有右在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。例如，子树，也可以只有右子树而没有左子树。例如，下图中所示的是下图中所示的是4颗不同的二叉树，但如果作为颗不同的二叉树，但如果作为树，它们就相同了。树，它们就相同了。4颗不同的二叉树在二叉树中，一个结点可以只有左子树而没有右子树，也可以862满二叉树与完全二叉树满二叉树与完全二叉树满二叉树与完全二叉树是两种特殊的二叉树。满二叉树与完全二叉树是两种特殊的二叉树。（1）满二叉树满二叉树 在一颗二叉树中，如果所有分支结点都存在左子树和在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二右子树，并且所有叶子结点都在同一层上，这样的二叉树称为叉树称为满二叉树满二叉树。图（。图（a）、（）、（b）分别是深度为）分别是深度为2、3的满二叉树。的满二叉树。2满二叉树与完全二叉树（2）完全二叉树完全二叉树 完全二叉树完全二叉树是指除最后一层外，每一层上的结是指除最后一层外，每一层上的结点数均达到最大值，而在最后一层上只缺少右点数均达到最大值，而在最后一层上只缺少右边的若干结点。显然，满二叉树也是完全二叉边的若干结点。显然，满二叉树也是完全二叉树，而完全二叉树不一定是满二叉树。下图是树，而完全二叉树不一定是满二叉树。下图是两颗深度为两颗深度为3的完全二叉树。的完全二叉树。（2）完全二叉树883二叉二叉树的基本性的基本性质二叉二叉树具有下列重要性具有下列重要性质：性性质1 在在二二叉叉树中中，第第i层的的结点点数数最最多多为2i-1个（个（i1）。）。性性质2 在在深深度度为k的的二二叉叉树中中，结点点总数数最最多多为2k-1个（个（k1）。）。20+21+22+。+2K-1=2K-13二叉树的基本性质20+21+22+。+2K-1例例如如，在在下下图所所示示的的二二叉叉树中中，有有5个个叶叶子子结点点，有有4个个度度为2的的结点，度点，度为0的的结点比度点比度为2的的结点多一个。点多一个。性性质3 对任任意意一一棵棵二二叉叉树，度度为0的的结点点（即即叶叶子子结点点）总是是比比度度为2的的结点多一个。点多一个。例如，在下图所示的二叉树中，有5个叶子结点，有4个度为2的结性性质4（1）具具有有n个个结点点的的二二叉叉树，其其深深度度至至少少为log2n+1，其其中中log2n表表示示取取log2n的的整整数数部部分分。（2）具具 有有 n个个 结 点点 的的 完完 全全 二二 叉叉 树 的的 深深 度度 为log2n+1。性质4（1）具有n个结点的二叉树，其深度至少为log2n6.6.3 二叉树的存储结构二叉树的存储结构 二叉树通常采用链式存储结构。用于存储二叉二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点由两部分组成：数据域树中各元素的存储结点由两部分组成：数据域与指针域。与指针域。6.6.3二叉树的存储结构二叉树通常采用链式存储结构 由于在二叉树的存储结构中每个存储结点有两个由于在二叉树的存储结构中每个存储结点有两个指针域，因此，二叉树的链式存储结构也称为二指针域，因此，二叉树的链式存储结构也称为二叉链表。下图表示二叉链表的存储示意图。叉链表。下图表示二叉链表的存储示意图。由于在二叉树的存储结构中每个存储结点有两个指针域，因此936.6.4 二叉树的遍历二叉树的遍历遍历是二叉树的重要运算。二叉树的遍历是指按一定的次序访问二遍历是二叉树的重要运