数据结构基础大纲-何敏.docVIP

《数据结构基础》课程教学大纲 一、课程基本信息 1、课程名称（中/英文）：数据结构基础/Fundamentals of Data Structure 2、课程性质：专业基础理论课 3、周学时/学分： 3/2.5 4、授课对象：通信工程专业、电子信息专业类 5、使用教材：严蔚敏，吴伟民.《数据结构》（C语言版）.清华大学出版社，2005 二、课程简介 本课程是通信工程专业的基础理论课程之一，学分数2.5，周学时3，其中理论课学分1.5， 一、单链表 二、静态链表 三、循环链表 四、双向链表 （本章）复习思考题： 3-7题， 上机实习 1次。 第3章 栈和队（教学时数5，其中理论课时数2，上机时数3） 本章主要介绍线性表的两种特殊结构：栈和队的基本概念、存储结构以及他们的操作和应用。本章的重点和难点是栈和队的存储结构以及他们的操作。 第一节 栈 一、栈的定义 二、栈的表示和实现 第二节 栈的应用举例 一、数制转换 二、括号匹配的检验 三、栈与递归 第三节 队列 一、队列的定义 二、链队列——队列的链式表示和实现 三、循环队列——队列的顺序表示和实现 （本章）复习思考题： 3-7题， 上机实习 1次。 第4章 串（教学时数3，其中理论课时数1，上机时数2） 本章主要介绍串的逻辑结构定义和存储结构以及串的应用。本章的重点和难点是串的匹配算法。 第一节 串的基本概念 一、串定义 二、串的长度，子串，串相等，空格串概念 三、串的最小操作子集 第二节 串的表示和实现 一、定长顺序存储表示 二、堆分配存储表示 三、串的块链存储表示 第三节 串的模式匹配算法 一、求子串位置的定位函数Index(S, T, pos) 二、模式匹配的一种改进算法探讨 （本章）复习思考题： 2-3题， 上机实习1次。 第5章 数组与广义表（教学时数3，其中理论课时数1，上机时数2） 本章重点介绍特殊矩阵如三角矩阵、稀疏矩阵的压缩存储结构及算法以及广义表的定义和实现。本章的重点和难点是矩阵的压缩存储，以及广义表的概念和广义表的存储结构。 第一节 数组的基本概念 一、数组的定义 二、数组的基本操作 第二节 数组的顺序表示和实现 一、顺序存储结构 二、存储地址的计算 三、基本操作的实现 第三节 矩阵的压缩存储 一、特殊矩阵 二、稀疏矩阵的存储 三、稀疏矩阵运算 第四节 广义表 一、广义表的概念 二、广义表存储结构 （本章）复习思考题： 3-5题， 上机实习 1次。 第6章 树和二叉树（教学时数11，其中理论课时数6，上机时数5） 本章主要介绍树的结构和定义、二叉树、森林和哈夫曼树。本章的重点和难点是二叉树的存储结构及遍历，线索二叉树及哈夫曼树的应用。 第一节 树的定义和基本术语 一、树的定义 二、基本术语 结点，结点的度，叶子或终端结点，非终端结点或分支结点，树的度，孩子和双亲，兄弟，祖先和子孙，层次，堂兄弟，深度，森林，有序树和无序树。 第二节 二叉树 一、二叉树的定义 二、二叉树的性质 三、二叉树的存储结构 讨论二叉树的两种存储结构：顺序存储和链式存储。 第三节 遍历二叉树和线索二叉树 本节是本章的重点，讨论遍历二叉树三种遍历的策略，以及线索二叉树的建立和基于线索二叉树的遍历。 一、遍历二叉树 二、线索二叉树 第四节 树和森林 一、树的存储结构 二、森林和二叉树的转换 三、树和森林的遍历 第五节 赫夫曼（Huffman）树及其应用 一、最优二叉树（赫夫曼树） 二、赫夫曼编码 （本章）复习思考题： 3-7个， 上机实习 1次。 第7章 图（教学时数12，其中理论课时间数7，上机时数5） 本章主要介绍图的定义和存储结构，图的连通性和最短路径。本章的重点和难点是图的存储结构与图的遍历，难点是最小生成树、有向无环图及其应用和最短路径问题。 第一节 图的定义和术语 一、抽象数据类型图的定义 二、常用术语 第二节 图的存储结构 一、数组表示法 二、邻接表 三、十字链表 四、邻接多重表示法 第三节 图的遍历 一、深度优先有哪些信誉好的足球投注网站遍历 二、广度优先有哪些信誉好的足球投注网站 讨论采用邻接表表示下的遍历算法。 第四节 图的连通性问题 一、无向图的连通分量和生成树 二、最小生成树 第五节 有向无环图及其应用 一、拓扑排序 二、关键路径 讨论AOV网和AOE网的应用。 第六节 最短路径 一、从某个源点到其余各顶点的最短路径 二、每一对顶点之间的最短路径 讨论迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法的应用。 （本章）复习思考题： 3-7题， 上机实习 1次。 第9章 查找（教学时数6，其中理论课时数3，上机时数3） 本章主要介绍查找的基本概念，静态查找和动态查找及哈希表。本章的重