北京师范大学数据结构教学资料 第1章——绪论ppt课件

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 1524361524361413121123456789103158710119987456623131bindevetclibuser112354871110291641012115123698712564312543611331814665161921n数据的存储结构是逻辑结构用计算数据的存储结构是逻辑结构用计算机语言的实现；机语言的实现；n数据的存储结构依赖于计算机语言。数据的存储结构依赖于计算机语言。n 顺序存储表示顺序存储表示n 链接存储表示链接存储表示n 索引存储表示索引存储表示n 散列存储表示散

4、列存储表示主要用于内存的主要用于内存的存储表示存储表示主要用于外存主要用于外存 (文文件件) 的存储表示的存储表示抽抽象象数数据据类类型型查找查找 登录登录 删除删除 修正修正 符符 号号 表表属性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

5、)Draw( )move(x, y)contains(aPoint)效力效力效力效力四边形类及其对象四边形类及其对象quadrilateralDraw( )move(x, y)contains(aPoint)PolygonreferencePointVerticesPolygon 类类referencePointVerticesDraw( )move(x, y)contains(aPoint)Polygon的子类的子类Quadrilateral类类Quadrilateral选择题选择题1、组成数据的基本单位是（、组成数据的基本单位是（ ）（A数据项数据项B数据类型数据类型C数据元素数据元素D数

6、据变量数据变量2、数据结构是研究数据的（、数据结构是研究数据的（ ）以及它们之间的相互关系。）以及它们之间的相互关系。（A理想结构，物理结构理想结构，物理结构 （B理想结构，抽象结构理想结构，抽象结构（C物理结构，逻辑结构物理结构，逻辑结构 （D抽象结构，逻辑结构抽象结构，逻辑结构3、在数据结构中，从逻辑上可以把数据结构分成（、在数据结构中，从逻辑上可以把数据结构分成（ ）（A动态结构和静态结构动态结构和静态结构 （B紧凑结构和非紧凑结构紧凑结构和非紧凑结构（C线性结构和非线性结构线性结构和非线性结构D内部结构和外部结构内部结构和外部结构4、数据结构是一门研究非数值计算的程序设计问题中计算机的

7、、数据结构是一门研究非数值计算的程序设计问题中计算机的 （）以及（）以及它们之间的（）和运算等的学科。它们之间的（）和运算等的学科。 （A数据元素数据元素B计算方法计算方法C逻辑存储逻辑存储D数据映像数据映像 （A构造构造 （B关系关系 （C运算运算 （D算法算法 练习 CCCAB 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

8、 j = i+1; j n; j+ ) if ( aj ak ) k = j; if ( i != k ) int temp = ai; ai = ak; ak = temp; 插装 time( ) 的计时程序 double start, stop; time (&start); int k = seqsearch (a, n, x); time (&stop); double runTime = stop - start; cout n runTime endl;缺陷：缺陷：1.必须执行程序必须执行程序 2.其它因素掩盖算法本质其它因素掩盖算法本质float sum ( float a ,

9、int float sum ( float a , int n ) n ) float s = 0.0; count+; /count 统计执行语句条数 for ( int i = 0; i n; i+ ) count+=2;/针对 for 语句 s += ai; count+; /针对赋值语句 count+=2;/针对 for 的最后一次 count+; /针对 return 语句 return s; 执行结束得 程序步数 count = 3*n+4void MatrixMultiply ( int Ann, int Bnn, int Cnn ) for ( int i = 0; i n;

10、i+ ) 2(n+1) for ( int j = 0; j n; j+ ) 2n(n+1) Cij = 0; n2 for ( int k = 0; k n; k+ ) 2n2(n+1) Cij = Cij + Aik * Bkj; n3 3n3 + 5n2 + 4n +2n算法中所有语句的频度之和是矩阵阶数算法中所有语句的频度之和是矩阵阶数n的函数的函数n T(n) = 3n3 + 5n2 + 4n +2n一般地，称一般地，称 n 是问题的规模。则时间复是问题的规模。则时间复杂度杂度 T(n) 是问题规模是问题规模 n 的函数。的函数。n当当n趋于无穷大时，把时间复杂度的数量趋于无穷大时，

11、把时间复杂度的数量级阶称为算法的渐进时间复杂度级阶称为算法的渐进时间复杂度n T(n) = O(n3) -大大O表示法表示法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) void exam ( float x , int m, int n ) float

12、 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;

13、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 );

14、 /发生逆序发生逆序, 交换交换 exchange = 1; /做做“发生交换标发生交换标志志 1121ni)n(ni)(nBubblrSort n-1趟趟BubbleExchange ( ) n-i次比较次比较n例：设有两个算法在同一机器上运行，例：设有两个算法在同一机器上运行，其执行时间分别为其执行时间分别为 100n2 和和 2n，问：要，问：要使前者快于后者，使前者快于后者，n 至少要取多大？至少要取多大？n 解答：解答： 问题是找出满足问题是找出满足 100n2 2n = 8192 n = 14时，时，100n2 = 19600 2n = 16384 n = 15时，时，100n2 = 22500 2n = 32764 取取 n = 15 满足要求。满足要求。1、算法分析的两个主要方面是（ ）答案（A正确性和简单性 （B可读性和文档性（C数据复杂性和程序复杂性 （D时间复杂度和空间复杂度2、算法分析的目的是（）。答案（A） 找出数据结构的合理性 （B研究算法中的输入和输出的关系（C分析算法的效率以求改进D分析算法的易懂性和文档性3、计算机算法指的