数据结构

拓朴排序
〖摘要：〗

比如用邻接矩阵存贮有向图，以入度为“0”的标准进行拓扑排序

步骤1：建立邻接矩阵，入有向边为 1->2, 1->3, 3->4, 2->5

则邻接矩阵如下：

0 0 0 0 0
0 0 1 1 0
1 0 0 0 0
0 0 0 0 1
0 0 0 0 0

步骤2：计算各顶点的入度，就是看矩阵中每一列上“1” 的个数

用in[]来存放各顶点入度，那么
in[0] = 1, in[1]=0, in[2]=1, in[3]=1, in[4]=1

步骤3：拓朴排序

从in[]中查找值为“0”的节点并输出，例如 in==0，说明节点i 的入度为“0”，这时要把 in 置为“-1”，说明它已经被查找过了，我们还要在矩阵中的第i 行上找值为“1”的列，如找到列 j, 说明 i->j 为一条有向边，我们已经把i 节点去掉了，自然 i->j 这条有向边就不存在了，j 的入度要减去”1“， 即 in--, 循环查找，知道全部节点已序


#include<stdio.h>
#include<stdlib.h>
#define NODENUM 40
int matrix[NODENUM][NODENUM];
int num = 0;

void read(){
继续阅读其余的  4916 字
irini   2007-02-28 22:29:10 阅读:83  评论:0  引用:0
最小生成树Kruskal算法
〖摘要：〗

kruskal 算法是根据边的权值以递增的方式，依次找出权值最低的边来建最小生成树，规定每次添加的边不能造成生产树有回路。

比如，一个图中所有边按权值递增的排序如下：
(4,5)2  (3,4)3  (1,4)5  (1,3)6 (1,2)7  (2,4)8  (2,5)8  (3,5)9  (1,5)12  (2,3)14

步骤1：将(4,5)的边加到生产树中
步骤2：将(3,4)的边加到生产树中
步骤3：将(1,4)的边加到生产树中
步骤4：将(1,3)的边加到生产树中，但发现这时出现了回路(1,3,4 顶点)，我们改用下条边(1,2)加到生产树中,现在已经连通了1 2 3 4 5 所有顶点，最小生产树建立完成。

下面看程序，读入一个带权连通无向图G，生产最小生产树T，输出T的各边及各边的权之和。输入形式如下：
n  i  j  w  ...  -1 -1 -1

n表示图的顶点个数，i j w 表示从顶点i 到顶点j 的权为w 的一条边。
我们的做法是读入一条边后按照权值由小到大的顺序把这条边插入链表，然后从链表中读边生产树。


#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MAX 100

struct Node{
	继续阅读其余的  4436 字
irini   2007-02-26 22:32:24 阅读:1032  评论:0  引用:0
构造AVL树
〖摘要：〗

AVL数是平衡的二叉排序树的一种，AVL树中任一节点的左右子树的高度之差的绝对值不超过1。

什么是平衡的二叉树呢？树中任一节点的左右子树的高度大致相同，若任一结点的左右子树的高度均相同（如满二叉树），则二叉树是完全平衡的。

二叉排序树（Binary Sort Tree）的性质：
（1）若它的左子树非空，则左子树上的所有结点的值均小于根结点的值。
（2）若它的右子树非空，则右子树上的所有结点的值均大于根结点的值。
（3）左右子树本身又各是一棵二叉排序树。

下面编写一个程序，它能读入n（n<=20）个两两不等的整数，最后一个是-9999，作为结束标志，构造一棵包含这n 个整数的AVL树，然后前 中 后序遍历树，算出树的高度。

这个程序的关键就是构造AVL 树，我们可以从空的AVL树开始，读入一个数就插入，再检测插入后是否符合AVL树性质，如不符合就进行调整。
还有一种方法，先对输入的数排序，再把中点的数插入AVL树中，对中点左右两边的的序列采用同样的插入方法，直到空为止。
第二种方法比较简单，我们的程序就采用此方法。


#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MAX 20
int acturalNum = 0; //实际输入的节点数

struct Node{
	继续阅读其余的  5750 字
irini   2007-02-24 11:32:43 阅读:353  评论:0  引用:0
Copyright@2006 powered by YuLog