抽象数据类型与面向对象概念

什么是数据结构抽象数据类型及面向对象概念数据结构的抽象层次算法定义模板性能分析与度量第一章绪论“学生”表格“课程”表格

“选课单”包含如下信息

学号课程编号成绩时间

学生选课系统中实体构成的网状关系学生(学号,姓名,性别,籍贯)课程(课程号,课程名,学分)选课(学号,课程号,成绩)UNIX文件系统的系统结构图/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp数据（data）数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据；非数值性数据。数据元素(dataelement)数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(DataItem)组成。数据项是具有独立含义的最小标识单位。数据元素又称为元素、结点、记录。数据对象(dataobject)数据的子集。具有相同性质的数据成员（数据元素）的集合。整数数据对象：N={0,1,2,…}学生数据对象。什么是数据结构定义:由某一数据对象及该对象中所有数据成员之间的关系组成。记为：Data_Structure={D,R}

其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。N个网点之间的连通关系

树形关系网状关系152436152436数据结构是数据的组织形式数据元素间间的逻辑关系，即数据的的逻辑结构；数据元素及及其关系在在计算机存存储内的表表示，即数数据的存储表示；数据的运算算，即对数数据元素施施加的操作。数据的逻辑辑结构数据的逻辑辑结构从逻辑关系系上描述数数据，与数据的存存储无关；数据的逻辑辑结构可以以看作是从具体问题题抽象出来来的数据模模型；数据的逻辑辑结构与数据元素素本身的形形式、内容容无关；数据的逻辑辑结构与数数据元素的的相对位置置无关。数据的逻辑辑结构分类类线性结构。。线性表非线性结构构。树图（或网络络）线性结构树形结构树二二叉树二二叉搜搜索树1413121123456789103158710119987456623131bindevetclibuser1堆结构“最大”堆“最小”堆123548711102916410121151236987图结构网网络结构12564312543611331814665161921数据的存储结结构数据的存储结结构是逻辑结结构用计算机机语言的实现现；数据的存储结结构依赖于计计算机语言。。顺序存储表示示链接存储表示示索引存储表示示散列存储表示示主要用于内存存的存储表示示主要用于外存存(文件)的存储表表示抽象数据类型型及面向对象象概念数据类型。定义：一组性质相同同的值的集合合,以及定定义于这个值值集合上的一一组操作的总总称。C语言中的数据据类型。charintfloatdoublevoid字符型整型型浮点型双双精度型无无值构造数据类型型由基本数据类型型或构造数据类型型组成。构造数据类型型由不同成分类型型构成。基本数据类型型可以看作是是计算机中已已实现的数据据结构。数据类型就是是数据结构，，不过它是从从编程者的角角度来使用的的。数据类型是模模板，必须定定义属于某种种数据类型的的变量，才能能参加运算。。抽象数据类型型(ADTs:AbstractDataTypes)由用户定义，，用以表示应应用问题的数据模型。由基本的数据类类型组成,并包包括一组相关的服服务（或称操作））。信息隐蔽和数据封装，使用与实现现相分离。抽象数据类型型查找登录录删除除修改符号表表自然数的抽象象数据类型定定义ADTNaturalNumberisobjects:一个整数的有有序子集合,它开始于0,结束于机器能能表示的最大大整数(MaxInt)。Function:对于所有的x,yNaturalNumber;False,TrueBoolean,+、-、<、==、=等都是可用的的服务。Zero():NaturalNumber返回自然数0IsZero(x):if(x==0)返回TrueBooleanelse返回FalseAdd(x,y):if(x+y<=MaxInt)返回x+yNaturalNumberelse返返回MaxIntSubtract(x,y):if(x<y)返回0NaturalNumberelse返返回x-yEqual(x,y):if(x==y)返回TrueBooleanelse返回FalseSuccessor(x):if(x==MaxInt)返回xNaturalNumberelse返返回x+1endNaturalNumber面向对象的概概念面向对象=对象＋类类＋继承＋通通信对象在应用问题中中出现的各种种实体、事件、规格说明等。由一组属性值和在这组值上上的一组服务（或称操作））构成。类(class)，实实例(instance)具有相同属性和服务的对象归于同同一类，形成成类。类中的对象为为该类的实例例。属性aPoint1aPoint2aPoint3aPoint4服务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)contains(aPoint)服务服务四边形类及其其对象quadrilateral继承派生类：四边形，三角角形，…子类特化化类(特殊化化类)基类：多边形父类泛化化类(一般化化类)通信消息传递Draw()move(x,y)contains(aPoint)PolygonreferencePointVerticesPolygon类referencePointVerticesDraw()move(x,y)contains(aPoint)Polygon的子类Quadrilateral类Quadrilateral线性结构直接存取类数组,文件件；顺序存取类表,栈,队队列,优优先队列；广义索引类线性索引,搜搜索树。非线性结构层次结构类树,二叉树树,堆；群结构类集合,图。。数据结构的抽抽象层次算法定义定义：一个有穷的指指令集，这些指令为为解决某一特特定任务规定定了一个运算算序列。特性：输入有0个或多个个输入；输出有一个或多个个输出(处理理结果)；确定性每步定义都是是确切无歧义义的；有穷性算法应在执行行有穷步后结结束；有效性每一条运算应应足够基本。。事例学习：选择排序问题题。明确问题：递增排序。解决方案：逐个选择最小小数据。算法框架：for(inti=0;i<n-1;i++){//n-1趟从从a[i]检查查到a[n-1];若若最小整数数在a[k],交换a[i]与a[k];}细化程序：程序SelectSort算法设计自顶向下，逐逐步求精voidselectSort(inta[],constintn){//对n个整数a[0],a[1],……,a[n-1]按递增顺序排排序for(inti=0;i<n-1;i++){intk=i;//从a[i]查到a[n-1],找最小整数,在a[k]for(intj=i+1;j<n;j++)if(a[j]<a[k])k=j;inttemp=a[i];a[i]=a[k];a[k]=temp;}}模板(template)定义适合多种数数据类类型的类定义义或算法，在特特定环环境下下通过过简单单地代代换，，变成成针对具具体某某种数数据类类型的类定义义或算法。。用模板板定义义用于于排序序的数数据表表类#ifndefDATALIST_H#defineDATALIST_H#include<iostream.h>template<classType>classdataList{private:Type*Element;intArraySize;voidSwap(intm1,intm2);intMaxKey(intlow,inthigh);public:dataList(intsize=10):ArraySize(size),Element(newType[Size]){}~dataList(){delete[]Element;}voidSort();friendostream&operator<<(ostream&outStream,datalist<Type>&outList);friendistream&operator>>(istream&inStream,datalist<Type>&inList);};#endif类中中所所有有操操作作作作为为模模板板函函数数的的实实现现#ifndefSELECTTM_H#defineSELECTTM_H#include“datalist.h””template<classType>voiddataList<Type>::Swap(intm1,intm2){//交交换换由由m1,m2为为下下标标的的数数组组元元素素的的值值Typetemp=Element[m1];Element[m1]=Element[m2];Element[m2]=temp;}template<classType>intdataList<Type>::MaxKey(intlow,inthigh){//查找找数数组组Element[low]到Element[high]//中的的最最大大值值，，函函数数返返回回其其位位置置intmax=low;for(intk=low+1,k<=high,k++)if(Element[max]<Element[k])max=k;returnmax;}template<classType>ostream&operator<<(ostream&OutStream,dataList<Type>OutList){OutStream<<“数组内容容:\n”;for(inti=0;i<OutList.ArraySize;i++)OutStream<<OutList.Element[i]<<‘‘’;OutStream<<endl;OuStream<<“数组当前前大小:”<<OutList.ArraySize<<endl;returnOutStream;}template<classType>istream&operator>>(istream&InStream,dataList<Type>InList){//输入入对象为为InList，输入入流对象象为InStreamcout<<“录入数组组当前大大小:”;Instream>>InList.ArraySize;cout<<“录入数组组元素值值:\n”;for(inti=0;i<InList.ArraySize;i++){cout<<“元素”<<i<<“:”;InStream>>InList.Element[i];}returnInStream;}template<classType>voiddataList<Type>::Sort(){//按按非递递减顺顺序对对ArraySize个个关键键码//Element[0]到到Element[ArraySize-1]排序序for(inti=ArraySize-1;i>0;i--){intj=MaxKey(0,i);if(j!=i)swap(j,i);}}#endif使用模模板的的选择择排序序算法法的主主函数数#include“selecttm.h”constintSIZE=10;intmain(){dataList<int>TestList(SIZE);cin>>TestList;cout<<TestList<<endl;TestList.Sort();cout<<TestList<<endl;return0;}性能分分析与与度量量算法的的性能能标准准算法的的后期期测试试算法的的事前前估计计算法的的性能能标准准正确性性可使用用性可读性性效率健壮性性算法的的后期期测试试在算法法中的的某些些部位位插装装时间间函数数time()测定算算法完完成某某一功功能所所花费费时间间。顺序搜搜索(SequenialSearch)intseqsearch(inta[],intn,intx){//在在a[0],……,a[n-1]中中搜索索xinti=0;while(i<n&&a[i]!=x)i++;if(i==n)return-1;returni;}插装time()的计时时程序序doublestart,stop;time(&start);intk=seqsearch(a,n,x);time(&stop);doublerunTime=stop-start;cout<<""<<n<<""<<runTime<<endl;算法的的事前前估计计空间复复杂度度时间复复杂度度空间复复杂度度度量量存储空空间的的固定定部分分程序指指令代代码的的空间间，常常数、、简单单变量量、定定长成成分(如数数组元元素、、结构构成分分、对对象的的数据据成员员等)变量量所占占空间间。可变部部分尺寸与与实例例特性性有关关的成成分变变量所所占空空间、、引用用变量量所占占空间间、递递归栈栈所用用空间间、通通过new和delete命令动动态使使用空空间。。时间复复杂度度度量量编译时时间。。运行时时间。。程序步步。语法上上或语语义上上有意意义的的一段段指令令序列列。执行时时间与与实例例特性性无关关。例如：：声明语语句：程序序步数数为0;表达式式：程序序步数数为1。程序步步确定定方法法插入计计数全全局变变量count建表，，列出出个语语句的的程序序步例以以迭代代方式式求累累加和和的函函数floatsum(floata[],intn){floats=0.0;for(inti=0;i<n;i++)s+=a[i];returns;}在求累累加和和程序序中加加入count语句floatsum(floata[],intn){floats=0.0;count++;//count统计执执行语语句条条数for(inti=0;i<n;i++){count++;//针对for语句s+=a[i];count++;}//针对赋赋值语语句count++;//针对for的最后后一次次count++;//针对return语句returns;}执行结束得得程序步步数count=2*n+3程序的简化化形式voidsum(floata[],intn){for(inti=0;i<n;i++)count+=2;count+=3;}注意意：一个个语语句句本本身身的的程程序序步步数数可可能能不不等等于于该该语语句句一一次次执执行行所所具具有有的的程程序序步步数数。。例如如：：赋赋值值语语句句x=sum(R,n)本身身的的程程序序步步数数为为1；；一次次执执行行对对函函数数sum(R,n)的调用需需要的程程序步数数为2*n+3；一次执行行的程序序步数为为1+2*n+3=2*n+4计算累加和程序程序步数计算工作表格格时间复杂度的的渐进表示法法例求两个个n阶方阵的的乘积C=ABvoidMatrixMultiply(intA[n][n],intB[n][n],intC[n][n]){for(inti=0;i<n;i++)…n+1for(intj=0;j<n;j++){…n(n+1)C[i][j]=0;…n2for(intk=0;k<n;k++)…n2(n+1)C[i][j]=C[i][j]+A[i][k]*B[k][j];…n3}}2n3+3n2+2n+1时间复杂度的的渐进表示法法算法中所有有语句的频频度之和是是矩阵阶数n的函数T(n)=2n3+3n2+2n+1一般地，称称n是是问题的规规模。则时时间复杂度度T(n)是问问题规模n的函函数。当n趋于无无穷大时，，把时间复复杂度的数数量级（阶阶）称为算算法的渐进进时间复杂杂度T(n)=O(n3)----大O表示法法时间复杂度度的渐进表表示法加法规则针对并列程程序段T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)))各种函数的的增长趋势势c<log2n<n<nlog2n<n2<n3<2n<3n<n!变量计数x=0;y=0;for(intk=0;k<n;k++)x++;for(inti=0;i<n;i++)for(intj=0;j<n;j++)y++;T1(n)=O(1)T2(n)=O(n)T3(n)=O(n2)T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2))=O(n2)乘法规则针对嵌套程程序段T(n,m)=T1(n)*T2(m)=O(f(n)*g(m))渐进的空间间复杂度S(n)=O(f(n))两个并列循循环的例子子voidexam(floatx[][],intm,intn){floatsum[];for(inti=0;i<m;i++){//x中各行sum[i]=0.0;//数据累加for(intj=0;j<n;j++)sum[i]+=x[i][j];}for(i=0;i<m;i++)//打印各行数数据和cout<<i<<““:”<<sum[i]<<endl;}渐进进时时间间复复杂杂度度为为O(max(m*n,m))template<classType>//起泡泡排排序序voiddataList<Type>::bubbleSort(){//对表表逐逐趟趟比比较较,ArraySize是表表当当前前长长度度inti=1;intexchange=1;//当exchange为0则停停止止排排序序while(i<ArraySize&&exchange){BubbleExchange(i,exchange);i++;}//一趟趟比比}

template<classType>voiddataList<Type>::BubbleExchange(inti,int&exchange){exchange=0;//假定定元元素素未未交交换换for(intj=ArraySize-1;j>=i;j--)if(Element[j-1]>Element[j]){Swap(j-1,j);//发生生逆逆序序,交交换换exchange=1;//做““发发生生交交换换””标标志志}}渐进进时时间间复复杂杂度度O(f(n)*g(n))=O(n2)BubblrSortn-1趟BubbleExchange()n-i次比比较较有时时,算算法法的的时时间间复复杂杂度度不不仅仅依依赖赖于于问问题题规规模模n，还还与与输输入入实实例例的的初初始始排排列列有有关关。。在数数组组A[n]中查查找找给给定定值值k的算算法法：：inti=n-1;while(i>=0&&A[i]!=k)i--;returni;算法法的的语语句句i--的频频度度不不仅仅与与n有关关，，还还与与A[]中中各各元元素素的的取取值值，以以及及k的取取值值有关关。。例：：设设有有两两个个算算法法在在同同一一机机器器上上运运行行，，其其执执行行时时间间分分别别为为100n2和2n，问问：：要要使使前前者者快快于于后后者者，，n至少少要要取取多多大大？？解答答：：问题题是是找