第七节：最短路径问题 7.1 概述 最短路径问题的抽象： 在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。这条路径就是两点之间的最短路径。第一个顶点称为源点，最后一个顶点为终点。 问题分类： （1）单源最短路径问题：从某固定源点触发，求其到所有其他顶点的最短路径。又分为（有无向）有权图和（有无向）无权图两种。 （2）多源最短路径问题：求任意两顶点间的最短路径。 7.2 无权图的单源最短路 按照递增（非递减）的顺序找出到各个顶点的最短路。例如图1：   图1 我们以v3作为源点，与v…

第六节：图（上） 6.1 图 1.关于图 图表示的是“多对多”的关系。它包含： （1）一组顶点：通常用V（Vertex）表示顶点集合。 （2）一组边：通常用E（Edge）表示边的集合，表示顶点与顶点的关系： ①边是顶点对：(v,w)∈E，其中v,w∈V。这是一个双向的。 ②有向边：<v,w>，表示从v指向w的边（单行线）。 ③不考虑重边和自回路。 其抽象数据类型为： 类型名称：图（Graph） 数据对象集：一非空的顶点集合Vertex和一个边集合Edge，每条边用对应的一对顶点表示。 操作集：对于任意的…

第五节：树（下） 5.1 堆 1.堆的介绍 优先队列：特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。 堆的两个特性： （1）结构性：用数组表示的完全二叉树； （2）有序性：任一结点的关键字是其子树所有结点的的最大值（最小值）： ①最大堆：也称“大顶堆”：最大值 ②最小堆，也称“小顶堆”：最小值。 类型名称：最大堆（MaxHeap） 数据对象集：一个有N>0个元素的最大堆H是一棵完全二叉树，每个结点上的元素值不小于其子结点元素的值。 操作集：对于任意最多有MaxS…

第四节：二叉搜索树 4.1 二叉搜索树 二叉搜索树（BST），也称二叉排序树和二叉查找树。一棵这个树，可以为空。如果不为空，满足以下性质： （1）非空左子树的所有键值小于其根结点的键值。 （2）非空右子树的所有键值大于其根结点的键值。 （3）左、右子树都是二叉搜索树。 1.二叉搜索树操作的函数： Position Find(ElementType X, BinTree BST)：从二叉搜索树BST中查找元素X，并返回其结点地址； Position FindMin(ElementType X, BinTree BST…

第三讲 树（上） 3.1 树与树的表示 1.查找 查找是指根据某个给定关键字K，从集合R中找出关键字与K相同的记录。它分为以下两类： （1）静态查找：集合中记录是固定的，没有插入和删除操作。 （2）动态查找：集合中记录是动态变化的，除了查找，还可能发生插入和删除。 首先举一个顺序查找的例子。此例需要注意，其设置了一个哨兵，因此可以减少判断中的一个条件。这个例子要求是在Element[1]~Element[n]中查找关键字为K的数据元素，其结构体如下： typedef struct LNode&n…

第一节：数据结构基本知识 1.1 什么是数据结构 例：写程序实现一个函数PrintN，使得传入一个正整数位N的参数后，能顺序打印从1道N的全部正整数。 代码1（循环实现）： void PrintN(int N){        int i;        for(i =1; i<=N; i++)  &n…