目 录
实验一 命题逻辑公式化简……………………………………………………1
实验二 关系的闭包运算 ………………………………………… ………… 2
实验三 最小生成树的Kruskal算法……………………………………… 4
实验一 命题逻辑公式化简
【实验目的】加深对五个基本联结词（否定、合取、析取、条件、双条件）的理解、掌握利用基本等价公式化简公式的方法。
【实验内容】用化简命题逻辑公式的方法设计一个表决开关电路。
实验用例：用化简命题逻辑公式的方法设计一个5人表决开关电路，要求3人以上（含3人）同意则表决通过（表决开关亮）。
【实验原理和方法】
（1）写出5人表决开关电路真值表，从真值表得出5人表决开关电路的主合取公式（或主析取公式），将公式化简成尽可能含五个基本联结词最少的等价公式。
（2）上面公式中的每一个联结词是一个开关元件，将它们定义成C语言中的函数。
（3）输入5人表决值（0或1），调用上面定义的函数，将5人表决开关电路真值表的等价公式写成一个函数表达式。
（4）输出函数表达式的结果，如果是1，则表明表决通过，否则表决不通过。
参考代码：
#include<stdio.h>
int vote(int a,int b,int c,int d,int e)
{
//五人中任取三人的不同的取法有10种。
if( a&&b&&c || a&&b&&d || a&&b&&e || a&&c&&d || a&&c&&e || a&&d&&e || b&&c&&d || b&&c&&e || b&&d&&e || c&&d&&e)
return 1;
else
return 0;
}
void main()
{
int a,b,c,d,e;
printf("请输入第五个人的表决值（0或1，空格分开）：");
scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
if(vote(a,b,c,d,e))
printf("很好，表决通过！\n");
else
printf("遗憾，表决没有通过！\n");
}
//注：联结词不定义成函数，否则太繁
实验二 关系的闭包运算
1、实验类型：设计性
2、实验目的
通过算法设计并编程实现求给定关系的各种闭包运算，加深学生对闭包运算的概念的理解。
3、实验内容
给定关系R，求R的自反闭包及R的对称闭包。
4、实验原理
若关系R的关系矩阵为M，而自反闭包为A（即r（R）=A），对称闭包为B（即S（R）=B），则A=M∨I B=M∨MT 其中，I为恒等矩阵，MT为M的转置矩阵。
5、实验仪器设备或软件环境及工具
运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。
6、实验要求
复习关系闭包的定义，实验由几人一组完成。所编程序能够通过编译，并能够实现求出给定关系的闭包的运算。
7、实验报告要求
（1）写出实验过程中遇到的问题及其解决过程。
（2）写出类c的算法并编写一个程序求出给定关系的闭包。
（3）写出实验结束时的程序清单及运行结果及实验总结。
8、思考题
设计出求关系R的传递闭包的Warshall算法的程序。
【实验目的】掌握求关系闭包的方法。
【实验内容】编程求一个关系的闭包，要求传递闭包用warshall方法。
【实验原理和方法】
设N元关元系用r[N][N]表示，c[N][N]表示各个闭包，函数initc(r)表示将c[N][N]初始化为r[N][N]。
（1）自反闭包：。
C语言算法： 将关系矩阵的对角线上所有元素设为1。
initc(r);
/*将关系矩阵的对角线上所有元素设为1*/
for(i=0;i<N;i++)
c[i][i]=1;
（2）对称闭包：
C语言算法： 在关系矩阵的基础上，若。
initc(r);
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(c[i][j]) c[j][i]=1;/*将关系矩阵的对角线上所有元素设为1*/
（3）传递闭包：，或用warshall方法。
方法1：，下面求得的关系矩阵T=就是。
int b[N][N];
initc(r);/*用c装好r*/
for(m=1;m<N;m++) /*得r的m次方,用c装好*/
{
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
b[i][j]=0;
for(k=0;k<N;k++)
b[i][j]+=c[i][k]*r[k][j];
if(b[i][j]) b[i][j]=1;
}
initc(b);/*把r的m次方b赋给c保存*/
方法2：warshall方法
initc(r);/*用c装好r*/
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(c[j][i])
for(k=0;k<N;k++)
{
c[j][k]=c[j][k]+c[i][k];
if(c[j][k]) c[j][k]=1;
}
实验三 最小生成树的Kruskal算法
1、实验类型：设计性
2、实验目的
通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树，加深学生对求最小生成树的Kruskal算法的理解。
3、实验内容
给定无向连通加权图，编程设计求出其一棵最小生成树。
4、实验原理
设所给定无向连通加权图具有n个结点，m条边，首先，将各条边的权按从小到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放置某一条边时，使得生成树形成回路，则删除这条边。这样，直至生成树具有n-1条边时，我们所得到的就是一棵最小生成树。
5、实验仪器设备或软件环境及工具
运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。
6、实验要求
复习树及最小生成树的定义，实验由一人一组完成。所设计程序能够通过编译，并能够求出给定无向连通加权图的一棵最小生成树。
7、实验步骤及注意事项
（1） 边依小到大顺序得l1，l2，…，lm。
（2） 置初值：S，0i，1j。
（3） 若i=n-1，则转（6）。
（4） 若生成树边集S并入一条新的边lj之后产生的回路，则j+1j，并转（4）。
（5） 否则，i+1i；ljS（i）；j+1j，转（3）。
（6） 输出最小生成树S。
（7） 结束。
8、实验报告要求
（1）写出实验过程中遇到的问题及其解决过程。
（2）写出类c的算法，并写一个程序求出给定无向连通加权图的一棵最小生成树。
（3）写出实验结束时的程序清单及运行结果及实验总结。
参考例子：
1闭包：
#include<stdio.h>
int main()
{
int i,j,k,n;
static int str[122],zifan[122],chuandi[122],duich[122];
printf("Please input the jie:\n");
scanf("%d",&n);
printf("A=%d\n",n);
for(i=0;i<n*n;i++)
{
scanf("%d",&str[i]);
}
printf("The shu zu is:\n");
for(j=0;j<n*n;j++)
{
printf("%4d",str[j]);
if((j+1)%n==0)
printf("\n");
}
for(j=0;j<n*n;j++)
{
zifan[j]=str[j];
chuandi[j]=str[j];
duich[j]=str[j];
}
printf("The zifan bibao is:\n");
for(i=0;i<n*n;i++)
{
if(i%(n+1)==0)
zifan[i]=zifan[i]||1;
printf("%4d",zifan[i]);
if((i+1)%n==0)
printf("\n");
}
printf("The duich bibao is:\n");
for(i=0,j=0;i<n*n&&j<n;i++)
{
if(i>j*(n+1)&&i<(j+1)*n)
{ duich[i]=duich[(i-j*(n+1))*(n-1)+i]||duich[i];
duich[(i-j*(n+1))*(n-1)+i]=duich[(i-j*(n+1))*(n-1)+i]||duich[i];
}
else if(i>=(j+1)*n)
j++;
}
for(i=0;i<n*n;i++)
{
printf("%4d",duich[i]);
if((i+1)%n==0)
printf("\n");
}
printf("The chuandi bibao is:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(chuandi[j*n+i])
{for(k=0;k<n;k++)
chuandi[j*n+k]=chuandi[j*n+k]||chuandi[i*n+k];
}
for(i=0;i<n*n;i++)
{
printf("%4d",chuandi[i]);
if((i+1)%n==0)
printf("\n");
}
return 0;
}
2、warshall算法：
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define N 3
#define TRUE 0
int get_matrix(int a[N][N])
{
int i = 0,j = 0;
for (i = 0;i < N;i++) {
for (j = 0;j < N;j++) {
scanf("%d",&a[i][j]);
if (a[i][j] != 0 && a[i][j] != 1) {
printf("0 or 1 in matrix\n");
exit(2);
}
}
}
return TRUE;
}
int output_matrix(int a[N][N])
{
int i = 0,j = 0;
for (i = 0;i < N;i++) {
for (j = 0;j < N;j++) {
printf("%d ",a[i][j]);
}
putchar('\n');
}
return TRUE;
}
int warshall(int a[N][N])
{
int col = 0;
int line = 0;
int temp = 0;
for (col = 0;col < N;col++) {
for (line = 0;line < N;line++) {
if (a[line][col] != 0) {
for (temp = 0;temp < N;temp++) {
a[line][temp] = a[line][temp] | a[col][temp];
}
}
}
}
return TRUE;
}
int main(void)
{
int a[N][N] = {0};
printf("please input a matrix with %d * %d:\n",N,N);
if (get_matrix(a)) {
printf("get matrix error!\n");
exit(1);
}
warshall(a);
output_matrix(a);
return 0;
}
3、Kruskal算法1:
#define MAXE 11
#define MAXV 10
#include "stdio.h"
typedef struct
{
int vex1; //边的起始顶点
int vex2; //边的终止顶点
int weight; //边的权值
} Edge;
void kruskal(Edge E[],int n,int e)
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MAXV];
for (i=1; i<=n; i++) //初始化辅助数组
vset[i]=i;
k=1; //表示当前构造最小生成树的第k条边，初值为1
j=0; //E中边的下标，初值为0
while (k < e) //生成的边数小于e时继续循环
{
m1=E[j].vex1;
m2=E[j].vex2;//取一条边的两个邻接点
sn1=vset[m1];
sn2=vset[m2];
//分别得到两个顶点所属的集合编号
if (sn1!=sn2)
//两顶点分属于不同的集合，该边是最小生成树的一条边
{
printf("(v%d,v%d): %d\n",m1,m2,E[j].weight);
k++; //生成边数增l
if (k>=6) break;
for (i=1; i<=n; i++) //两个集合统一编号
if (vset[i]==sn2) //集合编号为sn2的改为sn1
vset[i]=sn1;
}//if
j++; //扫描下一条边
}//while
}//kruskal
int main()
{
Edge E[MAXE];
int nume,numn;
/*
printf("输入边数和顶数:\n");
scanf("%d%d",&nume,&numn);*/
nume=10;
numn=6;
// printf("请输入各边及对应的的权值(起始顶点 终止顶点 权值)\n");
/*
for(int i=0; i<nume; i++)
scanf("%d%d%d",&E[i].vex1,&E[i].vex2,&E[i].weight);*/
//在这里对输入的数据进行排序，达到假设的要求，即：假设数组E存放图G中的
//所有边，且边已按权值从小到大的顺序排列
E[9].vex1=1;
E[9].vex2=2;
E[9].weight=6;
E[0].vex1=1;
E[0].vex2=3;
E[0].weight=1;
E[4].vex1=1;
E[4].vex2=4;
E[4].weight=5;
E[6].vex1=2;
E[6].vex2=3;
E[6].weight=5;
E[2].vex1=2;
E[2].vex2=5;
E[2].weight=3;
E[8].vex1=1;
E[8].vex2=2;
E[8].weight=6;
E[5].vex1=3;
E[5].vex2=4;
E[5].weight=5;
E[7].vex1=3;
E[7].vex2=5;
E[7].weight=6;
E[3].vex1=3;
E[3].vex2=6;
E[3].weight=4;
E[1].vex1=4;
E[1].vex2=6;
E[1].weight=2;
kruskal(E,numn,nume);
}
4、Kruskal算法2:
#include "stdio.h"
#define maxver 10
#define maxright 100
int G[maxver][maxver],record=0,touched[maxver][maxver];
int circle=0;
int FindCircle(int,int,int,int);
int main()
{
int path[maxver][2],used[maxver][maxver];
int i,j,k,t,min=maxright,exsit=0;
int v1,v2,num,temp,status=0;
restart:
printf("Please enter the number of vertex(s) in the graph:\n");
scanf("%d",&num);
if(num>maxver||num<0)
{
printf("Error!Please reinput!\n");
goto restart;
}
for(j=0; j<num; j++)
for(k=0; k<num; k++)
{
if(j==k)
{
G[j][k]=maxright;
used[j][k]=1;
touched[j][k]=0;
}
else if(j<k)
{
re:
printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);
scanf("%d",&temp);
if(temp>=maxright||temp<-1)
{
printf("Invalid input!\n");
goto re;
}
if(temp==-1)
temp=maxright;
G[j][k]=G[k][j]=temp;
used[j][k]=used[k][j]=0;
touched[j][k]=touched[k][j]=0;
}
}
for(j=0; j<num; j++)
{
path[j][0]=0;
path[j][1]=0;
}
for(j=0; j<num; j++)
{
status=0;
for(k=0; k<num; k++)
if(G[j][k]<maxright)
{
status=1;
break;
}
if(status==0)
break;
}
for(i=0; i<num-1&&status; i++)
{
for(j=0; j<num; j++)
for(k=0; k<num; k++)
if(G[j][k]<min&&!used[j][k])
{
v1=j;
v2=k;
min=G[j][k];
}
if(!used[v1][v2])
{
used[v1][v2]=1;
used[v2][v1]=1;
touched[v1][v2]=1;
touched[v2][v1]=1;
path[i][0]=v1;
path[i][1]=v2;
for(t=0; t<record; t++)
FindCircle(path[t][0],path[t][0],num,path[t][0]);
if(circle)
{
/*if a circle exsits,roll back*/
circle=0;
i--;
exsit=0;
touched[v1][v2]=0;
touched[v2][v1]=0;
min=maxright;
}
else
{
record++;
min=maxright;
}
}
}
if(!status)
printf("We cannot deal with it because the graph is not connected!\n");
else
{
for(i=0; i<num-1; i++)
printf("Path %d:vertex %d to vertex %d\n",i+1,path[i][0]+1,path[i][1]+1);
}
return 1;
}
int FindCircle(int start,int begin,int times,int pre)
{
/* to judge whether a circle is produced*/
int i;
for(i=0; i<times; i++)
if(touched[begin][i]==1)
{
if(i==start&&pre!=start)
{
circle=1;
return 1;
break;
}
else if(pre!=i)
FindCircle(start,i,times,begin);
else
continue;
}
return 1;
}