数据结构概念-树图的划分.ppt

《数据结构概念-树图的划分.ppt》由会员分享，可在线阅读，更多相关《数据结构概念-树图的划分.ppt（72页珍藏版）》请在三一办公上搜索。

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

2、),数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(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,构造数据类型由基本数据类型或构造数据类型组成。构造数据类型由不同成分类型构成。基本数据类型可以看作是计算机中已实现的数据结构。数据类型就是数据结构，不过它是从编程者的角度来使用的。数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。,20,抽象数据类型(ADTs:Abstract Data Types

5、),抽象数据类型是由用户定义，用以表示应用问题的数据模型。特点是：信息隐蔽和数据封装，使用与实现相分离。抽象数据类型可用（D,S,P）三元组表示，其中，D 是数据元素的集合（简称数据对象），S 是 D上的关系集合，P 是对 D 的基本操作集合。,21,抽象数据类型,22,抽象数据类型的描述,其中数据对象、数据之间的关系用伪码描述；基本操作定义格式为,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,基本操作名（参数表）前置条件：先决条件描述后置条件：操作结果描述,23,基本操作有两种参数：赋值参数只为操作提供输入值；引

6、用参数以&打头，除可提供输入值外，还将返回操作结果。“前置条件”描述了操作执行之前数据结构和参数应满足的先决条件，若不满足，则操作失败，并返回相应出错信息。“后置条件”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若前置条件为空，则省略之。,24,自然数的抽象数据类型定义,ADT NaturalNumber isobjects:一个整数的有序子集合,它开始于0,结束于机器能表示的最大整数(MaxInt)。Function:对于所有的 x,y NaturalNumber;False,True Boolean,+、-、=、=等都是可用的服务。Zero():NaturalNumber/前

7、置条件：无/后置条件：返回自然数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 Subtract(x,y):NaturalNumber/前置条件：x,y为NaturalNumber且xy/后置条件：返回 x-y,26,Equal(x,y):Boolean/前置条件：x,y为NaturalNumber/后置条件：if(x=y)返回True else

8、返回 False Successor(x):NaturalNumber/前置条件：x为NaturalNumber/后置条件：if(x=MaxInt)返回 x else 返回 x+1end NaturalNumber,27,面向对象的概念,面向对象=对象类继承通信对象在应用问题中出现的各种实体、事件、规格说明等。由一组属性值和在这组值上的一组服务（或称操作）构成。与C中构造数据类型不同在于：C中的构造数据类型的变量仅涉及属性值，与操作分离，而C+中的对象则不然。,28,类(class)，实例(instance)具有相同属性和服务的对象归于同一类，形成类。类中的对象为该类的实例。同一类的实例共享类

9、的属性和类的操作；通过继承共享其父类的公共的和保护性的属性和操作；同一类的不同实例有不同的属性值。,29,四边形类及其对象,30,继承派生类（子类）：四边形，三角形，基类（父类）：多边形,31,通信消息传递C+中消息传递的方式：定义：Point 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,referencePointVertices

10、,Polygon 类,referencePointVertices,Draw()move(x,y)contains(aPoint),Polygon的子类Quadrilateral类,Quadrilateral,33,算法定义,定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列特性：输入 有0个或多个输入输出 有一个或多个输出(处理结果)确定性 每步定义都是确切无歧义的有穷性 算法应在执行有穷步后结束有效性 每一条运算应足够基本,34,事例学习：选择排序问题明确问题：递增排序解决方案：逐个选择最小数据算法框架：for(int i=0;i n-1;i+)/n-1趟 从ai检查到a

11、n-1;若最小整数在ak,交换ai与ak;细化程序：程序 SelectSort,算法设计 自顶向下，逐步求精,35,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;,36,模板(template),定义 适合多种数据类型的类定义或算法，在特定环境下通过简单地代换，变成针对具体某种数据类型的类定义或算法。,37,

12、用模板定义用于排序的数据表类#ifndef DATALIST_H#define 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

13、#endif,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=high,i+)if(elementi elementm

14、in)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,44,使用模板的选择排序算法的主函数#include#include“dataList.h”const int SZ=10;int ma

15、in()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

16、)算法应满足具体问题的需求。可读性(Readability)算法应该容易阅读。以有利于阅读者对程序的理解。效率 效率指的是算法执行的时间和空间利用率。通常这两者与问题的规模有关。健壮性(Robustness)算法应具有容错处理的功能。当输入非法数据时，算法应对其作出反应，而不应产生莫名其妙的输出结果。,48,算法的后期测试,对一个算法要作出全面的分析可分成两个阶段进行，即事前分析和事后测试事前分析要求事前求出该算法的一个时间界限函数。事后测试则要求在算法执行后通过算法执行的时间和实际占用空间的统计资料来分析。事后分析要求在算法中的某些部位插装时间函数 time()，测定算法完成某一功能所花费时

17、间。,49,例如，给出顺序搜索(Sequenial Search)算法int seqsearch(int a,int n,int x)/在a0,an-1中搜索与给定值 x 相等的元/素，函数返回其位置，失败返回-1。int i=0;while(i n,50,插装 time()的计时程序 double start,stop;time(事实上，算法运行时间要受输入规模、利用编译程序生成的目标代码的质量、计算机程序指令系统的品质和速度等制约。,51,算法的事前估计,算法的事前估计主要包括时间复杂性和空间复杂性的分析：问题的规模：如：矩阵的阶数、图的结点个数、被分类序列的正整数个数等。时间复杂性：算法

18、所需时间和问题规模的函数，记为 T(n)。当 n 时的时间复杂性，称为渐进时间复杂性。空间复杂性：算法所需空间和问题规模的函数。记为 S(n)。当 n 时的时间复杂性，称为渐进空间复杂性。,52,空间复杂度度量,存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间,53,时间复杂度度量,编译时间运行时间程序步语法上或语义上有意义的一段指令序列；执行时间与问题规模无关；例如：声明语句：程序步数为0;表达式：程序步数

19、为1,54,程序步确定方法插入计数全局变量count建表，列出个语句的程序步,例 以迭代方式求累加和的函数 float sum(float a,int n)float s=0.0;for(int i=0;i n;i+)s=s+ai;return s;,55,在求累加和程序中加入 count 语句 float sum(float a,int n)float s=0.0;count+;/count 统计执行语句条数 for(int i=0;i n;i+)count+=2;/针对 for 语句s+=ai;count+;/针对赋值语句 count+=2;/针对 for 的最后一次 count+;/针对

20、 return 语句 return s;执行结束得 程序步数 count=3*n+4,56,程序的简化形式 void sum(float a,int n)for(int i=0;i n;i+)count+=3;count+=4;,57,注意：一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。例如：赋值语句x=sum(R,n)本身程序步数为 1；一次执行对函数 sum(R,n)的调用需要的程序步数为 3*n+4；一次执行的程序步数为 1+3*n+4=3*n+5,58,计算累加和程序程序步数计算工作表格,59,时间复杂度的渐进表示法,例 求两个n阶方阵的乘积C=AB,void Mat

21、rixMultiply(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=0;n2 for(int k=0;k n;k+)n2(2n+2)Cij=Cij+Aik*Bkj;n3,3n3+5n2+4n+2,60,时间复杂度的渐进表示法,算法中所有语句的频度之和是矩阵阶数n的函数 T(n)=3n3+5n2+4n+2一般地，称 n 是问题的规模。则时间复杂度 T(n)是问题规模 n 的函数。当n趋于无穷大时，把时间复杂度的数量级（阶）称为算法的渐进时间复杂度 T(n)=O(n3)大O表示法,61,

22、加法规则 针对并列程序段 T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)各种函数的增长趋势 c log2n n nlog2n n2 n3 2n 3n n!,62,T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2)=O(n2),63,乘法规则 针对嵌套程序段 T(n,m)=T1(n)*T2(m)=O(f(n)*g(m)渐进的空间复杂度 S(n)=O(f(n)两个并列循环的例子,64,void exam(float x,int m,int n)float sum;for(int i=0;i m;i+)/x中各行 sumi=0.0;/数据累加 for(in

23、t j=0;j n;j+)sumi+=xij;for(i=0;i m;i+)/打印各行数据和 cout i“:”sum i endl;渐进时间复杂度为 O(max(m*n,m),65,起泡排序 void bubbleSort(int a,int n)/对表 a 逐趟比较,n 是表当前长度 for(int i=1;i=i;j-)/n-i次比较 if(aj-1 aj)int tmp=aj-1;aj-1=aj;aj=tmp;/一趟比较,66,渐进时间复杂度 O(f(n)*g(n)=O(n2),67,有时,算法的时间复杂度不仅依赖于问题规模 n，还与输入实例的初始排列有关。在数组 An 中查找给定值

24、k 的算法：int i=n-1;while(i=0 算法的语句 i-的频度不仅与 n 有关，还与 A 中各元素的取值以及 k 的取值有关。,68,例：设有两个算法在同一机器上运行，其执行时间分别为 100n2 和 2n，问：要使前者快于后者，n 至少要取多大？解答：问题是找出满足 100n2 2n=8192 n=14时，100n2=19600 2n=16384 n=15时，100n2=22500 2n=32764 取 n=15 满足要求。,69,出错处理问题举例,试编写一个函数计算 n!*2n 的值，结果存放于数组 An 的第 i 个数组元素中(0 i n)若设计算机中允许的整数的最大值为 m

25、axInt，则当 i arraySize 或者对于某一个 k(0 k n)，使得k!*2k maxInt 时，应按出错处理。,70,可有如下几种不同的出错处理方式：,用 cerr 及 exit(1)语句来终止执行并报告错误；用返回整数函数值 0,1 来实现算法，以区别是正常返回还是错误返回；在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某中错误返回。抛出异常。,71,#include#define n 100#define maxInt 0 x7fffffffbool calc(int T,int n)int i,value=1;if(n!=0)for(i=1;i maxInt/n/2)return false;/直接判断 i!*2i MaxInt 是危险的 value*=n*2;,72,Tn=value;/n!*2n Tn return true;void main()int An,i;for(i=0;i n;i+)if(!calc(A,i)cout failed at i endl;break;,