《抽象数据类型及面向对象概念模板算法定义算法性能分析》由会员分享，可在线阅读，更多相关《抽象数据类型及面向对象概念模板算法定义算法性能分析（54页珍藏版）》请在金锄头文库上搜索。
1、 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURESn什么是数据结构什么是数据结构n抽象数据类型及面向对象概抽象数据类型及面向对象概念念n模板模板n算法定义算法定义n算法性能分析与度量算法性能分析与度量Chapter 1 基本概念和算法分析 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES1.1什么是数据结构什么是数据结构n数据：数据是信息的载体，是描述客观事物的数据：数
2、据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。算机程序识别和处理的符号的集合。P.2数值数据数值数据,非数值性数据非数值性数据n数据对象：数据的子集。具有相同性质的数据数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。成员（数据元素）的集合。整数数据对象整数数据对象N=0,1,2,学生数据对象学生数据对象 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES什么是什么是数据结
3、构数据结构？定义定义:由某一数据对象及该对象中所有数由某一数据对象及该对象中所有数据成员之间的关系组成。记为：据成员之间的关系组成。记为：Data_Structure=D,R其中，其中，D是某一数据对象，是某一数据对象，R是该对象是该对象中所有数据成员之间的关系的有限集合中所有数据成员之间的关系的有限集合 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES如：如： n个网站之间的连通关系个网站之间的连通关系树形关系树形关系树形关系树形关系网状关系网状关系网状关系网状关系1526431
4、52643复数的数据结构定义如下：复数的数据结构定义如下：Complex=(C，R)C是包含两个实数的集合是包含两个实数的集合 C1，C2R=P，P是定义在集合上的一种关系是定义在集合上的一种关系C1，C2。 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES数据结构是数据的组织形式n包括三个方面：包括三个方面：u数据元素间的逻辑关系，即数据的数据元素间的逻辑关系，即数据的逻辑结构逻辑结构；u数据元素及其关系在计算机存储内的表示，即数数据元素及其关系在计算机存储内的表示，即数据的据的
5、存储表示存储表示；u数据的运算，即对数据元素施加的数据的运算，即对数据元素施加的操作操作。 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES相关：相关：逻辑结构逻辑结构物理结构物理结构相关操作相关操作实现实现 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES数据的逻辑结构n数据的逻辑结构从逻辑关系上描述数据，与数据数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；的
6、存储无关；n数据的逻辑结构可以看作是从具体问题抽象出来数据的逻辑结构可以看作是从具体问题抽象出来的数据模型；的数据模型；n数据的逻辑结构与数据元素本身的形式、内容无数据的逻辑结构与数据元素本身的形式、内容无关；关；n数据的逻辑结构与数据元素的相对存储位置无关。数据的逻辑结构与数据元素的相对存储位置无关。 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES数据的逻辑结构分类n线性结构线性结构u线性表线性表n非线性结构非线性结构u树树u图（或网络）图（或网络） Department of
7、 Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES线性结构bindevetclibuser Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES树形结构树形结构树树 二叉树二叉树 二叉搜索树二叉搜索树14131211234567891031587101199874566231311 Department of Computer Science & Technology, Nanjing Univers
8、ityfallDATASTRUCTURES堆结构 “最大最大”堆堆 “最小最小”堆堆123548711102916410121151236987 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES图结构图结构 网络结构网络结构12543611331814665161921125634 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES数据的存储结构n数据的存储结构是逻辑结构
9、用计算机语言的实数据的存储结构是逻辑结构用计算机语言的实现；现；n数据的存储结构依赖于计算机语言。数据的存储结构依赖于计算机语言。u顺序存储表示顺序存储表示u链接存储表示链接存储表示u索引存储表示索引存储表示u散列存储表示散列存储表示主要用于内存的主要用于内存的存储表示存储表示主要用于外存主要用于外存(文文件件)的存储表示的存储表示 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES抽象数据类型：抽象数据类型：抽象数据类型：抽象数据类型：n n由用户定义，用以表示应用问题的由用户定义
10、，用以表示应用问题的由用户定义，用以表示应用问题的由用户定义，用以表示应用问题的数据模型数据模型数据模型数据模型n n由由由由基本的数据类型基本的数据类型基本的数据类型基本的数据类型组成组成组成组成, ,并包括并包括并包括并包括一组相关的服务一组相关的服务一组相关的服务一组相关的服务（或称操作）（或称操作）（或称操作）（或称操作）n n信息隐蔽信息隐蔽信息隐蔽信息隐蔽和和和和数据封装数据封装数据封装数据封装，使用与实现相分离，使用与实现相分离，使用与实现相分离，使用与实现相分离n n抽象数据类型可用抽象数据类型可用抽象数据类型可用抽象数据类型可用（D,S,PD,S,P）三元组表示，其三元组表示
11、，其三元组表示，其三元组表示，其中，中，中，中，DD是数据元素的集合（简称数据对象），是数据元素的集合（简称数据对象），是数据元素的集合（简称数据对象），是数据元素的集合（简称数据对象），SS是是是是 D D上的关系集合，上的关系集合，上的关系集合，上的关系集合，PP是对是对是对是对 DD的基本操作集合。的基本操作集合。的基本操作集合。的基本操作集合。 1.2抽象数据类型及面向对象概念抽象数据类型及面向对象概念 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES例：自然数的抽象数据类
12、型定义例：自然数的抽象数据类型定义(P.8)ADTNaturalNumberisobjects:一个整数的有序子集合一个整数的有序子集合,它开始于它开始于0,结束于机器能表示的最大整数结束于机器能表示的最大整数(MaxInt)。Function:对于所有的对于所有的x,y NaturalNumber;False,True Boolean,+、-、=、=等都等都是可用的服务。是可用的服务。 Zero():NaturalNumber 返回自然数返回自然数0IsZero(x):Booleanif(x=0)返回返回Trueelse返回返回False Department of Computer Sci
13、ence & Technology, Nanjing UniversityfallDATASTRUCTURES Add (x,y):NaturalNumber:if(x+y=MaxInt)返回返回x+yelse返回返回MaxInt Equal (x,y):Booleanif(x=y)返回返回Trueelse返回返回False Successor (x):NaturalNumber if(x=MaxInt)返回返回xelse返回返回x+1 Subtract (x,y):NaturalNumberif(x y)返回返回0else返回返回x - yendNaturalNumber Departmen
14、t of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES定义定义 适合多种数据类型的类定义或算法，适合多种数据类型的类定义或算法，在特定环境下通过简单地代换，变成针在特定环境下通过简单地代换，变成针对具体某种数据类型的类定义或算法对具体某种数据类型的类定义或算法1.3模板模板 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES用模板定义用于排序的数据表用模板定义用于排序的数据表(dataList)
15、类类 #ifndefDATALIST_H#defineDATALIST_H#includetemplateclassdataList private:Type*Element;intArraySize;voidSwap (constintm1,constintm2);intMaxKey(constintlow,constinthigh); Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURESpublic: dataList(intsize=10) : ArraySize (size),
16、 Element (new Type Size) dataList ( ) delete Element;void Sort ( );friendostream&operator(ostream&outStream,constdatalist& outList);friendistream&operator(istream&inStream,constdatalist& inList);#endif Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURESdataList类中所有操作作为模
17、板函数的实现类中所有操作作为模板函数的实现#ifndefSELECTTM_H#defineSELECTTM_H#include “datalist.h”templatevoiddataList:Swap(constintm1,constintm2) /交换由交换由m1,m2为下标的两个数组元素的值为下标的两个数组元素的值Type temp=Elementm1;Elementm1 = Elementm2;Element m2 = temp; Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTU
18、REStemplateintdataList:MaxKey(constintlow,constinthigh) /查找数组查找数组ElementlowElementhigh中中/的最大值，函数返回其位置的最大值，函数返回其位置int max = low;for(int k =low+1,k = high, k+)if( Elementmax Elementk ) max = k;returnmax; Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTUREStemplateostream&o
19、perator(ostream&OutStream,constdataListOutList) OutStream“Array Contents: n”;for (inti = 0;i OutList.ArraySize;i+)OutStream OutList.Elementi;OutStreamendl;OuStream“Array Current Size:”OutList.ArraySizeendl;returnOutStream; Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCT
20、UREStemplateistream& operator (istream&InStream,dataListInList) /输入对象为输入对象为InList，输入流对象为，输入流对象为InStream cout InList.ArraySize;cout “Enter array elements : n”;for (inti = 0;i InList.ArraySize;i+) cout “Elememt” i InList.Elementi;returnInStream; Department of Computer Science & Technology, Nanjing Uni
21、versityfallDATASTRUCTUREStemplatevoid dataList:Sort ( ) /按递减顺序对按递减顺序对ArraySize个关键码个关键码/Element0ElementArraySize-1排序排序。for ( int i = ArraySize -1; i 0; i- ) intj = MaxKey (0, i);if ( j != i ) swap (j, i);#endif Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES使用模板的选择排序
22、算法的主函数使用模板的选择排序算法的主函数#include “selecttm.h”constint SIZE = 10;int main ( ) dataList TestList (SIZE); cin TestList; cout “Testing Selection Sort :n” TestList endl; TestList.Sort ( ); cout “After sorting : n” TestList endl; return 0; Department of Computer Science & Technology, Nanjing UniversityfallDA
23、TASTRUCTURES定义定义：是对特定问题求解步骤的一种描述，是对特定问题求解步骤的一种描述，算法是算法是指令指令的的有限有限序列，其中每一条指令表示序列，其中每一条指令表示一个或多个操作。一个或多个操作。l特性特性：u输入输入u输出输出u确定性确定性u有穷性有穷性 u有效性有效性1.4算法定义算法定义 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES算法设计算法设计：自顶向下，逐步求精自顶向下，逐步求精例：选择排序问题例：选择排序问题n算法框架：算法框架：初始值初始值akfo
24、r(int i = 0; i n-1; i+)/n-1趟趟 从从ai检查到检查到an-1;若最小的整数在若最小的整数在ai,交换交换ai与与ak;细化程序：程序细化程序：程序SelectSort Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURESvoid selectSort ( int a ,constint n ) /对对n个整数个整数a0,a1,an-1, 按非递减顺序排序按非递减顺序排序for( int i = 0; i n-1; i+ ) int k = i;/从从ai检查
25、到检查到an-1,找最小的整数找最小的整数,在在ak for( int j = i+1;j n; j+ ) if ( aj ak ) k = j;/k指示当前找到的最小整数指示当前找到的最小整数 int temp = ai; ai = ak; ak = temp;/交换交换ai与与ak Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES四个层次：四个层次：程序不含语法错误程序不含语法错误;程序对于几组输入数据能够得出满足规格程序对于几组输入数据能够得出满足规格说明要求的结果说明要求的
26、结果;程序对于精心选择的典型、苛刻而带有刁程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明难性的几组输入数据能够得出满足规格说明要求的结果要求的结果;程序对于一切合法的输入数据都能产生满程序对于一切合法的输入数据都能产生满足规格说明要求的结果。足规格说明要求的结果。1.5算法性能分析与度量算法性能分析与度量l正确性正确性 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES可使用性可使用性可读性可读性健壮性健壮性(鲁棒性鲁棒性)效率效率时间代价时间代价空间代价
27、空间代价 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES后期测试后期测试事前估计事前估计空间复杂性度量空间复杂性度量时间复杂性度量时间复杂性度量算法效率的度量：算法效率的度量： Department of Computer Science & Technology, Nanjing UniversityfallDATA
28、STRUCTURES一般算法在执行期间所需要的存储量一般算法在执行期间所需要的存储量应该包括以下应该包括以下3个部分：个部分：（1）输入数据所占用的空间）输入数据所占用的空间（2）程序代码所占用的空间）程序代码所占用的空间（3）辅助变量所占用的空间）辅助变量所占用的空间算法空间复杂度度量算法空间复杂度度量 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES例例1：求表达式：求表达式a+b+b*c+(a+b-c)/(a+b)+4.0floatabc(floata,floatb,floa
29、tc)returna+b+b*c+(a+b-c)/(a+b)+4.0例例2:以迭代方式求累加和以迭代方式求累加和float sum ( float a , constint n ) float s = 0.0; for ( int i = 0; i n; i+ ) s += ai; return s; Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES例例3.3.递归实现累加和递归实现累加和floatrsum(floata ,constintn)if(n=0)return0;else
30、returnrsum(a,n-1)+an-1)空间复杂度是指当问题的规模以某种空间复杂度是指当问题的规模以某种单位从单位从1增加到增加到n时，解决这个问题的时，解决这个问题的算法在执行时所占用的存储空间也以算法在执行时所占用的存储空间也以某种单位由某种单位由1增加到增加到S（n）-P.27 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURESn运行时间运行时间u程序步程序步语法上或语义上有意义的一段指令序列语法上或语义上有意义的一段指令序列执行时间与实例特性无关执行时间与实例特性无关例
31、如：例如：注释：程序步数为注释：程序步数为0声明语句：程序步数为声明语句：程序步数为0表达式：程序步数为表达式：程序步数为1，returna+b+b*c算法的时间复杂度度量算法的时间复杂度度量 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES赋值语句赋值语句=循环语句（循环控制部分，执行语句）循环语句（循环控制部分，执行语句）for(;)whiledodowhileswitch语句语句ifthen函数执行语句：函数执行语句：动态存储管理：动态存储管理：newdeletesizeof
32、()转移语句：转移语句：continue,break,goto,return Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES例例 以迭代方式求累加和的函数以迭代方式求累加和的函数行行 float sum ( float a , constint n ) 1 2 float s = 0.0; 3 for ( int i = 0; i n; i+ ) 4 s += ai; 5 return s; 6 n n 程序步确定方法程序步确定方法 插入计数全局变量插入计数全局变量countco
33、unt Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURESfloat sum ( floata , constint n ) float s = 0.0; count+; /count统计执行语句条数统计执行语句条数 for( int i = 0; i =n0时，时，T(n)=cf(n),则记为则记为T(n)=O(f(n) Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES
34、 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES例例:(线性函数线性函数)考察考察f(n)=3n+2例例:平方平方函数函数考察考察f(n)=10n2+4n+2 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURE
35、Sn例：设有两个算法在同一机器上运行，其执例：设有两个算法在同一机器上运行，其执行时间分别为行时间分别为100n2和和2n，问：要使前者快，问：要使前者快于后者，于后者，n至少要取多大？至少要取多大？解答：解答：问题是找出满足问题是找出满足100n22n=8192n=14时，时，100n2=196002n=16384n=15时，时，100n2=225002n=32764取取n=15满足要求。满足要求。启示启示 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURESclog2nnnlog2
36、nn2n32n3nn!大大O表示法下表示法下: Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES使用大（使用大（O）表示法：）表示法：对于多项式，我们只保留最高次幂的项，对于多项式，我们只保留最高次幂的项，常数系数和低阶项可以不要。常数系数和低阶项可以不要。加法规则加法规则 : :针对并列程序段针对并列程序段 T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)clog2nnnlog2nn2n32n3nn! Department of Computer Scienc
37、e & Technology, Nanjing UniversityfallDATASTRUCTURES乘法规则乘法规则针对嵌套程序段针对嵌套程序段T(n,m)=T1(n)*T2(m)=O(f(n)*g(m)特例：特例：若若T1(n)=O(c),c与与n无关的任意常无关的任意常数，数，T2(n)=O(f(n),则则T(n)=O(f(n)任何非任何非0正常数都属于同一数量级，记为正常数都属于同一数量级，记为O(1) Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES例例1 1：P.33
38、P.33void example (float x ,int m, int n, int k)float sum ;for(int i = 0; i m;i+ ) sumi = 0.0;for ( int j=0;jn; j+ ) sumi += xij; for ( i = 0;i m;i+ ) cout “Line ” i “ :” sum i endl; Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES例例2：P.33-34起泡排序的算法起泡排序的算法templatevoid
39、 dataList:bubbleSort ( ) int i = 1; int exchange = 1; /当当exchange为为0则停止排序则停止排序 while ( i ArraySize & exchange ) BubbleExchange ( i, exchange ); i+; /一趟比较一趟比较 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTUREStemplatevoid dataList:BubbleExchange(constint i, int&exchange
40、 ) exchange = 0; /假定元素未交换假定元素未交换for ( intj = ArraySize-1;j=i; j-) if ( Elementj-1 Elementj ) Swap ( j -1, j ); /发生逆序发生逆序/交换交换Elementj-1与与Elementj exchange = 1;/做做“发生了交换发生了交换”标志标志 Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURESBubbleSortn- -1趟趟BubbleExchange()n- -i次比较次比较渐进时间复杂度渐进时间复杂度O(f (n)*g (n)= O(n2) Department of Computer Science & Technology, Nanjing UniversityfallDATASTRUCTURES渐进的空间复杂度渐进的空间复杂度S(n)=O(f(n)
