《数据结构大纲》由会员分享，可在线阅读，更多相关《数据结构大纲（20页珍藏版）》请在金锄头文库上搜索。
1、数据结构Data Structur）es课程基本信息课程编号：06021002 课程性质：非独立设课课程总学时：48 课程属性:专业基础课实验学时：8开设学期：第4 学期适用专业：计算机相关专业先修课程：离散数学、c语言程序设计主撰人：惠向晖审核人：丁立大纲制定（修订）日期： 2012.5一、课程的性质、地位和任务该课是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。 本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用 的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的 学习以及软件设计水平的提高打下
2、良好的基础。本课程的任务是：在基础方面，要求学生掌握常 用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上 实现不同的运算，并对算法设计的方式和技巧有所体会。二、课程教学的基本要求1、理论知识方面：要求学生掌握常用数据结构的基本概念及其不同的实现方法2、实验技能方面：通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。三、理论教学内容及学时分配（40学时）第一章 概论学时数： 4教学目的：本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。教学重点和
3、难点：数据、数据元素、数据项；逻辑结构和数据结构在概念上的联系与区别；运算的概念；存储结构及其三个组成部分；抽象数据类型和数据抽象；评价算法优劣的标准及方法。 主要教学内容及要求：了解数据、数据元素和数据项的概念及其相互间的关系；理解数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实 现；理解抽象数据类型的概念；掌握进行简单算法分析的方法。第二章 线性表学时数：8教学目的：本章目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本 运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应 用问题的要求和性质，选择合适的存
4、储结构设计出相应的有效算法，解决与线性表相关的实际问 题。教学重点和难点：线性表的定义及逻辑上的特点；顺序表上插入、删除和定位运算的实现；单链表的结构特点及类型说明；头指针和头结点的作用及区别；指针操作；定位、删除、插入运算在单链表上的实现；循环链表、双链表的结构特点；循环链表、双链表上删除与插入运算的实现。主要教学内容及要求：理解线性表的定义及其运算；理解顺序表和链表的定义、组织形式、结构特征和类型说明；掌握在这两种表上实现的插入、删除和按值查找的算法；了解循环链表、双（循环）链表的结构特点和在其上施加的插入、删除等操作。第三章 栈和队列学时数：6教学目的：本章目的是介绍栈和队列的逻辑结构定
5、义及在两种存储结构上如何实现栈和队列的基本运 算。要求在掌握栈和队列的特点的基础上，知道在什么样的情况下能够使用栈或队列。 教学重点和难点：栈的定义及逻辑特点；栈上的基本运算；栈的顺序存储结构及运算实现；栈的链式存储结构；入栈、出栈等运算在链栈上的实现；队列的定义及逻辑特点；队列上的基本运算；队列的顺序存储结构及其上的运算实现；队列的链式存储结构；入队、出队等运算在链队列上的实现。主要教学内容及要求：理解栈的定义、特征及在其上所定义的基本运算；掌握在两种存储结构上对栈所施加的基本运算的实现；理解队列的定义、特征及在其上所定义的基本运算；掌握在两种存储结构上对队列所施加的基本运算的实现。第四章
6、串学时数：4教学目的：本章目的是介绍串的逻辑结构、存储结构及其串上的基本运算。 教学重点和难点：串的基本概念、基本运算；串的两种存储方式；串的模式匹配算法。主要教学内容及要求：了解串的定义；理解和领会串的存储方式；掌握常用的串运算。学时数：4第五章 数组、特殊矩阵和广义表教学目的： 本章目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方 法及广义表的概念，要求学生熟悉这些内容。教学重点和难点：多维数组的逻辑结构； 多维数组的两种顺序存储方式； 计算给定元素在存储区中的地址；对称矩阵、三角矩阵的压缩存储方式；计算给定元素在存储区中的地址；稀疏矩阵的三元组表表示方法。主要
7、教学内容及要求：理解多维数组的结构特点和在内存中的两种顺序存储方式；理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算； 掌握稀疏矩阵的压缩方式和简单运算；了解广义表的定义和基本运算。第六章 树和二叉树学时数：12教学目的： 本章目的是介绍二叉树的定义、性质、存储结构、遍历、线索化，树的定义、存储结构、遍 历、树和森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。教学重点和难点：二叉树的定义、逻辑特点及五种基本形态；二叉树的五个性质；在二叉树上定义的基本运算；二叉树的链式存储结构及其类型说明；二叉树的顺序存储结构及其类型说明；二叉树链式存储结构的组织方式；二叉树的三种遍历方法及其算法；以遍历为基础
8、在二叉树上实现的几种运算； 哈夫曼树和哈夫曼算法。主要教学内容及要求：深刻理解二叉树和树的定义、性质及其存储方法；熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义；理解并掌握二叉树的三种遍历算法；掌握二叉树的线索化方法；熟练掌握二叉树的遍历方法解决相关的应用问题。熟练掌握森林与二叉树间的相互转换；理解树和森林的遍历；了解树的简单应用。第七章 图学时数：8教学目的：本章目的是介绍图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法。 教学重点和难点：图的定义、术语及其含义；各种图的邻接矩阵表示法及其类型说明；图的按深度优先搜索遍历方法和按广度优先搜索遍历方法；生成树和最小生成树的概
9、念；由 Prim 算法思想构造最小生成树按 Prim 算法思想；拓扑序列和拓扑排序的概念；拓扑排序的算法思想；关键路径的算法思想；最短路径的算法思想。主要教学内容及要求：理解图的基本概念及术语；掌握图的两种存储结构（邻接矩阵和邻接表）的表示方法；熟练掌握图的两种遍历（深度优先搜索遍历和广度优先搜索遍历）的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解最小生成树的概念，能按Prim算法构造最小生成树；理解并掌握拓扑排序、关键路径、最短路径的算法思想。第八章 查找学时数：8教学目的：本章目的是介绍线性表、树和散列表的查找方法、算法实现以及各种查找方法的时间性能（平 均查
10、找长度）分析。教学重点和难点：查找表的基本概念及查找原理；查找表的顺序存储结构、顺序表及其类型说明；查找运算在查找表和有序表上的实现；二叉排序树的定义、性质及各结点间的键值关系；二叉排序树的查找算法和基本思想；平衡二叉排序树的概念；散列表及散列存储和散列查找的基本思想；各种散列表的组织、解决冲突的方法；在散列表上实现查找、插入和删除运算的算法。主要教学内容及要求：了解查找的基本思想及查找成功和不成功的概念；掌握在顺序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相应的平均查 找长度；理解并掌握二叉排序树、平衡二叉树的各种算法。第九章 排序学时数：6教学目的：本章目的是介绍五类内部排序
11、方法的基本思想、排序过程、算法实现、时间和空间性能的分 析以及各种排序方法的比较和选择。教学重点和难点：排序基本概念及内排序和外排序、稳定排序和非稳定排序的区别；插入排序的基本思想、基本步骤和算法；冒泡排序的基本思想、基本步骤、算法和算法分析；快速排序的基本思想、基本步骤和算法；直接选择排序的基本思想、基本步骤、算法和算法分析；堆排序的基本思想、基本步骤和算法；归并排序的思想；两个有序文件合并的方法和算法；二路归并排序的算法和时空性能。主要教学内容及要求：理解排序的基本思想和基本概念；理解并掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、步骤、算法及时空效
12、率分析；了解外排序的定义和基本方法。四、实验教学内容及学时分配（8学时）序号060210021060210022060210023060210024实验名称线性表栈、队列与递归算法设计树、图及其应用查找和排序学时类型综合性基础性综合性综合性实验要求必做必做必做必做五、考试方法考试方式为闭卷、笔试。总成绩计算时办法：平时成绩占20-30%，期末考试成绩占 70-80%六、使用教材1、选用教材：（1）理论课教材：数据结构，严蔚敏 吴伟民编著，清华大学出版社，2010（2）实验课教材：数据结构习题解答与实验指导，罗文劼 王苗 石强编著，中国铁道出版社，20082、参考书：（1）数据结构. 刘振鹏、张
13、晓莉、郝杰. 北京：中国铁道出版社，2005（2）数据结构. 黄刘生 唐策善 著. 中国科学技术大学出版社，2009（3）数据结构. 刘大有 著. 高等教育出版社，2002（4）数据结构（面向对象语言描述）. 朱振元等 著. 清华大学出版社，2004（5）数据结构（C语言版）实践教程.胡元义等著.西安电子科技大学出版社，2008（6）数据结构一C语言描述耿国华等.西安：西安电子科技大学出版社.20023、推荐网站：（ 1）河南农业大学精品课程展示， http:/202.196.80.251:81/data/why/jpkczhanshi/数据结构课程实验教学大纲Data Structures
14、Course Experi）ment课程性质： 非独立设课承担实验室： 软件实验室大纲制定（修订）日期： 2012.5课程编号： 06021002课程总学时：8课程属性: 专业基础课开设学期： 第 4学期适用专业： 计算机相关专业先修课程：离散数学、C语言程序设计主撰人： 惠向晖审核人： 丁立（一）实验课程简介“数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键 性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介 绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后 续课程的学习以及软件设计水平的提高打下良好的基础。（二）实验教学目的和基本要求不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容 和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其 出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基 础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训
