OA自动化理工大学指挥自动化学院

OA自动化理工大学指挥自动化学院编写陈卫卫（2008.2）审批理工大学指挥自动化学院课程教案教员姓名：陈卫卫单位：软件技术教研室课程名称：算法与数据结构总学时：60+20适用对象：生长干部非合训本科学员授课学期：2008年春季学期理工大学训练部制表课程简介一、课程定位《算法与数据结构》是仿真工程（非合训）、网络工程（合一门重要的核心课程。通过本课程的教学，使学员知道数据结构的一般原理，掌握表、算法设计方法，以及对算法效率的评估方法，知道什么是好的算法，如何设计和选择好的算法，为学习后续的《操作系统》、《编译原理》、《软件工程》等专业课程，设计系统程序打下基础。本课程的先修课程为：《计算机程序设计导论》（C语言）、《离散数学》。二、课程内涵（一）总体目标通过本课程的教学，使学员懂得数据结构的一般原理，掌握表、各运算的算法，学会对算法的评估方法。培养学员的算法设计能力、下坚实的理论基础。（二）主要内容——表结用软件方法处理问题的能力。（三）对学员的要求能够熟练地使用C语言。三、教学设计《算法和数据结构》是一门理论性与实践性都很强的重要核心解。法，最后考虑如何编程实现，让学生体验解决问题的一般过程。用词，培养严谨的科学作风。立设计“好”算法的意识。具体内容如下：1．围绕表、树、图三大基本结构选择授课内容，依照“逻辑结构→物理结构→基本运算→基本算法→算法评价这个脉络，研究每特点选择合适的数据结构，进一步理解研究数据结构的意义。2．教学方法采用引导、启发、研究、讨论、问题驱动等多种形员的想象力和创新能力。3．教学手段采用多媒体和板书相结合的形式，全方位、多角度想更为形象、直观，提高学生的学习兴趣和求知欲。4．以知识验证、知识综合、创新设计为原则，设计上机实验内理论授课内容，贯彻“学以致用”的思想。教学进度总体安排课堂教学实践教学网络教序号教学内容学时学时学学时1概述22表结构1863树结构1864图结构104学员自5排序82主学习6集合运算227算法设计的一般方法2总计6020教学进度具体安排第一章概述………4学时第1讲《算法和数据结构》概述……………2学时第30讲算法设计的一般方法………………2学时第二章表结构……………18学时第2讲表结构的概念…………………2学时第3讲顺序表的运算…………………2学时第4讲链表的基本概念…………………2学时第5讲简单链表的运算………………2学时第6讲复杂链表及链表的应用…………2学时第7讲栈和队…………2学时第8讲静态链表………2学时第9讲矩阵运算………2学时第10讲字符串………2学时第三章树结构……………18学时第11讲树结构的概念…………………2学时第12讲二叉树……………2学时第13讲二叉树的遍历……2学时第14讲遍历算法的应用…………………2学时第15讲遍历序列的性质…………………2学时第16讲二叉树的构造……2学时第17讲检索树……………2学时第18讲平衡树……………2学时第19讲哈夫曼树、判定树………………2学时第四章图结构……………10学时第20讲图的概念和存储结构………………2学时第21讲先深搜索和先广搜索………………2学时第22讲最小生成树…………2学时第23讲最短路径……………2学时第24讲有向无回路图、双连通分量………2学时第五章排序……………8学时第25讲基本概念、插入排序…………2学时第26讲交换排序………2学时第27讲选择排序…………2学时第28讲合并排序、基数排序……………2学时第六章集合运算……………2学时第29讲散列表……………2学时说明：为了空出一次复习课的时间，在实施计划中将第11讲和第12讲压缩为了一次课。内容备注第一章概述第1讲《算法和数据结构》概述讲课题目：《算法和数据结构》概述（1.1、1.2、1.3）目的要求：1．了解课程基本信息，建立基本要求2．掌握基本数据结的构特征及其意义3．掌握算法的定义和三种描述方式4．了解算法的评价方法知识点：1．数据结构的基本概念2．算法的描述和实现3．算法的评价方法重点难点：1．表、树、图结构的特征及其意义2．算法的定义，算法的描述方式3．算法的时间复杂性方法步骤：1．介绍与课程有关的相关知识2．从求解问题的一般步骤入手，建立抽象的数据模型（数值、非数值）3征4．用示例介绍算法的描述形式和适用场合，研究算法“好问题的意义和价值，站在使用效果、满足需要等角度，讨论研究评价算法的标准。器材保障：电脑、投影仪、教鞭教学内容与时间安排:一、课程基本信息10分钟内容备注（一）教员信息主讲教员：陈卫卫联系方式：824546(O)，828596(H)E_mail：hchcww@263.net办公室：教学楼809（二）课程的主要任务使学员获得算法和数据结构方面的基本知识，培养学员的程序设计能力和初级算法设计能力，掌握运用计算机解决本专业实际问题的基本方法，为今后的工作和学习奠定坚实的基础。（三）教学重点和基本条件1．教学重点在于围绕算法指导学生编程，使学生知道什么是“好”的算法，如何才能学会编写高质量的程序。2．基本条件：熟练使用C语言（C++掌握VC++6.0集成开发环境（四）教材及参考书目1．教材(TextBook)《数据结构教程》王庆瑞编著北京希望电子出版社2．参考书一般的《DataStructuresandAlgorithmAnalysisinCSecondEditionMarkAllenWeiss著，陈越改编，北京：人民邮电出版社，2005数据结构（C语言版）严蔚敏、吴伟民编著清华大学出版社C算法（第一卷，基础、数据结构、排序和搜索第三版）AlgorithmsINC(THIRDEDITION)C算法（第二卷图算法）RobertSedgewick著周良忠译，人民邮电出版社POSTS&TELECOMPRESS经典的计算机程序设计艺术（第3版）TheArtofComputerProgramming第1卷基本算法内容备注第2卷半数值算法第3卷排序与查找DonaldE.Knuth著苏运霖译，国防工业出版社AddisonWesley，2003结合课程（五）学习方法特点，强调认真听讲读书、思考好的学习独立完成作业方法。上机练习（六）评价方式平时作业（含上机）上课表现笔试试卷二、数据结构的概念20分钟（一）问题的求解过程1．解题的一般过程接受任务（设计程序、软件）针对问题进行分析设计出求解策略，即算法（algorithm“问题级的算法（或初级算法）算法的需要，抽象出所要处理的数据建立数据结构将算法分解成对数据结构的运算设计出对数据结构进行处理的算法（数据结构级算法）对算法的性能（可行性和运行效率：时间和空间）进行评估着手程序设计对程序进行调试交付使用2．程序与算法的关系程序是按算法思想进行设计的，程序中含有算法。内容备注（二）数据和数据结构1．数据从狭义和能处理的一切符号的总称，是程序加工的对象和产品。广义两个2．数据的种类角度阐述数值型数据（整数、实数等）：例，四则运算文字型数据（字符、字符串）：例，文本文件，程序代码（编译软件）数据。声音、图像形式的数据：例，mp3、avi。数据总是以某种编码形式出现的。3举例说明数据元素的集合，元素之间的关系，对数据和数据集合进行哪些运算，如何提高运算效率。4．数据元素（dataelement）node质的一组相关信息组成一个数据结点。通常，一个结点含有多个数据项（记录型结点，或结构型结点）每个数据项是结点的一个域（field（key例如：（1点的关键字域。（2期。5．数据结构（datastructure）《数据结构》是一门研究非数值计算的程序设计问题中计算机的操作对象

以及它们之间的关系和处理算法的学科。（1）定义：数据结构B=(D，R)——逻辑结构

D：有穷的结点集合；R：D中结点间的有穷关系集合注意内容备注（2）研究内容数据及数据之间的关系、存储方式、基本运算、实现运算的算法、算法评价方法。“好”数据结构＋“好”算法＝“好”程序良好、合理的数据结构清晰、实用的算法简洁、高效的程序（3）数据结构的两个方面1立起来的，呈现在用户面前的结构形式。2内的表示方法，即存储形式。既要存储数据，又要（存储）体现出逻辑结构。主要概念有：存储结点：用于存储一个数据结点的存储单元。一个数据结点对结点、自由结点。6．常见的逻辑数据结构表、树、图、集合（1）表：描述结点之间简单的先后次序关系。一对一关系（2）树：描述结点之间的层次关系，或嵌套关系。一对多关系（3）图：描述结点之间的“多对多”关系。（4）集合：结点之间的“无关关系。结构中的数据元素之间除“同属于一个集合”的关系，无其他关系。7．基本存储结构从存储角度看，数据结构可以归结为两种基本结构：（1）顺序存储结构把逻辑上相邻的结点存储在物理位置上相邻存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。（2）链接存储结构不要求逻辑上相邻的结点其物理位置上亦相邻，结点间的逻辑关系是由附加的指针域表示的。内容备注8．运算（operation）：对数据和数据结构的处理操作。不同的数据结构有不同的运算。如表结构的常见运算：查找、插入、删除、排序等。（1）插入(Insert)在数据结构的指定位置上增添新的数据元素。阐述运算（2）删除(Delete)删去数据结构中某个指定的数据元素。（3）更新(Update)及关联关改变数据结构中某个数据元素的值，在概念上等价于删除和插入操作的组合。的运算一（4）查找(Search)在数据结构中寻找满足某个特定要求的数据元素(位置或值)。三、算法的描述和实现30分钟（一）算法(Algorithm)的定义1．简单定义：算法记载了求解问题的方法和步骤。算法(Algorithm)有限时间完成的、毫不含糊的指令的有限序列。其中每一条指令表示一个或多个操作。2．克努特（D.E.Knuth）的定义：算法就是一个有穷规则的集合。规则规定解决某一特定问题的运算序列。算法的5个重要特性。有穷性、确定性、输入、输出、可行性（算法中所（1）有穷性：执行有限步，每步均在有穷时间内完成。（2）确定性：对相同的输入，必产生相同的输出，即无二义性。（3）可行性：计算机可使用已实现的基本运算执行有限次来完成。（4）输入：零个或多个输入。（5）输出：一个或多个输出。（二）算法的存在形式1．程序形式程序形式——算法的实现——算法的最终形式。2．描述形式内容备注描述形式：便于理解、记忆和互相交流三种描述形式：形式化、半形式化、非形式化。3．形式化描述——用类语言描述的形式——“半程序形式。伪程序（伪类语言：以某种程序设计语言（C略加改造而形成的语言。/输出等细节，保留程序的基本框架。伪程序与“真程序”非常接近，略加改造就是真程序。4．半形式化5．非形式化——文字叙述形式，最原始形式。6．示例例1.1自然选择排序算法。把一组（共n个）杂乱数据排列成由小到大的递增序列。

simpleselectionsort（1）文字叙述形式：先从n个数据中选出一个最小元素，使它作为序列的第一项；再从剩下的

n-1个数据中选出一个最小元素作为第二项……，重复地作上述选择工作，

直至选择最后一项。最终将得到有序序列。算法不依赖数据结构，不考虑数据是如何存储的。（2）进一步叙述：假定数据存储在数组a[n]中：先从a的n个元素中选择一个最小元素（比如某个a[j]a[0]交换位置；再从剩下的n-1个元素中选择一个最小元素，将它与a[1]交换位置；再从剩下的n-2个元素中选择一个最小元素，将它与a[2]交换位置；……反复进行上述选择和交换，直到选择出最后一个元素，从而完成排序工作。（3）用类C程序（形式化）：for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(a[j]<a[k])k=j;内容备注w=a[i];a[i]=a[k];a[k]=w;}例1.2二分查找（binarysearch）算法。在元素从小到大排列的有序数组a[n]xx在数组a中出现，就用变量i记住它所在的数组下标，若x不出现，则i=-1。二分查找算法：（1）文字叙述步骤1置left和right的初值，即left=0，right=n-1；步骤2如果left>righta中没有x使i=-1法终止；否则：步骤3计算中值地址，即下标mid=(left+right)/2；步骤4比较x与a[mid]的值：（4.1）如果x=a[mid]，则找到x，i=mid，算法终止；否则，（4.2x<a[mid]rightright=mid-12继续查找；（4.3）如果x>a[mid]，则调整左指针left，使left=mid+1，转到步骤2继续查找。这样，反复执行步骤（2）到（4（2）流程图：P5图1.3二分查找算法的流程图

7．三种算法描述形式小结（1义性。（2）流图：直观、结构更清晰，容易理解，接近程序形式；也有二义性，比较麻烦，不容易修改。常用于对大型软件的结构分析和说明。（3）伪代码形式：克服二义性，突出算法的主体，保持算法的良好结构，可采用逐步求精的程序设计方法。便于对算法时间、空间作定量的分析。8．算法和程序的关系程序（Program）是用计算机程序设计语言实现的完成一定功能的代码。算法的程序形式称为算法的实现（例如，C式。程序中体现了算法的思想。算法不依赖于具体的实现语言。内容备注程序中有算法，算法不一定是程序。四、算法的评价标准5分钟（一）算法分析对算法的综合性能进行较为客观的分析评价评估，评测（二）评价角度（标准）1．算法的正确性(Correctness)能满足具体问题的需求，且所有合法的输入数据都正确才算正确。评价方法：调试只能证明算法有错，不能证明算法无错。人工证明（归纳法）2．算法的有效性（算法的运行效率）算法的运行效率(Efficiency)——耗用时间，占用空间。（1timecomplexity）：对时间的客观要求。同一问题，算法执行时间越短，效率越高。（2）算法的空间复杂性（spacecomplexity）：对空间的客观要求。指算法执行过程中所需的最大存储空间。3．对程序（软件）评价的附加标准（1）操作界面（2）健壮性(Robustness)对于异常的处理能力。能作出判断，并给出适当的提示或警告信息，以等

待操作员的干预或能自动进行适当处理。（3）可读性(Readability)希望一个算法易于理解、易于编码，也易于调试。（4）可维护性等等。五、算法的时间复杂性20分钟（一）算法的时间复杂性函数分析计算法时间复杂性的困难之处，剖内容备注1．T(n)n描述算法执行过程中所需的时间用量与问题规模n之间的函数关系T(n)。T(n)要计算得“精确（客观）很因难。2．计算的困难性执行时间取决于下列因素：问题的规模（输入的大小/复杂程度）所选用的语言编译程序所产生可执行代码的质量机器执行指令的速度（二）可能的方法1．事后统计思考：用具体的时分秒度量可以吗？2．事前估计事先估算的主要因素——问题的规模。例6：两个n×n矩阵相乘，令数乘作为基本运算for(i=1;i<=n;i++)for(j=1;j<=n;j++){C[i][j]=0;for(k=1;k<=n;k++)C[i][j]+=A[i][k]*B[k][j];};整个算法执行时间与数乘次数n3成正比，记作T(n)=O(n3)两个n×n矩阵相乘的时间复杂度为O(n3)。（三）时间度量单位明确度量单位的意T(n)等于执行基本语句的总条（次）数。大体上能够说明算法的时间性能。义，学会把（四）大“O”记号内容备注1．T(n)的上界（1）定义对某算法执行时间T(n)c和n0n>n0T(n)≤cf(n)都成立。即T(n)≤cf(n)（c是任意正的常数——常系数，f(n)那么，就记作T(n)=O(f(n))O(f(n))率的一个上界为f(n)，或说T(n)是f(n)的大O函数。（2）内涵只求出T(n)随输入数据量n而增长的趋势（极限情况）——算法的渐近时间复杂性（asymptotictimecomplexity形式，只求出T(n)的“阶。只求出T(n)的最高阶，忽略其低阶项和常系数。（3）示例设T(n)=n2+4n，则有f(n)=n2，即有：n2+4n=O(n2)因为存在c=2，n0=4，使对于一切n>n0，恒有n2+4n≤2n22．优点（1）简化T(n)的计算（2）比较客观地反映出当n很大时，算法的时间性能。3．示例对某问题，设计了两个算法，经过计算得出：算法A的时间耗费函数为T1(n)=20n2+100n算法B的时间耗费函数为T2(n)=0.5n2－3n+18这两个算法的时间耗费函数的阶是一样的，都是n的平方阶的，于是可以写成T1(n)=O(n2)T2(n)=O(n2)当n很大时，低阶算法比高阶算法好。内容备注4．常用阶O(1)常数时间，即算法时间用量与输入数据量n的大小无关O(logn)对数时间，对数阶通常不写底数（底数无关）因为任何常数C1，C2>0，有O(logc2n)=O(logc1c2logc1n)=O(logc1n)因为logc1c2是常数O(n)线性时间，即算法时间用量与n成正比O(nlogn)非常理想的阶O(n2)平方阶O(n3)立方阶……T(n)=O(nd)d“有效算法。O(2n)指数阶O(n!)阶乘阶则是无效算法，当n稍大一点，就不能在“有限的”时间内完成。示例：某算法的时间复杂性T(n)=2n，当n=1000时，其工作量（执行基本21000110-9秒）时间，那么解此问题共需要：（五）最坏情况和平均情况1．为什么要区分两种情况若某算法，对不同的输入数据（输入数据量都是n）耗用时间的差别很大，为使评价更客观，更有说服力，所以需要分几种情况讨论算法的时间性能。最坏情况（worst-case）和平均情况（expected-case态和平均性态。从这两个角度分析算法的时间性能，可以给算法作出更为客观的评价。举例说明2．最坏情况区分最坏对于具有相同输入数据量的不同输入数据，算法时间用量的最大值。用TW(n)表示最坏情况。3．平均情况情况和平均情况的对于所有相同输入数据量的各种不同数据，算法耗用时间的平均值。重要意义。内容备注用TE(n)表示平均情况下算法时间复杂性。4．注意（1）一般不讨论“最好”情况下算法的时间复杂性。（2两种不同情况了。笼统地用T(n)表示算法时间。三、算法的空间复杂性5分钟1．算法空间用量函数S(n)通常只计算辅助空间用量，而不计原始数据所占的空间。2．示例自然选择排序算法。for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(a[j]<a[k])k=j;w=a[i];a[i]=a[k];a[k]=w;}原始数据占用空间：n辅助空间（“纯”空间）：4（i，j，w，k）S(n)=O(1)3．时空转换四、计算时间复杂性的一般方法10分钟（一）典型语句度量法1“最多”是指：其他语句花费时间的总和将不超过这个语句花费时间的常数倍。用典型语句的执行次数度量这段程序花费时间的阶。若这段程序形如，语句1；语句2；……内容备注语句s；……语句m;假定语句s共执行f(n)次，除语句s外，其他语句执行次数总和不超过cf(n)次（c是常数，即与nf(n)+cf(n)=(c+1)f(n)根据渐近复杂性的定义，这段程序的时间耗费是O(f(n))。注意：这样的语句可能不止一条。2．示例注意：示意性程序：for(i=1,c=0,s=a[0];i<n;i++)语句序号{（123）1.if(a[i]<a[0])//统计小于a[0]的元素个数2.c+=1;不是程序3.s+=a[i];//计算数组元素的总和的一部分，}可选句1n-1O(n)

O(n)。3．典型语句的选择方法（1）一般情况，可以任选。但是要符合“最多”要求。

（2（与多少个元素比

较过）度量时间用量。（3量算法的时间用量。在算法理论上，分为“算法类。（二）分段计算法若一段耗时为O(f(n))，另一段耗时为O(g(m))，那么两段共耗费O(f(n))+O(g(m))=O(f(n)+g(m))例如，O(n2)+O(n)=O(n2)内容备注O(n)+O(n)=O(n)（三）分层计算法分层相乘，再化简1．简单相乘若外层循环共执行O(f(n))O(g(m))次，那么两层共执行O(f(n))O(g(m))=O(f(n)g(m))次。示例：示意性程序：for(i=0;i<n;i++)1.{x=y=0;for(j=0;j<n/2;j++)2.{if(a[j]>a[i])x+=1;3.if(a[j]<a[i])y+=1;priintf("%d,%d\n",x,y);}}外循环共执行n次，外循环每执行一次，内循环都执行n/2次，注意到O(n/2)=O(n)，所以本段程序时间复杂性为O(n)*O(n)=O(n2)注意：分层相乘有时不够精确，过于“粗糙。可能会算多了。2．直接计算内循环总的执行次数例如，for(i=1;i<=n;i++)for(j=1;j<=i;j++)printf("%d",i*j);显然，外循环第i次执行时，内循环执行i次，所以内循环总的执行次数等于（四）递推式方法过求解递归方程，计算出时间复杂性。示例：焚塔问题的时间耗费。用T(n)表示搬动高度为n的塔所需的移动总次数，那么可得出下列递归方程：内容备注（五）其他方法利用“便于”计算的数学模型，和复杂的数学演算（包括微分和积分运T(n)。（六）算法的选用原则需要考虑如下因素。算法实现的难易程度。算法运行环境（输入数据量的大小范围）当数据量不大时，低阶算法未必就快。例如，算法A1和A2的时间复杂性分别为T1(n)=1000n和T2(n)=n2虽然O(T1(n))<O(T2(n))，但是只有当n>1000时，A1才好于A2；而当n≤1000时，A2却好于A1，因为T2(n)≤T1(n)。小结：1．数据、数据结构、研究对象、逻辑结构、物理结构2．常见的4种基本数据结构及特点3．基本运算4．算法的描述方式5．算法的评价标准（正确性、有效性）6．时间复杂性（大O作业：P251.1、1.2（选）思考题：1．列举一些你知道的数值类问题的数学模型。参考资料：[1]MarkAllenWeiss著，陈越改编，《DataStructuresandAlgorithmAnalysisinCSecondEdition人民邮电出版社，2005内容备注[2]2003[3]王晓东编著，算法设计与分析，北京：清华大学出版社，2003本次课教学体会：第30讲算法设计的一般方法（简介）讲课题目：算法设计的一般方法目的要求：1．了解有效算法设计方法2．了解递归方法、分治方法、动态规划法、贪心法、搜索-回溯法、平衡原则。知识点：递归、分治法、贪心法、动态规划、平衡原则、回溯重点难点：各种算法设计方法的特点、可以解决的问题方法步骤：1．举例介绍问题，总结归纳方法器材保障：电脑、投影仪、教鞭教学内容与时间安排:一、算法设计的一般方法5分钟算法——“无法”靠人们的智慧和灵感，针对不同问题设计不同算法。-回溯法、平衡原则。二、递归（recursion）30分钟（一）好处结构简单清晰，易于阅读和理解。另外，便于写T(n)的递归推式，求出T(n)（使用组合论方法）（二）要求将问题写成递归定义形式内容备注（三）描述工具——（充分必要）递归函数。（四）种类有直接递归和间接递归两种递归方式1．直接递归函数p中含有调用自身的语句2．间接递归函数（联立递归）函数p调用函数q，而q又直接或间接地调用p。（五）终止条件（初始条件）（六）示例例1.3二分查找的递归算法。例1.4焚塔（Hanoitower）游戏。（七）单调递归和非单调递归1．每执行一次，至多产生一次递归。很容易改成非递归形式。2（八）递归与其他技术相结合，可以导出更有效的算法。三、分治和平衡20分钟（一）分治法（divide-and-conquertechnique）的基本原理在求解一个规模较大的问题时，可以把它分解成若干个规模较小的问题，并递归地把各子问题再次细分，直到问题“小到”容易求解为止，求出各子问题的解之后，再把这些解合成原问题的解。（二）示例例1.5求n个（n≥2）元素集合S的最大元素和最小元素问题。1．直观方法用2n-3次比较。2．分治法把SS1和S2S1和S2内容备注个最小元素选出一个较小的，它们分别是S的最大元素和最小元素。算法1.5（假设n=2kP16，半程序形式3．实现方法用数组a[n]存储集合。一对下标“限制”集合范围。4．时间复杂性列出比较次数的递推方程。很容易用迭代法求出式(1.2)的解是（三）采用分治法的条件和原则1．所求解的问题容易分解成子问题。2．容易把子问题的解合成原问题的解。3．划分工作量要少。4．要遵循平衡（balance）原则，也就是要尽量使分解出的子问题大小相等，并且子问题的个数和子