内容发布更新时间 : 2024/5/21 2:06:55星期一 下面是文章的全部内容请认真阅读。
《数据结构》 课程教学大纲
课程 名称 中文 数据结构 英文 Data Structure 60 4 陈香凝 课程编号 适用专业 理论教学学时 实践教学学时 编写日期 5012105014 软件工程 48 12 2015年7月 总学时 学 分 执笔者 讲授 《数据结构（c语言版）》严蔚敏等编著，清华大学出版社，2011.11，ISBN：9787302147510 教材 参考 ? 《数据结构与程序设计-C语言描述（Data Structures& Program Design In C）》 Robert Kruse/C.L. Tondo Bruce Leung，清华大学出版社，2004.1 ISBN：11471002
一、课程性质与目的
1．课程性质：本课程是软件工程本科专业的专业必修课。
2．教学目的：通过本课程的学习，使学生深刻地理解数据结构的逻辑结构和物理结构的基本概
念以及有关算法，能够正确分析计算机加工的数据对象的特性，以便选择合理的数据结构、存储方式并设计或选择相适应的算法，从而培养学生基本的、良好的程序设计技能，编制高效可靠的程序，并为学习《计算机算法分析与设计》、《操作系统》、《编译原理》和《数据库》等课程奠定基础。
二、课程教学内容、要求及学时分配
第一章 绪论 学时：2学时（讲课2学时）
本章讲授要点：了解数据结构的发展简史及其在计算机科学中的地位；掌握本章的基本概念和术语；理解抽象数据类型的表示与实现；掌握算法描述、算法性能分析与度量方法。 1.1什么是数据结构 1.2基本概念和术语
1.3抽象数据类型的表示与实现
1.4算法和算法分析(复杂度计算只讲时间)
1
第二章 线性表 学时：8学时（讲课6学时，实验2学时）
本章讲授要点：了解线性表的抽象类型定义；熟练掌握线性表的两类存储结构（顺序表和链表）上的基本算法：表的初始化、插入、删除等算法；了解基本算法的时间复杂度的计算方法；理解线性表的应用：一元多项式的表示和相加；深刻理解指针与指针所指结点的关系，区别头指针、头结点和开始结点。 2.1线性表的类型定义 2.2线性表的顺序表示和实现 2.3线性表的链式表示和实现 2.4一元多项式的表示及相加
第三章 栈和队列 学时：8学时（讲课4学时，实验4学时）
本章讲授要点：了解栈和队列的抽象类型定义； 熟练掌握顺序栈的基本算法：初始化、出栈、入栈等基本操作；熟练掌握链式队列和循环队列的基本算法：队列初始化、出队列、入队列等操作；掌握栈和队列的应用；理解栈的“上溢”和“下溢”的概念。 3.1栈
3.2栈的应用举例(不讲迷宫问题) 3.3队列
第四章 串 学时：2学时（讲课2学时）
本章讲授要点：了解串的抽象数据类型定义；掌握串的表示和实现；重点掌握串的顺序存储表示、堆分配存储表示和串的块链存储表示. 4.1串的类型定义 4.2串的表示和实现
第五章 数组和广义表 学时：6学时（讲课6学时）
本章讲授要点：了解数组的抽象数据类型定义；掌握多维数组的顺序存储表示和实现；了解十字链表存储；重点掌握矩阵的压缩存储方式；理解广义表的定义及存储结构；掌握广义表的表头和表尾的运算。 5.1数组的定义
5.2数组的顺序存储和表示(不讲基本操作算法) 5.3矩阵的压缩存储(只讲矩阵转置算法) 5.4广义表的定义
5.5广义表的存储结构(可只讲第一种)
2
第六章 树 学时：10学时（讲课8学时，实验2学时）
本章讲授要点：了解树的抽象数据类型定义及相关术语；掌握二叉树的定义、性质、基本操作和存储结构；熟练掌握二叉树的遍历和建立算法；了解线索二叉树的定义和基本操作，掌握树的存储表示及树和森林的遍历；掌握树及森林和二叉树之间的转换关系；理解最优二叉树及其应用：求哈夫曼编码。 重点：二叉树的遍历、赫夫曼树及其应用。 难点：线索二叉树、赫夫曼树及其应用。 6.1树的基本概念和术语 6.2二叉树
6.3遍历二叉树和线索二叉树(不讲线索二叉树的建立及对应的遍历算法) 6.4树和森林 6.5哈夫曼树及其应用
第七章 图 学时：8学时（讲课8学时）
本章讲授要点：了解图的抽象数据类型定义和相关术语，掌握图的存储结构；熟练掌握图的深度优先遍历、广度优先遍历算法；掌握最小生成树，拓扑排序、最短路径和关键路径的算法。 7.1图的定义和术语
7.2图的存储结构(十字链表只了解结构即可，可不讲建立算法) 7.3图的遍历
7.4图的连通性问题(无向图的生成树及有向图强连通算法不讲，普里姆、克鲁斯卡尔讲思想) 7.5有向无环图及其应用(拓扑排序及关键路径讲思想) 7.6最短路径(讲思想)
第八章 查找 学时：8学时（讲课6学时，实验2学时）
本章讲授要点：了解查找和平均查找长度等概念；掌握线性表的基本查找方法及对表的要求；熟练掌握二叉排序树的构造方法及平均查找长度的计算；理解B-树和哈希表的概念；掌握哈希函数的构造方法及处理冲突的方法。 8.1静态查找表
8.2动态查找表(B-树的插入只讲思想，B+只讲概念) 8.3哈希表
3