什么是数据结构

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 152436152436 抽抽象象数数据据类类型型查找查找 登录登录 删除删除 修改修改 符符 号号 表表属性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(aPoint)

4、Draw( )move(x, y)contains(aPoint)服务服务服务服务四边形类及其对象四边形类及其对象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 ) /对n个整数a0,a1,an-1按递增顺序排序 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; #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为下标的数组元素的值 Type temp = Element m1; Element m1 = Element m2; Element m2 = temp; template int dataList: MaxKey (int low, int high) /查找数组Elementlow到El

8、ementhigh /中的最大值，函数返回其位置 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 (int i = 0; i OutList.ArraySize; i+) OutStream OutList.Elementi ; OutStream en

9、dl; OuStream “数组当前大小 : ” OutList.ArraySize endl; return OutStream; template istream& operator (istream& InStream, dataList InList) cout InList.ArraySize; cout “录入数组元素值 : 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 统计执行语句条数 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 (

13、int i = 0; i n; i+ ) count += 2; count += 3; 程程 序序 语语 句句一一次次执执行行所所需需程程序序步步数数执执行行频频度度 程程序序 步步数数 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+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; /数据累加 for ( int j = 0; j n; j+ ) sumi += xij; for ( i = 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 ); i+; /一趟比较 template void dataList:BubbleExchange(int i, int & ex