数据结构(C语言版)第1章绪论讲解.ppt

1．正确性 首先，算法应当满足以特定的“规格说明”方式给出的需求。 其次，对算法是否“正确”的理解可以有以下四个层次： a．程序中不含语法错误； b．程序对于几组输入数据能够得出满足要求的结果； c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果； 通常以第c层意义的正确性作为衡量一个算法是否合格的标准。 d．程序对于一切合法的输入数据都能得出满足要求的结果； 算法设计的要求 * * 理论课教材：数据结构（C语言版） 严蔚敏 吴伟民 编著 数据结构 1.0 学习数据结构的主要意义和要求 1.1 数据结构讨论的范畴 1.2 基本概念 1.3 抽象数据类型的表示和实现 1.4 算法和算法的度量 第一章 绪论 学习数据结构的主要意义和要求 数据结构和算法是计算机学科的两大支柱 数据结构是程序设计的基础 程序=算法+数据结构 要求： 意义： （1）掌握各类基本数据结构类型和相应的存储结构 （2）提高阅读和编写算法的能力 （3）能针对给定问题，选择相适应的数据结构，并 能设计和分析算法 1.1数据结构讨论的范畴 程序 = 算法 + 数据结构 程序设计： 为计算机处理问题编制一组指令集 算法： 处理问题的策略 数据结构：问题的数学模型 非数值计算的程序设计问题 例1 书目自动检索系统 例2 人机对奕问题 例3 多叉路口交通灯管理问题 例1 书目自动检索系统 书目文件 按书名 按作者名 按分类号 索引表 线性表 例2 人机对奕问题 树 …….. …….. …... …... …... …... 例3 多叉路口交通灯管理问题 图 C E D A B AB AC AD BA BC BD DA DB DC EA EB EC ED 数据结构定义 数据结构是一门讨论“描述现实世界实体”的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。 数据（data)—所有能被输入到计算机中，且能被计算机处理的符号的集合，是计算机操作的对象的总称。 数据元素（data element）—是数据（集合）中的一个“个体”，是数据的基本单位，也称节点（node）或记录（record） 数据项（data item）—有独立含义的数据最小单位，也称域(field)。 数据对象（data object)—是性质相同的数据元素的集合，是数据的一个子集。 1.2 基本概念和术语 根据数据元素间关系的基本特性，有四种基本结构 （集合）——数据元素间除“同属于一个集合”外，无其它关系 线性结构——一个对一个，如线性表、栈、队列 树形结构——一个对多个，如树 图状结构——多个对多个，如图 1.2 基本概念和术语 数据结构(data structure)—是相互之间存在一种或多种特定关系的数据元素的集合 1.2 基本概念和术语 数据结构的形式定义为: 数据结构是一个二元组 Data_Structures = (D, S) 其中: D 是数据元素的有限集， S 是 D上关系的有限集。 数据元素的映象方法： 例用二进制位(bit)的位串表示数据元素 (321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2 关系的映象方法：（表示?x, y?的方法） 顺序映象 以相对的存储位置表示后继关系 链式映象 以附加信息(指针)表示后继关系 数据的逻辑结构—只抽象反映数据元素的逻辑关系 数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的映象 换句话说 按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构 数据的逻辑结构与存储结构密切相关 存储结构分为： 顺序存储结构——借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据 元素间的逻辑关系 线性表 树 图 顺序存储结构 链式存储结构 复合存储结构 逻辑结构 物理结构 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. ……. 1400 元素2 1536 ……. …….. ……. 1536 元素3 1346 链式存储 h 1536 元素2 1400 元素1 1346 元素3 ∧ 元素4