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