《数据结构》教学大纲.doc

此文档收集于网络，如有侵权，请联系网站删除课程编号：“数据结构”课程教学大纲Data Structure Course Outline70学时 3.5学分一、课程的性质、目的及任务用计算机来解决实际问题时，涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用中具有举足轻重的作用。数据结构作为一门主干课程主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。主要有三个方面：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。本课程的任务是：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。二、适用专业计算机科学与技术三、先修课程离散数学、C语言程序设计四、课程的基本要求通过本课程的学习，学生应能达到下列要求：(1) 掌握线性表的定义、两种存储结构及在不同的存储结构下基本算法的实现。(2) 掌握栈、队列的定义、特点、两种存储结构及基本运算的实现；了解栈、队列的应用。(3) 了解串的定义、存储方式及串的基本运算。(4) 理解多维数组的结构特点和存储方式；了解矩阵的压缩存储。(5) 深刻理解二叉树的定义、性质及其存储方法；熟练掌握二叉树的三种遍历算法；掌握二叉树的线索化方法。(6) 深刻理解树的定义、术语；掌握树的各种存储结构及森林与二叉树间的相互转换。(7) 理解图的基本概念及术语；掌握图的两种存储结构、图的两种遍历方法；理解图的应用。(8) 掌握在顺序表、有序表、索引表、散列表等上的查找算法；理解二叉排序树、平衡二叉树、B-树的各种算法。(9) 掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、步骤及算法；了解其算法分析。五、课程的教学内容（一）课堂讲授的教学内容1 数据结构的概念数据结构的概念，抽象数据类型，算法和算法分析。2 线性表线性表逻辑结构，线性表的顺序存储及运算实现，线性表的链式存储和实现，一元多项式的表示与相加。3栈和队列栈基本概念及栈的应用，队列基本概念及队列的应用。4 串串及其基本运算，串的表示与实现，串的模式匹配算法，串的应用。5 数组和广义表数组的定义，数组的顺序表示与实现，数组的压缩存储，广义表。6 树与二叉树树的定义与基本术语，二叉树，二叉树的遍历和线索二叉树，树与森林，哈夫曼树及应用。7 图图的基本概念，图的存储表示，图的遍历，图的连通性，有向无环图及其应用，最短路径。8 查找静态查找表，动态查找表，哈希表查找(杂凑法)9排序排序的基本概念，插入排序，交换排序，选择排序，二路归并排序，基数排序。(二) 课堂讨论的教学内容下列内容可以安排讨论课：1 二叉树的遍历2 图及其应用(三)实验的教学内容1 约瑟夫环问题 2学时2 栈与队列的应用 2学时3 二叉树基本操作 2学时4 图的基本操作 2学时5常用排序算法的对比分析 2学时六、学时分配表内 容讲 课讨 论实 验小 计1 数据结构的概念222 线性表82103栈和队列6284 串445 数组和广义表556 树与二叉树1012137 图1012138 查找779排序628合 计5821070七、主要参考书1数据结构（C语言版） 严蔚敏,吴伟民编著 清华大学出版社2数据结构习题集 严蔚敏、吴伟民编著 清华大学出版社3数据结构(C语言篇)习题与解析 李春葆编著 清华大学出版社4数据结构(用面向对象方法与C+描述) 殷人昆，陶永雷编著 清华大学出