数据结构-Python语言描述教案
- 格式：docx
- 大小：85.30 KB
- 文档页数：26
下载文档原格式
合集下载
数据结构课程设计python
数据结构课程设计python一、课程目标知识目标：1. 理解数据结构的基本概念，掌握常用数据结构如列表、元组、字典和集合的特点及应用场景。
2. 学习并掌握栈和队列的操作原理及其在Python中的实现方法。
3. 掌握树和图的基本概念，了解二叉树、遍历算法及图的表示方法。
技能目标：1. 能够运用Python语言实现基本数据结构，并对其进行增、删、改、查等操作。
2. 能够利用栈和队列解决实际问题，如递归、函数调用栈、任务调度等。
3. 能够运用树和图解决实际问题，如查找算法、路径规划等。
情感态度价值观目标：1. 培养学生严谨的逻辑思维，提高分析问题和解决问题的能力。
2. 激发学生对数据结构和算法的兴趣，培养良好的编程习惯。
3. 引导学生认识到数据结构在实际应用中的重要性，增强学习热情和责任感。
课程性质：本课程为高年级数据结构课程，旨在使学生掌握Python语言实现数据结构的方法，提高编程能力和解决问题的能力。
学生特点：学生具备一定的Python编程基础，具有较强的逻辑思维能力，对数据结构有一定的了解。
教学要求：结合实际案例，采用任务驱动法，引导学生通过实践掌握数据结构的基本原理和应用方法。
注重培养学生的动手能力和团队协作精神，提高学生的综合素质。
通过本课程的学习，使学生能够具备独立设计和实现小型项目的能力。
二、教学内容1. 数据结构基本概念：介绍数据结构的概念、作用和分类，结合Python语言特点，分析各类数据结构在实际应用中的优势。
- 列表、元组、字典和集合的原理与应用- 栈与队列的操作原理及实现2. 线性表：讲解线性表的概念，重点掌握顺序表和链表的操作方法。
- 顺序表和链表的实现及操作- 线性表的查找和排序算法3. 树与二叉树：介绍树的基本概念，重点讲解二叉树的结构及其遍历算法。
- 树的基本概念和表示方法- 二叉树的性质、存储结构、遍历方法4. 图：讲解图的基本概念，掌握图的存储结构及遍历方法。
- 图的基本概念和表示方法- 图的遍历算法（深度优先搜索、广度优先搜索）- 最短路径和最小生成树算法5. 算法分析与设计：结合实例，分析算法性能，掌握基本的算法设计方法。
数据结构与算法Python语言描述课程设计
数据结构与算法Python语言描述课程设计一、引言数据结构和算法是计算机程序猿必须掌握的技能。
为了更好地学习和应用数据结构和算法，我们选择Python语言进行描述和设计。
此文档主要介绍针对Python 语言的数据结构与算法课程设计。
二、目的本次课程设计的主要目的是让学员掌握如何利用Python语言设计和实现各种数据结构和算法，并能够应用于实际项目中。
三、设计内容3.1 数据结构部分3.1.1 链表链表是一种常见的数据结构，也是Python语言中常用的数据结构之一。
在本次课程设计中我们主要介绍了如何设计和实现链表，并介绍了在链表中进行插入、删除、查找等操作的方法。
3.1.2 数组数组也是Python语言中常用的一种数据结构，在本次课程设计中我们介绍了如何设计和实现数组，并介绍了在数组中进行插入、删除、查找等操作的方法。
3.1.3 栈和队列栈和队列也是常见的数据结构之一，在本次课程设计中我们介绍了如何设计和实现栈和队列，并介绍了在栈和队列中进行插入、删除、查找等操作的方法。
3.2 算法部分3.2.1 排序算法排序算法是常见的算法，也是Python语言中常用的算法之一。
在本次课程设计中我们主要介绍了几种排序算法，包括冒泡排序、插入排序、选择排序、归并排序以及快速排序，并介绍了这些算法的特点和实现方法。
3.2.2 查找算法查找算法是另一个重要的算法，也是Python语言中常用的算法之一。
在本次课程设计中我们主要介绍了线性查找算法和二分查找算法，并介绍了这些算法的特点和实现方法。
3.2.3 图算法图算法是常见的算法，也是Python语言中常用的算法之一。
在本次课程设计中我们主要介绍了几种图算法，包括最短路径算法、最小生成树算法以及拓扑排序算法，并介绍了这些算法的特点和实现方法。
四、学习方法本次课程设计既适合初学者，也适合有经验的程序猿或研究者。
对于初学者，我们建议先掌握Python语言的基础知识，并按照先后顺序学习文档中介绍的数据结构和算法；对于有经验的程序猿或研究者，可以根据自身需要选择介绍的内容进行学习。
数据结构(Python版)教学大纲 及 教案
数据结构（Python版）教学大纲及教案教学目标：1. 理解Python编程语言中数据结构的基本概念。
2. 掌握常用的数据结构如列表、元组、字典、集合及其操作方法。
3. 学会运用Python实现基本的数据结构操作，并解决实际问题。
教学内容：一、Python编程环境简介1. Python语言的特点和优势2. Python的安装和运行3. Python的基本语法二、数据结构基础1. 数据结构的概念和分类2. 线性结构：列表、元组3. 非线性结构：字典、集合三、列表和元组1. 列表的定义和特点2. 列表的基本操作：索引、切片、添加、删除、排序等3. 元组的定义和特点4. 元组的基本操作：索引、切片、添加、删除等四、字典和集合1. 字典的定义和特点2. 字典的基本操作：键值对添加、删除、修改、查找等3. 集合的定义和特点4. 集合的基本操作：添加、删除、交集、并集、差集等五、数据结构在实际问题中的应用1. 数组和链表的实现2. 栈和队列的实现3. 树和图的实现4. 排序和搜索算法的实现教学方法：1. 讲授法：讲解数据结构的基本概念、分类和操作方法。
2. 示例法：通过实际代码示例演示数据结构的应用。
3. 练习法：让学生通过编写代码练习数据结构的基本操作。
4. 讨论法：分组讨论实际问题，引导学生运用数据结构解决实际问题。
教学评价：1. 课堂参与度：观察学生在课堂上的发言和提问情况，了解学生的学习状态。
2. 代码练习：检查学生编写的代码，评估学生对数据结构操作的掌握程度。
3. 课后作业：布置相关课后作业，巩固学生对数据结构的理解和应用能力。
4. 小组项目：评估学生在小组项目中的表现，考察学生运用数据结构解决实际问题的能力。
六、数组和链表的实现1. 数组的定义和特点2. 使用Python实现数组及其操作3. 链表的定义和特点4. 使用Python实现链表及其操作七、栈和队列的实现1. 栈的定义和特点2. 使用Python实现栈及其操作3. 队列的定义和特点4. 使用Python实现队列及其操作八、树和图的实现1. 树的基本概念和类型2. 使用Python实现二叉树及其操作3. 图的基本概念和类型4. 使用Python实现图及其操作九、排序和搜索算法的实现1. 排序算法的基本概念和类型2. 使用Python实现常见排序算法（如冒泡排序、选择排序、插入排序等）3. 搜索算法的基本概念和类型4. 使用Python实现常见搜索算法（如深度优先搜索、广度优先搜索、二分搜索等）十、项目实践1. 结合实际问题，设计一个简单的数据结构应用项目2. 分组进行项目开发，引导学生运用所学知识解决实际问题3. 评估学生在项目中的表现，考察学生对数据结构知识的掌握和应用能力教学资源：1. 教案、PPT课件和教学代码示例2. Python编程环境（如PyCharm、VSCode等）3. 编程教材和在线教程4. 网络资源和相关论文教学进度安排：1. 每周安排2-3课时进行理论讲解和代码演示2. 每节课后布置相关的编程练习，巩固所学知识3. 每个章节结束后进行小组讨论和项目实践重点和难点解析一、Python编程环境简介补充说明：介绍Python的简洁明了的语法特点，如动态类型、缩进语法等；详细讲解Python的安装和运行过程；举例说明Python的基本语法规则。
数据结构-Python语言描述教学大纲
数据结构课程教学大纲课程代码：课程名称：数据结构开课学期：2学分/学时：4/48+32课程类型：必修适用专业/开课对象：就计算机相关/大一、大二先修课程：计算机导论、程序设计语言（Python）开课单位：团队负责人：责任教授：执笔人：核准院长：一、课程的性质、目的与任务随着近年来计算概念的快速发展，计算学科已经发展成为一个内涵繁杂的综合性学科，至少可以划分为计算机工程（CE）、计算机科学（CS）、信息系统（IS）、信息技术（IT）和软件工程（SE）等五个领域，而且不同领域的人才所应具备的知识结构与能力侧重也不尽相同。
尽管如此，从目前已经完成的部分来看，数据结构在各领域的知识体系中仍然占据着重要的位置。
数据结构是普通高等院校计算机和信息管理等专业的一门必修课程，主要讨论数据的逻辑结构，在计算机中的存储结构以及对其进行的各种处理运算的方法和算法。
二、教学内容及教学基本要求1.绪论（2学时）了解数据结构的基本概念，掌握算法的描述和算法时间复杂度、空间复杂度等内容。
2.线性表（7学时）了解线性表的基本概念和抽象数据类型定义，掌握线性表顺序和链式两种存储方式的表示，基本操作的实现和相应的应用。
3.栈和队列（6学时）掌握栈和队列的基本概念和抽象数据类型定义，栈和队列在顺序存储和链式存储结构下的基本操作和应用。
4.串和数组（5学时）了解串的基本概念和数据类型定义，串的存储结构，基本操作实现和应用等内容；掌握数组的概念。
5.树形结构（7学时）掌握树和二叉树的基本概念，二叉树的性质和存储结构，遍历方法、实现及应用，哈夫曼树的概念和构造方法。
6.图（7学时）了解图的基本概念、抽象数据类型定义、存储结构和遍历方法，掌握最小生成树的基本概念和算法、最短路径相关算法、拓扑排序的概念和实现方法。
7.排序（7学时）掌握排序的基本概念，插入排序、交换排序、选择排序、归并排序等多种排序的原理、实现方法及性能分析。
8.查找（7学时）掌握查找的基本概念，顺序查找、二分查找等查找的原理、实现方法和性能分析，平衡二叉树、哈希表的概念、结构定义和实现方法。
数据结构Python语言描述教案_第八章
在文件 ex080202.py 中定义一个用于顺序表基本操作的 SortSequenceList 类。我们调用 SortSequenceList 类的成员 函数 CreateSequenceListByInput(self,nElement)创建一个序列。调用 BinaryInsertSort(self)对该序列实现折半插入排序， 其算法思路如下。
哨兵用于在查找循环中“监视”下标变量是否越界，哨兵可以和待插入记录直接比较，从而避免了在该循环内 每一次均要检测下标是否越界，使得效率大大提高。
在文件 ex080201.py 中定义一个用于顺序表基本操作的 SortSequenceList 类。 我们调用 SortSequenceList 类的成员函数 CreateSequenceListByInput(self,nElement)创建一个序列。 调用 InsertSort(self)对该序列实现直接插入排序，其算法思路如下。 （1）首先将该序列分为有序部分和无序部分，并默认该序列第一个记录有序。 （2）然后从该序列的第二个记录开始，直到最后一个记录（无序部分）均执行步骤（3）～ （7）。 （3）将该序列中下标为 0 的记录当作哨兵，并将无序部分的第一个记录复制给哨兵。 （4）从当前记录（有序部分的最后一个记录）开始直到哨兵记录执行（5）。 （5）若当前记录大于哨兵记录，则执行（6）；否则执行（7）。 （6）将当前记录后移一位，并转（4）。
教案
～ 学年 第 学期
教学单位
课程名称
课程编号
学
时
适用专业
授课教师
职
称
数据结构 学分 年级
职务
2
本教案由本书作者张光河撰写，若有任何问题可邮件到 guanghezhang@
哨兵用于在查找循环中“监视”下标变量是否越界，哨兵可以和待插入记录直接比较，从而避免了在该循环内 每一次均要检测下标是否越界，使得效率大大提高。
在文件 ex080201.py 中定义一个用于顺序表基本操作的 SortSequenceList 类。 我们调用 SortSequenceList 类的成员函数 CreateSequenceListByInput(self,nElement)创建一个序列。 调用 InsertSort(self)对该序列实现直接插入排序，其算法思路如下。 （1）首先将该序列分为有序部分和无序部分，并默认该序列第一个记录有序。 （2）然后从该序列的第二个记录开始，直到最后一个记录（无序部分）均执行步骤（3）～ （7）。 （3）将该序列中下标为 0 的记录当作哨兵，并将无序部分的第一个记录复制给哨兵。 （4）从当前记录（有序部分的最后一个记录）开始直到哨兵记录执行（5）。 （5）若当前记录大于哨兵记录，则执行（6）；否则执行（7）。 （6）将当前记录后移一位，并转（4）。
教案
～ 学年 第 学期
教学单位
课程名称
课程编号
学
时
适用专业
授课教师
职
称
数据结构 学分 年级
职务
2
本教案由本书作者张光河撰写，若有任何问题可邮件到 guanghezhang@
数据结构(Python版)教学大纲 及 教案
数据结构（Python版）教学大纲及教案第一章：引言1.1 课程介绍数据结构的重要性Python在数据结构中的应用课程目标和学习内容1.2 数据结构的基本概念什么是数据结构数据的抽象和表示常见数据结构类型1.3 Python编程环境Python安装和配置Python编程基础常用数据类型和操作第二章：线性表2.1 线性表的定义和性质线性表的概念线性表的顺序存储结构线性表的链式存储结构2.2 线性表的基本操作线性表的插入和删除操作线性表的查找和排序操作线性表的常见算法实现2.3 Python中的线性表实现Python列表的使用Python元组的使用Python集合的使用第三章：栈和队列3.1 栈的定义和性质栈的概念栈的顺序存储结构栈的链式存储结构3.2 栈的基本操作栈的入栈和出栈操作栈的应用实例栈的算法实现3.3 队列的定义和性质队列的概念队列的顺序存储结构队列的链式存储结构3.4 队列的基本操作队列的入队和出队操作队列的应用实例队列的算法实现第四章：线性表的拓展4.1 双向链表双向链表的概念双向链表的存储结构双向链表的基本操作4.2 栈和队列的拓展栈的应用拓展队列的应用拓展栈和队列的其他变体4.3 Python中的拓展实现Python中的双向链表实现Python中的栈和队列实现第五章：非线性结构5.1 树的概念和性质树的基本概念树的存储结构树的遍历和操作5.2 常见的树结构二叉树binary search tree（BST）平衡树（AVL树）堆（Heap）5.3图的概念和性质图的基本概念图的存储结构图的遍历和操作5.4 Python中的非线性结构实现Python中的树结构实现Python中的图结构实现第六章：排序算法6.1 排序算法的概念与重要性排序算法的定义排序算法的作用排序算法的分类6.2 内部排序算法冒泡排序选择排序插入排序快速排序归并排序堆排序6.3 外部排序算法外部排序的概念外部排序的策略外部排序的实现6.4 Python中的排序算法实现Python内置的排序函数自定义排序函数第七章：查找算法7.1 查找算法概述查找算法的定义查找算法的作用查找算法的分类7.2 内部查找算法顺序查找二分查找分块查找7.3 哈希查找哈希查找的原理哈希函数的设计哈希冲突的解决方法7.4 Python中的查找算法实现Python内置的查找函数自定义查找函数第八章：树的高级应用8.1 平衡树（AVL树）平衡树的概念平衡树的性质平衡树的插入与删除8.2 红黑树红黑树的概念红黑树的性质红黑树的插入与删除8.3 堆（Heap）堆的概念堆的性质堆的插入与删除8.4 Python中的高级树结构实现Python中的平衡树实现Python中的红黑树实现Python中的堆实现第九章：图的算法9.1 图的算法概述图的算法的作用图的算法的分类9.2 深度优先搜索（DFS）DFS的概念DFS的实现DFS的应用9.3 广度优先搜索（BFS）BFS的概念BFS的实现BFS的应用9.4 最短路径算法迪杰斯特拉算法贝尔曼-福特算法Dijkstra算法A算法9.5 Python中的图算法实现Python内置的图库自定义图算法实现第十章：综合案例与实践10.1 数据结构在实际应用中的重要性数据结构在软件开发中的应用数据结构在数据分析中的应用数据结构在中的应用10.2 综合案例分析案例一：社交网络分析案例二：推荐系统案例三：网络爬虫10.3 实践项目项目一：实现一个简单的链表项目二：实现一个平衡二叉树项目三：实现一个图的搜索算法重点和难点解析重点环节1：线性表的基本概念和性质线性表的定义和特点线性表的顺序存储结构及其操作线性表的链式存储结构及其操作重点环节2：栈和队列的基本概念和性质栈的定义、特点和操作队列的定义、特点和操作栈和队列的典型应用场景重点环节3：线性表的拓展双向链表的结构和操作栈和队列的拓展形式Python中的实现方法和技巧重点环节4：非线性结构树的概念、分类和操作图的概念、分类和操作Python中的非线性结构实现方法重点环节5：排序算法和查找算法常见排序算法的原理和实现常见查找算法的原理和实现算法的时间复杂度和空间复杂度分析重点环节6：树的高级应用平衡树（AVL树）的概念和性质红黑树的概念和性质堆（Heap）的概念和性质Python中的高级树结构实现方法重点环节7：图的算法图的算法分类和应用场景深度优先搜索（DFS）和广度优先搜索（BFS）的原理和实现最短路径算法的原理和实现Python中的图算法实现方法重点环节8：综合案例与实践数据结构在实际应用中的重要性和作用社交网络分析、推荐系统和网络爬虫等案例的分析和实践实践项目的选题、实现方法和技巧本文主要分析了“数据结构（Python版）”教学大纲及教案中的重点环节，包括线性表、栈和队列、线性表的拓展、非线性结构、排序算法和查找算法、树的高级应用、图的算法以及综合案例与实践。
数据结构Python语言描述教学大纲
《数据结构——Python语言描述》教学大纲1.课程概要2.课程知识体系及教学要求课程内容是以章节和知识点为基础的体系架构。
教学要求分成三个层次：●掌握，◎理解，○了解。
（一）理论授课第1章绪论：理论2学时+实验2学时●1.1 数据结构概述◎1.2 数据类型概述○1.3 算法概述第2章线性表：理论10学时+实验6学时●2.1 线性表简介●2.2 顺序表●2.3 链表（2.3.1~2.3.4）第3章栈、队列和递归：理论4学时+实验2学时●3.1 栈●3.2 队列◎3.3 递归（3.3.1~3.3.2）第4章串、数组和广义表：理论4学时+实验2学时●4.1 串◎4.2 数组和特殊矩阵（4.2.1~4.2.2）◎4.3 广义表（4.3.1）第5章树、二叉树和森林：理论8学时+实验6学时●5.1树●5.2 二叉树○5.3 森林第6章图：理论6学时+实验6学时●6.1 图的基本概念●6.2 图的存储结构●6.3 图的遍历◎6.4 图的最小生成树○6.5 最短路径第7章查找：理论6学时+实验4学时●7.1 查找的基本概念◎7.2 基于静态查找表的查找（7.2.1~7.2.2）第8章内排序：理论8学时+实验4学时●8.1 排序的基本概念●8.2 插入排序●8.3 交换排序●8.4 选择排序●8.5 归并排序（二）实验课【实验教学环境】：自行搭建Python开发环境。
实验1：算法性能分析⚫实验目的：算法时间和空间复杂度分析⚫实验重点：三种不同语句的算法时间和空间复杂度估计⚫实验内容：在教材中1.5.1中挑选1~2个与学生水平适应的基础实验，然后再1.5.2中挑选1个综合实验，供学有余力的学生实验时使用。
实验2：线性表常用操作⚫实验目的：了解并掌握线性表的基本操作⚫实验重点：使用顺序存储结构和链式存储结构分别实现线性表的基本操作⚫实验内容：在教材中2.5.1中挑选3~5个与学生水平适应的基础实验，然后再2.5.2中挑选2~3个综合实验，供学有余力的学生实验时使用。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
教 学内 容（讲授提纲）
一 栈
栈的概念：栈是一种特殊的线性表，其插入，删除操作只能在表的尾部进行。在栈中允许进行插入，删除操作的一端称为栈顶，另一端称为栈底。
在栈{a0，a1，a2，……，an-1}中a0成为占地元素，an-1成为栈顶元素。通常，栈的插入叫做入栈，站的删除操作交出栈。
栈的抽象数据Python接口包含了栈的主要基本操作，如果要使用这个接口还需要具体的类来实现。栈的Python接口的实现方法主要有以下两种：
算法描述：算法可以采用1）自然语言2）程序设计语言3）伪代码多种语言来描述
P9【例1.3】
三算法分析
算法分析是主要是通过某种方法讨论算法的复杂度，评价算法的效率，以便在解决实际问题时根据实际情况和算法的优缺点对算法进行取舍。
四算法的时间复杂度
是指算法的执行时间虽问题规模的变化而变化的趋势，反映算法执行时间的长短。执行时间是用算法编写的程序在计算机上运行的时间，他是算法中涉及的所有的基本运算的执行时间之和。
单链表的建立操作
1)头插法P26【算法2.9】
2)尾插法P27【算法2.10】
本章节的教学重点、难点
本章重点是熟练掌握顺序表(P17-21)和单链表(P22-27)上实现的各种基本算法及相关的时间性能分析，难点是能够使用本章学到的基本知识设计有效算法与线性表相关的应用问题。
教学方法、教学手段：
1.开始到顺序表中各种操作实现
4)连接操作
5）比较操作 主要步骤如下：
1）确定需要Biblioteka 较的字符的个数n为两个字符串长度的较小值。
2）从下标0至n-1依次进行比较P54-55[【算法 4.4】【例4.1】]
链串的两种存储结构P55图4.2
串的匹配模式
串的模式匹配也叫查找定位，指的是在当前串中的寻找模式串的过程，主要的模式匹配算法有Brute-Force算法和KMP算法。
4）在插入位置及其新的数据元素。
5）表长加1.P19【算法2.1】
删除操作
P20图2.4主要步骤为：
1）判断参数i是否满足i<=i<=curLen-1,若不满足则抛出异常。
2）将第i个数据元素之后的数据元素都向前移动一个存储单元。
3）表长减1.P20【算法2.2】
查找操作
主要步骤为将x与顺序表中的每一个数据元素的值进行比较，若相等，则返回该数据元素的位置；若比较结束未找到等值的数据元素，返回-1.
顺序串基本操作的实现
1）求子串操作；P53【算法 4.1】
2）插入操作 主要步骤如下：
1）判断参数i是否0<=i<=n，若不满足，则抛出异常。
2）重新分配存储空间为n+m，m为插入的字符串str的长度。
3）将第i个及之后的数据元素向后移动m个存储单元。
4）将str插入到字符串从i开始的位置。
3）删除操作P54[【算法 4.2】【算法4.3】]
数据抽象：数据抽象指“定义和实现相分离”，即将一个类型的数据及其上的操作的逻辑含义和具体实现相分离，只考虑执行什么操作，而不考虑怎样实现这些操作。
抽象数据类型：抽象数据类型是从问题的数学模型中抽象出来的逻辑结构定义在逻辑结构上的一组操作，进描述了数据的特性和数据操作的语法规则，隐藏了数据的存储结构和操作的实现细节。P6【例1.2】
4)需要进行存储空间的预先分配，可能会造成空间浪费，但存储密度较高
描述：P17
插入操作：
P19图2.3主要步骤为：
判断顺序表的存储空间是否已满，若已满则抛出异常。
1）判断参数i的值是否满足0<=i<=curLen，若不满足则抛出异常。
2）将插入位置及其之后的所有数据元素后移一个存储位置。
3）在位置i出插入新的数据元素x。
P21【算法2.3】【例2.3】P22【例2.4】
三线性表的链式存储和实现
采用链式存储方式存储的线性表称为链表，链表是用若干地址分散的存储单元存储数据元素。逻辑上相邻的数据元素在屋里位置上不一定相邻，必须采用附加欣喜表示数据元素之间的逻辑关系，因此链表的每一个结点不仅包含元素本身的信息-数据域，而且包含元素之间的逻辑关系的信息，即逻辑上相邻结点地址的指针域。
串的比较规则和字符的比较规则有关，字符的比较规则由所属的字符集的编码决定。
字符串的抽象数据类型Python抽象类包含了串的主要基本操作，如果要使用这个接口，还需要具体的类来实现。串的Python抽象类的实现方法主要有以下两点：
1）基于顺序存储的实现，为顺序串；
2）基于链式存储的实现，为链串。
顺序串
顺序串与顺序表的逻辑结构相同，存储结构类似，均可用数组来存储数据元素。但串具有独特的不同雨线性表的操作，属于特殊类型的线性表。 如P51图4.1
P42图3.12所示为链队列进行入队操作的状态变化。
本章节的教学重点、难点：
本章重点是掌握栈(P31-36)和队列(P37-44)在两种存储结构上实现的基本运算.
教学方法、教学手段：
1．栈的基本概念和顺序栈
2．链栈、中缀表达式求值
使用教具：计算机和投影仪
作业、讨论题、思考题：
P47、48、49
讲授章节
链栈进行出栈操作后的状态变化如图3.5所示P40
P36[【算法3.4】【例3.2】]P37[【例3.3】【例3.4】]
二 队列
队列的基本概念
队列是一种特殊的线性表，其插入操作只能在表的尾部进行，删除操作只能在表头进行。
通常，队列的插入操作交入队，队列的删除操作叫出队。没有数据元素的队列称为空队列。
队列的抽象数据Python接口包含了队列的主要的基本操作，如果要使用这个接口，还需要具体的类来实现。队列的Python抽象类的实现方法主要有以下两种：
链栈基本操作的实现
1）入栈操作，主要步骤如下
1)改造购书值域为x的新结点。
2)改变新结点和首结点指针域，是新结点成为新的栈顶顶点。
链栈进行入栈操作后的状态棉花如图P363.4所示
P36【算法3.3】
2）出栈操作，主要步骤如下
1）判断链栈是否为空，若空则返回null。
2）修改top指针域的值，返回被删结点的数据域值。
五算法的时间/空间复杂度
·.算法分析举例书本P11【例1.4】
本章节的教学重点、难点：
1.重点是数据结构的基本概念
2.难点是时间复杂度分析
教学方法、教学手段：
1.介绍到算法概念
2.算法分析和举例
使用教具：计算机和投影仪
作业、讨论题、思考题：
P12
讲授章节
第二章线性表
授课时数
7
教学目的：
1.介绍线性表的基本概念（P15）和各种存储表示方法(P16-18)
数据的逻辑结构可分为四类：1）集合2）线性结构3）树形结构4）图形结构P3【图1.2】
数据的存储结构可分为四类：1）顺序存储结构2）链式存储结构3）索引存储结构4）散列存储结构
数据操作：1）创建操作2）插入创造3）删除创造4）查找创造5）修改操作6）遍历操作7）销毁操作
数据类型：是一组性质相同的值的集合和定义在此集合上的一组操作的总称。
教案
讲授章节
第1章绪论
授课时数
2
教学目的：
1.介绍数据结构的基本概念（P2）
2.算法的描述(P8)和算法时间复杂度(P10)空间复杂度(P10)
3.要求了解本章介绍的各种基本概念和术语，是全书的基础。
教 学内 容（课程导入）
一数据结构
数据结构基本概念：指的是相互之间存在着一种或者多种关系的数据元素的集合，也叫数据元素类，是数据的一个自己，数据元素是数据对象的一个实例。
1）基于顺序存储的实现，为顺序队列。
2）基于链式存储的实现，为链队列。
顺序队列
顺序队列的存储结构与顺序栈类似，可用数组实现，因为入队和出队操作分别在对为和对手进行，所以增加变量front来只是队首元素的位置，rear指示队尾元素的下一个存储单元的位置。顺序队列进行入队操作的状态变化如P39图3.7进行出对操作后的状态变化P37图3.8
·通常采用算法的渐进分析中的大O表示作为算法时间复杂度的渐进度量值，称为算法的渐进时间复杂度。
·循环语句的时间代价一般可用一下3条原则进行分析：
1）一个循环的时间代价=循环次数每次执行的基本指令数目。
2）多个并列的循环的时间代价=每个循环的时间代价之和。
3）多层嵌套循环的时间代价=每层循环的时间代价值积。
Brute-Force算法
是从主串的第一个字符开始和模式串的第一个字符进行比较，若想等，则继续比较后续字符；否则从主串的第二个字符开始重新和模式串进行比较。以此类推，知道模式串的每个字符一次与朱传的字符相等，匹配成功。P56【算法4.5】
KMP算法
Kmp算法的主要思想是当某次匹配失败时主串的开始标位置不会推推，而是利用部分字符匹配的结果将模式串向右移动较远的距离后再继续进行比较。
2.顺序表算法钟）
使用教具：计算机和投影仪
作业、讨论题、思考题：
P28-30
讲授章节
第三章栈
授课时数
6
教学目的：
1.介绍栈（P31）和队列(P37)的逻辑结构定义
2.两种顺序结构上如何实现栈(P32-36)和队列(P38-46)的基本运算。
3.要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。
1）基于顺序存储的实现，为顺序栈；
2）基于链式存储的实现，为链栈。
顺序栈
顺序栈基本操作的实现入栈操作(P33图3.1)
1）判断顺序栈是否为满，若满则抛出异常。
2）将x存入top所指的存储单元位置。
3）Top加1.P33【算法3.1】P33【算法3.2】P34【例3.1】
链栈
链栈的存储结构 ：P34图3.3
一 栈
栈的概念：栈是一种特殊的线性表，其插入，删除操作只能在表的尾部进行。在栈中允许进行插入，删除操作的一端称为栈顶，另一端称为栈底。
在栈{a0，a1，a2，……，an-1}中a0成为占地元素，an-1成为栈顶元素。通常，栈的插入叫做入栈，站的删除操作交出栈。
栈的抽象数据Python接口包含了栈的主要基本操作，如果要使用这个接口还需要具体的类来实现。栈的Python接口的实现方法主要有以下两种：
算法描述：算法可以采用1）自然语言2）程序设计语言3）伪代码多种语言来描述
P9【例1.3】
三算法分析
算法分析是主要是通过某种方法讨论算法的复杂度，评价算法的效率，以便在解决实际问题时根据实际情况和算法的优缺点对算法进行取舍。
四算法的时间复杂度
是指算法的执行时间虽问题规模的变化而变化的趋势，反映算法执行时间的长短。执行时间是用算法编写的程序在计算机上运行的时间，他是算法中涉及的所有的基本运算的执行时间之和。
单链表的建立操作
1)头插法P26【算法2.9】
2)尾插法P27【算法2.10】
本章节的教学重点、难点
本章重点是熟练掌握顺序表(P17-21)和单链表(P22-27)上实现的各种基本算法及相关的时间性能分析，难点是能够使用本章学到的基本知识设计有效算法与线性表相关的应用问题。
教学方法、教学手段：
1.开始到顺序表中各种操作实现
4)连接操作
5）比较操作 主要步骤如下：
1）确定需要Biblioteka 较的字符的个数n为两个字符串长度的较小值。
2）从下标0至n-1依次进行比较P54-55[【算法 4.4】【例4.1】]
链串的两种存储结构P55图4.2
串的匹配模式
串的模式匹配也叫查找定位，指的是在当前串中的寻找模式串的过程，主要的模式匹配算法有Brute-Force算法和KMP算法。
4）在插入位置及其新的数据元素。
5）表长加1.P19【算法2.1】
删除操作
P20图2.4主要步骤为：
1）判断参数i是否满足i<=i<=curLen-1,若不满足则抛出异常。
2）将第i个数据元素之后的数据元素都向前移动一个存储单元。
3）表长减1.P20【算法2.2】
查找操作
主要步骤为将x与顺序表中的每一个数据元素的值进行比较，若相等，则返回该数据元素的位置；若比较结束未找到等值的数据元素，返回-1.
顺序串基本操作的实现
1）求子串操作；P53【算法 4.1】
2）插入操作 主要步骤如下：
1）判断参数i是否0<=i<=n，若不满足，则抛出异常。
2）重新分配存储空间为n+m，m为插入的字符串str的长度。
3）将第i个及之后的数据元素向后移动m个存储单元。
4）将str插入到字符串从i开始的位置。
3）删除操作P54[【算法 4.2】【算法4.3】]
数据抽象：数据抽象指“定义和实现相分离”，即将一个类型的数据及其上的操作的逻辑含义和具体实现相分离，只考虑执行什么操作，而不考虑怎样实现这些操作。
抽象数据类型：抽象数据类型是从问题的数学模型中抽象出来的逻辑结构定义在逻辑结构上的一组操作，进描述了数据的特性和数据操作的语法规则，隐藏了数据的存储结构和操作的实现细节。P6【例1.2】
4)需要进行存储空间的预先分配，可能会造成空间浪费，但存储密度较高
描述：P17
插入操作：
P19图2.3主要步骤为：
判断顺序表的存储空间是否已满，若已满则抛出异常。
1）判断参数i的值是否满足0<=i<=curLen，若不满足则抛出异常。
2）将插入位置及其之后的所有数据元素后移一个存储位置。
3）在位置i出插入新的数据元素x。
P21【算法2.3】【例2.3】P22【例2.4】
三线性表的链式存储和实现
采用链式存储方式存储的线性表称为链表，链表是用若干地址分散的存储单元存储数据元素。逻辑上相邻的数据元素在屋里位置上不一定相邻，必须采用附加欣喜表示数据元素之间的逻辑关系，因此链表的每一个结点不仅包含元素本身的信息-数据域，而且包含元素之间的逻辑关系的信息，即逻辑上相邻结点地址的指针域。
串的比较规则和字符的比较规则有关，字符的比较规则由所属的字符集的编码决定。
字符串的抽象数据类型Python抽象类包含了串的主要基本操作，如果要使用这个接口，还需要具体的类来实现。串的Python抽象类的实现方法主要有以下两点：
1）基于顺序存储的实现，为顺序串；
2）基于链式存储的实现，为链串。
顺序串
顺序串与顺序表的逻辑结构相同，存储结构类似，均可用数组来存储数据元素。但串具有独特的不同雨线性表的操作，属于特殊类型的线性表。 如P51图4.1
P42图3.12所示为链队列进行入队操作的状态变化。
本章节的教学重点、难点：
本章重点是掌握栈(P31-36)和队列(P37-44)在两种存储结构上实现的基本运算.
教学方法、教学手段：
1．栈的基本概念和顺序栈
2．链栈、中缀表达式求值
使用教具：计算机和投影仪
作业、讨论题、思考题：
P47、48、49
讲授章节
链栈进行出栈操作后的状态变化如图3.5所示P40
P36[【算法3.4】【例3.2】]P37[【例3.3】【例3.4】]
二 队列
队列的基本概念
队列是一种特殊的线性表，其插入操作只能在表的尾部进行，删除操作只能在表头进行。
通常，队列的插入操作交入队，队列的删除操作叫出队。没有数据元素的队列称为空队列。
队列的抽象数据Python接口包含了队列的主要的基本操作，如果要使用这个接口，还需要具体的类来实现。队列的Python抽象类的实现方法主要有以下两种：
链栈基本操作的实现
1）入栈操作，主要步骤如下
1)改造购书值域为x的新结点。
2)改变新结点和首结点指针域，是新结点成为新的栈顶顶点。
链栈进行入栈操作后的状态棉花如图P363.4所示
P36【算法3.3】
2）出栈操作，主要步骤如下
1）判断链栈是否为空，若空则返回null。
2）修改top指针域的值，返回被删结点的数据域值。
五算法的时间/空间复杂度
·.算法分析举例书本P11【例1.4】
本章节的教学重点、难点：
1.重点是数据结构的基本概念
2.难点是时间复杂度分析
教学方法、教学手段：
1.介绍到算法概念
2.算法分析和举例
使用教具：计算机和投影仪
作业、讨论题、思考题：
P12
讲授章节
第二章线性表
授课时数
7
教学目的：
1.介绍线性表的基本概念（P15）和各种存储表示方法(P16-18)
数据的逻辑结构可分为四类：1）集合2）线性结构3）树形结构4）图形结构P3【图1.2】
数据的存储结构可分为四类：1）顺序存储结构2）链式存储结构3）索引存储结构4）散列存储结构
数据操作：1）创建操作2）插入创造3）删除创造4）查找创造5）修改操作6）遍历操作7）销毁操作
数据类型：是一组性质相同的值的集合和定义在此集合上的一组操作的总称。
教案
讲授章节
第1章绪论
授课时数
2
教学目的：
1.介绍数据结构的基本概念（P2）
2.算法的描述(P8)和算法时间复杂度(P10)空间复杂度(P10)
3.要求了解本章介绍的各种基本概念和术语，是全书的基础。
教 学内 容（课程导入）
一数据结构
数据结构基本概念：指的是相互之间存在着一种或者多种关系的数据元素的集合，也叫数据元素类，是数据的一个自己，数据元素是数据对象的一个实例。
1）基于顺序存储的实现，为顺序队列。
2）基于链式存储的实现，为链队列。
顺序队列
顺序队列的存储结构与顺序栈类似，可用数组实现，因为入队和出队操作分别在对为和对手进行，所以增加变量front来只是队首元素的位置，rear指示队尾元素的下一个存储单元的位置。顺序队列进行入队操作的状态变化如P39图3.7进行出对操作后的状态变化P37图3.8
·通常采用算法的渐进分析中的大O表示作为算法时间复杂度的渐进度量值，称为算法的渐进时间复杂度。
·循环语句的时间代价一般可用一下3条原则进行分析：
1）一个循环的时间代价=循环次数每次执行的基本指令数目。
2）多个并列的循环的时间代价=每个循环的时间代价之和。
3）多层嵌套循环的时间代价=每层循环的时间代价值积。
Brute-Force算法
是从主串的第一个字符开始和模式串的第一个字符进行比较，若想等，则继续比较后续字符；否则从主串的第二个字符开始重新和模式串进行比较。以此类推，知道模式串的每个字符一次与朱传的字符相等，匹配成功。P56【算法4.5】
KMP算法
Kmp算法的主要思想是当某次匹配失败时主串的开始标位置不会推推，而是利用部分字符匹配的结果将模式串向右移动较远的距离后再继续进行比较。
2.顺序表算法钟）
使用教具：计算机和投影仪
作业、讨论题、思考题：
P28-30
讲授章节
第三章栈
授课时数
6
教学目的：
1.介绍栈（P31）和队列(P37)的逻辑结构定义
2.两种顺序结构上如何实现栈(P32-36)和队列(P38-46)的基本运算。
3.要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。
1）基于顺序存储的实现，为顺序栈；
2）基于链式存储的实现，为链栈。
顺序栈
顺序栈基本操作的实现入栈操作(P33图3.1)
1）判断顺序栈是否为满，若满则抛出异常。
2）将x存入top所指的存储单元位置。
3）Top加1.P33【算法3.1】P33【算法3.2】P34【例3.1】
链栈
链栈的存储结构 ：P34图3.3