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

数据结构数据结构东南大学计算机学院东南大学计算机学院 XXXX1感谢你的观看2019年8月23数据结构东南大学计算机学院XX1感谢你的观看2019年8月课程程说明明n课程编号：课程编号：09002041n授课学时：授课学时：32学时（学时（1至至16周，周，2学时学时/周）周）n课程分类：选修课程分类：选修n答疑地点：计算机楼答疑地点：计算机楼532，每周，每周1次次(周一上午周一上午)n考核形式：考核形式：r期末笔试期末笔试80%+平时成绩平时成绩20%r期末考试实行开卷方式期末考试实行开卷方式n作业：作业：r从布置作业起，到下一次课前两天从布置作业起，到下一次课前两天(周日周日23:00)r电子版，提交到教务处网站上的课程中心电子版，提交到教务处网站上的课程中心r文件命名文件命名(04012501_XX)，文件格式，文件格式(.pdf、.doc、.docx、.jpg)，大小，大小500Kn联系方式联系方式r电话电话:rEmail:2感谢你的观看2019年8月23课程说明课程编号：090020412感谢你的观看2019年8教材教材n殷人昆殷人昆,数据结构数据结构用面向对象方法与用面向对象方法与C+描述（第描述（第2版）版）,清华大学出版社清华大学出版社,2007n参考书目参考书目r金远平，金远平，数据结构数据结构C+描述描述，清华大学出版社，清华大学出版社，2005rW.Ford and W.Topp,Data Structures with C+,清华大学出版社（影印版）清华大学出版社（影印版）,19973感谢你的观看2019年8月23教材殷人昆,数据结构用面向对象方法与C+描述（第2版数据数据结构的重要性构的重要性n计算机核心课程计算机核心课程n许多课程的基础许多课程的基础n考研、找工作须复习的一门课考研、找工作须复习的一门课4操作系统操作系统软件工程软件工程编译原理编译原理人工智能人工智能图形学图形学数据库数据库数据结构数据结构感谢你的观看2019年8月23数据结构的重要性计算机核心课程4操作系统软件工程编译原理人第一章第一章 绪论绪论东南大学计算机学院东南大学计算机学院 XXXX5感谢你的观看2019年8月23第一章绪论东南大学计算机学院XX5感谢你的观看2019年本章主要内容本章主要内容n数据结构的基本概念数据结构的基本概念n数据的逻辑结构数据的逻辑结构n数据的存储结构数据的存储结构n抽象数据类型抽象数据类型n算法定义算法定义n算法性能分析与度量算法性能分析与度量6感谢你的观看2019年8月23本章主要内容数据结构的基本概念6感谢你的观看2019年8月2数据数据结构的基本概念构的基本概念n数据数据n数据元素数据元素n数据结构数据结构7感谢你的观看2019年8月23数据结构的基本概念数据7感谢你的观看2019年8月23数据数据结构的基本概念构的基本概念n数据数据r信息的载体（殷人昆）信息的载体（殷人昆）r信息的一种符号表示（严蔚敏）信息的一种符号表示（严蔚敏）r描述事物的符号记录（维基）描述事物的符号记录（维基）r在计算机科学中，数据指能输入到计算机中并被计在计算机科学中，数据指能输入到计算机中并被计算机程序识别和处理的符号的集合。算机程序识别和处理的符号的集合。8感谢你的观看2019年8月23数据结构的基本概念数据8感谢你的观看2019年8月23数据数据结构的基本概念构的基本概念n数数据据n数数据据元元素素r数数据据的的基基本本单单位位。在在计计算算机机程程序序中中常常作作为为一一个个整整体体进进行行考考虑虑和和处处理理。r如如学学生生组组成成班班级级，学学生生是是数数据据元元素素，班班级级是是学学生生集集合合。9感谢你的观看2019年8月23数据结构的基本概念数据9感谢你的观看2019年8月23数据数据结构的基本概念构的基本概念n数数据据n数数据据元元素素n数数据据结结构构r某某一一数数据据元元素素集集合合中中数数据据元元素素之之间间的的关关系系。r形形式式化化定定义义：Data_Structure=D,RD 是是数数据据元元素素的的集集合合；R R 是是数数据据元元素素之之间间关关系系的的有有限限集集合合。10感谢你的观看2019年8月23数据结构的基本概念数据10感谢你的观看2019年8月23数据的数据的逻辑结构构n数据元素及其之间的抽象关系数据元素及其之间的抽象关系r集合集合r线状结构线状结构r树状结构树状结构r图或网状结构图或网状结构11感谢你的观看2019年8月23数据的逻辑结构数据元素及其之间的抽象关系11感谢你的观看20数据的数据的逻辑结构构n数数据据元元素素及及其其之之间间的的抽抽象象关关系系r集集合合r线线状状结结构构r树树状状结结构构r图图或或网网状状结结构构12感谢你的观看2019年8月23数据的逻辑结构数据元素及其之间的抽象关系12感谢你的观看20数据的数据的逻辑结构构n数数据据元元素素及及其其之之间间的的抽抽象象关关系系r集集合合r线线状状结结构构r树树状状结结构构r图图或或网网状状结结构构13感谢你的观看2019年8月23数据的逻辑结构数据元素及其之间的抽象关系13感谢你的观看20数据的数据的逻辑结构构n数数据据元元素素及及其其之之间间的的抽抽象象关关系系r集集合合r线线状状结结构构r树树状状结结构构r图图或或网网状状结结构构14感谢你的观看2019年8月23数据的逻辑结构数据元素及其之间的抽象关系14感谢你的观看20数据的数据的逻辑结构构n数数据据元元素素及及其其之之间间的的抽抽象象关关系系r集集合合r线线状状结结构构r树树状状结结构构r图图或或网网状状结结构构15115437121768图结构图结构网状结构网状结构感谢你的观看2019年8月23数据的逻辑结构数据元素及其之间的抽象关系1511543712数据的存数据的存储结构构n数据及其逻辑结构在计算机中的表示，实质上数据及其逻辑结构在计算机中的表示，实质上是存储器的分配是存储器的分配r顺序存储结构顺序存储结构r链接存储结构链接存储结构r索引存储结构索引存储结构r散列存储结构散列存储结构16感谢你的观看2019年8月23数据的存储结构数据及其逻辑结构在计算机中的表示，实质上是存储数据的存数据的存储结构构n数数据据及及其其逻逻辑辑结结构构在在计计算算机机中中的的表表示示，实实质质上上是是存存储储器器的的分分配配r顺顺序序存存储储结结构构r链链接接存存储储结结构构r索索引引存存储储结结构构r散散列列存存储储结结构构17存储（存储（bat,cat,eat）起始地址batcateat感谢你的观看2019年8月23数据的存储结构数据及其逻辑结构在计算机中的表示，实质上是存储数据的存数据的存储结构构n数数据据及及其其逻逻辑辑结结构构在在计计算算机机中中的的表表示示，实实质质上上是是存存储储器器的的分分配配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地址地址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、float、double+、-、*、/、%、=、=、!=、=r构造数据类型构造数据类型21Typedef struct double data100;int length;DataList;感谢你的观看2019年8月23抽象数据类型数据类型：一组值的集合以及一组相关的操作21Ty抽象数据抽象数据类型型n抽象数据类型：由用户定义，表示问题的数据抽象数据类型：由用户定义，表示问题的数据模型模型r由其他数据类型组成，并包括一组相关操作由其他数据类型组成，并包括一组相关操作n三大特征三大特征r信息隐藏、数据封装、使用与实现分离信息隐藏、数据封装、使用与实现分离22class Circle /对象对象:几何圆几何圆 float r;/圆的半径圆的半径public:Circle(float r);/构造函数，创建一个半径为构造函数，创建一个半径为r的对象实例的对象实例 float Circumference();/返回该实例的周长返回该实例的周长 float Area();/返回该实例的面积返回该实例的面积;感谢你的观看2019年8月23抽象数据类型抽象数据类型：由用户定义，表示问题的数据模型22抽象数据抽象数据类型型n抽象数据类型三大特征抽象数据类型三大特征r信息隐藏：把所有数据和操作分为公有和私有，可信息隐藏：把所有数据和操作分为公有和私有，可减少接口复杂性，从而减少出错机会。减少接口复杂性，从而减少出错机会。r数据封装：把数据和操作封装在一起，从语义上更数据封装：把数据和操作封装在一起，从语义上更加完整。加完整。r使用与实现相分离：使用者只能通过接口上的操作使用与实现相分离：使用者只能通过接口上的操作来访问数据，一旦将来修改数据结构，可以使得修来访问数据，一旦将来修改数据结构，可以使得修改局部化，提高系统灵活性。改局部化，提高系统灵活性。23感谢你的观看2019年8月23抽象数据类型抽象数据类型三大特征23感谢你的观看2019年8抽象数据抽象数据类型型n作业：二维向量的抽象数据类型作业：二维向量的抽象数据类型r数据类型数据类型r操作：加、减、点乘、叉乘操作：加、减、点乘、叉乘24感谢你的观看2019年8月23抽象数据类型作业：二维向量的抽象数据类型24感谢你的观看20算法定算法定义n是对特定问题求解步骤的一种描述，是指令的是对特定问题求解步骤的一种描述，是指令的有限序列。有限序列。n算法五大特性算法五大特性r输入：有输入：有0个或多个输入个或多个输入r输出：有输出：有1个或多个输出个或多个输出r有限性：算法有限步结束，指令有限时间完成有限性：算法有限步结束，指令有限时间完成r确定性：每条指令有确切含义确定性：每条指令有确切含义r可行性：每个运算可由计算机有限条指令完成可行性：每个运算可由计算机有限条指令完成25感谢你的观看2019年8月23算法定义是对特定问题求解步骤的一种描述，是指令的有限序列。2算法定算法定义n算法举例算法举例r“百钱买百鸡百钱买百鸡”问题：公鸡每只问题：公鸡每只5钱，母鸡每只钱，母鸡每只3钱，小鸡钱，小鸡3只只1钱，钱，100钱买钱买100只鸡，问各种鸡可只鸡，问各种鸡可买多少只买多少只?令公鸡母鸡小鸡分别为令公鸡母鸡小鸡分别为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算法定义算法举例26例：for(x=0;x=100;x+算法定算法定义n算法举例算法举例r欧几里德算法欧几里德算法辗转相除法求两个自然数辗转相除法求两个自然数m和和n的最大公约数的最大公约数27输入输入:m,n输出输出:m和和n的最大公约数的最大公约数r=m%n;循环直到循环直到r等于等于0 m=n;n=r;r=m%n;输出输出n感谢你的观看2019年8月23算法定义算法举例27输入:m,n感谢你的观看2019年8月算法性能分析与度量算法性能分析与度量n算法效率的评价方法：算法效率的评价方法：r事后统计事后统计将算法实现，统计其时间和空间开销将算法实现，统计其时间和空间开销r事前分析事前分析对算法所消耗时间和空间资源的一种估算方法对算法所消耗时间和空间资源的一种估算方法n算法效率的分析算法效率的分析r时间复杂度时间复杂度r空间复杂度空间复杂度28time(&start);algorithm();time(&stop);runTime=stop-start;感谢你的观看2019年8月23算法性能分析与度量算法效率的评价方法：28time(&st算法性能分析与度量算法性能分析与度量n算法的时间复杂度算法的时间复杂度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算法性能分析与度量算法的时间复杂度29算法的运行时间=每算法性能分析与度量算法性能分析与度量n算法的时间复杂度算法的时间复杂度r算法的运行时间可表示为基本语句执行次数，它是算法的运行时间可表示为基本语句执行次数，它是问题规模的一个函数问题规模的一个函数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，则当，则当 nn0(=1)时，有时，有3n3+2n23n3，T(n)=(n3)36感谢你的观看2019年8月23算法性能分析与度量算法的时间复杂度36感谢你的观看2019年算法性能分析与度量算法性能分析与度量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)时，有时，有3n3+2n25n3及及3n3+2n23n3（无（无穷多个），穷多个），T(n)=(n3)37感谢你的观看2019年8月23算法性能分析与度量算法的时间复杂度37感谢你的观看2019年算法性能分析与度量算法性能分析与度量n算法的时间复杂度算法的时间复杂度r常见的时间复杂度常见的时间复杂度r(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)(n!)38T(n)n02nn3nn2logn感谢你的观看2019年8月23算法性能分析与度量算法的时间复杂度38T(n)n02nn3n算法性能分析与度量算法性能分析与度量n算法的空间复杂度算法的空间复杂度r指算法在执行过程中所需最大存储空间指算法在执行过程中所需最大存储空间r空间复杂性的渐进分析空间复杂性的渐进分析39S(n)=O(f(n)O(log2n)?=O(log3n)O(2n)?=O(3n)感谢你的观看2019年8月23算法性能分析与度量算法的空间复杂度39S(n)=O(f(n)