数据结构 课件 胡学钢

数据结构(C语言版)目录概论第1章线性表第2章栈、队列和数组第3章树第4章图第5章查找第6章排序第7章文件第8章第1章概论数据结构的研究内容1.1基本术语1.2算法描述及分析1.3返回1.1数据结构的研究内容1.1.1用计算机解决实际问题的过程建立模型构造求解算法选择存储结构型编写程序测试思考：你认为数据结构课程会涉及到上述哪些步骤呢？数据结构课程在问题求解过程中的作用：•与建立模型的关系•与算法设计的关系•与选择存储结构的关系•与编程之间的关系1.1.2学习数据结构的意义在计算机科学中，数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。目前在我国，《数据结构》不仅是计算机专业的核心课程之一，而且是一些非计算机专业的主要选修课程之一。瑞士计算机科学家沃斯（N.Wirth）曾以“算法+数据结构＝程序”作为他的一本著作的名称。可见，程序设计的实质是对实际问题选择一种好的数据结构，并设计一个好的算法。因此，若仅仅掌握几种计算机语言和程序设计方法，而缺乏数据结构知识，则难以应付众多复杂的课题，且不能有效地利用计算机。返回•数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。是介于数学、计算机软件、计算机硬件的一门核心课程。1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现数据是指信息的载体，是能够输入到计算机中，并被计算机识别、存储和处理的符号的集合。数据的形式较多，例如我们前面所述的工资报表、学生成绩表，一个家族关系的表示形式，表示一个群体中个体之间关系的图形描述等。1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现数据中具有独立意义的个体。例如工资表中的个人工资信息，成绩表中的学生成绩信息，家族关系中的个人等。在有些场合下，也称之为元素、记录、结点、顶点等。1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现虽然将具有独立意义的个体用元素来表示，但在许多情况下还需要特定个体的具体信息，因而涉及到了元素的字段信息。字段是对元素的详细描述，通常情况下，元素可能包含多个字段。1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现数据结构是指组成数据的元素之间的结构关系。线性结构、树型结构和图结构是《数据结构》中的几类常见的数据结构形式。如果数据中的元素之间没有关系，则构成集合，这也是一种结构。1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现我们将线性结构、树型结构和图结构这几类结构称为逻辑结构，它包括数据元素的表示和关系的表示。因为仅考虑了元素之间的逻辑关系，而没有考虑到其在计算机中的具体实现。1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现为所涉及的数据结构选择一种存储形式，并将其存储到计算机中，这样就得到了数据结构在内存中的物理结构（有时也称为存储结构）。一种逻辑结构可能会有多种存储结构。例如，可以采用顺序存储，也可采用连接形式的存储。不同存储结构上所实现的运算的性能可能有一定的差异。1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现数据的逻辑结构与存储结构密切相关。一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构。在选择了数据结构的存储结构之后，就可以实现所给出的运算了。1.2小结数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现所以，由于不同的存储形式对算法的时间性能、空间性能等有较大影响，即使是相同的存储结构也可能会存在不同的算法实现，为此，需要解决这样的问题：究竟何种存储结构更为合适？什么算法更有效？为此，需要对算法进行分析，有关算法分析部分将在本章的后面部分讨论。通过分析，可以知道所实现的算法的性能及所选择的存储结构是否符合要求。返回1.3算法描述及分析1.3.1算法描述语言概述•描述：算法可采用多种描述语言来描述，如自然语言、计算机语言或某些伪语言。各种描述语言在对问题的描述能力方面存在一定的差异：自然语言较为灵活，但不够严谨；而计算机语言虽然严格，但由于语法方面的限制，使得灵活性不足。因此，许多教材中采用的是以一种计算机语言为基础，适当添加某些功能或放宽某些限制而得到的一种类语言，如类PASCAL语言、C语言等，这些类语言既具有计算机语言的严格性，又具有某些灵活性，同时也容易上机实现，因而被广泛接受。•定义:是对特定问题求解步骤的一种描述,是指令的有限序列,其中每一条指令表示一个或多个操作。•特性:有穷性确定性可行性输入输出•算法设计的要求：正确性：算法是否正确,是否符合具体问题的需求。可读性：有利于人机交流，机器执行。健壮性：对错误能适当的做出反应或进行处理。效率与低存储量的要求。1.3算法描述及分析1.3.2算法分析衡量算法的主要性能指标包括时间性能、空间性能等，其中时间性能是指运行算法所需的时间的度量，而空间性能则是指运行算法所需要的辅助空间的规模。度量运行时间的方法：事后统计，事前分析估算（常用后一种）。•时间的复杂度是指算法中包含简单操作重复执行的次数，而某个语句重复执行的次数就是该语句的频度。•可以记做：T(n)=O(f(n))其中f(n）是问题规模n的某个函数，一般是算法中频度最大的语句频度。•例如：s:=0;for(k=1;k=n;k++)for(j=0;j=n;j++)s:=s+2;①①语句的频度是n*(n+1)*存在循环嵌套语句时，算法的时间复杂度是由嵌套最深层的语句频度决定。•评价一个算法的时间性能主要标准是时间复杂度的数量级。这个程序段的时间复杂度为：T(n)=O(n2+n)=O(n2)所谓数量级是这样定义的：如果变量n的函数f(n)和g(n)满足：lim=常数k(k≠0)，则称f(n)和g(n)是同一数量级的，并用f(n)=O(g(n))的形式来表示。)()(ngnf•按数量级递增的顺序排列，常见的时间复杂度为：常数阶O（1）对数阶O（㏒2n）线性阶O（n）线性对数阶O（n㏒2n）平方阶O（n2）立方阶O（n3）K次方阶O（nk）指数阶O（2n）例：程序段语句频度时间复杂度1.x=x+1;2.FOR(i=0;i=n;i++)x:=x+1;3.FOR(i=1;in;i++)FOR(j=0;jn;j++)x:=x+1;1O(1)常数阶n+1O(n)线性阶(n-1)*nO(n2)平方阶•算法与程序的区别•算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。•程序是用某种程序设计语言对算法的具体实现。主要区别在：有穷性和描述方法•程序可以是无穷的，例如OS，算法是有穷的；•程序是用程序设计语言描述，在机器上可以执行；算法还可以用框图、自然语言等方式描述。思考题1.下面程序段的时间复杂度为（）(a)x=x+1;(b)FOR(i=0;i=n;i++)x=x+1;(c)FOR(i=1;in;i++)FOR(j=0;jn;j++)x:=x+1;(d)While((nmodj)0&&jsqrt(n))j=j+1;T(n)=O(√n)T(n)=O(n+1)=O(n)T(n)=O(1)T(n)=O((n-1)*(n-2))=O(n2)FOR(i=1;in;i++)FOR(j=1;j=i;j++)x:=x+1;ij112123123N-1N-11+2+3+….+n-1T(n)=O(n2)