《数据结构(Python语言描述)》教学教案

教学单元：数据结构（本科）课程概述（2学时）

授课班级：

教学内容提要：

1课程简介：地位（考研、软件开发岗位必考），在专业知识体系中的位置，就

业岗位等；

2课程主要内容及学时分配；

3课程考核方式；

4课程学习方法；

5算法的基本概念和术语；

6Java语言编程回顾。

教学目的：

1了解该课程所研究的内容、作用和发展状况，就业岗位，可以考取的证书等；

2了解算法基本概念和术语；

3在Eclipse环境下编辑一个简单的求最大公约数的程序。

教学重点、难点：

1数据结构、算法、算法复杂度的基本概念；

2如何把现实的问题抽象出来，建立模型，设计算法，再分析算法的复杂度，并

选取合适的语言编码实现。

教学方法：

通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。

教学过程设计：

1、利用CC网，介绍课程的资源：老师搭建的hustoj在线评测网站、几本教材的

PPT、Java软件等供他们下载，自学，要求他们主动学习，提供参考资料给他们；

2、介绍学习方法，课堂及作业要求、纪律要求、考核方式等；

3、了解学生：有多少人数准备继续深造（出国，考研等），多少人准备从事软件

开发，自己创业等；

4、介绍课程的作用，在专业课程中的地位，对个人提升的重要性等，特别强调所

有的相关计算机专业的考研以及高级程序员、系统分析师的考试、另外招聘程序

员的面试笔试等都会考相关的算法等；

5、介绍课程的主要内容和学时分配；

6、鼓励他们考取高级证书，提前到招聘会或者招聘网站上了解最新的岗位需求,

提前学些前沿的技术，为就业作准备，介绍一些学生就业情况

7、通过最大公约数、一列数中第k大数等例子，介绍计算机算法可以解决的实际

问题，引出算法、算法评价指标和算法复杂度等基本概念，并要同学举例说明：

现实世界中的有哪些运用计算机算法的地方？

课堂提问：

1、最小公倍数怎么计算？

2、n个数中第k大数，当数字的个数n非常巨大，而k比较小时，采用什么样的算法,

当k的阶和数字个数n相当时，又该如何计算？

小结：

1）初步认识算法基本概念和术语，一定要分清程序和算法是完全不同的两个概

念；

2）了解课程章节的安排规律；

3）基本熟悉Java环境的使用，知道如何在Java中进行算法编程。

作业：习题1（简答「3,7,8）

预习：算法复杂度分析

复习：Java与算法相关的类库和这些类的使用

教学单元：数据结构A——线性表基础(3学时)

授课班级：

教学内容提要：

2线性表的定义、分类和实现

2.1线性表的顺序表示和实现

1)线性表的顺序表示：指的是用一组地址连续的存储单元依次存储线性表的数据

元素。用物理位置来表示逻辑结构。

LOC(ai+i)=LOC(ai)+/

LOC(ai)=LOC(ai)+(i-l)*/

2)顺序表的特点：随机存取

3)顺序表的运算

顺序表容易实现访问操作，可随机存取元素。但是插入、删除操作是需要移动

大量的元素。

2.2线性表的链式表示和实现

2.2.1单链表：

1)单链表概念

2)单链表的存储结构定义

3)单链表的操作：

算法思想：单链表是非随机存取结构。每个元素的位置信息都包含在前驱结

点的信息中，所以取得第i个元素必须从头指针出发寻找。设置一个指针变量指向

第一个结点，然后，让该指针变量逐一向后指向，直到第i个元素。

插入操作：要在数据元素a和b之间插入元素x。

3.2.2掌握循环链表、双链表及静态链表存储结构及其运算实现

教学目的：

1了解线性表和链表、单链表、双向链表的定义；

2了解单链表的存储和操作；

3掌握循环链表、双链表及静态链表存储结构及其运算实现。

教学重点、难点：

1线性表的基本概念；

2单链表的实现，插入、删除和查询操作。

教学方法：

通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。

教学过程设计：

1、介绍线性表的基本概念；

2、介绍线性表的顺序存储和链式存储结构

对比顺序存储和链式存储的内存组织方式，让学生了解要根据实际场景选择

合适的存储结构；

介绍单链表、双向链表的逻辑结构，并画出示意图（黑板）；

3、提问单链表的插入、删除和查询操作如何实现；

4、让学生完成一个简单的链表插入节点和删除节点的程序；

提示学生一定要注意要判断引用不为空。否则引发空指针异常。

5、介绍双向链表的节点定义以及插入、删除和查询操作

课堂提问：

1、能开整数数组大小最大多少？为什么可用内存还有很多？

2、数组（顺序存储结构）插入、删除和查找节点的时间复杂度

3、单链表（链式存储结构）插入、删除和查找节点如何实现？这些操作的时间复

杂度是多少？

小结：

3）初步认识线性表基本概念和术语，一定要分清线性表的线性存储和链式存储

是完全不同的逻辑结构；

4）介绍多种链表的逻辑结构；

3）教会如何实现单链表和双向链表。

作业：预习：有序线性表

复习：常见数据结构

教学单元：《数据结构（本科）》有序线性表广义（6学时）

授课班级：

教学内容提要：

3.4有序线性表

3.4.1有序线性表的顺序存储

4）有序线性表的顺序存储结构的特点

相关概念：顺序存储、数组、二分查找

5）顺序存储结构的优点：

二分查找查找非常高效

6）顺序存储结构的缺点：

增加和删除操作，需要移动大量元素，效率低。

3.4.2有序线性表的链式表示和实现：

4）链式存储结构定义（链表节点）

5）有序链表的操作：

算法思想：单链表是非随机存取结构，所以从头节点出发寻找合适的位置插

入节点。找到第一个比待插入节点值大的节点（假设为节点N）,待插入节点就放

在节点N前面即可。

6）有序链表的作业1——多项式相加

7）有序链表的作业2——多项式相乘

3.5广义表

3.5.1广义表的定义

3.5.2广义表的创建的递归算法

教学目的：

1了解有序线性表的定义和分类；

2掌握有序数组的存储和二分查找操作；

3掌握有序链表的存储结构及其操作实现：插入、更新和删除；

4掌握广义表的存储结构及其操作实现：插入、更新和删除；

教学重点、难点：

1有序数组的二分查找；

2有序链表的实现，插入、删除和查询操作；

3广义表创建的递归算法

教学方法：

通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。

教学过程设计：

1、介绍有序线性表的基本概念；

2、介绍顺序存储和链式存储的逻辑结构，并画出示意图（黑板）；

3、复习书上没有的有序链表的插入、删除和更新操作；

4、提问如何保证插入节点后链表还是有序的；

5、用课件中微软面试题，拓展学生视野，并引发学生的讨论；

微软面试题：一共三道，难度为递进关系。而且环环相扣，对学生掌握链表的

设计和操作，有很大帮助

课堂提问：

提问1：为什么是第一个比待插入节点值大的节点

提问2：如果节点N为链表第一个节点，还要注意什么？

提问3：节点N是否会找不到，找不到怎么办？

提问4：广义表的创建为什么使用递归算法？可不可以不用？

小结：

5）介绍有序线性表基本概念和术语，一定要分清线性表的线性存储和链式存储

是完全不同的逻辑结构；

6）介绍有序线性表的操作，并分析相关的复杂度；

7）教会如何实现二分查找和有序链表；

8）广义表的创建和基本操作

作业：

预习：栈

复习：线性表的插入节点（代码）

教学单元：《数据结构A》栈和队列（栈4学时）

授课班级：

教学内容提要：

1.什么是堆栈？

2.堆栈的存储方式

3.堆栈的操作

4.堆栈的应用

5.实践项目：进制的转换、括号匹配、后缀表达式的计算

教学目的：

1理解堆栈的工作原理

2掌握堆栈的设计与实现

3会使用堆栈进行编程

教学重点、难点：

1堆栈的工作原理

2使用堆栈进行编程

3中缀表达式变后缀表达式以及后缀表达式的计算

教学方法：

通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。

教学过程设计：

1、介绍栈的基本概念；

2、介绍栈的顺序存储和链式存储，并画出示意图(黑板)；

3、利用提问栈的顺序存储和链式存储，栈顶位于哪一端，让学生掌握自己创建栈;

4、介绍括号匹配问题，并给出用栈的解决方法；

5、讲解栈和递归的关系，并让学生测试机房的机器递归最大深度；

6、讲解作业题“迷宫”，突出里面的递归思想；

7、讲解练习题“全排列”和“组合”，进一步消化递归思想；

课堂提问：

提问1：栈的顺序存储和链式存储，栈顶位于哪一端？

提问2：机房的机器，递归最大深度是多少，怎能知道？

提问3：迷宫问题，走回头路怎么办？

提问4：全排列问题的分解，是否能理解？

提问5：组合问题的分解，是否能理解？

小结：

9)介绍栈基本概念和术语，一定要分清栈的顺序存储和链式存储是完全不同的

逻辑结构；

10)介绍栈的操作，并分析相关的复杂度；

11)教会如何用栈解决括号匹配问题；

12)理解栈和递归的关系；

13)掌握常见递归问题的解法

作业：

预习：栈

复习：有序链表

教学单元：《数据结构》树和二叉树（6学时）

授课班级：

教学内容提要：

5树

5.1树的定义和基本术语

结点的度、树的度、儿子结点、父亲结点、兄弟结点

5.2树的表示形式

5.3树形结构的逻辑结构

树形结构的逻辑特征可用树中结点之间的父子关系来描述

树形结构是非线性结构

5.4二叉树

5.4.1二叉树的定义

二叉树的五种基本形态：

5.4.2二叉树的重要性质

性质1、在二叉树中的第i层上最多有的结点数为2i-l个结点。（i2l）

性质2、深度为k的二叉树至多有2k-l个结点（i'l）

性质3、在任意二叉树中，若叶子结点（即度为零的结点）的个数为nO,度

为1的结点个数为nl，度为2的结点个数为n2,则有nO=n2+l

性质4：具有n个结点的完全二叉树树深为log2n+1

性质5、对于完全二叉树，对其结点采用“按层编号”比较方便，即从根结

点开始由上而下逐层给结点编号，同一层的结点由左向右编号。

5.4.3二叉树的存储结构

顺序存储、二叉链表存储和三叉链表存储

5.4.4二叉树的遍历

1）遍历二叉树

三种遍历次序以递归的形式定义：

中序（Inorder）遍历

先序（Preorder）遍历

后序（Proorder）遍历

2）遍历算法的实现

3）遍历算法的应用

4）二叉树的层次遍历

层次遍历的定义、层次遍历的算法实现和层次遍历的应用

教学目的：

1了解树和二叉树的定义；

2了解二叉树的性质和存储结构；

3掌握二叉树的几种遍历；

4掌握利用前序和中序遍历构建二叉树的递归算法

教学重点、难点：

1二叉树二叉链式存储实现

2二叉树遍历的应用

3利用前序和中序遍历构建二叉树

教学方法：

通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。

教学过程设计：

1、介绍树和二叉树的基本概念；

2、介绍树和二叉树的顺序存储和链式存储的实现，并画出示意图（黑板）；

3、讲解完全二叉树的存储原理和实现细节（为后面堆的知识做铺垫）；

4、介绍二叉树常用的三种遍历

讨论二叉树的遍历能否确定一棵二叉树？

举出前序和后序遍历不能确定二叉树的反例

给出利用前序和中序遍历构建二叉树的递归算法，作业题9

5、讲解二叉树的层次遍历；

讨论二叉树的层次遍历，要怎么存储层次和父子信息

课堂提问：

提问1:如何判定完全二叉树？

提问2：能不能给出前序和后序遍历不能确定二叉树的反例？

提问3：老师给出的利用前序和中序遍历构建二叉树的算法，为什么要用递

归？使用递归有什么优点？

小结：

14)介绍二叉树基本概念和术语；

15)介绍二叉树常用的三种遍历和层次遍历;

3)掌握利用前序和中序遍历构建二叉树的算法。

作业：

预习：常用二叉树

复习：队列

教学单元：《数据结构》哈夫曼树（2时）

授课班级：

教学内容提要：

5哈夫曼树

5.1哈夫曼树构造方法

5.1.1最优二叉树概念

1.路径和路径长度

2.结点的权和带权路径长度

3.树的带权路径长度

WPL=^Wix\i

i=l

哈夫曼树构造的步骤如下：

（1）用给定的n个权值{wl,w2,…，wn}对应的n个结点构成n棵二叉树的森

林F={T1,T2,…，Tn},其中每一棵二叉树Ti（1WiWn）都只有一个权值为wi的

根结点，其左、右子树为空。

（2）在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、

右子树，标记新二叉树的根结点权值为其左右子树的根结点权值之和。（3）

从F中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林F中。

（4）重复（2）、（3）操作，直到森林中只含有一棵二叉树为止，此时得

到的这棵二叉树就是赫夫曼树。

5.2哈夫曼编码

前缀编码：任一个字符的编码都不是另一个字符编码的前缀，可利用二叉树

设计前缀编码。

5.3哈夫曼编码的编码方法

二叉树指向左孩子的边编码为1,指向右孩子的边编码为0。每个叶子节点代

表字符（单词）的编码，为从根节点到该节点所经边的编码串。

教学目的:

1了解哈夫曼树和哈夫曼编码的定义；

2了解哈夫曼树的性质和构造方法；

3掌握哈夫曼树的编码方法；

教学重点、难点：

1哈夫曼树存储实现

2哈夫曼树构造方法的编码实现

3哈夫曼树编码的编码实现

教学方法：

通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。

教学过程设计：

1、介绍哈夫曼树和哈夫曼编码的基本概念；

2、介绍哈夫曼树构造方法，并画出示意图(黑板)；

3、讲解哈夫曼树构造方法的代码实现(为后面哈夫曼编码做铺垫)；

4、讲解哈夫曼编码的代码实现；

讨论：采用链式存储好还是顺序存储好？

课堂提问:

有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9。

(1)试画出对应的编码赫夫曼树(要求左子树根结点的权小于等于右子树根结

点的权)。

(2)求出每个字符的赫夫曼编码。

小结：

16)介绍哈夫曼树和哈夫曼编码的基本概念；

17)掌握哈夫曼树构造方法和哈夫曼编码方法

作业：

预习：堆

复习：二叉树

教学单元：《数据结构》堆和堆排序（4时）

授课班级：

教学内容提要：

5哈夫曼树

5.1哈夫曼树构造方法

5.1.1最优二叉树概念

1.路径和路径长度

2.结点的权和带权路径长度

3.树的带权路径长度

WPL=^Wix\i

i=l

哈夫曼树构造的步骤如下：

（1）用给定的n个权值{wl,w2,…，wn}对应的n个结点构成n棵二叉树的森

林F={T1,T2,…，Tn},其中每一棵二叉树Ti（1WiWn）都只有一个权值为wi的

根结点，其左、右子树为空。

（2）在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、

右子树，标记新二叉树的根结点权值为其左右子树的根结点权值之和。（3）

从F中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林F中。

（4）重复（2）、（3）操作，直到森林中只含有一棵二叉树为止，此时得

到的这棵二叉树就是赫夫曼树。

5.2哈夫曼编码

前缀编码：任一个字符的编码都不是另一个字符编码的前缀，可利用二叉树

设计前缀编码。

5.3哈夫曼编码的编码方法

二叉树指向左孩子的边编码为1,指向右孩子的边编码为0。每个叶子节点代

表字符（单词）的编码，为从根节点到该节点所经边的编码串。

教学目的:

1了解哈夫曼树和哈夫曼编码的定义；

2了解哈夫曼树的性质和构造方法；

3掌握哈夫曼树的编码方法；

教学重点、难点：

1哈夫曼树存储实现

2哈夫曼树构造方法的编码实现

3哈夫曼树编码的编码实现

教学方法：

通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。

教学过程设计：

1、介绍哈夫曼树和哈夫曼编码的基本概念；

2、介绍哈夫曼树构造方法，并画出示意图(黑板)；

3、讲解哈夫曼树构造方法的代码实现(为后面哈夫曼编码做铺垫)；

4、讲解哈夫曼编码的代码实现；

讨论：采用链式存储好还是顺序存储好？

课堂提问:

有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9。

(1)试画出对应的编码赫夫曼树(要求左子树根结点的权小于等于右子树根结

点的权)。

(2)求出每个字符的赫夫曼编码。

小结：

18)介绍哈夫曼树和哈夫曼编码的基本概念；

19)掌握哈夫曼树构造方法和哈夫曼编码方法

作业：

预习：堆

复习：二叉树

教学单元：《数据结构》图的基本概念和存储(2学时)

授课班级：

教学内容提要：

1.图的概念

首先介绍“七桥问题”，说明数学模型的重要性

图的概念：有向图、无向图、完全图、度、出度、入度、邻接、邻接点、连通分

量、强连通分量、生成树、第一邻接点、下一邻接点

抽象数据类型定义

图的操作中最重要的4个操作：

GraphLocateVertex(G,v)；

GraphGetVertex(G,v)；

GraphFirstAdj(G,v)；

GraphNextAdj(G,v,w)；

2.图的顺序存储结构一一邻接矩阵表示法

图的邻接矩阵表示法的特点：对于无向图，邻接矩阵一定是一个对称矩阵

行(列)非零元素个数，表示度。对于有向图，矩阵不一定是一个对称矩阵

行非零元素个数，表示出度列非零元素个数，表示入度邻接矩阵的存储空间只和

顶点个数有关，和边数无关。

3.图的邻接表存储结构

图的邻接矩阵表示法(AdjacencyMatrix)也称作数组表示法。它采用两个

数组来表示图：一个是用于存储顶点信息的一维数组；另一个是用于存储图中顶

点之间关联关系的二维数组，这个关联关系数组被称为邻接矩阵。

4.图的存储结构间的相互转换（邻接矩阵转为邻接表的算法、邻接表转为邻接矩

阵的算法）

教学目的：

1.掌握图的基本概念

2.掌握图的存储结构，重点是邻接矩阵和邻接表

3.掌握图的算法，特别是图的生成算法

4.掌握邻接矩阵和邻接表存储结构间的相互转换

教学重点、难点：

1.重点是图的基本概念，存储结构

2.难点是图的存储结构间相互转换的算法

教学方法：

通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。

教学过程设计：

1、介绍图的基本概念；

2、介绍图的两种存储方法，并画出示意图（黑板）；

3、讲解图的基本操作；

4、讲解两种存储方法的转换

课堂提问:

1、一个n个顶点的连通无向图，其边的个数至少为多少？

2、n个顶点的无向图的邻接矩阵至少有多少非零元素？

3、n个顶点的完全有向图含有弧的数目是多少？

4、要连通具有n个顶点的有向图，至少需要多少条弧？

小结：

20）介绍图的基本概念和存储；

21）掌握两种存储方法的转换方法

作业：课本课后练习题

预习：图的连通性

教学单元：《数据结构》图的遍历、连通性和最小生成树

（10时）

授课班级：

教学内容提要：

1.图的遍历

图的遍历（TravellingGraph）:从图中某一个顶点出发，访问图中的其余顶

点，使每个顶点被访问一次且仅被访问一次。

方法：

深度优先遍历

广度优先遍历

（1）深度优先遍历

1）从任一个顶点v出发，访问该顶点；

2）然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和

v有路径相通的顶点都被访问到；

3）此时若图中尚有顶点未被访问，则另选中下一个未被访问的顶点作起始

点，访问该顶点，继续过程2）,直到所有顶点都被访问完。

（2）广度优先遍历

1）从图中某顶点v出发，访问v,之后：

2）依次访问v的各个未曾被访问过的邻接点，然后分别从这些邻接点出发依

次访问它们的未被访问的邻接点，并使“先被访问的顶点的邻接点'先于'

后被访问的顶点的邻接点”被访问，直至图中所有已经被访问的顶点的邻接

点都被访问到；

3）若图中尚有顶点未曾被访问，则另选图中一个未曾被访问的顶点作起点,

访问该顶点，继续过程2）,直至所有顶点被访问完毕。

2.图的连通分量

进入DFS或BFS一次可以求得一个连通分量

3.深度优先生成树和广度优先生成树

采用DFS遍历图所得到的生成树称为深度优先生成树，采用BFS遍历图所得到

的生成树称为广度优先生成树

4.最小生成树

n个顶点网络的生成树有n个结点，nT条分枝。假设网络中有m条边(m2n-l),

用MST表示许多可能的生成树的集合，每棵树中n-1条分枝上的权之和用WG⑴表

示，则使得

WG(Tmin)=Min{WG(T)|TGMST}

的生成树Tmin便是网络的最小生成树。

MST性质

假设N=(V,{E})是一个连通无向网，U是顶点集V的一个非空子集。若(u,v)

是一条具有最小权值的边，其中uGU,veV-U,则必存在一棵包含边(u,v)的

最小生成树。

5.Prim算法

算法思想：假设N=(V,|E|)是连通图，TE是N上最小生成树中边的集合。算

法从U={uO}(uOeV),TE={}开始，重复执行下述操作：在所有ueU,veV—U的边

(u,v)中找一条代价最小的边(uO,vO)并入集合TE,同时vO并入U,直至U=V为止。

此时，TE中必有nT条边，则T=(V,{TE})为N的最小生成树。

教学目的：

1.掌握图的遍历算法：深度优先遍历，宽度优先遍历。

2.了解图的连通性，掌握连通分量的求法

3.掌握生成树的构造方法

4.理解构造生成树的算法

教学重点、难点：

1.重点：图的遍历算法和生成树

2.难点：图的遍历算法的应用

教学方法：

通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。

教学过程设计：

1、介绍图的遍历、连通性和最小生成树的基本概念；

2、介绍图的两种遍历方法，并画出示意图（黑板）；

3、讲解求图的连通性和最小生成树方法（黑板）；

4、求图的遍历、连通性和最小生成树的代码实现；

课堂提问：

图的BFS生成树的树高要小于等于同图DFS生成树的树高，对吗？

如果图有多个连通分量，深度优先遍历如何找出？

Prim算法的时间复杂度是多少？

小结:

22)介绍图的遍历、连通性和最小生成树;

23)掌握图的两种遍历方法；

24)掌握求图的连通性和最小生成树方法

作业：课本课后练习题

一带权无向图的邻接矩阵如下图，试画出它的一棵最小生成树。

011000

101200

110030

020011

003101

000110

如图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有

三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个

边结点的指针。试求：

（1）该带权有向图的图形；

（2）从顶点VI为起点的广度优先遍历的顶点序列及对应的生成树；

（3）以顶点VI为起点的深度优先遍历生成树;

预习：堆

复习：二叉树

教学单元：《数据结构》图的最短路径(6时)

授课班级：

教学内容提要：

1.从某源点到其它各顶点的最短路径。

(1)Dijkstra算法

按路径长度递增的次序来产生最短路径算法

(2)方法：把V分成两组

S：己求出最短路径的顶点的集合

V-S：尚未确定最短路径的顶点集合,将V-S中顶点按最短路径递增的次序加入到S

(3)步骤：

(1)邻接矩阵arcs来表示带权的有向图，arcs[i][J]表示〈vi,vj＞上的权值。若＜vi,

vj＞eE,则置arcs[i][j]=8。S为已找到从v出发的最短路径的终点集合，初态为空。

(2)选择vj,使D[j]=min{D[i]|viGV-S}vj就是当前求得的一条从v出发的最短

路径，并令S-SU{j}

(3)从v出发到集合V-S上任一顶点vk可达的最短路径，有

D[k]=min{D[k],D[j]+arcs[i][k]}

(4)重复(2)、(3)直到S=V。

2.每一对顶点之间的最短路径

方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次一T(n)=O(n3)

方法二：弗洛伊德(Floyd)算法

(1)Floyd算法思想

逐个顶点试探法

求最短路径步骤

初始时设置一个n阶方阵，令其对角线元素为0,若存在弧则对应元

素为权值；否则为8

逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之;

否则，维持原值

所有顶点试探完毕，算法结束

(2)Floyd算法

voidShortestPath_Floyed(GraphG,PathMatrixP[],DistanceMatrixD)

{〃用Floyed算法求有向图G中各对顶点v和w之间最短路径P[v][w],及其带权路

//径长度D[v][w]。若P[v][w][u]为真，则u是从v到当前求得最短路径上的顶点

for(v=0；v<G.vexnum；v++)

for(w=0；w<G.vexnum；w++)

{D[v][w]=G.arcs[v][w]；

for(u=0；u<G.vexnum；u++)p[v][w][u]=0；

if(D[v][w]<INTMAX)//从v到w有直接通路

{P[v][w][v]=1；P[v][w][w]=l；

}//if

}//for

for(u=0；u<G.vexnum；u++)

for(v=0；v<G.vexnum；v++)

for(w=0；w<G.vexnum；w++)

if(D[v][u]+D[u][w]<D[v][w])//从v经u到w一条路径更短

{D[v][w]=D[v][u]+D[u][w]；

for(i=0；i<G.vexnum：i++)

P[v][w][i]=P[v][u][i]||P[u][w][i]；

}//if

}//ShortestPath_Floyed

(3)举例

教学目的：

1.掌握单源点到其它各顶点的最短路径。

2.掌握任意两顶点间的最短路径。

教学重点、难点：

1.重点是单源点和任意两顶点间的最短路径

2.难点是算法的理解和应用

教学方法：

通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。

教学过程设计：

1、介绍单源最短路径和多点间最短路径的基本概念;

2、介绍Dijkstra方法，并画出示意图（黑板）；

3、讲解Dijkstra方法的代码实现；

4、介绍Floyd方法，并画出示意图（黑板）；

5、讲解Floyd方法的代码实现；

课堂提问：

比较Dijkstra方法和Prim算法的异同。

Dijkstra方法中寻找最小的D[v][w]有什么好算法？

小结：

25）介绍单源最短路径和多点间最短路径的基本概念；

26）掌握求解单源最短路径和多点间最短路径的基本概念方法