《数据结构》教学大纲
执笔人：张力 审核人：周枫
课程名称：数据结构 Data Structure
专业： 计算机科学与技术
课程编码： 身什么其境
总学时： 80=64（授课）+16（上机）
选用教材：《数据结构》 唐策善 等编著 高等教育出版社
先行课程：《程序设计方法与C语言》、《离散数学》
一、 地位、任务及目的
本课程是各计算机类专业的核心课程，也是许多非计算机专业的必修课或选修课。它是设计和实现编译程序、操作系统、数据库系统以及其他系统程序和应用程序的重要基础。其主要
的任务通过对计算机处理对象——数据的逻辑结构（关系）、存储结构（关系）及在数据这些结构(关系)上进行的各种操作的算法，在线性、非线性结构上的分析、讨论与研究，达到在利用计算机解决实际问题时，如何分析数据的逻辑结构、有效地选择和设计数据的存储结构及其在此基础上实现对数据运算的算法的目的。同时也达到增强学生软件设计及编程的能力的目的。
二、 犁的组词基本内容及学时分配
灰色的英语怎么说（一） 教学内容
第一篇 概念 （ 4 学时）
● 人才英文教学内容
第1章 概论
1．1 数据结构的概念
1．2 数据结构学习的重要性
1．3算法分析
● 教学要求
本章从人当前面临用计算机解决实际问题的需求，引出用计算机解决实际问题的基本过程，简要地介绍数据、数据结构等基本概念；阐述数据结构是包含数据的逻辑结构、数据的存储结构和实现数据的运算算法等三个方面的内容；简单讨论线性结构和非谈性结构的逻辑特征，数据存储的四种基本方法以及数据运算的涵义。同时引进了算法的概念及评价算法的方法，讲解如何分析程序的时间复杂度和空间复杂度的方法。要求学习这些内容和例子后，希望能对《数据结构》课程的基本实质具有初步的认识和理解。
第二篇 线性结构 12 学时
● 教学内容
第2章 线性表 8学时
2.1线性表的逻辑结构
2.2线性表的顺序存储结构及其操作
2.3线性表的链式存储结构及其操作
2.4线性循环链表和双向链表
2.5多项式相加
2.6静态链表
● 教学要求
线性表是一种最基本、最常用的数据结构，本章要求介绍线性表的定义、运算和各种存储结构的描述方法。重点讨论了线性表的两种存储结构——顺序表和链表，以及在这沟种存储结构上实现的基本运算。
顺序表是用数组实现的，链表是用指针或游标实现的，用指针来实现的链表，因为它的结点空间是动态分配的，故称之为动态链表；用游标摸拟指针实现的链表，由于其结，点空间是静态分配的，所以称之为静态链表。这两种链表又可按链接形式的不同，区分为单链
表、双链表和循环链表。
在实际应用中，对线性表采用哪种存储结构，要视实际问题的要求而定，主要考虑求解算法的时间和空间的复杂度。因此，要求熟练掌握在顺序表和链表上实现的各种基本运算及其时间、空间特性。
● 教学内容
第3章 栈和队列 4 学时 3.1栈 3.2队列
● 教学要求
栈和队列是两种常见的数据结构，它们都是运算受限的线性表。栈的插入和删除均是在栈顶进行，它是后进先出的线性表；队列的插入在队尾，删除在队头，它是先进先出的线性表。在具有后进先出（或先进先出）特性的实际问题中，我们可以使用栈（或队列）这种数据结构来求解。
和线性表类似，依照存储表示的不同，栈有顺序栈和链栈之分，队列有顺序队列和链队列
两种，而实际中使用的顺序队列是循环队列。本章分别介绍顺序栈、循环队列和链队列的五种基本运算，对链栈则讨论了它的插入和删除运算，要求掌握。
另外，栈和队列“上溢”和“下溢”概念及其判别条件应重点领会，要求正确判别栈或队列的空间满而产生的溢出，正确使用栈空或队列空来控制返回。
第三篇 非线性结构 28 学时
● 教学内容
第4章 树 12 学时
5.1树的基本概念
5.2二叉树打印标题
5.3打板遍历二叉树
5.4线索二叉树
5.5树和森林
5.6哈夫曼树及其应用
● 教学要求
树和二又树是一类具有层次或嵌套关系的非线性结构，被广泛地应用于计算机领域，尤其是二叉树最重要、最常用。本章要求着重介绍了二又树的概念、性质和存储表示；二叉树的三种遍历操作；线索二叉树的有关概念和运算。同时介绍了树、森林与二叉树之间的转换；树的三种存储表示法；树和森林的遍历方法。最后讨论了最优二叉树（哈夫曼树）的概念及其应用。
这一章是本课程的重点之一，要求熟练掌握射击练习5.2、5.5各节的内容；熟悉树和二叉树的定义和有关术语；理解和记住二又树的性质；熟练掌握二叉树的顺序存储和链式存储结构．遍历二又树是二叉树中各种运算的基础，能灵活运用各种次序的遍历算法,实现二叉树的其它运算。二又树的线索化，目的是加速遍历过程和有效利用存储空间，熟练掌握在中序线索树中，查找给定结点的中序前趋和后继的方法。并能掌握树和二叉树之间的转换方法，存
储树的双亲链表法、孩子链表法和孩子兄弟链表法，最后，对树和森林的遍历、最优二叉树的特性要理解。
● 教学内容
第5章 图 12 学时
6.1图的基本概念
6.2图的存储结构
6.3图的遍历
6.4图的连通性
6.5无向无环图及其应用
6.6有向无环图及其应用
6.7最短路径及其应用
● 教学要求
图是一种复杂的非线性结构，具有广泛的应用背景。本章要求介绍图的基本概念和两种常用的存储结构，对图的遍历、最小生成树、拓扑排序及关键路径、最短路径等问题做了较详细的讨论，给出了相应的求解算法，并理解它们。 相对而言之，图这一章内容较难，只要求理解本章所介绍的算法实质，掌握图的有关术语和存储表示，面对实际问题时，学会引用本章的有关内容。
第四篇 查找与排序 16 学时
● 教学内容
第6章 查找 8 学时
8.1顺序表的查找
8.2二分查找
8.3分块查找
8.4公共治理理论树表查找
8.5 HASH查找技术
● 教学要求
查找和排序一样，是数据处理中经常使用的一种运算。关于线性表的查找，本章介绍须序查找、二分查找和分块查找三，种方法。若线性表是有序表，则二分查找是一种最快的查找法。关于树表的查找，介绍二叉排序树，AVL树B-树的方法，分别讨论了这三种树表的基本概念、插入和删除操作以及它们的查找过程。 上述方法都基子关键字比较进行的查找。而散列表方法则是直接计算出结点的地址，介绍散列表的概念、散列函数和处理冲突的方法。叙述各种查找方法的平均查找长度。
