目录
实验代码
代数
#include<bits/stdc++.h> //修改1：万能头文件
using namespace std;
#define N 100
//基本函数
int printYsh(char a[]) {
//由于集合保存在一个字符串，显示时在各元素之间加入逗号，及返回长度
//int nLen=0;
//int i=0;
//nLen=strlen(a);
//if (nLen>0) {
// printf("%c",a[0]);
//}
//for(i=1; i<nLen; i++) {
// printf(",%c",a[i]);
//}
//printf("\n");
//return nLen;
int nLen=strlen(a);
if(nLen==0)
printf("空集");
else
for(int i=0; i<nLen; ++i) {
if(i>0) printf(",");
printf("%c",a[i]);
}
printf("\n"); //修改点2：输出函数改变 增加空集判断
return nLen;
}
int printAlgTableYsh(char a[][N],int n) {
//由于集合保存在一个字符串，显示时在各元素之间加入逗号，及返回长度
int i=0,j=0;
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
printf("%4c",a[i][j]);
}
printf("\n");
}
return n;
}
int inputYsh2(char a[])
{
//由于集合保存在一个字符串，但是输入时各字符是用逗号分隔的
//形参a是一个数组，送入是一个地址值，在函数对该数组的修改会反映在主函数
char nLen=0,i=0,j=0,k=0;
char stmp[1024]; //最多1024个字符
printf("集合元素只能是A-Za-z0-9,其他字符被当作分隔符而去掉：\n");
gets(stmp);fflush(stdin);
nLen=strlen(stmp);
for(i=0;i<nLen;i++)
{
if (((stmp[i]>='A') && (stmp[i]<='Z')) ||
((stmp[i]>='a') && (stmp[i]<='z'))||
((stmp[i]>='0') && (stmp[i]<='9')))
{
a[j]=stmp[i];
j++;
}
}
//sort(a,a+j);
a[j]='\0';
return j;//字符串的长度
}
int inputYsh1(char a[]) {
//由于集合保存在一个字符串，但是输入时各字符是用逗号分隔的
//形参a是一个数组，送入是一个地址值，在函数对该数组的修改会反映在主函数
char nLen=0,i=0,j=0,k=0;
char stmp[1024]; //最多1024个字符
printf("集合元素只能是A-Za-z0-9,其他字符被当作分隔符而去掉：\n");
gets(stmp);
fflush(stdin);
nLen=strlen(stmp);
for(i=0; i<nLen; i++) {
if (((stmp[i]>='A') && (stmp[i]<='Z'))||
((stmp[i]>='a') && (stmp[i]<='z'))||
((stmp[i]>='0') && (stmp[i]<='9'))) {
//a[j]=stmp[i];
// j++;
if(strchr(a,stmp[i])==NULL) {
a[j]=stmp[i];
j++;
}
} //修改点3：增加一个输入函数用来处理输入集合有重复元素情况 用strchr函数来代替搜索过程
}
sort(a,a+j); //修改点4：使用sort将集合排序
a[j]='\0';
return j;//字符串的长度
}
int inputInt(int fun[]) {
int i=0,n=0;
printf("输入多个数整数，彼此间用空格分隔：");
scanf("%d",&i);
while (i>=0) {
fun[n]=i;
n++;
scanf("%d",&i);
}
fflush(stdin);
return n;
}
int string2matrix(char a[],char b[][N],int n) {
//将字符串按每行n个转换为二维数组，
int i=0,j=0,nLen=0,k=0;
nLen=strlen(a);
for (k=0; k<nLen; k++) {
b[i][j]=a[k];
if ((k+1)%n==0) {
i++;
j=0;
} else {
j++;
}
}
return i;
}
int getIndex(char alphaTable[],char yz) {
//寻找字符yz在字母表alphaTable表中的序号
int i=0,nLen=0;
nLen=strlen(alphaTable);
for (i=0; i<nLen; i++) {
if (alphaTable[i]==yz) {
break;
}
}
return i;
}
int testCombine(char ysb[][N],char alphaTable[]) {
//组合律
//ysb[][]是运算表，运算表的真实的行数与列数=字母表的alphaTable中的元素个数
int i=0,nRow,nChar=0,n3=0,iyz=0,ixy=0,ix=0,iy=0,iz=0;
char yz,xy,xyz1,xyz2;
nChar=strlen(alphaTable);
n3=nChar*nChar*nChar;
ix=0;
iy=0;
iz=0;
printf("%4c%4c%4c%20s%20s%10s\n",'x','y','z',"x*(y*z)","(x*y)*z","相等");
for (i=0; i<n3; i++) {
yz=ysb[iy][iz];//y*z对应的运算结果
iyz=getIndex(alphaTable,yz);//寻找字母yz对应的序号
xyz1=ysb[ix][iyz];//x*(y*z)的结果
xy=ysb[ix][iy]; //x*y对应的运算结果
ixy=getIndex(alphaTable,xy);
xyz2=ysb[ixy][iz];
printf("%4c%4c%4c%20c%20c%10s\n",alphaTable[ix],alphaTable[iy], alphaTable[iz],xyz1,xyz2,(xyz1==xyz2?"=":"!=")); //修改：将输出的字符类型改为字符串类型 解除警告
iz++;
if (iz==nChar) {
iz=0;
iy++;
}
if (iy==nChar) {
iy=0;
ix++;
}
}
return n3;
}
int testAssign(char ysb[N][N],char alphaTable[],char ysbb[N][N]) {
//分配律
//ysb[][]是运算表，运算表的真实的行数与列数=字母表的alphaTable中的元素个数
int i=0,nChar=0,n3=0,iyz=0,ixy=0,ix=0,iy=0,iz=0,ixz=0;
char yz,xy,xz,xyz1,xyz2;
nChar=strlen(alphaTable);
n3=nChar*nChar*nChar;
ix=0;
iy=0;
iz=0;
//*运算1 +运算2
printf("%4c%4c%4c%20s%20s%10s\n",'x','y','z',"x*(y+z)","(x*y)+(x*z)","相等");
for (i=0; i<n3; i++) {
yz=ysbb[iy][iz];//y+z进行运算2的结果
iyz=getIndex(alphaTable,yz);//寻找字母yz对应的序号
xyz1=ysb[ix][iyz];//x*(y+z)进行运算1的结果
xy=ysb[ix][iy]; //x*y进行运算1的结果
ixy=getIndex(alphaTable,xy);
xz=ysb[ix][iz]; //x*z进行运算1的结果
ixz=getIndex(alphaTable,xz);
xyz2=ysbb[ixy][ixz];//xy+xz进行运算2的结果
printf("%4c%4c%4c%20c%20c%10s\n",alphaTable[ix],alphaTable[iy],alphaTable[iz], xyz1,xyz2,(xyz1==xyz2?"=":"!="));
iz++;
if (iz==nChar) {
iz=0;
iy++;
}
if (iy==nChar) {
iy=0;
ix++;
}
}
return n3;
}
int testStruct(char ysb[][N],char a[],char ysbb[][N],char b[],int fun[],int nFun) {
//同构
//ysb[][]是运算表，运算表的真实的行数与列数=字母表的alphaTable中的元素个数
int i=0,n2=0,ix,iy,ixy,ifx,ify,ifxy;
char xyc,xycb,xy;
n2=nFun*nFun;
ix=0;
iy=0;
//*运算1 +运算2
printf("%4c%4c%20s%20s%10s\n",'x','y',"f(x*y)","f(x)+f(y)","相等");
for (i=0; i<n2; i++) {
xy=ysb[ix][iy];//x+y进行运算1的结果
ixy=getIndex(a,xy);//寻找字母xy对应的序号
ifxy=fun[ixy]; //该序号映身为集合B中的序号
xyc=b[ifxy]; //该序与在集合B中的字符
ifx=fun[ix]; //ix映射为集合B中第几个元素
ify=fun[iy];
xycb=ysbb[ifx][ify]; //集合B中的元素进行运算2
printf("%4c%4c%20c%20c%10s\n",a[ix],a[iy],xyc,xycb,(xyc==xycb?"=":"!="));
iy++;
if (iy==nFun) {
iy=0;
ix++;
}
}
return n2;
}
int main() { //修改：void改为 int
char a[N],b[N],ystable[N],ystableD2[N][N],ystableB[N],ystableBD2[N][N];
int i=0,nLen1=0,nChoice=0,fun[N],nFun=0;
while (1) {
printf("\n========================\n");
printf("1...输入相关元素值\n");
printf("2...判断运算表是否可结合\n");
printf("3...判断二个运算表是否可分配\n");
printf("4...判断二个系统是否构造相同\n");
printf("0...退出\n");
printf("========================\n您的选择：");
while(scanf("%d",&nChoice)) //修改点2：判断输入是否合法
if((nChoice>=0&&nChoice<=4)) break;
else printf("请重新输入\n");
//scanf("%d",&nChoice);
fflush(stdin);
if (nChoice==0) {
break;
}
switch (nChoice) {
case 1: {
printf("输入集合A:");
inputYsh1(a); // 修改；主函数里面用不同输入函数输入集合和运算表
printf("输入运算表:");
inputYsh2(ystable);
printYsh(a);
printYsh(ystable);
string2matrix(ystable,ystableD2,strlen(a));
printAlgTableYsh(ystableD2,strlen(a));
break;
}
case 2: {
testCombine(ystableD2,a);
break;
}
case 3: {
printf("输入集合A:");
inputYsh1(a);
printf("输入运算表1:");
inputYsh2(ystable);
printf("输入运算表2:");
inputYsh2(ystableB);
printf("二维形式的运算表1*：\n");
string2matrix(ystable,ystableD2,strlen(a));
printAlgTableYsh(ystableD2,strlen(a));
printf("二维形式的运算表2+：\n");
string2matrix(ystableB,ystableBD2,strlen(a));
printAlgTableYsh(ystableBD2,strlen(a));
testAssign(ystableD2,a,ystableBD2);
break;
}
case 4: {
printf("输入集合A:");
inputYsh1(a);
printf("输入集合B:");
inputYsh1(b);
printf("映射关系：");
nFun=inputInt(fun);
printf("输入运算表1:");
inputYsh2(ystable);
printf("输入运算表2:");
inputYsh2(ystableB);
// printYsh(a);
// printYsh(ystable);
// printYsh(b);
// printYsh(ystableB);
printf("二维形式的运算表1*：\n");
string2matrix(ystable,ystableD2,strlen(a));
printAlgTableYsh(ystableD2,strlen(a));
printf("二维形式的运算表2+：\n");
string2matrix(ystableB,ystableBD2,strlen(a));
printAlgTableYsh(ystableBD2,strlen(a));
testStruct(ystableD2,a,ystableBD2,b,fun,nFun);
break;
}
}
}
//序偶形式的关系到关系矩阵
/*
a,b,c
a,b,c,b,c,a,c,a,b 运算表1
a,b,c,b,b,b,c,b,c 用于可分配的运算表2
//以下数据用于测试同构
0,2,4 集合B
0 1 2 -1 映射关系
0,2,4,2,4,0,4,0,2 用于同构的运算表2
*/
}
集合与关系
//共 6 个修改点
//修改点1：万能头文件
//修改点2：合并if和for语句，使代码简洁易懂
//修改点3：用strchr函数来代替搜索过程
//修改点4：使用memset函数替代双重循环初始化数组
//修改点5：利用布尔函数优化交互
//修改点6：利用while判断输入是否合法
#include <bits/stdc++.h>//修改点1：万能头文件
#define N 100
//集合的基本运算交、并、差、对称差、直积
int printYsh(char a[])
{
//由于集合保存在一个字符串，显示时在各元素之间加入逗号，及返回长度
int nLen = 0;
int i = 0;
nLen = strlen(a);
if (nLen > 0)
{
printf("%c", a[0]);
}
for (i = 1; i < nLen; i++)
{
printf(",%c", a[i]);
}
printf("\n");
return nLen;
}
int printRelaYsh(char a[][3], int n)
{
//由于集合保存在一个字符串，显示时在各元素之间加入逗号，及返回长度
int i = 0;
// if (n > 0)
// {
// printf("<%c,%c>", a[0][0], a[0][1]);
// }
// for (i = 1; i < n; i++)
// {
// printf(",<%c,%c>", a[i][0], a[i][1]);
// }
for (i = 1; i <= n; i++)
{
printf(",<%c,%c>", a[i-1][0], a[i-1][1]);
}
//修改点2：合并if和for语句，使代码简洁易懂
printf("\n");
return n;
}
int printRelaMatrix(int M[][N], int n)
{
//打印关系矩阵的值
int i = 0, j = 0;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
printf("%4d", M[i][j]);
printf("\n");
}
}
int inputYsh(char a[])
{
//由于集合保存在一个字符串，但是输入时各字符是用逗号分隔的
//形参a是一个数组，送入是一个地址值，在函数对该数组的修改会反映在主函数
char nLen = 0, i = 0, j = 0, k = 0;
char stmp[1024];//最多1024个字符
printf("集合元素只能是A-Za-z0-9,其他字符被当作分隔符而去掉：\n");
gets(stmp);
fflush(stdin);
nLen = strlen(stmp);
for (i = 0; i < nLen; i++)
{
if (((stmp[i] >= 'A') && (stmp[i] <= 'Z')) ||
((stmp[i] >= 'a') && (stmp[i] <= 'z')) || ((stmp[i] >= '0') && (stmp[i] <= '9')))
//还要判断该字符 是否已经在a中出现过
if(strchr(a,stmp[i])==NULL)
{
a[j]=stmp[i];
j++;
}
//修改点3：用strchr函数来代替搜索过程
}
a[j] = '\0';
return j;//字符串的长度
}
int inputRelaYsh(char a[][3])
{
//由于序偶是保存在一个字符串，但是输入时各字符是用逗号分隔的
char nLen = 0, i = 0, j = 0;
int nbit = 0;
char stmp[1024];//最多1024个字符
printf("序偶只能是A-Za-z0-9。其他字符被当作分隔符而去掉，形如<a,b>:\n");
gets(stmp);
fflush(stdin);
nLen = strlen(stmp);
for (i = 0; i < nLen; i++)
{
if (((stmp[i] >= 'A') && (stmp[i] <= 'Z')) ||
((stmp[i] >= 'a') && (stmp[i] <= 'z')) ||
((stmp[i] >= '0') && (stmp[i] <= '9')))
{
a[j][nbit] = stmp[i];
nbit++;
if (nbit == 2)
{
a[j][2] = '\0';
j++;
nbit = 0;
}
}
}
return j;//字符串的长度
}
int relaCompose(char R[][3], char S[][3], char T[][3], int nR, int nS)
{
//关系的复合，让RS中每个序偶进行比较，组合成功的写入到T中
int i = 0, j = 0, k = 0, m = 0;
char a1 = ' ', a2 = ' ';
for (i = 0; i < nR; i++)
{
for (j = 0; j < nS; j++)
{
if (R[i][1] == S[j][0]) //<a,b> of R,<b,c> of S then <a,c> in T
{
a1 = R[i][0];//还要在T中寻找新序偶是否存在
a2 = S[j][1];
m = 0;
for (m = 0; m < k; m++)
{
//如果已经存在则中止
if ((T[m][0] == a1) && (T[m][1] == a2))
{
break;
}
}
if (m >= k) //如果原来不存在则加入其中
{
T[k][0] = a1;
T[k][1] = a2;
T[k][2] = '\0';
k++;
}
}
}
}
return k;
}
int relaSelf(char a[], char R[][3], int nR, char T[][3])
{
//自反闭包：判断集合a中各序偶是否在关系R中出现，若没出现则加入其中
int i = 0, j = 0, k = 0;
int nLen = 0;
nLen = strlen(a);
//先将关系R全部转抄到T中
for (i = 0; i < nR; i++)
{
T[i][0] = R[i][0];
T[i][1] = R[i][1];
}
for (i = 0; i < nLen; i++)
{
for (j = 0; j < nR; j++)
{
if ((R[j][0] == a[i]) && (R[j][1] == a[i])) //<x,x> in R
{
break;
}
}
if (j >= nR) //不在关系R中
{
T[j][0] = a[i];
T[j][1] = a[i];
T[j][2] = '\0';
nR++;
}
}
return nR;
}
int relaSym(char R[][3], char T[][3], int nR)
{
//自反闭包:判断集合a中各序偶是否在关系R中出现，若没出现加入其中
int i = 0, j = 0, k = 0;
int nLen = nR;
//先将关系R全部转抄到T中
for (i = 0; i < nR; i++)
{
T[i][0] = R[i][0];
T[i][0] = R[i][0];
}
for (i = 0; i < nR; i++)
{
for (j = 0; j < nR; j++)
{
//每个序偶到本关系中寻找对偶关系，若找到了则是对称，否则加上
if ((R[j][0] == R[i][1]) && (R[j][1] == R[i][0])) //<x,y>,<y,a> inR
{
break;
}
}
if (j >= nR) //不是成对出现
{
T[nLen][0] = R[i][1];
T[nLen][1] = R[i][0];
T[nLen][2] = '\0';
nLen++;
}
}
return nLen;
}
void rela2matrix(char a[], char R[][3], int nR, int M[][N])
{
//关系矩阵的行数与列数，等于基本元素即数组a中当前元素的个数
int i = 0, j = 0, na = 0, k = 0, m = 0;
na = strlen(a); //基本元素的个数
//关系矩阵的每个元素清0
// for (i = 0; i < na; i++)
// {
// for (j = 0; j < na; j++)
// {
// M[i][j] = 0;
// }
// }
memset(M,0,sizeof(M));
//修改点4：使用memset函数替代双重循环初始化数组
//寻找关系R中每个序偶之元素对应的序号，
//从而在数组M的指定位置置成1
for (i = 0; i < nR; i++)
{
//确定第i个序偶的首个元素在基本元素集中的序号
for (j = 0; j < na; j++)
{
if (R[i][0] == a[j])
{
k = j;
break;
}
}
//确定第i个序偶的次个元素在基本元素集中的序号
for (j = 0; j < na; j++)
{
if (R[i][1] == a[j])
{
m = j;
break;
}
}
M[k][m] = 1;
}
}
int matrix2rela(char a[], char R[][3], int M[][N])
{
int i = 0, j = 0, k = 0, nLen = 0;
nLen = strlen(a);
for (i = 0; i < nLen; i++)
{
for (j = 0; j < nLen; j++)
{
if (M[i][j] == 1)
{
//有次序偶则生成也
R[k][0] = a[i];
R[k][1] = a[j];
k++;
}
}
}
return k;
}
void matrixmulti(int M[][100], int R[][N], int T[][N], int n)
{
//两个方程相乘，超过二则为1
int i = 0, j = 0, k = 0, nsum = 0;
for (i = 0; i < n; i++)
{
for(j=0; j<n; j++)
{
nsum = 0;
for (k = 0; k < n; k++)
{
nsum = nsum + M[i][k] * R[k][j];
if (nsum >= 1)
{
nsum = 1;
break;
}
}
T[i][j] = nsum;
}
}
}
int trorder(char R[][3], char RM[][3], int nR, int n)
{
char T[1024][3], T2[1024][3];//关系R的i次方
int i = 0, nT = 0, j = 0, k = 0, nRM = 0, nT2 = 0;
//先将R保存到RM中
for (i = 0; i < nR; i++)
{
RM[i][0] = R[i][0];
RM[i][1] = R[i][1];
T[i][0] = R[i][0];
T[i][1] = R[i][1];
}
nRM = nR;
nT = nR;
for (i = 2; i <= n; i++)//n-1为止
{
//将R@R的复合函数暂存到T
printRelaYsh(T, nT);
printRelaYsh(R, nR);
nT2 = relaCompose(T, R, T2, nT, nR);
printRelaYsh(T2, nT2);
printf("\n");
//将复合以后的添加到R中，得到R+R@R，剔除重复的元素
for (j = 0; j < nT2; j++)
{
for (k = 0; k < nRM; k++)
{
if ((T2[j][0] == RM[k][0]) && (T2[j][1] == RM[k][1]))
{
break;
}
}
if (k >= nRM)//如果没有找到，则加入其中
{
RM[nRM][0] = T2[j][0];
RM[nRM][1] = T2[j][1];
nRM++;
}
}
//将T2复制给T
for (j = 0; j < nT2; j++)
{
T[j][0] = T2[j][0];
T[j][1] = T2[j][1];
}
nT = nT2;
}
return nRM;
}
int rPower(char R[][3], char T[][3], int nR, int n, int np)
{
//R的np次方
char T2[1024][3];//关系R的i次方
int i = 0, nT = 0, j = 0, k = 0, nRM = 0, nT2 = 0;
//先将R保存到T中
for (i = 0; i < nR; i++)
{
T[i][0] = R[i][0];
T[i][1] = R[i][1];
}
nT = nR;
for (i = 2; i <= np; i++) //n-1为止
{
//将T@R的复合暂存到T2
nT2 = relaCompose(T, R, T2, nT, nR);
//将T2复制给T
for (j = 0; j < nT2; j++)
{
T[j][0] = T2[j][0];
T[j][1] = T2[j][1];
}
nT = nT2;
}
return nT;
}
int trmatrix(int R[][N], int n)
{
int i = 0, j = 0, k = 0;
for (j = 0; j < n; j++)
{
for (i = 0; i < n; i++)
{
if (R[i][j] == 1)
{
for (k = 0; k < n; k++)
{
//将第j行加到第i行
R[i][k] = R[i][k] + R[j][k];
if (R[i][k] >= 1)
{
R[i][k] = 1;
}
}
}
}
}
return n;
}
int main()
{
char a[1024], R1[1024][3], R2[1024][3], T[1024][3];
int nLen1 = 0, nLen2 = 0, nT = 0, M[N][N], nChoice = 0;
int MR1[N][N], MR2[N][N];
int i = 0, n = 0;
bool flag=false;//修改点5：利用布尔函数优化交互
while (1)
{
printf("\n========================\n");
if(!flag)
printf("1...输入相关元素值\n");
if(flag)
{
printf("2...R1*R2关系的复合\n");
printf("3...自反闭包\n");
printf("4...对称闭包\n");
printf("5...序偶形式的关系转关系矩阵\n");
printf("6...利用矩阵求关系的复合\n");
printf("7...利用序偶形式的复合求传递闭包\n");
printf("8...利用warshall算法的求传递闭包\n");
//printf("9...R2*R1关系的复合\n");
//printf("10..R1的任意次方\n");
//printf("11..R2的任意次方\n");
}
printf("0...退出\n");
printf("========================\n您的选择: ");
//scanf("%d", &nChoice);
//fflush(stdin);
while(scanf("%d",&nChoice)){
fflush(stdin);
if((nChoice>=0&&nChoice<=8)) break;
else printf("请重新输入\n");}
//修改点6：利用while判断输入是否合法
if (nChoice == 0)
{
break;
}
switch (nChoice)
{
case 1:
{
flag=true;
printf("输入集合a:");
inputYsh(a);
printf("输入关系R1:");
nLen1 = inputRelaYsh(R1);
printf("输入关系R2:");
nLen2 = inputRelaYsh(R2);
printf("A:");
printYsh(a);
printf("关系R1:");
printRelaYsh(R1, nLen1);
printf("关系R2:");
printRelaYsh(R2, nLen2);
break;
}
case 2:
{
nT = relaCompose(R1, R2, T, nLen1, nLen2);
printf("R1@R2:");
printRelaYsh(T, nT);
break;
}
case 9:
{
nT = relaCompose(R2, R1, T, nLen2, nLen1);
printf("R2@R1:");
printRelaYsh(T, nT);
break;
}
case 3:
{
nT = relaSelf(a, R1, nLen1, T);
printf("R1的自反闭包：");
printRelaYsh(T, nT);
break;
}
case 4:
{
nT = relaSym(R1, T, nLen1);
printf("R1的对称闭包：");
printRelaYsh(T, nT);
break;
}
case 5:
{
//序偶形式的关系转换为矩阵形式
rela2matrix(a, R1, nLen1, M);
printf("R1关系的序偶");
printRelaYsh(R1, nLen1);
printf("R1关系的矩阵\n");
printRelaMatrix(M, strlen(a));
break;
}
case 6:
{
//利用矩阵求关系的复合
//先求出二个关系的关系矩阵
rela2matrix(a, R1, nLen1, MR1);
printf("R1关系的矩阵\n");
printRelaMatrix(MR1, strlen(a));
rela2matrix(a, R2, nLen2, MR2);
printf("R2关系的矩阵\n");
printRelaMatrix(MR2, strlen(a));
matrixmulti(MR1, MR2, M, strlen(a));
printf("复合后的矩阵\n");
printRelaMatrix(M, strlen(a));
printf("\n复合后的序偶");
nT = matrix2rela(a, T, M);
printRelaYsh(T, nT);
break;
}
case 7://trorder(char R[][3],char RM[][3],int nR,int n)
{
nT = trorder(R1, T, nLen1, strlen(a));
printf("R1的传递闭包:");
printRelaYsh(T, nT);
printf("\n序偶转化为数组\n");
rela2matrix(a, T, nT, M);
printRelaMatrix(M, strlen(a));
break;
}
case 8:
{
rela2matrix(a, R1, nLen1, M);
printf("R1关系的序偶");
printRelaYsh(R1, nLen1);
printf("R1关系中的矩阵\n");
printRelaMatrix(M, strlen(a));
trmatrix(M, strlen(a));
printf("warshall后的矩阵\n");
printRelaMatrix(M, strlen(a));
printf("\n序偶");
nT = matrix2rela(a, T, M);
printRelaYsh(T, nT);
break;
}
case 10:
{
printf("n=?");
scanf("%d", &n);
fflush(stdin);
nT = rPower(R1, T, nLen1, strlen(a), n);
printf("R1的%d次方：", n);
printRelaYsh(T, nT);
printf("\n序偶转换为数组\n");
rela2matrix(a, T, nT, M);
printRelaMatrix(M, strlen(a));
break;
}
case 11:
{
printf("n=?");
scanf("%d", &n);
fflush(stdin);
nT = rPower(R2, T, nLen2, strlen(a), n);
printf("R2的%d次方：", n);
printRelaYsh(T, nT);
printf("\n序偶转换为数组\n");
rela2matrix(a, T, nT, M);
printRelaMatrix(M, strlen(a));
break;
}
//序偶形式的关系到关系矩阵
/*
a,b,c,d,e
<a,b>;<b,c>;<a,d>;<c,e>;<e,a>;<d,b>
<b,a>;<c,b>;<d,a>;<e,c>;<a,e>;<b,d>
*/
}
}
}
图论
#include <bits/stdc++.h> //修改点1：万能头文件
#define N 100
using namespace std;
struct stree {
int pointa,pointb,weight;
};
int inputAdjaceEdge(int A[][N],int B[][N],int *n,int *m);
int inputAdjace(int A[][N],int *n);
int inputEdge(int B[][N],int n,int *m);
int printAll(int T[][N],int n,int m,char msg[]);
void calDegree(int A[][N],int n,int D[]);
void calDegreeB(int B[][N],int n,int m,int D[]);
void isEuler(int D[],int n);
void isHamilton(int D[],int n);
int warShall(int A[][N],int n);
int powerAdjace(int A[][N],int n);
int powellColor(int A[][N],int n,int Color[]);
int getEdge(int A[][N],int n,struct stree T[]);
void printTree(struct stree T[],int nT);
void sortEdge(struct stree T[],int nT);
int kruskal(struct stree T0[],int nt0,int n,struct stree T[]);
int prim(struct stree T0[],int nt0,int n,struct stree T[]);
/*
6
9
0 0 6 0 5 3
0 0 4 5 5 0
6 4 0 0 2 0
0 5 0 0 1 0
5 5 2 1 0 4
3 0 0 0 4 0
1 0 0 0 0 1 1 0 0
0 1 1 0 0 0 0 0 1
1 1 0 0 0 0 0 1 0
0 0 1 1 0 0 0 0 0
0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 0 0 0
*/
int main() { //修改点2：void改为int
struct stree st0[N],st1[N];
int A[N][N],B[N][N],D[N],Color[N];
int i=0,j=0,n=0,m=0;
int nChoice=1,nt0=0,nt=0;
while (1) {
printf("\n=========================================\n");
printf(" 1.输入邻接矩阵\n");
printf(" 11.输入关联矩阵\n");
printf(" 2.邻接矩阵求每点度数及判断图形性质\n");
printf(" 3.关联矩阵求每点度数及判断图形性质\n");
printf(" 4.用warshall算法判断是否连通\n");
printf(" 5.计算A，A平方，A立方,...\n");
printf(" 6.用powell染色算法对结点杂色\n");
printf(" 7.用Kruskal求最小生成树\n");
printf(" 8.用Prim求最小生成树\n");
printf("\n========================================\n");
printf("您的选择(输入0则结束)：");
while(scanf("%d",&nChoice)) //修改点2：判断输入是否合法
if((nChoice>=0&&nChoice<=8)) break;
else printf("请重新输入\n");
//scanf("%d",&nChoice);
fflush(stdin);
if (nChoice==0) {
break;
}
switch(nChoice) {
case 1: {
//inputAdjaceEdge(A,B,&n,&m);
inputAdjace(A,&n);
printAll(A,n,n,"邻接矩阵");
break;
}
case 11: {
inputEdge(B,n,&m);
printAll(B,n,m,"关联矩阵");
break;
}
case 2: {
calDegree(A,n,D);
isEuler(D,n);
isHamilton(D,n);
break;
}
case 3: {
calDegreeB(B,n,m,D);
isEuler(D,n);
isHamilton(D,n);
break;
}
case 4: {
warShall(A,n);
break;
}
case 5: {
powerAdjace(A,n);
break;
}
case 6: {
powellColor(A, n,Color);
printf("各点的颜色：\n");
for (i=0; i<n; i++) {
printf("%2d",Color[i]);
}
break;
}
case 7: {
nt0=getEdge(A,n,st0);
printTree(st0,nt0);
sortEdge(st0,nt0);
printTree(st0,nt0);
nt=kruskal(st0,nt0,n,st1);
printTree(st1,nt);
break;
}
case 8: {
nt0=getEdge(A,n,st0);
printTree(st0,nt0);
sortEdge(st0,nt0);
printTree(st0,nt0);
nt=prim(st0,nt0,n,st1);
printTree(st1,nt);
break;
}
}
}
}
/*int inputAdjaceEdge(int A[][N],int B[][N],int *n,int *m) { //修改点：删除没有用的函数
int i=0,j=0;
printf("点数：");
scanf("%d",n);
fflush(stdin);
printf("边数：");
scanf("%d",m);
fflush(stdin);
printf("n=%d m=%d\n",*n,*m);
printf("\n输入邻接矩阵的值：");
for (i=0; i<*n; i++) {
for (j=0; j<*n; j++) {
scanf("%d",&A[i][j]);
}
}
fflush(stdin);
printf("\n输入关联矩阵的值：");
for (i=0; i<*n; i++) {
for (j=0; j<*m; j++) {
scanf("%d",&B[i][j]);
}
}
return 1;
}*/
int inputAdjace(int A[][N],int *n) {
int i=0,j=0;
printf("点数：");
scanf("%d",n);
fflush(stdin);
printf("\n输入邻接矩阵的值：");
for (i=0; i<*n; i++) {
for (j=0; j<*n; j++) {
scanf("%d",&A[i][j]);
}
}
fflush(stdin);
return 1;
}
int inputEdge(int B[][N],int n,int *m) {
int i=0,j=0;
printf("边数：");
scanf("%d",m);
fflush(stdin);
printf("\n输入关联矩阵的值：");
for (i=0; i<n; i++) {
for (j=0; j<*m; j++) {
scanf("%d",&B[i][j]);
}
}
return 1;
}
int printAll(int T[][N],int n,int m,char msg[]) {
int i=0,j=0;
printf("\n%s：\n",msg);
for (i=0; i<n; i++) {
for (j=0; j<m; j++) {
printf("%4d",T[i][j]);
}
printf("\n");
}
return 1;
}
void calDegree(int A[][N],int n,int D[]) {
//求每个点的度数
int i=0,j=0;
for (i=0; i<n; i++) {
D[i]=0;
}
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
D[i]+=(A[i][j]==0?0:1);
}
}
}
void isEuler(int D[],int n) {
int nOdd=0,i=0;
int iOdd1=0,jOdd2=0;
printf("\n各点的度数：");
for (i=0; i<n; i++) {
printf("%4d",D[i]);
}
printf("\n");
for (i=0; i<n; i++) {
if (D[i]%2==1) {
nOdd++;
if (iOdd1==0) {
iOdd1=i;
} else {
jOdd2=i;
}
}
}
if (nOdd==0) {
printf("\n存在Euler回路，即为Euler图\n");
} else if (nOdd==2) {
printf("\n存在Euler路，起点为%d 终点为%d\n",iOdd1,jOdd2);
} else {
printf("\n不存在Euler路与回路\n");
}
}
void isHamilton(int D[],int n) {
int isHp=1,isHg=1;//前者是否存在Hamilton路,后者表示存在H回路
int i=0,j=0;
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
if (D[i]+D[j]<(n-1)) {
isHp=0;
isHg=0;
break;
} else if (D[i]+D[j]<n) {
isHg=0;
break;
}
}
if (isHp==0 ) {
break;
}
}
if (isHg==1) {
printf("为Hamilton图\n");
} else if ((isHp==1)&&(isHg==0)) {
printf("存在Hamilton路\n");
} else {
printf("不存在Hamilton路\n");
}
}
void calDegreeB(int B[][N],int n,int m,int D[]) {
//根据关联矩阵计算结点度数，每行数据中非0数字之和为度数
int i=0,j=0;
for (i=0; i<n; i++) {
D[i]=0;
}
for (i=0; i<n; i++) {
for (j=0; j<m; j++) {
if (B[i][j]!=0) {
D[i]++;
}
}
}
}
int warShall(int A[][N],int n) {
int P[N][N],i=0,j=0,k=0,n1Count=0;
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
P[i][j]=(A[i][j]>0?1:0);
}
}
for (j=0; j<n; j++) {
for (i=0; i<n; i++) {
if (P[i][j]==1) {
for (k=0; k<n; k++) {
P[i][k]=P[i][k]+P[j][k];
if (P[i][k]>=1) {
P[i][k]=1;
}
}
}
}
}
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
printf("%3d",P[i][j]);
n1Count+=P[i][j];
}
printf("\n");
}
if (n1Count==(n*n)) {
printf("图连通\n");
} else {
printf("图不连通\n");
}
return n1Count;
}
int powerAdjace(int A[][N],int n) {
//T T2是计算的中间结果，AA是所有幂次方的和 P规范化以后的矩阵
int T[N][N],T2[N][N],AA[N][N],A0[N][N];
char msg[100]="长度为",msgi[10];
int i=0,j=0,k=0,m=0;
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
A0[i][j]=(A[i][j]>0?1:0);
T[i][j]=A0[i][j];
AA[i][j]=A0[i][j];
}
}
printAll(A0,n,n,strcat(msg,"长度为1的路情况即直接相连的情况"));
//2--n次方
for (i=2; i<=n; i++) {
for (j=0; j<n; j++) {
for (k=0; k<n; k++) {
T2[j][k]=0;
for (m=0; m<n; m++) {
T2[j][k]=T2[j][k]+T[j][m]*A0[m][k];
}
AA[j][k]=AA[j][k]+T2[j][k];
}
}
for (j=0; j<n; j++) {
for (k=0; k<n; k++) {
T[j][k]=T2[j][k];
}
}
itoa(i,msgi,10);
strcpy(msg,"长度为");
strcat(msg,msgi);
strcat(msg,"的路情况");
printAll(T2,n,n,msg);
}
printAll(AA,n,n,"汇总表");
return 1;
}
int powellColor(int A[][N],int n,int Color[]) {
//先求出结点的度数
int D[N],subIndex[N],i=0,j=0,k=0,k0=0,itmp=0,thisColor[N],m=0,nthisColor=0;
for (i=0; i<n; i++) {
subIndex[i]=i;
Color[i]=0;
}
calDegree(A,n,D);
//将结点度从高到低排队
for (i=0; i<n-1; i++) {
for (j=0; j<n-1-i; j++) {
if (D[j]<D[j+1]) { //小于后面的互换，小的往后走
// itmp=D[j];
// D[j]=D[j+1];
// D[j+1]=itmp;
// itmp=subIndex[j];
// subIndex[j]=subIndex[j+1];
// subIndex[j+1]=itmp;
swap(D[j],D[j+1]); //修改点：用swap函数代替交换过程
swap(subIndex[j],subIndex[j+1]);
}
}
}
printf("排序后的结点度数：\n");
for (i=0; i<n; i++) {
printf("%4d[%1d]",D[i],subIndex[i]);
}
//排序后最先的颜色数
// 5[4] 3[0] 3[1] 3[2] 2[3] 2[5]各点的颜色：
itmp=0;//颜色号
for (i=0; i<n; i++) {
//thisColor清空
for (j=0; j<n; j++) {
thisColor[j]=0;
}
nthisColor=0;
//寻找未着色的第一个结点
j=0;
while ((D[j]==-1)&&(j<n)) {
j++;
}
if (j>=n) {
break;
}
k0=subIndex[j]; //未着色的结点号
itmp++; //新的颜色
Color[k0]=itmp; //着色
D[j]=-1; //已着色点度数为-1，表示已经处理过了
thisColor[nthisColor]=k0; //首种颜色的结点序号
printf("\nk0=%d j=%d nthisColor=%d itmp=%d\n",k0,j,nthisColor,itmp);
nthisColor++;//同色下一个结点保存位置号
j++; //下一个染色结点的寻找起始位置
//从j以后的点中寻找与本轮已经着色的点不相邻的点染相同的色
while (1) {
while ((D[j]==-1)&&(j<n)) {
j++;
}
if (j==n) {
break;
}
k=subIndex[j]; //找到了未染色的结点
//判断k是否与thisColor中点相邻
for (m=0; m<nthisColor; m++) {
//只要与一个相邻就
if (A[k][thisColor[m]]>0) {
break;
}
}
printf("j=%d n=%d k=%d m=%d nthisColor=%d\n",j,n,k,m,nthisColor);
if (m>=nthisColor) {
Color[k]=itmp;
thisColor[m]=k;
nthisColor++;
D[j]=-1;
}
j++; //下一下结点
}
}
return 0;
}
int getEdge(int A[][N],int n,struct stree T[]) {
int i=0,j=0,nstree=0;
for (i=0; i<n; i++) {
//因为对称，所以只要右上角就可以了
for (j=i; j<n; j++) {
if (A[i][j]>0) {
T[nstree].pointa=i;
T[nstree].pointb=j;
T[nstree].weight=A[i][j];
nstree++;
}
}
}
return nstree;
}
void printTree(struct stree T[],int nT) {
//打印树
int i=0;
for (i=0; i<nT; i++) {
printf("%d--%d(%d) ",T[i].pointa,T[i].pointb,T[i].weight);
}
}
void sortEdge(struct stree T[],int nT) {
struct stree t0;
int i=0,j=0;
for (i=0; i<nT-1; i++) {
for (j=0; j<nT-1-i; j++) {
if (T[j].weight>T[j+1].weight) {
//违反了低到高的原则，则要互换
swap(T[j],T[j+1]); //修改点：中间元交换值改为swap
}
}
}
}
int kruskal(struct stree T0[],int nt0,int n,struct stree T[]) {
//根据边权从低到高排好序，选择最小的n-1条边
int i=0,j=0,k=0,nt=0,B[N][N],m=0,mtmp=0,nCount=0;
T[nt]=T0[0];
nt++;
//针对每条边进行处理
for (i=1; i<nt0; i++) {
//判断当前边是否跟已经选定的边构成回路
//
//清空当前关联矩阵，最多到所有边
for (j=0; j<n; j++) {
for (k=0; k<nt0; k++) {
B[j][k]=0;
}
}
for (j=0; j<nt; j++) {
//第j条边的两个端点
B[T[j].pointa][j]=1;
B[T[j].pointb][j]=1;
}
//加上第i条边的二个端点
B[T0[i].pointa][j]=1;
B[T0[i].pointb][j]=1;
printf("加入新边后的关联矩阵\n");
for (j=0; j<n; j++) {
for (k=0; k<=nt; k++) {
printf("%4d",B[j][k]);
}
printf("\n");
}
//将首列第一个1所在行互换到首行，然后将剩下其他行清0
//从第0列到最后一列
for (k=0; k<=nt; k++) {
//从第k行起向下寻找首个1
for (j=k; j<n; j++) {
if (B[j][k]!=0) {
if (j>k) {
for (m=0; m<=nt; m++) {
mtmp=B[j][m];
B[j][m]=B[k][m];
B[k][m]=mtmp;
}
}
break;
}
}
//将k+1行--最后一行，减去第k行
for (j=k+1; j<n; j++) {
if (B[j][k]==1) {
for (m=k; m<=nt; m++) {
B[j][m]=B[j][m]-B[k][m]*B[j][k]/B[k][k];
}
}
}
}
printf("关联矩阵处理以后：\n");
for (j=0; j<n; j++) {
for (k=0; k<=nt; k++) {
printf("%4d",B[j][k]);
}
printf("\n");
}
//统计B[j][j]非0的个数
nCount=0;
for (k=0; k<=nt; k++) {
if (B[k][k]!=0) {
nCount++;
}
}
if (nCount==(nt+1)) {
//线性无关
T[nt]=T0[i];
nt++;
if (nt==(n-1)) {
break;
}
}
}
return nt;
}
int prim(struct stree T0[],int nt0,int n,struct stree T[]) {
//根据边权从低到高排好序，便于选择
int i=0,j=0,k=0,nt=0,B[N][N],m=0,mtmp=0,nCount=0;
int U[N],mDis=0,iDis=0,jtree=0,ntree=0;
//预置第0个点
U[nt]=0;
printf("U[%d]=%d\n",nt,U[nt]);
nt++;
//当点数没有到n时
while (nt<n) {
mDis=999999;
iDis=-1;
//依次寻找离散U中各点最近的点
for (i=0; i<nt; i++) {
k=U[i]; //U中点i的编号
//寻找离k最近的点
for (j=0; j<nt0; j++) {
//k出去的点
if (T0[j].pointa==k) {
if (mDis>T0[j].weight) {
mDis=T0[j].weight;
iDis=T0[j].pointb;
jtree=j;
}
}
//到k的点
else if (T0[j].pointb==k) {
if (mDis>T0[j].weight) {
mDis=T0[j].weight;
iDis=T0[j].pointa;
jtree=j;
}
}
}
}
//
U[nt]=iDis;//吸收最短的点进来
T[ntree]=T0[jtree];//吸收最短的边
T0[jtree].weight=999999;//这条边不能选了，给一个很大的数字
printf("nt=%d U[%d]=%d ntree=%d jtree=%d\n",nt,nt,U[nt],ntree,jtree);
ntree++;
nt++;
}
return ntree;
}