华中科技电子与信息工程系大二上学期学习数构数据结构课件

数据结构刘应状华中科技大学电信系讲授内容关系（结构）第一章 绪论第二章 线性表第三章 栈和队列第四章

串第五章 数组和广义表第六章 树和二叉树第七章

图第九章 查找第十章 内部排序操作第一章

绪

论内容

什么是数据结构？为什么要学习数据结构？基本概念和术语抽象数据类型的表示和实现算法和算法分析1、什么是数据结构？考察两个例子：例1：字典的排序与查找问题随机排序： 查找方法：两种排序有序排列： 查找方法：例2：档案管理问题按照两种方式管理：1）随机存放：相应的查找方法：顺序查找2）按照下面方式存放：查找方法学

校计算机系电信系其它系自控系教师学生其他人员99级2000级2001级2002级………………………例子的结论同样的对象（字、档案等），用不同的

存放（表示）方式和查找（操作）方法，效率有明显的差异。抽象对象、对象之间的关系、操作“数据结构”的研究内容（见教材P3）2、为什么要学习数据结构？数学软件硬件这是由“数据结构”所研究的内容和我们所学习的专业共同决定的关系对象关系操作对象关系操作3、基本概念和术语数 据：是对客观事物的符号表示，客观世界上所有的事物（如：文字、图象、声音等）都可以用数据来表示。在计算机科学中，它是指所有能够被计算机所处理的符号的总称。数据元素：数据的基本单位，一个数据元素又可以分为若干个数据项，数据项是数据的最小单位。数据对象：性质相同的数据元素的集合，是数据的一个子集。比如：正整数对象是集合N={0，2，3….}，字母对象是集合C={‘A’，’B’，…}数据结构：相互之间存在关系的数据元素的集合。这里，数据元素之间的关系称为结构，也就是说数据结构是具有某种结构的数据元素的集合。通常，数据元素之间的关系有以下四种：1）集合结构：数据元素之间只有“属于同一个集合”的关系，没有其他关系。如下图所示：集合结构2）线性结构：数据元素之间存在一对一的关系。如下图所示：线性结构3）树形结构：数据元素之间存在一对多的关系。如下图所示：树形结构4）图状结构：数据元素之间存在多对多的关系。如下图所示：图状结构数据结构的数学定义：Data_Structure

=

(D,S)其中，D表示数据元素的有限集合，S是D上关系的有限集合。举例：见教材P5以上对数据结构的定义是一种逻辑上的定义，它定义了数据元素（操作对象）之间的逻辑

关系。因此，我们又称为数据的逻辑结构。在数据结构中，仅仅讨论数据的逻辑结构是

不够的，我们还必须知道这种逻辑结构在计

算机中是如何表示的。我们将数据的逻辑结

构在计算机中的表示（映象）叫做数据的物理结构（又称存储结构）。数据的逻辑结构在计算机中有两种映射方式：顺序映象和非顺序映象。由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储结构：逻辑上相邻的两个元素，在存储器中仍然相邻。所有的元素在存储器中是按照顺序存放的。用数组即可实现顺序存储。链式存储结构：逻辑上相邻的两个元素，在存储器中不一定相邻。它需要借助于指针来实现的。数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：是一个数学模型加上定义在该模型上的一组操作。抽象数据类型的定义仅仅取决于它的一组逻辑特性，而与它在计算机内如何表示和实现无关，它与数据类型实质上是一个概念。抽象数据类型可以用以下的三元组来表示：ADT

=

（D，S，P）其中，D是数据对象，S是D上的关系集，P是D上的操作集。以后，我们采用以下格式定义抽象数据类型（ADT）ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>}ADT抽象数据类型名4、抽象数据类型的表示和实现抽象数据类型可以通过固有的数据类型（如：整型、实型、字符型等）来表示和实现。为了使算法具有更好的可读性，本课程将用介于伪码和C语言之间的类C语言作为描述工具。有关类C语言的描述语法见教材P10-115、算法和算法分析算法的定义是对特定问题求解步骤的一种描述，它是指令的有限序列。算法的特性1、有穷性2、确定性3、可行性4、输入、输出算法设计的要求1、正确性2、可读性3、健壮性4、效率与低存储量需求算法效率的量度1、计算时间2、算法的规模时间复杂度算法中基本操作的重复次数，通常用O(f(n))表示，如