课程简介
course introduction
数据结构是计算机专业一门重要的专业基础课程，是开展计算机业务的技术基础。它是由某一数据元素的集合和该集合中数据元素的关系组成。本课程用面向对象的观点讨论数据结构，主要介绍了数据结构的基本概念，线性表，栈和队列，数组、串和广义表，树，集合，搜索结构，排序和文件10章的内容，分析它们的特点，以及在计算机中的存储方法，和常规操作的实现。 课程以c 语言作为算法的描述工具，强化数据结构基本知识和面向对象程序设计基本能力的训练，目的是使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计的实践与训练，培养学生的数据抽象能力和程序设计的能力，为以后的专业课程学习打下坚实的基础。
教学大纲
teaching syllabus
单元一:数据结构和算法的相关概念
1. 数据结构的一些基本概念:数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等。
2. 抽象数据类型。
3. 描述算法所用的c 语言中的一些有关问题。
4. 算法时间复杂度和空间复杂度的分析。
单元二:线性表
1. 线性表的基本概念和类型定义
2. 线性表的顺序存储结构
3. 线性表的链式存储结构
(1) 单链表的查找、插入和删除
(2) 循环链表的查找、插入和删除
(3) 双向链表的查找、插入和删除
单元三:栈和队列
1. 栈的类型定义
2. 栈的顺序存储和链接存储的表示
3. 在栈的顺序存储和链接存储上进行各种栈操作的算法
4. 栈的应用分析
(1)表达式求值问题的分析及算法设计
(2)迷宫问题的求解分析及算法设计
5. 队列的类型定义
6. 队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法
单元四:数组、串与广义表
1．特殊矩阵的定义、存储和运算
2．串的概念(包括 串, 空串 ,子串, 串的长度).
3．串的存储结构(静态存储和动态存储的方法)
4．掌握c/c 中有关串的常用函数并能运用到实际的问题解决中。
5．广义表的定义、存储和运算
单元五: 树
1. 树的定义、性质和表示方法
2. 二叉树的定义、性质和存储结构
3. 二叉树的各种遍历方法及算法的实现
4. 建立二叉树、输出二叉树、求二叉树深度等的操作方法及算法的实现
5. 树的存储结构，进行前序遍历、中序遍历、后序遍历和按层遍历的方法及算法的实现
6. 进行树与二叉树的转换方法
7. 哈夫曼树的定义、构造哈夫曼树、哈夫曼编码的方法以及算法的实现
单元六:集合与字典
1.集合及其表示
2.并查集与等价类的基本概念及算法设计思路
3.散列查找的基本概念及算法设计思路的分析与实现
单元七:搜索结构
1. 顺序查找和二分查找的处理策略及算法实现过程
2．索引查找和分块查找的处理策略及算法实现过程
3．二叉树查找树及平衡树的概念及处理策略
单元八:图
1. 图的定义和术语
2. 图的邻接矩阵、邻接表和边集数组表示
3. 图的深度和广度优先搜索遍历的思想及算法实现
4. 图的生成树和最小生成树的思路及算法实现
5. 拓扑排序的思想及算法实现
6．最短路径的思想及算法实现
单元九:排序
1.排序的概念
2.直接插入排序的处理思想及算法设计思路
3.冒泡排序和快排序的处理思想及算法设计思路
4.直接选择排序和堆排序的处理思想及算法设计思路
5．二路归并排序的处理思想及算法设计思路
6．分配排序的处理思想及算法设计思路
单元十:文件、外部排序与搜索
1．文件的基本概念
2．顺序文件，索引文件和散列文件的组织方法和操作方法。
3．外排序的方法
4. b树的概念及操作
