《数据结构》教学大纲
课程编码：1512105703
课程名称：数据结构
学时/学分：48/3
先修课程：《高等代数》、《离散数学》、《C语言程序设计》
适用专业：信息与计算科学
开课教研室：信息与计算科学教研室
一、课程的性质和任务
1．课程性质：该课程是信息与计算科学专业的一门专业必修课。
2．课程任务：通过本课程的学习，应使学生掌握线性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法；了解各种抽象数据类型的性质；掌握处理各种抽象数据类型的基本算法；重点掌握各种典型数据结构的应用；了解各种典型排序和查算法的性能和设计方法；重点掌握程序设计的基本原理
和方法；初步掌握算法的时间分析和空间分析的技术。
学生通过学习该课程后能够运用数据结构的思想，针对不同数据对象的特性，能够选择适当的数据结构和存储结构以及相应的算法，解决实际的问题。学生通过学习该课程后能够应用一门程序设计语言进行各种应用系统的设计、开发及维护。
二、课程教学基本要求
学生通过学习该课程后能够针对不同数据对象的特性，选择适当的数据结构和存储结构以及相应的算法，去解决实际应用问题。学生通过学习该课程后能够应用一门程序设计语言进行各种应用系统的设计、开发及维护，为编译技术、操作系统和数据库等后续课程的学习以及为应用软件特别是非数值应用软件的开发打下良好的理论基础和实践基础。
本课程共计学时：理论学时48。
成绩考核形式：末考成绩（闭卷考查）（70%）＋平时成绩（平时测验、作业、课堂提问、课堂讨论等）（30％)。成绩评定采用百分制，60分为及格。
三、课程教学内容
第一章    绪  论
1.教学基本要求
了解数据的逻辑结构和物理结构；了解算法对于程序设计的重要性；掌握算法时间复杂度的分析方法 。
2.要求学生掌握的基本概念、理论、技能
通过本章教学使学生了解数据结构的基本概念，主要包括数据、数据元素、数据项、数据结构、四种逻辑结构、四种存储结构、时间复杂度等基本概念；掌握时间复杂度和空间复杂度来评价算法效率的基本分析方法。
3.教学重点和难点
教学重点是数据结构的基本概念。教学难点是抽象数据类型和算法分析技术。
4.教学内容
（1）什么是数据结构
主要知识点：从数据结构实验演示认识数据结构；数据结构研究的内容。
（2）数据的逻辑结构
主要知识点：.基本概念：数据、数据元素、数据项、数据对象、数据的逻辑结构。
（3）数据的存储结构
主要知识点：顺序存储；链式存储；索引存储；散列存储。
（4）算法和算法分析
主要知识点：算法特性；算法的效率；算法效率的评价。
第二章    线性表
1.教学基本要求
掌握线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。
2.要求学生掌握的基本概念、理论、技能
通过本章的学习，掌握线性表的逻辑结构特征，线性表上定义的基本运算，掌握顺序表的定义及特点，顺序表上的插入删除操作及其平均时间性能；掌握单链表、双链表、循环链表链式存储方式上的区别、
基本运算算法和平均时间性能分析。通过本章学习，使学生能够针对具体应用问题的要求和性质，选择合适的存诸结构设计出相应的有效算法，解决与线性表相关的实际问题。
3.教学重点和难点
教学重点是顺序表的插入运算、删除运算，链表的创建、插入、删除运算。教学难点是双链表插入、删除运算的算法；利用链表结构的特点设计算法。
二叉树定义
4.教学内容
（1）线性表的定义与运算
主要知识点：线性表的定义；线性表的基本操作。
（2）线性表的顺序存储
主要知识点：线性表的顺序存储特点；顺序表结构体类型的定义；顺序表上基本运算的实现：顺序表的空间分配及初始化、插入、删除等基本运算及其平均时间性能分析。
（3）线性表的链式存储结构
主要知识点：线性表的链式存储的特点；线性表的链式存储的基本运算：头部尾部建立线性链表、带头指针和不带头指针求表长、插入、删除等基本运算；循环链表特点及基本运算、尾指针取代头指针；存储密度；双链表的特点及基本运算。
第三章    栈
1.教学基本要求
掌握栈的逻辑结构以及在两种存储结构上如何实现栈的基本运算。
2.要求学生掌握的基本概念、理论、技能
通过本章的学习，掌握.栈的逻辑结构特点，栈与线性表的异同。顺序栈和链栈上实现的入栈、出栈等基本算法。栈的"上溢"和"下溢"的概念及其判别条件，利用栈设计算法解决简单的应用问题。
3.教学重点和难点
教学重点是栈的定义和特点、栈的基本运算和算法以及栈的典型应用。教学难点是后缀表达式的算法、数制的换算、利用本章的基本知识设计相关的应用问题
4.教学内容
（1）栈的定义与运算
主要知识点：栈的定义；栈的特性；栈的应用实例。
（2）栈的存储和实现
主要知识点：顺序栈的特点、顺序栈结构体类型的定义、顺序栈的基本运算；链栈的特点、链栈结构体类型的定义、链栈的基本运算。
（3）栈的应用举例
主要知识点：数制转换；括号匹配；表达式求值；子程序调用；递归调用。
第四章    队列
1.教学基本要求
掌握队列的逻辑结构以及在两种存储结构上如何实现队列的基本运算。
2.要求学生掌握的基本概念、理论、技能
通过本章的学习，掌握队列的逻辑结构特点，队列与线性表的异同，队列的"上溢"和"下溢"的概念及其判别条件，使用数组实现的循环队列取代普通的顺序队列的原因，循环队列中对边界条件的处理方法，利用队列设计算法解决简单的应用问题。
3.教学重点和难点
教学重点是队列的定义和特点、队列的基本运算和算法以及队列的典型应用。教学难点
是循环队列的特点及判断溢出的条件；利用队列的特点设计相关的应用问题。
4.教学内容
（1）队列的定义与运算
主要知识点：队列的定义；队列的特性；队列的应用实例。
（2）队列的存储实现及运算的实现
主要知识点：顺序队列的特点、顺序队列结构体类型的定义、顺序队列的基本运算；循环队列的特点、循环队列结构体类型的定义、循环队列的基本运算；链队列的特点、链队列结构体类型的定义、链队列的基本运算。
（3）队列的应用举例
主要知识点：队列在输入、输出管理中的应用；对CPU的分配管理；优先队列。
第五章    串
1.教学基本要求
掌握串的逻辑结构、存储结构及其串上的基本运算，C语言及其它高级语言均已具备了较强的串处理功能，掌握串上实现的模式匹配算法。
2.要求学生掌握的基本概念、理论、技能
通过本章的学习，掌握串的有关概念及基本运算。串与线性表的关系，掌握串的两种存储表示。串上实现的模式匹配算法及其时间性能分析，使用高级程序设计语言提供的串操作函数构造与串相关的算法解决简单的应用问题。
3.教学重点和难点
教学重点是串的有关概念和术语、串的基本运算、串的存储方法和串的模式匹配运算算法。教学难点是串的模式匹配运算算法。
4.教学内容
（1）串的定义
主要知识点：串的定义；串的相关术语：长度、空串、空格串、串相等、子串、主串、模式匹配；串的应用；串的输入输出；串的基本运算。
（2）串的表示和实现
主要知识点：定长顺序存储描述、存储方式；链接存储的描述；串的存储密度；大结点结构；串的堆分配存储结构；堆分配存储的方法；带长度索引表的描述。
（3）串的基本运算
主要知识点：串长度、求子串、串连接、串比较、插入子串、删除子串、模式匹配基本算法。
第六章    多维数组和广义表
1.教学基本要求
掌握多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，
2.要求学生掌握的基本概念、理论、技能
通过本章的学习，掌握多维数组的顺序存储结构及地址计算方式，多维数组的存储方式、特殊矩阵的压缩存储方式，稀疏矩阵的三元组表表示方法及有关算法，广义表的定义及其求表头和表尾的运算。
3.教学重点和难点
教学重点是多维数组的逻辑结构和存储结构，特殊矩阵的压缩存储，稀疏矩阵的三元组存储，广义表的逻辑结构、存储结构。教学难点是十字链表存储。
4.教学内容
（1）多维数组
主要知识点：多维数组的逻辑结构；多维数组的存储结构。
（2）特殊矩阵的压缩存储
主要知识点：对称矩阵的特点及压缩存储方式；三角矩阵的特点及压缩存储方式。
（3）稀疏矩阵
主要知识点：稀疏矩阵的三元组存储；稀疏矩阵的带行指针的链表存储；稀疏矩阵的十字链表存储。
（4）广义表
主要知识点：广义表的定义、性质；广义表的首尾存储法。
第七章    树和二叉树
1.教学基本要求
掌握二叉树的定义、性质、存储结构、遍历、线索化；树的定义、存储结构、遍历、树、森林与二叉树的转换；哈夫曼树及哈夫曼编码等内容，使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。
2.要求学生掌握的基本概念、理论、技能
通过本章的学习，掌握树的逻辑结构特征，二叉树的递归定义及树与二叉树的差别，二叉树的性质，二叉树的两种存储方法、特点及适用范围；二叉树的三种遍历算法，理解其执行过程，以遍历算法为基础，设计有关算法解决简单的应用问题；二叉树线索化的目的及实质，中序线索树中查给定结点的中序前趋和中序后继的方法；树和森林与二叉树之间的转换方法，树的各种存储结构及其特点。最优二叉树和最优前缀码的概念及特点，哈夫曼算法的思想。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。