数据结构教案(清华大学) dsppt课件

1、第一章 数据构造概念数据构造电子教案数据构造电子教案殷人昆殷人昆 王王 宏宏第一章第一章 数据构造概念数据构造概念 学学 号号 姓姓 名名 性别性别 籍籍 贯贯 出生年月出生年月 1 98131 刘激扬刘激扬 男男 北北 京京 1979.12 2 98164 衣春生衣春生 男男 青青 岛岛 1979.07 3 98165 卢声凯卢声凯 男男 天天 津津 1981.02 4 98182 袁秋慧袁秋慧 女女 广广 州州 1980.10 5 98224 洪洪 伟伟 男男 太太 原原 1981.01 6 98236 熊南燕熊南燕 女女 苏苏 州州 1980.03 7 98297 宫宫 力力 男男 北北

2、 京京 1981.01 8 98310 蔡晓莉蔡晓莉 女女 昆昆 明明 1981.02 9 98318 陈陈 健健 男男 杭杭 州州 1979.12 课程编号课程编号 课课 程程 名名 学时学时 024002 程序设计基础程序设计基础 64 024010 汇编语言汇编语言 48 024016 计算机原理计算机原理 64 024020 数据结构数据结构 64 024021 微机技术微机技术 64 024024 操作系统操作系统 48 024026 数据库原理数据库原理 48学生学生( (学号学号, ,姓名姓名, ,性别性别, ,籍贯籍贯) )课程课程( (课程号课程号, ,课程名课程名, ,学分

3、学分) )选课选课( (学号学号, ,课程号课程号, ,成果成果) )UNIX文件系统的系统构造图文件系统的系统构造图/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp数据数据datadatan数据是信息的载体，是描画客观事物的数、数据是信息的载体，是描画客观事物的数、字符、以及一切能输入到计算机中，被计算字符、以及一切能输入到计算机中，被计算机程序识别和处置的符号的集合。机程序识别和处置的符号的集合。n数据的分类：数据的分类：n 数值性数据数值性数据n 非数值性数据非数值性数据姓名姓名 所在院系所在院系 性别性别

4、出生日期出生日期 年年 月月职务职务 业绩业绩数据元素数据元素 (data element) (data element)n数据的根本单位。在计算机程序中常作为数据的根本单位。在计算机程序中常作为一个整体进展思索和处置。一个整体进展思索和处置。n有时一个数据元素可以由假设干数据项有时一个数据元素可以由假设干数据项 (Data Item)(Data Item)组成。数据项是具有独立含义组成。数据项是具有独立含义的最小标识单位。的最小标识单位。n数据元素又称为元素、结点、记录。数据元素又称为元素、结点、记录。什么是数据构造什么是数据构造定义定义: 由某一数据元素的集合以及该集合中一切由某一数据元素

5、的集合以及该集合中一切数据元素之间的关系组成。记为：数据元素之间的关系组成。记为： Data_Structure = D, R 其中，其中，D 是某一数据元素的集合，是某一数据元素的集合，R 是该是该集合中一切数据元素之间的关系的有限集合。集合中一切数据元素之间的关系的有限集合。例：例：N N 个网点之间的连通关系个网点之间的连通关系 156152436243数据构造是数据的组织方式数据构造是数据的组织方式n包括三个方面：包括三个方面：n数据元素间的逻辑关系，即数据的逻辑构数据元素间的逻辑关系，即数据的逻辑构造；造；n数据元素及其关系在计算机存储内的表示，数据元素及其关系在计算机存储内的表示，

6、即数据的存储表示；即数据的存储表示；n数据的运算，即对数据元素施加的操作。数据的运算，即对数据元素施加的操作。数据的逻辑构造数据的逻辑构造n数据的逻辑构造从逻辑关系上描画数据，数据的逻辑构造从逻辑关系上描画数据，与数据的存储无关；与数据的存储无关；n数据的逻辑构造可以看作是从详细问题笼数据的逻辑构造可以看作是从详细问题笼统出来的数据模型；统出来的数据模型；n数据的逻辑构造与数据元素本身的方式、数据的逻辑构造与数据元素本身的方式、内容无关；内容无关；n数据的逻辑构造与数据元素的相对存储位数据的逻辑构造与数据元素的相对存储位置无关。置无关。数据的逻辑构造分类数据的逻辑构造分类n线性构造线性构造n

7、线性表线性表n非线性构造非线性构造n 树树n 图或网络图或网络线性构造线性构造树形构造树形构造树树 二叉树二叉树 二叉搜索树二叉搜索树bindevetclibuser14131211234567891031587101199874566231311堆构造堆构造123548711102916410121151236987图构造图构造 网络构造网络构造12543611331814665161921125634数据的存储构造数据的存储构造n数据的存储构造是逻辑构造用计算机言语数据的存储构造是逻辑构造用计算机言语的实现；的实现；n数据的存储构造依赖于计算机言语。数据的存储构造依赖于计算机言语。n 顺序

8、存储表示顺序存储表示n 链接存储表示链接存储表示n 索引存储表示索引存储表示n 散列存储表示散列存储表示主要用于内存的主要用于内存的存储表示存储表示主要用于外存主要用于外存 (文文件件) 的存储表示的存储表示笼统数据类型及面向对象概念笼统数据类型及面向对象概念n数据类型数据类型 定义：一组性质一样的值的集合定义：一组性质一样的值的集合, 以及定以及定义于这个值集合上的一组操作的总称义于这个值集合上的一组操作的总称.nC言语中的数据类型言语中的数据类型n char int float double voidn 字符型字符型 整型整型 浮点型浮点型 双精度型双精度型 无无值值 n构造数据类型由根本

9、数据类型或构造数据构造数据类型由根本数据类型或构造数据类型组成。类型组成。n构造数据类型由不同成分类型构成。构造数据类型由不同成分类型构成。n根本数据类型可以看作是计算机中已实现根本数据类型可以看作是计算机中已实现的数据构造。的数据构造。n数据类型就是数据构造，不过它是从编程数据类型就是数据构造，不过它是从编程者的角度来运用的。者的角度来运用的。n数据类型是模板，必需定义属于某种数据数据类型是模板，必需定义属于某种数据类型的变量，才干参与运算。类型的变量，才干参与运算。 笼统数据类型笼统数据类型 (ADTs: Abstract Data Types)(ADTs: Abstract Data T

10、ypes)n笼统数据类型是由用户定义，用以表示运笼统数据类型是由用户定义，用以表示运用问题的数据模型。用问题的数据模型。n特点是：信息隐蔽和数据封装，运用与实特点是：信息隐蔽和数据封装，运用与实现相分别。现相分别。n笼统数据类型可用笼统数据类型可用D, S, P三元组表示，三元组表示，其中，其中，D 是数据元素的集合简称数据对是数据元素的集合简称数据对象，象，S 是是 D上的关系集合，上的关系集合，P 是对是对 D 的的根本操作集合。根本操作集合。 n笼笼统统数数据据类类型型查找查找 登录登录 删除删除 修正修正 符符 号号 表表笼统数据类型的描画笼统数据类型的描画n其中数据对象、数据之间的关

11、系用伪码描其中数据对象、数据之间的关系用伪码描画；根本操作定义格式为画；根本操作定义格式为ADT 笼统数据类型名笼统数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义 数据关系：数据关系的定义数据关系：数据关系的定义 根本操作：根本操作的定义根本操作：根本操作的定义 ADT 笼统数据类型名笼统数据类型名根本操作名参数表根本操作名参数表前置条件：先决条件描画前置条件：先决条件描画后置条件：操作结果描画后置条件：操作结果描画n根本操作有两种参数：赋值参数只为操作提根本操作有两种参数：赋值参数只为操作提供输入值；援用参数以供输入值；援用参数以&打头，除可提供输打头，除可提供输入值外

12、，还将前往操作结果。入值外，还将前往操作结果。n “前置条件前置条件描画了操作执行之前数据构描画了操作执行之前数据构造和参数应满足的先决条件，假设不满足，造和参数应满足的先决条件，假设不满足，那么操作失败，并前往相应出错信息。那么操作失败，并前往相应出错信息。n “后置条件后置条件阐明了操作正常完成之后，阐明了操作正常完成之后，数据构造的变化情况和应前往的结果。假设数据构造的变化情况和应前往的结果。假设前置条件为空，那么省略之。前置条件为空，那么省略之。自然数的笼统数据类型定义自然数的笼统数据类型定义ADT NaturalNumber isobjects: 一个整数的有序子集合一个整数的有序子

13、集合,它开场于它开场于0, 终了于机器能表示的最大整数终了于机器能表示的最大整数(MaxInt)。Function: 对于一切的对于一切的 x, y NaturalNumber; False, True Boolean, +、-、=、= 等都是等都是可用的效力。可用的效力。 Zero( ) : NaturalNumber /前置条件：无前置条件：无 /后置条件：前往自然数后置条件：前往自然数0 面向对象的概念面向对象的概念n面向对象面向对象 = = 对象类承继通讯对象类承继通讯n对象对象n在运用问题中出现的各种实体、事件、规在运用问题中出现的各种实体、事件、规格阐明等。格阐明等。n由一组属性值

14、和在这组值上的一组效力由一组属性值和在这组值上的一组效力或称操作构成。或称操作构成。n与与C C中构造数据类型不同在于：中构造数据类型不同在于：C C中的构造中的构造数据类型的变量仅涉及属性值，与操作分数据类型的变量仅涉及属性值，与操作分别，而别，而C+C+中的对象那么不然。中的对象那么不然。n类类 (class)，实例，实例 (instance)n具有一样属性和效力的对象归于同一类，具有一样属性和效力的对象归于同一类，构成类。构成类。n类中的对象为该类的实例。类中的对象为该类的实例。n同一类的实例同一类的实例n共享类的属性和类的操作；共享类的属性和类的操作；n经过承继共享其父类的公共的和维护

15、性的经过承继共享其父类的公共的和维护性的属性和操作；属性和操作；n同一类的不同实例有不同的属性值。同一类的不同实例有不同的属性值。四边形类及其对象四边形类及其对象属性aPoint1 aPoint2aPoint3 aPoint4效力效力Draw( )move(x, y)contains(aPoint)属性值属性值quadrilateral1quadrilateral2(35, 10) (50, 10)(35, 25) (50, 25)(45, 65) (50, 45)(65, 66) (60, 70)Draw( )move(x, y)contains(aPoint)Draw( )move(x,

16、y)contains(aPoint)效力效力效力效力quadrilateraln承继承继n派生类子类：四边形，三角形，派生类子类：四边形，三角形，n基类父类：多边形基类父类：多边形派生类派生类承继的特性承继的特性+特有的特性特有的特性基类基类多边形多边形四边形四边形三角形三角形六边形六边形n通讯通讯n音讯传送音讯传送nC+中音讯传送的方式：中音讯传送的方式：n定义：定义：Point p; void move(int x, inty);n运用：运用：p.move(x, y);nC中那么不同，需运用函数调用方式：中那么不同，需运用函数调用方式：n定义：定义：Point p; void move(P

17、oint q, int x, inty);n运用：运用：move(p, x, y); Draw( )move(x, y)contains(aPoint)PolygonreferencePointVerticesPolygon 类类referencePointVerticesDraw( )move(x, y)contains(aPoint)Polygon的子类的子类Quadrilateral类类Quadrilateral算法定义算法定义n定义：一个有穷的指令集，这些指令为处定义：一个有穷的指令集，这些指令为处理某一特定义务规定了一个运算序列理某一特定义务规定了一个运算序列n特性：特性：n输入输入

18、 有有0个或多个输入个或多个输入n输出输出 有一个或多个输出有一个或多个输出(处置结果处置结果)n确定性确定性 每步定义都是确切无歧义的每步定义都是确切无歧义的n有穷性有穷性 算法应在执行有穷步后终了算法应在执行有穷步后终了n有效性有效性 每一条运算应足够根本每一条运算应足够根本n事例学习：选择排序问题事例学习：选择排序问题n明确问题：递增排序明确问题：递增排序n处理方案：逐个选择最小数据处理方案：逐个选择最小数据n算法框架：算法框架： for (int i = 0; i n-1; i+) /n-1趟趟 从从ai检查到检查到an-1; 假设最小整数在假设最小整数在ak, 交换交换ai与与ak;

19、n n细化程序：程序细化程序：程序 SelectSort 算法设计算法设计 自顶向下，逐渐求精自顶向下，逐渐求精 void selectSort ( 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; 模板模板 (template) (t

20、emplate)定义定义 适宜多种数据类型的类定义或算法，在特适宜多种数据类型的类定义或算法，在特定环境下经过简单地代换，变成针对详细某定环境下经过简单地代换，变成针对详细某种数据类型的类定义或算法。种数据类型的类定义或算法。用模板定义用于排序的数据表类用模板定义用于排序的数据表类#ifndef DATALIST_H#define DATALIST_H#include /K是表项关键是表项关键码类型码类型template / /E是是表项类型表项类型class dataList private: E *element; int listSize; void swap (int m1, int

21、m2); int minKey (int low, int high); public: dataList (int size = 10) : listSize (size), element (new Esize) dataList ( ) delete element; void sort ( ); friend ostream& operator (ostream& outStream, dataList& outList); friend istream& operator (istream& inStream, dataList& in

22、List); ; #endif 类中一切操作作为模板函数的实现类中一切操作作为模板函数的实现template void dataList : swap (int m1, int m2) /交换由交换由m1, m2为下标的数组元素的值为下标的数组元素的值 E temp = element m1; element m1 = element m2; element m2 = temp; ;template int dataList:minKey (int low, int high) /查找数组查找数组Elementlow到到Elementhigh中具中具/有最小关键码值的表项，函数前往其位置有最小

23、关键码值的表项，函数前往其位置 int min = low; for (int i = low+1, i = high, i+) if ( elementi elementmin ) min = i; return min;定义的重载操作定义的重载操作template ostream& operator (ostream& outStream, dataList outList) outStream “输出数组内容输出数组内容 : n; for (int i = 0; i outList.listSize; i+) outStream outList.elementi; out

24、Stream endl; ouStream “输出数组当前大小输出数组当前大小 : outList.listSize endl; return outStream; template istream& operator (istream& inStream, dataList inList) /输入对象为输入对象为inList，输入流对象为，输入流对象为inStream cout inList.listSize; cout “输入数组元素值输入数组元素值 : n; for (int i = 0; i inList.listSize; i+) cout “元素元素 i inLis

25、t.elementi; return inStream; 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 运用模板的选择排序算法的主函数运用模板的选择排序算法的主函数 #include #include “dataList.h const int S

26、Z = 10; int main ( ) struct sick /患者患者 int key; char *name15; int age; char *address30; bool operator (sick x) return key x.key; ; dataList TestList (SZ); cin TestList; cout TestList endl; TestList.Sort ( ); cout TestList endl; return 0; 定义对象时，代定义对象时，代入实践数据类型入实践数据类型重载友元操作重载友元操作规范规范IO操作操作音讯通讯音讯通讯算法简单

27、性能分析与度量算法简单性能分析与度量算法的性能规范算法的性能规范算法的后期测试算法的后期测试n对一个算法要作出全面的分析可分成两个阶对一个算法要作出全面的分析可分成两个阶段进展，即事前分析和事后测试段进展，即事前分析和事后测试n事前分析要求事前求出该算法的一个时间界事前分析要求事前求出该算法的一个时间界限函数。限函数。n事后测试那么要求在算法执行后经过算法执事后测试那么要求在算法执行后经过算法执行的时间和实践占用空间的统计资料来分析。行的时间和实践占用空间的统计资料来分析。n事后分析要求在算法中的某些部位插装时间事后分析要求在算法中的某些部位插装时间函数函数 time ( ) time ( )

28、，测定算法完成某一功能所，测定算法完成某一功能所破费时间。破费时间。例如，给出顺序搜索例如，给出顺序搜索 (Sequenial Search)算法算法int seqsearch ( int a , int n, int x ) /在在a0,an-1中搜索与给定值中搜索与给定值 x 相等的元相等的元/素，函数前往其位置，失败前往素，函数前往其位置，失败前往-1。 int i = 0; while ( i n & ai != x ) i+; if ( i = n ) return -1; return i; 插装 time( ) 的计时程序 double start, stop; time

29、(&start); int k = seqsearch (a, n, x); time(&stop); double runTime = stop - start; cout n runTime endl;现实上，算法运转时间要受输入规模、利用编译程序生成的目的代码的质量、计算机程序指令系统的质量和速度等制约。算法的事前估计算法的事前估计n算法的事前估计主要包括时间复杂性和空算法的事前估计主要包括时间复杂性和空间复杂性的分析：间复杂性的分析：n问题的规模：如：矩阵的阶数、图的结点问题的规模：如：矩阵的阶数、图的结点个数、被分类序列的正整数个数等。个数、被分类序列的正整数个数等。

30、n时间复杂性：算法所需时间和问题规模的时间复杂性：算法所需时间和问题规模的函数，记为函数，记为 T(n) T(n)。当。当 n n 时的时间复时的时间复杂性，称为渐进时间复杂性。杂性，称为渐进时间复杂性。n空间复杂性：算法所需空间和问题规模的空间复杂性：算法所需空间和问题规模的函数。记为函数。记为 S(n) S(n)。当。当 n n 时的时间复时的时间复杂性，称为渐进空间复杂性。杂性，称为渐进空间复杂性。空间复杂度度量空间复杂度度量时间复杂度度量时间复杂度度量n程序步确定方法程序步确定方法n插入计数全局变量插入计数全局变量countn建表，列出个语句的程序步建表，列出个语句的程序步例例 以迭代

31、方式求累加和的函数以迭代方式求累加和的函数 float sum (float a , int n) float sum (float a , int n) float s = 0.0; float s = 0.0; for (int i = 0; i n; for (int i = 0; i n; i+)i+) s = s + ai; s = s + ai; return s; return s; 在求累加和程序中参与在求累加和程序中参与 count 语句语句 float sum (float a , int n) float s = 0.0; count+; /count 统计执行语统计执行

32、语句条数句条数 for (int i = 0; i n; i+) count += 2; /针对针对 for 语句语句s += ai;count+; /针对赋值语句针对赋值语句 count += 2; /针对针对 for 的最后一的最后一次次 count+; /针对针对 return 语句语句 return s; 执行终了得执行终了得 程序步数程序步数 count = 3*n+4留意：留意： 一个语句本身的程序步数能够不等于该语一个语句本身的程序步数能够不等于该语句一次执行所具有的程序步数。句一次执行所具有的程序步数。 例如：例如：赋值语句赋值语句x = sum (R, n) 本身程序步数为本

33、身程序步数为 1；一次执行对函数一次执行对函数 sum (R, n) 的调用需求的程序的调用需求的程序步数为步数为 3*n+4；一次执行的程序步数为一次执行的程序步数为 1+3*n+4 = 3*n+5计算累加和程序计算累加和程序程序步数计算任务表格程序步数计算任务表格时间复杂度的渐进表示法时间复杂度的渐进表示法例例 求两个求两个n阶方阵的乘积阶方阵的乘积C = ABvoid MatrixMultiply (int Ann, int Bnn, int Cnn) for (int i = 0; i n; i+) 2n+2 for (int j = 0; j n; j+) n(2n+2) Cij =

34、 0; n2 for (int k = 0; k n; k+) n2(2n+2) Cij = Cij + Aik * Bkj; n3 3n3 + 5n2 + 4n +2时间复杂度的渐进表示法时间复杂度的渐进表示法n算法中一切语句的频度之和是矩阵阶数算法中一切语句的频度之和是矩阵阶数n的的函数函数n T(n) = 3n3 + 5n2 + 4n +2n普通地，称普通地，称 n 是问题的规模。那么时间复是问题的规模。那么时间复杂度杂度 T(n) 是问题规模是问题规模 n 的函数。的函数。n当当n趋于无穷大时，把时间复杂度的数量级趋于无穷大时，把时间复杂度的数量级阶称为算法的渐进时间复杂度阶称为算法的

35、渐进时间复杂度n T(n) = O(n3) 大大O表示法表示法n加法规那么加法规那么 针对并列程序段针对并列程序段 n T(n, m) = T1 (n) + T2 (m)n = O(max (f (n), g (m)n各种函数的增长趋势各种函数的增长趋势 n c log2n n nlog2n n2 n3 2n 3n n!T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1 (n) = O(1)T2(n) = O(n)T

36、3(n) = O(n2)x = 0; y = 0;for ( int k = 0; k n; k + ) x +;n乘法规那么乘法规那么 针对嵌套程序段针对嵌套程序段n T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)n渐进的空间复杂度渐进的空间复杂度n S (n) = O(f (n)n两个并列循环的例子两个并列循环的例子 void exam (float x , int m, int n) float sum ; for (int i = 0; i m; i+) /x中各行中各行 sumi = 0.0; /数据累加数据累加 for (int j = 0; j n; j+) sumi += xij; for (i = 0; i m; i+) /打印各行数据和打印各行数据和 cout i “ : sum i endl; 渐进时间复杂度为渐进时间复杂度为 O(max (m*n, m)起泡排序起泡排序 void bubbleSort (int a , int n ) /对表对表 a 逐趟比较逐趟比较, n 是表当前长度是表当前长度 for (int i