抽象数据类型与面向对象概念(共70页).ppt

1、 学学 号号 姓姓 名名 性别性别 籍籍 贯贯 出生年月出生年月 1 98131 刘激扬刘激扬 男男 北北 京京 1979.12 2 98164 衣春生衣春生 男男 青青 岛岛 1979.07 3 98165 卢声凯卢声凯 男男 天天 津津 1981.02 4 98182 袁秋慧袁秋慧 女女 广广 州州 1980.10 5 98224 洪洪 伟伟 男男 太太 原原 1981.01 6 98236 熊南燕熊南燕 女女 苏苏 州州 1980.03 7 98297 宫宫 力力 男男 北北 京京 1981.01 8 98310 蔡晓莉蔡晓莉 女女 昆昆 明明 1981.02 9 98318 陈陈 健健

2、 男男 杭杭 州州 1979.12 课程编号课程编号 课课 程程 名名 学时学时 024002 程序设计基础程序设计基础 64 024010 汇编语言汇编语言 48 024016 计算机原理计算机原理 64 024020 数据结构数据结构 64 024021 微机技术微机技术 64 024024 操作系统操作系统 48 024026 数据库原理数据库原理 48学生学生( (学号学号, ,姓名姓名, ,性别性别, ,籍贯籍贯) )课程课程( (课程号课程号, ,课程名课程名, ,学分学分) )选课选课( (学号学号, ,课程号课程号, ,成绩成绩) )/ (root)binlibuseretcm

3、athdsswyintaoxieStack.cppQueue.cppTree.cpp 1524361524361413121123456789103158710119987456623131bindevetclibuser112354871110291641012115123698712564312543611331814665161921n数据的存储结构是逻辑结构用计算数据的存储结构是逻辑结构用计算机语言的实现；机语言的实现；n数据的存储结构依赖于计算机语言。数据的存储结构依赖于计算机语言。u 顺序存储表示顺序存储表示u 链接存储表示链接存储表示u 索引存储表示索引存储表示u 散列存储表示散

4、列存储表示主要用于内存的主要用于内存的存储表示存储表示主要用于外存主要用于外存 (文文件件) 的存储表示的存储表示 抽抽象象数数据据类类型型查找查找 登录登录 删除删除 修改修改 符符 号号 表表属性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(aPoin

5、t)Draw( )move(x, y)contains(aPoint)效劳效劳效劳效劳四边形类及其对象四边形类及其对象quadrilateralDraw( )move(x, y)contains(aPoint)PolygonreferencePointVerticesPolygon 类类referencePointVerticesDraw( )move(x, y)contains(aPoint)Polygon的子类的子类Quadrilateral类类Quadrilateral void selectSort ( int a , const int n ) /对n个整数a0,a1,an-1按递增

6、顺序排序 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; #ifndef DATALIST_H#define DATALIST_H#include template class dataList private: Type *Element; int ArraySize; void Swap (int m1, int m2); int MaxKey (

7、int low, int high); public: dataList (int size = 10) : ArraySize (size), Element (new Type Size) dataList ( ) delete Element; void Sort ( ); friend ostream& operator (ostream& outStream, datalist& outList); friend istream& operator (istream& inStream, datalist& inList); ; #en

8、dif template int dataList: MaxKey (int low, int high) /查找数组Elementlow到Elementhigh /中的最大值，函数返回其位置 int max = low; for (int k = low+1, k = high, k+) if ( Elementmax Elementk ) max = k; return max; template ostream& operator (ostream& OutStream, dataList OutList) OutStream “数组内容数组内容 : n; for (in

9、t i = 0; i OutList.ArraySize; i+) OutStream OutList.Elementi ; OutStream endl; OuStream “数组当前大小数组当前大小 : OutList.ArraySize endl; return OutStream; template istream& operator (istream& InStream, dataList InList) /输入对象为输入对象为InList，输入流对象为，输入流对象为InStream cout InList.ArraySize; cout “录入数组元素值录入数组元素

10、值 : n; for (int i = 0; i InList.ArraySize; i+) cout “元素元素 i InList.Elementi; return InStream; template void dataList : Sort ( ) for ( int i = ArraySize -1; i 0; i- ) int j = MaxKey (0, i); if ( j != i ) swap (j, i); #endif time ( ) (Sequenial Search)int seqsearch ( int a , int n, int x ) /在在a0,an 1中

11、搜索中搜索x int i = 0; while ( i n & ai != x ) i+; if ( i = n ) return -1; return i; double start, stop; time (&start); int k = seqsearch (a, n, x); time (&stop); double runTime = stop - start; cout n runTime endl;float sum ( float a , int float sum ( float a , int n ) n ) float s = 0.0; coun

12、t+;/count 统计执行语句条数 for ( int i = 0; i n; i+ ) count+;/针对 for 语句 s += ai; count+; /针对赋值语句 count+;/针对 for 的最后一次 count+;/针对 return 语句 return s; 执行结束得执行结束得 程序步数程序步数 count = 2*n+3 void sum ( float a , int n ) for ( int i = 0; i n; i+ ) count += 2; count += 3; 程程 序序 语语 句句一一次次执执行行所所需需程程序序步步数数执执行行频频度度 程程序序

13、步步数数 0 1 0 float s = 0.0; 1 1 1 for ( int i=0; in; i+ ) 1 n+1 n+1 s += ai; 1 n n return s; 1 1 1 0 1 0 总总程程序序步步数数 2n+3void MatrixMultiply ( int Ann, int Bnn, int Cnn ) for ( int i = 0; i n; i+ ) n+1 for ( int j = 0; j n; j+ ) n(n+1) Cij = 0; n2 for ( int k = 0; k n; k+ ) n2(n+1) Cij = Cij + Aik * Bk

14、j; n3 2n3 + 3n2 + 2n +1n算法中所有语句的频度之和是矩阵阶数算法中所有语句的频度之和是矩阵阶数n的函数的函数n T(n) = 2n3 + 3n2 + 2n +1n一般地，称一般地，称 n 是问题的规模。那么时间是问题的规模。那么时间复杂度复杂度 T(n) 是问题规模是问题规模 n 的函数。的函数。n当当n趋于无穷大时，把时间复杂度的数量趋于无穷大时，把时间复杂度的数量级阶称为算法的渐进时间复杂度级阶称为算法的渐进时间复杂度n T(n) = O(n3) -大大O表示法表示法x = 0; y = 0;for ( int k = 0; k n; k + ) x +;for (

15、int i = 0; i n; i+ ) for ( int j = 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) 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

16、= 0; i m; i+ ) /打印各行数据和打印各行数据和 cout i “ : sum i endl; 渐进时间复杂度为渐进时间复杂度为 O(max (m*n, m) template /起泡排序起泡排序 void dataList : bubbleSort ( ) /对表逐趟比较对表逐趟比较, ArraySize 是表当前长度是表当前长度 int i = 1; int exchange = 1; /当当 exchange 为为 0 那么停止排序那么停止排序 while ( i ArraySize & exchange ) BubbleExchange ( i, exchange

17、); i+; /一趟比较一趟比较 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; /做做“发生交换发生交换标志标志 O(f (n)*g (n) = O(n2) 1121ni)n(ni)(nBubblrSort n- -1趟趟Bub

18、bleExchange ( ) n-i次比较次比较 int i = n-1; while ( i = 0 & Ai != k ) i-; return i; i- n A 中各元素的取值中各元素的取值 k n例：设有两个算法在同一机器上运行，例：设有两个算法在同一机器上运行，其执行时间分别为其执行时间分别为 100n2 和和 2n，问：要，问：要使前者快于后者，使前者快于后者，n 至少要取多大？至少要取多大？ 解答：解答： 问题是找出满足问题是找出满足 100n2 2n = 8192 n = 14时，时，100n2 = 19600 2n = 16384 n = 15时，时，100n2 = 22500 2n = 32764 取取 n = 15 满足要求。满足要求。 #include iostream.h #define arraySize 100#define MaxInt 0 x7fffffffint cal