数据结构 清华 殷人昆.pptx

《数据结构 清华 殷人昆.pptx》由会员分享，可在线阅读，更多相关《数据结构 清华 殷人昆.pptx（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、“学生学生”表格表格第1页/共58页“课程课程”表格表格第2页/共58页“选课单选课单”包含如下信息包含如下信息 学号学号 课程编号课程编号 成绩成绩 时间时间 学生选课系统中实体构成的网状关系学生选课系统中实体构成的网状关系学生学生(学号学号,姓名姓名,性别性别,籍贯籍贯)课程课程(课程号课程号,课程名课程名,学分学分)选课选课(学号学号,课程号课程号,成绩成绩)第3页/共58页UNIX文件系统的系统结构图文件系统的系统结构图/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp第4页/共58页数据数据（data）n n

2、数据是信息的载体，是描述客观事数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处计算机中，被计算机程序识别和处理的符号的集合。理的符号的集合。uu 数值性数据数值性数据uu 非数值性数据非数值性数据第5页/共58页数据对象数据对象(data object)n n数据的子集。具有相同性质的数据数据的子集。具有相同性质的数据成员（数据元素）的集合。成员（数据元素）的集合。uu整数数据对象整数数据对象 N=0,1,2,uu学生数据对象学生数据对象第6页/共58页什么是数据结构什么是数据结构定义定义:由某一数据对象及该对象中所有数由

3、某一数据对象及该对象中所有数据成员之间的关系组成。记为：据成员之间的关系组成。记为：Data_Structure=D,R 其中，其中，D 是某一数据对象，是某一数据对象，R 是该是该对象中所有数据成员之间的关系的有限对象中所有数据成员之间的关系的有限集合。集合。第7页/共58页N 个网点之间的连通关系个网点之间的连通关系 树形关系树形关系网状关系网状关系152436152436第8页/共58页抽象数据类型及面向对象概念抽象数据类型及面向对象概念n n数据类型数据类型 定义：定义：一组性质相同的值的集合一组性质相同的值的集合,以及定义于这个值集合上的一组操以及定义于这个值集合上的一组操作的总称作

4、的总称.n nC语言中的数据类型语言中的数据类型 char int float double void 字符型字符型 整型整型 浮点型浮点型 双精度型双精度型 无无值值 第9页/共58页抽象数据类型抽象数据类型(ADTs:Abstract Data Types)uu由用户定义，用以表示应用问题由用户定义，用以表示应用问题的的数据模型数据模型uu由由基本的数据类型基本的数据类型组成组成,并包括并包括一一组相关的服务组相关的服务（或称操作）（或称操作）uu信息隐蔽信息隐蔽和和数据封装数据封装，使用与实，使用与实现相分离现相分离第10页/共58页抽抽象象数数据据类类型型查找查找 登录登录 删除删除

5、修改修改 符符 号号 表表第11页/共58页自然数的抽象数据类型定义自然数的抽象数据类型定义ADTADT NaturalNumberNaturalNumber is isobjectsobjects:一个整数的有序子集合一个整数的有序子集合一个整数的有序子集合一个整数的有序子集合,它开始于它开始于它开始于它开始于0,0,结束于机器能表示的最大整数结束于机器能表示的最大整数结束于机器能表示的最大整数结束于机器能表示的最大整数(MaxIntMaxInt)。FunctionFunction:对于所有的对于所有的对于所有的对于所有的 x x,y y NaturalNumberNaturalNumber

6、;FalseFalse,TrueTrue BooleanBoolean,+、-、=、=等都是可用的服务。等都是可用的服务。等都是可用的服务。等都是可用的服务。ZeroZero():():NaturalNumber NaturalNumber 返回自然数返回自然数返回自然数返回自然数0 0 第12页/共58页IsZeroIsZero(x x):):if(if(x x=0)=0)返回返回返回返回TrueTrue BooleanBoolean else else 返回返回返回返回FalseFalseAdd Add(x x,y y):):if(if(x x+y y=MaxIntMaxInt)返回返回返

7、回返回 x x+y y NaturalNumberNaturalNumber else else 返回返回返回返回MaxIntMaxIntSubtract Subtract(x x,y y):):if(if(x yx y)返回返回返回返回 0 0 NaturalNumberNaturalNumber else else 返回返回返回返回 x-yx-yEqual Equal(x x,y y):):if(if(x=yx=y)返回返回返回返回TrueTrue BooleanBoolean else else 返回返回返回返回 FalseFalseSuccessor Successor(x x):):

8、if(if(x=MaxIntx=MaxInt)返回返回返回返回 x x NaturalNumber NaturalNumber else else 返回返回返回返回 x x+1+1endend NaturalNumberNaturalNumber第13页/共58页面向对象的概念面向对象的概念n n面向对象面向对象 =对象类继承通信对象类继承通信n n对象对象uu 在应用问题中出现的各种在应用问题中出现的各种实体实体、事件事件、规格说明规格说明等等uu 由一组由一组属性值属性值和在这组值上的一和在这组值上的一组组服务服务（或称操作）构成（或称操作）构成第14页/共58页n n类类(class)，

9、实例，实例(instance)uu 具有具有相同属性和服务相同属性和服务的对象归于的对象归于同一类，形成类同一类，形成类uu 类中的对象为该类的实例类中的对象为该类的实例第15页/共58页属性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,y)con

10、tains(aPoint)服务服务服务服务四边形类及其对象四边形类及其对象quadrilateral第16页/共58页n n继承继承uu 派生类：派生类：四边形，三角形，四边形，三角形，子类子类 特化类特化类(特殊化类特殊化类)uu 基类：基类：多边形多边形 父类父类 泛化类泛化类(一般化类一般化类)n n通信通信uu 消息传递消息传递第17页/共58页Draw()move(x,y)contains(aPoint)PolygonreferencePointVerticesPolygon 类类referencePointVerticesDraw()move(x,y)contains(aPoint

11、)Polygon的子类的子类Quadrilateral类类Quadrilateral第18页/共58页n n线性结构线性结构uu直接存取类直接存取类 数组数组,文件文件uu顺序存取类顺序存取类 表表,栈栈,队列队列,优先优先队列队列 uu广义索引类广义索引类 线性索引线性索引,搜索树搜索树n n非线性结构非线性结构uu层次结构类层次结构类 树，二叉树，堆树，二叉树，堆uu群结构类群结构类 集合，图集合，图数据结构的抽象层次数据结构的抽象层次第19页/共58页线性结构线性结构树形结构树形结构树树 二叉树二叉树 二叉搜索树二叉搜索树141312112345678910315871011998745

12、6623131bindevetclibuser1第20页/共58页堆结构堆结构 “最大最大”堆堆 “最小最小”堆堆123548711102916410121151236987第21页/共58页群聚类群聚类图结构图结构 网络结构网络结构12564312543611331814665161921第22页/共58页数据的两个视图数据的两个视图n n数据的逻辑结构数据的逻辑结构 面向应用面向应用n n数据的物理结构数据的物理结构 面向存储面向存储uu 顺序结构顺序结构uu 链表结构链表结构uu 散列结构散列结构uu 索引结构索引结构n n在该数据结构上的操作在该数据结构上的操作第23页/共58页为什么

13、选用面向对象及为什么选用面向对象及C+语言语言讲述数据结构？讲述数据结构？n nPASCAL与与C描述是面向过程的。描述是面向过程的。n nC+描述兼有面向过程与面向对描述兼有面向过程与面向对象的特点。象的特点。n nJava描述是面向对象的。描述是面向对象的。n n用面向对象及用面向对象及C+描述与国际接描述与国际接轨，是市场需要轨，是市场需要。第24页/共58页用用C+描述面向对象程序描述面向对象程序uuC+的函数特征的函数特征uuC+的数据声明的数据声明uuC+的作用域的作用域uuC+的类的类uuC+的对象的对象uuC+的输入的输入/输出输出uuC+的函数的函数uuC+的参数传递的参数传

14、递uuC+的函数名重载的函数名重载和操作符重载和操作符重载uuC+的动态存储分的动态存储分配配uu友元友元(friend)函数函数uu内联内联(inline)函数函数uu结构结构(struct)与类与类uu联合联合(Union)与类与类第25页/共58页算法定义算法定义n n定义：定义：一个有穷的指令集一个有穷的指令集，这些指令，这些指令为解决某一特定任务规定了一个运算序为解决某一特定任务规定了一个运算序列列n n特性：特性：uu 输入输入 有有0个或多个输入个或多个输入uu 输出输出 有一个或多个输出有一个或多个输出(处理结果处理结果)uu 确定性确定性 每步定义都是确切、无歧义的每步定义都

15、是确切、无歧义的uu 有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束uu 有效性有效性 每一条运算应足够基本每一条运算应足够基本第26页/共58页uu事例学习：事例学习：选择排序问题选择排序问题uu明确问题：明确问题：递增排序递增排序uu解决方案：解决方案：逐个选择最小数据逐个选择最小数据uu算法框架：算法框架：for(int i=0;i n-1;i+)/n-1趟趟 从从ai检查到检查到an-1;若最小整数在若最小整数在ak,交换交换ai与与ak;uu细化程序：细化程序：程序程序 SelectSort 算法设计算法设计 自顶向下，逐步求精自顶向下，逐步求精 第27页/共58页

16、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;第28页/共58页模板模板(template)定义定义 适合适合多种数据类型多种数据类型的的类定义类定义或或算法算法，在特定环境下通过简单地代换，变成在特定环境下通过简单地代换，变成针对具体某种数据类型针对具体某种数据类型的的类定义类定义或或算算法法第29页/共5

17、8页用模板定义用于排序的数据表类用模板定义用于排序的数据表类#include template class dataList private:Type*Element;int ArraySize;void Swap(int m1,int m2);int MaxKey(int low,int high);第30页/共58页 public:dataList(int size=10):ArraySize(size),Element(new Type Size)dataList()delete Element;void Sort();friend ostream&operator (ostream&o

18、utStream,datalist&outList);friend istream&operator (istream&inStream,datalist&inList);第31页/共58页类中所有操作作为模板函数的实现类中所有操作作为模板函数的实现#include“datalist.h”template void dataList :Swap(int m1,int m2)/交换由m1,m2为下标的数组元素的值 Type temp=Element m1;Element m1=Element m2;Element m2=temp;第32页/共58页 template int dataList:M

19、axKey(int low,int high)/查找数组Elementlow到Elementhigh/中的最大值，函数返回其位置 int max=low;for(int k=low+1,k=high,k+)if(Elementmax Elementk)max=k;return max;第33页/共58页 template ostream&operator(ostream&OutStream,dataList OutList)OutStream “数组内容:n”;for(int i=0;i OutList.ArraySize;i+)OutStream OutList.Elementi ;OutS

20、tream endl;OuStream “数组当前大小:”OutList.ArraySize endl;return OutStream;第34页/共58页 template istream&operator (istream&InStream,dataList InList)cout InList.ArraySize;cout “录入数组元素值:n”;for(int i=0;i InList.ArraySize;i+)cout “元素”i InList.Elementi;return InStream;第35页/共58页 template void dataList:Sort()/按非递减顺

21、序对ArraySize个关键码/Element0到ElementArraySize-1排序 for(int i=ArraySize-1;i 0;i-)int j=MaxKey(0,i);if(j!=i)swap(j,i);第36页/共58页使用模板的选择排序算法的主函数使用模板的选择排序算法的主函数#include“selecttm.h”const int SIZE=10;int main()dataList TestList(SIZE);cin TestList;cout TestList endl;TestList.Sort();cout TestList endl;return 0;第3

22、7页/共58页性能分析与度量性能分析与度量uu算法的性能标准算法的性能标准uu算法的后期测试算法的后期测试uu算法的事前估计算法的事前估计第38页/共58页算法的性能标准算法的性能标准uu正确性正确性uu可使用性可使用性uu可读性可读性uu效率效率uu健壮性健壮性第39页/共58页算法的后期测试算法的后期测试在算法中的某些部位插装时间函在算法中的某些部位插装时间函数数 time()测定算法完成某一功能所花费时测定算法完成某一功能所花费时间间第40页/共58页顺序搜索顺序搜索(Sequenial Search)int seqsearch(int a,int n,int x)/在在a0,an-1中

23、搜索中搜索x int i=0;while(i n&ai!=x)i+;if(i=n)return-1;return i;第41页/共58页 插装插装 time()的计时程序的计时程序 double start,stop;time(&start);int k=seqsearch(a,n,x);time(&stop);double runTime=stop-start;cout n runTime endl;第42页/共58页算法的事前估计算法的事前估计uu 空间复杂度空间复杂度uu 时间复杂度时间复杂度第43页/共58页空间复杂度度量空间复杂度度量n n存储空间的固定部分存储空间的固定部分程序指令

24、代码的空间，常数、简单变程序指令代码的空间，常数、简单变量、定长成分量、定长成分(如数组元素、结构成分、如数组元素、结构成分、对象的数据成员等对象的数据成员等)变量所占空间变量所占空间n n可变部分可变部分尺寸与实例特性有关的成分变量所占尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所空间、引用变量所占空间、递归栈所用空间、通过用空间、通过new和和delete命令动态命令动态使用空间使用空间第44页/共58页时间复杂度度量时间复杂度度量n n编译时间编译时间n n运行时间运行时间uu 程序步程序步F语法上或语义上有意义的一段指令语法上或语义上有意义的一段指令序列序列F执行时间

25、与实例特性无关执行时间与实例特性无关F例如：例如：声明语句声明语句：程序步数为：程序步数为0;表达式表达式：程序步数为：程序步数为1第45页/共58页 程序步确定方法程序步确定方法w 插入计数全局变量插入计数全局变量countw 建表，建表，列出个语句的程序步列出个语句的程序步第46页/共58页例例 以迭代方式求累加和的函数以迭代方式求累加和的函数float sum(float a,int n)float s=0.0;for(int i=0;i n;i+)s+=ai;return s;在求累加和程序中加入在求累加和程序中加入count语句语句float sum(float a,int n)第4

26、7页/共58页 float s=0.0;count+;/count 统计执行语句条数 for(int i=0;i n;i+)count+;/针对 for 语句 s+=ai;count+;/针对赋值语句 count+;/针对 for 的最后一次 count+;/针对 return 语句 return s;执行结束得执行结束得 程序步数程序步数 count=2*n+3第48页/共58页程序的简化形式程序的简化形式 void sum(float a,int n)for(int i=0;i n;i+)count+=2;count+=3;第49页/共58页注意注意：一个语句本身的程序步数可能不等一个语句

27、本身的程序步数可能不等于该语句一次执行所具有的程序步数。于该语句一次执行所具有的程序步数。例如：赋值语句例如：赋值语句 x=sum(R,n)本身的程序步数为本身的程序步数为 1；一次执行对函数一次执行对函数 sum(R,n)的调用的调用需要的程序步数为需要的程序步数为 2*n+3；一次执行的程序步数为一次执行的程序步数为 1+2*n+3=2*n+4第50页/共58页计算计算累加和累加和程序程序程序步数程序步数计算工作表格计算工作表格第51页/共58页时间复杂度的渐进表示法时间复杂度的渐进表示法n n大大O表示法表示法n n加法规则加法规则 针对并列程序段针对并列程序段 T(n,m)=T1(n)

28、+T2(m)=O(max(f(n),g(m)c log2n n nlog2n n2 n3 2n 3n n!第52页/共58页n n乘法规则乘法规则 针对嵌套程序段针对嵌套程序段 T(n,m)=T1(n)*T2(m)=O(f(n)*g(m)n n渐进的空间复杂度渐进的空间复杂度 S(n)=O(f(n)n n两个并列循环的例子两个并列循环的例子第53页/共58页 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;

29、i m;i+)/打印各行数据和 cout i “:”sum i endl;渐进时间复杂度为渐进时间复杂度为 O(max(m*n,m)第54页/共58页 template /起泡排序起泡排序 void dataList:bubbleSort()/对表逐趟比较,ArraySize 是表当前长度 int i=1;int exchange=1;/当 exchange 为 0 则停止排序 while(i ArraySize&exchange)BubbleExchange(i,exchange);i+;/一趟比较 第55页/共58页template void dataList:BubbleExchange(int i,int&exchange)exchange=0;/假定元素未交换 for(int j=ArraySize-1;j=i;j-)if(Elementj-1 Elementj)Swap(j-1,j);/发生逆序,交换 exchange=1;/做“发生交换”标志 第56页/共58页渐进时间复杂度渐进时间复杂度 O(f(n)*g(n)=O(n2)BubblrSort n-1趟趟BubbleExchange()n-i次比较次比较第57页/共58页感谢您的观看！第58页/共58页