数据结构-用面向对象方法与C++描述.ppt课件.ppt

1、数据结构数据结构东南大学计算机学院东南大学计算机学院 XXXX1感谢你的观看2019年8月23课程说明课程说明n课程编号：课程编号：09002041n授课学时：授课学时：32学时（学时（1至至16周，周，2学时学时/周）周）n课程分类：选修课程分类：选修n答疑地点：计算机楼答疑地点：计算机楼532，每周，每周1次次(周一上午周一上午)n考核形式：考核形式：r期末笔试期末笔试80%+平时成绩平时成绩20%r期末考试实行开卷方式期末考试实行开卷方式n作业：作业：r从布置作业起，到下一次课前两天从布置作业起，到下一次课前两天(周日周日23:00)r电子版，提交到教务处网站上的课程中心电子版，提交到教

2、务处网站上的课程中心r文件命名文件命名(04012501_XX)，文件格式，文件格式(.pdf、.doc、.docx、.jpg)，大小，大小500Kn联系方式联系方式r电话电话: rEmail: 2感谢你的观看2019年8月23教材教材n殷人昆殷人昆,数据结构数据结构用面向对象方法与用面向对象方法与C+描述（第描述（第2版）版）, 清华大学出版社清华大学出版社, 2007n参考书目参考书目r金远平，金远平，数据结构数据结构C+描述描述，清华大学出版社，清华大学出版社，2005rW. Ford and W. Topp, Data Structures with C+, 清华大学出版社（影印版）清

3、华大学出版社（影印版）, 19973感谢你的观看2019年8月23数据结构的重要性数据结构的重要性n计算机核心课程计算机核心课程n许多课程的基础许多课程的基础n考研、找工作须复习的一门课考研、找工作须复习的一门课4操作系统操作系统软件工程软件工程编译原理编译原理人工智能人工智能图形学图形学数据库数据库数据结构数据结构感谢你的观看2019年8月23第一章第一章 绪论绪论东南大学计算机学院东南大学计算机学院 XXXX5感谢你的观看2019年8月23本章主要内容本章主要内容n数据结构的基本概念数据结构的基本概念n数据的逻辑结构数据的逻辑结构n数据的存储结构数据的存储结构n抽象数据类型抽象数据类型n算

4、法定义算法定义n算法性能分析与度量算法性能分析与度量6感谢你的观看2019年8月23数据结构的基本概念数据结构的基本概念n数据数据n数据元素数据元素n数据结构数据结构7感谢你的观看2019年8月23数据结构的基本概念数据结构的基本概念n数据数据r信息的载体（殷人昆）信息的载体（殷人昆）r信息的一种符号表示（严蔚敏）信息的一种符号表示（严蔚敏）r描述事物的符号记录（维基）描述事物的符号记录（维基）r在计算机科学中，数据指能输入到计算机中并被在计算机科学中，数据指能输入到计算机中并被计算机程序识别和处理的符号的集合。计算机程序识别和处理的符号的集合。8感谢你的观看2019年8月23数据结构的基本概

5、念数据结构的基本概念n数据数据n数据元素数据元素r数据的基本单位。在计算机程序中常作为一个整数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理体进行考虑和处理。r如学生组成班级，学生是数据元素，班级如学生组成班级，学生是数据元素，班级是学生是学生集合集合。9感谢你的观看2019年8月23数据结构的基本概念数据结构的基本概念n数据数据n数据元素数据元素n数据结构数据结构r某一数据元素集合中数据元素之间的关系。某一数据元素集合中数据元素之间的关系。r形式化定义：形式化定义：Data_Structure = D, RD 是数据是数据元素的集合；元素的集合；是数据元素之间关系是数据元素之间关系

6、的有限的有限集合。集合。10感谢你的观看2019年8月23数据的逻辑结构数据的逻辑结构n数据元素及其之间的抽象关系数据元素及其之间的抽象关系r集合集合r线状结构线状结构r树状结构树状结构r图或网状结构图或网状结构11感谢你的观看2019年8月23数据的逻辑结构数据的逻辑结构n数据元素及其之间的抽象关系数据元素及其之间的抽象关系r集合集合r线状结构线状结构r树状结构树状结构r图或图或网状网状结构结构12感谢你的观看2019年8月23数据的逻辑结构数据的逻辑结构n数据元素及其之间的抽象关系数据元素及其之间的抽象关系r集合集合r线状结构线状结构r树状结构树状结构r图或网状结构图或网状结构13感谢你的

7、观看2019年8月23数据的逻辑结构数据的逻辑结构n数据元素及其之间的抽象关系数据元素及其之间的抽象关系r集合集合r线状结构线状结构r树状结构树状结构r图或网状结构图或网状结构14感谢你的观看2019年8月23数据的逻辑结构数据的逻辑结构n数据元素及其之间的抽象关系数据元素及其之间的抽象关系r集合集合r线状结构线状结构r树状结构树状结构r图或网状结构图或网状结构15115437121768图结构图结构网状结构网状结构感谢你的观看2019年8月23数据的存储结构数据的存储结构n数据及其逻辑结构在计算机中的表示，实质上数据及其逻辑结构在计算机中的表示，实质上是存储器的分配是存储器的分配r顺序存储结

8、构顺序存储结构r链接存储结构链接存储结构r索引存储结构索引存储结构r散列存储结构散列存储结构16感谢你的观看2019年8月23数据的存储结构数据的存储结构n数据及其逻辑结构在计算机中的表示，实质上数据及其逻辑结构在计算机中的表示，实质上是存储器的分配是存储器的分配r顺序存储结构顺序存储结构r链接存储结构链接存储结构r索引存储结构索引存储结构r散列存储结构散列存储结构17存储（存储（bat, cat, eat）起始地址batcateat感谢你的观看2019年8月23数据的存储结构数据的存储结构n数据及其逻辑结构在计算机中的表示，实质上数据及其逻辑结构在计算机中的表示，实质上是存储器的分配是存储器

9、的分配r顺序存储结构顺序存储结构r链接存储结构链接存储结构r索引存储结构索引存储结构r散列存储结构散列存储结构18存储（存储（bat, cat, eat）bat0200cat03200320eat02000256感谢你的观看2019年8月23数据的存储结构数据的存储结构n数据及其逻辑结构在计算机中的表示，实质上数据及其逻辑结构在计算机中的表示，实质上是存储器的分配是存储器的分配r顺序存储结构顺序存储结构r链接存储结构链接存储结构r索引存储结构索引存储结构r散列存储结构散列存储结构19文件名文件名1地址地址1文件文件2文件名文件名2地址地址2文件名文件名3地址地址3文件文件3文件文件1地址地址2

10、地址地址3地址地址1感谢你的观看2019年8月23数据的存储结构数据的存储结构n数据及其逻辑结构在计算机中的表示，实质上数据及其逻辑结构在计算机中的表示，实质上是存储器的分配是存储器的分配r顺序存储结构顺序存储结构r链接存储结构链接存储结构r索引存储结构索引存储结构r散散列存储结构列存储结构20100，400，500，800，900129834567100400500800900hash(key)=key/100感谢你的观看2019年8月23抽象数据类型抽象数据类型n数据类型：一组值的集合以及一组相关的操作数据类型：一组值的集合以及一组相关的操作r基本数据类型基本数据类型C语言中语言中int、

11、float、double+、-、*、/、%、=、=、!=、=r构造数据类型构造数据类型21Typedef struct double data100; int length; DataList;感谢你的观看2019年8月23抽象数据类型抽象数据类型n抽象数据类型：由用户定义，表示问题的数据抽象数据类型：由用户定义，表示问题的数据模型模型r由其他数据类型组成，并包括一组相关操作由其他数据类型组成，并包括一组相关操作n三大特征三大特征r信息隐藏、数据封装、使用与实现分离信息隐藏、数据封装、使用与实现分离22class Circle / 对象对象: 几何圆几何圆 float r; / 圆的半径圆的半

12、径public: Circle(float r); / 构造函数，创建一个半径为构造函数，创建一个半径为r的对象实例的对象实例 float Circumference( ); / 返回该实例的周长返回该实例的周长 float Area( ); / 返回该实例的面积返回该实例的面积;感谢你的观看2019年8月23抽象数据类型抽象数据类型n抽象数据类型三大特征抽象数据类型三大特征r信息隐藏：把所有数据和操作分为公有和私有，信息隐藏：把所有数据和操作分为公有和私有，可减少接口复杂性，从而减少出错机会。可减少接口复杂性，从而减少出错机会。r数据封装：把数据和操作封装在一起，从语义上数据封装：把数据和操

13、作封装在一起，从语义上更加完整。更加完整。r使用与实现相分离：使用者只能通过接口上的操使用与实现相分离：使用者只能通过接口上的操作来访问数据，一旦将来修改数据结构，可以使作来访问数据，一旦将来修改数据结构，可以使得修改局部化，提高系统灵活性。得修改局部化，提高系统灵活性。23感谢你的观看2019年8月23抽象数据类型抽象数据类型n作业：二维向量的抽象数据类型作业：二维向量的抽象数据类型r数据类型数据类型r操作：加、减、点乘、叉乘操作：加、减、点乘、叉乘24感谢你的观看2019年8月23算法定义算法定义n是对特定问题求解步骤的一种描述，是指令的是对特定问题求解步骤的一种描述，是指令的有限序列。有

14、限序列。n算法五大特性算法五大特性r输入：有输入：有0个或多个输入个或多个输入r输出：有输出：有1个或多个输出个或多个输出r有限性：算法有限步结束，指令有限时间完成有限性：算法有限步结束，指令有限时间完成r确定性：每条指令有确切含义确定性：每条指令有确切含义r可行性：每个运算可由计算机有限条指令完成可行性：每个运算可由计算机有限条指令完成25感谢你的观看2019年8月23算法定义算法定义n算法举例算法举例r“百钱买百鸡百钱买百鸡”问题：公鸡每只问题：公鸡每只5钱，母鸡每只钱，母鸡每只3钱，小鸡钱，小鸡3只只1钱，钱，100钱买钱买100只鸡，问各种鸡可只鸡，问各种鸡可买多少只买多少只?令公鸡母

15、鸡小鸡分别为令公鸡母鸡小鸡分别为x,y,z只只26例：例：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 & z%3=0) printf(“%d,%d,%d”,x,y,z); 感谢你的观看2019年8月23算法定义算法定义n算法举例算法举例r欧几里德算法欧几里德算法辗转相除法求两个自然数辗转相除法求两个自然数m和和n的最大公约数的最大公约数27输入输入: m,n输出输出: m和和n的最大公约数的最大公约数r = m % n;循环直到循环直到r等于等于0 m = n; n =

16、 r; r = m % n;输出输出n感谢你的观看2019年8月23算法性能分析与度量算法性能分析与度量n算法效率的评价方法：算法效率的评价方法：r事后统计事后统计将算法实现，统计其时间和空间开销将算法实现，统计其时间和空间开销r事前分析事前分析对算法所消耗时间和空间资源的一种估算方法对算法所消耗时间和空间资源的一种估算方法n算法效率的分析算法效率的分析r时间复杂度时间复杂度r空间复杂度空间复杂度28time (&start);algorithm();time (&stop); runTime = stop - start;感谢你的观看2019年8月23算法性能分析与度量算法性能分析与度量n算

17、法的时间复杂度算法的时间复杂度29算法的运行时间算法的运行时间 = = 每条语句执行时间之和每条语句执行时间之和执行次数执行次数执行一次的时间执行一次的时间例：例：for(i=0;in;i+) for(j=0;jn;j+) cij=0; for(k=0;kn;k+) cij=cij+aik*bkj; 指令系统、代码质量有关指令系统、代码质量有关每条语句执行次数之和每条语句执行次数之和基本语句执行次数基本语句执行次数感谢你的观看2019年8月23算法性能分析与度量算法性能分析与度量n算法的时间复杂度算法的时间复杂度r算法的运行时间可表示为基本语句执行次数，它算法的运行时间可表示为基本语句执行次数

18、，它是问题规模的一个函数是问题规模的一个函数r称这个函数的渐进阶为算法的时间复杂度称这个函数的渐进阶为算法的时间复杂度30问题规模：问题规模：n基本语句：基本语句：cij=0cij=cij+aik*bkj时间复杂度时间复杂度: O(n3)例：例：for(i=0;in;i+) for(j=0;jn;j+) cij=0; for(k=0;k 0，和正整数，和正整数n01，使得当，使得当nn0时，时，有有T(n)c*f(n)成立。成立。给出算法复杂度的下界，不可能比给出算法复杂度的下界，不可能比c*f(n)更小更小例：例： T(n)=3n3+2n2，取，取c=3，n0=1，f(n)=n3，则当，则当

19、 nn0(=1)时，有时，有3n3+2n23n3，T(n)=(n3)36感谢你的观看2019年8月23算法性能分析与度量算法性能分析与度量n算法的时间复杂度算法的时间复杂度rT(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)时，有时，有3

20、n3+2n25n3及及3n3+2n23n3（无（无穷多个），穷多个），T(n)= (n3)37感谢你的观看2019年8月23算法性能分析与度量算法性能分析与度量n算法的时间复杂度算法的时间复杂度r常见的时间复杂度常见的时间复杂度r(1)(log2n) (n) (nlog2n) (n2) (n3) (2n) (n!)38T(n)n02nn3nn2logn感谢你的观看2019年8月23算法性能分析与度量算法性能分析与度量n算法的空间复杂度算法的空间复杂度r指算法在执行过程中所需最大存储空间指算法在执行过程中所需最大存储空间r空间复杂性的渐进分析空间复杂性的渐进分析39S(n)=O(f(n)O(log2n) ?= O(log3n)O(2n) ?= O(3n)感谢你的观看2019年8月23