C++数据结构.ppt

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

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

2、课程课程”表格表格 课程编号 课 程 名 学时 024002 程序设计基础 64 024010 汇编语言 48 024016 计算机原理 64 024020 数据结构 64 024021 微机技术 64 024024 操作系统 48 024026 数据库原理 48 选课单包含如下信息选课单包含如下信息 (ADTs: Abstract Data Types)ADT NaturalNumber isobjects: (MaxInt)。Function: x, y NaturalNumber;False, True Boolean, 、 、 、Zero( ) : 0 NaturalNumberIsZ

3、ero(x) : if (x=0) True Boolean else FalseAdd (x, y) : if (x+y=MaxInt) x+y NaturalNumber else MaxIntSubtract (x, y) : if (x 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 面向对象面向对象 = 对象类继承通信对象类继承通信clas

4、sinstanceF F F void selectSort ( int a , 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 (dataList) #ifn

5、def DATALIST_H #define DATALIST_H #include 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

6、 Sort ( ); friend ostream& operator (ostream& outStream, const datalist& outList); friend istream& operator (istream& inStream, const datalist& inList); ; #endif #ifndef SELECTTM_H #define SELECTTM_H #include “datalist.h” template void dataList : Swap (const int m1, const int m2) /交换由交换由m1, m2为下标的两个

7、数组元素的值为下标的两个数组元素的值 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 (int k = low+1, k = high, k+) if ( Elementmax Elementk ) max = k; return

8、max; template ostream&operator (ostream& OutStream, const dataList OutList) OutStream “Array Contents : n”; for (int i=0; iOutList.ArraySize; i+) OutStream OutList.Elementi ; OutStream endl; OuStream “Array Current Size : ” OutList.ArraySize endl; return OutStream; template istream& operator (istrea

9、m& InStream, dataList InList) /输入对象为输入对象为InList，输入流对象为输入流对象为InStream cout InList.ArraySize; cout “Enter array elements : n”; for (int i=0; iInList.ArraySize; i+) cout “Elememt” i InList.Elementi; return InStream; template void dataList:Sort ( ) /按非递减顺序对按非递减顺序对ArraySize个关键码个关键码 /Element0ElementArrayS

10、ize-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; int main ( ) dataList TestList (SIZE); cin TestList; cout “Testing Selection Sort : n” TestList endl; TestList.Sort ( ); cout “After sorting : n” TestLis

11、t endl; return 0; (Sequenial Search) int seqsearch ( int a , const int n, const int x ) /a0,an-1 1 2 int i = 0; 3 while ( i n & ai != x ) 4 i+; 5 if ( i = n ) return -1; 6 return i; 7 void TimeSearch ( ) /在在1.1000中搜索中搜索0,10,90,100,200,1000 int a1001, n20; for ( int j=1; j=1000; j+ ) aj = j; /a1=1, a

12、2=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, stop; time (start); int k = seqsearch (a, nj, 0); time (stop); long runTime = stop - start; cout nj runTime endl; cout Times are in hundredths

13、 of a second. endl; n 0 10 20 30 40 50 60 70 80 90 runTime 0 0 0 0 0 0 0 0 0 0 n1002003004005006007008009001000 runTime 0 0 0 0 0 0 0 0 0 0void TimeSearch ( ) int a1001, n20; const long r20 = 300000, 300000, 200000, 200000, 100000, 100000, 100000, 80000, 80000, 50000, 50000, 25000, 15000, 15000, 100

14、00, 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 ); time (stop); long totalTime = stop -

15、 start; float runTime = (float)(totalTime) / (float)(rj); cout nj totalTime runTime endl; n 0102030405060708090总的运行时间241 533 582 736 467 565 659 604 681 472单个运行时间0.00080.00180.00290.00370.00470.00560.00660.00750.00850.0094 n100 200 300 400 500 600 700 800 900 1000总的运行时间527 505 451 593 494 439 484 46

16、7 434 484单个运行时间0.01050.02020.03010.03950.04940.05850.06910.07780.08680.0968 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 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语句语句 return s; 执行结束得执行结束得 程序步数程序步数count =2 * n + 3程序的简化形式程序的简化形式 void sum ( float a , const int n ) for ( int i=0; in; i+ )