高级程序设计语言C课程教学大纲

《数据结构A》课程教学大纲

一、课程基本信息课程中文名称:数据结构A课程英文名称DataStructureA课程编号10072105课程性质学科基础课课程学时和学分总学时64总学分

3.5理论学口寸48上机学时16适用专业计算机科学与技术、网络工程、软件工程先修课程计算机程序设计语言、离散数学等开课系部、教研室电子与信息工程系、计算机应用教研室

二、课程的地位与作用《数据结构》是计算机科学中一门综合性的专业核心基础课程它是编译原理、操作系统、数据库系统原理、算法设计与分析及计算机应用方面的主要基础

三、课程总的教学目的和要求本课程教学目的是通过本课程的学习，要求学生驾驭数据结构的特点、存储方法和基本运算，培育学生运用C（C++）语言正确编程及调试的实力，运用数据结构解决简洁的实际问题的实力，为后续计算机专业课程的学习打下坚实的基础

四、各章主要教学内容第1章数据结构概述（2学时）本章应了解数据结构及算法的概念；驾驭计算语句频度和估算算法时间困难度的方法重点数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系难点算法困难度的分析方法第2章线性表（8学时）本章应了解线性表的逻辑结构特性，以及线性表的两种存储实现方式；娴熟驾驭依次表的定义与实现包括查找、插入、删除算法的实现；娴熟驾驭在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构；本章试验应驾驭线性表的基本操作在依次和链式存储结构上的实现重点依次表和单链表上实现的各种基本算法及相关的时间性能分析难点运用本章所学到的基本学问设计有效算法解决与线性表相关的应用问题第3章栈和队列（8学时）本章应驾驭栈和队列的定义、特性，并能正确应用它们解决实际问题；娴熟驾驭栈的依次表示、链表表示以及相应操作的实现；娴熟驾驭队列的依次表示、链表表示以及相应操作的实现；本章试验应驾驭栈和队列的特点及栈和队列的基本运算重点栈和队列在两种存储结构上实现的基本运算难点循环队列中对边界条件的处理第4章串（2学时）本章应理解串的基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法；娴熟驾驭在串的依次存储结构上实现串的各种操作的方法；了解串操作的应用方法和特点重点依次存储结构上串的各种操作难点串上实现的模式匹配算法第5章数组与广义表（4学时）本章应了解数组的两种存储表示方法，并驾驭数组在以行为主的存储结构中的地址计算方法；驾驭对特别矩阵进行压缩存储时的下标变换公式；了解稀疏矩阵的两种压缩存储方法的特点和适用范围，理解以三元组表示稀疏矩阵时进行矩阵运算采纳的处理方法；驾驭广义表的结构特点及其存储表示方法，会对非空广义表进行分解重点多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算难点稀疏矩阵的压缩存储表示下实现的算法第6章树与森林（10学时）本章应了解树和森林的概念包括树的定义、树的术语和性质；娴熟驾驭二叉树的结构特性，熟识二叉树的各种存储结构的特点及适用范围；娴熟驾驭二叉树的遍历方法及遍历算法；熟识树的各种存储结构及其特点，驾驭树、森林与二叉树的转换方法；驾驭建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算；本章试验应驾驭二叉树的结构特性，以及用指针类型描述、访问和处理二叉树的运算重点二叉树的遍历算法及其相关应用难点运用本章所学到的有关学问设计出有效算法，解决与树或二叉树相关的应用问题第7章图（10学时）本章应理解图的基本概念，熟识图的各种存储结构及其构造算法；娴熟驾驭图的两种搜寻路径的遍历并理解算法；驾驭构造最小生成树的方法；理解用Dijkstra方法求解单源最短路径问题；驾驭求活动网络的拓扑排序的方法，并理解算法；了解求解关键路径的方法；本章试验应熟识图的存储结构及邻接矩阵和邻接表等有关概念，驾驭图的两种搜寻路径的遍历方法重点图的两种存储结构上实现的遍历算法难点图的应用的实现第8章查找（8学时）本章应娴熟驾驭依次表和有序表的查找算法及其性能分析方法；娴熟驾驭二叉排序树的构造和查找算法及其性能分析方法；理解AVL树的维护平衡方法；了解B_树、B+的特点、查找及构造方法；娴熟驾驭哈希函数的构造及解决冲突的方法；本章试验应娴熟驾驭二叉排序树的构造和查找方法重点依次查找、二分查找，二叉查找树上查找以及散列表上查找的基本思想和算法实现难点二叉查找树的删除算法及B—树上的插入和删除算法第9章排序（12学时）本章应驾驭排序的基本概念和各种排序方法的特点，并能加以敏捷应用；驾驭插入排序、交换排序、选择排序、归并排序的方法及其性能分析方法；了解基数排序方法及其性能分析方法；本章试验应驾驭常用的排序方法，并驾驭用高级语言实现排序算法的方法重点快速排序、堆排序、归并排序和希尔排序的基本思想及排序过程难点这四个排序算法的实现试验1线性表的应用（4学时）试验目的驾驭线性表的基本操作在依次和链式存储结构上的实现试验要求

（1）建立含有若干个元素的依次表链表；

（2）对已建立的依次表实现插入、删除、查找、逆置等操作试验2栈和队列的应用（2学时）试验目的驾驭栈和队列的特点，及栈和队列的基本运算试验要求

（1）栈的初始化、判栈是否为空、进栈、出栈等运算的实现

（2）利用栈实现判定表达式中的括号是否匹配试验3数组的应用（2学时）（选作）试验目的熟识数组的有关概念，驾驭稀疏矩阵的三元组存储结构的转置方法试验要求采纳两种方法实现稀疏矩阵的转置试验4树和森林的应用（2学时）试验目的驾驭二叉树的结构特性，以及用指针类型描述、访问和处理二叉树的运算试验要求

（1）创建以二叉链表作存储结构的二叉树；

（2）按中序遍历二叉树；

（3）计算二叉树的单枝结点数；

（4）按层次遍历二叉树试验5图的应用（4学时）试验目的熟识图的存储结构及邻接矩阵和邻接表等有关概念，驾驭图的两种搜寻路径的遍历方法试验要求

（1）创建以邻接表作存储结构的无向图；

（2）按深度优先遍历图；

（3）按广度优先遍历图试验6查找方法的实现（2学时）试验目的娴熟驾驭二叉排序树的构造和查找方法试验要求

（1）创建以二叉链表作存储结构的二叉排序树；

（2）实现二叉排序树的查找、插入、中序遍历操作试验7排序方法的实现（2学时）试验目的驾驭常用的排序方法，并驾驭用高级语言实现排序算法的方法试验要求用各种排序方法实现学生考试成果表的排序并输出学生的考试成果表必需通过键盘输入数据而建立，同时要对输出格式进行限制试验课考核方式采纳课堂表现和试验报告相结合方式试验课成果占课程总成果的10%o

五、课程考核和成果评定方式闭卷考试和平常考核方式结合，期末考试占70%；平常成果占30虬

六、教材与主要参考书.教材

[1]王红梅，胡明，王涛.数据结构（C++版）.北京清华高校出版社，

2005..试验指导书或教材

[1]王红梅，胡明，王涛.数据结构（C++版）学习辅导与试验指导北京清华高校出版社，

2005.

[2]严蔚敏，吴伟民著.数据结构题集（C语言版）.北京清华高校出版社，

1997.、主要参考教材和参考文献

[1]严蔚敏，吴健民.数据结构（C语言版）.北京清华高校出版社，

1997.2]Robert.KruseC.L.TondoBruceLeung.《DataStructuresprogramdesigninC》2ndEdition.4匕京清华高校出版社.笔人邢振祥审核。