Ch01 数据结构概论01(1)

1、第一章 数据结构概念数据结构电子教案1什么是数据结构抽象数据类型及面向对象概念算法定义模板算法简单性能分析与度量第一章 数据结构概念2“学生”表格3“课程”表格4学生(学号,姓名,性别,籍贯)课程(课程号,课程名,学分)选课(学号,课程号,成绩) “选课单”包含如下信息 学号 课程编号 成绩 时间 学生选课系统中的实体之间是一种网状关系5UNIX文件系统的系统结构图/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp6数据（data）数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别

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

3、是该集合中所有数据元素之间的关系的有限集合。10例：N 个网点之间的连通关系树形关系网状关系15615243624311数据结构是数据的组织形式包括三个方面：数据元素间的逻辑关系，即数据的逻辑结构；数据元素及其关系在计算机存储内的表示，即数据的存储表示；数据的运算，即对数据元素施加的操作。本书1.1.3节先从逻辑的角度出发分析数据的结构类别。12数据的逻辑结构数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；数据的逻辑结构可以看作是从具体问题抽象出来的数据模型；数据的逻辑结构与数据元素本身的形式、内容无关；数据的逻辑结构与数据元素的相对存储位置无关。13数据逻辑结构的分类线性结构 线性表非

4、线性结构 树 图（或网络）14线性结构树形结构树 二叉树 二叉搜索树bindevetclibuser1413121123456789103158710119987456623131115堆结构 “最大”堆 “最小”堆12354871110291641012115123698716图结构 网络结构12543611331814665161921125634不难发现：树有层次感，而图和网络没有。17数据的存储结构数据的存储结构是逻辑结构用计算机语言的实现（也叫物理结构）；数据的存储结构依赖于计算机语言。 顺序存储表示 链接存储表示 索引存储表示 散列存储表示主要用于内存的存储表示主要用于外存 (文件

5、) 的存储表示见课本P.6, 上数第2段 18数据结构课程的内容分析实际问题，确定时空限制，建立数学模型（数据的逻辑结构）及基本运算。在计算机上实现（把逻辑结构转换为物理结构，并实现运算）。评价。19抽象数据类型及面向对象概念数据类型 定义：一组性质相同的值的集合，以及定义于这个值集合上的一组操作的总称。C+语言中的基本数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值 20构造数据类型由基本数据类型或构造数据类型组成。构造数据类型由不同成分类型构成。基本数据类型可以看作是计算机中已实现的数据结构。数据类型就是数据结构，不过它是从编程者的角度来

6、使用的。数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。 21抽象数据类型 (ADTs: Abstract Data Types)抽象数据类型是由用户定义，用以表示应用问题的数据模型。特点是：信息隐蔽和数据封装，使用与实现相分离。抽象数据类型可用（D, R, P）三元组表示，其中，D 是数据元素的集合（简称数据对象），R是 D上的关系集合，P 是对 D 的基本操作集合。 22抽象数据类型查找 登录 删除 修改 符 号 表23抽象数据类型的描述其中数据对象、数据之间的关系用伪码描述；基本操作定义格式为ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操

7、作：基本操作的定义 ADT 抽象数据类型名基本操作名（参数表）前置条件：先决条件描述后置条件：操作结果描述24基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。 “前置条件”描述了操作执行之前数据结构和参数应满足的先决条件，若不满足，则操作失败，并返回相应出错信息。 “后置条件”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若前置条件为空，则省略之。25自然数的抽象数据类型定义ADT NaturalNumber IS Objects: 一个整数的有序子集合,它开始于0, 结 束于机器能表示的最大整数(MaxInt)。 Function: 对于所有的 x, y NaturalNumber; False, True Boolean, +、-、 0，返回 false；否则返回trueDelete ( ID )：Student前置条件：学生信息表不空，且存在学号为ID的学生后置条件：删除学号为ID的学生，并返回被删学生信息 END Student30关于前置条件的判断问题 一般用if else来判断，也可以用C+提供的assert函数来实现。 如：a