《数据结构》作为一门独立的课程最早是美国的一些大学开设的，1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们就越来越重视数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。

数据结构是计算机程序设计的重要理论技术基础，它对理论和实践的要求都相当高，具有相当的难度，且内容较多。本课程旨在讨论现实世界中数据（即事物的抽象描述）的各种逻辑结构在计算机中的存储结构，以及进行多种非数值基本运算的方法，让学生学习、分析和研究计算机加工数据对象的特性，掌握数据的组织方法，以便选择合适的数据的逻辑结构和存储结构，设计相应的操作运算，把现实中的问题转化为在计算机内部的表示和处理。在计算机应用领域中，尤其是在系统软件和应用软件的设计和应用中都要用到各种数据结构，这对提高程序编制和软件设计水平都有很大的帮助。

数据结构是计算机科学与技术专业的核心课程之一，属于专业基础课，是一门理论与实践相结合的课程。随着信息技术的发展，数据结构课程不仅是计算机科学与技术专业必修的核心课，同时也是电子工程、信息工程等专业的重要选修课程。本课程是针对我校非计算机专业本科生不同基础、不同能力和学习目标等情况而开设的。适合我校广大非计算机专业，包括理科、文科在内，本科生学习计算机程序设计的技术基础知识。

 

数据结构及应用算法教学大纲

第一章 预备知识（4学时）

1.1 程序设计概述

1.2 指针与结构体

1.3 函数

1.4 文件

1.5 结构化程序设计

1.5 本章小结

 

第二章 数据结构导论（4学时）

2.1 数据结构概念

2.2 数据结构知识层次

2.3 算法及算法分析概述

2.4 算法分析示例

2.5 本章小结

 

第三章 线性结构（6学时）

3.1 线性结构定义

3.2 线性结构基本操作

3.3 线性结构表示方法：数组表示（线性表及其基本操作的实现）

3.4 线性结构表示方法：指针表示（线性表及其基本操作的实现）

3.5 线性结构深入（双向链表、循环链表等，若干稍复杂的示例及算法分析）

3.6 线性结构应用：特殊矩阵表示

3.7 本章小结

 

第四章 堆棧与队列（6学时）

4.1 堆栈定义与表示

4.2 堆栈基本操作

4.3 堆栈应用示例（若干不同难度的示例）

4.4 队列定义与表示

4.5 队列基本操作

4.6 队列应用示例（若干不同难度的示例）

4.7 递归应用示例

4.7 本章小结

 

第五章 字符串（4学时）

5.1 字符串定义与表示

5.2 字符串操作

5.3 字符串应用示例

5.4 字符串匹配算法（KMP等算法）

5.5 本章小结

 

第六章 树与二叉树（8学时）

6.1 树的定义与表示i

6.2 树的操作与应用示例

6.3 二叉树定义与表示

6.4 二叉树操作

6.5 二叉树应用示例（树、森林与二叉树转换，Huffman树）

*6.6 二叉树深入（AVL树、B树）

6.7 本章小结

 

第七章 图（8学时）

7.1 图的定义与表示

7.2 图的操作

7.3 图的应用示例（连通、最小生成树、拓扑排序、关键路径和最短路径）

7.4 图的深入（搜索与回溯等）

7.5 本章小结

 

第八章 查找算法（4学时）

8.1 查找算法概述

8.2静态查找（顺序、有序、树、索引等方式）

8.3 动态查找（二叉树、B+树、键树、）

8.4 哈希查找

*8.5 查找算法深入（2-3树，红黑树等）

8.6 本章小结

 

第九章 排序算法（6学时）

9.1 排序算法概述

9.2插入排序

9.3 快速排序

9.4 选择排序（简单、树形、堆）

9.5 归并排序

9.6 基数排序

9.7 本章小结

 

第十章 文件结构（4学时）

10.1 文件结构概述

10.2 顺序文件

10.3 索引文件

10.4 ISAM文件

10.5 散列文件

*10.6 文件结构深入

10.7 本章小结

 

*第十一章 算法设计策略

11.1 算法设计概述

11.2 贪心策略

11.3 分治策略

11.4 动态规划策略

11.5 回溯策略

11.6 分支定界策略

11.7 本章小结