数据结构PPT

1数据结构1绪论2教学安排•共64学时–讲课48学时：每周3学时–上机16学时单周2学时•成绩考核–平时表现30%：课堂提问、考勤–期末考试70%3教材与参考书•教材：–唐策善李龙澎黄刘生《数据结构－－用C语言描述》高等教育出版社4教材与参考书•参考书–严蔚敏吴伟民《数据结构（C语言版）》清华大学出版社5教材与参考书•参考书–EllisHorowitz,SartajSahni,SusanAnderson-Freed《FundamentalsofdatastructuresinC》6主要内容•1.1本课程研究的主要内容•1.2数据结构的概念–基本术语•数据、数据元素、数据项•逻辑结构、物理结构–什么是数据结构•1.3算法和算法分析–算法的概念–算法的复杂度71.1本课程研究的主要内容8数据结构研究的主要内容•NiklausWirth（Pascal之父）程序=算法+数据结构为计算机处理问题编制的一组指令集处理问题的策略问题的数学模型9数据结构研究的主要内容•使用计算机解决问题的步骤–从具体问题抽象出数学模型–设计求解此数学模型的算法–编制程序10数据结构研究的主要内容•数值计算的程序设计问题–结构静力分析计算需要编写线性方程组进行求解–全球天气预报需要编写环流模式方程进行求解数学模型数学模型和数值计算相关的数学模型有线性代数方程、非线性代数方程、常微分方程等，它们的数值解问题是计算数学所要研究的问题11数据结构研究的主要内容•非数值计算的程序设计问题–求n个数中的最大值–井字棋人机对弈–教学数据库管理系统数学模型？这些非数值计算问题的数学模型的表示和求解方法就是数据结构研究的内容12数据结构研究的主要内容•数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。13数据结构的应用•数据结构在编译器中的应用•数据结构在操作系统中的应用•数据结构在数据库中的应用141.2数据结构的概念15什么是数据结构•至今尚未有一个被一致公认的定义，不同的人使用该词时所表达的意思有所不同。16基本术语：数据•数据–所有需输入计算机并被程序所处理的对象的总称•例如：图书借阅管理系统–图书信息：登录号书名借阅者编号001理论力学9002002高等数学9001.........17基本术语：数据元素•数据元素–数据的基本单位，在程序中常作为一个整体考虑和处理登录号书名借阅者编号001理论力学9002002高等数学9001.........一个数据元素(一条记录)18基本术语：数据项•数据项–数据的不可分割的最小单位–一个数据元素可由一或多个数据项构成登录号书名借阅者编号001理论力学9002002高等数学9001.........3个数据项19基本术语：逻辑结构•逻辑结构–数据元素间的逻辑关系–即在现实世界中的关系•分类–集合：同在一个集合中•比如同班同学之间20基本术语：逻辑结构–线性结构：一个接一个•比如学生花名册中的记录之间–树形结构：一对多•比如家谱–图形结构：多对多•比如地图21基本术语：物理结构•物理结构–即存储结构–数据元素在计算机中存储时的关系22基本术语：物理结构•例：学生花名册–数据元素之间的逻辑关系：线性关系学号姓名性别籍贯年龄98131张三男北京2098164李斯女上海2198165王武男广州1998182赵柳女香港2298224...23基本术语：物理结构–顺序存储：各个数据元素在计算机中的存储地址也是线性关系，即连续存放98131张三男98164李斯女......第一个数据元素第二个数据元素24基本术语：物理结构–链式存储：各个数据元素在计算机中的存储位置任意，通过指针相互连接起来女李斯98164男张三98131下一个节点的地址下一个节点的地址25基本术语：物理结构•顺序存储结构–逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。•链式存储结构–不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段表示的。26什么是数据结构•（本教材定义）：按某种逻辑关系组织起来的一批数据，应用计算机语言，按一定的存储方式把它们存储在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做一个数据结构。•它一般包含三个方面的内容：–（1）数据元素之间的逻辑关系，即数据的逻辑结构–（2）数据元素及其关系在计算机存储器内的表示，即数据的存储结构/物理结构。–（3）数据的运算，即对数据施加的操作。27什么是数据结构•例：学生名单学号姓名性别籍贯年龄98131张三男北京2098164李斯女上海2198165王武男广州1998182赵柳女香港2298224...281.3算法和算法分析29算法和算法分析：概念•算法(Algorithm)–算法是对问题求解步骤的描述–是指令的有限序列，其中每条指令表示一或多个操作30算法和算法分析：概念•算法的特性–一个正确的算法必须满足•有穷性：算法在执行有穷步后结束，且每步可在有穷时间内完成•确定性：算法中指令无二义性，且在任何条件下执行路径唯一•可行性：算法中各操作可通过已实现的基本运算执行有限次完成•输入：零或多个输入•输出：一或多个输出31算法和算法分析：概念•算法设计的要求–一个好的算法应当满足：•正确性：算法应能满足具体问题的需求•可读性：算法应易于阅读和理解•健壮性：输入数据非法时，算法也能适当作出反应或进行处理•高效性：算法执行时间短，占用存储空间少32算法和算法分析：时间复杂度•程序的执行时间取决于如下因素：–算法–问题的规模–编程语言–编译程序–硬件性能•通常只需考虑算法本身和问题的规模33算法和算法分析：时间复杂度•时间复杂度与渐进时间复杂度–算法的时间复杂度T(n)是该算法的时间耗费，它是该算法所求解问题规模n的函数f(n)–当问题规模n趋向无穷大时，把T(n)的数量级(阶)称为算法的渐近时间复杂度，记为T(n)=O(f(n))（表示随着问题规模的增大，算法所需运行时间的增长率和f(n)的增长率是相同的）。–在算法分析时，往往对时间复杂度和渐进时间复杂度不加以区分，经常将渐进时间复杂度简称为时间复杂度。34算法和算法分析：时间复杂度•如何求算法的渐近时间复杂度–找出算法中频度（语句重复执行的次数）最大的语句；–计算它的执行次数；–求最大执行次数的阶。35算法和算法分析：时间复杂度•例1–该程序中频度最大的语句是c[i][j]+=a[i][k]*b[k][j];–其执行次数为：n3–T(n)=O(n3)for(i=0;in;++i)for(j=0;jn;++j){c[i][j]=0;for(k=0;kn;++k)c[i][j]+=a[i][k]*b[k][j];}36•例2–基本操作++x的执行次数–因此渐进复杂度=O(n2)for(i=2;i=n;++i)for(j=2;j=i-1;++j){++x;a[i][j]=x;}2(1)(2)3222nnnn37•例3–对于整个算法，T(n)=O(n2+n)=O(n2)for(i=0;in;i++){m=i;for(j=i;j=n;j++){if(data[j]data[m])m=j;if(m!=i){temp=data[m];data[m]=data[i];data[i]=temp;}}}执行次数=n，T(n)=O(n)执行次数都是n(n+1)/2，T(n)=O(n2)38算法和算法分析：时间复杂度•各种常见的渐进复杂度按数量级递增排列–O(1)O(log2n)O(n)O(nlog2n)O(nk)O(2n)39算法和算法分析：空间复杂度•空间复杂度–空间复杂度是算法执行时所需存储空间的量度，记作：S(n)=O(f(n))，其中n为问题的规模–一般不考虑存放数据本身占用的空间，只考虑执行算法所需辅助空间，除非数据所占空间与算法本身有关40算法和算法分析•有些算法的复杂度与输入数据有关–比如冒泡排序，当输入数据基本有序时，其时间复杂度为O(n)，基本无序时，为O(n2)，平均为O(n2)–此时就应该分最好情况、最差情况、平均情况来讨论