初始化栈操作void InitStack(SqStack *S){ 第44页：入栈操作Pushint
入栈操作Pushint：Push(SqStack *S, NODE e){
第45页：重新分配存储器块的地址函数
- 即重新分配存储器块的地址函数原型extern void *realloc(void *mem_address, unsigned int newsize);
- 先判断当前指针是否有足够的连续空间，如果有，扩大mem_address指向的地址，并且将mem_address返回.
- 如果空间不够，先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来mem_address所指内存区域
第46页：出栈操作POPint Pop
出栈操作POPint Pop：(SqStack *S，NODE *e){
第47页：队列
- 队列（Queue）是一种先进先出（First In Last Out，FILO）的线性表。只能在表的一端进行插入操作，在另一端进行删除操作。
- 允许插入的一端称为队尾（Rear），允许删除的一端称为队首（Front）。
第48页：队列的基本操作
- （1）InitQueue(Q)：初始化操作，设置一个空的队列Q。
- （2）EntQueue(Q,x)：入队操作，将元素x插入到队列Q的尾部，成为队列新的队尾元素。
- （3）DelQueue(Q)：出队列函数，若队列Q不为空，返回Q的队首元素，且将队首元素从队列中删除。如果队列Q为空，则函数返回值为NULL。
- （4）GetHead(Q)：取队首元素，若队列Q不为空，返回Q的队首元素。如果队列为空，则函数返回值为NULL。
- （5）CurrentSize(Q)：队列大小函数，返回队列Q当前所包含的元素个数。
第49页：队列存储结构#define
队列存储结构#define：QueueSize 100
第50页：队列初始化操作InitQueue
队列初始化操作InitQueue：(Q)//（1）初始化操作，设置一个空的队列Q。void InitQueue(CircleQueue *Q){Q->front = Q->rear = 0;Q->count = 0;}
- 队列初始化操作InitQueue(Q)//（1）初始化操作，设置一个空的队列Q。void InitQueue(CircleQueue *Q){Q->front = Q->rear = 0;Q->count = 0;}
第51页：判队空、队满函数
判队空、队满函数：//（2）判队空int QueueEmpty(CirQueue *Q){return Q->count==0;
第52页：入队操作EntQueue
入队操作EntQueue：(Q,x)void EntQueue(CircleQueue *Q, DataType x){if (QueueFull(Q))Error("Queue overflow");
第53页：出队操作DelQueue
出队操作DelQueue：(Q)DataType DelQueue(CircleQueue *Q){DataType temp;if (QueueEmpty(Q))Error("Queue underflow");
第54页：4.2 线性结构
- 4.1 数、数据及数据结构
- 4.2 线性结构
- 4.3 树形结构
- 4.4 图结构
- 4.5 应用举例
知识要点：层次关系，树形结构，树，树根，子树，结点的度，叶子（终端结点），分支结点，树的度，孩子，双亲，兄弟，祖先，子孙，树的深度，二叉树，满二叉树，完全二叉树，二叉树的遍历。
第55页：4.3 树形结构
第56页：层次关系
- 在我们的实际生活中，有许多数据之间的关系表现为层次关系，例如，人类社会的家族族谱、各种社会组织机构的设置、一本书的章节目录，问题决策、博弈等等，
- 数据之间的关系都是一种层次关系，可以用树形结构来描述和建模。树形结构是一种用于描述层次关系的数据结构。
第57页：博弈与决策问题
- 博弈
- 狭义的讲，博弈即下棋，对弈。
- 现代意义，泛指在一定的游戏规则约束下，基于直接相互作用的环境条件，各参与者依靠所掌握的信息，选择各自策略（行动），以实现利益最大化和风险成本最小化的过程。
- 只要有涉及人群的互动，就有博弈。人与人之间的博弈，组织之间的博弈，国家之间的博弈。
- 博弈和决策是两类常见的问题，对这类问题的求解过程可以用图形来描述，这种图形就像一棵自然界中的树，称为博弈树和决策树。
第58页：博弈树（Game Tree）
- 博弈的过程通常可以用一颗树来描述，即博弈树（Game Tree），它描述了博弈的过程和可能的结果。
- 井字游戏
- 两个玩家，一个打圈O，一个打叉×，轮流在3×3的格上打自己的符号，
- 最先以横、直、斜连成一线为胜。
第59页：“井字棋”博弈树示例
本页主体为图片内容，文字版要点待对照原课件补充。
第60页：“井字棋”博弈结果分析
- 井子棋，有9个格，树的高度最高为9层，第一层有9种选择，第二层有9*8=72中选择，第三层有9*8*7=504种选择，依次类推，则第八层有9*8*7*6*5*4*3*2=362 880种走法。最后一步，只剩一个格，由先手×占据，可见最终结果是362880种状态。
- 在全部362880种状态中，有大量的状态是中间就已经确定了胜负，无需进一步往下走，即对应的后续走法可以“剪”枝。这样，当获胜导致游戏结束时，则只剩下255168种可能的棋局。若×是先手，则131184种棋局为×获胜，77904种棋局为O获胜，46080种棋局为平局。
第61页：博弈问题的发展
- 人与机器的博弈
- 1951年，A.S. Douglas在EDSAC计算机上开发出OXO（井字游戏），开启了人与机器对弈的时代。
- 1996年2月10日，美国IBM的深蓝计算机首次挑战国际象棋世界冠军卡斯巴罗夫，但以2-4落败，比赛在2月17日结束。
- 1997年5月再度挑战卡斯巴罗夫，比赛在5月11日结束，最终深蓝电脑以3.5–2.5击败卡斯巴罗夫
- 博弈论（Game Theory）
- 研究在多决策主体之间行为具有相互作用时，各主体根据所掌握信息及对自身能力的认知，做出有利于自己的决策的一种行为理论。
- 在经济学、管理科学、国际关系、政治学、军事战略、计算机科学和其他很多学科都有广泛的应用。
第62页：决策问题与决策树
- 决策问题
- 在处理问题时，常常会面临几种可能出现的自然情况，同时又存在着几种可供选择的行动方案。此时，需要决策者根据当前状态和已知信息作决策，即选择出一种行动方案
- 决策问题通常还涉及到各种情况发生的概率，在此基础上进行计算和推演。
- 决策问题的求解过程可以很自然的用树状图形来描述，这就是决策树（Decision Tree）。它是一种直观的运用概率，进行可行性决策分析的图解方法，常用于项目风险评价等领域。
第63页：决策树举例某企业准备投资一个新的项目
决策树举例某企业准备投资一个新的项目：，市场预测表明：产品销路好的概率为0.7；销路差的概率为0.3。有三种可选方案：（1）建设大型工厂，需要投资1000万元，可使用10年。若产品销路好，每年可赢利200万元；若销路不好，每年将亏损50万元。（2）建设小型工厂，需投资300万元。如销路好，每年可赢利70万元；如销路不好，每年也会赢利50万元。（3）先建设小型工厂，若销路好，3年后扩建，扩建需投资500万元，可使用7年，扩建后每年会赢利180万元。针对上述三种可选方案，企业如何选择？
- 决策树举例某企业准备投资一个新的项目，市场预测表明：产品销路好的概率为0.7；销路差的概率为0.3。有三种可选方案：（1）建设大型工厂，需要投资1000万元，可使用10年。若产品销路好，每年可赢利200万元；若销路不好，每年将亏损50万元。（2）建设小型工厂，需投资300万元。如销路好，每年可赢利70万元；如销路不好，每年也会赢利50万元。（3）先建设小型工厂，若销路好，3年后扩建，扩建需投资500万元，可使用7年，扩建后每年会赢利180万元。针对上述三种可选方案，企业如何选择？
第64页：决策树
- 计算各状态点的利润期望值
- 点②：0.7×200×10 + 0.3×(-50)×10-1000（大厂投资）=250（万元）
- 点⑤：1.0×180×7–500（扩建投资）=760（万元）
- 点⑥：1.0×70×7=490（万元）
第65页：树形结构
- 树（tree）是n（n≥0）个结点的有限集。在一棵非空树中：（1）有且仅有一个特殊的结点，称为树根（Root）；（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，且其中的每一个集合也是一棵树。T1,T2,…,Tm称为根的子树。
- 层次关系的抽象，用于表达数据间的层次关系，是一类重要的非线性数据结构。也可表示从属关系、并列关系。
第66页：树的表示--1树形结构
本页主体为图片内容，文字版要点待对照原课件补充。
第67页：树的表示—2
本页主体为图片内容，文字版要点待对照原课件补充。
第68页：常用术语
- 结点的度
- 叶子（Leaf）或终端结点
- 非终端结点或分支结点
- 树的度
- 孩子
- 双亲
- 兄弟
- 祖先
- 树的深度
第69页：二叉树
- 二叉树（Binary tree）是n（n≥0）个结点的有限集合，或者是空集，或者是由一个根和称为左右子树的两个不相交的二叉树构成。
- 二叉树和树是两个不同的概念
- 树的子树没有顺序，二叉树的两棵子树有左右之分。
- 树中结点的度是任意的，二叉树中每个结点的度不能大于2。
- 二叉树共有5种不同的形态
第70页：二叉树的特性（1）
- 在二叉树的第i（i≥1）层上的结点数最多为2i-1。
- 证明
- 当i=1时，只有一个根结点。显然，2i-1=21-1=1，命题成立。
- 假定对所有的1
- j<i命题成立，即在j层的结点数最多为2j-1。
- 由归纳假设知，第i-1层上结点的最大数目为2i-2。由于二叉树中每个结点的度最大为2，因此，第i层上结点的最大数目为第i-1层上结点数目的2倍，即为2
- 2i-2=2i-1。
第71页：二叉树的特性（2）
第72页：二叉树的特性（3）
- 对于任意二叉树T，假设终端结点数为n0，度为2的结点数为n2，则有n0=n2+1
- 证明
第73页：满二叉树
- 满二叉树，若深度为k的二叉树且结点个数恰好为2k-1
第74页：完全二叉树
- 完全二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应
第75页：二叉树的特性（4）
第76页：二叉树的特性（5）
- 对一棵具有n个结点的完全二叉树中的结点，从根开始，按照从上到下，自左至右的顺序连续编号为1~n，则对于任意结点i（1
- i
- n）有（1）如果i=1，则结点i是二叉树的根。若i>1，则结点i的父结点的编号为⌊i/2
- 。（2）如果结点i有左儿子，即2i
- n，则结点i左儿子的编号为2i。（3）如果结点i有右儿子，即2i+1
- n，则结点i右儿子的编号为2i+1。
第77页：证明
- 对于i=1：结点i=1为根结点，根据编号原则，如果存在左右儿子，编号应该分别为2和3。即：结点i（i=1）的左儿子编号为2（2i=2）；结点i（i=1）的右儿子编号为3（2i+1=3）。因此，性质（2）、（3）成立。
- 对于i>1：设对于结点序号1<j<i时，性质（2）、（3）成立，即：结点j的左儿子编号为2j（2j
- n），右儿子编号为2j+1（2j+1
- n）。下面证明j=i时命题成立。
- 对于任意两个编号连续的结点i-1和i，存在下面两种情况
- 结点i-1和结点i在同一层
- 结点i-1和结点i在相邻的两层，其中结点i-1为上一层最后一个结点，结点i为下一层第一个结点
第78页：证明（续）
- 因为，结点j（1<j<i）的左儿子编号为2j（2j
- n），右孩子编号为2j+1（2j+1
- n），因此结点i-1的左孩子结点编号为2(i-1)，右孩子结点编号为2(i-1)+1=2i-1。因此对于情况（a），如果结点i存在左右孩子，其编号应分别为(2i-1)+1=2i和2i+1。即当j=i时性质(2)、(3)成立。
- 由性质（2）和性质（3）可知，对于任意结点i其父结点的编号为⌊i/2
第79页：常用操作及算法
第80页：树的存储结构
本页主体为图片内容，文字版要点待对照原课件补充。
第81页：二叉树中序遍厉算法
- 算法：中序遍厉二叉树算法前序遍厉：ABDEHCFG中序遍厉：DBHEAFCG后序遍厉：DHEBFGCA
第82页：4.3 树形结构
- 4.1 数、数据及数据结构
- 4.2 线性结构
- 4.3 树形结构
- 4.4 图结构
- 4.5 应用举例
知识要点：任意关系，图结构，无向图，有向图，边，弧，圈，简单图，完全图，平面图，子图，真子图，支撑子图，关联，邻接，顶点的度，入度，出度，路径，通路，回路，简单路径，连通图，连通分量，强连通图，强连通分量，网，邻接矩阵，邻接表，逆邻接表，图的遍历，深度优先搜索，广度优先搜索，生成树，最小生成树
第83页：4.4 图结构
第84页：图论
- 哥尼斯堡七桥问题的数学抽象
- 1736年，欧拉向圣彼得堡科学院递交了关于哥尼斯堡七桥问题的论文—“与位置几何相关的一个问题的解”。在论文中，欧拉将七桥问题抽象出来，把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。并由此得到了如图一样的几何图形
- 欧拉开创了数学的一个新的分支—图论（Graph Theory）。图论的创立，为人们问题求解提供了一种新的数学理论和工具。
第85页：图的概念
- 图（Graph）是比线性表和树更为复杂的数据结构，图可以表达数据对象之间的任意关系。
- 图的定义
- 图G是由两个集合V(G)和E(G)构成的，记作G=(V(G)，E(G))，或简记作G=(V,E)，其中V(G)是顶点的非空有穷集合，E(G)是边的有穷集合，边表示元素之间的关系。
第86页：图的表示
- 图通常用图形来形象的描述，用圆圈表示顶点，连接两个顶点的线段表示边。
第87页：有向图和无向图
- 无向图，其边是顶点的无序对，
- 边没有方向性。若顶点x和顶点y之间有一条边，记作（x,y）
- 有向图，其边是顶点的有序对，
- 边有方向性，又称为“弧”（Arc），从顶点x到顶点y的有向边（弧）用<x,y>来表示
第88页：图相关概念--1
- 圈，若一条边（或弧）的两个顶点相同，则称其为“圈”
- 简单图，若图G不存在圈，也没有两边（或弧）连接同样两个顶点，则称这样的图为“简单图”。
- 完全图，对于简单图，n个顶点的无向图最多有n(n-1)/2条边，其中任意的两个顶点之间都有边相连，称为“完全图”
- 有向完全图，对于有向图，具有n(n-1)条弧的的简单图称为“有向完全图”。
- 平面图，对于一个图，若存在一种画法，使其边仅在顶点处相交，则称其为“平面图”
第89页：图相关概念--2
- 子图，若图G={V,E}和G′={V′,E′}满足条件：
- （1）V′
- V；
- （2）E′
- E，
- 则称G′为图G的“子图”
- 真子图，如果G′
- G，但G′
- G，则称G′为图G的“真子图”，记作G′
- G
- 支撑子图，若G′
- G，且V′=V，E′
- E，即两个图的顶点集相同，而G′的边集是G的边集的子集，则称G′是图G的“支撑子图”。
第90页：图相关概念--3
- 关联，顶点和边（或弧）之间的关系，一条边和它所连接的顶点是相关联的。
- 邻接，顶点和顶点之间、边和边之间的关系，和同一条边（或弧）相关联的两个顶点是邻接的，有共同顶点的两条边也是邻接的。
- 顶点v的度，指和顶点v相关联的边的条数，记作d(v)
- 对于有向度，度又分为“入度”（Indegree）和“出度”（Outdegree）。顶点v的“入度”是指以v为终点（弧头）的弧的条数，记作ID(v)；v的“出度”是指以v为始点（弧尾）的弧的条数，记作OD(v)
第91页：图相关概念--4
- 路径
- 从顶点v到顶点v′的一条路经是一个有穷非空序列w=（v=vi0,vi1,…,vik=v′），其中（vij-1,vij）
- E
- 路径中边的树目k称为路径的“长度”
- 起点和终点相同的路径称为“回路”或“环”（Cycle）
- 序列中顶点不重复出现的路径称为“简单路径”
- 顶点v到v′存在一条路经，则称v到v′有一条“通路”
第92页：图相关概念--5
- 连通图
- 在无向图中，定点vi和vj之间存在一条通路，则成vi和vj之间是连通的。若图G中，任意两个不同的顶点vi和vj之间都是连通的，则称G为“连通图”
- 无向图的“连通分量”是它的极大连通子图。
- 强连通图
- 若有向图G中，任意两个不同的顶点vi和vj之间都存在一条从vi到vj和一条从vj到vi通路，则称有向图G为“强连通图”。
- 有向图中，极大的强连通子图称为它的“强连通分量”。
- 所谓极大，是指再加入一个顶点或边，将不满足图的连通性。一个图G的连通分量可以有多个
第93页：图相关概念--5（举例）
本页主体为图片内容，文字版要点待对照原课件补充。
第94页：图相关概念--6
- 网与图的权
- 图中的边或弧往往给定一个权（Weight），这种带权的图即是网
- 生成树
- 一个连通图G的生成树是图G的极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。
第95页：图的存储
- 存储问题
- 数据、数据之间的关系
- 静态存储（顺序存储）和动态存储（链式存储）
- 存储结构影响算法
- 图的存储
第96页：邻接矩阵
- 设图G=（V,E）具有n个顶点v1,v2,…,vn和m条边e1，e2,…,em，则G的邻接矩阵是一个n
- 例如
第97页：图的邻接矩阵存储结构
图的邻接矩阵存储结构
本页主体为图片内容，文字版要点待对照原课件补充。
第98页：算法4-4：图的邻接矩阵构造算法
算法4-4：图的邻接矩阵构造算法：CreateAM(MGraph &G){scanf("%d%d",&G.vexnum,&G.arcnum)
第99页：邻接表
- 所谓“邻接表”（Adjacency list）就是对图中的每个顶点与它相关联的所有边建立一个单链表，每个链表的头结点保存该顶点的有关信息，链内其它结点，保存与该顶点向关联的边的信息。
- 存储结构
第100页：图的邻接表存储结构
本页主体为图片内容，文字版要点待对照原课件补充。
第101页：举例--1图G1的邻接表
本页主体为图片内容，文字版要点待对照原课件补充。
第102页：举例—2图G4的邻接表
本页主体为图片内容，文字版要点待对照原课件补充。
第103页：逆邻接表
- 对有向图的每个顶点vi建立一个以vi为头的弧的链表。
第104页：图的遍历
- 图的遍历
- 给定图G=（V,E）后，一个最基本的问题就是对于顶点集中的任意顶点v0，从v0出发访问图中的所有顶点，且每一个顶点只访问一次
- 图的遍历算法是解决图的连通性问题、拓扑排序以及关键路经等算法的基础
- 深度优先搜索
- 广度优先搜索
第105页：深度优先搜索
- 深度优先搜索（Depth First Search，DFS）递归算法（1）访问v0，对v0作已访问标记。（2）找出与v0邻接未被访问的顶点w，按深度优先搜索与w邻接的未作标记的顶点。（3）若与v0邻接的顶点皆已作访问标记，则返回；否则，找出与v0邻接的未被访问的所有顶点w，按深度优先搜索与w邻接的未作标记的顶点。
第106页：深度优先搜索（举例）
- 举例
- 深度优先搜索序列为：v1,v2,v4,v8,v5,v3,v6,v7
第107页：广度优先搜索
- 图的广度优先搜索（Breadth First Search，BFS）类似于树的按层次遍历（1）首先从顶点v（初值为v0）开始，访问v，对v作已访问标记；（2）按照字母或编号次序依次访问与v邻接且尚未访问的顶点；（3）然后再顺序从这些顶点出发，按同样原则访问邻接这些顶点的未被访问的所有顶点，直到所有顶点都被访问过为止。
第108页：广度优先搜索（举例）
- 举例
- 广度优先搜索序列为：v1,v2,v3,v4,v5,v6,v7,v8
第109页：生成树
- 图的生成树，当G为连通图时，G的具有下列性质的子图T称为G的生成树（又称支撑树）（1）T包含G的所有顶点；（2）T为连通图；（3）T包含的边数最少。
- 一般情况下，一个连通图的生成树不是唯一的。若连通图G有n个顶点，由n-1条边构成的包含G中所有顶点的连通子图都是G的生成树（连接n个顶点至少需要n-1条边）。
第110页：最小代价生成树
- 图往往是赋权图，即图中的每条边（或弧）都对应一个数，这样的图又称网
- 在赋权图中，其生成树往往也是不唯一的，我们通常用生成树中各边的权之和来衡量生成树，称作生成树的代价。在G的所有生成树中，其代价最小的生成树称为最小代价生成树（Minimum Cost Spanning Tree），简称最小生成树（Minimum Spanning Tree，MST）
- 在n个城市之间建立通信网络，如何选择n-1条线路，使得总的造价最低？这就是一个典型的图的最小生成树的例子
第111页：最小生成树示例
最小生成树示例
本页主体为图片内容，文字版要点待对照原课件补充。
第112页：最小生成树性质
- 设G=(V，E）是一个连通网络，U是顶点集V的一个非空真子集。若(u，v）是G中一条“一个端点在U中（例如：u∈U），另一个端点不在U中的边（例如：v∈V-U），且（u，v）具有最小权值，则一定存在G的一棵最小生成树包括此边（u，v）。
第113页：证明MST性质
- 假设G中任何一棵最小生成树都不含边(u，v)，即若T是G的一棵最小生成树，则它不含边(u，v)。
第114页：普里姆（Prim）算法
- 根据MST的上述性质，可以容易的求得图的最小生成树。
- 设G=(V，E)为赋权连通图，G的最小生成树的顶点集合为U，边的集合TE
- 普里姆（Prim）算法
第115页：图结构（举例）
- 举例
- 从顶点v1开始，U={v1}
- 选择代价最小的边（v1,v5）,将v5加入顶点集U={v1，v5}
- 选择代价最小边（v5,v4）,将v4加入顶点集U={v1，v5，v4}
- 选择代价最小边（v5,v3）,将v3加入顶点集U={v1，v5，v4，v3}
- 选择代价最小边（v5,v6）,将v6加入顶点集U={v1，v5，v4，v3，v6}
- 选择代价最小边（v3,v2）,将v2加入顶点集U={v1，v5，v4，v3，v6，v2}
第116页：克鲁斯卡尔（Kruskal）算法
- 由美国计算机科学家约瑟夫·克鲁斯卡尔（JosephBernard Kruskal）于1956年发明
- 基本思想：对于具有n个顶点的图，将图中边按其权值由小到大的次序顺序选取，若选边后不形成回路，则保留作为一条边，若形成回路则除去该边。直到依次选够n-1条边为止，即得到图的最小生成树。
第117页：4.4 图结构
- 4.1 数、数据及数据结构
- 4.2 线性结构
- 4.3 树形结构
- 4.4 图结构
- 4.5 应用举例
知识要点：最短路径，Dijkstra算法，AOV网络，拓扑有序，AOE网络，关键路经
第118页：4.5 应用举例
- 网络与最短通路问题
- 工程拓扑排序问题
- 工程关键路径问题
第119页：交通问题及其抽象
- 交通问题
- 顶点表示城市，边表示城市之间的道路，可以带权（表示道路的长度或沿道路行驶需要花费的时间、费用等）
- 问题
- 从城市A到城市B有通路吗？
- 若从城市A到城市B有多条通路，哪一条是最短的或者是最经济的呢？
- 图的最短通路
- Dijkstra最短路径算法
- Floyd求所有顶点对之间的最短通路算法
- 蚁群算法
第120页：Dijkstra最短路径算法
第121页：Dijkstra算法
本页主体为图片内容，文字版要点待对照原课件补充。
第122页：Dijkstra算法（举例）
本页主体为图片内容，文字版要点待对照原课件补充。
第123页：工程问题及其抽象
- 在工程项目或产品加工中，除了最简单的情况外，通常需要把一个复杂的工程分成若干个子工程，一个产品的加工分成若干加工工序。完成了这些子工程或加工工序则意味着整个工程的结束或产品制造的完成。而这些子工程或加工工序之间，通常受一定条件的约束，例如，某个子工程或加工工序的开始必须在另一些子工程或加工工序结束之后。
- 工程项目的施工或产品加工过程抽象为一个有向图，顶点表示各个子工程或加工工序，顶点之间的有向弧表示子工程或加工工序之间的约束，例如子工程之间的时间先后。
第124页：AOV网络
- 如果有向图为非赋权图，图中的顶点表示活动（Activity），表示一个工程的子工程或一个产品的加工工序，有向边表示活动之间的优先关系，这样的有向图称为AOV（activity onvertex）网络。
第125页：拓扑排序
- 所谓拓扑排序，就是产生这样的顶点序列：若网络中，vi是vj的前驱，则在序列中，vi在vj之前，有这种特性的序列称为拓扑有序。
第126页：AOV网络拓扑分类算法Step1设一
AOV网络拓扑分类算法Step1设一：AOV队列，并初始化为空。Step2计算每个顶点的入度，将入度为0的顶点入队列AOV。Step3如果AOV队列空，转Step4；3.1输出队首元素vi3.2在图中删除以vi为狐尾的所有弧，即对于所有的<vi,vj>，则vj入度减1。如果vj入度为0，则将vj入队。3.3转Step3。Step4.若全部顶点被输出则拓扑有序，或者网络中没有无先驱的顶点。
- AOV网络拓扑分类算法Step1设一AOV队列，并初始化为空。Step2计算每个顶点的入度，将入度为0的顶点入队列AOV。Step3如果AOV队列空，转Step4；3.1输出队首元素vi3.2在图中删除以vi为狐尾的所有弧，即对于所有的<vi,vj>，则vj入度减1。如果vj入度为0，则将vj入队。3.3转Step3。Step4.若全部顶点被输出则拓扑有序，或者网络中没有无先驱的顶点。
- 拓扑序列：v1,v2,v3,v4,v6,v7,v8,v5,v9
第127页：举例—课程编列
- 课程编列是指不同课程之间学习顺序的安排。课程之间学习顺序同样可以用AOV网结构来表达，其中顶点表示课程，顶点之间的有向弧表达课程之间的学习顺序。例如，如果存在一条有向弧<Ci,Cj>，则表明课程Ci是课程Cj的先导课程，换句话说，课程Cj是课程Ci的后续课程。
- 在高等学校计算机基础教学领域，计算机基础教学包括7门主要课程，其教学编列如图
第128页：工程问题及其抽象
- 工程问题
- AOE（Activity On Edge）网络
- 图的顶点表示事件，有向边表示活动，权表示活动持续的时间
- 为了描述问题的需要，还可以增加持续时间为0的虚拟活动
第129页：AOE网络与关键路经
- AOE（Activity On Edge）网络
- 图的顶点表示事件，有向边表示活动，权表示活动持续的时间
- 为了描述问题的需要，还可以增加持续时间为0的虚拟活动
- 关键路经
- 在AOE网络中，某些活动可以并行进行，完成工程的最短时间是从开始顶点（也称源点）到结束顶点（又称终点）最长路径的长度（路径上所有活动的时间和）
第130页：事件与活动的最早和最迟发生时间
第131页：事件的最早和最迟发生时间
事件的最早和最迟发生时间：（1）设起点的最早时间ve(0)=0，从v0开始沿正向递推，可依次求得各事件的最早发生时间，递推公式如下：ve(j)=max{ve(i)+t(<i,j>) | <i,j>∈T，2≤j≤n}，其中T是所有以j为头的弧的集合。（2）从vl(n)=ve(n)起，反向递推，可求各事件的最迟发生时间，递推公式如下：vl(i)=min{vl(j)-t(<i,j>) | <i,j>∈S，1≤i≤n-1}，其中S是所有以i为尾的弧的集合。
- 事件的最早和最迟发生时间（1）设起点的最早时间ve(0)=0，从v0开始沿正向递推，可依次求得各事件的最早发生时间，递推公式如下：ve(j)=max{ve(i)+t(<i,j>) | <i,j>∈T，2≤j≤n}，其中T是所有以j为头的弧的集合。（2）从vl(n)=ve(n)起，反向递推，可求各事件的最迟发生时间，递推公式如下：vl(i)=min{vl(j)-t(<i,j>) | <i,j>∈S，1≤i≤n-1}，其中S是所有以i为尾的弧的集合。
第132页：活动的最早和最迟发生时间
- 根据AOE网络中活动和事件的约束关系
- ae(i)=ve(j)
- al(i)=vl(k)-t(<j,k>)
第133页：活动的最早和最迟发生时间（举例）
本页主体为图片内容，文字版要点待对照原课件补充。
第134页：计算结果
本页主体为图片内容，文字版要点待对照原课件补充。
第135页：关键路径
本页主体为图片内容，文字版要点待对照原课件补充。
第136页：说明--1
- 在求顶点v5的最早发生时间ve(5)时，由于存在虚拟活动a12（对应弧<v6,v5>)，因此，要考察v2、v3和v6三个顶点。虚拟活动虽然时间为0，但它改变着工程的启动顺序，因此，在上述AOE网络中，长度最长的路径是（v1,v4,v6,v5,v8,v9），而不是（v1,v4,v6,v8,v9）。
- 活动的最早和最迟发生时间如果不相同，说明该活动的启动时间可以适当推迟，而不影响整个工程的进度。
第137页：说明--2
- 在关键路径上，各活动的最早开始时间和最迟开始时间相等，没有时间余量。
- 通常情况下，缩短关键活动的工期，可以缩短整个工程的工期。但这不是绝对的，因为改变某个活动的权值，将直接影响整个AOE网络中各个事件的最早和最迟发生时间的计算，可能使的关键路径发生变化。如果活动不再是关键路径上的活动，缩短该活动的时间无法缩短整个工程的工期。
第138页：本章小结
- 4.1 数、数据与数据结构数据，数据类型
- ，简单数据类型，构造数据类型，数据结构，抽象数据类型，逻辑结构，物理结构（存储结构），顺序存储结构，链式存储结构。
- 4.2 线性结构先后关系，线性结构，线性表
- ，线性表基本操作，堆栈，队列。。
- 4.3 树形结构层次关系，树形结构，树
- ，树根，子树，结点的度，叶子（终端结点），分支结点，树的度，孩子，双亲，兄弟，祖先，子孙，树的深度，二叉树，满二叉树，完全二叉树，二叉树的遍历。。
- 4.4 图结构任意关系，图结构，无向图
- ，有向图，边，弧，圈，简单图，完全图，平面图，子图，真子图，支撑子图，关联，邻接，顶点的度，入度，出度，路径，通路，回路，简单路径，连通图，连通分量，强连通图，强连通分量，网，邻接矩阵，邻接表，逆邻接表，图的遍历，深度优先搜索，广度优先搜索，生成树，最小生成树。
- 4.5 应用举例最短路径，Dijkstra算
- 法，AOV网络，拓扑有序，AOE网络，关键路经。
第139页：问题思考
- 数据结构是数据的关系，抽象的研究数据结构及其操作运算，有何意义？
- 如何理解数据的存储结构对算法的影响？根据图结构，举例说明。
- 在AOE网络中，缩短关键路径上的活动工期，一定可以缩短整个工程的工期吗？为什么？
第140页：本章结束
本章结束：Unit 1 Web基础谢谢大家
