《数据结构与算法》课程理论教学大纲

课程编号：10301440       授课学时：64学时           学分数：6

先修课程：《程序设计基础》、《离散数学》                    

一、课程性质和任务

《数据结构与算法》是计算科学专业中一门重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，如编译原理、操作系统、数据库、人工智能等课程打下了厚实的知识基础，同时也提供了必要的技能训练。另外，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。因此，《数据结构》课程在计算机应用专业中具有举足轻重的作用。　　本课程的任务是：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。通过学习，初步具备分析问题、解决问题的能力，养成良好的程序设计风格，积聚和提高基本的分析设计能力，为后续课程的学习打下坚实的基础。

二、教学内容和要求

（一）课程基本要求

学生学习本课程之前，应先修C++语言（C语言）程序设计语言、离散数学等课程。

学习了本课程以后，在"识记"、"领会"、"分析应用"三个能力层次上，对学生掌握知识的深度和应用知识的能力的基本要求是：

1）掌握各种数据结构的特点及实现方法和适用范围

2）培养学生阅读、分析和设计算法的能力

3）进行必要的分析设计基本技能训练

4）掌握常规设计方法和技巧

（二）课程的主要内容

1. 绪论（3学时）                       

了解：数据结构的定义和研究的方向；数据结构相关术语；

掌握：数据逻辑结构和存储结构；算法特点、描述方法和复杂度分析方法，抽象数据类型的结构描述。

2.线性表 （7学时）                      

掌握：线性表抽象数据类型描述；顺序表类的和实现；单链表类的定义和实现；线性表的应用方法。

了解：单向循环链表；双向循环链表。

3. 栈和队列  （6学时）                   

了解：栈的定义和基本运算；队列的定义和运算。

掌握：顺序栈类的定义和实现；链栈类的定义和实现；栈的应用。循环队列类的定义和实现；链队列类的定义和实现；队列的应用。

4. 串（3学时）

了解：C风格的串处理，了解串类的定义；KMP算法

掌握：C++String类对象的应用，简单模式匹配算法

5. 数组（3学时）                  

了解：数组的定义和基本运算。

掌握：数组的顺序存储结构。掌握特殊矩阵的压缩、存储和处理与稀疏矩阵的三元组表示。了解稀疏矩阵在三元组存储结构下的运算。  

6.树 （10学时）                            

了解：树结构的定义、特点、基本术语和基本操作。二叉树的定义、操作、性质及其存储结构特点。

掌握：二叉树遍历的递归算法和非递归算法。理解树的存储结构、树与二叉树的转换和森林与二叉树的转换。掌握二叉排序树。掌握哈夫曼树和哈夫曼编码。

 7. 图 （8学时）                             

理解：图的定义和基本术语。

掌握：图的邻接矩阵和邻接表的存储结构。理解图的深度优先搜索DPS和广度优先搜索BFS的遍历算法。理解生成树的概念和最小生成树算法。理解求某源点到其余顶点和每对顶点之间的最短路径方法的算法。

 8. 查找 （6学时）                             

了解：查找的基本思想及查找成功和不成功的概念；二叉查找树、二叉平衡树和B-树查找算法。

掌握：顺序、折半和分块查找算法。哈希表的定义、哈希函数的构造、冲突处理方法、

 9. 排序 （10学时）                             

了解：排序的基本思想和基本概念，基数排序基本思想

掌握：直接插入排序和希尔排序算法；冒泡排序和快速排序等交换排序算法；简单选择排序和堆排序算法；归并排序算法；基数排序算法。

（增加1学时，详细讲解穷举法/蛮力法）

10. 算法基础（6学时）

   了解穷举、减治、分治、动态规划、贪心、回溯等常用基础算法思想，以及NP完全问题。

掌握：常见经典问题的算法设计

11.总结（2学时）

三、教材和参考资料

（一） 建议教材

  李春葆主编，《数据结构教程》第五版，清华大学出版社，2022年

（二）参考书目

（1）William Ford, William  Topp著，刘卫东等译,《数据结构C++语言描述》， 清华大学出版社，2001

（2）严蔚敏，吴伟民编著，《数据结构（C语言版）》清华大学出版社，2002年

（3）耿国华等编著，《数据结构C语言描述》，西安电子科技大学出版社，2002年。

（4）王红梅等，《算法分析与设计》第2版，清华大学出版社，2018年

修 订：梁宝兰   审 定：李文生

《数据结构与算法》课程实验教学大纲

课程编号：10345260                         实验学时：32学时

先修课程：《程序设计基础》《离散数学》   

一、实验教学目的和任务

掌握数据结构的原理和基本内容。以理论为依托，以掌握基础知识为目的，将实践和理论联系紧密，加深学生对数据结构理论知识的理解。

二、实验项目名称及学时分配

三、实验教学内容和要求

实验一：预备实验：

熟悉C语言的基本语法，熟练掌握C语言的输入、输出和文件的读写操作，熟悉Educoder平台。 

实验二：线性表：

熟悉EasyX图形库，掌握线性表的实现和查找、插入和删除操作，并应用线性表解决实际问题，完成Educoder平台实践题目。 

实验三：栈和队列：

掌握栈的顺序存储结构和链式存储结构的实现；掌握栈的顺序存储结构和链式存储结构的实现，并应用栈和队列结构解决实际问题，完成Educoder平台实践题目。 

实验四串结构及其应用：

 掌握C语言或C++语言，串处理的基本操作，掌握串的模式匹配算法，掌握文本文件册查找与替换。 

实验五：树结构及其应用

理解二叉树特别是完全二叉树的性质，掌握二叉树的存储结构（二叉链表）；熟练掌握二叉树的常用操作算法（初始化、插入结点、删除结点、遍历等）；初步掌握二叉树的应用，完成Educoder平台实践题目。 

实验六图结构及其应用：

理解图的数据结构，掌握图的邻接矩阵存储结构，建立邻接矩阵的算法，掌握深度搜索和广度搜索的应用，并应用图解决具体问题等，完成Educoder平台实践题目。 

实验七查找： 

了解各种查找结构，掌握二叉排序树的构建与查找，掌握哈希表的原理，并利用哈希表解决实际问题。  

实验八内部排序：

掌握常用排序方法的基本思想，通过实验加深理解各种排序算法的算法思想以及及其时间和空间复杂度，并利用排序解决实际问题，完成Educoder平台实践题目。

 上述实验主要通过VisualStudio 工具实现，要求提交实验源程序。

四、实验教材和实验指导书

（一） 建议教材

  李春葆主编，《数据结构教程》第六版，清华大学出版社，2022年

修 订：梁宝兰   审 定：李文生

教师授课计划*

                   填表日期： 2022年 8  月  28 日

实践课 程 授 课 计 划

  填表日期： 2022年 8  月  28 日

梁宝兰：

时间：周三上午34节

地点：厚B707

（另：也可通过QQ或电话的联系方式约具体时间和地点进行答疑）

吴舜歆：

时间：周二全天

地点：QQ群

李瑞芳：

时间：周四3-4节  （学习通、微信等网上答疑不限时间）

地点：厚B810

课程综合分=平时成绩*0.3+期末考试成绩*0.7

平时成绩组成百分比）：

（1）educoder平台实训评分 （20%）

（3）基于EasyX的图形化实践项目评分 （20%）

（4）泛雅平台各章客观题作业（约6次）（15%）

（5）泛雅平台的测验（20%）

（6）泛雅平台考勤（20%）

（7）泛雅平台随堂提问互动积分（15%）

期末考试方式：  笔试，闭卷

Educoder实训平台：

https://zsxy.educoder.net/classrooms/aorntif9/shixun_homework