《算法与数据结构》课程教学大纲

PAGE1PAGE1算法与数据结构课程教学大纲（AlgorithmandDataStructure）学时数：48其中：实验学时：12课外学时：0学分数：3适用专业：电子信息工程一、课程的性质、目的和任务本课程是电子信息工程专业的专业任选课程。本课程的目的在于分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。其任务主要是通过本课程的学习，使学生能深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。二、课程教学的基本要求本课程要求学生能较系统地学习数据结构的逻辑结构和物理结构的基本概念以及有关算法。并通过实践环节，使学生加深对算法与数据结构的理解，能运用数据结构知识建立数学模型，解决实际的应用问题。（一）了解数据结构及其分类、数据结构与算法的密切关系。（二）熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。（三）掌握设计算法的步骤和算法分析方法，掌握数据结构在排序等常用算法中的应用。三、课程的教学内容、重点和难点第一章绪论一、数据结构的基本概念二、算法描述（一）算法的概念（二）算法的描述三、算法分析与评价（一）算法设计的要求（二）算法效率的度量重点：数据结构的基本概念，逻辑结构、存储结构的联系与区别，算法的分析与评价。难点：算法分析第二章线性表一、线性表的基本概念（一）线性表的定义（二）线性表的基本运算二、线性表的顺序结构及运算实现（一）线性表的顺序存储结构（二）线性表在顺序存储结构下的运算实现三、线性表的链式存储和运算实现（一）链表的存储结构（二）单向链表（三）循环链表（四）双向链表四、线性表的应用重点：掌握在顺序表和链表上实现的插入、删除和按值查找的算法。难点：线性表与线性结构的联系与区别。头结点在链表中的作用。删除、插入运算中的指针操作顺序。第三章栈和队列一、栈（一）栈的定义和运算（二）栈的顺序存储结构及其基本运算的实现（三）栈的链式存储结构及其基本运算的实现二、栈的应用三、栈与递归（一）递归与递归程序的设计（二）递归程序执行过程的分析（三）递归的应用举例四、队列（一）队列的定义和运算（二）队列的顺序存储结构及其基本运算的实现（三）队列的链式存储结构及其基本运算的实现（四）队列应用举例重点：掌握在两种存储结构上对栈和队列所施加的基本运算的实现。难点：循环队列的队空、队满判断条件。循环队列上的插入、删除操作。第四章串一、串及其运算（一）串的逻辑结构（二）串的基本运算二、串的存储结构（一）串的顺序存储结构及其基本运算的实现（二）串的链式存储结构及其基本运算的实现重点：串的存储结构。难点：串的链式存储结构及其基本运算的实现。第五章数组和广义表一、数组（一）数组的定义（二）数组的基本操作（三）数组的存储结构二、矩阵的压缩存储（一）特殊矩阵的压缩存储方法（二）稀疏矩阵的压缩存储方法三、广义表（一）广义表的定义（二）广义表的存储结构（三）广义表的基本操作重点：理解多维数组的结构特点和在内存中的两种顺序存储方式，领会稀疏矩阵的压缩方式和简单运算。难点：稀疏矩阵的压缩存储表示下的运算的实现。第六章树和二叉树一、树的逻辑结构和存储结构（一）树的定义和基本运算（二）树的表示（三）树的存储结构二、二叉树（一）二叉树的定义与性质（二）二叉树的存储结构（三）二叉树的基本运算及实现三、遍历二叉树和线索二叉树（一）遍历二叉树（二）线索二叉树四、树、森林与二叉树的转换五、二叉树的应用（一）二叉排序树（二）路径长度和哈夫曼树（三）构造哈夫曼树重点：理解树的定义、术语，掌握其各种存储结构。深刻理解二叉树的定义、性质及其存储方法。掌握二叉树的线索化方法。熟练掌握森林与二叉树间的相互转换。领会树和森林的遍历。难点：二叉树的递归定义；二叉树链式存储结构的组织方式；三种遍历的主要区别；二叉树上的复杂运算；哈夫曼算法及其应用。第七章图一、图及其基本运算（一）图的定义（二）图的基本术语（三）图的基本运算二、图的存储结构（一）邻接矩阵（二）邻接表（三）十字链表三、图的遍历（一）深度优先搜索（二）广度优先搜索四、最小生成树（一）克鲁斯卡尔算法（二）普里姆算法*五、最短路径（一）求一顶点到其余顶点的最短路径（二）每对顶点之间的最短路径*六、拓扑排序重点：掌握图的两种存储结构的表示方法。熟练掌握图的两种遍历的算法思想。掌握拓扑排序、关键路径、最短路径的算法思想。难点：正确理解与区别图的常用术语。区别图的两种存储结构的不同点及其应用场合。关键路径的算法思想。第八章排序一、排序的基本概念（一）排序及其分类（二）排序算法的效率分析二、插入排序（一）直接插入排序（二）折半插入排序（三）希尔排序三、交换排序（一）冒泡排序（二）快速排序四、选择排序（一）简单选择排序（二）堆排序五、归并排序六、各种排序方法的比较重点：掌握各种排序方法。难点：快速排序算法，堆排序方法。第九章查找一、基本概念二、顺序表的静态查找（一）简单顺序查找（二）二分查找（三）分块查找三、树表的动态查找（一）二叉排序树（二）平衡二叉树四、散列表查找（一）什么是散列表（二）散列函数的构造方法（三）冲突的解决方法（四）散列表的查找及性能分析（五）有关散列表的算法重点：掌握在顺序表、有序表、索引表、散列表等上的查找方法和算法。难点：二叉排序树上的插入算法。平衡二叉树的旋转平衡算法；散列表上的有关算法。四、课程各教学环节要求（一）算法与数据结构知识的应用很广泛，所以授课时，应注重与实际问题的联系。（二）本课程有12学时上机实验，通过上机使学生能够深入理解算法与数据结构课程的主要内容，掌握其精髓，能够进一步熟悉C语言或者C++的编程。（三）本课程主要是由讲授和一定数量的上机实验两部分组成。在授课的过程中应安排适当的作业和练习。（四）增强学生的感性认识和实际编程能力，安排一定数量的综合性或设计性上机实验。（五）考试形式开卷、闭卷皆可，重点在于运用所学的知识对具体实际问题的解决和分析处理。五、学时分配教学内容各教学环节学时分配作业题量备注章节主要内容讲授实验讨论习题课外其它小计1绪论222线性表4433栈和队列4434串1125数组和广义表2226树81947图61748内部排序3329查找3142合计331234822六、课程与其它课程的联系本课程的先修课程为《计算机文化基础》、《C语言程序设计》或者《C++语言程序设计》。七、教材与教学参考书（一）教材赵坚等编著.数据结构（C语言版）.北京：中国水利水电出版社，2005年5月。（二）教学参考书[1]唐善策等编著.数据结构－用C语言描述.北京：高等教育出版，1995年。[2