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