什么是數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型及面向?qū)ο蟾拍顢?shù)據(jù)結(jié)構(gòu)的抽象

1、 學(xué)學(xué) 號(hào)號(hào) 姓姓 名名 性別性別 籍籍 貫貫 出生年月出生年月 1 98131 劉激揚(yáng)劉激揚(yáng) 男男 北北 京京 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 課程編號(hào)課程編號(hào) 課課 程程 名名 學(xué)時(shí)學(xué)時(shí) 024002 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ) 64 024010 匯編語言匯編語言 48 024016 計(jì)算機(jī)原理計(jì)算機(jī)原理 64 024020 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 64 024021 微機(jī)技術(shù)微機(jī)技術(shù) 64 024024 操作系統(tǒng)操作系統(tǒng) 48 024026 數(shù)據(jù)庫原理數(shù)據(jù)庫原理 48 學(xué)生學(xué)生 ( (學(xué)號(hào)學(xué)號(hào), ,姓名姓名, ,性別性別, ,籍貫籍貫) ) 課程課程 ( (課程號(hào)課程號(hào), ,課程名課程名, ,學(xué)分學(xué)分) ) 選課選課 ( (學(xué)號(hào)學(xué)號(hào), ,課程號(hào)課程號(hào), ,成績成績) ) / (root) binlib

3、useretc mathdsswyintaoxie Stack.cppQueue.cppTree.cpp 1 5 2 4 3 6 1 5 2 4 3 6 抽抽 象象 數(shù)數(shù) 據(jù)據(jù) 類類 型型 查找查找 登錄登錄 刪除刪除 修改修改 符符 號(hào)號(hào) 表表 屬性 aPoint1 aPoint2 aPoint3 aPoint4 服務(wù)服務(wù) Draw( ) move(x, y) contains(aPoint) 屬性值屬性值 quadrilateral1quadrilateral2 (35, 10) (50, 10) (35, 25) (50, 25) (45, 65) (50, 45) (65, 66) (

4、60, 70) Draw( ) move(x, y) contains(aPoint) Draw( ) move(x, y) contains(aPoint) 服務(wù)服務(wù)服務(wù)服務(wù) 四邊形類及其對(duì)象四邊形類及其對(duì)象 quadrilateral Draw( ) move(x, y) contains(aPoint) Polygon referencePoint Vertices Polygon 類類 referencePoint Vertices Draw( ) move(x, y) contains(aPoint) Polygon的子類的子類 Quadrilateral類類 Quadrilater

5、al 14131211 234 56789103 15 8 7 10 11 9 987 456 62313 1 bindevetclib user 1 12 3548 7 11 10 2 9 16 4 10 1211 5 1 2 36 98 7 12 5 6 4 3 12 54 3 6 11 33 18 14 6 6 5 16 19 21 。 void selectSort ( int a , const int n ) /對(duì)n個(gè)整數(shù)a0,a1,an-1按遞增順序排序 for ( int i = 0; i n-1; i+ ) int k = i; /從ai查到an-1, 找最小整數(shù), 在ak

6、for ( int j = i+1; j n; j+ ) if ( aj ak ) k = j; int temp = ai; ai = ak; ak = temp; #include template class dataList private: Type *Element; int ArraySize; void Swap (int m1, int m2); int MaxKey (int low, int high); public: dataList (int size = 10) : ArraySize (size), Element (new Type Size) dataLis

7、t ( ) delete Element; void Sort ( ); friend ostream friend istream #include “datalist.h” template void dataList : Swap (int m1, int m2) /交換由m1, m2為下標(biāo)的數(shù)組元素的值 Type temp = Element m1; Element m1 = Element m2; Element m2 = temp; template int dataList: MaxKey (int low, int high) /查找數(shù)組Elementlow到Elementhi

8、gh /中的最大值，函數(shù)返回其位置 int max = low; for (int k = low+1, k = high, k+) if ( Elementmax Elementk ) max = k; return max; template ostream for (int i = 0; i OutList.ArraySize; i+) OutStream OutList.Elementi ; OutStream endl; OuStream “數(shù)組當(dāng)前大小 : ” OutList.ArraySize endl; return OutStream; template istream co

9、ut “錄入數(shù)組元素值 : 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); #include “selecttm.h” const int SIZE = 10; int main ( ) dataList TestList (S

10、IZE); cin TestList; cout TestList endl; TestList.Sort ( ); cout TestList endl; return 0; time ( ) (Sequenial Search) int seqsearch ( int a , int n, int x ) /在在a0,an 1中搜索中搜索x int i = 0; while ( i n if ( i = n ) return -1; return i; double start, stop; time ( int k = seqsearch (a, n, x); time ( double

11、 runTime = stop - start; cout n runTime endl; float sum ( float a , int n ) float s = 0.0; for ( int i = 0; i n; i+ ) s += ai; return s; float sum ( float a , int n ) float s = 0.0; count+;/count 統(tǒng)計(jì)執(zhí)行語句條數(shù) for ( int i = 0; i n; i+ ) count+;/針對(duì) for 語句 s += ai; count+; /針對(duì)賦值語句 count+;/針對(duì) for 的最后一次 coun

12、t+;/針對(duì) return 語句 return s; 執(zhí)行結(jié)束得執(zhí)行結(jié)束得 程序步數(shù)程序步數(shù) count = 2*n+3 void sum ( float a , int n ) for ( int i = 0; i n; i+ ) count += 2; count += 3; 程程 序序 語語 句句 一一次次執(zhí)執(zhí)行行所所 需需程程序序步步數(shù)數(shù) 執(zhí)執(zhí)行行 頻頻度度 程程序序 步步數(shù)數(shù) 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 總總程程序序步

13、步數(shù)數(shù) 2n+3 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), 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 exam ( float x , int m, int n ) float sum ; for ( int i = 0; i m; i+ ) /x中各行 sumi = 0.0; /數(shù)據(jù)累加 for ( int j = 0; j n; j+ ) sumi += xij; for ( i = 0; i m; i+ ) /打印各行數(shù)據(jù)和 cout i “ : ” sum i endl; O(max (m*n, m) template / void dataList : bubbleSort ( ) /對(duì)表逐趟比較, ArraySize 是表當(dāng)前長度 int i = 1; int exchange = 1; /當(dāng) exchange 為 0 則停止排序 while ( i ArraySize i+; /一趟比較 template void dataList: BubbleExchange(int i, int /