Ch数据结构概论

1、Ch数据结构概论什么是数据构造抽象数据类型及面向对象概念算法定义模板算法简单性能分析与度量第一章 数据构造概念2Ch01数据构造概论013Ch01数据构造概论014学生(学号,姓名,性别,籍贯)课程(课程号,课程名,学分)选课(学号,课程号,成绩)Ch01数据构造概论015Ch01数据构造概论01/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp6Ch01数据构造概论01数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数据的分类： 数值性数据 非数值性数据7姓

2、名所在院系性别出生日期年 月职务业绩数据元素 (data element)数据的根本单位。在计算机程序中常作为一个整体进展考虑和处理。有时一个数据元素可以由假设干数据项 (Data Item)组成。数据项是具有独立含义的最小标识单位。数据元素又称为元素、结点、记录。8数据元素之间的关系数据元素和数据元素之间都不会是孤立的，而是有这样或那样的关系的，这种关系称为构造。9Ch01数据构造概论01定义: 由某一数据元素的集合以及该集合中所有数据元素之间的关系组成。记为： Data_Structure = D, R 其中，D 是某一数据元素的集合，R 是该集合中所有数据元素之间的关系的有限集合。10C

3、h01数据构造概论01 树形关系网状关系15615243624311数据构造是数据的组织形式包括三个方面：数据元素间的逻辑关系，即数据的逻辑构造；数据元素及其关系在计算机存储内的表示，即数据的存储表示；数据的运算，即对数据元素施加的操作。本书节先从逻辑的角度出发分析数据的构造类别。12数据的逻辑构造数据的逻辑构造从逻辑关系上描述数据，与数据的存储无关；数据的逻辑构造可以看作是从具体问题抽象出来的数据模型；数据的逻辑构造与数据元素本身的形式、内容无关；数据的逻辑构造与数据元素的相对存储位置无关。13数据逻辑构造的分类线性构造 线性表非线性构造 树 图或网络14线性构造树形构造树 二叉树 二叉搜索

4、树bindevetclibuser1413121123456789103158710119987456623131115堆构造 “最大堆 “最小堆12354871110291641012115123698716图构造 网络构造12543611331814665161921125634不难发现：树有层次感，而图和网络没有。17数据的存储构造数据的存储构造是逻辑构造用计算机语言的实现也叫物理构造；数据的存储构造依赖于计算机语言。 顺序存储表示 链接存储表示 索引存储表示 散列存储表示主要用于内存的存储表示主要用于外存 (文件) 的存储表示见课本P.6, 上数第2段 18Ch01数据构造概论01分析

5、实际问题，确定时空限制，建立数学模型数据的逻辑构造及根本运算。在计算机上实现把逻辑构造转换为物理构造，并实现运算。评价。19Ch01数据构造概论01数据类型 定义：一组性质一样的值的集合，以及定义于这个值集合上的一组操作的总称。C+语言中的根本数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值 20构造数据类型由根本数据类型或构造数据类型组成。构造数据类型由不同成分类型构成。根本数据类型可以看作是计算机中已实现的数据构造。数据类型就是数据构造，不过它是从编程者的角度来使用的。数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。 21C

6、h01数据构造概论01抽象数据类型是由用户定义，用以表示应用问题的数据模型。特点是：信息隐蔽和数据封装，使用与实现相别离。抽象数据类型可用D, R, P三元组表示，其中，D 是数据元素的集合简称数据对象，R是 D上的关系集合，P 是对 D 的根本操作集合。 22抽象数据类型查找 登录 删除 修改 符 号 表23Ch01数据构造概论01其中数据对象、数据之间的关系用伪码描述；根本操作定义格式为ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 根本操作：根本操作的定义 ADT 抽象数据类型名根本操作名参数表前置条件：先决条件描述后置条件：操作结果描述24根本操作有两种参数

7、：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。 “前置条件描述了操作执行之前数据构造和参数应满足的先决条件，假设不满足，那么操作失败，并返回相应出错信息。 “后置条件说明了操作正常完成之后，数据构造的变化状况和应返回的结果。假设前置条件为空，那么省略之。25Ch01数据构造概论01ADT NaturalNumber IS Objects: 一个整数的有序子集合,它开场于0, 结 束于机器能表示的最大整数(MaxInt)。 Function: 对于所有的 x, y NaturalNumber; False, True Boolean, +、-、 0，返回 false；否那么返回trueDelete ( ID )：Student前置条件：学生信息表不空，且存在学号为ID的学生后置条件：删除学号为ID的学生，并返回被删学生信息 END Student30Ch01数据构造概论01 一般用if else来判断，也可以用C+提供的assert函数来实现。 如：assert ( x 0 ); 当程序运行到这句话时会判断条件