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

1、应用数据结构教学大纲课程名称：应用数据结构Applied Data Structure学时/学分：64/4（其中含实验16学时）先修课程：离散数学，C语言适用专业：信息管理与信息系统开课学院（部）、系(教研室)：管理学院信息管理与信息系统系一、课程的性质与任务1、开设目的：应用数据结构课程是高等学校计算机学科相关专业学生的一门必修的重要专业基础理论课，是后续专业课程学习的基础，它是为培养我国社会主义现代化建设所需要的高质量专门人才服务的。它的目的是向学生介绍计算机程序设计的算法基础，使学生进一步巩固C语言程序设计的基本方法与编程技巧，培养学生应用计算机解决和处理实际问题的思维方法与基本能力，为

2、深入学习和培养编程能力打下基础。2、基本要求：数据结构课程是一门实践性非常强的课程，要求学生在学习过程中认真掌握基础知识和基本理论，注重基本技能训练，重视上机实践环节。通过该课程学习达到以下要求：熟悉线性和非线性数据结构的基本概念；掌握基于各种结构的算法设计与实现方法；掌握递归函数的设计方法及编程技巧，能正确使用C语言编写较为复杂的程序；掌握调试程序的基本方法；启发学生主动将计算机引入到其他专业课，让程序设计真正走向实用 。3、本课程教学中应注意的问题：课程重点是数据结构中所涉及的线性和非线性结构，基于树和图的优化算法，查找和排序的实现原理。通过学习并掌握这些知识，学生就可以设计出较为复杂的C

3、语言算法程序。课程难点是树和图部分。由于非线性结构需要使用指针和结构体相结合，对于初学者而言存在理解上的困难，需要经过大量的练习来强化理解。在传授知识的同时，要通过各个教学环节逐步培养学生具有抽象思维能力、逻辑推理能力、程序阅读理解能力和自学能力，还要特别注意培养学生具有比较熟练的编程能力和综合运用所学知识去分析和解决问题的能力。理论教学使用多媒体教室，要安排必要的实验教学环节。二、课程的教学内容、基本要求及学时分配（一）教学内容1. 绪论数据结构：数据，数据类型，数据元素，抽象数据类型，抽象数据类型；算法分析：算法，时间复杂度，空间复杂度。2. 线性表线性表：结点，前件，后件，表长；表的操作

4、：初始化（建表），求表长，输出表元素，插入，删除；顺序表：顺序存储结构，向量，顺序表的操作；链表：指针，动态变量，堆，指针变量与动态变量的关系和区别，指针场（域），数据场（域），单链表的构造及其操作，循环链表与Josephus问题，双链表，链表的应用。3. 栈和队列栈：栈顶，栈底，进栈，出栈，栈指针，出栈序列的讨论，栈上溢的克服，栈的应用（表达式求值）；队列：队首，队尾，队首指针，队尾指针，循环队列，进出队操作，队列的应用（机场事件模拟）。4. 串概念：定义，串长，子串，串的存储；串操作：赋值，串比较，求串长，串连接，求子串，串置换，模式匹配；串的模式匹配：简单匹配（有回溯算法），KMP算法（

5、无回溯算法）。5. 数组和广义表数组：定义，顺序表示和实现，n维数组的寻址公式；矩阵：一维数组的压缩存储，特殊矩阵（对称阵和三角阵）的压缩存储，对角矩阵；稀疏矩阵的压缩存储：稀疏因子，三元组表，十字链表；广义表：定义，存储结构，运算。6. 递归递归：定义，模型，用法，调用原理，算法设计。7. 树树的概念：递归与非递归定义，子树，叶子，内结点，结点的度，树的度，树的深度（高度），完全树，满树，有序树，森林，双亲，孩子，兄弟，堂兄弟，祖先，子孙，树的各种表示（嵌套集合、凹入、广义表、层号）；树的存储方法：双亲数组法，孩子表示法，双亲孩子法，孩子兄弟法；二叉树：定义，表示，满二叉树，完全二叉树，二叉

6、树的顺序和链式存储；遍历二叉树：前序遍历，中序遍历，后序遍历；二叉树的应用：恢复二叉树，遍历表达式树，二叉树与森林的转换；线索二叉树：定义，线索化，中序遍历线索二叉树的算法，构造线索二叉排序树的算法；Huffman树：定义，最优树，路径，路径长度，叶子树，带权路径长度，Huffman算法，Huffman编码。8. 图概念：定义，边，有向边（图），无向边（图），无向完全图，子图，路径，回路，路径长度，简单路径，简单回路，连通图，连通分量，可达，强连通图，强连通分量，度，入度，出度，有根图，树图，网络；图的表示：有序数偶对，图形，邻接矩阵，带权的邻接矩阵；图的存储：标准形式，邻接矩阵，邻接表；图的

7、遍历：深度优先搜索，广度优先搜索；图的连通性：生成树，最小生成树及其Prim算法和Kruskal算法；图的应用：最短路径问题，单源最短路径问题及Dijkstra算法，每对顶点间的最短路径问题及Floyd算法，拓扑排序，AOE网与关键路径。9. 查找概念：查找表，关键字，查找，平均查找长度；静态查找表：顺序查找，折半查找，分块查找；动态查找表：二叉排序树，平衡二叉树，B-树，B+树；Hash查找：Hash函数，Hash表，冲突，Hash函数的构造方法（直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法），处理冲突的方法（开放定址法、再哈希法、链地址法、公共溢出区法），性能分析。10

8、. 内排序排序的基本概念：分类，稳定排序，内排序和外排序；插入排序：直接插入排序，折半插入排序，Shell排序；交换排序：起泡排序，快速排序，枢轴；选择排序：简单选择排序，树形选择排序，关系传递原理，堆的构造和堆排序；归并排序，基数排序；Hash排序：单调递增Hash排序、Super-Hash排序。11. 外排序概述，磁盘排序，磁带排序。12. 文件文件：概念，逻辑结构，存储结构；顺序文件，索引文件，Hash文件，多关键字文件。（二）教学要求1.正确理解下列基本概念和它们之间的内在联系：数据结构，顺序表，链表，栈，队列，串，数组，稀疏矩阵，广义表，二叉树，二叉树的遍历，图，图的遍历，静态查找，

9、动态查找，插入排序，交换排序，选择排序，归并排序，Hash排序，基数排序。2.正确理解下列基本定理和公式并能正确运用：树的结点与边的数量关系定理，二叉树的五个性质定理，图的顶点与路径关系定理，各查找算法的平均查找长度计算公式，各排序算法的时间复杂度。3.熟练运用下列法则和方法：顺序表的数据移动算法，单链表的结点插入与删除算法，双链表的节点插入与删除算法，栈的顺序表实现算法，队列的顺序表和链表实现算法，二叉树的前序和中序遍历算法，Huffman编码的构造过程，图的深度和广度优先遍历的过程，针对不同的图的应用问题使用相应的算法进行手工求解，静态查找的算法，动态查找的实现过程，根据给定的Hash函数

10、构造Hash表并计算查找成功与不成功的平均查找长度，各排序算法的实现原理。4.会运用C语言编写一些简单的算法并能阅读理解教材中所有算法的C源程序代码。5.在课程设计中能针对具体问题运用C语言编写一些较复杂的程序。（三）学时分配本课程理论教学48学时，实验16学时，共计64学时。 教学环节课程内容 学时讲 课实 验小 计绪论22线性表426栈和队列426串22数组和广义表325递归11树和二叉树628图628查找（含习题课）8210内排序628外排序22文件224习题课22合 计 =SUM(ABOVE) 481664（四）课程内容的重点、难点1. 绪论重点：数据结构的逻辑结构、存储结构、数据运算

11、三方面的概念及相互关系；算法时间复杂度分析。难点：分析算法的时间复杂度。2. 线性表重点：线性表的定义和特点，线性表的存储结构；顺序表和链表的组织方法和算法设计。难点：单链表和双链表上的各种算法设计。3. 栈和队列重点：栈和队列的特点，顺序栈和链栈上基本运算的实现算法；顺序队列、环形队列和链队上的基本运算算法。难点：灵活运用栈和队列设计解决应用问题的算法。4. 串重点：串的顺序存储方法和串的链式存储方法，以及串基本运算算法的实现。难点：模式匹配的KMP算法。5. 数组和广义表重点：数组的复杂算法设计，广义表的算法设计。难点：稀疏矩阵的各种存储结构以及基本运算的实现算法，广义表的算法设计。6.

12、递归重点：递归模型、递归算法的执行过程和递归设计思想。难点：将递归算法转化为非递归算法。7. 树重点：二叉树的性质、二叉树的遍历（二叉树各种遍历方法及它们所确定的序列之间的关系）、二叉树的线索化方法，构造Huffman树。难点：二叉树上各种算法，特别是递归算法的设计。8. 图重点：图的各种存储结构和遍历算法（递归和非递归算法）设计，构造最小生成树，生成最短路径，生成图的关键路径，拓扑排序的应用。难点：图的遍历算法和图的各种复杂算法的设计。9. 查找重点：各种顺序表和树表的查找算法和性能分析，构造Hash表、冲突处理和性能分析。难点：各种查找算法设计和性能分析。10. 内排序重点：各种排序算法的

13、性能特点、各种排序算法的比较和选择。难点：复杂排序算法设计。11. 外排序重点：置换-选择排序生成初始归并段，利用败者树实现多路平衡归并、最佳归并树。难点：置换-选择排序生成初始归并段，利用败者树实现多路平衡归并、最佳归并树。12. 文件重点：各类文件（顺序文件、索引文件、Hash文件和多关键字文件）的特点和构造方法。难点：各类文件上文件操作的实现。三、课程改革与特色本门课程使用了多媒体教学，可选择采用双语形式或中文进行讲授。考虑到本课程的主要目的不是要求学生死记硬背算法和原理，而是要求灵活掌握算法的核心思想，因此摒弃了以往的划分重点、闭卷考试、编程为主的思路，采取了开卷考试，侧重基本原理和算

14、法，全面覆盖课程内容的考试改革，提倡学生将所领会的算法在课程设计中充分运用并体现出来。本门课程的多媒体演示课件提供了中文和英文版本，同时彻底改变了过去单纯文本演示的弊病，大量采用了动画技术，使得算法中的难点能够通过动态演示与声光效果结合的方式以最浅显易懂的形式展现在学生面前，并通过不定期在网上公布修订版本的方法免费提供给学生下载，使得学生能在课后自行深入学习和理解。此外，为加强课堂互动和深化学生对基本概念和基本原理的理解，本课程采用有奖问答形式的课堂练习并提供相应的互动教学课件，以激发学生的参与热情和学习兴趣。四、推荐教材及参考书推荐教材：中文版：李春葆等，数据结构教程（第3版），清华大学出版

15、社，2009年3月第3版；李春葆等，数据结构教程（第3版）上机实验指导，清华大学出版社，2009年3月第1版；英文版：Mark Allen Weiss，陈越改编，Data Structures and Algorithm Analysis in C (Second Edition)，Pearson Education Asia Ltd授权人民邮电出版社，2005年8月第1版参考书：1李春葆等，数据结构教程（第3版）学习指导，清华大学出版社，2009年3月第3版；2李春葆，数据结构习题与解析（A级），清华大学出版社，2006年10月第3版；3李春葆，喻丹丹，数据结构习题与解析（B级），清华大学出

16、版社，2006年11月第3版；4严蔚敏，吴伟民，数据结构（C语言版），清华大学出版社，2007年4月5Robert Sedgewick, Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, Third Edition，Pearson Education Asia Ltd.授权机械工业出版社，2006年9月第1版6Robert Sedgewick, Algorithms in C, Part 5: Graph Algorithms, Third Edition，Pearson Educati

17、on Asia Ltd.授权机械工业出版社，2006年9月第1版应用数据结构实验教学大纲实验总学时数：16适应专业：信息管理与信息系统承担实验室：管理学院实验中心一、实验教学的目的和任务1实验教学的目的 本课程的教学要求之一是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，其重要程度绝不亚于知识传授。实验的作用在于帮助学生深入理解教材内容，巩固基本概念，促使学生在动手过程中进一步体会C语言中数据结构的运用技巧，并锻炼学生在调试过程中分析和发现问题的能力。2实验教学的要求学生应掌握C语言基本编程能力并运用数据结构的原理和方法解决具体问题。除按时上机外，学生应具备构造算法并用程序实现的能力

18、；在程序调试过程中，学生应能正确解读程序的错误提示并找到有效的解决办法。此外，规范书写算法也是一个值得高度重视的问题，教师有责任在教学过程中提醒学生，避免形成一系列难以纠正且贻害无穷的程序设计坏习惯。此外，本门课程设计的算法比较多，要求教师熟练掌握C语言和数据结构各类算法，并能准确理解和回答学生提出的编程问题。二、实验项目及学时分配序号实 验 项 目 名 称实验学时实验类型开出要求1线性表2验证必做2栈和队列2验证必做3数组和广义表2验证必做4树和二叉树2演示必做5图2验证必做6查找2验证必做7内排序2演示必做8综合实验2综合必做合 计16三、每项实验的内容和要求实验设备及耗材：所有实验用计算

19、机由院系计算机中心或机房提供上机场所和硬件设施，软件配置每台电脑上必须安装有Turbo C 2.0运行环境。所有实验均无耗材需求。实验一 线性表1实验内容：实现顺序表各种基本运算的算法。实现单链表各种基本运算的算法。实现双链表各种基本运算的算法。实现循环单链表各种基本运算的算法。实现循环双链表各种基本运算的算法。2实验要求：参见实验指导书。实验二 栈和队列1实验内容：实现顺序栈各种基本运算的算法。实现链栈各种基本运算的算法。实现顺序队列各种基本运算的算法。实现链队各种基本运算的算法。停车场管理程序2实验要求：参见实验指导书。实验三 数组和广义表1实验内容：求55阶螺旋方阵。求一个矩阵的马鞍点。求两个对称矩阵之和与乘积。实现稀疏矩阵（采用三元组表示）的基本运算。实现广义表的基本运算。2实验要求：参见实验指导书。实验四 树和二叉树1实验内容：实现二叉树各种基本运算的算法。实现二叉树各种遍历算法。求二叉树中从根结点到叶子结点的路径。由遍历序列构造二叉树。实现中序线索化二叉树。构造Huffman树。2实验要求：参见实验指导书。实验五 图1实验内容：实现图的邻接矩阵和邻接表存储。实现图的遍历算法。求有向图的简单路径