数据结构模板.ppt.ppt
数据结构,1,课程说明,2,教材,殷人昆,数据结构用面向对象方法与C+描述（第2版）,清华大学出版社,2007参考书目金远平，数据结构C+描述，清华大学出版社，2005W.Ford and W.Topp,Data Structures with C+,清华大学出版社（影印版）,1997,3,数据结构的重要性,计算机核心课程许多课程的基础考研、找工作须复习的一门课,4,本章主要内容,数据结构的基本概念数据的逻辑结构数据的存储结构抽象数据类型算法定义算法性能分析与度量,5,数据结构的基本概念,数据数据元素数据结构,6,数据结构的基本概念,数据信息的载体（殷人昆）信息的一种符号表示（严蔚敏）描述事物的符号记录（维基）在计算机科学中，数据指能输入到计算机中并被计算机程序识别和处理的符号的集合。,7,数据结构的基本概念,数据数据元素数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。如学生组成班级，学生是数据元素，班级是学生集合。,8,数据结构的基本概念,数据数据元素数据结构某一数据元素集合中数据元素之间的关系。形式化定义：Data_Structure=D,RD 是数据元素的集合；R 是数据元素之间关系的有限集合。,9,数据的逻辑结构,数据元素及其之间的抽象关系集合线状结构树状结构图或网状结构,10,数据的逻辑结构,数据元素及其之间的抽象关系集合线状结构树状结构图或网状结构,11,数据的逻辑结构,数据元素及其之间的抽象关系集合线状结构树状结构图或网状结构,12,数据的逻辑结构,数据元素及其之间的抽象关系集合线状结构树状结构图或网状结构,13,数据的逻辑结构,数据元素及其之间的抽象关系集合线状结构树状结构图或网状结构,14,图结构,网状结构,数据的存储结构,数据及其逻辑结构在计算机中的表示，实质上是存储器的分配顺序存储结构链接存储结构索引存储结构散列存储结构,15,数据的存储结构,数据及其逻辑结构在计算机中的表示，实质上是存储器的分配顺序存储结构链接存储结构索引存储结构散列存储结构,16,存储（bat,cat,eat）,bat,cat,eat,数据的存储结构,数据及其逻辑结构在计算机中的表示，实质上是存储器的分配顺序存储结构链接存储结构索引存储结构散列存储结构,17,存储（bat,cat,eat）,0320,0200,0256,数据的存储结构,数据及其逻辑结构在计算机中的表示，实质上是存储器的分配顺序存储结构链接存储结构索引存储结构散列存储结构,18,文件2,文件3,文件1,地址2,地址3,地址1,数据的存储结构,数据及其逻辑结构在计算机中的表示，实质上是存储器的分配顺序存储结构链接存储结构索引存储结构散列存储结构,19,100，400，500，800，900,1,2,9,8,3,4,5,6,7,100,400,500,800,900,hash(key)=key/100,抽象数据类型,数据类型：一组值的集合以及一组相关的操作基本数据类型C语言中int、float、double+、-、*、/、%、=、=、!=、=构造数据类型,20,Typedef struct double data100;int length;DataList;,抽象数据类型,抽象数据类型：由用户定义，表示问题的数据模型由其他数据类型组成，并包括一组相关操作三大特征信息隐藏、数据封装、使用与实现分离,21,class Circle/对象:几何圆 float r;/圆的半径public:Circle(float r);/构造函数，创建一个半径为r的对象实例 float Circumference();/返回该实例的周长 float Area();/返回该实例的面积;,抽象数据类型,抽象数据类型三大特征信息隐藏：把所有数据和操作分为公有和私有，可减少接口复杂性，从而减少出错机会。数据封装：把数据和操作封装在一起，从语义上更加完整。使用与实现相分离：使用者只能通过接口上的操作来访问数据，一旦将来修改数据结构，可以使得修改局部化，提高系统灵活性。,22,抽象数据类型,作业：二维向量的抽象数据类型数据类型操作：加、减、点乘、叉乘,23,算法定义,是对特定问题求解步骤的一种描述，是指令的有限序列。算法五大特性输入：有0个或多个输入输出：有1个或多个输出有限性：算法有限步结束，指令有限时间完成确定性：每条指令有确切含义可行性：每个运算可由计算机有限条指令完成,24,算法定义,算法举例“百钱买百鸡”问题：公鸡每只5钱，母鸡每只3钱，小鸡3只1钱，100钱买100只鸡，问各种鸡可买多少只?令公鸡母鸡小鸡分别为x,y,z只,25,例：for(x=0;x=100;x+)for(y=0;y=100;y+)for(z=0;z=100;z+)if(x+y+z=100,算法定义,算法举例欧几里德算法辗转相除法求两个自然数m和n的最大公约数,26,输入:m,n输出:m和n的最大公约数r=m%n;循环直到r等于0 m=n;n=r;r=m%n;输出n,算法性能分析与度量,算法效率的评价方法：事后统计将算法实现，统计其时间和空间开销事前分析对算法所消耗时间和空间资源的一种估算方法算法效率的分析时间复杂度空间复杂度,27,time(,算法性能分析与度量,算法的时间复杂度,28,算法的运行时间=每条语句执行时间之和,例：for(i=0;in;i+)for(j=0;jn;j+)cij=0;for(k=0;kn;k+)cij=cij+aik*bkj;,算法性能分析与度量,算法的时间复杂度算法的运行时间可表示为基本语句执行次数，它是问题规模的一个函数称这个函数的渐进阶为算法的时间复杂度,29,问题规模：n基本语句：cij=0cij=cij+aik*bkj时间复杂度:O(n3),例：for(i=0;in;i+)for(j=0;jn;j+)cij=0;for(k=0;kn;k+)cij=cij+aik*bkj;,算法性能分析与度量,算法的时间复杂度大O表示法：若存在两个正的常数c和n0，对于任意nn0，都有T(n)cf(n)，则称T(n)=O(f(n),30,表示当问题规模充分大时在渐进意义下的阶,算法性能分析与度量,算法的时间复杂度大O表示法：若存在两个正的常数c和n0，对于任意nn0，都有T(n)cf(n)，则称T(n)=O(f(n)例1：T(n)=3n+2当n2时，3n+2 3n+n=4n因此T(n)=O(n),31,算法性能分析与度量,算法的时间复杂度大O表示法：若存在两个正的常数c和n0，对于任意nn0，都有T(n)cf(n)，则称T(n)=O(f(n)例2：T(n)=10n2+4n+2当n2时，10n2+4n+2 10n2+5n又有当n5时，10n2+5n 10n2+n2=11n2因此T(n)=O(n2),32,算法性能分析与度量,算法的时间复杂度大O表示法：若存在两个正的常数c和n0，对于任意nn0，都有T(n)cf(n)，则称T(n)=O(f(n)作业：求解T(n)=amnm+am-1nm-1+a2n2+a1n+a0，并给出证明过程,33,算法性能分析与度量,算法的时间复杂度T(n)=O(f(n)若存在两个正的常数c和n0，对于任意nn0，都有T(n)cf(n)，则称T(n)=O(f(n)给出算法复杂度的上界，不可能比c*f(n)更大例：T(n)=6*2n+n2当n4时，6*2n+n2 6*2n+2n=7*2n因此T(n)=O(2n),34,算法性能分析与度量,算法的时间复杂度T(n)=(f(n)若存在c 0，和正整数n01，使得当nn0时，有T(n)c*f(n)成立。给出算法复杂度的下界，不可能比c*f(n)更小例：T(n)=3n3+2n2，取c=3，n0=1，f(n)=n3，则当 nn0(=1)时，有3n3+2n23n3，T(n)=(n3),35,算法性能分析与度量,算法的时间复杂度T(n)=(f(n)若存在c1,c20，和正整数n01，使得当nn0时，总有 T(n)c1*f(n)且T(n)c2*f(n)成立，即T(n)=O(f(n)与T(n)=(f(n)都成立。给出了算法时间复杂度的上界和下界e.g.T(n)=3n3+2n2，c1=5，取c2=3，n0=1，f(n)=n3，则当nn0(=1)时，有3n3+2n25n3及3n3+2n23n3（无穷多个），T(n)=(n3),36,算法性能分析与度量,算法的时间复杂度常见的时间复杂度(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)(n!),37,算法性能分析与度量,算法的空间复杂度指算法在执行过程中所需最大存储空间空间复杂性的渐进分析,38,S(n)=O(f(n),O(log2n)?=O(log3n)O(2n)?=O(3n),
