中国科学技术大学 - 数据结构 教学大纲

课程名称    数 据 结 构 |V<h=D5W  
英文名称    Data Structures Me 5_4H&Sg  
课程编号    不填    总学时    60    学 分    不填 L!=QR8?@E  
预修课程    C语言    开课学期    不填 R {-5Etv  
大纲撰写人    黄刘生 4;2< ^[M  
一、教学目标和基本要求 Iu$K i  
    目的：使学生较全面地掌握各种常用的数据结构，提高其数据抽象和程序设计能力,为学习后续软件课程提供坚实的基础。 y@\V+  
    基本要求：使学生能够从逻辑结构、存储结构和数据的运算三个方面去掌握各种数据结构的特性, 对算法的时、空复杂性有一定的分析能力，使之能够针对具体的应用问题， 选择合适的数据结构及设计结构清晰、正确有效的算法解决之。 J~#;<e{\"  
二、课程简介 hWX% 66  
  数据结构是计算机学科一门重要的专业基础课，该课程系统地讨论各种常用的数据结构及其应用，以及查找和排序的各种方法及其综合分析比较，培养学生数据抽象和程序设计的能力，算法时、空复杂性的分析能力。 Dk?\)lD`  
三、教学重点、难点 K_dOq68_  
1．    概论：重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及其相互关系，难点是抽象数据类型和算法复杂度的分析方法。  trAkcYd  
2．    线性表：重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是能够使用所学到的基本知识设计有效算法解决与线性表相关的应用问题。 lV%N  
3．    栈和队列：重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。 hZ.Z3`v70  
4．    串：重点是掌握串上实现的模式匹配算法，这也是本章的难点。 3-&QRR#p  
5．    树：重点掌握二叉树的遍历算法及其有关应用，难点是使用本章所学到的有关知识设计出有效算法解决与树或二叉树相关的应用问题。 Lq
A@&H  
6．    图：重点掌握图在邻接矩阵与邻近表上实现的遍历算法。难点是求图的最小生成树、最短路径、拓扑排序等应用算法及其时间性能分析。 tg{H9tU;  
7．    动态存储管理: 重点是内存空间的分配与回收算法，以及可利用空间表的结构。本章难点是无用单元收集算法的理解与掌握。 -;'1^  
8．    查找：重点掌握顺序查找、二分查找、二叉查找树上查找以及散列表上查找的基本思想和算法实现。本章难点是二叉查找树的删除算法及B-树上的插入和删除算法。 i9/aAH
0  
9．    文件：本章重点是介绍存储在外存上的数据絇OST http://www.freekaobo.com/post.php? HTTP/1.0 ]MxC_V+P`  
Pro和更新操作。 ra o[VZ  
;UxP Kpl  
M%@!cW  
四、教材名称及主要参考书 e
d<n9R  
《数据结构C语言版》严蔚敏、吴伟民，清华大学出版社，2000。 qzTuxo0B  
《数据结构第2版》黄刘生、唐策善，中国科技大学出版社，2001。 Rj4|Q:XG  
"Data Structures with C++" Williaw Ford et al., Prentice Hall Inc., 1996. $C `;fA
 
"Data Structures & Program Design in C, 2nd Ed." Robert Kruse et al., Prentice Hall Inc., 1997. Sv +IS  
五、课程章节主要内容及学时分配 %HL*c=  
UXdUO@  
第一章 概 论（3学时） R00eisd  
第一节 基本概念和术语 5=Di<!a;  
第二节    学习数据结构的意义 $g sxO!G  
第三节    抽象数据类型 PbmDNKEh{  
第四节    算法的描述和分析 v&=gF/$  
第二章 线性表（6学时） ~/P&Tub^  
第一节 线性表的逻辑结构 `b^Ru+(dM  
第二节 线性表的顺序存贮结构 ~x|F)~:0=  
第三节 线性表的链式存贮结构 8p:j&F  
第四节 顺序表和链表的比较 >M`CV
Uf  
第三章 栈和队列（6学时） *3?'4"B{8  
第一节 栈 7:2WgLo  
第二节    队列 fP. 6HF_p_  
第三节    栈与队列的应用实例 vMm1Z5S/  
第四章 串（4学时） %;rHrDP(>  
第一节 串及其运算 MP>dW nl  
第二节    串的存贮结构 lb3]$Da   
第三节    串的模式匹配 c|#8T*`C  
第六章 树（10学时） v^1pN>#%g  
第一节 树的概念 ayfFVTy1d  
第二节 二叉树 }3OKC2K~  
第三节    二叉树的遍历 [_Qa9e  
第四节    线索二叉树 *exS6@N]  
第五节    树和森林 5Er2}KZJv,  
第六节    哈夫曼树及其应用    第七节    树与等价问题、树的计数 |v$JCU3!A  
第六章 图（10学时） HlH64w2^R  
第一节 图的概念 yc?a=6q'm  
第二节 图的存贮结构 x;8A!8w  
第三节 图的遍历 j
'HZ\_  
第四节 图的连通性问题 mD^jd+  
第五节 最短路径 WjlZ6g2i  
第六节    有向无环图及其应用 R wZ]),o  
第七章 动态存储管理（5学时） vy\RcP  
第一节 概述 ;,?KI$K  
第二节    可利用空间表及分配算法 @ < Q|5  
第三节    边界标识法 ~2gG(1%At9  
第四节    伙伴系统 !Ikt '5/  
第五节    无用单元收集 -i%e !DgH  
第八章 查找（8学时） tF{D= ;G  
第一节 基本概念 {/ BT9|LI  
第二节 静态查找 !& z(:d  
第三节 动态查找 ):b$xNn  
第四节 散列查找 d~1gMz+)  
第九章 文件简介（2学时） @Bf%s(Uj+  
第一节    文件基本概念 "O%gFye  
第二节    顺序文件与索引文件 MMx9(`t*.  
第三节 ISAM和VSAM文件 @CZ T  
第四节 散列文件 N<IT w/@^  
六、系教学委员会意见 ^$'z!+QRM  
z$?~Y(EY  
R'!   
5 *,f Fib  
-6n K<e`  
组长签字：       年 月 日 b"vv>Q~U  
七、系主任意见 P8*=Ls+-F  
rU2%dkTa  
+/)#( j@  
]y1OFKYv  
o aoU _V  
系主任签字：       年 月 日