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 Tamassia著．霍红卫译．算法分析与设计[M]．北京：人民邮电出版社 [15]（美）Bruno R.Preiss著．胡广斌等译．数据结构与算法—面向对象的C++设计模式 [M]．北京： 电子工业出版社

七、考核方式

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

执笔人： 白明

编写日期： 2007-10-31 7

第二篇：数据结构教学大纲

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

课程编号：030816 适用专业：教育技术学 总学时数：64

学 分：4 编制单位：茂名学院理学院教育与信息技术系 编制时间：2008年6月20日

一、课程地位、性质和任务

《数据结构与算法》课程是计算机相关学科专业的基础课程中的一门重要的核心课程。通过本课程的教学，使学生知道求解非数值类问题的基本模型（表、树、图），模型的特点和适用场合，能够根据问题设计和选择好的算法，为学习后续的操作系统、编译原理和软件工程等专业课程，设计应用程序打下基础。

本课程以提高学生的计算机应用能力和综合素质为目标，通过课程教学，为学生构建数据结构与算法方面的知识体系，使学生一方面能够根据问题选择合适的数据结构，设计高效的算法，提高程序设计能力，另一方面，在工程应用中，具有甄别好算法的能力，也就是要从建模、解模和综合等三个方面，提高学生的程序设计能力。

二、与其他课程的关系

先修课：程序设计基础、离散数学、计算机组成原理、计算机文化基础

三、教学内容、课时安排和基本要求

（一）教学部分 第1章 绪论（2学时）1.1什么是数据结构 1.2 基本概念和术语

1.3 抽象数据类型的表示与实现

1.4 算法和算法分析（算法及其设计的要求，算法效率的度量，算法的存储空间需求）1.5 问题求解

基本要求：

了解：抽象数据类型，算法设计方法与算法分析。

掌握：数据与数据结构、算法的基本概念；问题求解的方法与步骤 重点：数据结构和算法的概念，算法的描述形式和评价方法，问题求解的一般步骤 难点：评价算法的标准和评价方法，最坏情况和平均情况的区分。

第2章 线性表（8学时）2.1 线性表的类型定义 2.2 线性表的顺序表示和实现

2.3 线性表的链式表示和实现（线性链表，循环链表，双向链表）2.4 一元多项式的表示及相加

基本要求：

了解：两种存储结构（顺序存储结构和链式存储结构）及一元多项式的表示及相加。

掌握：要求熟练掌握处理线性表的各种算法。为后继章节的学习打基础。重点：各种算法。难点：链表的理解。

第3章 栈与队列（4学时）

3.1 栈（定义，栈的表示和实现）

3.2 栈的应用举例（数制转换，括号匹配的检验，行编辑程序，迷宫求解，表达式求值）

3.3 栈与递归的实现

3.4 队列及其实现（定义，链队列，循环队列）3.5 *离散事件模拟

教学要求：熟练掌握栈和队列的特性和在不同存储结构前提下的算法实现。栈和队列是表最基本和重要的数据结构，是数据结构课程的基础。

基本要求：

了解： 栈和队列的定义及其实现。

掌握： 熟练掌握栈和队列的特性和在不同存储结构前提下的算法实现。重点： 栈和队列的算法实现。难点： 栈和队列的算法实现。

第4章 串（2学时）4.1 串类型的定义

4.2 串的表示和实现（定长顺序存储，堆分配存储，串的块链存储）4.3 串的模式匹配算法（求子串位置的定位函数，模式匹配的一种改进算法）4.4 串操作应用举例（文本编辑，建立词索引表）

基本要求：

了解：串的基本概念及主要操作和运算。掌握：掌握串的基本概念和运算。重点：主要操作和运算。难点：模式匹配及串的应用。

第5章 数组（2学时）5.1 数组的定义

5.2 数组的顺序表示和实现

5.3 矩阵的压缩存储（特殊矩阵，稀疏矩阵）5.4 广义表的定义 5.5 广义表的存储结构 5.6 m元多项式的表示

5.7 广义表的递归算法（求广义表的深度，复制广义表，建立广义表的存储结构）

基本要求：

了解：了解作为抽象数据类型的数组和C语言的数组。认识到数组可以作为顺序存储结构用于顺序表、字符串和稀疏矩阵的实现。也可以采用链式存储结构。

掌握：掌握基本概念和算法。重点：算法。

难点：广义表的递归算法。

第6章 树与二叉树（15学时）6.1 树的定义和基本术语

6.2 二叉树（二叉树的定义，二叉树的性质，二叉树的存储结构）6.3 遍历二叉树和线索二叉树（遍历二叉树，线索二叉树）

6.4 树和森林（树的存储结构，森林与二叉树的转换，树和森林的遍历）6.5 树与等价问题

6.6 赫夫曼树及其应用（最优二叉树（赫夫曼树），赫夫曼编码）6.7 回溯法与树的遍历 6.8 树的计数

基本要求：

了解：理解树与森林的定义与术语。

掌握：熟练掌握二叉树性质和遍历算法，掌握树与森林的孩子兄弟存储表示和遍历。掌握哈夫曼树构造的方法和算法。重点： 树的存储结构和遍历算法。难点：哈夫曼树构造的方法和算法

第7章 图（11学时）7.1 图的定义和术语

7.2 图的存储结构（数组表示法，邻接表，十字链表，邻接多重表）7.3 图的遍历（深度优先搜索，广度优先搜索）

7.4 图的连通性问题（无向图的连通分量和生成树，有向图的强连通分量，最小生成树，关节点和重连通分量）

7.5 有向无环图及其应用（拓扑排序，关键路径）

7.6 最短路径（从某个源点到其余各项点的最短路径，每一对顶点之间的最短路径）基本要求：

了解：图的基本概念和相关术语。

掌握：图的两种主要存储结构及遍历算法。掌握最小生成树、最短路径和活动网算法的思想。

重点：图的两种主要存储结构及遍历算法。难点：图的遍历算法，最短路径算法。

第8章 查找（8学时）

9.1 静态查找表（顺序表，有序表，静态树表，索引顺序表）9.2 动态查找表（二叉排序树和平衡二叉树，B_树和B+树，键树）9.3 哈希表（定义，构造方法，处理冲突的方法，查找及其分析）

基本要求：

了解： 各种查找法的基本概念及实现的基本思想。

掌握：熟练掌握搜索结构的折半查找、二叉搜索树、平衡二叉树主要搜索算法。掌握哈希表查找算法。重点：各种算法的基本思想及实现。难点：哈希表查找算法。

第9章 内部排序（8学时）10.1 概述

10.2 插入排序（直接插入，其他插入，希尔）10.3 交换排序（冒泡排序、快速排序）10.4 选择排序（简单，树形，堆）10.5 归并排序

10.6 基数排序（多关键字，链式）10.7 排序算法分析

基本要求：

了解：基数排序，排序算法分析方法

掌握：排序的基本概念，插入排序，交换排序，选择排序，归并排序重点：内部排序算法

难点：基数排序（多关键字，链式）

第10章 *外部排序（2学时）11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换-选择排序 11.5 最佳归并树

基本要求：

了解：外部排序的基本概念和相关术语。

掌握：基本掌握外排算法的基本思想，不同排序方法的比较。重点：外部排序算法 难点：多路平衡归并的实现 第11章 算法设计的一般方法（2学时）

1．重点

（1）有效算法的概念，问题固有难度的概念；

（2）递归法；分治法；平衡原则；贪心法；动态规划的基本原理；（3）搜索-回溯法的基本原理和本质.2．难点

（1）问题固有难度的概念；

（2）递归分治法的效率分析（写出时间耗费的递推式，并求解）；（3）动态规划法中的状态转移方程的确定。

（二）实验、实习部分

课程安排五个类别的实验，实验时数为12课时，其中： 实验

一、线性链表及运算 2课时 实验

二、栈和队列 2课时 实验

三、树和二叉树 4课时 实验

四、图及其应用 2课时 实验

五、查找与排序 2课时

四、课程考核方式

闭卷考试70%、平时作业与实验30%

五、建议教材和教学参考书 参考教材：

1、《数据结构》（C语言描述）高等教育出版社 耿国华主编

2、《数据结构》（C语言版）清华大学出版社 严蔚敏，吴伟民编者

3、《数据结构题集》（C语言版）清华大学出版社 严蔚敏，吴伟民编者

4、《数据结构》算法实现及解析（第二版）西安电子科技大学出版社 高一凡

六、说明

1、因课时安排少，教学内容多。建议采用多媒体教学。

2、由于本课程内容较多，在实际教学中可根据大纲内容，进行适当调整。

第三篇：数据结构教学大纲

中央广播电视大学“开放教育试点”计算机科学与技术专业（本科）

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

第一部分 大纲说明

一、课程的性质和任务

《数据结构》是计算机科学与技术专业本科生的一门必修课程。本课程介绍如何组织各种数据在计算机中的存储、传递和转换。内容包括：数组、链接表、栈和队列、递归、树与森林、图、堆与优先级队列、集合与搜索结构、排序、索引与散列结构等。课程采用面向对象的观点讨论数据结构技术，并以兼有面向过程和面向对象双重特色的C++语言作为算法的描述工具，强化数据结构基本知识和面向对象程序设计基本能力的双基训练。为后续计算机专业课程的学习打下坚实的基础。

二、先修课要求

面向对象程序设计、计算机数学(离散数学)。

三、课程的教学基本要求

1、掌握重要数据结构的概念、使用方法及实现技术；

2、学会做简单的算法分析，包括算法的时间代价和空间代价。

四、教学方法和教学形式建议

电视授课为主，结合面授辅导、面授或电子邮件答疑，进行必要的上机实验。

五、课程教学要求的层次

1、熟练掌握：要求学生能够全面、深入理解和熟练掌握所学内容，并能够用其知识分析、设计和解答相关的应用问题。

2、掌握：要求学生能够较好地理解和掌握，并且能够做简单的分析。

3、了解：要求学生能够一般地了解的所学内容。

六、课程实验

实验内容和要求由省级电大作出具体规定，从2004年春开始按该课程实验教材规定进行。

第二部分 多种媒体教材一体化总体设计初步方案

一、学时分配

课程教学总学时数为 72学时，4学分，其中讲授学时48，实验24

教 学 内 容

讲授学时

实验学时

一、数据结构基本概念及算法分析

3学时

2学时

二、数组

3学时

2学时

三、链表

3学时

3学时

四、栈和队列

3学时

2学时

五、递归

3学时

2学时

六、树与森林

9学时

4学时

七、集合与搜索

5学时

2学时

八、图

7学时

4学时

九、排序

7学时

3学时

十、索引与散列结构

5学时

二、教学环节

1、电视教学

本课程是计算机专业基础课，内容多且带有一定的抽象性，学习起来有一定难度。为保证教学效果，采取电视集中授课方式。聘请有经验的教师担任主讲教师，尽可能利用多种媒体进行教学，使学生能够很快掌握课程的主要知识和解决问题的方法。

2、面授辅导或答疑

本课程教学过程中，面授辅导和答疑是必不可少的教学环节。各地方电大应聘请有经验、认真负责的教师任教，以习题课、专题讨论或答疑的方式，对课程中的重要概念和典型问题的解决方法进行总结和深入讨论，巩固和加深课堂内学到的知识。面授辅导或答疑安排两周一次为宜。必要时可采用电子邮件方式直接与主讲教师联系进行答疑。

3、自学与练习

自学是获取知识的重要手段。教师讲课只是起到抛砖引玉的作用，关键还在于学生的自学。为达到自学的效果，除读懂教科书中所讲内容外，还需大量做题。其目的是要通过做题弄懂、加深对概念的理解，提高程序设计，解决问题的能力。为此，安排一定的实验上机学时。要求学生珍惜实验机时，真正做到学有所获。

学生在上机做实验前，应事先将程序、调试数据、上机操作顺序准备好，并提前使用这些调试数据人工执行过。目的是提高上机的效率和成功率，严禁抄袭或拷贝他人的成果，自觉培养科学、严谨的作风。

除学校提供的时间外，要求课外学生利用自己可能拥有的计算机条件，完成更多的练习，不通过大量的实践，能力和知识水平得不到有效得提高。

4、考试

考试是对学生掌握知识水平的检验。本着多练多考的原则，各地方电大可以再平时多做一些小考。要求考试内容紧扣大纲要求，既要能够检验学生的掌握情况，又要体现水平。因此，不要出难题、怪题，但也不要过于简单，适当有一些编程题。

课程考试具体规定请参看该课程考核说明。

第三部分 教学内容和教学要求

一、数据结构基本概念及简单的算法分析 3学时

1、教学内容：

什么是数据结构

抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言

数据结构的抽象层次

算法定义

性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂度

2、教学要求：

了解：什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系

了解：什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象

了解：算法的定义、算法的特性、算法的时间代价、算法的空间代价

掌握：用C++语言描述算法的方法，能够使用C++语言编写程序

二、数组 3学时

1、教学内容：

作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组；数组的顺序存储方式

顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例

字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配

2、教学要求：

了解：线性表的逻辑结构特性，以及线性表的两种存储实现方式

了解：作为抽象数据类型的数组的定义，数组的按行顺序存储与按列顺序存储

熟练掌握：顺序表的定义与实现，包括搜索、插入、删除算法的实现及其平均比较次数的计算，掌握应用顺序表作为集合的简单操作

了解：稀疏矩阵的定义及其数组实现

熟练掌握：字符串的定义及实现

三、链表 3学时

1、教学内容：

单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；静态链表

循环链表：循环链表的类定义；用循环链表解约瑟夫问题；

多项式及其相加：多项式的类定义；多项式的加法

双向链表

2、教学要求：

了解：链表与数组一样，是一种实现级结构。有动态链表和静态链表之分

了解：链表有单链表、循环单链表、双向链表之分

了解：单链表的结构、特点

掌握：单链表的类定义、构造函数、单链表的插入与删除算法

了解：带表头结点的单链表的优点和类定义及相应操作的实现

熟练掌握：用模板定义的单链表类

了解：循环链表的特点，循环链表的类定义，以及用循环链表解决问题的方法

掌握：双向链表的特点，双向链表的类定义及相关操作的实现，用双向链表解决问题的方法。

四、栈和队列 3学时

1、教学内容：

栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示

表达式求值：中缀表达式求值；中缀表示到后缀表示的转换

队列 ：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示；队列的应用举例

优先级队列：优先级队列的定义；优先级队列的存储表示

2、教学要求：

熟练掌握：栈的定义、特性和栈的抽象数据类型，栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件

了解：在表达式计算时栈是如何使用的，重点了解用后缀表示计算表达式及中缀表示改后缀表示的方法和算法思路

熟练掌握：队列的定义、特性和队列的抽象数据类型，队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针的变化情况

掌握：优先级队列的定义、特性和优先级队列的抽象数据类型，优先级队列的插入与删除算法

五、递归 3学时

1、教学内容：

递归的概念：递归问题的求解

递归过程与递归工作栈：单向递归和尾递归的迭代实现；一般递归问题利用栈实现非递归解法

广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广义表的访问算法；广义表的递归算法

2、教学要求：

掌握：递归的概念。包括什么是递归，有那些种类的递归，递归问题的递归求解方法

掌握：递归过程的机制与利用递归工作栈实现递归的方法

了解：迷宫问题的递归求解思路及如何利用栈实现迷宫问题的非递归解法

掌握：利用递归解决问题的分治法和回溯法

掌握：广义表的定义及其实现方法

掌握：广义表的递归算法

六、树与森林 9学时

1、教学内容：

树和森林的概念：树的定义；树的术语；树的抽象数据类型

二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型

二叉树的表示：顺序表示；二叉链表表示

遍历二叉树：中序遍历；前序遍历；后序遍历；应用二叉树遍历的事例；二叉树的计数

线索化二叉树：线索；中序线索化二叉树

堆：堆的定义；堆的建立；堆的插入与删除；堆的调整算法

树与森林：树的存储表示；森林与二叉树的转换；遍历树；遍历森林

霍夫曼树：路径长度；霍夫曼树；霍夫曼编码

2、教学要求：

了解：树和森林的概念。包括树的定义、树的术语、树的抽象数据类型

掌握：二叉树的概念、性质及二叉树的表示

熟练掌握：二叉树的遍历方法

掌握：线索化二叉树的特性及寻找某结点的前驱和后继的方法

熟练掌握：堆的定义，堆的建立、堆的插入与删除、堆的向上和向下调整等算法以及用来实现优先级队列的方法

掌握：树与森林的实现，重点在用二叉树实现

掌握：森林与二叉树的转换；树的遍历算法

掌握：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法

掌握：霍夫曼树的实现方法、构造霍夫曼编码的方法及带权路径长度的计算

七、集合与搜索 5学时

1、教学内容：

集合及其表示：集合基本概念；以集合为基础的抽象数据类型；用位向量实现集合抽象据类型；用有序链表实现集合的抽象数据类型

并查集：并查集的定义；并查集的实现

简单的搜索结构：搜索的概念；静态搜索结构；顺序搜索；基于有序顺序表的顺序搜索和折半搜索

二叉搜索树：二叉搜索树的定义；二叉搜索树上的搜索；二叉搜索树的插入；二叉搜索树的删除

AVL树：AVL树定义；平衡化旋转；AVL树的插入和删除；AVL树高度

2、教学要求：

掌握：集合的基本概念及其表示方法，包括位数组及有序链表的表示及其相关操作的实现算法

掌握：利用并查集实现集合的方法

熟练掌握：静态搜索表的顺序搜索和折半搜索算法及其性能分析方法

熟练掌握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法

掌握：AVL树的平衡化旋转、构造、插入、删除时的调整方法及其性能分析

八、图 7学时

1、教学内容：

图的基本概念：图的基本概念；图的抽象数据类型

图的存储表示：邻接矩阵；邻接表；邻接多重表

图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；关节点与重连通分量

最小生成树：kruskul算法；prim算法

单源最短路径问题：dijkstra算法

活动网络：AOV网络与拓扑排序；AOE网络与关键路径

2、教学要求：

理解：图的基本概念和图的抽象数据类型

掌握：图的3种存储表示：邻接矩阵、邻接表和邻接多重表。对于前两种，要求掌握典型操作，如构造、求根、找第一个邻接顶点、找下一个邻接顶点等操作的实现算法

熟练掌握：图的两种遍历算法与求解连通性问题的方法。包括深度优先搜索和广度优先搜索算法、求连通分量的方法(不要求算法)

理解：求解关节点及构造重连通图的方法(不要求算法)

掌握：构造最小生成树的Prim算法和Kruskal算法，要求理解算法

理解：如何用Dijkstra方法求解单源最短路径问题(不要求算法)

熟练掌握：活动网络的拓扑排序算法

掌握：求解关键路径的方法

九、排序 7学时

1、教学内容：

概述

插入排序：直接插入排序；折半插入排序；链表插入排序；希尔排序

交换排序：起泡排序；快速排序

选择排序：直接选择排序；锦标赛排序；堆排序

归并排序：归并；迭代的归并排序算法；递归的链表归并排序

基数排序：多关键码排序；链式基数排序

外排序：外排序的基本过程；k路平衡归并；初始归并段的生成；最佳归并树

2、教学要求：

掌握：排序的基本概念和性能分析方法

掌握：插入排序、交换排序、选择排序、归并排序等内排序的方法及其性能分析方法

了解：基数排序方法及其性能分析方法

掌握：多路平衡归并等外排序方法及败者树构造方法

掌握：生成初始归并段及败者树构造方法

掌握：最佳归并树的建立方法

十、索引与散列结构 5学时

1、教学内容：

静态索引结构：线性索引；倒排索引；m路静态查找树

动态索引结构：动态的m路查找树；B树的定义；B树的插入；B树的删除；B+树

散列：散列表与散列方法；散列函数；处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析

2、教学要求：

熟练掌握：静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法

熟练掌握：动态索引结构，包括B树、B+树的搜索和构造方法

熟练掌握：散列法，包括散列函数的构造、解决冲突的方法

第四篇：数据结构课程教学大纲

数据结构课程教学大纲

一、课程基本概况

课程名称：数据结构

课程名称（英文）： Data Structures

课程编号：B09042

课程总学时：60（其中，讲课48，实验12）

课程学分：3

课程分类：专业选修课

开设学期：4

适用专业：计算机网络工程本科

先修课程：集合论，图论，高级语言（结构或记录，指针）

后续课程：数据库，编译原理，操作系统等

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

数据结构是计算机专业的一门核心专业课程，是软件课程中非常重要的一门课程，在整个专业教学中占有十分重要的地位，是一门理论性非常强的课程。通过课堂教学、课外练习和上机实习，使学生了解数据对象的特性，数据组织的基本方法，并初步具备分析和解决现实世界问题在计算机中如何表示和处理的能力以及培养良好的程序设计技能，为后续课程的学习和科研工作的参与打下良好的基础。

三、主要内容、重点及深度

本门课程共60学时，其中理论教学48学时，实验教学12学时。其中，理论教学部分：

第一章

绪论

（一）目的要求

了解数据结构的意义与发展过程、数据结构在计算机科学中的作用、学习本课程的目的、任务及要求。理解数据结构的基本概念；算法设计；掌握算法的时间和空间复杂度。

（二）教学内容 本章知识点：

1.相关的基本概念(掌握)；

2.算法五大要素(掌握)；

3.计算语句频度和估算算法时间复杂度的方法（掌握）。

（三）重点与难点

重点：数据结构的定义；算法的描述方法。

难点：数据结构的定义；算法与程序的区别；时间复杂度及其计算。

第二章

线性表

（一）目的要求

掌握线性表的逻辑结构；线性表的存储结构及操作的实现；理解一元多项式的表示；

（二）教学内容 本章知识点：

1.线性表的逻辑结构(掌握)；2.线性表的存储结构(掌握)；

3.线性表在顺序结构和链式结构上实现基本操作的方法(掌握)；

4.从时间和空间复杂度的角度比较线性表两种存储结构的不同特点及其适用场合(掌握)。

（三）重点与难点

重点：线性表的概念；线性表的顺序存储结构、链式存储结构及其常用算法。难点：链式存储结构及其常用算法；双向循环链表。

第三章 栈和队列

（一）目的要求

掌握栈的定义，表示及实现；表达式求值；栈与递归过程；队列的定义、表示及实现。

（二）教学内容 本章知识点： 1.栈和队列的特点(掌握)；

2.在两种存储结构上栈的基本操作的实现(掌握)； 3.循环队列和链队列的基本运算(熟练掌握)； 4.递归算法执行过程中栈状态的变化过程(掌握)。

（三）重点与难点

重点：堆栈和队列的概念；递归的定义；循环队列和链队列的基本运算。难点：递归的编程实现；循环队列和链队列的基本运算。

第四章 串

（一）目的要求

了解串的逻辑结构，存储结构；掌握串操作的实现(重点难点BF和KMP算法)串的应用。

（二）教学内容 本章知识点：

1.串的七种基本运算的定义（了解）；

2.利用这些基本运算来实现串的其它各种运算的方法(掌握)； 3.在顺序存储结构上实现串的各种操作的方法(掌握)；

4.KMP算法，熟悉NEXT函数和改进NEXT函数的定义和计算(掌握)； 5.串名的存储映象和在堆存储结构实现串操作的方法(理解)。

（三）重点与难点 重点：串定义和存储方法；串的操作 难点：串操作实现方法

第五章 数组和广义表

（一）目的要求

掌握数组的存储结构；稀疏矩阵的表示及操作的实现；广义表的定义和存储结构；广义表的递归算法。

（二）教学内容 本章知识点：1.数组在以行为主的存储结构中的地址计算方法(掌握)； 2.矩阵实现压缩存储时的下标变换(掌握)；

3.理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀疏矩阵时进行运算采用的处理方法(掌握)；

4.广义表的定义及其存储结构，学会广义表的表头，表尾分析方法(掌握)； 5.学习编制广义表的递归算法(掌握)。

（三）重点与难点

重点：多维数组元素存储地址的计算；稀疏矩阵的三元组表示；广义表的存储定义、操作。难点：稀疏矩阵的三元组表示；广义表的存储定义、操作。

第六章 树和二叉树

（一）目的要求

了解树的基本概念；理解二叉树的性质和存储结构；遍历二叉树和线索二叉树；理解树的存储结构和遍历；集合的一种表示方法；掌握哈夫曼树及其应用；

（二）教学内容 本章知识点： 1.二叉树的结构特点(理解)；

2.二叉树的各种存储结构的特点及适用范围(掌握)； 3.按各种次序遍历二叉树的递归和非递归算法(掌握)；

4.二叉树的线索化，在中序线索树上找给定结点的前驱和后继的方法(掌握)； 5.树的各种存储结构及其特点(掌握)； 6.编写树的各种运算的算法(掌握)；

7.建立最优二叉树和哈夫曼编码的方法(掌握)。

（三）重点与难点 重点：二叉树的概念、性质；二叉树的遍历方式；构造二叉排序树。难点：二叉树的遍历方式；二叉排序树的构造方法；二叉树的线索化。

第七章 图

（一）目的要求

理解图的基本概念；图的存储结构；掌握图的遍历及应用{最小生成树，最短路径等}；拓扑排序和关键路径。

（二）教学内容 本章知识点： 1.熟悉图的各种存储结构；

2.了解实际问题与采用何种存储结构和算法有密切联系(掌握)； 3.遍历图的递归和非递归算法(掌握)；

4.应用图的遍历算法求各种简单路径问题（比如，最小生成树、最短路径、拓扑排序、关键路径等）(掌握)。

（三）重点与难点

重点：图的存储结构；图的遍历 难点：图遍历的算法；

第八章

动态存储管理

（一）目的要求

了解边界标识法和伙伴系统；无用单元收集和紧缩；

（二）教学内容 本章知识点：

1.存储器分配策略和算法（了解）；

2.无用单元收集时的标志算法（了解）。

（三）重点与难点

存储器分配策略和算法、无用单元收集时的标志算法

第九章

查找

（一）目的要求

了解静态查找表(顺序表，有序表，索引顺序表)；动态查找表(二叉排序树，平衡二叉树，B-树和B+树)的建立和查找；掌握哈希表的建立，查找及分析；

（二）教学内容 本章知识点：

1.顺序查找、折半查找和索引查找的方法、应用(掌握)；

2.二叉排序树的构造方法(掌握)；

3.二叉平衡树的建立方法(掌握)；

4.B-树，B+树和键树的特点以及它们的建立过程（理解）；

5.哈希表的构造方法(掌握)；

6.按定义计算各种查找方法在等概率情况下查找成功时和失败时的平均查找长度；

7.哈希表在查找不成功时的平均查找长度的计算方法(掌握)。

（三）重点与难点

重点：二叉排序树的构造方法、二叉平衡树的建立方法；哈希表的构造、应用；

难点：二叉排序树的构造及应用；哈希表的构造方法；查找的平均长度。

第十章

内部排序

（一）目的要求

掌握插入排序、交换排序(起泡排序，快速排序)、选择排序(简单选择，树形选择，堆)、归并排序、基数排序等算法。

（二）教学内容 本章知识点：

1.各种排序方法的特点并能灵活应用(掌握)； 2.各种方法的排序过程(掌握)；

3.各种排序方法的时间复杂度分析(掌握)。

（三）重点与难点

重点：各种排序方法的特点及其应用；实现排序的各种算法。难点：各种排序算法的时间复杂度分析。

十一章

外部排序

（一）目的要求

理解外部排序的基本方法；掌握败者树和多路平衡归并的实现；置换--选择排序；最佳归并树。

（二）教学内容 本章知识点：

1.外部排序的两个过程(理解)；

2.外排过程中所需进行外存读/写次数的计算方法(掌握)；

3.败者树的建立过程(掌握)；

4.实现多路归并的算法(掌握)；

5.置换-选择排序的过程(掌握)；

6.最佳归并树的构造方法（熟悉）；

7.按最佳归并树的归并方案进行平衡归并时，外存读/写次数的计算方法(掌握)。

（三）重点与难点

重点：外部排序过程和实现方法；多路并归算法及其实现； 难点：最佳并归树的构造方法及其应用。

实践教学部分：上机实验分4个专题，每个专题可提供2~4个难度不等的题目供选。

实验一

停车场管理系统

（一）实验内容 以栈模拟车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。栈以顺序结构实现，队列以链表结构实现。

（二）实验过程 编程实现实验内容。

（三）实验教学基本要求

通过实例，使学生掌握栈和队列两种特殊的线性结构，掌握栈和队列的特点。实验后学生提交实验报告。

（四）实验设备和材料 计算机。

（五）实验学时 4学时

实验二

教学计划编制问题

（一）实验内容

假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。编制一个教学计划程序。

（二）实验过程编程实现实验内容。

（三）实验教学基本要求

通过实例，使学生熟悉图的各种存储结构的特性，掌握如何应用图结构解决具体问题。实验后学生提交实验报告。

（四）实验设备和材料 计算机。

（五）实验学时 2学时

实验三

最小生成树问题

（一）实验内容

利用克鲁斯卡尔算法求最小生成树。以文本形式输出树中各条边以及他们的权值。

（二）实验过程 编程实现实验内容

（三）实验教学基本要求

通过实例，使学生熟悉图的各种存储结构的特性，掌握如何应用图结构解决具体问题。实验后学生提交实验报告。

（四）实验设备和材料 计算机。

（五）实验学时 2学时

实验四

哈希表设计

（一）实验内容

假设人名为中国人的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。

（二）实验过程 编程实现实验内容

（三）实验教学基本要求 掌握索引技术的使用。

（四）实验设备和材料 计算机

（五）实验学时 4学时

五、课程教学的基本要求和主要环节

本课程可采用课堂讲授、课堂讨论、习题课等进行课堂教学;条件允许可采用CAI、电子教案、幻灯片、参观等进行辅助教学;每章布置3~6道习题以巩固教学;在课程后半程，安排3~4个上机实验，让学生应用数据结构的理论、方法，分组设计几个较大的软件，使理论与实际相结合。

考试采用闭卷方式。总成绩由平时成绩和考试成绩组成。平时成绩占30%，考试成绩占70%。

六、本课程与其它课程的联系与分工

先修课包括：集合论，图论，高级语言（结构或记录，指针）；

后续课包括：数据库，编译原理，操作系统等。

七、建议教材与参考教材

《数据结构》（C语言版）

严蔚敏等

清华大学出版社

1997 《数据结构题集》

严蔚敏等

清华大学出版社

1999

《数据结构习题与解析》

李春葆

清华大学出版社

2004

八、负责人

撰稿人：刘景汇、李玉香

审稿人：

系（院）领导：

第五篇：数据结构课程设计教学大纲

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

Data Structure Course Design

一、课程的性质、教学目的和要求

《数据结构》是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好《数据结构》，必须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同时提高解决计算机应用实际问题的能力。

二、设计要点

1．设计和调试过程要规范化。① 需求分析

将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计），设计或叙述解决此问题的算法，描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。

给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来。

对有些题目提出算法改进方案，比较不同算法的优缺点。

如果程序不能正常运行，写出实现此算法中遇到的问题，和改进方法。②源程序（可以是一组源程序，即详细设计部分）

源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。

程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环。

2．课程设计实习报告的书写格式

① 设计题目（任选其一）②运行环境（软、硬件环境）③算法设计的思想 ④算法的流程图 ⑤算法设计分析 ⑥源代码 ⑦运行结果分析 ⑧收获及体会 3．实施方式

可设2-3人一题，安排在《数据结构》课程开课学期布置题目，然后在期末前两周完成。

三．设计要求

学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。课程设计按照教学要求需要1周时间完成，1周中每天至少要上6-8小时的机来调试C语言设计的程序，总共至少要上机调试程序30小时。为保证质量，需要每个学生将每天的上机调试程序的时间记录下来，作为评判成绩的标准之一。

四．设计题目

1、校园导游程序

[问题描述]

用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。

[基本要求]（1）查询各景点的相关信息；

（2）查询图中任意两个景点间的最短路径。

（3）查询图中任意两个景点间的所有路径。

（4）增加、删除、更新有关景点和道路的信息。

[选作内容]

（1）求多个景点的最佳（最短）游览路径。

（2）区分机动车道和人行道。

（3）实现导游图的仿真界面。

2、算术表达式求值

[问题描述]

一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。

[基本要求]

（1）从键盘读入一个合法的算术表达式，输出正确的结果。

（2）显示输入序列和栈的变化过程。

[选作内容]

扩充运算符集合。

引入变量操作数。

操作数类型扩充到实数。

3、文学研究助手

[问题描述]

文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。[基本要求]

英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。[测试数据]

以你的源程序模拟英文小说，程序语言保留字集作为待统计的词汇集。[实现提示]

设小说中的词汇一律不跨行。这样，每读入一行，就统计每个词在这行中的出现次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次，不必存多个相同的行号。

如果读者希望达到选作部分（1）和（2）所提出的要求，则首先应把KMP算法改写成如下的等价形式，再将它推广到多个模式的情形。[选作内容]

（1）模式匹配要基于KMP算法。

（2）整个统计过程中只对小说文字扫描一遍以提高效率。

（3）假设小说中的每个单词或者从行首开始，或者前置以一个空格符。利用单词匹配特点另写一个高效的统计程序，与KMP算法统计程序进行效率比较。

（4）推广到更一般的模式集匹配问题，并设待查模式串可以跨行（提示：定义操作getachar）

4.迷宫求解

[问题描述]

可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；

[基本要求]

含有两个以上的迷宫图，由用户选择哪一张迷宫图； 实现深度优先、广度优先两种回溯法。

在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、算法的时间复杂度、另外可以提出算法的改进方法；

[实现提示]

可以用一个二维数组存储迷宫图，值为1或者0分别表示通路和不通； 搜索路径可以参考树的深度优先和广度优先算法。

5.括号匹配的检验

[问题描述]

假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即CC或[（[ ] [ ]）]等为正确格式，[（]）或（（（]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列：

[([ ] [ ])]

8

当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“[”只能暂时靠边，而迫切等待与第2个括号相匹配的 第7个括号“）”的出现，类似的，因只等来了第3个括号“[”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了，„„，依次类推。可见这个处理过程正好和栈的特点相吻合。

[基本要求]

设置一个栈，每读入一个括号，若是左括号，则作为一个新的更急迫的期待压入栈中，若是右括号，则或者是和当前栈顶的括号相匹配，或者是不合法的情况，输出“此串括号匹配不合法”。在初始和结束时，栈应该是空的。

[测试数据]

输入 #（[ ]（））#，结果“匹配”

输入 #[（）]#，结果“此串括号匹配不合法”

#为起始和结束标志。

6.停车场管理

[问题描述]

设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。[测试数据]

设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。[基本要求]

以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。[实现提示]

需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。[选作内容]

（1）两个栈共享空间，思考应开辟数组的空间是多少？

（2）汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。

（3）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。

（4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。

7.简单行编辑程序

[问题描述]

文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。

被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的做法既不经济，也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存，称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过320个字符，很少超过80字符。[基本要求]

实现以下4条基本编辑命令：

（1）行插入。格式：i<行号><回车><文本><回车>

将<文本>插入活区中第<行号>行之后

（2）行删除。格式：d<行号1>[□<行号2>]<回车>

删除活区中第<行号1>行（到第<行号2>行）。两种格式的例子是：“d10↙”和“d10□14↙”

（3）活区切换。格式：n<回车>

将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。

（4）活区显示。格式：p<回车>

逐页地（每页20行）显示活区内容，每显示一页之后请用户决定是否继续显示以后各页（如果存在）。印出的每一行要前置以行号和一个空格符，行号固定占4位，增量为1。

各条命令中的行号均须在活区中各行行号范围之内，只有插入命令的行号可以等于活区第一行行号减1，表示插入当前屏幕中第一行之前，否则命令参数非法。[测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据，如首行、尾行。[实现提示]

（1）设活区的大小用行数activemaxlen（可设为100）来描述。考虑到文本文件行长通常为正态分布，且峰值在60到70之间，用320×activemaxlen大小的字符数组实现存储将造成大量浪费。可以以标准行块为单位为各行分配存储，每个标准行块含81个字符。这些行块可以组成一个数组，也可以利用动态 8 链表连接起来。一行文字可能占多个行块。行尾可用一个特殊的ASCII字符（如(012)8）标识。此外，还应记住活区起始行号。行插入将引起随后各行行号的顺序下推。

（2）初始化过程包括：请用户提供输入文件名（空串表示无输入文件）和输出文件名，两者不能相同。然后尽可能多地从输入文件中读入各行，但不超过activemaxlen-x。x的值可以自定，例如20。

（3）在执行行插入命令的过程中，每接收到一行时到要检查活区大小是否已达activemaxlen。如果是，则为了在插入这一行之后仍保持活区大小不超过activemaxlen，应将插入点之前的活区部分中第一行输出到输出文件中；若插入点为第一行之前，则只得将新插入的这一行输出。

（4）若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部，以保持阅读连续性；否则，它意味着结束编辑或开始编辑另一个文件。

（5）可令前三条命令执行后自动调用活区显示。[选作内容]

（1）对于命令格式非法等一切错误作严格检查和适当处理。

（2）加入更复杂的编辑操作，如对某行进行串替换；在活区内进行模式匹配等，格式可以为S<行号>@<串1>@<串2><回车>和m<串><回车>。

8.图遍历的演示

[问题描述]

很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示无向图的遍历操作。[基本要求]

以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。[测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。[实现提示]

设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,„,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。

[选作内容]

（1）借助于栈类型（自己定义和实现）将深度优先遍历用非递归算法实现。

（2）以邻接多重表为存储结构建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树

（3）实现有向图的遍历操作。

9、赫夫曼树的建立

*问题描述：建立建立最优二叉树函数

*要求：可以建立函数输入二叉树，并输出其赫夫曼树

在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；

10、图的建立及输出

*问题描述：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。

11、各种排序

*问题描述：对30000个随机整数，利用插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。

*输入的数据形式为任何一个正整数，大小不限。*输出的形式：数字大小逐个递增的数列?

12、图的遍历

*问题描述：对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索周游。

13、线性表的操作

*问题描述：利作链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。

14、编制一个求解迷宫通路的图形界面演示程序。*问题描述：

1）输入一个任意大小的迷宫，任设起点、终点、障碍，用栈求出一条走出迷宫的路径，并显示在屏幕上。

2）根据用户界面提示，用键盘输入。Home键设置迷宫起点，End键设终点，上下左右箭头键移动，Enter键添加墙，Del键删除墙，完成后按F9键演示，Esc键退出。

3）橙色的实心小圆圈表示起点，绿色实心圆圈表示终点，空心圆圈表示足迹，红色方块表示墙。4）本程序只求出一条成功的通路，但若对求解函数MazePath稍加更改即可求得全部路径。此外，因受图形界面限制，不能保存或载入测试文件（此功能可在Maze_text中实现）。

5）当未输入起点时，消息显示“Error： You must set Startplace.”；未输入终点时，显示“Error： You must set Endplace.” 找到路径时，屏幕显示足迹，并在消息框出现Path found，否则消去足迹，显示Path not found.15．一元稀疏多项式计算器

*问题描述：一元多项式简单计算器的基本功能是：（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列n,c1,e1,c2,e2,„,cn,en，其中n是多项式的项数，ci和ei分别是第I项的系数和指数，序列指指数降序排列；（3）多项式a和b相加，建立多项式a+b；（4）多项式a和b相减，建立多项式a-b。*实现提示：用带头结点的单链表存储多项式，多项式的项数存在头结点。

16．算术表达式求值演示

*问题描述：表达式求值是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。

*基本要求：以字符序列的形式从终端上输入语法正确的、不含变量的整数表达式。利用教材中给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教材例3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。

*实现提示：（1）设置运算栈和运算数栈辅助分析算符优先关系。（2）在输入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以及相应的运算。（3）在识别出运算数的同时，要将其字符序列形式转换成整数形式。

*选作内容：（1）扩充运算符集，如增加乘方、单目减、赋值等运算；（2）运算量可以是变量；（3）运算量可以是实数类型；（4）计数器的功能和仿镇界面。

17．稀疏矩阵运算器

*问题描述：稀疏矩阵是指那些多数元素为0的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本原酸的运算器。

*基本要求：以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结构的矩阵则以通常的阵列形式列出。

*实现提示：（1）首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否匹配。可设矩阵的行数和列数均不超过20。（2）程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教科书中的算法，以便提高计算效率。（3）在用三元组表示稀 疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可以用二维数组存放。18．图书管理

*问题描述：图书管理基本业务活动包括：对一本书的采编入库、清除库存、借阅和归还等等。试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。

*基本要求：（1）每种书的登记内容至少包括书号、书名、作者、现存量和总库存量等五4。（2）作为演示系统，不必使用文件，全部数据可以都在内存存放。但是由于上述四项基本业务活动都是通过书号（即关键字）进行的，所以要用B树对书号尽力索引，以获得高效率。（3）系统应实现的操作及功能定义如下：①采编入库：新购入一种书，经分类和确定书号后登记到图书帐目中去。如果这种书在帐目中已有，则只将总库存量增加。②清除库存：某种书已无保留价值，将它从图书帐目中注销。③某种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限。④归还：注销对借阅者的登记，改变该书的现存量。⑤显示：以凹入表的形式显示B树。这个操作是为了调试和维护的目的而设置的。下列B树的打印格式如下所示：

19、文章编辑

*问题描述：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行。

*要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。

*存储结构使用线性表，分别用几个子函数实现相应的功能；

*输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。

*输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出“全部字母数”、“数字个数”、“空格个数”、“文章总字数”（3）输出删除某一字符串后的文章；

50，52 70，72

20、回文判断

[问题描述]

试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符‘&’，且序列2 是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。[实现提示]

首先，序列1进栈，然后序列1出栈并与序列2比较。

21、建立二叉树，层序、先序遍历（用递归或非递归的方法都可以）*问题描述：

要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；

五、参考书目

《数据结构 C语言》 严蔚敏 清华大学出版社 《c语言程序设计》 谭浩强 清华大学出版社 《数据结构》 高教出版社

《数据结构习题》 李春保 清华大学出版社 《数据结构习题》 严蔚敏 清华大学出版社 《c语言与数据结构》 王立柱 清华大学出版社

《数据结构（C语言篇）习题与解析》李春葆 清华大学出版社

计算机软件教研室 2004年1月7日