《数据结构》课程教学大纲课程编号：课程名称：数据结构英文名称：DataStructure课程类型：专业必修课总学时：54理论学时：36实验学时：18适用对象：信息管理与信息系统专业（卫生信息方向）本科课程简介：数据结构主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。主要有三个方面：数据的逻辑结构：数据的物理存储结构：对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构及该算法的时、空复杂度分析。用计算机来解决任何问题时，都要进行数据表示及数据处理，而数据表示以及数据处理正是数据结构课程的主要研究对象。通过本课程的学习，使学生透彻地理解数据结构的逻辑结构和物理结构、基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为后续课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，《数据结构》课程在计算机应用中具有举足轻重的作用。学习本课程前，学生应具备计算机的基本操作能力，并掌握至少一门计算机高级编程语言。一、课程性质、自的和任务性质：本课程是卫生信息管理专业学生的一门必修课，主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。目的：在基础理论方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法：在理论应用方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计和技巧有所体会。任务：总学时54学时，其中理论讲授24学时，实验学时18学时。将系统学习数据结构方面的知识，提高本专业学生在应用数据结构解决实际问题中的能力。二、教学基本要求通过本课程的学习，学生应能达到下列要求：（1）了解数据结构及其分类、数据结构与算法的密切关系。(2）掌握各种基本数据结构及其操作、学会根据实际问题的要求选择适当的数据结构。(3）掌握设计算法的步骤和算法分析方法。(4)掌握线性表、数组、栈、队列以及树和图的定义、存储结构及基本算法的实现。(5）掌握在顺序表、有序表、散列表等上的查找算法。(6）掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序的基本思想及算法；了解其算法时、空复杂度的分析。1
1 《数据结构》课程教学大纲 课程编号: 课程名称：数据结构 英文名称：Data Structure 课程类型：专业必修课 总学时：54 理论学时：36 实验学时：18 适用对象：信息管理与信息系统专业（卫生信息方向）本科 课程简介： 数据结构主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。主要有三 个方面：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的 设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构及该算法的时、空复杂 度分析。 用计算机来解决任何问题时，都要进行数据表示及数据处理，而数据表示以及数据处理 正是数据结构课程的主要研究对象。通过本课程的学习，使学生透彻地理解数据结构的逻辑 结构和物理结构、基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可 靠的程序，为后续课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，《数 据结构》课程在计算机应用中具有举足轻重的作用。 学习本课程前，学生应具备计算机的基本操作能力，并掌握至少一门计算机高级编程语 言。 一、课程性质、目的和任务 性质：本课程是卫生信息管理专业学生的一门必修课，主要研究数据的各种逻辑结构和 存储结构，以及对数据的各种操作。 目的：在基础理论方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法； 在理论应用方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计和技 巧有所体会。 任务：总学时 54 学时，其中理论讲授 24 学时，实验学时 18 学时。将系统学习数据结 构方面的知识，提高本专业学生在应用数据结构解决实际问题中的能力。 二、教学基本要求 通过本课程的学习，学生应能达到下列要求： （1） 了解数据结构及其分类、数据结构与算法的密切关系。 （2） 掌握各种基本数据结构及其操作、学会根据实际问题的要求选择适当的数据结 构。 （3） 掌握设计算法的步骤和算法分析方法。 （4） 掌握线性表、数组、栈、队列以及树和图的定义、存储结构及基本算法的实现。 （5） 掌握在顺序表、有序表、散列表等上的查找算法。 （6） 掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序的基 本思想及算法；了解其算法时、空复杂度的分析
三、各教学环节学时分配内容课堂讲授实验、见习课2（一）数据结构概述31（二）顺序表和链表31（三）栈和队列（四）串2121（五）数组22（六）递归63（七）树和二叉树53（八）图53（九）查找63（十）排序3618总计四、教学内容及要求第一章绪论【掌握】1.算法的描述方法：2.掌握算法时间复杂度的计算方法。【了解】1.数据、数据元素、数据项、结点及抽象数据类型等数据结构的基本概念；2.数据结构在计算机编程中的作用和地位；数据结构课程所包含的三方面的内容：算法的定义，掌握算法的五个特点：3.算法时间（空间）复杂度概念。4.第二章线性表【掌握】1.顺序表的结构定义；2.熟练掌握顺序表的构造、置空、插入、删除等基本操作；3.掌握动态分配内存和释放函数的使用方法。【熟悉】1．单链表的建立、查找、插入、删除算法；2．理解单链表的逆向链接算法思想。【了解】1.线性表的特性，掌握线性表的表示方法；2.顺序表的概念，掌握顺序表的存储方式；3．线性链表的定义，掌握线性链表的存储特点。2
2 三、各教学环节学时分配 内容 课堂讲授 实验、见习课 （一）数据结构概述 2 （二) 顺序表和链表 3 1 （三）栈和队列 3 1 （四）串 2 1 （五）数组 2 1 （六）递归 2 2 （七）树和二叉树 6 3 （八）图 5 3 （九）查找 5 3 （十）排序 6 3 总 计 36 18 四、教学内容及要求 第一章 绪论 【掌握】 1. 算法的描述方法； 2. 掌握算法时间复杂度的计算方法。 【了解】 1. 数据、数据元素、数据项、结点及抽象数据类型等数据结构的基本概念； 2. 数据结构在计算机编程中的作用和地位； 3. 数据结构课程所包含的三方面的内容；算法的定义，掌握算法的五个特点； 4. 算法时间（空间）复杂度概念。 第二章 线性表 【掌握】 1. 顺序表的结构定义； 2. 熟练掌握顺序表的构造、置空、插入、删除等基本操作； 3. 掌握动态分配内存和释放函数的使用方法。 【熟悉】 1. 单链表的建立、查找、插入、删除算法； 2. 理解单链表的逆向链接算法思想。 【了解】 1. 线性表的特性，掌握线性表的表示方法； 2. 顺序表的概念，掌握顺序表的存储方式； 3. 线性链表的定义，掌握线性链表的存储特点
第三章栈和队列【掌握】1.栈的表示方法及基本操作：2.线性队列的表示方法及相关运算；3.掌握循环队列的基本算法。【熟悉】1.递归的执行过程：2.栈在解决实际问题中的应用。【了解】1.栈的基本概念，掌握其存储特性：2.队列的基本概念，掌握其存储特性：3.循环队列的概念；4.队列在解决实际问题中的应用。第四章串【掌握】1.串的逻辑结构定义；2.串的基本运算及其实现。【熟悉】1.串的匹配算法；2.串在解决实际问题中的应用。第五章递归【掌握】1.递归的定义方法和递归算法的设计。【熟悉】1. 常用的递归算法。第六章数组和广义表【掌握】1．一维、二维数组定义的方法；2.数组的存储方式（以列为主序、以行为主序），会计算数组元素的存储位置：3.掌握矩阵的转置、求和和乘积算法：4.稀疏矩阵的表示方法：5.掌握基于三元组顺序存储的矩阵转置算法。【了解】1.数组的基本概念：2.矩阵的概念；3.稀疏矩阵的概念。第七章树【掌握】1.树的表示方法：2.掌握二叉树的性质；3.掌握二叉树的表示方法，掌握二叉树的遍历算法；3
3 第三章 栈和队列 【掌握】 1. 栈的表示方法及基本操作； 2. 线性队列的表示方法及相关运算； 3. 掌握循环队列的基本算法。 【熟悉】 1. 递归的执行过程； 2. 栈在解决实际问题中的应用。 【了解】 1. 栈的基本概念，掌握其存储特性； 2. 队列的基本概念，掌握其存储特性； 3. 循环队列的概念； 4. 队列在解决实际问题中的应用。 第四章 串 【掌握】 1. 串的逻辑结构定义； 2. 串的基本运算及其实现。 【熟悉】 1. 串的匹配算法； 2. 串在解决实际问题中的应用。 第五章 递归 【掌握】 1. 递归的定义方法和递归算法的设计。 【熟悉】 1. 常用的递归算法。 第六章 数组和广义表 【掌握】 1. 一维、二维数组定义的方法； 2. 数组的存储方式（以列为主序、以行为主序），会计算数组元素的存储位置； 3. 掌握矩阵的转置、求和和乘积算法； 4. 稀疏矩阵的表示方法； 5. 掌握基于三元组顺序存储的矩阵转置算法。 【了解】 1. 数组的基本概念； 2. 矩阵的概念； 3. 稀疏矩阵的概念。 第七章 树 【掌握】 1. 树的表示方法； 2. 掌握二叉树的性质； 3. 掌握二叉树的表示方法，掌握二叉树的遍历算法；
4.掌握线索二叉树的概念及应用；5.掌握二叉排序树的建立、查找、删除算法；6.掌握树与二叉树的相互转换；7.掌握Huffman树的概念，熟练掌握Haffman编码方法，会构造Haffman树。【了解】1．树的概念，掌握结点、结点的度、树的度、森林等的概念；2.二叉树的基本概念；3.二叉排序树的概念。第八章图【掌握】1.图的存储结构及深度（DFS）和广度（BFS）优先搜索方法及其实现；2.求图的最小生成树的普里姆算法和克鲁斯卡尔算法并了解其实现算法：3.掌握最短路径的求解问题；4.掌握拓扑排序的方法并了解其实现算法。【了解】1.图的定义和术语：2.图的生成树的概念。第九章查找【掌握】1．顺序查找和折半查找的方法及实现；2.利用除留余数法构造散列函数的方法，利用线性探查法和链接法处理冲突的方法【了解】1.查找的相关概念；2.哈希查找的基本思想，掌握构造哈希函数的方法：3．哈希散列表的定义。第十章内排序【掌握】1.．直接插入排序、直接选择排序、冒泡排序的方法及其实现；2．快速排序、堆排序、二路归并排序的方法及其实现。【了解】1．各种排序方法的稳定性、时间复杂度和空间复杂度。五、实贼及见习实验一表的操作()实验类别：验证性、设计性实验。(二)实验目的：1.学会在VC环境下使用结构定义方法；2.掌握顺序表的操作（构造、置空、插入、删除等操作）。（三）实验内容：4
4 4. 掌握线索二叉树的概念及应用； 5. 掌握二叉排序树的建立、查找、删除算法； 6. 掌握树与二叉树的相互转换； 7. 掌握 Huffman 树的概念，熟练掌握 Haffman 编码方法，会构造 Haffman 树。 【了解】 1. 树的概念，掌握结点、结点的度、树的度、森林等的概念； 2. 二叉树的基本概念； 3. 二叉排序树的概念。 第八章 图 【掌握】 1. 图的存储结构及深度（DFS）和广度(BFS)优先搜索方法及其实现； 2. 求图的最小生成树的普里姆算法和克鲁斯卡尔算法并了解其实现算法； 3. 掌握最短路径的求解问题； 4. 掌握拓扑排序的方法并了解其实现算法。 【了解】 1. 图的定义和术语； 2. 图的生成树的概念。 第九章 查找 【掌握】 1. 顺序查找和折半查找的方法及实现； 2. 利用除留余数法构造散列函数的方法，利用线性探查法和链接法处理冲突的方法。 【了解】 1. 查找的相关概念； 2. 哈希查找的基本思想，掌握构造哈希函数的方法； 3. 哈希散列表的定义。 第十章 内排序 【掌握】 1. 直接插入排序、直接选择排序、冒泡排序的方法及其实现； 2. 快速排序、堆排序、二路归并排序的方法及其实现。 【了解】 1. 各种排序方法的稳定性、时间复杂度和空间复杂度。 五、实贱及见习 实验一 表的操作 （一） 实验类别：验证性、设计性实验。 （二） 实验目的： 1. 学会在 VC 环境下使用结构定义方法； 2. 掌握顺序表的操作（构造、置空、插入、删除等操作）。 （三） 实验内容：
1.熟悉VC编译环境，利用数组构造一个线性顺序表；2.编程实现对该表的遍历、插入、删除操作(四）实验学时：1。实验二栈和队列的操作（一）实验类别：验证性、设计性实验。（二）实验目的：1.掌握线性队列的链表表示方法：2.掌握队列的入队和删除运算。（三）实验内容：1.基于链表结构建立一个队列；2.编程实现入队、出队操作。（四）实验学时：1。实验三串的操作（一）实验类别：验证性、设计性实验。（二）实验目的：1.掌握串的表示方法，模式匹配算法。（三）实验内容：1.对于顺序串；编程实现BF算法。（四）实验学时：1。实验四数组（一）实验类别：验证性、设计性实验。（二）实验目的：1.掌握一维、二维数组定义的方法；2.掌握矩阵的转置、求和算法。（三）实验内容：1.建立两个二维数组，对其中一个进行转置操作，然后再对两数组进行加运算。（四）实验学时：1。实验五递归（一）实验类别：验证性、设计性实验。（二）实验目的：1.掌握递归的设计方法。（三）实验内容：1.用递归方法解决八皇后问题。（四）实验学时：2。实验六树的操作（一）实验类别：验证性、设计性实验。（二）实验目的：1.掌握二叉树的节点定义及表示方法：5
5 1. 熟悉 VC 编译环境，利用数组构造一个线性顺序表； 2. 编程实现对该表的遍历、插入、删除操作 （四） 实验学时：1。 实验二 栈和队列的操作 （一） 实验类别：验证性、设计性实验。 （二） 实验目的： 1. 掌握线性队列的链表表示方法； 2. 掌握队列的入队和删除运算。 （三） 实验内容： 1. 基于链表结构建立一个队列； 2. 编程实现入队、出队操作。 （四） 实验学时：1。 实验三 串的操作 （一） 实验类别：验证性、设计性实验。 （二） 实验目的： 1. 掌握串的表示方法，模式匹配算法。 （三） 实验内容： 1. 对于顺序串；编程实现 BF 算法。 （四） 实验学时：1。 实验四 数组 （一） 实验类别：验证性、设计性实验。 （二） 实验目的： 1. 掌握一维、二维数组定义的方法； 2. 掌握矩阵的转置、求和算法。 （三） 实验内容： 1. 建立两个二维数组，对其中一个进行转置操作，然后再对两数组进行加运算。 （四） 实验学时：1。 实验五 递归 （一） 实验类别：验证性、设计性实验。 （二） 实验目的： 1. 掌握递归的设计方法。 （三） 实验内容： 1. 用递归方法解决八皇后问题。 （四） 实验学时：2。 实验六 树的操作 （一） 实验类别：验证性、设计性实验。 （二） 实验目的： 1. 掌握二叉树的节点定义及表示方法；