《数据结构》课程教学实施计划

《《数据结构》课程教学实施计划》由会员分享，可在线阅读，更多相关《《数据结构》课程教学实施计划（24页珍藏版）》请在金锄头文库上搜索。

1、数据结构课程教学实施计划 数据结构课程教学实施计划课程代码04812600课程名称数据结构Data Structuresand Algorithms学时/学分64学时（48授课课时+16实验课时）/31学分先修知识高等程序设计、软件基础实验、高等数学、离散数学开课单位计算机与通信学院适用专业计算机科学技术、信息安全、通信工程、智能科学与技术专业开课时间本科2年1期课程性质必修使用教材数据结构（C语言版）严蔚敏著清华大学出版社xx 一、课程教学目标“数据结构与算法”是计算机专业本科生的一门必修的专业基础课，通过本课程的学习，让学生掌握线性表、栈、队列、二叉树、树和图等常用的数据结构；掌握常用的排

2、序、检索算法及其时间、空间代价；学会分析计算机处理的数据对象的特性，能够选择并设计合适的数据结构及相应的算法，初步掌握算法的时间和空间代价的分析方法。 二、教学内容及基本要求（一）绪论 (1)了解数据类型、抽象数据类型、数据结构的概念以及它们之间的关系 (2)了解问题、算法、程序、算法的代价等概念（二）算法分析 (1)了解渐近算法分析、算法代价的增长率等概念 (2)了解算法的最佳情况、最差情况和平均情况 (3)掌握上限、下限的概念以及大、大和大表示法 (4)掌握渐进分析的化简法则 (5)掌握简单程序运行时间的计算方法 (6)了解问题的代价与算法的代价的区别 (7)了解多参数问题、空间代价、空间

3、/时间权衡原则和实际操作中的一些因素（三）递归掌握递归算法的设计方法（四）线性表、栈和队列 (1)了解线性表的基本概念和抽象数据类型 (2)掌握顺序表的实现方法 (3)掌握带表头结点的单链表的实现方法 (4)了解线性表的两种实现方法的优点和缺点 (5)掌握带表头结点的双链表的实现方法 (7)了解单循环链表和双循环链表的结构 (8)了解栈的基本概念 (9)掌握顺序栈的实现方法 (10)掌握链式栈的实现方法 (11)了解顺序栈与链式栈的比较 (12)了解队列的基本概念 (13)掌握顺序队列的实现方法 (14)掌握链式队列的实现方法 (15)了解顺序队列与链式队列的比较（五）二叉树 (1)了解二叉树

4、的定义与术语 (2)掌握满二叉树与完全二叉树的定义 (3)掌握满二叉树定理及其推论 (4)了解二叉树结点的抽象数据类型 (5)掌握前序、中序和后序周游二叉树的方法 (6)掌握用指针实现二叉树的方法 (7)了解二叉树实现的结构性开销的计算 (8)掌握用数组实现完全二叉树的方法 (9)掌握二叉检索树的实现方法 (10)掌握实现堆以及利用堆实现优先队列的方法 (11)掌握Huffman编码树的建立以及利用它进行编码/反编码的方法（六）树 (1)了解树的定义与术语 (2)了解树结点的抽象数据类型及树的周游方法 (3)掌握树的父指针表示法以及利用UNION/FIND算法解决等价类问题的方法 (4)了解树

5、的子结点表表示法、动态和静态的左子结点/右兄弟结点表示法 (5)了解K叉树和树的顺序表示法（七）图 (1)了解图的术语和邻接矩阵、邻接表表示法 (2)了解图的抽象数据类型 (3)掌握图的邻接矩阵和邻接表实现方法 (4)掌握图的两种周游算法:深度优先和广度优先算法 (5)掌握图的两种拓扑排序算法 (6)了解关键路径算法 (7)掌握求单源最短路径的Dijkstra算法 (8)掌握求每对顶点间最短路径的Floyd算法 (9)掌握求最小支撑树的Prim算法和Kruskal算法（八）内排序 (1)掌握冒泡排序、选择排序和插入排序算法 (2)了解Shell排序算法 (3)掌握快速排序算法 (4)掌握归并排

6、序算法 (5)掌握堆排序算法 (6)了解基数排序算法 (7)了解各种排序算法的实验比较和排序问题的下限（九）查找 (1)了解已排序数组的查找方法 (2)了解自组织线性表的查找方法 (3)了解集合的查找方法 (4)了解B树 (5)掌握散列函数的设计方法 （6）掌握两种冲突解决策略:开散列方法和闭散列方法 三、考核方式课堂讲授+作业+实验+考试课堂参与 （10）+课后作业 （10）+课程实验 （20）+课程考试 （60） 四、教学进度安排（含作业及实验安排）授课内容授课时间作业课程实验第一章绪论2作业1第二章线性表8作业2实验 1、2第三章堆栈和队列4作业3实验3第四章串2作业4实验4第五章数组和

7、广义表2第六章树和二叉树8作业5实验5第七章图6作业6实验6第八章内部排序8作业7实验7第九章查找8作业8实验8小计488次8个 四、参考书1.数据结构与算法分析（C+版）（第二版）Clifford A.Shaffer著张铭刘晓丹等译电子工业出版社xx年2.数据抽象和问题求解Java语言描述.Frank M.Carrano等著,韩志宏译.清华大学出版社xx年4月第1版.附录一大作业设计并实现一个简单文本器设计目标1.该文本器能不断接收和执行人通过键盘发出的命令，直至收到结束命令时终止运行。 2.启动后给出提示信息，表示已经进入结束和执行命令的正常工作状态。 具体要求实现如下命令（注意下面说明中

8、的和在实际命令中并不出现，命令和命令参数之间用空格分隔）i文件名把指定文件读入器（存储区）o文件名将存储区的内容写入指定文件ln字符串把给定字符串插入文本中作为第n行dn删除区里的第n行v显示整个文本区的内容pn显示文本第n行的内容f字符串显示包含指定字符串的所有行，在行前给出行的编号r字符串1字符串2将文本里所有的字符串1替换为字符串2sn字符串1字符串2将第n行里所有的字符串1替换为字符串2q终止器程序h帮助，说明所有命令及其使用方式（类似这个表）设计建议1.请首先考虑好内容的存储组织问题2.可以假定每行的长度不超过某指定字符数，例如80和127字符3.可以不考虑跨行的字符串匹配问题4.可

9、以考虑用C标准库的行式读入命令（gets或fgets）把命令行整个读入一个字符数组，而后在数组里分析命令内容的实现方式。 这样实现起来比较方便5.可根据自己的认识增加其他命令（设计命令形式并完成相应实现）注意事项?该设计最重要的工作就是数据结构的选择和设计。 适当的数据结构可以使程序结构清晰，操作的实现方便，算法具有好的性质（速度快，虽然在小文件时不明显，但大文件就会显现出来），适应性强（例如，请考虑能否适应大型文件），易于扩充等等。 ?请综合考虑学过的几种数据结构，考虑器需要执行的各种操作，做出自己的设计选择。 ?可能的数据结构设计非常多，建议各位同学设想若干种设计，而后根据对问题的分析选出

10、一种使用。 作业提交要求及注意事项1.要求每个同学独立完成这个实习项目，并写出一篇“实习报告”o说明程序的使用方式，包括所实现的所有命令及其使用形式和功能o给出几个使用程序中所提供命令的例子o程序实现中的设计问题选择了什么样的数据结构（为什么）；程序的基本部分及其相互关系；几个最重要的操作的实现；实现中遇到的问题及其解决方法；最后的效果o程序完成后的思考完成的程序有哪些不足之处；如果你重新做可能怎样改进；如果要你做一个真正能提供给别人使用的器，你可能怎样设计等等。 2.程序和实习报告都采用电子文档形式（通过email附件）交老师。 报告可以交PDF或DOC文件。 3.如果采用多个源文件的形式开

11、发，发给老师前请把文件打包（可以打包为rar或者zip）。 注意只上交所有源程序文件（不要交可执行程序）。 必须保证程序能正常编译和执行。 4.请注明所用的程序开发环境（作为程序里的注释），以便老师检查时参考。 5.请注意保证自己上交的文档中没有病毒。 6.实习项目成绩将根据所做工作和上面各项要求的完成情况评定。 附录二小作业作业一1.1什么是抽象数据类型？试述抽象数据类型与C+类的区别。 1.2试用C+的类来定义表示复数的抽象数据类型。 (1)在复数内部用浮点数定义其实部和虚部； (2)实现2个构造函数缺省的构造函数没有参数；第2个构造函数将2个双精度浮点数分别赋给复数的是部和虚部； (3)

12、定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。 1.3 (1)假设某算法在输入规模为n时的计算时间为T(n)=3*2n。 在某台计算机上实现并完成该算法的时间为t秒。 现有另一台计算机,其运行速度为第一台的64倍,那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题? (2)若上述算法的计算时间改进为T(n)=n2，其余条件不变，则在新机器上用t秒时间能解输入规模为多大的问题? (3)若上述算法的计算时间进一步改进为T(n)=8,其余条件不变,那么在新机器上用t秒时间能解输入规模为多大的问题?1.4硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手A

13、BC公司同类产品的100倍。 对于计算复杂性分别为n,n2,n3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题?1.5证明如果一个算法在平均情况下的计算时间复杂性为(f(n)，,则该算法在最坏情况下所需的计算时间为(f(n)?。 作业二2.1用数组实现表的一个缺点是需要预先估计表的大小。 克服这个缺点的一个方法是在初始化时先将数组大小MaxSize置为1，其后在插入一个元素时，如果表已满，就重新分配一个大小为2*MaxSize的数组，将表中元素复制到新数组中，并删除老数组。 类似地，在删除一个元素后，如果

14、表的大小已降至1/4MaxSize，就重新分配一个大小为1/2MaxSize的新数组，将表中元素复制到新数组中，并删除老数组。 (1)用上述思想重新设计用数组实现表的模板类。 (2)设P1,P2,P3,Pn是从空表开始的n个表运算组成的序列。 如果教材中用原数组实现表的方法执行此运算序列需要F(n)计算时间，试证明用本题实现表的方法执行此运算序列最多需要cF(n)计算时间，其中c是一个常数。 2.2解决习题2.1中提出的数组空间分配问题的另一种方法是预先为数组分配一个较大的空间，让多个表共享这一数组空间。 采用这种方法在设计算法时就应考虑多个表在同一数组空间中协调共存的问题。 试用上述思想重新设计用数组实现表的一个模板类。 2.3设表的Reverse运算将表中元素的次序反转。 (1)扩充用数组实现表的模板类List，使Reverse成为它的一个公有成员函数，并要求就地实现Reverse运算。 (2)试设计一个就地实现表的反转运算的函数Reverse（L），其中L是用数组实现的表，而Reverse不是List的成员函数。 2.4设A和B均为用数组实现的Lis