离散数学 欧拉图实验.doc

1、欧拉图判定和应用【实验内容】 判断一个图是不是，如果是，求出所有欧拉路【实验原理和方法】（1）用关系矩阵R=表示图。（2）对无向图而言，若所有结点的度都是偶数，则该图为欧拉图。C语言算法：flag=1;for(i=1;i=n & flag;i+)sum=0;for(j=1;j=n;j+)if(rij) sum+;if(sum%2=0) flag=0;如果 flag 该无向图是欧拉图（3）对有向图而言，若所有结点的入度等于出度，则该图为欧拉图。C语言算法：flag=1;for(i=1;i=n & flag;i+)sum1=0;sum2=0;for(j=1;j=n;j+)if(rij) sum1+;for(j=1;j=n;j+)if(rji) sum2+;if(sum1%2=0 | sum2%2=0) flag=0;如果 flag 该有向图是欧拉图（4）求出欧拉路的方法：欧拉路经过每条边一次且仅一次。可用回溯的方法求得所有欧拉路。C语言算法：int count=0,cur=0,rNN; / rNN为图的邻接矩阵，cur为当前结点编号，count为欧拉路的数量。int sequenceM;/ sequence保留访问点的序列，M为图的边数输入图信息;void try1(int k) /k表示边的序号int i,pre=cur; /j保留前一个点的位置,pre为前一结点的编号for (i=0;iN;i+) if (rcuri) /当前第cur点到第i点连通 /删除当前点与第i点的边，记下第k次到达点i，把第i个点设为当前点rcuri=0;cur=sequencek=i; if (kM) try1(k+1); /试下一个点else prt1();/经过了所有边，打印一个解/上面条件不满足，说明当前点的出度为0，回溯，试下一位置rprei=1;cur=pre; 2、最优二叉树的应用【实验内容】最优二叉树在通信编码中的应用。要求输入一组通信符号的使用频率，求各通信符号对应的前缀码。【实验原理和方法】（1）用一维数组fN存贮通信符号的使用频率，用求最优二叉树的方法求得每个通信符号的前缀码。（2）用链表保存最优二叉树，输出前缀码时可用树的遍历方法。#include #include #define N 13struct tree float num;struct tree *Lnode;struct tree *Rnode;* fpN;/保存结点char s2*N;/放前缀码void inite_node(float f,int n)/生成叶子结点int i;struct tree *pt;for(i=0;inum=fi;pt-Lnode=NULL;pt-Rnode=NULL;fpi=pt;void sort(struct tree * array,int n)/将第N-n个点插入到已排好序的序列中。int i;struct tree *temp;for(i=N-n;inumarrayi+1-num)temp=arrayi+1;arrayi+1=arrayi;arrayi=temp;struct tree * construct_tree(float f,int n)/建立树int i;struct tree *pt;for(i=1;inum=fpi-1-num+fpi-num;pt-Lnode=fpi-1;pt-Rnode=fpi;fpi=pt;/w1+w2sort(fp,N-i);return fpN-1;void preorder(struct tree *p,int k,char c) int j;if(p!=NULL) if(c=l) sk=0;else sk=1;if(p-Lnode=NULL) /P指向叶子printf(%.2f: ,p-num);for(j=0;jLnode,k+1,l);preorder(p-Rnode,k+1,r);void main()float fN=2,3,5,7,11,13,17,19,23,29,31,37,41;struct tre