数据结构重点概要.doc

数据结构重点概要.doc顶点i的直接后驱.
例如:?这个问题可以被看成是一个大的工程,在此工程中,.
计算机专业的课程设置及其关系
课程代码
课程名称
先修课程代码
C1
高等数学
无
C2
程序设计基础
无
C3
离散数学
C1 C2
C4
数据结构
C2 C3
C5
算法语言
C2
C6
编译技术
C4 C5
C7
操作系统
C4 C9
C8
普通物理
C1
C9
计算机原理
C8
从表中可以看出,C1、C2 是独立于其它课程的基础课,而有的课却需要有先修课程,比如,学完程序设计基础和离散数学后才能学数据结构,,顶点表示课程, i为课程j 的先修课,则必然存在有向边〈i,j〉.
表示课程之间优先关系的有向无环图

在AOV网中,顶点线性序列如具有下列两个性质,则称之为拓扑有序序列,构造拓扑序列的过程称为拓扑排序.
⑴在AOV网中,若顶点i 优先于顶点j ,则在线性序列中顶点i仍然优先于顶点j;
⑵对于网中原来没有优先关系的顶点与顶点,,在线性序列中也建立一个先后关系,或者顶点i优先于顶点j ,或者顶点j 优先于i.
那么,怎样求一个AOV的拓扑序列呢?拓扑排序的方法和步骤是:
⑴从AOV网中选择一个没有前驱的顶点(该顶点的入度为0)并且输出它;
⑵从网中删去该顶点,并且删去从该顶点发出的全部有向边;
⑶重复上述两步,直到剩余的网中不再存在没有前驱的顶点为止.
这样操作的结果有两种:一种结果是网中全部顶点都被输出,这说明网中不存在有向回路;另一种结果是网中顶点未被全部输出,剩余的顶点均有前驱顶点,这说明网中存在有向回路.
,执行上述过程可以得到如下拓扑序列:
V1,V6,V4,V3,V2,V5 和 V1,V3,V2,V6,V4,V5
为了实现上述算法,对AOV网采用邻接表存储方式,并且邻接表中顶点结点中增加一个记录顶点入度的数据域,顶点表结点结构的描述改为:
typedef struct vnode{ /*顶点表结点*/
int count /*存放顶点入度*/
VertexType vertex; /*顶点域*/
EdgeNode * firstedge; /*边表头指针*/
}VertexNode;
算法中可设置一个堆栈,凡是网中入度为0 ,拓扑排序的算法步骤为:
①将没有前驱的顶点(count 域为0)入栈;
②从栈中退出栈顶元素输出,并把该顶点引出的所有有向边删去,即把它的各个邻接顶点的入度减1;
③将新的入度为0的顶点再入堆栈;
④重复②~④,,或者剩下的顶点中没有入度为0的顶点.
下面给出用C语言描述的拓扑排序算法的实现.
void Topo_Sort (AlGraph *G)
{/*对以带入度的邻接链表为存