《数据结构 (Ⅱ)》教学大纲

《数据结构 (Ⅱ)》教学大纲编写人：董凯宁 编写时间：2005 年 10 月 30 日一、课程基本信息课程名称： 数据结构 (Ⅱ) Data Structure (II)课 程 号： 40128830课程类别： 专业课学 时： 48 学 分： 3二、教学目的及要求数据结构概论，从抽象数据类型的角度讨论线性表、栈、队列，串、数组、广义表，树 、二叉 树和 图等基本类型的数据结构及其应用，抽象数据类型的常用表示方法,操作系统和编译程序中涉及的动态存储管理的基本技术，查找、内部排序，外部排序，置换－选择排序, 文件的概念，文件结构,索引顺序存取方法。三、教学内容第 1 章 绪论 （共 3 学时） 1.1 什么是数据 结 构 （0.5 学时）教学内容：由数学方程无法描述的非数值计算问题引出数据结构表、图、树的 3 种实例，阐述数据结构的概念，数据结构的内涵和特点，数据结构所处的学科地位，数据结构的学科背景、起源、发展和现状；要求学生掌握数据结构的概念，能辨 别数学模型中数学方程和表、图、树等数据结构的区别。 1.2 基本概念和 术语 （1 学时）教学内容：阐述本课使用的一些基本概念，包括数据、数据元素、数据项、数据对象、数据结构、集合、结构、 线性结构、 树形结构、图状结构、网状结构、逻辑结构、物理结构、存储结构、位、元素、结点、数据域、顺序映像、非顺序映像、顺序存储结构、链式存储结构、指针、虚拟存储结构、数据 类型、原子类型、结构类型、抽象数据类型、固定聚合类型、可变聚合类型、多形数据 类型；要求学生掌握包括数据、数据元素、数据项、数据对象、数据结构、集合、结构、线性结构、树形结构、图状结构、网状 结构等在内的所有基本概念。162 1.3 抽象数据 类 型的表示与 实现 （0.5 学时）教学内容：阐述在 C 语言中，抽象数据 类型的常用表示方法，包括 预定义常量和类型、数据结构的表示用类型定义（typedef）描述、函数表示法、各种 赋值语句、选择语句、结束语句、输入和输出语句、基本函数、 逻辑运算约 定；要求学生了解抽象数据类型的描述语言、构成方法，掌握抽象数据类型的类 C 语言 11 种表示方法。 1.4 算法与算法分析 （1 学时）1.4.1 算法教学内容：阐述算法的定义，算法的 5 个重要特征：有穷性、确定性、可行性、输入、输 出；要求学生掌握算法的定义，理解算法的 5 个重要特征。1.4.2 算法 设计 要求教学内容：阐述好算法设计的 4 个要求——即正确性、可读性、强壮性和效率与低存储量需求；要求学生理解好算法设计的 4 个要求。 1.4.3 算法效率的度量教学内容：阐述算法效率的 2 种度量方法：事前统计的方法和事后分析估算的方法，时间 复 杂度的概念，频度的概念；要求学生掌握 时间复杂度的概念， 频度的概念。1.4.4 算法的存 储 空 间 需求教学内容：阐述空间复杂度的概念，空间复杂度的表示法，算法原地工作的概念；要求学生掌握空间复杂度的概念，了解算法原地工作的概念。第 2 章 线性表 （共 4 学时）  2.1 线 性表的 类 型定 义 （0.5 学时）教学内容：阐述线性结构的特点，线性表的抽象数据类型定义，数据项、 记录、文件的定义，实例说明线性表的插入、删除、归并等操作方式，并对算法做相应的分析；要求学生掌握线性表的概念和抽象数据类型定义。 2.2 线 性表的 顺 序表示和 实现 （重点） （1.5 学时）教学内容：阐述线性表的顺序表示的概念，顺序映像的方式，顺序映像的随机存取特性，实例描述线性表在顺序存储表示时进行插入、 删除、合并操作的几种算法；要求学生掌握线性表的顺序表示的概念和顺序映像的方式，理解线性表在顺序存储结构时的插入、删除、合并等操作方法。 2.3 线 性表的 链 式表示和 实现 （重点） （1.5 学时）2.3.1 线 性 链 表教学内容：阐述线性链表的概念、构成方式，结点、数据域、指针域、指针、链、链表、头 指针 、头结点和静态链表的概念， 线性链的表示法，实例算法说明单链表的插入、 删除、合并操作处理算法，静 态链表的算法；要求学生掌握线性有序链表的概念、与之相关的名词概念，理解 单链表的插入、删除、合并操作算法过程。2.3.2 循 环链 表教学内容：阐述循环链表的概念，循环链表的操作特点；要求学生掌握循环链表的概念。2.3.3 双向 链 表教学内容：阐述双向链表的概念和特点，双向链表的抽象数据类型定义，双向链表的几种操作算法；要求学生掌握双向链表的概念，理解双向链表的抽象数据类型定义，理解双向 链表的操作算法。编号：信息管理与信息系统—2005—8 公共管理学院本科课程教学大纲163 2.4 一元多 项 式的表示及相加 （0.5 学时）教学内容：阐述存储高次一元多项式的线性表可以采用每个元素包含 2 个数据项的方法，利用线性链表的基本操作来实现一元多项式的定义、相加和相乘运算；要求学生掌握利用线性链表的基本操作来实现一元多项式的定义、相加和相乘运算。第 3 章 栈和队列 （共 4 学时） 3.1 栈 （0.5 学时）3.1.1 抽象数据 类 型 栈 的定 义教学内容：阐述栈、栈顶、栈底、后进先出等概念，栈的抽象数据定义；要求学生掌握栈及栈的相关概念，理解栈的抽象数据定义。3.1.2 栈 的表示和 实现教学内容：阐述栈的 2 种存储表示法：顺序栈和链栈的定义，顺序栈的模块说明；要求学生掌握顺序栈的定义。 3.2 栈 的 应 用 举 例 （1 学时）3.2.1 数制 转换教学内容：阐述应用栈结构的后进先出特性，进行十进制 N 和其它 d 进制数的转换算法；要求学生理解应用栈结构的数制转换算法。3.2.2 括号匹配的 检验教学内容：阐述应用栈结构的后进先出特性，进行圆括号和方括号书写格式是否正确的检查算法；要求学生理解应用栈结构的括号匹配检验算法。3.2.3 行 编辑 程序教学内容：阐述应用栈结构的文本行编辑算法；要求学生理解应用栈结构的文本行编辑算法。3.2.4 迷 宫 求解教学内容：阐述应用栈结构的迷宫求解算法，即求出迷宫中从入口到出口的所有路径；要求学生理解应用栈结构的迷宫求解算法。3.2.5 表达式求 值教学内容：阐述应用栈结构进行表达式求值的算符优先法，算符优先法中的算符优先关系，要求学生理解应用栈结构进行表达式求值的算符优先法。 3.3 栈 与 递归 的 实现 （0.75 学时）教学内容：阐述递归的概念、递归问题的特性， 栈在 n 阶 Hanoi 塔问题等典型递归问题中的应用；要求学生理解栈在 n 阶 Hanoi 塔递归算法中的应用。 3.4 队 列 （重点） （1.5 学时）3.4.1 抽象数据 类 型 队 列的定 义教学内容：阐述队列、FIFO 的概念，队列的特性， 队列的抽象数据定义，双端队列的概念；要求学生掌握队列的概念，理解队列的特性，队列的抽象数据定义，双端 队列的概念。3.4.2 链队 列－ 队 列的 链 式表示和 实现教学内容：阐述链队列的概念，链队列类型的模块说明，队列链式表示的基本操作函数；要求学生掌握链队列的概念，理解链队列类型的模块说明，队列链式表示的基本操作函数。3.4.3 循 环队 列－ 队 列的 顺 序表示和 实现教学内容：阐述循环队列的概念，循环队列类型的模块说明，队列循环表示的基本操作函数；要求学生掌握循环队列的概念，理解循环队列类型的模块说明，164队列循环表示的基本操作函数。 3.4 离散事件模 拟 （0.25 学时）教学内容：阐述使用有序链表和队列这两种数据类型做离散事件模拟的算法；要求学生理解包含有序链表和队列的事件模拟程序。第 4 章 串 （共 3 学时） 4.1 串 类 型的定 义 （0.5 学时）教学内容：阐述串产生的背景，串的概念，串长度、空串、子串、主串、位置、空格串等概念，串的抽象数据类型定义，串的基本操作集概念；要求学生掌握串及相关的概念，理解串的抽象数据类型定义。 4.2 串的表示和 实现 （重点） （1.5 学时）4.2.1 定 长顺 序存 储 表示教学内容：阐述串在机内的定长顺序表示，在这种存储结构表示时如何实现串的连接操作和子串操作；要求学生掌握串的定长顺序存储表示，理解在定长顺序存储结构表示时实现串的连接操作和子串操作的方法。4.2.2 堆分配存 储 表示教学内容：阐述串的堆分配存储表示，在这种存储结构表示时如何实现串的插入操作；要求学生掌握串的堆分配存储表示，理解在堆分配存储结构表示时实现串的插入操作4.2.3 串的 块链 存 储 表示教学内容：阐述串的块链存储表示；要求学生掌握串的块链存储表示。 4.3 串的模式匹配算法 （0.75 学时）4.3.1 求子串位置的定位函数教学内容：阐述定位操作、匹配、模式匹配、模式串等概念，求子串位置的定位函数；；要求学生掌握模式匹配的概念，熟悉求子串位置的定位函数。4.3.2 模式匹配的一种改 进 算法教学内容：阐述克努特－莫里斯－普拉特（KMP）模式匹配算法；要求学生熟悉 KMP 模式匹配算法。 4.4 串操作 应 用 举 例 （0.25 学时）4.4.1 文本 编辑教学内容：阐述文本编辑是修改字符数据的形式或格式，在文本编辑中使用串操作；要求学生理解文本编辑中串的用法。4.4.2 建立 词 索引表教学内容：阐述使用串建立词索引表的方法，词索引表插入的实现算法；要求学生理解建立词索引表中串的用法。第 5 章 数组和广义表 （共 5 学时）  5.1 数 组 的定 义 （0.5 学时）教学内容：阐述抽象数据类型数组的定义；要求学生掌握抽象数据类型数组的定义。 5.2 数 组 的 顺 序表示和 实现 （重点） （1.5 学时）教学内容：阐述数组的顺序存储结构，以列序为主序的二维数组存储方式，以行序为主序的二维数组存储方式，n 维数组的数据元素存储位置的计算；要求学生掌握数组的顺序表示法。 5.3 矩 阵 的 压缩 存 储 （重点） （1.5 学时）编号：信息管理与信息系统—2005—8 公共管理学院本科课程教学大纲1655.3.1