欢迎来到天天文库
浏览记录
ID:39544210
大小:31.50 KB
页数:4页
时间:2019-07-05
《离散数学 欧拉图实验》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、1、欧拉图判定和应用【实验内容】判断一个图是不是,如果是,求出所有欧拉路【实验原理和方法】(1)用关系矩阵R=表示图。(2)对无向图而言,若所有结点的度都是偶数,则该图为欧拉图。C语言算法:flag=1;for(i=1;i<=n&&flag;i++){sum=0;for(j=1;j<=n;j++)if(r[i][j])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++
2、)if(r[i][j])sum1++;for(j=1;j<=n;j++)if(r[j][i])sum2++;if(sum1%2==0
3、
4、sum2%2==0)flag=0;}如果flag该有向图是欧拉图(4)求出欧拉路的方法:欧拉路经过每条边一次且仅一次。可用回溯的方法求得所有欧拉路。C语言算法:intcount=0,cur=0,r[N][N];//r[N][N]为图的邻接矩阵,cur为当前结点编号,count为欧拉路的数量。intsequence[M];//sequence保留访问点的序列,M为图的边数输入图信息;voidtry1(intk)//k表示边的序号{inti,pre=cur;/
5、/j保留前一个点的位置,pre为前一结点的编号for(i=0;i6、方法】(1)用一维数组f[N]存贮通信符号的使用频率,用求最优二叉树的方法求得每个通信符号的前缀码。(2)用链表保存最优二叉树,输出前缀码时可用树的遍历方法。#include#include#defineN13structtree{floatnum;structtree*Lnode;structtree*Rnode;}*fp[N];//保存结点chars[2*N];//放前缀码voidinite_node(floatf[],intn)//生成叶子结点{inti;structtree*pt;for(i=0;i7、)malloc(sizeof(structtree));//生成叶子结点pt->num=f[i];pt->Lnode=NULL;pt->Rnode=NULL;fp[i]=pt;}}voidsort(structtree*array[],intn)//将第N-n个点插入到已排好序的序列中。{inti;structtree*temp;for(i=N-n;inum>array[i+1]->num){temp=array[i+1];array[i+1]=array[i];array[i]=temp;}}structtree*construct_tree(8、floatf[],intn)//建立树{inti;structtree*pt;for(i=1;inum=fp[i-1]->num+fp[i]->num;pt->Lnode=fp[i-1];pt->Rnode=fp[i];fp[i]=pt;//w1+w2sort(fp,N-i);}returnfp[N-1];}voidpreorder(structtree*p,intk,charc){intj;if(p!=NULL){if(c=='l')s[k]='0';elses9、[k]='1';if(p->Lnode==NULL){//P指向叶子printf("%.2f:",p->num);for(j=0;j<=k;j++)printf("%c",s[j]);putchar('');}preorder(p->Lnode,k+1,'l');preorder(p->Rnode,k+1,'r');}}voidmain(){floatf[N]={2,3,5,7,11,13,17,19,23,29,3
6、方法】(1)用一维数组f[N]存贮通信符号的使用频率,用求最优二叉树的方法求得每个通信符号的前缀码。(2)用链表保存最优二叉树,输出前缀码时可用树的遍历方法。#include#include#defineN13structtree{floatnum;structtree*Lnode;structtree*Rnode;}*fp[N];//保存结点chars[2*N];//放前缀码voidinite_node(floatf[],intn)//生成叶子结点{inti;structtree*pt;for(i=0;i7、)malloc(sizeof(structtree));//生成叶子结点pt->num=f[i];pt->Lnode=NULL;pt->Rnode=NULL;fp[i]=pt;}}voidsort(structtree*array[],intn)//将第N-n个点插入到已排好序的序列中。{inti;structtree*temp;for(i=N-n;inum>array[i+1]->num){temp=array[i+1];array[i+1]=array[i];array[i]=temp;}}structtree*construct_tree(8、floatf[],intn)//建立树{inti;structtree*pt;for(i=1;inum=fp[i-1]->num+fp[i]->num;pt->Lnode=fp[i-1];pt->Rnode=fp[i];fp[i]=pt;//w1+w2sort(fp,N-i);}returnfp[N-1];}voidpreorder(structtree*p,intk,charc){intj;if(p!=NULL){if(c=='l')s[k]='0';elses9、[k]='1';if(p->Lnode==NULL){//P指向叶子printf("%.2f:",p->num);for(j=0;j<=k;j++)printf("%c",s[j]);putchar('');}preorder(p->Lnode,k+1,'l');preorder(p->Rnode,k+1,'r');}}voidmain(){floatf[N]={2,3,5,7,11,13,17,19,23,29,3
7、)malloc(sizeof(structtree));//生成叶子结点pt->num=f[i];pt->Lnode=NULL;pt->Rnode=NULL;fp[i]=pt;}}voidsort(structtree*array[],intn)//将第N-n个点插入到已排好序的序列中。{inti;structtree*temp;for(i=N-n;inum>array[i+1]->num){temp=array[i+1];array[i+1]=array[i];array[i]=temp;}}structtree*construct_tree(
8、floatf[],intn)//建立树{inti;structtree*pt;for(i=1;inum=fp[i-1]->num+fp[i]->num;pt->Lnode=fp[i-1];pt->Rnode=fp[i];fp[i]=pt;//w1+w2sort(fp,N-i);}returnfp[N-1];}voidpreorder(structtree*p,intk,charc){intj;if(p!=NULL){if(c=='l')s[k]='0';elses
9、[k]='1';if(p->Lnode==NULL){//P指向叶子printf("%.2f:",p->num);for(j=0;j<=k;j++)printf("%c",s[j]);putchar('');}preorder(p->Lnode,k+1,'l');preorder(p->Rnode,k+1,'r');}}voidmain(){floatf[N]={2,3,5,7,11,13,17,19,23,29,3
此文档下载收益归作者所有