C++数据结构.ppt

《C++数据结构.ppt》由会员分享，可在线阅读，更多相关《C++数据结构.ppt（56页珍藏版）》请在课桌文档上搜索。

1、数据结构DATA STRUCTURE,C+描述,什么是数据结构抽象数据类型及面向对象概念数据结构的抽象层次用C+描述面向对象程序算法定义模板性能分析与度量,第一章 绪论,“学生”表格,“课程”表格,选课单包含如下信息 学 号 课程编号 成 绩 时 间 学生选课系统中实体构成的网状关系,UNIX文件系统的系统结构图,数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据非数值性数据数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。整数数据对象 N=0,1,2,学生数据对象,什么是数据结构,定义:由某一数据对象及该对

2、象中所有数据成员之间的关系组成。记为：Data_Structure=D,R 其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。,n个网站之间的连通关系,树形关系,网状关系,抽象数据类型及面向对象概念,数据类型 定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称.C语言中的数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值,抽象数据类型(ADTs:Abstract Data Types),由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现

3、相分离,自然数的抽象数据类型定义,ADT NaturalNumber isobjects:一个整数的有序子集合,它开始于0,结束于机器能表示的最大整数(MaxInt)。Function:对于所有的 x,y NaturalNumber;False,True Boolean,+、-、=、=等都是可用的服务。Zero():返回自然数0 NaturalNumber,IsZero(x):if(x=0)返回True Boolean else 返回FalseAdd(x,y):if(x+y=MaxInt)返回 x+y NaturalNumber else 返回MaxIntSubtract(x,y):if(x

4、y)返回 0 NaturalNumber else 返回 x-yEqual(x,y):if(x=y)返回True Boolean else 返回 FalseSuccessor(x):if(x=MaxInt)返回 x NaturalNumber else 返回 x+1end NaturalNumber,面向对象的概念 面向对象=对象类继承通信对象在应用问题中出现的各种实体、事件、规格说明等由一组属性值和在这组值上的一组服务（或称操作）构成类(class)，实例(instance)具有相同属性和服务的对象归于同一类，形成类类中的一个对象为该类的一个实例,继承 派生类：载重车，轿车，摩托车，子类 特

5、化类(特殊化类)基类：车辆 父类 泛化类(一般化类)通信 消息传递用于描述数据结构的语言 Smalltalk Effel C+Java,线形聚类直接存取类顺序存取类广义索引类非线形聚类层次聚集类 树，二叉树，堆群聚集类 集合，图,数据结构的抽象层次,数据结构的抽象层次,线性聚集类中各数据成员之间的线性关系,树形结构,树 二叉树 二叉搜索树,堆结构,“最大”堆“最小”堆,群聚类,图结构 网络结构,用C+描述面向对象程序,C+的函数特征C+的数据声明C+的作用域C+的类C+的对象C+的输入/输出C+的函数C+的参数传递,C+的函数名重载和操作符重载C+的动态存储分配友元(friend)函数内联(i

6、nline)函数结构(struct)与类联合(Union)与类,算法定义,定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列特性：输入 有0个或多个输入输出 有一个或多个输出(处理结果)确定性 每步定义都是确切、无歧义的有穷性 算法应在执行有穷步后结束有效性 每一条运算应足够基本,事例学习：选择排序问题明确问题：非递减排序解决方案：逐个选择最小数据算法框架：for(int i=0;in-1;i+)/n-1趟 从ai检查到an-1;若最小的整数在ak,交换ai与ak;细化程序：程序 SelectSort,算法设计 自顶向下，逐步求精,void selectSort(int a,

7、const int n)/对n个整数a0,a1,an-1,按非递减顺序排序 for(int i=0;in-1;i+)int k=i;/从ai检查到an-1,找最小的整数,在ak for(int j=i+1;jn;j+)if(aj ak)k=j;/k指示当前找到的最小整数 int temp=ai;ai=ak;ak=temp;/交换ai与ak,模板(template),定义 适合多种数据类型的类定义或算法，在特定环境下通过简单地代换，变成针对具体某种数据类型的类定义或算法,用模板定义用于排序的数据表(dataList)类#ifndef DATALIST_H#define DATALIST_H#in

8、clude template class dataList private:Type*Element;int ArraySize;void Swap(const int m1,const int m2);int MaxKey(const int low,const int high);,public:dataList(int size=10):ArraySize(size),Element(new Type Size)dataList()delete Element;void Sort();friend ostream#endif,dataList类中所有操作作为模板函数的实现#ifndef

9、SELECTTM_H#define SELECTTM_H#include“datalist.h”template void dataList:Swap(const int m1,const int m2)/交换由m1,m2为下标的两个数组元素的值 Type temp=Element m1;Element m1=Element m2;Element m2=temp;,template int dataList:MaxKey(const int low,const int high)/查找数组ElementlowElementhigh中的/最大值，函数返回其位置 int max=low;for(i

10、nt k=low+1,k=high,k+)if(Elementmax Elementk)max=k;return max;,template ostream,template istream,template void dataList:Sort()/按非递减顺序对ArraySize个关键码/Element0ElementArraySize-1排序。for(int i=ArraySize-1;i0;i-)int j=MaxKey(0,i);if(j!=i)swap(j,i);#endif,使用模板的选择排序算法的主函数#include“selecttm.h”const int SIZE=10;

11、int main()dataList TestList(SIZE);cin TestList;cout“Testing Selection Sort:n”TestList endl;TestList.Sort();cout“After sorting:n”TestList endl;return 0;,性能分析与度量,算法的性能标准算法的后期测试算法的事前估计,算法的性能标准,正确性可使用性可读性效率健壮性,算法的后期测试,在算法中的某些部位插装时间函数 time()测定算法完成某一功能所花费的时间,顺序搜索(Sequenial Search)行 int seqsearch(int a,con

12、st int n,const int x)/a0,an-1 1 2 int i=0;3 while(i n 7,插装time()的计时程序 void TimeSearch()/在1.1000中搜索0,10,90,100,200,1000 int a1001,n20;for(int j=1;j=1000;j+)aj=j;/a1=1,a2=2,for(j=0;j10;j+)nj=10*j;/n0=0,n1=10,n2=20 nj+10=100*(j+1);/n10=100,n11=200,n12=300.cout n time endl;,for(j=0;j20;j+)long start,sto

13、p;time(start);int k=seqsearch(a,nj,0);time(stop);long runTime=stop-start;cout nj runTime endl;cout Times are in hundredths of a second.endl;,程序测试结果输出,改进的计时程序void TimeSearch()int a1001,n20;const long r20=300000,300000,200000,200000,100000,100000,100000,80000,80000,50000,50000,25000,15000,15000,10000,

14、7500,7000,6000,5000,5000;for(int j=1;j=1000;j+)aj=j;for(j=0;j10;j+)nj=10*j;nj+10=100*(j+1);cout n totalTime runTime endl;,for(j=0;j20;j+)long start,stop;time(start);/开始计时 for(long b=1;b=rj;b+)int k=seqsearch(a,nj,0);/执行rj次 time(stop);/停止计时 long totalTime=stop-start;float runTime=(float)(totalTime)/(

15、float)(rj);cout nj totalTime runTime endl;,程序测试结果输出,算法的事前估计,空间复杂度时间复杂度,空间复杂度度量,存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占的空间可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过new和delete命令动态使用的空间,时间复杂度度量,编译时间运行时间程序步语法上或语义上有意义的一段指令序列执行时间与实例特性无关例如：注释：程序步数为0 声明语句：程序步数为0 表达式：程序步数为1,例 以迭代方式求累加和的函数行

16、float sum(float a,const int n)1 2 float s=0.0;3 for(int i=0;in;i+)4 s+=ai;5 return s;6,程序步确定方法 插入计数全局变量count 建表，列出个语句的程序步,在求累加和程序中加入count语句 float sum(float a,const int n)float s=0.0;count+;/count统计执行语句条数 for(int i=0;in;i+)count+;/针对for语句 s+=ai;count+;/针对赋值语句 count+;/针对for的最后一次 count+;/针对return语句 ret

17、urn s;执行结束得 程序步数count=2*n+3,程序的简化形式 void sum(float a,const int n)for(int i=0;in;i+)count+=2;count+=3;,注意：一个语句本身的程序步数可能不等于该语句一 次执行所具有的程序步数。例如：赋值语句x=sum(R,n);本身的程序步数为1；一次执行对函数 sum(R,n)的调用需要的程序步数为 2*n+3；一次执行的程序步数为1+2*n+3=2*n+4,累加和程序程序步数计算工作表格,时间复杂度的渐进表示法,大O表示法加法规则 针对并列程序段 T(n,m)=T1(n)+T2(m)=O(max(f(n),

18、g(m)c log2n n nlog2n n2 n3 2n 3n n!,乘法规则 针对嵌套程序段 T(n,m)=T1(n)*T2(m)=O(f(n)*g(m)渐进的空间复杂度 S(n)=O(f(n),两个并列循环的例子 void example(float x,int m,int n,int k)float sum;for(int i=0;im;i+)/x 中各行 sumi=0.0;/数据累加 for(int j=0;jn;j+)sumi+=xij;for(i=0;i m;i+)/打印各行数据和 cout“Line”i“:”sum i endl;渐进时间复杂度为O(max(m*n,m),template/起泡排序的算法 void dataList:bubbleSort()/对表Element0到ElementArraySize-1/逐趟进行比较,ArraySize是表当前长度 int i=1;int exchange=1;/当exchange为0则停止排序 while(i ArraySize/一趟比较,template void dataList:BubbleExchange(const int i,int/做“发生了交换”标志 渐进时间复杂度 O(f(n)*g(n)=,再见,