离散数学实验指导书(3)

}

如果 flag 该无向图是欧拉图

（3）对有向图而言，若所有结点的入度等于出度，则该图为欧拉图。

C语言算法： flag=1;

for(i=1;i<=n && flag;i++) { }

如果 flag 该有向图是欧拉图

（4）求出欧拉路的方法：欧拉路经过每条边一次且仅一次。可用回溯的方法求得所有欧拉路。

C语言算法：

int count=0,cur=0,r[N][N]; // r[N][N]为图的邻接矩阵，cur为当前结点编号，count为欧拉路的数量。

int sequence[M];// sequence保留访问点的序列，M为图的边数 输入图信息;

void try1(int k) //k表示边的序号 { }

int i,pre=cur; //j保留前一个点的位置,pre为前一结点的编号 for (i=0;i

if (r[cur][i]) //当前第cur点到第i点连通

{ }

r[cur][i]=0;cur=sequence[k]=i; if (k

for(j=1;j<=n;j++)

if(r[i][j]) sum1++; if(r[j][i]) sum2++; for(j=1;j<=n;j++)

if(sum1%2==0 || sum2%2==0) flag=0;

//删除当前点与第i点的边，记下第k次到达点i，把第i个点设为当前点

//上面条件不满足，说明当前点的出度为0，回溯，试下一位置

实验七 最优二叉树的应用

【实验目的】掌握求最优二叉树的方法。

【实验内容】最优二叉树在通信编码中的应用。要求输入一组通信符号的使用频率，求

各通信符号对应的前缀码。

【实验原理和方法】

（1）用一维数组f[N]存贮通信符号的使用频率，用求最优二叉树的方法求得每个通信符号的前缀码。

（2）用链表保存最优二叉树，输出前缀码时可用树的遍历方法。 #include #include #define N 13 struct tree {

float num;

struct tree *Lnode; struct tree *Rnode;

}* fp[N];//保存结点 char s[2*N];//放前缀码

void inite_node(float f[],int n)//生成叶子结点 {

}

void sort(struct tree * array[],int n)//将第N-n个点插入到已排好序的序列中。 {

int i;

struct tree *temp; for(i=N-n;i

struct tree * construct_tree(float f[],int n)//建立树 {

int i;

struct tree *pt; for(i=1;i

pt=(struct tree *)malloc(sizeof(struct tree));//生成非叶子结点 pt->num=fp[i-1]->num+fp[i]->num; pt->Lnode=fp[i-1];pt->Rnode=fp[i]; if(array[i]->num>array[i+1]->num) { }

temp=array[i+1]; array[i+1]=array[i]; array[i]=temp; int i;

struct tree *pt; for(i=0;i

pt=(struct tree *)malloc(sizeof(struct tree));//生成叶子结点 pt->num=f[i];

pt->Lnode=NULL;pt->Rnode=NULL; fp[i]=pt;

}

fp[i]=pt;//w1+w2 sort(fp,N-i);

return fp[N-1]; }

void preorder(struct tree *p,int k,char c) {

int j; if(p!=NULL) { } }

void main(){

float f[N]={2,3,5,7,11,13,17,19,23,29,31,37,41}; struct tree *head;

inite_node(f,N); //初始化结点 head=construct_tree(f,N);//生成最优树 s[0]=0;

preorder(head,0,'l');//遍历树 }

if(c=='l') s[k]='0'; else s[k]='1';

if(p->Lnode==NULL) {//P指向叶子 }

preorder(p->Lnode,k+1,'l'); preorder(p->Rnode,k+1,'r');

printf(\for(j=0;j<=k;j++)

printf(\putchar('\\n');

实验八 群的判定

【实验目的】掌握群的判定方法。

【实验内容】输入代数系统(A,*)的集合A和*运算的运算表，判断(A，*)是否是群。 【实验原理和方法】

（1）用一维数组a[n]存贮集合A。 （2）用二维数组op[n][n]存贮运算表。

（3）根据群的定义，代数系统(A，*)若为群，除运算表已表明运算*封闭外，还应该满足下列三个条件：*运算可结合、有幺元e、 A中任何元素都有逆元。 *运算可结合：

for(i=0;i

for(j=0;j

for(k=0;k