数据结构基础教程.pptVIP

数据结构（C语言版） 教学计划安排 开课周次：1-16周 周一：5、6节，松1318 周四：1、2节，松1318 上机实践： 周四：1、2节 (第3周－16周) 158 期终考试形式： 闭卷考试 教学计划安排 本课程的内容及学习的基本方法 本课程讲述的主要内容： 将分别讲述数据结构的基本概念、线性表、栈和队列、数组、树型结构、图结构、查找、排序等内容。 学习本课程的基本方法： 上课认真听讲。 仔细阅读教材及课件的讲授内容，体会并灵活掌握数据结构中的基本概念和知识点。 仔细阅读教材及课件中的大量例题，多做算法练习。 本课程成绩计算 平时成绩占10% 上机实践实验占20% 期终考试占70% E-mail地址：fengxy@ 网络硬盘URL： 第1章 绪论 学习要点 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。 了解抽象数据类型的定义、表示和实现方法。 熟悉类C语言的书写规范、表示和实现方法。 理解算法五个要素的确切含义和对算法正确性的理解。 掌握计算语句频度和估算算法时间复杂度的方法。 数据结构的发展史 数据结构作为一门独立的课程在国外是从1968年才开始设立的。 1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 随着计算机技术的不断发展，数据结构广泛应用于计算机科学的各个领域。 编译程序利用堆栈、符号表和语法分析树； 操作系统由过程并列表和文件支持，并利用由可用空间的并列表或表格组成的存储管理模式； 人工智能程序利用堆栈、队列、集、搜索树、表格和图； 数据库利用串、并列表、树、环和表格。 数据结构讨论的范畴 数据结构是计算机相关专业的一门重要的专业基础课。它主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法。它是学习操作系统、编译原理、数据库原理等计算机专业核心课程的基础。掌握好这门课程的内容，是学习计算机其他相关课程的必备条件。 Nikalaus Wirth (Pascal语言之父) Algorithm + Data Structures = Programs 数据结构讨论的范畴 数值性计算 数值性计算： 数值计算问题的数学模型通常可以用一组线性或非线性的代数方程组或微分方程组来描述。 即使是不需要用计算机求解的简单问题也需要一个数学模型来描述。 鸡兔同笼问题：二元一次方程组 房屋设计或桥梁设计中的结构应力分析：线性代数方程组 天气预报：环流模式方程 数值性计算 非数值性计算 非数值性计算： 当操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，就需要对之进行非数值性处理。 当计算机进入非数值计算领域，特别是用在管理上的时候，计算机的操作对象之间的关系就无法用数学方程加以描述了。 应用举例1 —— 学籍档案管理 假设一个学籍档案管理系统应包含如下页的表1-1所示的学生信息。 非数值性计算(举例1) 特点： 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格。 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构。 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。 非数值性计算(举例2) 非数值性计算(举例2) 特点： 在求解过程中，所处理的数据之间具有层次关系，这就是我们所说的树形结构。 对它的操作有：建立树形结构，输出最底层结点内容等等。 应用举例3 —— 制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下页的表1-2所示。 非数值性计算(举例3) 非数值性计算(举例3) 非数值性计算(举例3) 特点： 课程之间的先后关系用图结构描述。 通过实施创建图结构，按要求将图结构中的顶点进行线性排序。 结论： 以上所举例子中的数学模型正是数据结构要讨论的问题。因此，简单地说，数据结构是一门讨论描述现实世界实体的数学模型(非数值计算) 及其上的操作在计算机中如何表示和实现的学科。 基本概念和术语(数据) 数据(data) 数据是对客观事物的符号表示。在计算机科学中，其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。 例如，一个个人书库管理程序所要处理的数据可能是下表所示的表格。 基本概念和术语(数据元素) 数据元素(data element) 数据元素也称为结点，是数据集合中的一个实体，是数据结构中讨论的基本单位。 数据元