《数据结构教案清华大学ds-01教学幻灯片》由会员分享，可在线阅读，更多相关《数据结构教案清华大学ds-01教学幻灯片（72页珍藏版）》请在金锄头文库上搜索。
1、1,第一章 数据结构概念,数据结构电子教案,殷人昆 王 宏,2,什么是数据结构 抽象数据类型及面向对象概念 算法定义 模板 算法简单性能分析与度量,第一章 数据结构概念,3,“学生”表格,5,学生 (学号,姓名,性别,籍贯),课程 (课程号,课程名,学分),选课 (学号,课程号,成绩),“选课单”包含如下信息 学号 课程编号 成绩 时间 学生选课系统中实体构成的网状关系,6,UNIX文件系统的系统结构图,7,数据（data）,数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数据的分类： 数值性数据 非数值性数据,8,数据元素 (dat
2、a element),数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。 有时一个数据元素可以由若干数据项 (Data Item)组成。数据项是具有独立含义的最小标识单位。 数据元素又称为元素、结点、记录。,9,什么是数据结构,定义: 由某一数据元素的集合以及该集合中所有数据元素之间的关系组成。记为： Data_Structure = D, R 其中，D 是某一数据元素的集合，R 是该集合中所有数据元素之间的关系的有限集合。,10,例：N 个网点之间的连通关系,树形关系,网状关系,11,数据结构是数据的组织形式,包括三个方面： 数据元素间的逻辑关系，即数据的逻辑结构； 数据元素及其关
3、系在计算机存储内的表示，即数据的存储表示； 数据的运算，即对数据元素施加的操作。,12,数据的逻辑结构,数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关； 数据的逻辑结构可以看作是从具体问题抽象出来的数据模型； 数据的逻辑结构与数据元素本身的形式、内容无关； 数据的逻辑结构与数据元素的相对存储位置无关。,13,数据的逻辑结构分类,线性结构 线性表 非线性结构 树 图（或网络）,14,线性结构,树形结构,树 二叉树 二叉搜索树,15,堆结构,“最大”堆 “最小”堆,16,图结构 网络结构,17,数据的存储结构,数据的存储结构是逻辑结构用计算机语言的实现； 数据的存储结构依赖于计算机语言。 顺
4、序存储表示 链接存储表示 索引存储表示 散列存储表示,主要用于内存的存储表示,主要用于外存 (文件) 的存储表示,18,抽象数据类型及面向对象概念,数据类型 定义：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称. C语言中的数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值,19,构造数据类型由基本数据类型或构造数据类型组成。 构造数据类型由不同成分类型构成。 基本数据类型可以看作是计算机中已实现的数据结构。 数据类型就是数据结构，不过它是从编程者的角度来使用的。 数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。
5、,20,抽象数据类型 (ADTs: Abstract Data Types),抽象数据类型是由用户定义，用以表示应用问题的数据模型。 特点是：信息隐蔽和数据封装，使用与实现相分离。 抽象数据类型可用（D, S, P）三元组表示，其中，D 是数据元素的集合（简称数据对象），S 是 D上的关系集合，P 是对 D 的基本操作集合。,21,抽象数据类型,22,抽象数据类型的描述,其中数据对象、数据之间的关系用伪码描述；基本操作定义格式为,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,基本操作名（参数表） 前置条件：先决条件
6、描述 后置条件：操作结果描述,23,基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以 False, True Boolean, +、-、=、= 等都是可用的服务。 Zero( ) : NaturalNumber /前置条件：无 /后置条件：返回自然数0,25,IsZero(x) : Boolean /前置条件：x为NaturalNumber /后置条件：if (x = 0) then 返回True else 返回False Add (x, y) : NaturalNumber /前置条件：x, y为NaturalNumber且x+yMaxInt /后置条件：返回 x+y Subtra
7、ct (x, y) : NaturalNumber /前置条件： x, y为NaturalNumber且xy /后置条件：返回 x- y,26,Equal (x, y) : Boolean /前置条件： x, y为NaturalNumber /后置条件： if (x = y) 返回True else 返回 False Successor (x) : NaturalNumber /前置条件： x为NaturalNumber /后置条件： if (x = MaxInt) 返回 x else 返回 x+1 end NaturalNumber,27,面向对象的概念,面向对象 = 对象类继承通信 对象
8、在应用问题中出现的各种实体、事件、规格说明等。 由一组属性值和在这组值上的一组服务（或称操作）构成。 与C中构造数据类型不同在于：C中的构造数据类型的变量仅涉及属性值，与操作分离，而C+中的对象则不然。,28,类 (class)，实例 (instance) 具有相同属性和服务的对象归于同一类，形成类。 类中的对象为该类的实例。 同一类的实例 共享类的属性和类的操作； 通过继承共享其父类的公共的和保护性的属性和操作； 同一类的不同实例有不同的属性值。,29,四边形类及其对象,30,继承 派生类（子类）：四边形，三角形， 基类（父类）：多边形,31,通信 消息传递 C+中消息传递的方式： 定义：P
9、oint p; void move(int x, inty); 使用：p.move(x, y); C中则不同，需使用函数调用方式： 定义：Point p; void move(Point q, int x, inty); 使用：move(p, x, y);,32,Draw( ) move(x, y) contains(aPoint),Polygon,referencePoint Vertices,Polygon 类,referencePoint Vertices,Draw( ) move(x, y) contains(aPoint),Polygon的子类 Quadrilateral类,Quad
10、rilateral,33,算法定义,定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列 特性： 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本,34,事例学习：选择排序问题 明确问题：递增排序 解决方案：逐个选择最小数据 算法框架： for (int i = 0; i n-1; i+) /n-1趟 从ai检查到an-1; 若最小整数在ak, 交换ai与ak; 细化程序：程序 SelectSort,算法设计 自顶向下，逐步求精,35,void selectSort (
11、int a , const int n ) /对n个整数a0,a1,an-1按递增顺序排序 for (int i = 0; i n-1; i+) int k = i; /从ai查到an-1, 找最小整数, 在ak for (int j = i+1; j n; j+) if (aj ak) k = j; int temp = ai; ai = ak; ak = temp; ,36,模板 (template),定义 适合多种数据类型的类定义或算法，在特定环境下通过简单地代换，变成针对具体某种数据类型的类定义或算法。,37,用模板定义用于排序的数据表类 #ifndef DATALIST_H #def
12、ine DATALIST_H #include /K是表项关键码类型 template / /E是表项类型 class dataList private: E *element; int listSize; void swap (int m1, int m2); int minKey (int low, int high);,38,public: dataList (int size = 10) : listSize (size), element (new Esize) dataList ( ) delete element; void sort ( ); friend ostream #e
13、ndif,39,类中所有操作作为模板函数的实现 template void dataList : swap (int m1, int m2) /交换由m1, m2为下标的数组元素的值 E temp = element m1; element m1 = element m2; element m2 = temp; ;,40,template int dataList:minKey (int low, int high) /查找数组Elementlow到Elementhigh中具 /有最小关键码值的表项，函数返回其位置 int min = low; for (int i = low+1, i =
14、high, i+) if ( elementi elementmin ) min = i; return min; ;,定义的重载操作,41,template ostream ,42,template istream ,43,template void dataList : sort ( ) /按非递减顺序对listSize个关键码element0到 /elementArraySize-1排序 for (int i = 0; i = listSize-2; i+) int j = minKey (i, listSize-1); if (j != i) swap (j, i); #endif,4
15、4,使用模板的选择排序算法的主函数 #include #include “dataList.h” const int SZ = 10; int main ( ) struct sick /患者 int key; char *name15; int age; char *address30; bool operator (sick x) return key x.key; ;,45,dataList TestList (SZ); cin TestList; cout TestList endl; TestList.Sort ( ); cout TestList endl; return 0; ,定义对象时，代入实际数据类型,重载友元操作,标准IO操作,消息通信,46,算法简单性能分析与度量,算法的性能标准 算法的后期测试 算法的事前估计,47,算法的性能标准,正确性 (Correctness ) 算法应满足具体问题的需求。 可读性(Readability) 算法应该容易阅读。以有利于阅读者对程序的理解。 效率 效率指的是算法执行的时间和空间利用率。通常这两者与问题的规模有关。 健壮性 (Robustness) 算法应具有容错处理的功能。当输入非法数据时，算法应对其作出反应，而不应产生
