（2021版）
课程编码： |
UY401204 |
课程名称： |
数据结构与算法（C） |
学分： |
2 |
总学时： |
32 |
理论学时 |
32 |
实验学时 |
0 |
适用专业： |
计算机科学与技术、电子信息工程、物联网工程、网络工程等 |
先修课程： |
C语言程序设计 |
后续课程： |
操作系统、数据库原理、人工智能导论等 |
一、课程简介
《数据结构》是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是操作系统、数据库原理、编译原理、软件工程、人工智能等课程的基础。数据结构技术广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。通过本课程的学习，使学生了解软件分析阶段、设计阶段、编码阶段的若干基本问题，明确数据结构的内容包括抽象、实现和评价三个层次，即五个基本组成“要素”逻辑结构，存储结构、基本运算、算法及不同数据结构的比较与算法分析，初步具备分析问题、解决问题的能力，养成良好的程序设计风格。为学生在此领域中继续学习和研究打下坚实的基础。
二、课程目标及要求
本课程主要讲授内容有线性表、树、图、查找、排序和文件。
目标1：掌握数据结构基本原理；掌握线性表、树、图、查找和排序。
目标2：了解广义表、文件及外排序。
目标3：要求学生应能够灵活运用基本数据结构及算法，学会分析研究计算机加工数据对象的特性，掌握数据结构的基本原理，在实际应用中正确运用数据结构的思路与方法，提高分析问题和解决问题的能力。
三、教学内容及安排
第1章 概论 （2学时）
教学目的：
（1）领会数据、数据元素和数据项的概念及其相互间的关系
（2）清楚数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实现
（3）理解抽象数据类型的概念
（4）掌握进行简单算法分析的方法。
教学重点
（1）数据、数据元素、数据项
（2）逻辑结构和数据结构在概念上的联系与区别
（3）运算的概念
（4）存储结构及其三个组成部分
（5）抽象数据类型和数据抽象
（6）评价算法优劣的标准及方法
教学难点
（1）区别算法与程序
（2）逻辑结构、存储结构的联系与区别
（3）抽象数据类型与数据抽象
（4）算法的时间复杂度分析
1.1 数据结构的概念
1.2 抽象数据类型
1.3 算法和算法分析
第2章 线性表 （6学时）
教学目的：
（1）理解线性表的定义及其运算
（2）理解顺序表和链表的定义、组织形式、结构特征和类型说明
（3）掌握在这两种表上实现的插入、删除和按值查找的算法
（4）了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作
教学重点：
（1）线性表的定义及逻辑上的特点
（2）顺序表上插入、删除和定位运算的实现
（3）单链表的结构特点及类型说明
（4）头指针和头结点的作用及区别
（5）指针操作
（6）定位、删除、插入运算在单链表上的实现
（7）循环链表、双链表的结构特点
（8）循环链表、双链表上删除与插入运算的实现
教学难点：
（1）线性表与线性结构的联系与区别
（2）头结点在链表中的作用；指针操作
（3）删除、插入运算中的指针操作顺序
（4）双链表上指针的操作顺序
2.1 线性表逻辑结构（2学时）
2.1 线性表的顺序存储及运算实现（2学时）
2.3 线性表的链式存储和实现（2学时）
第3章 栈和队列 （4学时）
教学目的：
（1）理解栈的定义、特征及在其上所定义的基本运算
（2）掌握在两种存储结构上对栈所施加的基本运算的实现
（3）理解队列的定义、特征及在其上所定义的基本运算
（4）了解在两种存储结构上对队列所施加的基本运算的实现
教学重点：
（1）栈的定义及逻辑特点
（2）栈上的基本运算
（3）栈的顺序存储结构及运算实现
（4）栈的链式存储结构
（5）入栈、出栈等运算在链栈上的实现
（6）队列的定义及逻辑特点
（7）队列上的基本运算
（8）队列的顺序存储结构及其上的运算实现
（9）队列的链式存储结构
（10）入队、出队等运算在链队列上的实现
教学难点：
（1）顺序栈的溢出判断条件
（2）循环队列的队空、队满判断条件
（3）循环队列上的插入、删除操作
3.1 栈
3.2 栈应用举例
3.3 队列
3.4 队列应用举例
第4章 串 （2学时）
教学目的：
（1）了解串的定义
（2）理解和领会串的存储方式
（3）掌握常用的串运算
教学重点：
（1）串的基本概念、基本运算
（2）串的两种存储方式
（3）串的模式匹配算法
教学难点：
（1）串的模式匹配算法
（2）串的基本运算的综合应用
4.1 串及其基本运算
4.2 串的定长顺序存储及基本运算
第5章 数组和广义表 （2学时）
教学目的：
（1）理解多维数组的结构特点和在内存中的两种顺序存储方式
（2）理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算
（3）领会稀疏矩阵的压缩方式和简单运算
（4）了解广义表的定义和基本运算
教学重点：
（1）多维数组的逻辑结构
（2）多维组的两种顺序存储方式
（3）计算给定元素在存储区中的地址
（4）对称矩阵、三角矩阵的压缩存储方式
（5）计算给定元素在存储区中的地址
（6）稀疏矩阵的三元组表表示方法
教学难点：
稀疏矩阵的压缩存储表示下的运算的实现
5.1 多维数组
5.2 特殊矩阵的压缩存储
5.3 稀疏矩阵
5.4 广义表
第6章 树和二叉树 （6学时）
教学目的：
（1）深刻理解二叉树的定义、性质及其存储方法
（2）熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义
（3）理解并掌握二叉树的三种遍历算法
（4）了解二叉树的线索化方法
（5）运用二叉树的遍历方法解决相关的应用问题
教学重点：
（1）二叉树的定义、逻辑特点及五种基本形态
（2）二叉树的五个性质
（3）在二叉树上定义的基本运算
（4）二叉树的链式存储结构及其类型说明
（5）二叉树的顺序存储结构及其类型说明
（6）二叉树链式存储结构的组织方式
（7）二叉树的三种遍历方法及其算法
（8）以遍历为基础在二叉树上实现的几种运算
（9）哈夫曼树和哈夫曼算法
教学难点：
（1）二叉树的递归定义
（2）二叉树链式存储结构的组织方式
（3）三种遍历的主要区别
（4）二叉树上的复杂运算
（5）哈夫曼算法及其应用
6.1 树的定义和基本术语
6.2 二叉树
6.3 遍历二叉树和线索二叉树
6.4 树和森林
6.5 树与等价问题
6.6 赫夫曼树及其应用
第7章 图 （6学时）
教学目的：
（1）理解图的基本概念及术语
（2）掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法
（3）熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列
（4）理解最小生成树的概念，能按Prim算法构造最小生成树
（5）了解拓扑排序、关键路径、最短路径的算法思想
教学重点：
（1）理解图的定义、术语及其含义
（2）了解各种图的邻接矩阵表示法及其类型说明
（3）理解并掌握图的按深度优先搜索遍历方法和按广度优先搜索遍历方法
（4）领会生成树和最小生成树的概念
（5）掌握由Prim算法思想构造最小生成树按Prim算法思想
（6）领会拓扑序列和拓扑排序的概念
（7）了解拓扑排序的算法思想
（8）了解关键路径的算法思想
（9）了解最短路径的算法思想
教学难点：
（1）正确理解与区别图的常用术语
（2）区别图的两种存储结构的不同点及其应用场合
7.1 图的基本概念
7.2 图的存储表示
7.3 图的遍历
7.4 图的连通性
7.5 最小生成树
7.6 最短路径
第9章 查找 （2学时）
教学目的：
（1）了解查找的基本思想及查找成功和不成功的概念
（2）掌握在顺序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相应的平均查找长度
（3）了解二叉排序树、平衡二叉树的各种算法
教学重点：
（1）查找表的基本概念及查找原理
（2）查找表的顺序存储结构、顺序表及其类型说明
（3）查找运算在查找表和有序表上的实现
（4）散列表及散列存储和散列查找的基本思想
（5）各种散列表的组织、解决冲突的方法
教学难点：
（1）理解查找表的逻辑结构是集合，它的运算以查找为核心
（2）理解散列表的建立与查找。
9.1 基本概念与术语
9.2 静态查找表
9.3 动态查找表
9.4 哈希表查找(杂凑法)
第10章 内部排序 （2学时）
教学目的：
（1）领会排序的基本思想和基本概念
（2）理解并掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、步骤、算法及时空效率分析
（3）了解外排序的定义和基本方法
教学重点：
（1）排序基本概念及内排序和外排序、稳定排序和非稳定排序的区别
（2）插入排序的基本思想、基本步骤和算法
（3）冒泡排序的基本思想、基本步骤、算法和算法分析
（4）快速排序的基本思想、基本步骤和算法
（5）直接选择排序的基本思想、基本步骤、算法和算法分析
教学难点：
（1）快速排序算法
10.1 基本概念
10.2 插入排序
10.3 交换排序
10.4 选择排序
10.5 二路归并排序
10.6 基数排序
四、作业、练习和安排与要求
1、课内练习：每章课内练习例题
2、学生课外作业的内容：每章课后练习
五、教材或参考书
1、建议教材：
《数据结构》（C语言版） 严蔚敏 吴伟民编著 清华大学出版社 2018
《数据结构》（C语言版 第2版 附微课视频）严蔚敏 李冬梅 吴伟民 著 人民邮电出版社，2017
《数据结构题集》（C语言版）严蔚敏 吴伟民编著 清华大学出版社 2018
2、建议参考书目：
《数据结构与算法分析》（第2版）[美] 马克·艾伦·维斯（Mark，Allen，Weiss） 著，冯舜玺译 译，机械工业出版社，2019
《数据结构教程-上机实验指导》 （第5版） 李春葆 清华大学出版社，2017
《数据结构与算法》 张铭著 高等教育出版社，2008
《数据结构》 许卓群编著 高等教育出版社 2004
《数据结构》殷人昆 清华大学出版社 2007
六、考核方式、内容及评分标准
考核环节包括平时考核、期末考核两个环节。总成绩包含平时成绩（30%）、期末考试成绩（70%）两部分。
1、平时成绩包含平时作业（40%）、考勤（40%）、课堂表现（20%）四部分。
（1）平时作业：（1）每周布置2-3道题目，平均每次课1道题以上。（2）成绩采用百分制，根据作业完成准确性、是否按时上交、是否独立完成。（3）作业抄袭，未能按时完成，作图不规范，解题思路混乱<60分；独立思考、按时完成，作图比较规范，解题思路比较清晰、步骤比较完整、格式比较合理、答案准确60-75分；独立思考、按时完成，作图比较规范，解题思路比较清晰、步骤比较完整、格式合理、答案准确75-90分；独立思考、按时完成，作图规范，解题思路清晰、步骤完整、格式合理、答案准确90-100分。
（2）考勤：（1）随机点名、学习通、刷卡点名等；（2）缺勤3次以上<60分；缺勤2-3次60-75分；缺勤1次75-90分；全勤90-100分。
（3）课堂表现：（1）随机检查学生上课精神状态、回答问题情况；（2）精神状态较差，回答问题有误<60分；精神状态一般，问题回答一般60-75分；精神状态良好，问题回答较好75-90分；精神状态饱满，回答问题准确90-100分。
2、期末考试成绩
（1）闭卷考试，成绩采用百分制，卷面成绩总分100分。
（2）主要考核学生对数据结构基本知识的掌握能力，学生综合运用所学知识分析问题、解决问题的能力，题型主要有填空题、选择题、判断题、简答题、分析题、算分设计题等。
七、主要参考文献
［1］严蔚敏.数据结构（C语言版）. 北京:清华大学出版社,2018.
［2］严蔚敏,李冬梅,吴伟民 著. 数据结构（C语言版 第2版 附微课视频）. 北京:人民邮电出版社,2017.
［3］李春葆. 数据结构习题与解析（C语言篇）. 北京:清华大学出版社,2000.
［4］殷人昆. 数据结构. 北京:清华大学出版社,2000.
［5］[美]马克·艾伦·维斯（Mark，Allen，Weiss）著,冯舜玺译.北京：机械工业出版社,2019.
［4］ 李春葆.数据结构教程-上机实验指导 （第5版）.北京:清华大学出版社，2017.
