一、课程性质与教学目的
用计算机解决任何问题都需要进行数据表示和数据处理,而数据表示和数据处理正是《数据结构》要研究的内容。《数据结构》是计算机科学中一门综合性的专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据,正确地设计算法以及对算法的分析和评价。通过本课程的学习,使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法,培养基本的、良好的程序设计技能,编制高效可靠的程序,为学习操作系统、编译原理和数据库等课程奠定基础。
二、基本要求
1. 了解数据结构及其分类、数据结构与算法的密切关系。
2. 熟悉各种基本数据结构及其操作,学会根据实际问题要求来选择数据结构。
3. 掌握设计算法的步骤和算法分析方法。
4. 掌握数据结构在排序和查找等常用算法中的应用。
5. 初步掌握文件组织方法和索引技术。
三、教学内容
1. 引论
数据、数据元素、数据结构、数据类型、抽象数据类型的概念;算法、算法描述与算法分析。
2. 线性表
线性表的逻辑结构定义、基本操作和在两种存储结构中基本操作的实现;链表;用线性表表示一元多项式及实现稀疏多项式的相加等运算。
3. 栈和队列
栈和队列的结构特性、基本操作及在两种存储结构上基本操作的实现;栈和队列的应用、递归算法的设计。
4. 串
串的逻辑结构定义、串的基本运算及其实现;串的匹配算法。
5. 数组和广义表
数组的逻辑结构定义和存储方法;特殊矩阵和稀疏矩阵的压缩存储方法;广义表的逻辑结构和存储结构以及广义表运算的递归算法。
6. 树和二叉树
树的基本概念;二叉树的定义、性质、存储表示;二叉树的遍历;线索二叉树;森林和二叉树的相互转换;树的应用;哈夫曼树及哈夫曼编码。
7. 图
图的基本概念、存储表示(邻接矩阵、邻接表、十字链表,邻接多重表);图的遍历、图的连通性问题;拓扑排序、关键路径;最短路径。
8. 动态存储管理
内存的"分配"和"回收"策略;可利用空间表及分配方法;边界标识法和伙伴系统。
9. 查找
查找表是集合类型的数据结构,其操作借助静态查找表、动态查找表、哈希表实现;
10. 排序
排序分为内部排序和外部排序。
内部排序介绍插入排序、快速排序(交换排序)、选择排序、归并排序;排序的基本思想和算法分析。
外部排序介绍外存储器(磁带、磁盘)简介;多路平衡归并、置换选择排序、最佳归并树及磁带归并排序。
11. 文件
基本概念;文件组织;顺序文件、随机文件、索引文件、倒排文件。
四、学分及学时分配
学分:4
学时:课程讲授学时64,上机学时16,合计80学时,建议分配如下。
|
序
号 |
内
容 |
学
时 |
|
1 |
引论 |
2 |
|
2 |
线性表 |
6 |
|
3 |
栈和队列 |
6 |
|
4 |
串 |
4 |
|
5 |
数组和广义表 |
4 |
|
6 |
树和二叉树 |
8 |
|
7 |
图 |
10 |
|
8 |
动态存储管理 |
2 |
|
9 |
查找 |
8 |
|
10 |
排序 |
12 |
|
11 |
文件 |
2 |
|
合计 |
|
64 |
五、参考书目
1.严蔚敏等著
《数据结构》
清华大学出版社 1997
2.范策等著
《算法与数据结构》
机械工业出版社 2004
3. 谢楚屏等编著
《数据结构》
人民邮电出版社
4. 徐绪松等著 《数据结构与算法导论》 电子工业出版社
5. D.E.Knuth著 《计算机程序设计技巧》第一、三卷 管纪文译 国防出版社
6. FULLS HORO-WITZ&SARTAJ SAHNT《FUNDAMENTALS OF DATA STRUCTURES》
《数据结构基础》(中译本)程惟宁译 新时代出版社
Web: http://www.qqread.com/data-structure/f968111102.html相关专题
- 数据结构 (175篇文章)
- Solaris基础知识入门 (4653篇文章)
- 数据结构相关文章 (175篇文章)
- TMPGEnc中码率控制的两大类模式浅析 (0次浏览)



