《2010年自学考试《数据结构》各章复习要点总结课件》由会员分享，可在线阅读，更多相关《2010年自学考试《数据结构》各章复习要点总结课件（38页珍藏版）》请在金锄头文库上搜索。
1、课程背景,计算机硬件软件,软件=程序+文档（软件工程的观点）,程序=算法+数据结构（Niklaus Wirth，图灵奖获得者),“数据结构”=“计算机程序设计技巧”(Kunth，图灵奖获得者),熟悉c语言写出好的程序,学习数据结构=编写高水平的程序,数据结构：计算机类专业8大核心课程之一,教育部计算机教指委认定的8大核心课程：计算机语言、数据结构、离散数学、计算机网络、计算机组成原理、操作系统、数据库、软件工程,课程简介,她是计算机相关专业的一门重要的专业基础课,她主要研究计算机加工对象的逻辑结构、在计算机中的表示形式、实现各种基本操作的算法以及算法分析,她是学习操作系统、编译原理、数据库原理
2、等计算机专业课程的基础，学习计算机其他相关课程的必备条件,她的前序课程是离散数学、计算机基础、一门高级语言,熟练掌握C语言的基本语法是理解课程的重要基础,计算机类研究生招生考试的考核课程之一,课程组成 理论(56学时)+实验(24学时)+应用实践(1周课程设计),数据结构课程主要内容,理论： 数据结构的基本概念；线性表；栈和队列；数组与广义表；树形结构；图结构；查找；排序。,实验： 实验一：线性表及其应用 （4学时） 实验二：栈和队列的应用 （4学时） 实验三：矩阵的压缩存储与运算 （2学时） 实验四：树和二叉树的建立和应用 （4学时） 实验五：图的建立和应用 （4学时） 实验六：数据结构在排
3、序、查找中的应用（6学时）,学习方法,上课前了解预习课堂内容,上课时认真听讲，回答问题和提出不同的见解,课后仔细阅读教材例题，独立完成每章节后的所以习题,实验课前查阅资料，完成实验报告的前三部分（需求分析、概要设计和详细设计），并进行初步的调试,实验时，积极调试程序，不懂的地方力争自己解决，无法解决的主动询问老师,实验结束后，完成整个实验报告，提交学习委员,通过理论，切实提高分析问题，解决问题的能力；通过实验，在实验中提高对算法理论的理解以及编程能力的提高。,勤学勤练,要求与考核,上课不得迟到、早退和旷课，请假必须有正当理由,每旷课一次扣平时分5分，迟到、早退一次扣2分,按时独立完成作业，在规
4、定的时间交学习委员,作业缺交一次扣平时分3分,实验前必须完成实验报告的前三部分；实验后按时提交实验报告,进实验室前实验老师检查，没有完成的不予进入实验室，并作旷课处理；缺交一次实验报告扣平时分5分,注意：平时分扣到60分以下不得参加考试,考核平时分占30分，考试占70分,本章主要内容,数据结构研究的主要内容,基本概念和术语,算法,【教学目的】掌握数据结构的研究内容；数据结构的有关概念和名词术语；算法的效率 【教学重点】抽象数据类型和数据结构以及算法效率的度量 【教学难点】数据类型的表示及实现,数据结构研究的主要内容,计算机应用的特点： 所处理的数据量大且具有一定的关系 对其操作不再是单纯的数值
5、计算，而更多地是需要对其进行组织、管理和检索,特点： 1.每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；2.表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；3.通常的操作：插入、删除、更新、检索。,数据结构研究的主要内容,应用举例1学籍档案管理 假设一个学籍档案管理系统应包含如下表所示的学生信息：,特点： 1.所处理的数据之间具有层次关系，这是我们所说的树形结构；2.对它的操作有：建立树形结构，输出最低层结点内容等等,数据结构研究的主要内容,应用举例1输出n个对象的全排列 输出3个对象的全排列可以使用下图所示的形式描述：,全排列的结果,特点
6、： 1.课程顶点之间的先后关系用图表示比较清晰明了；2.一个顶点与多个顶点有关系；3.通常的操作：排序，遍历等操作。,数据结构研究的主要内容,应用举例1制订教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业部分课程的开设情况如表所示：,课程的先后关系用图表示,数据结构研究的主要内容,操作对象的关系复杂,操作形式不再是单纯的数值计算，更多的是对数据进行组织，管理称为非数值性处理,有效的表示方式以及各个操作的具体实现,基本概念和术语,数据：信息的载体，它能够被计算机识别、存储和加工处理的符号。,数据元素
7、：数据的基本单位，又可称为元素、结点、顶点、记录等。一个数据元素可由若干个数据项组成。 由一个数据项组成为简单型元素；（数据项就是数据中不可再分割的最小单位）复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。,数据对象：或数据元素类，是具有相同性质的数据元素的集合。,基本概念和术语,数据结构：就是相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构有：线性结构（元素之间是一对一的关系）、树形结构（元素之间是一对多的关系）和图形结构（元素之间是多对多的关系）。,数据类型：是相互之间存在关系的元素集合和定义在这个集合上的一组操作的总称。,数据类型的三要素： 数据对象（集合
8、） 元素之间的关系 对数据的操作运算,基本概念和术语,逻辑结构：数据结构定义中所说的“元素之间关系”即是指数据元素之间的逻辑关系。,物理结构：或存储结构，数据结构在计算机中存储器中的具体实现（又称映像）。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要体现数据元素之间的逻辑结构（关系）。 有两大类：顺序存储结构和链式存储结构。,对数据的操作运算：是对数据结构中数据施加的操作。操作的定义直接依赖于逻辑结构，但运算的实现必依赖于具体的存储结构 。,基本概念和术语,顺序存储结构：顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺
9、序存储结构。,链式结构：链式存储方法对逻辑上相邻的元素不要求其物理位置相邻（离散地分布在内存中），元素间的逻辑关系通过附设的指示元素地址的指针字段来表示。,除了通常采用的顺序存储方法和链式存储方法外，有时为了查找的方便还采用索引存储方法和散列存储方法。,算法,算法概念：算法是解决某个特定问题的一种方法或一个过程。,算法类型：计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。,算法,设计过程：,通过对问题进行详细地分析，抽象出相应的数学模型,确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作
10、的算法,用某种语言将算法转换成程序,调试并运行这些程序,算法,算法的特性：,有穷性：一个算法必须在执行有穷步之后结束,确定性：算法中的每一步，必须有确切的含义，在他人 理解时不会产生二义性,可行性：算法中描述的每一步操作都可以通过已有的基 本操作执行有限次实现,输入：一个算法应该有零个或多个输入,输出：一个算法应该有一个或多个输出,算法,算法的描述选择算法描述语言的准则,该语言应该具有描述数据结构和算法的基本功能,该语言应该尽可能地简捷，以便于掌握、理解,使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言,算法,举例 问题：按从小到大的顺序重新排列x，y，z三个数值的内容。,（1
11、）输入x，y，z三个数值,（2）从三个数值中挑选出最小者并换到x中,（3）从y，z中挑选出较小者并换到y中,（4）输出排序后的结果,算法：,算法,算法的描述可以使用各种不同的方法来描述算法,使用自然语言。用自然语言来描述算法的优点是简单且便于人们对算法的阅读,缺点是不够严谨，容易产生二义性。,可以使用程序流程图、N-S图等算法描述工具。其特点是描述过程简洁、明了。,这两种描述算法不能够直接在计算机上执行，需要将它转换成可执行的程序,算法,类C描述将三个数值排序的算法。,void Three_Sort( int *x,int *y,int *z) /将x,y,z三个指针所指内容按从小到大的顺序重
12、新排列 if (*y*x /在y和z所指单元中挑较小者换到y中 ,算法,算法评价,正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求,可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性,当输入数据非法运行环境改变时，算法能恰当地作出反应或进行处理，不会产生慕名其妙的输出结果,时间与空间效率：算法对应的程序在计算机上运行时所花费的时间及所占据空间的度量(一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量),算法,可读性要求的良好的程序设计风格,算法,算法,算法,影响算法的时间效率的因素:,书写程序的语言。实现语言的级别越高，其执行效率就越低。,编译程序所
13、生成目标代码的质量。对于代码优化较好的编译程序其所生成的程序质量较高。,问题的规模。例如，求100以内的素数与求1000以内的素数其执行的时间必然是不同的,算法设计的好坏,硬件的速度。,算法,例子：求两个N阶方阵的乘积C=A*B的算法如下,#define N 100 void MatrixMultiply (int A NN，int BNN，int CNN) ,for(i=0;iN; i+) / n+1 for(j=0; jN;j+) / n(n+1) ,Cij=0; / n2 for(k=0;kN;k+) / n2(n+1) Cij=Cij+Aik*Bkj; / n3,/ 时间复杂度T(n)
14、=2n3+3n2+2n+1 /显然，它是方阵阶数n立方的函数，一般简写为O(n3)。,算法,时间复杂度的表示：,算法的执行时间是求解问题的规模n（如矩阵的阶数，线性表的长度）的函数，我们考察它的数量级量度，即它与什么简单函数f(n)是同一数量级的，即T(n)=O(f(n)。对于前例，当n时 T(n)/n3 = (2n3+3n2+2n+1)/ n32 按“O”的定义我们可知T(n)=O(n3),常数阶O（1），对数阶O（log2n），线性阶O（n），平方阶O（n2），立方阶O（n3），指数阶O（2n）的数量级大小是怎样的？,递增,效率低,算法,例子：若矩阵Amxn中存在某个元素aij满足：aij
15、是第i行中最小值且是第j行列中的最大值，则称该元素为矩阵A的一个鞍点，试编写算法找出A中的所有鞍点。,算法一 ： 找出每行最小的后判断其在列中是否为最大的,1）i从第一行开始； 2) 在第i行中找出最小数Aij ； 3）判断Aij看它是否也是第j列的最大数，如果成立则是鞍点，输出； 4）判断是否到了最后一行，若是退出，否则转2) 继续。 算法描述如下：,算法,#define m 10 #define n 10 void saddle ( int Amn) /*求m行n列矩阵的鞍点*/ int i,j,k,min; ,是否有缺陷？,/O(m*(m+n),for (i=0；im；i+ ) ,min
16、= Ai0 ; j=0; for (k=1；kn；k+ ) if(Aik min) min= Aik; j = k ；,for (k=0; kmin) break; if(k=m) printf ( “nA%d%d是鞍点” , i, j) ;,算法,例子：若矩阵Amxn中存在某个元素aij满足：aij是第i行中最小值且是第j行列中的最大值，则称该元素为矩阵A的一个鞍点，试编写算法找出A中的所有鞍点。,算法二 用穷举法 ：对每一个元素aij进行判别,1）i，j从第一行第一列开始； 2) 判断Aij是否是第i行中最小的, 若是转3）, 否则转4）; 3）判断Aij是否也是第j列最大的，若是则为鞍点，输出; 4）判断是否到了最后一个元素，若是
