数据结构-用面向对象语言描述-殷人昆-导论

1、数据结构数据结构讲授： 杨* QQ *Email：*从从我们的孩子是否足够坚强我们的孩子是否足够坚强 -中式教育中式教育说说起起lBBC纪录片-中国教师进入英国学校进行对比教学l学生的课堂纪律差l学生的学习积极性差l水平远低于中国l为什么？l缺乏竞争我们为什么要学习？我们为什么要学习？l为了改变自己的命运l自己喜欢学习l获得更好的生存发展的机会l实现自我价值应当怎样学习？应当怎样学习？l认真的学习（预习、听课、复习、练习）l学明白l不明白怎么办？ 反复看书，问老师、问同学、网上搜一下、多多思考。l学以致用l做课后习题l使用学到的东西做一些应用l不喜欢学习怎么办？l挺过去、人总要做几件对自己有益

2、但自己不喜欢的事数据结构是怎样的课程数据结构是怎样的课程l一门必须努力才能学好的课程l介绍如何组织数据和处理数据的课程不同的结构带来不同的性能不同的结构带来不同的性能l了解数据结构中每种结构的特点和性能使用不同的操作来操作不同的结使用不同的操作来操作不同的结构构l最大堆数据有哪些操作数据有哪些操作l添加（基本操作，谁都要有）l删除（基本操作，谁都要有）l修改（基本操作，谁都要有）l查找（非常常用的，最体现性能的操作）l排序（非常常用的，最体现性能的操作）性能：程序跑的快慢和什么有关性能：程序跑的快慢和什么有关系？系？l数据的规模（要处理多少数据）l算法的性能（同一件事不同人干效率不同）数据（数

3、据（data）l数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。l简而言之： 用数字描述信息就是数据。l字符也是用数字表示的（对应表叫做编码表，如ASCII）另一些无关紧要的概念另一些无关紧要的概念l数据项-数据元素 数据l数据元素是数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。l有时一个数据元素可以由若干数据项(Data Item)组成。数据项是具有独立含义的最小标识单位。l数据元素又称为元素、结点、记录。l属性-对象-集合什么是数据结构什么是数据结构l定义: l 由某一数据对象及该对象中所有数据成员之间的关系组成。记为

4、：l Data_Structure = D, Rl 其中，D 是某一数据对象，R 是该对象中所有数据成员之间的关系的有限集合。N 个网点之间的连通关系个网点之间的连通关系数据结构是数据的组织形式数据结构是数据的组织形式l数据元素间的逻辑关系，即数据的逻辑结构；l数据元素及其关系在计算机存储内的表示，即数据的存储表示；l数据的运算，即对数据元素施加的操作。数据的逻辑结构分类数据的逻辑结构分类l线性结构l线性表l非线性结构l 树l 图（或网络）12354871110291641012115123698712564312543611331814665161921n数据的存储结构是逻辑结构用计算数据的

5、存储结构是逻辑结构用计算机语言的实现；机语言的实现；n数据的存储结构依赖于计算机语言。数据的存储结构依赖于计算机语言。u 顺序存储表示顺序存储表示u 链接存储表示链接存储表示u 索引存储表示索引存储表示u 散列存储表示散列存储表示 n数据类型就是数据结构，不过它是从编数据类型就是数据结构，不过它是从编程者的角度来使用的。程者的角度来使用的。n数据类型是模板，必须定义属于某种数数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。据类型的变量，才能参加运算。 属性aPoint1 aPoint2aPoint3 aPoint4服务服务Draw( )move(x, y)contains(aPo

6、int)属性值属性值quadrilateral1quadrilateral2(35, 10) (50, 10)(35, 25) (50, 25)(45, 65) (50, 45)(65, 66) (60, 70)Draw( )move(x, y)contains(aPoint)Draw( )move(x, y)contains(aPoint)服务服务服务服务四边形类及其对象四边形类及其对象quadrilateralDraw( )move(x, y)contains(aPoint)PolygonreferencePointVerticesPolygon 类类referencePointVerti

7、cesDraw( )move(x, y)contains(aPoint)Polygon的子类的子类Quadrilateral类类Quadrilateral。 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; #ifndef DA

8、TALIST_H#define DATALIST_H#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) dataList ( ) delete Element; void Sort ( ); friend ostream& o

9、perator (ostream& outStream, datalist& outList); friend istream& operator (istream& inStream, datalist& inList); ; #endif #ifndef SELECTTM_H#define SELECTTM_H #include “datalist.h”template void dataList : Swap (int m1, int m2) /交换由m1, m2为下标的数组元素的值 Type temp = Element m1; Element

10、m1 = Element m2; Element m2 = temp; 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)

11、OutStream “数组内容 : n”; for (int i = 0; i OutList.ArraySize; i+) OutStream OutList.Elementi ; OutStream endl; OuStream “数组当前大小 : ” OutList.ArraySize endl; return OutStream; template istream& operator (istream& InStream, dataList InList) cout InList.ArraySize; cout “录入数组元素值 : n”; for (int i = 0

12、; 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 #include “selecttm.h” const int SIZE = 10; int main ( ) dataList TestList (SIZE); cin TestList; cou

13、t 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 & ai != x ) i+; if ( i = n ) return -1; return i; double start, stop; time (&start); int k = seqsearch (a, n, x); time

14、(&stop); double 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 统计执行语句条数 for ( int i = 0; i n; i+ ) count+; /针对 for 语句 s += ai; count+; /针对赋值语句 count+;

15、/针对 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; 程程 序序 语语 句句一一次次执执行行所所需需程程序序步步数数执执行行频频度度 程程序序 步步数数 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

16、 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!x = 0; y = 0;for ( int k = 0; k n; k + ) x +;for ( 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) T

17、(n, m) = T1 (n) * T2 (m) = O(f (n)*g (m) 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 ( ) /对表逐趟

18、比较, ArraySize 是表当前长度 int i = 1; int exchange = 1; /当 exchange 为 0 则停止排序 while ( i ArraySize & exchange ) BubbleExchange ( i, exchange ); 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趟趟BubbleExchange ( ) n- -i次比较次比较 int i = n-1; while ( i = 0 & Ai != k ) i-; return i; i- n A 中各元素的取值中各元素的取值 k #include iostream.h #define arraySize 100#define MaxInt 0 x7ffff