什么是數(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 匯編語(yǔ)言匯編語(yǔ)言 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ù)庫(kù)原理數(shù)據(jù)庫(kù)原理 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), ,成績(jī)成績(jī)) )/ (root)binlibuseretcm

3、athdsswyintaoxieStack.cppQueue.cppTree.cpp 152436152436 抽抽象象數(shù)數(shù)據(jù)據(jù)類類型型查找查找 登錄登錄 刪除刪除 修改修改 符符 號(hào)號(hào) 表表屬性aPoint1 aPoint2aPoint3 aPoint4服務(wù)服務(wù)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)

4、Draw( )move(x, y)contains(aPoint)服務(wù)服務(wù)服務(wù)服務(wù)四邊形類及其對(duì)象四邊形類及其對(duì)象quadrilateralDraw( )move(x, y)contains(aPoint)PolygonreferencePointVerticesPolygon 類類referencePointVerticesDraw( )move(x, y)contains(aPoint)Polygon的子類的子類Quadrilateral類類Quadrilateral1413121123456789103158710119987456623131bindevetclibuser112354

5、871110291641012115123698712564312543611331814665161921。 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 for ( int j = i+1; j n; j+ ) if ( aj ak ) k = j; int temp = ai; ai = ak; ak = temp; #include template class dataList

6、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) dataList ( ) delete Element; void Sort ( ); friend ostream& operator (ostream& outStream, datalist& outList); fr

7、iend istream& operator (istream& inStream, datalist& inList); #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到El

8、ementhigh /中的最大值，函數(shù)返回其位置 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 “數(shù)組內(nèi)容 : n”; for (int i = 0; i OutList.ArraySize; i+) OutStream OutList.Elementi ; OutStream en

9、dl; OuStream “數(shù)組當(dāng)前大小 : ” OutList.ArraySize endl; return OutStream; template istream& operator (istream& InStream, dataList InList) cout InList.ArraySize; cout “錄入數(shù)組元素值 : n”; for (int i = 0; i InList.ArraySize; i+) cout “元素” i InList.Elementi; return InStream; template void dataList:Sort ( )

10、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 (SIZE); cin TestList; cout TestList endl; TestList.Sort ( ); cout TestList endl; return 0; time ( ) (Sequenial Search)int seqsearch ( int

11、a , int n, int x ) /在在a0,an 1中搜索中搜索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 n ) float s = 0.0; for

12、( 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í)行語(yǔ)句條數(shù) for ( int i = 0; i n; i+ ) count+;/針對(duì) for 語(yǔ)句 s += ai; count+; /針對(duì)賦值語(yǔ)句 count+;/針對(duì) for 的最后一次 count+;/針對(duì) return 語(yǔ)句 return s; 執(zhí)行結(jié)束得執(zhí)行結(jié)束得 程序步數(shù)程序步數(shù) count = 2*n+3 void sum ( float a , int n ) for (

13、int i = 0; i n; i+ ) count += 2; count += 3; 程程 序序 語(yǔ)語(yǔ) 句句一一次次執(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 總總程程序序步步數(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) =

14、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)前長(zhǎng)度 int i = 1; int exchange = 1; /當(dāng) exchange 為 0 則停止排序 while ( i ArraySize & exchange ) BubbleExchange ( i, exchange ); i+; /一趟比較 template void dataList:BubbleExchange(int i, int & ex