数据结构（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学时）

掌握查找的基本概念，顺序查找、二分查找等查找的原理、实现方法和性能分析，平衡

二叉树、哈希表的概念、结构定义和实现方法。

三、教学方法

本课程教学方法以教师为主导的启发式讲授教学法为主，讨论（提问）式教学为辅，结

合课外学习的教学方法。

1.本课程概念较多，因此教学形式以讲授方式为主。本课程拟采用多媒体PPT的教学方法，

增加课堂信息，浅显通俗地对概念、定义和原理进行解释，增加教学的直观性，教学过程中

注意各个知识点的关联性，以使学生更好地理解课程内容。

2.对课程中关键性概念、设计思想方面的问题可辅以课堂讨论的形式。

3.为加强和落实动手能力的培养，每章课后应安排作业，帮助学生学习和应用。

四、课内外教学环节及基本要求

本课程共48+32个学时，理论48个学时，讲授16周（每周3学时）；实验32个学时。

课外学习要求：

1.做好课前预习，预习时以教材为主，了解相关的概念、定义、原理。预习中认真思考，

以便带着问题主动地听课。

2.课后要复习，有余力的学生复习时还应阅读参考资料，认真整理课堂听课笔记。

3.要求学生课外自主学习，学生课外阅读的参考资料以本大纲所列参考资料为主。

4.认真完成所布置的大作业。

五、考核内容及方式

本课程成绩由平时成绩和期末考核成绩组合而成，课程成绩以百分制计算，分配比例如

下：

1.平时成绩占30%,主要考查作业的完成程度，理论课的出勤率，其中作业占25%,出

勤率占5%。

2.期末成绩占70%,采用考试的考核方式。考试采用闭卷形式，题型为选择题、正确/

错误题、填空题、简答题，以及应用题。

六、持续改进

本课程根据学生作业、课堂讨论、平时考核情况和学生、教学督导等反馈，及时对教学

中不足之处进行改进，并在下一轮课程教学中改进。

七、建议教材及参考资料

建议教材：

[1]吕云翔，郭颖美，孟爻等.数据结构（Python版）[M].北京：机械工业出版社，2020

参考资料：

[1]KennethA.Lambert.数据结构Python语言描述[M].李军，译.北京：人民邮电出版

社,2017.

[2]裘宗燕.数据结构与算法:Python语言描述[M].北京:机械工业出版社,2016.

教案

讲授章节第1章绪论

授课时数2

教学目的：

1.介绍数据结构的基本概念(P2)

2.算法的描述(P8)和算法时间复杂度(P10)空间复杂度(P10)

3.要求了解本章介绍的各种基本概念和术语，是全书的基础。

教学内容（课程导入）

一数据结构

数据结构基本概念：指的是相互之间存在着一种或者多种关系的数据元素的集合，也叫

数据元素类，是数据的一个自己，数据元素是数据对象的一个实例。

数据的逻辑结构可分为四类：1）集合2）线性结构3）树形结构4）图形结构P3【图

1.2]

数据的存储结构可分为四类：1）顺序存储结构2）链式存储结构3）索引存储结构4）

散列存储结构

数据操作：1）创建操作2）插入创造3）删除创造4）查找创造5）修改操作6）遍

历操作7）销毁操作

数据类型：是一组性质相同的值的集合和定义在此集合上的一组操作的总称。

数据抽象：数据抽象指''定义和实现相分离”，即将一个类型的数据及其上的操作的逻

辑含义和具体实现相分离，只考虑执行什么操作，而不考虑怎样实现这些操作。

抽象数据类型：抽象数据类型是从问题的数学模型中抽象出来的逻辑结构定义在逻辑结

构上的一组操作，进描述了数据的特性和数据操作的语法规则，隐藏了数据的存储结构和操

作的实现细节。P6【例1.2】

二算法：

算法的定义：算法是有穷规则的集合，其规则确定一个解决某一特定类型问题的指令序

列，其中每一条指令表示计算机的一个或者多个操作。

算法必须满足五个特性：1）有穷性2）确定性3）可行性4）有输入5）有输出

算法建立在数据结构上，对数据结构的操作需要使用算法来描述。算法设计依赖于数据

的逻辑结构，算法实现依赖于数据的存储结构。

算法描述：算法可以采用1）自然语言2）程序设计语言3）伪代码多种语言来描述

P9【例1.3]

三算法分析

算法分析是主要是通过某种方法讨论算法的复杂度，评价算法的效率，以便在解决实际

问题时根据实际情况和算法的优缺点对算法进行取舍。

四算法的时间复杂度

是指算法的执行时间虽问题规模的变化而变化的趋势，反映算法执行时间的长短。执行时

间是用算法编写的程序在计算机上运行的时间，他是算法中涉及的所有的基本运算的执行时

间之和。

•通常采用算法的渐进分析中的大0表示作为算法时间复杂度的渐进度量值，称为算法

的渐进时间复杂度。

•循环语句的时间代价一般可用一下3条原则进行分析：

1）一个循环的时间代价=循环次数每次执行的基本指令数目。

2）多个并列的循环的时间代价=每个循环的时间代价之和。

3）多层嵌套循环的时间代价=每层循环的时间代价值积。

五算法的时间/空间复杂度

•.算法分析举例书本P11【例1.4】

本章节的教学重点、难点：

1.重点是数据结构的基本概念

2.难点是时间复杂度分析

教学方法、教学手段：

1.介绍到算法概念

2.算法分析和举例

使用教具：计算机和投影仪

♦作业、讨论题、思考题：

P12

讲授章节第二章线性表

授课时数7

教学目的：

1.介绍线性表的基本概念（P15）和各种存储表示方法（P16-18）

2.定义在逻辑结构上的各种基本运算及在存储结构上如何实现这些基本运算

(P18-22)。

3.要求在这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储

结构设计出相应的有效算法，解决与线性表相关的实际问题。

教学内容（讲授提纲）

-线性表

线性表的Python抽象类的实现方法主要有以下两种

1）基于顺序存储的实现2）基于链式存储的实现。

二线性表的顺序存储

定义：是把线性表中的所有元素按照其逻辑顺序依次存储到计算机的内存单元中指定存

储位置开始的一块连续的存储空间中，成为顺序表。PI7图2.2

特点：

1）在线性表中逻辑上相邻的元素在物理存储位置上也同样相邻。

2）可按照数据元素的位序号进行随机存取。

3）进行插入，杀出操作需要移动大量的数据元素。

4）需要进行存储空间的预先分配，可能会造成空间浪费，但存储密度较高

描述：P17

插入操作：

P19图2.3主要步骤为：

判断顺序表的存储空间是否已满，若已满则抛出异常。

1）判断参数i的值是否满足0<=i<=curLen,若不满足则抛出异常。

2）将插入位置及其之后的所有数据元素后移一个存储位置。

3）在位置i出插入新的数据元素X。

4）在插入位置及其新的数据元素。

5）表长加1.P19【算法2.11

删除操作

P20图2.4主要步骤为：

1）判断参数i是否满足i<=i<=curLen-l,若不满足则抛出异常。

2）将第i个数据元素之后的数据元素都向前移动一个存储单元。

3）表长减1.P20【算法2.2】

查找操作

主要步骤为将x与顺序表中的每一个数据元素的值进行比较，若相等，则返回该数据元

素的位置；若比较结束未找到等值的数据元素，返回-1.

P21[算法2.3][例2.3]P22【例2.4]

三线性表的链式存储和实现

采用链式存储方式存储的线性表称为链表，链表是用若干地址分散的存储单元存储数据

元素。逻辑上相邻的数据元素在屋里位置上不一定相邻，必须采用附加欣喜表示数据元素之

间的逻辑关系，因此链表的每一个结点不仅包含元素本身的信息-数据域，而且包含元素之

间的逻辑关系的信息，即逻辑上相邻结点地址的指针域。

单链表

单链表指结点中只包含一个指针域的链表，指针域中储存着指向后继结点的指针。P22

图2.5、2.6

查找操作

其主要步骤为将x与单链表中的每一个数据元素的数据域进行比较，若想等，则返回该

数据元素在单链表中的位置；若比较结束未找到等值的数据元素，返回-1.

P241算法2.4】【算法2.5]

插入操作

主要步骤如下：

1）查找到插入位置的前驱结点，即第i-1个结点。

2）创建数据域值为x的新节点.

3）修改前去结点的指针域为指向新节点的指针，新结点的指针域位指向原第i个结点

的指针。

P25【算法2.6]【算法2.7]

删除操作

主要步骤如下

1）判断单链表是否为空。

2）查找待删除结点的前驱结点。

3）修改前驱结点的指针域为待删除结点的指针域。P26【算法2.8】

单链表的建立操作

1）头插法P26【算法2.91

2）尾插法P27【算法2.10】

本章节的教学重点、难点

本章重点是熟练掌握顺序表（P17-21）和单链表（P22-27）上实现的各种基本算法及相关

的时间性能分析，难点是能够使用本章学到的基本知识设计有效算法与线性表相关的应用问

题。

教学方法、教学手段：

I.开始到顺序表中各种操作实现

2.顺序表算法钟）

使用教具：计算机和投影仪

作业、讨论题、思考题：

P28-30

讲授章节第A-/r-二------,n早*r,栈LI1

授课时数6

教学目的：

1.介绍栈（P31）和队列（P37）的逻辑结构定义

2.两种顺序结构上如何实现栈（P32-36）和队列（P38-46）的基本运算。

3.要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。

教学内容（讲授提纲）

一栈

栈的概念：栈是一种特殊的线性表，其插入，删除操作只能在表的尾部进行。在栈中允

许进行插入，删除操作的一端称为栈顶，另一端称为栈底。

在栈｛aO,al,a2,...,anT｝中aO成为占地元素，anT成为栈顶元素。通常，栈的

插入叫做入栈，站的删除操作交出栈。

栈的抽象数据Python接口包含了栈的主要基本操作，如果要使用这个接口还需要具体的

类来实现。栈的Python接口的实现方法主要有以下两种：

1）基于顺序存储的实现，为顺序栈；

2）基于链式存储的实现，为链栈。

顺序栈

顺序栈基本操作的实现入栈操作（P33图3.1）

1）判断顺序栈是否为满，若满则抛出异常。

2）将x存入top所指的存储单元位置。

3）Top加1.P33【算法3.1]P33【算法3.2]P34【例3.1】

链栈

链栈的存储结构：P34图3.3

链栈基本操作的实现

1）入栈操作，主要步骤如下

1）改造购书值域为x的新结点。

2）改变新结点和首结点指针域，是新结点成为新的栈顶顶点。

链栈进行入校操作后的状态棉花如图P363.4所示

P36【算法3.31

2）出栈操作，主要步骤如下

1）判断链栈是否为空，若空则返回null。

2）修改top指针域的值，返回被删结点的数据域值。

链栈进行出栈操作后的状态变化如图3.5所示P40

P36［【算法3.4】【例3.2］北37［【例3.3】【例3.4】］

二队列

队列的基本概念

队列是一种特殊的线性表，其插入操作只能在表的尾部进行，删除操作只能在表头进行。

通常，队列的插入操作交入队，队列的删除操作叫出队。没有数据元素的队列称为空队

列。

队列的抽象数据Python接口包含了队列的主要的基本操作，如果要使用这个接口，还

需要具体的类来实现。队列的Python抽象类的实现方法主要有以下两种：

1）基于顺序存储的实现，为顺序队列。

2）基于链式存储的实现，为链队列。

顺序队列

顺序队列的存储结构与顺序栈类似，可用数组实现，因为入队和出队操作分别在对为和

对手进行，所以增加变量front来只是队首元素的位置，rear指示队尾元素的下一个存储

单元的位置。顺序队列进行入队操作的状态变化如P39图3.7进行出对操作后的状态变化

P37图3.8

顺序队列之所以会出现“假溢出”（P40图3.9）现象是因为顺序队列的存储单元没有重

复使用机制，为了解决顺序队列因数组下标越界而应起的“溢出”问题，课将顺序序列的首

位项链，形成循环顺序队列。

循环顺序队列进行入队和出对操作后状态变化如P40图3.10P41【例3.5】【例3.6］

链队列是单链表实现，由于入队和出对分别在队尾和队首进行，不存在在队列的任意位

置进行插入和删除的情况，所以不需要设置头结点，只需要将指针front和rear分别指向

对手节点和对为节点，每个节点的指针域指向其后继结点即可。

P42图3.12所示为链队列进行入队操作的状态变化。

本章节的教学重点、难点：

本章重点是掌握栈(P31-36)和队列(P37-44)在两种存储结构上实现的基本运算.

教学方法、教学手段：

1.栈的基本概念和顺序栈

2.链栈、中缀表达式求值

使用教具：计算机和投影仪

作业、讨论题、思考题：

P47、48、49

讲授章节第四章串和数组

授课时数5

教学目的:

1.本章主要是介绍串的基本概念(P50)

2.数据类型定义(P50)

3.串的存储结构，基本操作实现和应用等（P51）。

4.介绍多维数组的逻辑结构特征及存储方式（P60-61）,特殊矩阵和稀疏矩阵的压

缩存储方法（P61-64）。

教学内容（讲授提纲）

-串

串的概念：字符串也叫串，是有字符组成的有限序列，是一种常用的非数值数据。串的

逻辑结构是线性表，串是一种特殊的线性表，其每个数据元素都是一个字符。穿的操作特点

与线性表不同，，主要是对字串进行操作，通过采用顺序存储结构存储。

串的比较规则和字符的比较规则有关，字符的比较规则由所属的字符集的编码决定。

字符串的抽象数据类型Python抽象类包含了串的主要基本操作，如果要使用这个接口，

还需要具体的类来实现。串的Python抽象类的实现方法主要有以下两点：

1）基于顺序存储的实现，为顺序串；

2）基于链式存储的实现，为链串。

顺序串

顺序串与顺序表的逻辑结构相同，存储结构类似，均可用数组来存储数据元素。但串具

有独特的不同雨线性表的操作，属于特殊类型的线性表。如P51图4.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】］

4）连接操作

5）比较操作主要步骤如下：

1）确定需要比较的字符的个数n为两个字符串长度的较小值。

2）从下标0至n-1依次进行比较P54-55［【算法4.4］【例4.1】］

链串的两种存储结构P55图4.2

串的匹配模式

串的模式匹配也叫查找定位，指的是在当前串中的寻找模式串的过程，主要的模式匹配

算法有Brute-Force算法和KMP算法。

Brute-Force算法

是从主串的第一个字符开始和模式串的第一个字符进行比较，若想等，则继续比较后

续字符；否则从主串的第二个字符开始重新和模式串进行比较。以此类推，知道模式串的每

个字符一次与朱传的字符相等，匹配成功。P56【算法4.5】

KMP算法

Kmp算法的主要思想是当某次匹配失败时主串的开始标位置不会推推，而是利用部分字

符匹配的结果将模式串向右移动较远的距离后再继续进行比较。

Kmp模式匹配算法分析

K值的计算「57【算法4.6】

Kmp算法步骤

1）计算模式穿的next□函数值

2）I为主串的比较字符位序号，j为模式串的比较字符位序号。当字符相等时，i,

j分别加1后继续比较；否则i的值不变，j=next［j］,继续比较。

3）重复步骤2）,直到j等于模式串的长度是匹配成功，否则匹配失败。

P58［【算法4.7】【例4.2】【例4.3】］

二数组

数组是n个具有相同数据类型的数据元素构成的集合，数组元素按某种次序存储在地质

连续的存储单元中，是顺序存储的随机存储结构。

数组元素在数组中的位置成为数组元素的下标,用户通过下标可以访问相应的数组元素。

数组的下标的个数是数组的维数，具有一个下标的数组叫一维数组，具有两个下标的数

组叫二维数组。

一维数组的逻辑结构是线性表，多维数组是线性表的扩展。

数组的特性

数组元素被存放在一组地址连续的存储单元里，并且每个数据元素的大小相同，故只要

已知首地址和每个数据元素占用的内存单元大小即可求出数组中任意数据元素的存储地址。

数组的遍历

对二维数组进行遍历操作有两种次序，即行主序和列主序。P61【例4.4】

三特殊矩阵的压缩存储

在科学技术和工程计算的许多领域，矩阵是数值分析问题研究的对象。

本章将以特殊矩阵为例介绍矩阵的压缩存储。

矩阵采用二维数组进行存储，至少占用mxn个存储单元。

三角矩阵的压缩存储

线性压缩存储

使用三角形的二维数组压缩存储

对称矩阵的压缩存储

对角矩阵的压缩存储

稀疏矩阵的压缩存储

1.稀疏矩阵的非零元素三元组P64【算法4.81

矩阵元素的行号，列号和元素值称为钙元素的三元组。

2.稀疏矩阵的十字链表存储P64【例4.5】

本章节的教学重点、难点：

1.中缀表达式转成前缀、后缀表达式，并对两种表达式求值。

2.用递归解决的问题：问题的定义是递归的，数据结构是递归的，以及问题的解法是

递归的，掌握典型问题的算法。将递归算法转为非递归算法，特别是尾递归的消除。

教学方法、教学手段：

使用教具：计算机和投影仪

作业、讨论题、思考题:

P65、P66,P67

讲授章节第五章树形结构

授课时数7

教学目的：

1.介绍树的定义(P68)

2.二叉树的定义和性质(69)

3.存储结构(P71)

4.遍历及算法和应用(P72-79)

5.哈夫曼树及哈夫曼编码(P79-83)等内容。

教学内容(讲授提纲)

-树

树的概念

树是数据元素之间具有层次关系的非线性结构，是由n个结点构成的有限集合，结点数

为0的树叫空树。

树必须满足：

1)有且仅有一个被称为根的结点。

2)其余结点可分为m个互不相交的有限集合，每个集合又构成一棵树，叫根结点的子

树。

树的表示方法有很多种，如树形表示法，文氏图表示法，凹入图表示法和广义表表示法。

见68[图5.1图5.2]

树的术语P69需熟悉

二叉树

二叉树的基本概念

1）普通二叉树

2）满二叉树

3）完全二叉树

二叉树的性质

有五个性质P705.2.2、P70-71[【例5.1][例5.2]]

二叉树的存储结构

二叉树的顺序存储结构：是指将二叉树的各个结点存放在一组地址连续的存储单元中，

所有结点按结点序号进行顺序存储。可以利用5.2.2节总的性质5将二叉树的结点排成线性

序列，将节点存放在下标为对应编号的数组元素中。示意图P71图5.5

二叉树的链式存储结构：是指将二叉树的各个结点随机存放在存储空间中，二叉树的各

结点间的逻辑关系由指针确定。

二叉树的链式存储结构又分为P72[【图5.6]]

1）二叉链式存储结构

2）三叉链式存储结构

二叉树链式存储结构的结点类的描述

二叉树类的描述

二叉树的遍历

二叉树的遍历方法

二叉树通常可划分为三个部分，即根结点，左子树和右子树。根据3个部分的访问顺

序不同，可将二叉树的遍历方法分为：P73[【图5.7]]

1）层次遍历

2）P73先序遍历【算法5.1]

3)P73中序遍历【算法5.2]

4)P73后序遍历【算法5.3]

二叉树遍历操作实现的递归算法

二叉树遍历操作实现的非递归算法

将递归算法转换成非递归算法

•使用临时便利保存中间结果，用循环结构代替递归过程

•利用栈保存中间结果

1)P74先序遍历【算法5.4]

2)P74中序遍历【算法5.51

3)P75后序遍历【算法5.61

4)P75层次遍历【算法5.7]

二叉树遍历算法的应用

二叉树上的查找算法P76【算法5.8]

统计二叉树的结点个数的算法P77【算法5.91

二叉树的深度P77【算法5.10]

二叉树的建立P79[【例5.3][图5.9]]

1)由中序和先序遍历序列建立二叉树P78[【图5.8】【算法5.11]]

2)由标明空子树的先序遍历序列创建二叉树P79[【算法5.12]]

二哈夫曼树及哈夫曼编码

哈夫曼树的基本概念

1结点间的路径

2节点的路径长度

3结点的权

4节点的带权路径长度

5树的带权路径长度

6最优二叉树

哈夫曼树的构造

P81【图5.10]P80【例5.4]

构造哈夫曼树和哈夫曼编码的类的描述

构造哈夫曼树需要从子结点到父结点的操作，译码是需要从父结点到子结点的操作，所

以为了提高算法的效率将哈夫曼树的结点设计为三叉链式存储结构。

构造哈夫曼树P82【算法5.13]

求哈夫曼编码P82【算法5.14]P83【例5.5]

三树和森林

树的存储结构

1树的父母孩子链表

2树的父母孩子兄弟链表

树的遍历规则

树的孩子有限遍历规则有两种

1）树的先序遍历

2）树的后序遍历

树的遍历规则也是递归的

本章节的教学重点、难点：

重点掌握二叉树的遍历算法及其与有关应用（P76-79）

难点是使用本章所学到的有关知识设计出有效算法

解决与树或二叉树相关的应用问题。

教学方法、教学手段：

使用教具：计算机和投影仪

作业、讨论题、思考题：

P84、P85、P86

讲授章节第六章图

授课时数7

教学目的：

1.主要介绍图的基本概念(P87)

2.抽象数据类型定义和存储结构(P89-96),遍历方法(P97-P101)

3.介绍最小生成树的基本概念和算法(P102T04)

4.最短路径的相关算法(P104T07),拓扑排序的概念和实现方法(P107T10)。

教学内容(讲授提纲)

一图概述

图的概念

•无向边

•有向边

•零图

•无向图

•有向图

•完全图P88【图6.16.26.3]

•稠密图

•子图

•生成子图

•邻接点

•顶点的度

•路径

•回路

•连通图

•连通分量

•强连通图

•强连通分量

•生成树和生成森林

•网

图的抽象数据类型描述

二图的存储结构

邻接矩阵

1.图的邻接矩阵的存储结构

2.图的邻接矩阵类的基本操作的实现

1）图的创建【P90算法6.1P91E6.26.3]P916.4]（创建无/有向图，创建

无/有向网）

2）顶点的定位P921算法6.5]

3）查找第一个邻接点P92【算法6.6]

4）查找下一个邻接点P92【算法6.7]

3.邻接矩阵表示图的性能分析P93【例6.1]

邻接表

1.图的邻接表存储结构

2.图的邻接表的基本操作的实现

1）图的创建【算法P95E6.86.9]P96[6.106.11]]（创建无/有向图,创建无/

有向网）

2）在图中插入边节点P96【算法6.12]

3）查找第一个邻接点P96【算法6.13]

4）查找下一个邻接点

三图的遍历

图的遍历概念

图的遍历方式分为

1.广度优先搜索

图的广度优先搜索遵循“先被访问的顶点，其邻接点先被访问”的规则P98【算法

6.14]

2.深度优先搜索

P99[【算法6.15】【例6.2]]P100【例6.3]

P100-101[【例6.4][例6.5]]

四最小生成树

在一个网的所有生成树中权值总和最少的生成树称为最小代价生成树，简称为最小生成

树，最小生成树不一定唯一，需要满足以下三条准则

1)只能使用图中的边构造最小生成树

2)具有n个顶点和n-1条边

3)不能使用产生回路的边。

产生最小生成树的算法主要有两种

Krusakl算法

Prim算法

P1041例6.6]

五最短路径

最短路径的求解问题主要分为两类

1.求某个顶点到其余顶点的最短路径

2.求任意两个顶点间的最短路径

六拓扑排序和关键路径

拓扑排序

主要步骤

1).在AOV网中选择一个没有前去的顶点并输出

2).在AOV网中删除该顶点以及从它出发的弧

3).重复1.2直到AOV网为空，或者剩余子图中不存在没有前驱的顶点，此时说明AOV

网中存在环。

P108【算法6.166.17]

关键路径

由于AOE网中某些活动可以并行进行，故完成整个工程的最短时间即从源点到汇点的最

长路径的长度，这条路径被称为关键路径，构成关键路径的弧即为关键活动

P109-110【算法6.186.19]

本章节的教学重点、难点：

要求学生在熟悉这些内容的基础上

重点掌握图的存储结构和图的两种遍历算法(P89-101))

本章难点是求最小生成树的算法(P102-104)

最短路径(P104-106)

拓扑排序和关键路径算法(P107-110)。

教学方法、教学手段：

使用教具：计算机和投影仪

作业、讨论题、思考题：

P11KP112

讲授章节第七章排序

授课时数7

教学目的:

1.本章目的是介绍五类内部排序方法的基本思想

2.排序过程

3.算法实现

4.时间和空间性能的分析以及各种排序方法的比较和选择。

教学内容（讲授提纲）

一排序概述

排序的基本概念

是指将一组数据按照关键字值的大小（递增或递减）次序进行排列。

排序是线性表，二叉树等数据结构的一种基本操作。

排序算法的性能评价

通常从时间复杂度和空间复杂度两个方面评价排序算法的性能

待排序的记录和顺序表的类描述

二插入排序

直接插入排序

1.直接插入算法的实现P114［【图7.1］【算法7.1］］

2.算法性能分析

1.时间复杂度

2.空间复杂度

3.算法稳定性

希尔排序

1.希尔排序算法的实现P115［【图7.2】【算法7.2】］

2.算法性能分析

1.时间复杂度

2.空间复杂度

3.算法稳定性

三交换排序

冒泡排序

1.冒泡算法的实现P116［【图7.3】【算法7.3】

2.算法性能分析

1.时间复杂度

2.空间复杂度

3.算法稳定性

快速排序

1.快速排序算法的实现P1181图7.47.51P119【算法7.4】

2.算法性能分析P120【例7.1】

1.时间复杂度

2.空间复杂度

3.算法稳定性

四选择排序

直接选择排序

1.直接选择排序算法的实现P121E【图7.6】【算法7.5】］

2.算法性能分析

1.时间复杂度

2.空间复杂度

3.算法稳定性

堆排序

1.堆的定义

是利用完全二叉树特性的一种选择排序

2.用筛选法调整堆

在进行堆排序的过程中，当堆顶元素和堆中的最后一个元素交换位置后根结点和其

子结点的关键字值不再满足堆的含义，需要进行调整。

3.堆排序P123【算法7.7】

4.算法性能分析P123【例7.2】

1.时间复杂度

2.空间复杂度

3.算法稳定性

五归并程序

1.两个相邻有序序列归并P124【算法7.8]

2.一趟归并排序P125[【算法7.9]]

3.二路归并排序P125【算法7.10】

算法性能分析P1