1、数据结构课程教学大纲中文课名：数据结构（Python语言描述）英文课名：Data Structure in Python 学 时：72+36 学 分：6学分 先修课程：面向对象Python语言程序设计 适用专业：计算机科学与技术、人工智能、软件工程、网络工程等计算机相关专业一、课程性质与任务数据结构课程属于计算机科学与技术相关专业本科生的主干课、专业基础课程，也是本专业的学位课程。它在计算机类的专业知识结构中起着非常重要的作用，帮助学生培养问题分析、识别判断的能力，并用计算机解决实际问题打下坚实基础。数据结构是理论性和实践性都较强的课程，其理论部分介绍：栈、队列、线性表、二叉树、树和图等经典数
2、据结构的概念和特点，本课程采用 Python语言进行存储表示和算法实现，课程内容上注重研究计算机科学及现实世界中各种数据结构的运用，并讨论计算机中最常见的查找、排序算法的不同实现方法及性能。通过本课程的学习，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应算法，并初步掌握算法的时间分析和空间分析的能力；另外，通过在数据结构实践课程中复杂程序设计的训练，进一步巩固所学的相关理论知识，增强对数据结构概念和原理的理解，培养学生的数据抽象能力以及编写质量高、风格好的应用程序的能力，为后续课程的学习打下良好的理论基础和实践基础。二、教学目标本课程的主要
3、教学环节有理论教学、实验教学，具体教学目标如下：目标1：使学生掌握线性表、栈、队列、串、数组、树、二叉树、图等常见的数据结构的基本概念、特点和存储表示；使学生具有针对复杂工程问题进行分析、比较、选择、优化数据结构（建模）和存储结构的能力。目标2：根据已学的各种不同数据结构的概念和特点，进行存储结构设计和PYTHON语言实现，并完成其基本操作的算法及程序实现。包括各种基础数据结构的算法实现，对一些实际应用设计解决方案，如哈夫曼编码设计、最短路径算法设计、拓扑排序算法设计、不同的查找、排序等操作的算法设计与实现。目标3：学会对算法进行性能分析，用时间复杂度和空间复杂度等指标，分析比较各个算法的性能
4、；进而设计出更高效的算法。目标4：通过对各数据结构及存储实现的学习和分析，对不同逻辑结构、不同存储结构、不同的时间复杂度，不同的查找算法，不同的冲突解决方案，不同的排序算法之间的区别和适用场合进行比较，得出如何合理选择的结论。目标5：了解数据结构和算法相关的新知识和新技术，能以自然语言、流程图和伪语言算法等形式描述新算法，发表自己观点，进行双语沟通和交流。目标6：具有运用现代信息获取方法进行文献、知识检索能力，看懂数据结构领域的学术资料，对数据结构及算法的新发展、新应用有所了解，撰写调研报告，并能清晰汇报所做工作。三、教学内容第1章 Python语言程序设计基础数据结构课程中常用的Python
5、语言知识的总结和概览，主要供学生复习和自学使用。第2章 数据结构概述（建议4学时）教学内容：数据结构的基本概念；数据结构课程研究的内容；算法的基本概念；算法分析。教学重点：数据结构的基本概念；数据的逻辑结构、存储结构以及二者之间的关系；算法及算法的特性；大记号时间复杂度分析。教学难点：抽象数据类型；算法的时间复杂度分析。教学要求：认识到本课程在计算机及相关学科的重要性，明确课程的学习目标及学习方法；理解程序设计的一般过程；理解数据结构和算法在程序设计中的作用；熟练掌握数据结构的基本概念；掌握算法的基本概念、衡量算法好坏的衡量标准，时间复杂度的概念及算法分析的方法；了解Python语言内置结构常
6、用操作的时间性能。 第3章 线性表（建议8学时）教学内容：线性表的定义和基本操作；线性表顺序存储结构及基本操作算法实现；线性表链式存储结构及实现；顺序表和链表各个结构之间的比较。教学重点：顺序存储结构和链接存储结构的基本思想；顺序表和单链表的基本算法；顺序表和单链表基本操作的时间性能；顺序表和链表之间的比较。教学难点：基于单链表的算法设计。教学要求：熟练掌握线性表的逻辑结构，熟练掌握顺序表及其算法实现，熟练掌握单链表及其算法实现，掌握单链表、双向链表、循环链表等线性表的链式实现方案及基本操作算法实现，掌握顺序表和链表各自的优缺点和适用场合。第4章 栈（建议6学时）教学内容：栈的定义和基本操作；
7、栈的顺序和链式存储结构及实现；括号匹配检验、后缀表达式求值、中缀表达式求值、迷宫求解等栈的应用。教学重点：教学重点是栈的后进先出的特性及应用。教学难点：中缀表达式求值等应用。教学要求：熟练掌握栈的操作特性；熟练掌握顺序栈存储结构及实现；掌握栈的应用场合。第5章 队列（建议4 学时）教学内容：队列的定义及基本操作；队列的存储结构及实现，杨辉三角形的输出、迷宫求解等队列的应用；双端队列、优先队列；Python中的队列。教学重点：队列的操作特性；队列的存储及基本操作的实现。教学难点：循环队列的存储方法；循环队列中队空和队满的判定条件。教学要求：熟练掌握队列的操作特性；熟练掌握循环队列存储结构及实现；
8、熟练掌握链队列存储结构及实现；掌握队列的应用；了解双端队列和优先队列。第6章 递归（建议6 学时）教学内容：递归的概念；递归定义的方法；线性表及其算法的递归定义；递归算法举例；递归与栈的关系；递归的工作原理；递归算法的性能分析；递归算法的设计。教学重点：递归的概念；递归定义的方法；递归算法的设计。教学难点：递归算法的设计；递归算法的性能分析。教学要求：掌握递归的概念以及递归与栈的关系；理解递归的工作原理；重点掌握递归算法的设计方法。第7章 串和数组（建议4学时）教学内容：字符串的逻辑结构和存储结构，模式匹配算法；数组的逻辑结构、存储结构及寻址；特殊矩阵的压缩存储方法。教学重点：串的模式匹配算法
9、；二维数组的存储和下标函数；和特殊矩阵的压缩存储和下标函数。教学难点：KMP算法，next函数求解。教学要求：掌握字符串的逻辑结构；理解字符串的存储结构；掌握模式匹配BF算法；理解模式匹配KMP算法；熟练掌握二维数组的存储结构及下标函数；掌握特殊矩阵的压缩存储。第8章 二叉树（建议8学时）教学内容：二叉树的定义、相关概念和基本术语；二叉树的性质；二叉树的存储结构；二叉树的操作；堆与优先级队列；哈夫曼树及哈夫曼编码。教学重点：二叉树的性质；二叉树的二叉链表存储表示；二叉树的遍历及递归算法。教学难点：二叉树的非递归遍历算法；二叉树的建立算法；哈夫曼算法。教学要求：熟练掌握二叉树的定义及基本性质；熟
10、练掌握二叉链表存储结构及其下的遍历递归算法；理解二叉树的其他存储结构；理解遍历的非递归算法；掌握二叉链表下的层次遍历及建立算法；掌握堆的概念和优先队列的操作；掌握哈夫曼树及哈夫曼编码。第9章 树（建议4学时）教学内容：树和森林的概念；树的性质；树的存储结构；树、森林和二叉树之间的转换；树和森林的遍历；树的孩子兄弟链表存储及基本操作实现。教学重点：树与二叉树的转换；树和森林的遍历。教学要求：掌握树和森林的概念、树的性质和树的存储结构；熟练掌握树、森林和二叉树之间的转换；熟练掌握树和森林的遍历，了解树和森林的遍历序列与对应二叉树遍历序列间的关系。第10章 图（建议10 学时）教学内容：图的图的定义
11、和相关术语；图的图的邻接矩阵、邻接表、邻接字典表示；最小生成树；最短路径；有向无环图。教学重点：图的基本术语；图的存储表示；图的遍历；图的经典应用。教学难点：图的遍历算法；Prim算法；Kruskal算法；Dijkstra算法；Floyd算法；拓扑排序算法；关键路径算法。教学要求：掌握图的定义及基本术语；掌握图的深度优先、广度优先遍历方法。熟练掌握图的邻接矩阵存储及算法实现；掌握图的邻接表存储及算法实现；掌握Prim算法、Dijkstra算法、拓扑排序算法；理解Kruskal算法、Floyd算法、AOV网的定义及性质、AOE网的定义及性质、关键路径算法。第11章 查找（建议8学时）教学内容：查
12、找的基本概念及算法性能；线性表下的查找；树表下的查找；散列表下的查找；各种查找方法的比较。教学重点：2种二分查找算法及性能分析；二叉查找树的构造及查找；散列表的构造和查找。教学难点：二叉查找树的删除操作；平衡二叉树的调整。教学要求：掌握查找的基本概念及算法分析方法；熟练掌握顺序查找算法、2种二分查找算法；熟练掌握二叉树查找树的概念，二叉查找树下的查找算法，掌握二叉查找树下的结点插入算法，理解二叉查找树下的结点删除算法。掌握二叉查找树下的查找性能。掌握AVL树的概念，平衡二叉树的调整方法；掌握哈希查找、处理冲突的方法。掌握装载因子的基本概念，哈希表在采用不同冲突方法时的平均查找长度分析。熟练掌握
13、散列的构造和查找；掌握各种查找方法特性。了解建立在关键字比较的基础下的查找算法时间性能的下界。第12章 排序（建议10 学时）教学内容：排序的基本概念及算法性能；插入排序；交换排序；选择排序；归并排序；基数排序；各种排序算法的比较。C+ STL的排序和Timsort排序。教学重点：各种排序算法的基本思想；各种排序算法的执行过程；各种排序算法的实现方法；时间、空间复杂度分析；各种排序算法之间的比较。教学难点：快速排序、堆排序、归并排序等算法及时间复杂度分析。教学要求：理解排序的基本概念；掌握排序算法的性能分析方法；熟练掌握直接插入排序、冒泡排序、快速排序的一次划分、简单选择排序；掌握快速排序、堆
14、排序、筛选法调整堆算法、二路归并排序的2种实现；理解希尔排序和基数排序算法；熟练掌握各种排序算法的特性。分析以比较为基础的排序算法的时间性能的下限，理解各种排序算法在时间、空间、程序效率等方面的比较结果，并做出正确选择。了解C+ STL中的混合排序和Python等语言中的TimSort。四、实验实验学时：36学时实验内容参考：1算法性能分析与比较可包括：变位词判断算法性能比较、Python内置类型常见操作性能验证、生命游戏等。举例：Python列表生成方法性能比较。问题描述（1）设计至少四种不同的方法生成长度为n的列表，分析各算法的时间复杂度；（2）编写程序统计n为不同规模时各个算法所花的时间
15、，对数据进行统计分析，讨论实验数据与理论分析是否一致。实验结果统计分析时可引入matplotlib库，将不同算法随着n的变化所用时间在坐标轴上进行可视化对比。2线性表及其应用可包括学生成绩管理、长整数运算等线性表的应用。举例：长整数运算问题描述（1）实现线性表顺序存储结构、链式存储结构的基本操作，包括顺序表、单链表、双链表、单循环链表、双循环链表等；（2）设计并实现两个长整数的加、减、乘运算。3栈的实现及应用可包括后缀表达式求值、中缀表达式求值、括号匹配等栈的综合应用。举例：中缀表达式求值问题描述中缀表达式是我们熟悉的表达式形式。为了能正确表示运算的先后顺序，中缀表达式中难免要出现括号。假设我
16、们的表达式中只允许有圆括号。读入一个浮点数为操作数的中缀表达式后，对该表达式进行运算。要求中缀表达式以一个字符串的形式读入，可含有加、减、乘、除运算符和左、右括号，并假设该表达式以“#”作为输入结束符。如输入“3.5*(20+4)-1#”，则程序运行结果应为83。4栈与队列综合应用可包括字符串属性判断、小猫钓鱼纸牌游戏、停车场管理等栈和队列的应用。题目：小猫钓鱼纸牌游戏问题描述A和B两个同学玩简单的纸牌游戏，每人手里有n张牌，两人轮流出牌并依次排列在桌面上，每次出掉手里的第1张牌，出牌后如果发现桌面上有跟刚才打出的牌的数字相同的牌，则把从相同的那张牌开始的全部牌按次序放在自己手里的牌的末尾。当
17、一个人手中的牌先出完时，游戏结束，对方获胜。编写程序，利用栈和队列，判断谁是胜者。5二叉树的实现和应用可包括二叉树、Huffman编码、家谱管理等类型应用。举例：二叉树的实现问题描述产生一个菜单驱动的演示程序，用以说明二叉树的使用。元素由单个键组成，键为单个字符。用户能演示的二叉树基本操作至少包括：构造二叉树，按先序、中序、后序、层序遍历这棵二叉树，求二叉树的深度、宽度，统计度为0，1，2的结点数等。二叉树采用链式存储结构。6图的实现和应用可包括图的基本应用、社交网络等类型应用，或图的拓扑排序、最短路径或最小生成树等应用。举例：社交网络模型问题描述设计并实现一个社交网络模型图。要求：（1）每个
18、人的信息是一个顶点，两个人相互认识则构成边。（2）根据输入的任意两个人的信息，给出他们之间的联系路径，最少经过多少人构成联系。（3）可根据自己的创意添加更多的功能。7查找算法性能比较可包括查找相关的基本应用，以及算法性能的比较和分析。举例：查找算法的实现及性能测试与比较（1）设计并测试顺序表下的顺序查找算法；（2）设计并测试识别相等的二分查找算法，要求写出递归和非递归形式；（3）创建二叉排序树，设计并测试二叉排序树下的查找算法。（4）通过实验比较非递归的顺序查找和二分查找在成功查找和失败查找时的绝对运行时间和平均关键字比较次数。（5）通过实验比较非递归二分查找和递归二分查找在成功查找和失败查找
19、时的绝对运行时间。（6）通过实验比较高度分别为n和log2n+1的两棵二叉排序树下，成功查找和失败查找时的绝对运行时间和平均关键字比较次数。方案推荐：（1）为保证在相同的查找表下进行不同查找，线性查找表设定为有序表。二叉排序树通过有序表创建。（2）为分别评测成功和失败查找情况下的性能，可设有序查找表中存放12n-1范围的n个奇数。用查找12n-1范围中的奇数模拟成功查找，用查找02n-2范围中的偶数来模拟失败查找。（3）为了能更客观比较出各个查找算法执行的性能，需要对表中的数据进行较多次的查找，设为m次； 为了做尽量真实的模拟，m次的成功查找或失败查找时查找不同关键字的概率要求相同，即查找成功
20、时，查找1,3,5,2n-1中每个数的概率是一样的；查找失败时，查找0,2,4,6,2n-2中每个数的概率是一样的。（4） n和m的值由用户输入确定。如n为1000，m为10000时，对长度为1000的表作10000次等概率的成功顺序查找。8排序算法性能测试与比较可包括与排序相关的基本应用，以及算法性能的比较和分析。举例：排序算法的实现及性能测试及比较问题描述在书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过具体数据比较各种算法的关键字比较次数和记录移动次数，以取得直观感受。要求：（1）编写程序创建一些整数文件用于排序。创建的这些文件可以根据需要生成不
21、同的长度，如长度分别为20，200和2000，以正序、逆序、随机顺序的方式创建这些文件，通过把所有这些测试数据保存在文件中（而不是每次在测试程序时用随机数生成），可以使用同样的数据去测试不同的方法，因此会更易于比较这些方法的性能。（2）数据表采用顺序存储结构，实现插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序等排序，并对这些算法的实现效率进行比较和分析。（3）排序的指标包含：运行时间，比较次数，移动次数。五、教材及主要参考书1. 主讲教材1 张玉华等编著，数据结构（Python语言描述）-微课视频版，北京：清华大学出版社，2020.112. 参考书目1 严蔚敏，吴伟明编著，数据结构，
22、北京：清华大学出版社，19972 Robert L.Kruse等著，数据结构与程序设计：C+语言描述（影印版），北京：高等教育出版社20013（美）Bradley N.Miller等著，吕能，刁寿钧译，Python数据结构与算法分析（第2版），北京：人民邮电出版社，20194（美）Michael T.Goodrich等著，张晓等译，数据结构与算法Python语言实现，北京：机械出版社，20185 王红梅等编著，数据结构（C+版）（第2版），北京：清华大学出版社，20116 李春葆等，数据结构教程（第5版），北京：清华大学出版社，20177 刘小晶，杜选等，数据结构Java语言描述（第2版），北京：清华大学出版社，20158 裘宗燕，数据结构与算法：Python语言描述，北京：机械出版社，20159（美）Randal E.Bryant，David R.OHallaron著，龚奕利、贺莲译，深入理解计算机系统，北京：机械工业出版社，201610（美）Kenneth A.Lambert著，李军译，数据结构（Python语言描述），北京：人民邮电出版社，201711 张光河，数据结构：Python语言描述，北京：人民邮电出版社，2018
