数据结构-清华大学-殷人昆-01

1数据结构引言清华大学计算机系殷人昆数据结构课件38-2数据结构在计算机教育中的地位计算机教育是一个大的系统工程，有计划、有设计、有实施、有检验，最后要有成果。数据结构在计算机教育中是一门核心课程，是程序设计系列课程中重要的一环。数据结构与算法与程序设计课程一脉相承。程序设计训练学生分析问题、解决问题的技能，数据结构与算法则训练学生在问题解决过程中如何组织数据，如何运用合理的数据结构辅助实现高效的算法。38-3数据结构在计算机教育中的地位（必修）计算机组织与系统结构程序设计与问题解决数据结构基础数学1数学2计算机科学基础计算机系统原理与汇编算法与数据结构Ⅱ程序设计语言基础操作系统有穷自动机38-4数据结构在计算机教育中的地位（选修）数据结构基础计算机科学基础算法与数据结构Ⅱ文件处理(数据库)算法设计与分析软件工程图形学系统模拟5第一章基本概念清华大学计算机系殷人昆数据结构课件第一章数据结构概论算法与数据结构的预备知识38-6数据结构的基本概念抽象数据类型算法定义性能分析与度量第一章数据结构的概念38-7数据（data）数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数据的分类数值性数据、非数值性数据输入数据、输出数据、存储数据计算机软件=程序+文档+数据数据是指计算机程序执行所用的数据38-8数据元素(dataelement)数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项（DataItem）组成。数据项是具有独立含义的最小标识单位。数据元素又称为元素、结点、记录。数据元素的集合是针对某种特定的应用，相同数据类型的数据元素的一个聚集。如学生组成班级，学生是数据元素，班级是一学生集合。38-9数据在系统开发中的视图数据在系统开发中的讨论范畴分为数据结构+数据内容+数据流数据结构指某一数据元素集合中数据元素之间的关系。数据内容指这些数据元素的具体涵义和内容。数据流指这些数据元素在系统处理过程中是如何传递和变换的。因此，讨论数据结构时,主要不是讨论数据元素的内容和如何处理。38-10数据结构（DataStructures）指某一数据元素集合中的所有数据成员之间的关系。完整的定义为：Data_Structure={D,R,M}其中，D是某一数据元素的集合；R是该集合中所有数据成员之间的关系的有限集合；M是作用在该集合所有数据成员之上的方法（或操作）。38-11例：N个网点之间的连通关系树形关系：n个结点用n-1条边连通。网状关系（或图）：n个结点可以用多条边（0≤e≤n(n-1)/2）连通。e是边数。树形关系网状关系15243615243638-12数据结构是数据的组织形式数据元素间的逻辑关系，即数据的逻辑结构；数据元素及其关系在计算机存储内的表示，即数据的物理结构；数据的运算，即对数据元素施加的操作。逻辑结构用户物理结构公用操作集私用操作集访问使用通过映射到38-13数据的逻辑结构数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；数据的逻辑结构可以看作是从具体问题抽象出来的数据模型（面向应用的）；数据的逻辑结构与数据元素本身的形式、内容无关；数据的逻辑结构与数据元素的相对存储位置无关。38-14数据的逻辑结构分类线性结构线性表非线性结构多维数组广义表树图（或网络）无结构集合38-15线性结构树形结构树二叉树二叉搜索(排序)树1413121123456789103158710119987456623131bindevetclibuser138-16堆结构“最大”堆“最小”堆12354871110291641012115123698738-17图结构网络结构1256431254361133181466516192138-18数据的存储结构数据的存储结构是逻辑结构用计算机语言的实现；数据的存储结构依赖于计算机语言。顺序存储表示链接存储表示索引存储表示散列存储表示38-19数据类型（DataType）数据类型一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称。数据类型的分类基本数据类型构造数据类型C语言中的基本数据类型charintfloatdoublevoid字符型整型浮点型双精度型无值38-20基本数据类型可以看作是计算机中已实现的数据结构。构造数据类型由基本数据类型或构造数据类型组成，在应用中可视为一种数据模型。构造数据类型由不同成分类型构成。数据类型就是数据结构，不过它是从编程者的角度来使用的。数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。38-21抽象数据类型(ADTs:AbstractDataTypes)抽象数据类型由用户定义，用以表示应用问题的数据模型。抽象数据类型由构造数据类型组成,并包括一组相关的服务（或称操作）。三大特征：信息隐蔽数据封装使用与实现相分离。38-22抽象数据类型查找登录删除修改符号表38-23抽象数据类型构成现代程序设计的基础。它的作用是使程序编写得易于编程、易于测试、易于修改。实现信息隐藏，把所有数据和操作分为公有和私有，可减少接口复杂性，从而减少出错机会。实现数据封装，把数据和操作封装在一起，从语义上更加完整。实现使用与实现相分离，使用者只能通过接口上的操作来访问数据，一旦将来修改数据结构，可以使得修改局部化，提高系统灵活性。38-24算法定义定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列算法+数据结构=程序特性：输入有0个或多个输入输出有一个或多个输出(处理结果)确定性每步定义都是确切、无歧义的有穷性算法应在执行有穷步后结束有效性每一条运算应足够基本，可用计算机指令实现38-25几种常用算法的类型三种最基本的常用算法：穷举型：按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。递推型：由已知至i-1规模的解，通过递推，获得规模为i的解。递归型：把规模为N的问题分解成一些规模较小的问题，然后从这些小问题的解构造出大问题的解。38-26穷举法举例求解“百钱买百鸡”问题：公鸡每只5钱，母鸡每只3钱，小鸡3只1钱。求解思路：设公鸡数为x，母鸡数为y，小鸡数为z，则可以得到下面的整数不定方程组：x+y+z=1005*x+3*y+z/3=100利用穷举法可以写出下面的算法程序：#includestdio.hvoidmain(){38-27intx,y,z;for(x=0;x=100;x++)for(y=0;y=100;y++)for(z=0;z=100;z++)if(x+y+z==100&&5*x+3*y+z/3==100)printf(%d%d%d\n,x,y,z);}执行结果38-28穷举法的算法分析虽然上述程序很简单，但分析一下可知，此程序为三重循环，循环次数为1013=1030301，为106量级。如果改为“万钱买万鸡”，循环次数将达1012量级，计算量太大，这正是穷举法的缺点。为此，可考虑对程序做优化。例如，针对“百钱买百鸡”问题，如果用所有的钱去买公鸡，最多可买20只，而用所有的钱去买母鸡，最多可买33只，所以x、y的值范围可限定在20和33。这样，z的值就自然确定了，而不再是一个变量，可剪去第3层循环。38-29与上面程序等效的程序：#includestdio.hvoidmain(){intx,y,z;for(x=0,x=20;x++)for(y=0;y=33;y++){z=100-x-y;if(5*x+3*y+z/3==100)printf(%d%d%d\n,x,y,z);}}这个程序的循环次数只有21*34=714。38-30递推法举例编写程序，用递推法计算斐波那契（Fibonacci）数列的第n项。求解思路：斐波那契（Fibonacci）数列为0,1,l,2,3,5,8,13,…，即：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)，当n1时。用递推法编写的程序为：#includestdio.hintFib(intn){intf0=0,f1=1,f,i;38-31if(n==0||n==1)returnn;for(i=2;i=n;i++){f=f0+f1;//由前两步结果推出当前结果f0=f1;//原前一步当作下一次的前两步f1=f;//当前结果当作下一次的前一步}//在进行向前传递时，要注意传递的时序returnf;}主程序调用方式：intn=7;printf(”Fib(%d)=%d\n”,n,Fib(n));38-32递归法举例所谓递归算法就是在函数过程中直接或间接调用自己。还是求斐波那契数列的问题，相应的递归程序为：intFib(intn){if(n==0||n==1)returnn;//结束项elsereturnFib(n-1)+Fib(n-2);//递归项}递归算法简单，但不能无限递归。因此，算法中需要设置递归结束条件。38-33递归法分析递归法的时间效率较低，原因是重复计算太多。例如，计算Fib(5)，总计算次数为2Fib(6)-1=15。递归调用树Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)38-34例如，编写一个算法，在一个一维整数数组A[n]中查找满足给定值x的元素，找到后函数返回该元素的位置，否则函数返回-1。intSearch(intA[],intx,intn){inti=0;while(in)//通过循环枚举检查if(A[i]==x)returni;//满足要求elsei=i+1;return-1;}更复杂的实例38-35再看递归法。每次递归自己是为了缩小查找区间，逐步逼近到要查找的元素。在函数参数表中增加本次递归调用时的开始查找位置。intSearch(intA[],intx,intn,intstart){if(start==n)return-1;if(A[start]==x)returnstart;elsereturnSearch(A,x,n,start+1);}递归的主调用语句为loc=Search(A,x,n,0)。如果查找失败或查找成功，函数直接返回结果，否则通过递归，到start以后的区间逐个检查。38-36性能分析与度量算法就是为了问题求解。算法的效率是衡量是否具有可计算性的关键。性能分析的目的就是要了解算法的效率。性能（Performance），指算法功能实际执行的功效或表现如何。主要从算法执行的时间和空间效率进行分析。分析方式有：算法的后期测试算法的事前估计38-37算法的后期测试在算法中的某些部位插装时间函数time()，测定算法完成某一功能所花费时间。例如，有一个顺序搜索(SequenialSearch)算法intseqsearch(inta[],intn,intx){//在a[0],…,a[n-1]中搜索xinti=0;while(in&&a[i]!=x)i++;if(i==n)return-1;returni;}38-38插装time()后的计时程序为doublestart,stop;time(&start);intk=seqsearch(a,n,x);time(&stop);doublerunTime=stop-start;printf(”%d%d\n,n,runTime);可以测算。但受限于硬件设备和操作系统、编译器等，测算比较有一定困难。38-39算法的事前估计空间复杂度度量存储空间的固定部分附加存储空间，常数、简单变量、定长成分（如数组元素、结构成分、对象的数据成员等）变量所占空间可变部分尺寸与问题规模有关的成分变量所占空间、递归栈所用空间、通过ma