数据结构PPT.ppt

《数据结构PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构PPT.ppt（40页珍藏版）》请在优知文库上搜索。

1、1数据结构数据结构1绪论绪论2教学安排教学安排共共64学时学时讲课讲课48学时：学时：每周每周3学时学时上机上机16学时学时单周单周2学时学时成绩考核成绩考核平时表现平时表现30%：课堂提问、考勤：课堂提问、考勤期末考试期末考试70%3教材与参考书教材与参考书教材：教材：唐策善唐策善李龙澎李龙澎黄刘生黄刘生数据结构用数据结构用C语言描述语言描述高等教育出版社高等教育出版社4教材与参考书教材与参考书参考书参考书严蔚敏严蔚敏吴伟民吴伟民数据结构（数据结构（C语言版）语言版）清华大学出版社清华大学出版社5教材与参考书教材与参考书参考书参考书Ellis Horowitz, Sartaj Sahni,

2、Susan Anderson-FreedFundamentals of data structures in C6主要内容主要内容1.1 本课程研究的主要内容本课程研究的主要内容1.2 数据结构的概念数据结构的概念基本术语基本术语数据、数据元素、数据项数据、数据元素、数据项逻辑结构、物理结构逻辑结构、物理结构什么是数据结构什么是数据结构1.3 算法和算法分析算法和算法分析算法的概念算法的概念算法的复杂度算法的复杂度71.1 本课程研究的主要内容本课程研究的主要内容8数据结构研究的主要内容数据结构研究的主要内容Niklaus Wirth（Pascal之父）之父） 程序程序=算法算法+数据结构数据

3、结构为计算机处理问为计算机处理问题编制的一组指题编制的一组指令集令集处理问题的处理问题的策略策略问题的数学问题的数学模型模型9数据结构研究的主要内容数据结构研究的主要内容使用计算机解决问题的步骤使用计算机解决问题的步骤从具体问题抽象出数学模型从具体问题抽象出数学模型设计求解此数学模型的算法设计求解此数学模型的算法编制程序编制程序10数据结构研究的主要内容数据结构研究的主要内容数值计算的程序设计问题数值计算的程序设计问题结构静力分析计算结构静力分析计算需要编写线性方程组进行求解需要编写线性方程组进行求解全球天气预报全球天气预报需要编写环流模式方程进行求解需要编写环流模式方程进行求解数学模型数学模

4、型数学模型数学模型和数值计算相关的数学模型有线性代数方程、非和数值计算相关的数学模型有线性代数方程、非线性代数方程、常微分方程等，它们的数值解问线性代数方程、常微分方程等，它们的数值解问题是题是计算数学计算数学所要研究的问题所要研究的问题11数据结构研究的主要内容数据结构研究的主要内容非数值计算的程序设计问题非数值计算的程序设计问题求求n个数中的最大值个数中的最大值井字棋人机对弈井字棋人机对弈教学数据库管理系统教学数据库管理系统数学模型？数学模型？这些非数值计算问题的数学模型的表示和求解这些非数值计算问题的数学模型的表示和求解方法就是方法就是数据结构数据结构研究的内容研究的内容12数据结构研究

5、的主要内容数据结构研究的主要内容数据结构是一门研究非数值计算的程数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。它们之间的关系和操作等的学科。13数据结构的应用数据结构的应用数据结构在编译器中的应用数据结构在编译器中的应用数据结构在操作系统中的应用数据结构在操作系统中的应用数据结构在数据库中的应用数据结构在数据库中的应用141.2 数据结构的概念数据结构的概念15什么是数据结构什么是数据结构至今尚未有一个被一致公认的定义，至今尚未有一个被一致公认的定义，不同的人使用该词时所表达的意思有不同的人使用该词时所表达的意思有

6、所不同。所不同。16基本术语：数据基本术语：数据数据数据所有需输入计算机并被程序所处理的对所有需输入计算机并被程序所处理的对象的总称象的总称例如：例如：图书借阅管理系统图书借阅管理系统图书信息：图书信息：登录号登录号书名书名借阅者编号借阅者编号001理论力学理论力学9002002高等数学高等数学9001.17基本术语：数据元素基本术语：数据元素数据元素数据元素数据的基本单位，在程序中常作为一个数据的基本单位，在程序中常作为一个整体考虑和处理整体考虑和处理登录号登录号书名书名借阅者编号借阅者编号001理论力学理论力学9002002高等数学高等数学9001.一个数据元素一个数据元素(一条记录一条记

7、录)18基本术语：数据项基本术语：数据项数据项数据项数据的不可分割的最小单位数据的不可分割的最小单位一个数据元素可由一或多个数据项构成一个数据元素可由一或多个数据项构成登录号登录号书名书名借阅者编号借阅者编号001理论力学理论力学9002002高等数学高等数学9001.3个数据项个数据项19基本术语：逻辑结构基本术语：逻辑结构逻辑结构逻辑结构数据元素间的逻辑关系数据元素间的逻辑关系即在现实世界中的关系即在现实世界中的关系分类分类集合：同在一个集合中集合：同在一个集合中比如同班同学之间比如同班同学之间20基本术语：逻辑结构基本术语：逻辑结构线性结构：一个接一个线性结构：一个接一个比如学生花名册中

8、的记录之间比如学生花名册中的记录之间树形结构：一对多树形结构：一对多比如家谱比如家谱图形结构：多对多图形结构：多对多比如地图比如地图21基本术语：物理结构基本术语：物理结构物理结构物理结构即存储结构即存储结构数据元素在计算机中存储时的关系数据元素在计算机中存储时的关系22基本术语：物理结构基本术语：物理结构例：例：学生花名册学生花名册 数据元素之间的逻辑关系：线性关系数据元素之间的逻辑关系：线性关系学号学号姓名姓名性别性别籍贯籍贯年龄年龄98131张三张三男男北京北京2098164李斯李斯女女上海上海2198165王武王武男男广州广州1998182赵柳赵柳女女香港香港2298224.23基本术

9、语：物理结构基本术语：物理结构顺序存储：各个数据元素在计算机中的顺序存储：各个数据元素在计算机中的存储地址也是线性关系，即连续存放存储地址也是线性关系，即连续存放98131张三张三男男98164李斯李斯女女.第一个数据元素第一个数据元素第二个数据元素第二个数据元素24基本术语：物理结构基本术语：物理结构链式存储：各个数据元素在计算机中的链式存储：各个数据元素在计算机中的存储位置任意，通过指针相互连接起来存储位置任意，通过指针相互连接起来女女李斯李斯98164男男张三张三98131下一个下一个节点的节点的地址地址下一个下一个节点的节点的地址地址25基本术语：物理结构基本术语：物理结构顺序存储结构

10、顺序存储结构逻辑上相邻的结点存储在物理位置相邻逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。储单元的邻接关系来体现。链式存储结构链式存储结构不要求逻辑上相邻的结点在物理位置上不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的也相邻，结点间的逻辑关系是由附加的指针字段表示的。指针字段表示的。26什么是数据结构什么是数据结构 （本教材定义）：按某种逻辑关系组织起（本教材定义）：按某种逻辑关系组织起来的一批数据，应用计算机语言，按一定来的一批数据，应用计算机语言，按一定的存储方式把它们存储在计算机的存储

11、器的存储方式把它们存储在计算机的存储器中，并在这些数据上定义了一个运算的集中，并在这些数据上定义了一个运算的集合，就叫做一个数据结构。合，就叫做一个数据结构。 它一般包含三个方面的内容：它一般包含三个方面的内容： （1）数据元素之间的逻辑关系，即数据的逻）数据元素之间的逻辑关系，即数据的逻辑结构辑结构 （2）数据元素及其关系在计算机存储器内的）数据元素及其关系在计算机存储器内的表示，即数据的存储结构表示，即数据的存储结构/物理结构。物理结构。 （3）数据的运算，即对数据施加的操作。）数据的运算，即对数据施加的操作。27什么是数据结构什么是数据结构例：例：学生名单学生名单学号学号姓名姓名性别性别

12、籍贯籍贯年龄年龄98131张三张三男男北京北京2098164李斯李斯女女上海上海2198165王武王武男男广州广州1998182赵柳赵柳女女香港香港2298224.281.3 算法和算法分析算法和算法分析29算法和算法分析：概念算法和算法分析：概念算法算法(Algorithm)算法是对问题求解步骤的描述算法是对问题求解步骤的描述是指令的有限序列，其中每条指令表示是指令的有限序列，其中每条指令表示一或多个操作一或多个操作30算法和算法分析：概念算法和算法分析：概念算法的特性算法的特性一个正确的算法必须满足一个正确的算法必须满足有穷性：算法在执行有穷步后结束，且每步有穷性：算法在执行有穷步后结束，

13、且每步可在有穷时间内完成可在有穷时间内完成确定性：算法中指令无二义性，且在任何条确定性：算法中指令无二义性，且在任何条件下执行路径唯一件下执行路径唯一可行性：算法中各操作可通过已实现的基本可行性：算法中各操作可通过已实现的基本运算执行有限次完成运算执行有限次完成输入：零或多个输入输入：零或多个输入输出：一或多个输出输出：一或多个输出31算法和算法分析：概念算法和算法分析：概念算法设计的要求算法设计的要求一个好的算法应当满足：一个好的算法应当满足：正确性：算法应能满足具体问题的需求正确性：算法应能满足具体问题的需求可读性：算法应易于阅读和理解可读性：算法应易于阅读和理解健壮性：输入数据非法时，算

14、法也能适当作健壮性：输入数据非法时，算法也能适当作出反应或进行处理出反应或进行处理高效性：算法执行时间短，占用存储空间少高效性：算法执行时间短，占用存储空间少32算法和算法分析：时间复杂度算法和算法分析：时间复杂度程序的执行时间取决于如下因素：程序的执行时间取决于如下因素：算法算法问题的规模问题的规模编程语言编程语言编译程序编译程序硬件性能硬件性能通常只需考虑算法本身和问题的规模通常只需考虑算法本身和问题的规模33算法和算法分析：时间复杂度算法和算法分析：时间复杂度 时间复杂度与渐进时间复杂度时间复杂度与渐进时间复杂度 算法的时间复杂度算法的时间复杂度T(n)是该算法的时间耗费，是该算法的时间

15、耗费，它是该算法所求解问题规模它是该算法所求解问题规模n的函数的函数f(n) 当问题规模当问题规模n趋向无穷大时，把趋向无穷大时，把T(n)的数量级的数量级(阶阶)称为算法的渐近时间复杂度，记为称为算法的渐近时间复杂度，记为T(n)=O(f(n)（表示随着问题规模的增大，（表示随着问题规模的增大，算法所需运行时间的增长率和算法所需运行时间的增长率和f(n)的增长率是的增长率是相同的）。相同的）。 在算法分析时，往往对时间复杂度和渐进时间在算法分析时，往往对时间复杂度和渐进时间复杂度不加以区分，经常将渐进时间复杂度简复杂度不加以区分，经常将渐进时间复杂度简称为时间复杂度。称为时间复杂度。34算法

16、和算法分析：时间复杂度算法和算法分析：时间复杂度如何求算法的渐近时间复杂度如何求算法的渐近时间复杂度找出算法中频度（语句重复执行的次数）找出算法中频度（语句重复执行的次数）最大的语句；最大的语句；计算它的执行次数；计算它的执行次数；求最大执行次数的阶。求最大执行次数的阶。35算法和算法分析：时间复杂度算法和算法分析：时间复杂度 例例1 该程序中频度最大的语句是该程序中频度最大的语句是cij+=aik*bkj; 其执行次数为：其执行次数为：n3 T(n) = O(n3)for(i=0; in; +i)for(j=0; jn; +j)cij=0;for(k=0; kn; +k)cij+=aik*bkj;36 例例2 基本操作基本操作+x的执行次数的执行次数 因此渐进复杂度因此渐进复杂度=O(n2)for(i=2; i=n; +i)for(j=2; j=i-1; +j) +x;aij = x;2(1)(2)3222nnnn37 例例3 对于整个算法，对于整个算法，T(n)=O(n2+n)=O(n2)for(i = 0; i n; i+) m = i;for(j = i; j = n; j+)