理工大学指挥自动化学院

编写陈卫卫（2008.2）审批理工大学指挥自动化学院课程教案教员姓名：陈卫卫单位：软件技术教研室课程名称：算法与数据结构总学时：60+20适用对象：生长干部非合训本科学员授课学期：2008年春季学期理工大学训练部制表第2页共246页课程简介一、课程定位《算法与数据结构》是仿真工程（非合训）、网络工程（合训）、作战信息管理（非合训）专业的本科生学科专业基础课程中的一门重要的核心课程。通过本课程的教学，使学员知道数据结构的一般原理，掌握表、树、图等基本数据结构的特点、存储表示、具有的运算、实现运算的算法设计方法，以及对算法效率的评估方法，知道什么是好的算法，如何设计和选择好的算法，为学习后续的《操作系统》、《编译原理》、《软件工程》等专业课程，设计系统程序打下基础。本课程的先修课程为：《计算机程序设计导论》（C语言）、《离散数学》。二、课程内涵（一）总体目标通过本课程的教学，使学员懂得数据结构的一般原理，掌握表、树、图等基本结构的特点，各结构的存储表示和所具有的运算，实现各运算的算法，学会对算法的评估方法。培养学员的算法设计能力、程序设计能力以及用软件方法处理问题的能力，培养学员的分析、对比、归纳、综合和创新能力，为学习后续专业课程，设计系统程序打下坚实的理论基础。（二）主要内容本课程主要内容包括两大部分。一是基本概念，主要介绍算法第3页共246页和数据结构的概念，算法的描述方法和评价标准、评价方法；算法设计的一般方法。这部分教学的主要目的是使学员了解算法和数据结构的一般原理，了解对算法的评估方法。二是最基本的数据结构——表结构、树结构和图结构，通过对表、树、图等基本结构的特点、存储方法，查找、插入、删除、排序、图的最优化等算法，以及实现运算的算法设计方法的学习，培养学员的算法设计能力、程序设计能力以及用软件方法处理问题的能力。（三）对学员的要求能够熟练地使用C语言。三、教学设计《算法和数据结构》是一门理论性与实践性都很强的重要核心课程。课程实施的总体方案是以提高学员的应用能力、创新能力和综合素质为目标，总体上，按照先易后难，先简单后复杂的思路进行讲解。在每一堂课上，大体的讲课思路是：先分析问题的特点，抽象出数据以及数据之间的关系，然后，引导学员寻找解决问题的思路和方法，最后考虑如何编程实现，让学生体验解决问题的一般过程。对于基本概念，多举例阐述概念的内涵，强调术语的作用，规范用词，培养严谨的科学作风。对于算法设计，突出重点，以点带面，通过对比，使学员逐步建立设计“好”算法的意识。具体内容如下：第4页共246页1．围绕表、树、图三大基本结构选择授课内容，依照“逻辑结构→物理结构→基本运算→基本算法→算法评价”这个脉络，研究每种结构的特点，给学生一个清晰的研究过程，使学员能够根据问题的特点选择合适的数据结构，进一步理解研究数据结构的意义。2．教学方法采用引导、启发、研究、讨论、问题驱动等多种形式，充分发挥学员的主体作用，激发每个学员的特长和潜能，培养学员的想象力和创新能力。3．教学手段采用多媒体和板书相结合的形式，全方位、多角度地阐述教学内容。利用多媒体动画，揭示算法思想的内涵，使算法思想更为形象、直观，提高学生的学习兴趣和求知欲。4．以知识验证、知识综合、创新设计为原则，设计上机实验内容。实验分为两类，一类为理解知识点的基本实验，另一类为综合应用的实验。通过上机编程强化学生的程序设计能力，进一步消化理解理论授课内容，贯彻“学以致用”的思想。第5页共246页教学进度总体安排序号教学内容课堂教学学时实践教学学时网络教学学时1概述2学员自主学习2表结构1863树结构1864图结构1045排序826集合运算227算法设计的一般方法2总计6020第6页共246页教学进度具体安排第一章概述………………………………………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学时第7页共246页第四章图结构……………………………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讲压缩为了一次课。第8页共246页内容备注第一章概述第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：[e-mail]办公室：教学楼809第9页共246页内容备注（二）课程的主要任务使学员获得算法和数据结构方面的基本知识，培养学员的程序设计能力和初级算法设计能力，掌握运用计算机解决本专业实际问题的基本方法，为今后的工作和学习奠定坚实的基础。（三）教学重点和基本条件1．教学重点在于围绕算法指导学生编程，使学生知道什么是“好”的算法，如何才能学会编写高质量的程序。2．基本条件：熟练使用C语言（C++中的传引用功能）、有一定的离散数学知识掌握VC++6.0集成开发环境（四）教材及参考书目1．教材(TextBook)《数据结构教程》王庆瑞编著北京希望电子出版社2．参考书一般的《DataStructuresandAlgorithmAnalysisinC》（SecondEdition），MarkAllenWeiss著，陈越改编，北京：人民邮电出版社，2005数据结构（C语言版）严蔚敏、吴伟民编著清华大学出版社C算法（第一卷，基础、数据结构、排序和搜索）（第三版）AlgorithmsINC(THIRDEDITION)C算法（第二卷图算法）RobertSedgewick著周良忠译，人民邮电出版社POSTS&TELECOMPRESS经典的计算机程序设计艺术（第3版）TheArtofComputerProgramming第1卷基本算法第2卷半数值算法第3卷排序与查找DonaldE.Knuth著苏运霖译，国防工业出版社AddisonWesley，2003（五）学习方法认真听讲读书、思考独立完成作业上机练习（六）评价方式介绍课程整体情况，帮助学生明确学习目标，知道相关的学习要素。结合课程特点，强调好的学习方法。学会搜集资料，知道参考书的作用和价值，以及如何使用参考书。充实、深化相关学习内容。第10页共246页内容备注平时作业（含上机）上课表现笔试试卷板书二、数据结构的概念20分钟板书（一）问题的求解过程1．解题的一般过程接受任务（设计程序、软件）针对问题进行分析设计出求解策略，即算法（algorithm），程序的雏形“问题级的算法”（或初级算法）算法的需要，抽象出所要处理的数据建立数据结构将算法分解成对数据结构的运算设计出对数据结构进行处理的算法（数据结构级算法）对算法的性能（可行性和运行效率：时间和空间）进行评估着手程序设计对程序进行调试交付使用2．程序与算法的关系程序是按算法思想进行设计的，程序中含有算法。算法就是程序（但算法不等于程序）。程序也称算法。程序（或算法）就是问题的解（算法解，或程序解，软件解）。板书（二）数据和数据结构板书1．数据是对客观事物的名称、数量、特征、性质的描述形式（编码），是计算机所能处理的一切符号的总称，是程序加工的对象和产品。板书2．数据的种类数值型数据（整数、实数等）：例，四则运算文字型数据（字符、字符串）：例，文本文件，程序代码（编译软件）声音、图像形式的数据：例，mp3、avi。数据总是以某种编码形式出现的。板书3．《数据结构》研究的对象数据元素的集合，元素之间的关系，对数据和数据集合进行哪些运算，如何提高运算效率。板书4．数据元素（dataelement）总结归纳问题求解的一般过程，从中把握数据结构课程的地位和作用。说明：算法和程序概念的差异，在没有歧义的情况下，可以不区别。从狭义和广义两个角度阐述数据。举例说明这些术语的内涵，进一步理解计算机的工作方式。第11页共246页内容备注数据结点，简称结点（node）。描述一个独立事物的名称、数量、特征、性质的一组相关信息组成一个数据结点。通常，一个结点含有多个数据项（记录型结点，或结构型结点）每个数据项是结点的一个域（field），能够唯一标识结点的域叫关键字域（key）。若结点只含一个数据项（单值结点），可把结点看成整数（编码）。例如：（1）学生结点：学生的姓名、学号、各科考试成绩等等，学号可以作为结点的关键字域。（2）商品结点：商品编号和名称、规格、数量、生产厂家、单价、入库日期。板书5．数据结构（datastructure）《数据结构》是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和处理算法的学科。（1）定义：数据结构B=(D，R)——逻辑结构D：有穷的结点集合；R：D中结点间的有穷关系集合注意：不研究一个结点内部各域之间的关系（由编码，存储方式决定）。板书（2）研究内容数据及数据之间的关系、存储方式、基本运算、实现运算的算法、算法评价方法。“好”数据结构＋“好”算法＝“好”程序良好、合理的数据结构清晰、实用的算法简洁、高效的程序板书（3）数据结构的两个方面1）数据的逻辑结构：指各数据元素之间的逻辑关系，是用户按使用需要建立起来的，呈现在用户面前的结构形式。2）数据的物理结构：亦称数据的物理结构、存储结构，是指数据在计算机内的