目录
实验目的
掌握判断欧拉图的方法；
掌握求最优二叉树的方法。
实验内容
判断一个图是不是欧拉图，如果是，求出所有欧拉回路；
最优二叉树在通信编码中的应用。要求输入一组通信符号的使用频率，求各通信符号对应的前缀码。
欧拉图的判定
实验内容
一、欧拉图的判定
（1）用关系矩阵R=表示图。
（2）对无向图而言，若所有结点的度都是偶数，则该图为欧拉图。
（3）对有向图而言，若所有结点的入度等于出度，则该图为欧拉图。
（4）求欧拉路的方法：欧拉路经过每条边一次且仅一次。可用回溯的方法求得所有欧拉路。
编辑
本题采用分块编写，每一部分单独介绍，最后会有总写。
无向图的判断
对无向图的判断：
对无向图而言，若所有结点的度都是偶数，则该图为欧拉图。
算法展示
//算法如下 for (int i = 0; i < n && flag; i++) { sum = 0; for (int j = 0; j < n; j++) { if (r[i][j]) sum++; } if (sum % 2 == 0) flag = 0; }
源码
#include <stdio.h> int r[101][101]; int main() { int flag = 1; int sum; int n; scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &r[i][j]); } } for (int i = 0; i < n && flag; i++) { sum = 0; for (int j = 0; j < n; j++) { if (r[i][j]) sum++; } if (sum % 2 == 0) flag = 0; } if (flag == 0) printf("不是欧拉图\n"); else printf("是欧拉图\n"); }
有向图的判断
对有向图的判断：
对有向图而言，若所有结点的入度等于出度，则该图为欧拉图。
算法展示
//算法 for (int i = 0; i < n && flag; i++) { sum1 = 0; sum2 = 0; for (int j = 0; j < n; j++) { if (r[i][j]) sum1++; } for (int j = 1; j <= n; j++) { if (r[j][i]) sum2++; } if (sum1 % 2 == 0|| sum2 % 2 == 0) flag = 0; }
源码
#include <stdio.h> int r[101][101]; int main() { int flag = 1; int sum1,sum2; int n; scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &r[i][j]); } } for (int i = 0; i < n && flag; i++) { sum1 = 0; sum2 = 0; for (int j = 0; j < n; j++) { if (r[i][j]) sum1++; } for (int j = 1; j <= n; j++) { if (r[j][i]) sum2++; } if (sum1 % 2 == 0|| sum2 % 2 == 0) flag = 0; } if (flag == 0) printf("不是欧拉图\n"); else printf("是欧拉图\n"); }
求欧拉路
求欧拉路的方法：欧拉路经过每条边一次且仅一次。可用回溯的方法求得所有欧拉路。
算法展示
int count = 0, cur = 0, r[N][N]; int sequence[M]; void try1(int k) { int i, pre = cur; for (i = 0; i < N; i++) if (r[cur][i]) { r[cur][i] = 0; cur = sequence[k] = i; if (k < M) try1(k + 1); else prt1(); r[pre][i] = 1; cur = pre; } }
整体源码
对无向图的判断
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <time.h> int n, a[100][100], m = 0, visit[100]; int cur = 0, s[100], vis[100][100]; void try1(int k) { int i; if (cur == m + 1) { for (i = 0; i < cur; i++) { if (i == 0) printf("%d", s[i] + 1); else printf("->%d", s[i] + 1); } printf("\n"); } else { for (i = 0; i < n; i++) { if (a[k][i] && !vis[k][i]) { vis[k][i] = 1; vis[i][k] = 1; s[cur++] = i; try1(i); cur--; vis[k][i] = 0; vis[i][k] = 0; } } } } void dfs(int k) { int i; visit[k] = 1; for (i = 0; i < n; i++) { if (a[k][i] && !visit[i]) { dfs(i); } } } int fun() { int i; dfs(0); for (i = 0; i < n; i++) { if (!visit[i]) return 0; } return 1; } int main() { int i, j; printf("请输入节点个数n："); scanf("%d", &n); for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf("%d", &a[i][j]); printf("邻接矩阵为：\n"); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) printf("%d ", a[i][j]); printf("\n"); } if (fun() == 0) { printf("该图不是连通图\n"); return 0; } printf("该图是连通图\n"); int odd = 0; for (i = 0; i < n; i++) { int sum = 0; for (j = 0; j < n; j++) { if (a[i][j]) sum++; } if (sum % 2) odd++; } if (odd == 0) { printf("该图是欧拉图。\n"); printf("所有的欧拉路为：\n"); for (i = 0; i < n; i++) { s[cur++] = i; try1(i); cur--; } } else printf("不是欧拉图\n"); return 0; }
对有向图的判断
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <time.h> int n, a[100][100], m = 0, visit[100]; int cur = 0, s[100], vis[100][100]; void try1(int k) { int i; if (cur == m + 1) { for (i = 0; i < cur; i++) { if (i == 0) printf("%d", s[i] + 1); else printf("->%d", s[i] + 1); } printf("\n"); } else { for (i = 0; i < n; i++) { if (a[k][i] && !vis[k][i]) { vis[k][i] = 1; s[cur++] = i; try1(i); cur--; vis[k][i] = 0; } } } } void dfs(int k) { int i; visit[k] = 1; for (i = 0; i < n; i++) { if (a[k][i] && !visit[i]) { dfs(i); } } } int fun()//判断连通性 { int i, j; for (i = 0; i < n; i++) { memset(visit, 0, sizeof(visit)); dfs(i); for (j = 0; j < n; j++) { if (!visit[j]) break; } if (j == n) return 1; } return 0; } int main() { int i, j; printf("请输入节点个数n："); scanf("%d", &n); for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf("%d", &a[i][j]); if (fun() == 0) { printf("该图不是连通图！\n"); return 0; } printf("该图是连通图！\n"); int odd = 0, begin = -1, end = -1; for (i = 0; i < n; i++) { int sum1 = 0, sum2 = 0; for (j = 0; j < n; j++) { sum1 += a[i][j]; sum2 += a[j][i]; } if (sum1 != sum2) { odd++; if (sum1 - sum2 == 1) begin = i; if (sum2 - sum1 == 1) end = i; } } if (odd == 0) { printf("该图是欧拉图。\n"); printf("所有的欧拉路为：\n"); for (i = 0; i < n; i++) { s[cur++] = i; try1(i); cur--; } } else printf("不是欧拉图\n"); return 0; }
二叉树的应用
（1）用一维数组f[N]存贮通信符号的使用频率，用求最优二叉树的方法求得每个通信符号的前缀码。
（2）用链表保存最优二叉树，输出前缀码时可用树的遍历方法。
源码
#include <stdio.h> #include <stdlib.h> #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) { //生成叶子结点 int i; struct tree* pt; for (i = 0; i < n; i++) { pt = (struct tree*)malloc(sizeof(struct tree));//生成叶子结点 pt->num = f[i]; pt->Lnode = NULL; pt->Rnode = NULL; fp[i] = pt; } } void sort(struct tree* array[],int n) { //将第N-n个点插入到已排好序的序列中。 int i; struct tree* temp; for (i = N - n; i < N - 1; i++) { if (array[i]->num > array[i + 1]->num) { temp = array[i + 1]; array[i + 1] = array[i]; array[i] = temp; } } } struct tree* construct_tree(float f[], int n) { //建立树 int i; struct tree* pt; for (i = 1; i < N; 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]; 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) { if (c == 'l') s[k] = '0'; else s[k] = '1'; if (p->Lnode == NULL) { //P指向叶子 printf("%.2f: ", p->num); for (j = 0; j <= k; j++) printf("%c", s[j]); putchar('\n'); } preorder(p->Lnode, k + 1, 'l'); preorder(p->Rnode, k + 1, 'r'); } } int 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');//遍历树 return 0; }
源码下载
gitee下载链接：
欧拉图/欧拉图/test1.c · 赵博涵/c_language_exercises - 码云 - 开源中国 (gitee.com)
