正在播放：数据结构(西北大学)精品课程视频

“数据结构”是信息办理与信息系统专业一门重点专业基础课程，也是学科专业核心专业基础课程之一，属于专业学位必修课程。本课程的教学任务是针对大量的信息处理对象，介绍对象信息与数据表示的各种抽象的、基本的逻辑结构及其上的基本运算操作。通过研究各种基本数据结构内在的逻辑关系和它们在计算机中的存储表示方式，初步建立数据结构上基本运算操作的正确性概念，同时，结合各种典型问题讨论其上的各种基本运算操作及其基本算法，讲授各种数据结构的特点、适用范围，以及对一些基本算法效率的定性和定量分析方法，为后续课程提供必要的数据结构基础。

《数据结构A》在计算机科学中是一门综合性的专业基础课，不仅是一般程序设计的基础，并且是设计和实现操作系统、数据库系统、编译程序及其它系统程序和大型应用程序的重要基础。

课程教学内容与基本要求

（一）绪论（ 3 学时）

1．主要内容： （1）介绍什么是数据结构； （2）基本概念和术语 : 数据、数据元素、数据对象，以及数据结构的定义、逻辑结构、 物理结构（理解）数据类型、抽象数据类型； （3）抽象数据类型的表示与实现； （4）算法和算法分析 : 算法的概念、算法设计的要求以及算法效率的度量。 2．基本要求 （1）了解学习数据结构的重要性； （2）掌握数据结构的定义及相关概念和术语； （3）了解抽象数据类型的定义、表示与实现方法； （4）理解算法的概念、特点并掌握度量其效率的基本方法。 3．自学内容： 类 C语言的书写规范。

（二）线性表（ 6 学时）

1．主要内容： （1）线性表的抽象数据类型定义和相关概念：数据项、记录、文件等； （2）线性表挨次存储表示和基本操作的实现； （3）线性表的链式存储表示和基本操作的实现； （4）稀疏多项式的抽象数据类型定义、表示和加法的实现。

2．基本要求 （1）掌握线性表的定义和特点； （2）熟练掌握线性表的挨次存储表示和插入、删除、查找等实现算法； （3）熟练掌握单链表、循环链表、双向链表三种链表的表示，以及单链表的查找、插 入、删除、创建等实现算法。 3．自学内容： 静态链表。

（三）栈和队列（ 5 学时）

1．主要内容： （1）栈和队列的结构特性和抽象数据类型定义； （2）栈和队列的挨次存储表示和实现； （3）栈和队列的链式存储表示和实现； （4）栈和队列在程序设计中的应用。 2．基本要求 （1）掌握栈和队列两种抽象数据类型的特点； （2）掌握栈的两种存储表示和实现，特别注意栈满栈空的条件； （3）掌握队列的两种存储表示和实现，特别注意队满队空的条件； （4）了解递归算法与栈的关系。 3．自学内容： 链栈，离散事件模拟

（四）串（ 3 学时）

1．主要内容： （1）串的抽象数据类型定义； （2）串的表示和实现 : 定长挨次存储结构和堆分配存储结构； （3）串的各种基本操作的实现及其应用； （4）串的模式匹配操作。 2．基本要求 （1）熟悉串的一些基本操作的定义，并能利用基本操作实现串的其它操作； （2）掌握串的定长挨次存储结构以及基本操作的实现； （3）掌握串的堆分配存储结构以及基本操作的实现； （4）掌握串的简单模式匹配算法，理解 KMP 算法。 3．自学内容： 串操作的应用实例。

（五）数组和广义表（ 4 学时）

1．主要内容： （1）数组的抽象数据类型定义及其挨次表示和实现； （2）特殊矩阵和稀疏矩阵的压缩存储； （3）广义表的抽象数据类型定义和存储结构。 2．基本要求 （1）了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算 方法；

（2）掌握对特殊矩阵进行压缩存储时的下标变换公式； （3）熟悉稀疏矩阵的三元组挨次表存储结构下的一般转置和快速转置算法；了解十字 链表等存储结构； （4）掌握广义表的结构特点、取表头表尾操作，及其存储表示方法。 3．自学内容： 采用十字链表存储结构创建稀疏矩阵。

（六）树和二叉树（ 10 学时）

1．主要内容： （1）树的抽象数据类型定义和基本术语； （2）二叉树的抽象数据类型定义、性质和存储结构； （3）二叉树的遍历； （4）线索二叉树的定义、遍历及线索化二叉树； （5）树的存储结构、树和森林的遍历以及与二叉树的转换； （6）Huffman 树及其应用。 2．基本要求 （1）掌握树型结构的特点和基本术语； （2）熟练掌握二叉树的性质，了解相应的证明方法； （3）了解二叉树的挨次存储结构和链式存储结构，熟练掌握二叉链表存储结构； （4）熟练掌握二叉树三种遍历的递归算法和中序遍历非递归算法，能灵活运用遍历算 法实现二叉树的其他操作； （5）熟练掌握二叉树的线索化过程，以及在中序线索二叉树上找结点的前驱与后继的 方法； （6）熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法； （7）了解 Huffman 树的特性，掌握建立 Huffman 树和 Huffman 编码的方法。 3．自学内容： 先序、后序遍历二叉树非递归算法，层次遍历二叉树算法。

（七）图（ 9 学时）

1．主要内容： （1）图的定义和术语； （2）图的四种存储结构：数组表示法（邻接矩阵） 、邻接表、十字链表和邻接多重表； （3）图的两种遍历策略：深度优先遍历和广度优先遍历； （4）图的连通性和最小生成树； （5）有向无环图及其应用：拓扑排序和关键路径； （6）最短路径问题。 2．基本要求 （1）熟悉图的定义和术语； （2）了解图的存储结构，熟练掌握数组表示法（邻接矩阵）和邻接表存储表示； （3）熟练掌握图的深度优先遍历和广度优先遍历算法； （4）掌握无向连通带权图的最小生成树求解算法； （5）了解有向无环图、 AOV网、 AOE网及其在实际中的应用，熟悉拓扑排序算法和关 键路径算法； （6）熟悉两种最短路径问题求解算法。