数据结构 课件 胡学钢.ppt

《数据结构 课件 胡学钢.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构(C语言版)目录概论第1章线性表第2章栈、队列和数组第3章树第4章图第5章查找第6章排序第7章文件第8章第1章概论数据结构的研究内容1.1基本术语1.2算法描述及分析1.3返回1.1数据结构的研究内容1.1.1用计算机解决实际问题的过程建立模型构造求解算法选择存储结构型编写程序测试思考：你认为数据结构课程会涉及到上述哪些步骤呢？数据结构课程在问题求解过程中的作用：与建立模型的关系与算法设计的关系与选择存储结构的关系与编程之间的关系1.1.2学习数据结构的意义在计算机科学中，数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操

2、作系统、数据库系统及其它系统程序和大型应用程序的重要基础。目前在我国，《数据结构》不仅是计算机专业的核心课程之一，而且是一些非计算机专业的主要选修课程之一。瑞士计算机科学家沃斯（N.Wirth）曾以“算法+数据结构＝程序”作为他的一本著作的名称。可见，程序设计的实质是对实际问题选择一种好的数据结构，并设计一个好的算法。因此，若仅仅掌握几种计算机语言和程序设计方法，而缺乏数据结构知识，则难以应付众多复杂的课题，且不能有效地利用计算机。返回数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。是介于数学、计

3、算机软件、计算机硬件的一门核心课程。1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现数据是指信息的载体，是能够输入到计算机中，并被计算机识别、存储和处理的符号的集合。数据的形式较多，例如我们前面所述的工资报表、学生成绩表，一个家族关系的表示形式，表示一个群体中个体之间关系的图形描述等。1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现数据中具有独立意

4、义的个体。例如工资表中的个人工资信息，成绩表中的学生成绩信息，家族关系中的个人等。在有些场合下，也称之为元素、记录、结点、顶点等。1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现虽然将具有独立意义的个体用元素来表示，但在许多情况下还需要特定个体的具体信息，因而涉及到了元素的字段信息。字段是对元素的详细描述，通常情况下，元素可能包含多个字段。1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现数据结构是指组成数据的元素之间的结构关系。线性结构、树型结

5、构和图结构是《数据结构》中的几类常见的数据结构形式。如果数据中的元素之间没有关系，则构成集合，这也是一种结构。1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现我们将线性结构、树型结构和图结构这几类结构称为逻辑结构，它包括数据元素的表示和关系的表示。因为仅考虑了元素之间的逻辑关系，而没有考虑到其在计算机中的具体实现。1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现为所涉及的数据结构选择一种存储形式，并将其存储到计算机中，这样就得到了数据结构在内存

6、中的物理结构（有时也称为存储结构）。一种逻辑结构可能会有多种存储结构。例如，可以采用顺序存储，也可采用连接形式的存储。不同存储结构上所实现的运算的性能可能有一定的差异。1.2基本术语数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现数据的逻辑结构与存储结构密切相关。一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构。在选择了数据结构的存储结构之后，就可以实现所给出的运算了。1.2小结数据数据元素字段(域)数据结构数据结构的逻辑结构数据结构的物理结构数据结构运算的实现所以，由于不同的存储形式对

7、算法的时间性能、空间性能等有较大影响，即使是相同的存储结构也可能会存在不同的算法实现，为此，需要解决这样的问题：究竟何种存储结构更为合适？什么算法更有效？为此，需要对算法进行分析，有关算法分析部分将在本章的后面部分讨论。通过分析，可以知道所实现的算法的性能及所选择的存储结构是否符合要求。返回1.3算法描述及分析1.3.1算法描述语言概述描述：算法可采用多种描述语言来描述，如自然语言、计算机语言或某些伪语言。各种描述语言在对问题的描述能力方面存在一定的差异：自然语言较为灵活，但不够严谨；而计算机语言虽然严格，但由于语法方面的限制，使得灵活性不足

8、。因此，许多教材中采用的是以一种计算机语言为基础，适当添加某些功能或放宽某些限制而得到的一种类语言，如类PASCAL语言、C语言等，这些类语言既具有计算机语言的严格