数据结构 01-绪论.ppt

《数据结构》 第一章 绪 论 数据结构（C语言版） 第一章 绪 论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求 为了编写出一个“好”的程序，必须分析待处理对象的特性及各对象之间存在的关系。 “数据结构”学科形成和发展背景 计算机应用——科学计算→非数值计算（控制、管理等） 处理对象——纯数值→具有一定结构的数据（字符、图像等） §1.1 什么是数据结构 用计算机解决问题：建立模型——设计算法——编程求解 例1 书目自动检索系统 根据书目信息（登录号、书名、作者、分类号...）建立书目文件、索引表，再根据需求进行查询。 书目文件 按书名 按作者名 按分类号 索引表 线性表 例2 人机对奕问题——井字棋（三子棋） 必须对对弈过程中所有可能的格局以及相应的对策都考虑周全。 …….. …….. …... …... …... …... 树 例3 多叉路口交通灯管理问题 C E D A B AB AC AD BA BC BD DA DB DC EA EB EC ED 图 必须考虑各种可能的通行和各通行之间的冲突，再根据这种关系提出相应的策略。 数据结构的定义 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。 数据结构的地位 是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 数据结构的发展 1、面向各专门领域的特殊问题； 2、从抽象数据类型的观点来讨论（即面向对象）。 数据结构的研究目的和研究内容 ★研究目的：寻求有效地组织和处理非数值数据的理论、技术和方法，这类数据具有量大且具有一定内在逻辑关系的特点。 ★研究内容：数据的逻辑结构、存储结构以及相应的基本操作运算的定义和实现。 ★数据(Data)：是计算机程序所加工处理的描述客观事物的符号的总称。 ★数据元素(Data Element) ：数据的基本单位，是数据集合的一个个体。一个数据元素可以由若干个数据项（域）组成。 也称节点(Node)或记录(Record)。 ★数据对象(Data Object)：是具有相同性质的数据元素的集合，是数据的一个子集。 ★数据结构(Data Structure)：具有结构的数据元素的集合。它包括三个方面的内容：数据元素的逻辑结构、存储结构和相适应的运算（操作）。 §1.2 基本概念和术语 ★逻辑结构：数据元素之间的逻辑关系，可用一个二元组表示：Data_Structure=(D,R) 其中，D——数据元素的有穷集合； R——D上关系的有穷集合。 逻辑结构的四种基本形态 以某班级学生作为数据对象，数据元素是学生的学籍档案为例，考察数据元素之间的关系。 （1）集合结构：数据元素之间除了“属于同一集合”的联系之外，没有其它关系。（认定一个学生是否为班级成员） （2）线性结构：数据元素之间存在一对一的关系。（以学生入学报到的时间先后顺序排列数据元素） （3）树型结构：数据元素之间存在一对多个的关系。（班级中的管理体系） （4）图状结构（或称网状结构）：数据元素之间存在多对多的关系。（同学之间的朋友关系） ★存储结构（或称物理结构）：指数据的逻辑结构在计算机存储器中的映像表示，即在能够反映数据逻辑关系的原则下，数据在存储器中的存储方式。 ◆顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系 ◆链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系 逻辑结构与存储结构密切相关 算法设计→逻辑结构 算法实现→存储结构 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队列 树 图 元素n …….. 元素i …….. 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+(n-1)*m 存储地址 存储内容 Loc(元素i)=Lo+（i-1)*m 顺序存储 1536 元素2 1400 元素1 1346 元素3 ∧ 元素4 1345 h 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. ……. 1400 元素2 1536 ……. …….. ……. 1536 元素3 1346 链式存储 h ★数据类型（Data Type）：高级语言中指数据的取值范围及其上可进行的操作的总称。 ◆原子类型—