006A1060《数据结构》教学大纲_数据结构本教学大纲

006A1060《数据结构》教学大纲由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构本教学大纲”。

《数据结构》教学大纲

课程英文名称：Data Structure

课程编号：006A1060

学时：54＋18（实验）

学分：4.0分

一、课程教学对象

本教学大纲适用于五邑大学信息学院计算机科学与技术专业的普通本科生数据结构课程的教学。

二、课程性质、目的和任务

数据结构课程是计算机科学与技术专业必修的专业基础课，是计算机专业学科的核心课程。是编译原理、操作系统等课程的基础。

数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、人工智能、数据系统及其它系统程序和大型应用程序的重要基础。同时，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。

值得注意的是，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来讨论数据结构，已成为一种新的趋势，越来越被人们所重视。

根据我校“培养高素质应用型创新人才”的人才培养的层次定位，以及我院生源的实际情况，本课程在专业培养目标中的定位：一是要满足后继专业课程的基本需要；二是要为今后研制开发各种应用软件打下扎实的理论和实践基础，使学生在编程能力方面得到比较系统的训练，以适应计算机学科专业对应用型、复合型人才培养的要求。

为此，本课程强调理论和实践的统一，突出对学生的动手能力的培养。在对学生进行基本数据结构的技术、理论、设计等各种技能培养的同时，突出对学生进行将实际问题转化为基本数据结构的问题的分析能力。鼓励学生学以致用，将学到的知识用以解决实际问题。在教学方法上应用现代教育技术，采用多媒体课件形式辅助教学，对抽象的数据结构辅之以形象的动画，不仅能提高学生的学习兴趣，也加深了学生对抽象概念的理解。运用网络教学平台辅助教学，加强教学过程的师生互动，对课程实施规范化管理。

本课程的目标：适应计算机学科各个专业发展的需要，使学生掌握基本数据结构及其特点，了解数据结构与算法的关系及优劣，培养学生设计及选择有效的算法、设计合适的数据结构的能力，并具有初步的算法分析能力。在教学过程中，将后续课程中常用到的基本知识，如《编译原理》中用到的线性表、栈、查找树，《操作系统》中用到队列、目录树等，作为本课程的重点，注重学生分析问题、解决问题能力及自主创新能力的培养，使本课程在处理知识面的宽度和深度上，既满足作为学科基础课的要求又达到一定的水平。

三、对先修课的要求

高级程序设计语言、离散数学是学习数据结构的主要先修课程。具体要求如下： 1． 掌握程序设计语言的基本概念。

2． 掌握结构化程序设计的的基本原理、良好的设计习惯，并具备较好的程序调试能力。3． 掌握离散数学的基本理论。4．具有一定的逻辑思维和推理能力

四、课程的主要内容、基本要求和学时分配建议（总学时数: 54）

本课程着重介绍数据结构的基本概念、基本算法以及各种常用数据结构，主要包括线性表、栈和队列和串、广义表、树和二叉树、图、排序、查找等内容。阐明各种数据结构的内在逻辑关系、存储结构和相应运算。本课程计划总学时为72学时，理论课54学时，实验18学时，授课学时（理论课54学时）分配如下： 第1章

绪论(6学时)

主要内容：

数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和实现方法；描述算法的伪代码方法；算法设计的基本要求以及从时间和空间角度分析算法的方法。

学习要求：

1．数据结构的兴起和发展（C）

2．数据结构的研究对象

（A）

3．数据结构的基本概念

（A）

4．抽象数据类型的概念

（B）

5．算法的特性和基本方法（B）

6．算法时间复杂度的方法（B）

第2章线性表(6学时)

主要内容：

线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线性表的两类存储结构上实现基本操作；稀疏多项式的抽象数据类型定义、表示和加法的实现。

学习要求：

1．线性表的定义及其逻辑特征

（A）

2．线性表的抽象数据类型定义

（B）

3．顺序表的存储结构、基本操作算法及其时间性能

（A）

4．各种链表结构中实现线性表操作的基本方法及其时间性能

（A）

5．静态链表和间接寻址的存储方法

（B）

6．顺序表类、单链表类与线性表处向数据类型之间的关系

（B）第3章

特殊线性表——栈、队列和串(6学时)

主要内容：

栈和队列的结构特性，在两种存储结构上如何实现栈和队列的基本操作，以及栈和队列在程序设计中的应用。串的数据类型定义；串的3种存储表示；定长顺序存储结构、块链存储结构和堆分配存储结构；串的各种基本操作的实现及其应用；串的模式匹配算法。

学习要求：

1．栈的定义及其操作特性

（A）

2．栈的抽象数据类型定义

（B）

3．顺序栈和链栈的实现方法

（A）

4．队列的定义及其操作特性

（A）

5．队列的抽象数据类型定义

（B）

6．顺序队列和链队列的实现方法

（A）

7．串的定义及其基本概念

（B）

8．串的存储方法、BF算法的执行过程

（B）

第4章

广义线性表——多维数组合广义表(4学时)

主要内容：

数组是一种十分常用的数据结构，大多数程序设计语言都支持数组类型。本章重点介绍数组的内部实现，即如何在计算机内部处理数组，其中的主要问题是数组的存储结构与寻址。广义表示一种特殊的数据结构，它兼有线性表、树、图等结构的特点。

学习要求：

1．数组的定义、存储结构及寻址方法

（A）

2．矩阵压缩存储的基本思想

（B）

3．特殊矩阵和稀疏矩阵的压缩存储方法及寻址方法（A）

4．三元组顺序表的转置运算

（B）

5．广义表的定义及其基本概念（A）

6．广义表的存储结构

（B）

7．广义表的基本运算

（C）第5章

树和二叉树(8学时)

主要内容：

二叉树的定义、性质和存储结构；二叉树的遍历和线索化以及遍历算法的各种描述形式；树和森林的定义、存储结构、与二叉树树的转换、遍历；树的多种应用。本章是课程的重点内容之一。

学习要求：

1．树的定义及其基本术语

（A）

2．树的抽象数据类型定义

（B）

3．树的各种存储方法

（A）

4．树和森林的遍历方法

（A）

5．二叉树的定义及特点、二叉树的基本性质

（A）

6．二叉树的各种存储结构方法、遍历方法及实现（A）

7．树、森林与二叉树树的转换方法

（A）

8．哈夫曼树的构造方法和哈夫曼编码方法

（A）

9．哈夫曼树的构造算法

（B）

第6章

图(8学时)

主要内容：

图的定义和术语；图的四种存储结构：数组表示法、邻接表、十字链表和邻接多重表；图的两种遍历策略：深度优先搜索和广度优先搜索；图的连通性：连通分量和最小生成树；拓扑排序和关键路径；两类求最短路径问题的解法。

学习要求：

1．图的定义及其基本术语

（A）

2．图的邻接矩阵和邻接表存储（A）

3．图的遍历方法及其在邻接矩阵和邻接表存储结构上的实现

（A）

4． 无向图和有向图的连通性

（B）

5． Prim算法和Kruskal算法的基本思想和求解过程

（A）6． Prim算法和Kruskal算法的C++描述

（B）

7． Dijkstra算法和Floyd算法的基本思想和求解过程

（A）8． 拓扑排序的定义及拓扑排序算法

（A）9． 关键路径的定义及求解过程

（A）10．关键路径算法

（B）第7章

查找技术(6学时)

主要内容：

讨论查找表(包括静态查找表和动态查找表)的各种实现方法：顺序表、有序表、二叉排序树、平衡二叉树和散列表；以及关于衡量查找表的主要操作—查找的查找效率的平均查找长度的讨论。

学习要点：

1．查找的基本概念以及查找算法的时间性能分析

（B）

2．顺序表和折半查找技术

（A）

3．二叉排序树的定义、查找算法及时间性能

（A）

4．平衡二叉树的定义及调整方法

（A）

5．平衡二叉树的插入算法

（C）

6．散列的基本思想和基本概念

（A）

7．散列技术中处理冲突的方法

（A）

8．散列技术的查找性能

（B）第8章

排序技术(8学时)

学习内容：

讨论和比较各种内部排序方法：插入排序、交换排序、选择排序、堆排序和归并排序的基本思想、算法特点、排序过程以及它们的进间复杂度分析。

学习要点：

1．排序的定义以及评价排序算法的标准

（A）

2．直接插入排序算法及其时间性能

（A）

3．希尔排序

（B）

4．起泡排序算法及其时间性能

（A）

5．快速排序算法及其时间性能和空间性能

（A）

6．简单选择排序算法及其时间性能

（A）

7．堆的定义及构建堆的方法、堆排序算法及其时间性能

（A）

8．二路归并排序算法及其时间性能和空间性能

（A）

9．各种排序方法的比较及结论

（A）课程实践活动成果展示课(2学时)

对课程涉及的线性表、树、图及查找排序算法等核心内容，要求学生结合实际问题进行自主选题，利用课外学习团队完成相应原理的动画制作，相应算法的编写与实现。为每个团队提供展示作品的舞台，相互交流，进行评比，教师点评及总结。

五、实验内容和实验要求（学时数: 18）

1.基本要求

数据结构是一门实践性较强的课程，每个学生必须完成一定数量的上机作业。通过上机作业，要求在数据结构的逻辑特性和存储表示，基本数据结构的选择和应用、算法设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法、上机操作等基本技能和科学作风方面接受比较系统的、严格的训练。

本课程始终坚持理论和实际相结合的原则，布置足够多的习题和较大型的上机实践题。为了巩固课堂所学知识，要求学生课内、课外时间比达到1：1.5~1：2，以便更好地巩固基本算法，提高分析和设计算法的能力，为后续课程的学习打好基础。2．实验教学安排

实验一 线性表

（2学时）

了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系有顺序存储结构和链式存储结构；掌握这两种存储结构的描述方法；掌握线性表的基本操作（查找、插入、删除）；考虑时间复杂度和空间复杂度进行算法设计。实验二 栈

（2学时）

理解栈的定义、特点及与线性表的异同； 熟悉顺序栈的组织方法，栈满、栈空的判断条件及其描述；掌握栈的基本操作（进栈、退栈等）。

实验三 队列

（2学时）

理解队列的定义、特点及与线性表的异同； 熟悉队列的组织方法，队列满、队列空的判断条件及其描述； 掌握队列的基本操作（入队、出队等）。实验四 二叉树

（2学时）

掌握二叉树的结构特性和二叉链表的存储结构；理解二叉树、完全二叉树、满二叉树的概念和存储特点；掌握二叉树遍历的递归和非递归方法。实验五 哈夫曼树

（2学时）

理解哈夫曼树的概念、结构特性和哈夫曼编码原理；掌握构造哈夫曼树的基本方法；掌握运用哈夫曼树进行哈夫曼编码的方法。

实验六 图的存储

（2学时）

理解图的基本概念、图的结构特性；掌握邻接表表示图的基本方法；掌握连通图遍历的基本的方法。实验七 图的应用

（2学时）

理解拓扑排序的基本概念和拓扑排序的实用意义；掌握AOV网解决拓扑排序问题的基本方法。理解最小生成树的基本概念和实用意义；掌握利用MST性质构造最小生成树的prim算法和Kruskal算法。

实验八 查找

（2学时）

理解查找表的基本概念，定义、分类和各类的特点；掌握哈希表的构造方法以及解决冲突的方法；掌握哈希存储和哈希查找的基本思想及有关方法。实验九 排序

（2学时）

理解各类内部排序的基本思想；掌握各类内部排序的基本方法；了解各类内部排序的优缺点。

六、教材及参考书

1．理论课教材

理论课教材：

王红梅等．数据结构（C++版）[M] ．北京：清华大学出版社，2007 实验课教材：

王红梅等． 数据结构（C++版）学习辅导和实验指导[M] ．北京：清华大学出版社，2006 2．主要参考文献

[1] 许卓群．数据结构[M]．北京：高等教育出版社，2006 [2] 殷人昆．数据结构C＋＋实现[M]．北京：清华大学出版社，2006 [3] 黄国瑜，叶乃菁．数据结构[M]．北京：清华大学出版社，2005

[4] 胡学刚．数据结构算法设计指导[M]．北京：清华大学出版社，2004 [5] 胡元义，邓亚玲，徐睿琳．数据结构课程辅导与习题解析[M]．北京：人民邮电出版社，2003 [6] 罗文，王苗，石强．数据结构习题解答与实验指导[M]．北京：中国铁道出版社，2003 [7] 王晓东．数据结构（C语言版）[M]．北京：电子工业出版社，2007 [8] 陈慧南．数据结构——使用C++语言描述[M]．北京：人民邮电出版社，2006 [9] 吕国英．算法设计与分析[M]．北京：清华大学出版社，2006 [10] Sartaj Sahni．Data Structures, Algorithms and Applications in C++[M]．北京：机械工业出版社，2003 [11] William Ford．Data Structure with C++[M]．北京：清华大学出版社，2001 [12] 苏光奎．数据结构导学[M]．北京：清华大学出版社，2002 [13] 严蔚敏等．数据结构（C语言版）[M]．北京：清华大学出版社，2002 [14]（美）Michael T.Goodrich，Roberto Tamaia著．霍红卫译．算法分析与设计[M]．北京：人民邮电出版社 [15]（美）Bruno R.Prei著．胡广斌等译．数据结构与算法—面向对象的C++设计模式 [M]．北京：电子工业出版社

七、考核方式

以闭卷考试为主，结合平时作业及自主应用和设计综合评定成绩。各部分分配比例为： 期末考试成绩70%，平时作业及考勤10%，实验10%，自主设计作品或期中考核10%。

执笔人： 白明

编写日期： 2007-10-31 7