[工学]数据结构C语言版.ppt

数据结构（C语言版） 主讲 张明伟 教学内容 第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串 第五章 数组和广义表 第六章 树和二叉树 第七章 图 第九章 查找 第十章 内部排序 第一章 绪论 学习要点 理解关于数据结构的相关名词术语。 掌握算法的设计要求及时间复杂度和空间复杂度的分析和计算方法。 1.1 数据结构的定义 计算机解题步骤 例1 书目自动检索系统 例3 田径赛的时间安排问题（无向图的着色问题） ： 设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。 （1）设用如下六个不同的代号代表不同的项目： 跳高 跳远 标枪 铅球 100米 200米 A B C D E F （2）用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。 （3）某选手比赛的项目必定有边相连（不能同时比赛）。 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 1.2 基本概念及术语 数据：是对客观事物的符号表示。 数据元素是数据的基本单位。在计算机程序中通常作为一个整体考虑和处理。 数据项是数据不可分割的最小单位。 数据对象是性质相同的数据元素的集合。 数据结构定义1 是相互之间存在一种或多种特定关系的数据元素的集合。 形式化定义：数据结构是一个二元组 Data_Structure = (D,R) 其中，D是数据元素的有限集合，R是D上关系的集合 数据结构定义2按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示 方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算（操作）。 逻辑结构：“数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。 物理结构：数据结构在计算机中的表示称为物理结构。又称存储结构。 逻辑结构---划分方法 例：用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。 （1） S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)} （2） S=(D, R) D={di | 1≤i≤5} R={(di , dj ), ij} d1 d5 d2 d4 d3 物理结构： 顺序结构 （元素在存储器中的相对位置） 链式结构 （元素地址的指针） 1.3 数据类型和抽象数据类型 数据类型：是一个值的集合和定义在这个值集上一组操作总称。 抽象数据类型（ADT） 作用：抽象数据类型可以使我们更容易描述实际问题。 例：用线性表描述学生成绩表，用树或图描述遗传关系。 定义：一个数学模型以及定义在该模型上的一组操作。 好处：可提高软件的复用程度。 使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。 例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。 抽象数据类型表示法： 一、 三元组表示：（D，S，P） 　其中D是数据对象，S是D上的关系集，P是对D的基本操作集。 二、标准定义格式： ADT 抽象数据类型名{ 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 }ADT 抽象数据类型名 例：线性表的表示 1.4 算法和算法分析 　定义：算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 算法的特性 有穷性：算法必须在有限步内结束； 确定性：组成算法的操作必须清晰无二义性。 可行性：组成算法的操作必须能够在计算机上实现。 输入：0个或多个输入； 输出：1个或多个输出； 算法设计的要求 正确性 可读性 健壮性 效率与低存储量需求 　效率指的是算法执行时间。对于解决同一问题的多个算法，执行时间短的算法效率高。 　存储量需求指算法执行过程中所需要的最大存储空间。