数据结构C语言版教学大纲.doc

《数据结构（C语言版）》教学大纲 湖南省郴州职业技术学院计算机系 编写时间：2004年8月28日  《数据结构（C语言版）》教学大纲 一、课程性质、任务和基本要求 ⒈本课程的教学目的和要求 用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用中具有举足轻重的作用。　　 　　本课程的任务是：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。 ⒉本课程的主要内容 ⑴数据、数据元素和数据项的概念及其相互间的关系；数据结构的逻辑结构、存储结构的联系与区别以及在数据结构上施加的运算及其实现。 ⑵线性表的定义及其运算；顺序表和链表的定义、组织形式、结构特征和类型说明以及在这两种表上实现的插入、删除和按值查找的算法。循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。 ⑶栈和队列的定义、特征及在其上所定义的基本运算，在两种存储结构上对栈和队列所施加的基本运算的实现。 ⑷串的定义、存储方式和常用的串运算；多维数组的结构特点和在内存中的两种顺序存储方式，矩阵和三角矩阵元素的存储。 ⑸树的定义、性质及其存储方法；二叉树的二叉链表存储方式、结点结构和类型定义；二叉树的遍历算法；树、森林与二叉树间的相互转换；哈夫曼树的构造方法。 ⑹图的基本概念及术语；图的两种存储结构(邻接矩阵和邻接表)的表示方法；图的遍历(深度优先有哪些信誉好的足球投注网站遍历和广度优先有哪些信誉好的足球投注网站遍历)算法；最小生成树的构造；拓扑排序、关键路径以及最短路径算法。 ⑺查找的基本思想及查找成功和不成功的概念；在顺序表、有序表、索引表、散列表等上的查找方法和算法；二叉排序树、平衡二叉树以及B-树的概念和有关算法；散列表的构造。 ⑻排序的基本思想和基本概念；插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序及基数排序的基本思想、步骤及算法。 ⒊教学重点及难点 　　⑴领会数据、数据元素和数据项的概念及其相互间的关系。清楚数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实现。会进行简单的算法分析。 ⑵理解线性表的定义及其运算。理解顺序表和链表的定义、组织形式、结构特征和类型说明，掌握在这两种表上实现的插入、删除和按值查找的算法。了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。了解串的定义、存储方式和常用的串运算。 ⑶理解栈和队列的定义、特征及在其上所定义的基本运算，掌握在两种存储结构上对栈和队列所施加的基本运算的实现。理解多维数组的结构特点和在内存中的两种顺序存储方式，对矩阵和三角矩阵能推出给定元素在存储区中的地址。 ⑷深刻理解树的定义、性质及其存储方法，熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义，并能画出给定二叉树的二叉链表的结构示意图；理解并掌握二叉树的三种遍历方法，并能写出该三种遍历的算法；会完成树、森林与二叉树间的相互转换；理解哈夫曼树的构造方法，并能对给定的数据集合构造出哈夫曼树。 　　⑸理解图的基本概念及术语，掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法；熟练掌握图的两种遍历(深度优先有哪些信誉好的足球投注网站遍历和广度优先有哪些信誉好的足球投注网站遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解最小生成树的概念，能按Prim算法构造最小生成树；了解并掌握拓扑排序、关键路径、最短路径的算法思想。 ⑹了解查找的基本思想及查找成功和不成功的概念，掌握在顺序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相应的平均查找长度。 ⑺了解排序的基本思想和基本概念，理解和掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、步骤及算法。 4．教材的选用 严蔚敏,吴伟民.数据结构（C语言版）.北京：清华大学出版社.1999,2 二、课程时数分配 内 容 讲课 实验 小计 第一章　绪论 2 2 第二章　线性表 12 4 16 第三章 栈和队列 6 2 8 第四章 串 6 2 8 第五章 数组和广义表 6 6 第六章 树和二叉树 12 4 16 第七章 图 8 4 12 第九章 查找 8 4 12 第十章 排序 8 4 12 总 计 68 16 92 三、课程内容 第一章　　概论 ⒈教学内容 　　1.1 数据结构的概念 抽象数据类型 算法和算法分析。 ⒉教学目的及要求 ⑴领会数据、数据元素和数据项的概念