湖大离散数学实验代码汇总_坤斤拷的博客-程序员秘密_离散数学代码

技术标签: 学校课程  

整理一下大一上过的离散数学的实验代码...

!已整理至本人的 GitHub上:ljkjk/HNU-DiscreteMathematics-Experiment/湖南大学离散数学实验

实验一

/*
 * 实验一
 * 利用字符数组检索判断合式公式的合法性。 
 * by ljkjk
 */

/* 修改点1:使用万能头文件,减少了头文件的输入 */
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
void rule1(char a[],int i)
{
	if(a[i]>='a' && a[i]<='z') a[i]='1';
	else if(a[i]=='0') a[i]='1';
}
int rule2(char a[],int i)
{
	int n=strlen(a);
	int _result=0;

	if(i+1<n && a[i]=='!' && a[i+1]=='1')
	{
		a[i]='1';
		i++;
		while(a[i+1]!='\0')
		{
			a[i]=a[i+1];
			i++;
		}
		a[i]='\0';
		_result=1;
	}
	/* 修改点2:修改运算顺序的问题,优化了运算的逻辑,减少了出错的概率 */
	else if(i+3<n && a[i]=='!' && a[i+1]=='(' && a[i+2]=='1' && a[i+3]==')')
	{
		a[i]='1';
		i++;
		while(a[i+3]!='\0')
		{
			a[i]=a[i+3];
			i++;
		}
		a[i]='\0';
		_result=1;
	}
	else if(i+2<n && a[i]=='(' && a[i+1]=='1' && a[i+2]==')')
	{
		a[i]='1';
		i++;
		while(a[i+2]!='\0')
		{
			a[i]=a[i+2];
			i++;
		}
		a[i]='\0';
		_result=1;
	}
	/* 修改点3:增加遇到空格时的判断,避免输入格式问题 */
	else if(i<n && a[i]==' ')
	{
		while(a[i+1]!='\0')
		{
			a[i]=a[i+1];
			i++;
		}
		a[i]='\0';
		_result=1;
	}
	return _result;
}
int rule3Con(char a[],int i)
{
	int _result=0;
	int n=strlen(a);
	if(i+2<n && a[i]=='1' && a[i+1]=='*' && a[i+2]=='1')
	{
		a[i]='1';
		i++;
		while(a[i+2]!='\0')
		{
			a[i]=a[i+2];
			i++;
		}
		a[i]='\0';
		_result=1;
	}
	return _result;
}
int rule3BiCond(char a[],int i)
{
	int _result=0;
	int n=strlen(a);
	if(i+2<n && a[i]=='1' && a[i+1]=='=' && a[i+2]=='1')
	{
		a[i]='1';
		i++;
		while(a[i+2]!='\0')
		{
			a[i]=a[i+2];
			i++;
		}
		a[i]='\0';
		_result=1;
	}
	return _result;
}
int rule3Cond(char a[],int i)
{
	int _result=0;
	int n=strlen(a);
	if(i+2<n && a[i]=='1' && a[i+1]=='-' && a[i+2]=='1')
	{
		a[i]='1';
		i++;
		while(a[i+2]!='\0')
		{
			a[i]=a[i+2];
			i++;
		}
		a[i]='\0';
		_result=1;
	}
	return _result;
}
int rule3DisConj(char a[],int i)
{
	int _result=0;
	int n=strlen(a);
	if(i+2<n && a[i]=='1' && a[i+1]=='+' && a[i+2]=='1')
	{
		a[i]='1';
		i++;
		while(a[i+2]!='\0')
		{
			a[i]=a[i+2];
			i++;
		}
		a[i]='\0';
		_result=1;
	}
	return _result;
}
void rule3(char a[],int i)
{
	int n=strlen(a);
	if(i+2<n && a[i]=='1' && (a[i+1]=='*' || a[i+1]=='-' || a[i+1]=='=' || a[i+1]=='+') && a[i+2]=='1')
	{
		a[i]='1';
		i++;
		while(a[i+2]!='\0')
		{
			a[i]=a[i+2];
			i++;
		}
		a[i]='\0';
	}
}

int main()
{
	/* 修改点4:连续判断多个公式,方便了使用 */
	while(true)
	{
		char pstate[120],pstate0[120];
		int i=0,nold=0,nnew=0;
		printf("请输入公式(析+,合*,条-,双=,否定!,01):\n");
		gets(pstate0);
		fflush(stdin);

		nold=strlen(pstate0)+1;
		nnew=strlen(pstate0);
		for(i=0;i<nnew;i++)
			pstate[i]=pstate0[i];
		pstate[i]='\0';
		i=0;
		while(i<strlen(pstate))
		{
			rule1(pstate,i);
			i++;
		}
		printf("规则1后:%s\n",pstate);

		nold=strlen(pstate0)+1;
		nnew=strlen(pstate);
		/* 修改点5:优化了显示逻辑,只输出需要进行的步骤,便于理解 */
		while(nnew<nold)
		{
			nold=strlen(pstate);
			i=0;
			bool flag=false;
			while(i<strlen(pstate))
				if(rule2(pstate,i)==0)
					i++;
				else flag=true;
			if(flag) printf("规则2后:%s\n",pstate);

			i=0;
			flag=false;
			while(i<strlen(pstate))
				if(rule3Con(pstate,i)==0)
					i++;
				else flag=true;
			if(flag) printf("规则3合取后:%s\n",pstate);

			i=0;
			flag=false;
			while(i<strlen(pstate))
				if(rule3BiCond(pstate,i)==0)
					i++;
				else flag=true;
			if(flag) printf("规则3双条件后:%s\n",pstate);

			i=0;
			flag=false;
			while(i<strlen(pstate))
				if(rule3Cond(pstate,i)==0)
					i++;
				else flag=true;
			if(flag) printf("规则3单条件后:%s\n",pstate);

			i=0;
			flag=false;
			while(i<strlen(pstate))
				if(rule3DisConj(pstate,i)==0)
					i++;
				else flag=true;
			if(flag) printf("规则3析取后:%s\n",pstate);

			nnew=strlen(pstate);
		}
		if(pstate[0]=='1' && strlen(pstate)==1)
			printf("%s is valid\n\n",pstate0);
		else
			printf("%s is invalid\n\n",pstate0);
	}
	return 0;
}

实验二

/*
 * 实验二
 * 输出合式公式的真值表以及主析取范式
 * by ljkjk
 */

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int getalpha(char a[],char b[])
{
    int n=strlen(a),i=0,j=0,k=0;
    for(i=0;i<n;++i)
        if((a[i]>='a'&&a[i]<='z')||(a[i]>='A'&&a[i]<='Z'))
        {
            /* 修改点1:用strchr函数替代循环搜索,优化了运行速度 */
            if(strchr(b,a[i])==NULL)
            {
                b[j]=a[i];
                j++;
            }
        }
    /* 修改点2:用sort函数替代冒泡排序,优化了运行速度 */
    sort(b,b+j);
    b[j]='\0';
    return j;
}

void fillvalue(char a[],char varchar[],int nvar,char valchar[],char resultchar[])
{
    int nLen=strlen(a),i=0,j=0,k=0;
    for(i=0;i<nLen;++i)
        resultchar[i]=a[i];
    resultchar[i]='\0';
    for(i=0;i<nLen;++i)
        for(j=0;j<nvar;++j)
            if(resultchar[i]==varchar[j])
            {
                resultchar[i]=valchar[j];
                break;
            }
}

/* 修改点3:重复代码编写成函数,减少代码量 */
void eraser(int r,int &i,int &j,char a[],int w)
{
    if(r==1)
    {
        j++;
        while(a[j+w]!='\0')
        {
            a[j]=a[j+w];
            j++;
        }
        a[j]='\0';
    }
    else
        i++;
}

void negatecal(char a[])
{
    int _result=0,i=0,j=0;
    while(i<strlen(a))
    {
        j=i;
        _result=0;
        if(j+1<strlen(a)&&a[j]=='!'&&a[j+1]=='1')
        {
            a[j]='0';
            _result=1;
        }
        else if(j+1<strlen(a)&&a[j]=='!'&&a[j+1]=='0')
        {
            a[j]='1';
            _result=1;
        }
        eraser(_result,i,j,a,1);
    }
}

void bracket(char a[])
{
    int _result=0,i=0,j=0;
    while(i<strlen(a))
    {
        j=i;
        _result=0;
        if(j+2<strlen(a)&&a[j]=='('&&a[j+1]=='1'&&a[j+2]==')')
        {
            a[j]='1';
            _result=1;
        }
        else if(j+2<strlen(a)&&a[j]=='('&&a[j+1]=='0'&&a[j+2]==')')
        {
            a[j]='0';
            _result=1;
        }
        eraser(_result,i,j,a,2);
    }
}

void con(char a[])
{
    int _result=0,i=0,j=0;
    while(i<strlen(a))
    {
        j=i;
        _result=0;
        if(j+2<strlen(a)&&a[j]=='0'&&a[j+1]=='*'&&a[j+2]=='0')
        {
            a[j]='0';
            _result=1;
        }
        else if(j+2<strlen(a)&&a[j]=='0'&&a[j+1]=='*'&&a[j+2]=='1')
        {
            a[j]='0';
            _result=1;
        }
        else if(j+2<strlen(a)&&a[j]=='1'&&a[j+1]=='*'&&a[j+2]=='0')
        {
            a[j]='0';
            _result=1;
        }
        else if(j+2<strlen(a)&&a[j]=='1'&&a[j+1]=='*'&&a[j+2]=='1')
        {
            a[j]='1';
            _result=1;
        }
        eraser(_result,i,j,a,2);
    }
}

void bicond(char a[])
{
    int _result=0,i=0,j=0;
    while(i<strlen(a))
    {
        j=i;
        _result=0;
        if(j+2<strlen(a)&&a[j]=='0'&&a[j+1]=='='&&a[j+2]=='0')
        {
            a[j]='1';
            _result=1;
        }
        else if(j+2<strlen(a)&&a[j]=='0'&&a[j+1]=='='&&a[j+2]=='1')
        {
            a[j]='0';
            _result=1;
        }
        else if(j+2<strlen(a)&&a[j]=='1'&&a[j+1]=='='&&a[j+2]=='0')
        {
            a[j]='0';
            _result=1;
        }
        else if(j+2<strlen(a)&&a[j]=='1'&&a[j+1]=='='&&a[j+2]=='1')
        {
            a[j]='1';
            _result=1;
        }
        eraser(_result,i,j,a,2);
    }
}

void cond(char a[])
{
    int _result=0,i=0,j=0;
    while(i<strlen(a))
    {
        j=i;
        _result=0;
        if(j+2<strlen(a)&&a[j]=='0'&&a[j+1]=='-'&&a[j+2]=='0')
        {
            a[j]='1';
            _result=1;
        }
        else if(j+2<strlen(a)&&a[j]=='0'&&a[j+1]=='-'&&a[j+2]=='1')
        {
            a[j]='1';
            _result=1;
        }
        else if(j+2<strlen(a)&&a[j]=='1'&&a[j+1]=='-'&&a[j+2]=='0')
        {
            a[j]='0';
            _result=1;
        }
        else if(j+2<strlen(a)&&a[j]=='1'&&a[j+1]=='-'&&a[j+2]=='1')
        {
            a[j]='1';
            _result=1;
        }
        eraser(_result,i,j,a,2);
    }
}

void disconj(char a[])
{
    int _result=0,i=0,j=0;
    while(i<strlen(a))
    {
        j=i;
        _result=0;
        if(j+2<strlen(a)&&a[j]=='0'&&a[j+1]=='+'&&a[j+2]=='0')
        {
            a[j]='0';
            _result=1;
        }
        else if(j+2<strlen(a)&&a[j]=='0'&&a[j+1]=='+'&&a[j+2]=='1')
        {
            a[j]='1';
            _result=1;
        }
        else if(j+2<strlen(a)&&a[j]=='1'&&a[j+1]=='+'&&a[j+2]=='0')
        {
            a[j]='1';
            _result=1;
        }
        else if(j+2<strlen(a)&&a[j]=='1'&&a[j+1]=='+'&&a[j+2]=='1')
        {
            a[j]='1';
            _result=1;
        }
        eraser(_result,i,j,a,2);
    }
}

/* 修改点4:标准化输入,避免输入格式错误 */
void getformula(char a[])
{
    char cc;
    int cnt=0;
    while((cc=getchar())!='\n')
        if((cc>='a'&&cc<='z')||(cc>='A'&&cc<='Z')||cc=='='||cc=='-'||
           cc=='+'||cc=='*'||cc=='!'||cc=='0'||cc=='1'||cc=='('||cc==')')
            a[cnt++]=cc;
}

int main()
{
    /* 修改点5:持续化输入,方便使用 */
    while(1)
    {
        char pstate[120]={' '},pstate0[120]={' '},charlist[120]={' '},charval[120]={' '};
        char minitem[1024][52]={' '},maxitem[1024][52]={' '},truetable[1024]={' '};
        int i=0,nold=0,nnew=0,nvar=1,nrow=1,j=0,flagsum=1,iminitem=0,imaxitem=0;
        printf("请输入公式(析+,合*,条-,双=,否定!,01):\n");
        //gets(pstate0);
        getformula(pstate0);
        fflush(stdin);

        nold=strlen(pstate0)+1;
        nnew=strlen(pstate0);
        for(i=0;i<nnew;++i)
            pstate[i]=pstate0[i];
        pstate[i]='\0';
        nvar=getalpha(pstate,charlist);
        nrow=1;
        for(i=0;i<nvar;++i)
        {
            charval[i]='0';
            /* 修改点6:用位运算加速乘法,优化了运行速度 */
            nrow<<=1;
        }
        charval[i]='\0';

        printf("\n");
        for(i=0;i<nvar;++i)
            printf("%4c",charlist[i]);
        printf("%15c%s\n",' ',pstate);
        for(i=0;i<nvar;++i)
            printf("%4c",'-');
        printf("|");
        for(i=0;i<60;++i)
            printf("%c",'-');
        printf("\n");

        int sum=1;
        for(i=0;i<nrow;++i)
        {
            for(j=0;j<nvar;++j)
                printf("%4c",charval[j]);
            pstate[0]='\0';
            fillvalue(pstate0,charlist,nvar,charval,pstate);
            nold=strlen(pstate0)+1;
            nnew=strlen(pstate);
            while(nnew<nold)
            {
                nold=strlen(pstate);
                negatecal(pstate);
                bracket(pstate);
                con(pstate);
                bicond(pstate);
                cond(pstate);
                disconj(pstate);
                nnew=strlen(pstate);
            }
            if(strlen(pstate)==1)
            {
                if(pstate[0]=='1')
                {
                    for(j=0;j<nvar;++j)
                        minitem[iminitem][j]=charval[j];
                    minitem[iminitem][j]='\0';
                    iminitem++;
                }
                else if(pstate[0]=='0')
                {
                    for(j=0;j<nvar;++j)
                        maxitem[imaxitem][j]=charval[j];
                    maxitem[imaxitem][j]='\0';
                    imaxitem++;
                }
                truetable[i]=pstate[0];
            }

            printf("%20c%s",' ',pstate);
            printf("\n");
            /* 修改点7:优化为变元赋值的逻辑,优化了运行速度 */
            int tmp=sum;
            for(int j=nvar-1;j>=0;--j)
            {
                charval[j]=(tmp%2+'0');
                tmp/=2;
            }
            sum++;
        }
        printf("\n");

        printf("主析取范式:\n");
        for(i=0;i<iminitem;++i)
            if(i==0)
                printf("m%s",minitem[i]);
            else
                printf("+m%s",minitem[i]);
        printf("\n");
        for(i=0;i<iminitem;++i)
            if(i==0)
            {
                printf("(");
                for(j=0;j<nvar;++j)
                {
                    if(j==0)
                        if(minitem[i][j]=='1')
                            printf("%c",charlist[j]);
                        else
                            printf("!%c",charlist[j]);
                    else
                        if(minitem[i][j]=='1')
                            printf("*%c",charlist[j]);
                        else
                            printf("*!%c",charlist[j]);
                }
                printf(")");
            }
            else
            {
                printf("+(");
                for(j=0;j<nvar;++j)
                {
                    if(j==0)
                        if(minitem[i][j]=='1')
                            printf("%c",charlist[j]);
                        else
                            printf("!%c",charlist[j]);
                    else
                        if(minitem[i][j]=='1')
                            printf("*%c",charlist[j]);
                        else
                            printf("*!%c",charlist[j]);
                }
                printf(")");
            }
        printf("\n\n");

        /* 修改点8:添加主合取范式的输出,丰富了功能 */
        printf("主合取范式:\n");
        for(i=0;i<imaxitem;++i)
            if(i==0)
                printf("M%s",maxitem[i]);
            else
                printf("*M%s",maxitem[i]);
        printf("\n");
        for(i=0;i<imaxitem;++i)
            if(i==0)
            {
                printf("(");
                for(j=0;j<nvar;++j)
                {
                    if(j==0)
                        if(maxitem[i][j]=='0')
                            printf("%c",charlist[j]);
                        else
                            printf("!%c",charlist[j]);
                    else
                        if(maxitem[i][j]=='0')
                            printf("+%c",charlist[j]);
                        else
                            printf("+!%c",charlist[j]);
                }
                printf(")");
            }
            else
            {
                printf("*(");
                for(j=0;j<nvar;++j)
                {
                    if(j==0)
                        if(maxitem[i][j]=='0')
                            printf("%c",charlist[j]);
                        else
                            printf("!%c",charlist[j]);
                    else
                        if(maxitem[i][j]=='0')
                            printf("+%c",charlist[j]);
                        else
                            printf("+!%c",charlist[j]);
                }
                printf(")");
            }
        printf("\n\n");
    }
	return 0;
}

实验三

/*
 * 实验三
 * 利用程序进行自然推理
 * by ljkjk
 */

/* 修改点1:万能头文件,减少了头文件的输入 */
#include <bits/stdc++.h>
using namespace std;
struct tmd{
    char gs[120],gslast[120],reason[120];
    int nletter,nused,isletter,iscond;
};

void nonoop2(char aa[])
{

    int i=0,j=0;
    while(i<strlen(aa)-2)
    {
        if(i+1<strlen(aa)&&aa[i]=='!'&&aa[i+1]=='!')
        {
            j=i;
            while(j<strlen(aa)-2)
            {
                aa[j]=aa[j+2];
                j++;
            }
            aa[j]='\0';
            break;
        }
        else
           i++;
    }
}

void print(tmd tmrec[],int np)
{
    int i=0;
    for(i=0;i<np;++i)
    {
        if(tmrec[i].isletter==1)
            printf("(%d)\t%s为真\t\t\t%s---文字\n",i+1,tmrec[i].gs,tmrec[i].reason);
        else if(tmrec[i].iscond==1)
            printf("(%d)\t%s-%s为真\t\t\t%s---条件式\n",i+1,tmrec[i].gs,tmrec[i].gslast,tmrec[i].reason);
        else
            printf("(%d)\t%s为真\t\t\t%s\n",i+1,tmrec[i].gs,tmrec[i].reason);
    }
}

int setreason(tmd tmrec[],int np,string r0,int j0,int j1,int nused0,int iscond0,int isletter0)
{
    char stmpj0[20],stmpj1[20];
    int nlen1=0,j=0,nlenj0=0,nlenj1=0;
    nlen1=r0.length();
    itoa(j0+1,stmpj0,10);
    nlenj0=strlen(stmpj0);
    itoa(j1+1,stmpj1,10);
    nlenj1=strlen(stmpj1);
    if(j0==-1)//输出“前提条件”
    {
        for(j=0;j<nlen1;++j)
            tmrec[np].reason[j]=r0[j];
        tmrec[np].reason[j]='\0';
    }
    else if(j1==-1)
    {
        tmrec[np].reason[0]='(';
        for(j=0;j<nlenj0;++j)
            tmrec[np].reason[j+1]=stmpj0[j];
        tmrec[np].reason[j+1]=')';

        for(j=0;j<nlen1;++j)
            tmrec[np].reason[j+2+nlenj0]=r0[j];
        tmrec[np].reason[j+2+nlenj0]='\0';
    }
    else
    {
        tmrec[np].reason[0]='(';
        for(j=0;j<nlenj0;++j)
            tmrec[np].reason[j+1]=stmpj0[j];
        tmrec[np].reason[j+1]=')';

        tmrec[np].reason[nlenj0+2]='(';
        for(j=0;j<nlenj1;++j)
            tmrec[np].reason[nlenj0+3+j]=stmpj1[j];
        tmrec[np].reason[nlenj0+3+j]=')';

        for(j=0;j<nlen1;++j)
            tmrec[np].reason[nlenj0+nlenj1+4+j]=r0[j];
        tmrec[np].reason[nlenj0+nlenj1+4+j]='\0';
    }
    tmrec[np].nused=nused0;
    tmrec[np].iscond=iscond0;
    tmrec[np].isletter=isletter0;
}

/* 修改点2:调换了inputprimary函数与setreason函数的位置,解决了报错的问题 */
int inputprimary(tmd gs0[])
{
    tmd tmp;
    char pstate[120];
    /* 修改点3:用string替换字符数组,消除了警告 */
    string r0="前提条件";
    string r1="原命题的逆否命题";
    string r2="双条件导出的条件式";
    string r3="析取式转换为条件式";

    int i=0,j=0,nlen=0,k=0;
    int i0=0;
    printf("输完一个前提条件请按回车,不输直接回车则结束\n析+,合-,条-,双=,否定!\n前提中只能为双条件、单条件、析取式,\n若为两个个条件的合取,请输入两个前提,文字请在最前面输入:\n");
    while(1)
    {
        gets(pstate);
        nlen=strlen(pstate);
        if(nlen==0)
            break;
        if(nlen==1)
        {
            gs0[i].nletter=strlen(pstate);
            gs0[i].gs[0]=pstate[0];
            gs0[i].gs[1]='\0';
            gs0[i].gslast[0]='\0';
            setreason(gs0,i,r0,-1,-1,0,0,1);
        }
        else if(nlen==2&&pstate[0]=='!')
        {
            gs0[i].nletter=strlen(pstate);
            gs0[i].gs[0]=pstate[0];
            gs0[i].gs[1]=pstate[1];
            gs0[i].gs[2]='\0';
            gs0[i].gslast[0]='\0';
            setreason(gs0,i,r0,-1,-1,0,0,1);
        }
        else
        {
            for(j=0;j<nlen;++j)
            {
                if(pstate[j]=='-')
                {
                    gs0[i].nletter=strlen(pstate);
                    for(k=0;k<j;++k)
                        gs0[i].gs[k]=pstate[k];
                    gs0[i].gs[k]='\0';
                    for(k=j+1;k<nlen;++k)
                        gs0[i].gslast[k-j-1]=pstate[k];
                    gs0[i].gslast[k-j-1]='\0';
                    setreason(gs0,i,r0,-1,-1,0,1,0);
                    i++;
                    gs0[i].nletter=gs0[i-1].nletter;
                    gs0[i].gslast[0]='!';
                    for(k=0;k<j;++k)
                        gs0[i].gslast[k+1]=pstate[k];
                    gs0[i].gslast[k+1]='\0';
                    nonoop2(gs0[i].gslast);

                    gs0[i].gs[0]='!';
                    for(k=j+1;k<nlen;++k)
                        gs0[i].gs[k-j-1+1]=pstate[k];//>??????
                    gs0[i].gs[k-j-1+1]='\0';
                    nonoop2(gs0[i].gs);
                    setreason(gs0,i,r1,i-1,-1,0,1,0);
                    break;
                }
                else if(pstate[j]=='=')
                {
                    gs0[i].nletter=strlen(pstate);
                    for(k=0;k<strlen(pstate);++k)
                        gs0[i].gs[k]=pstate[k];
                    gs0[i].gs[k]='\0';
                    gs0[i].gslast[0]='\0';
                    setreason(gs0,i,r0,-1,-1,0,0,0);
                    i++;
                    gs0[i].nletter=strlen(pstate);
                    for(k=0;k<j;++k)
                        gs0[i].gslast[k-j-1]=pstate[k];
                    gs0[i].gslast[k-j-1]='\0';
                    setreason(gs0,i,r2,i-1,-1,0,1,0);
                    i++;
                    gs0[i].nletter=gs0[i-1].nletter;
                    for(k=0;k<j;++k)
                        gs0[i].gslast[k]=pstate[k];
                    gs0[i].gs[k-j-1]='\0';
                    setreason(gs0,i,r2,i-2,-1,0,1,0);
                    break;
                }
                else if(pstate[j]=='+')
                {
                    gs0[i].nletter=strlen(pstate);
                    for(k=0;k<strlen(pstate);++k)
                        gs0[i].gs[k]=pstate[k];
                    gs0[i].gs[k]='\0';
                    gs0[i].gslast[0]='\0';
                    setreason(gs0,i,r0,-1,-1,0,0,0);
                    i++;
                    gs0[i].nletter=strlen(pstate);
                    gs0[i].gs[0]='!';
                    for(k=0;k<j;++k)
                        gs0[i].gs[k+1]=pstate[k];
                    gs0[i].gs[k+1]='\0';
                    for(k=j+1;k<nlen;++k)
                        gs0[i].gslast[k-j-1]=pstate[k];
                    gs0[i].gslast[k-j-1]='\0';
                    setreason(gs0,i,r3,i-1,-1,0,1,0);
                    nonoop2(gs0[i].gs);
                    i++;
                    gs0[i].nletter=strlen(pstate);
                    for(k=0;k<j;++k)
                        gs0[i].gslast[k]=pstate[k];
                    gs0[i].gslast[k]='\0';
                    gs0[i].gs[0]='!';
                    for(k=j+1;k<nlen;++k)
                        gs0[i].gs[k-j-1+1]=pstate[k];
                    gs0[i].gs[k-j-1+1]='\0';
                    setreason(gs0,i,r3,i-2,-1,0,1,0);
                    nonoop2(gs0[i].gs);
                    break;
                }
            }
            if(j>=nlen)
            {
                gs0[i].nletter=strlen(pstate);
                for(k=0;k<nlen;++k)
                    gs0[i].gs[k]=pstate[k];
                gs0[i].gs[k]='\0';
                gs0[i].gslast[0]='\0';
                setreason(gs0,i,r0,-1,-1,0,0,0);
            }
        }
        i++;
    }
    nlen=i;
    for(i=0;i<nlen-1;++i)
    {
        k=i;
        /* 修改点4:将nlen-1改为nlen,否则最后一个元素无法排序 */
        for(j=i+1;j<nlen;++j)
            if(gs0[k].nletter>gs0[j].nletter)
                k=j;
        /* 修改点5:用swap替代中间元交换两个数的值,使代码简洁 */
        if(k>i) swap(gs0[i],gs0[k]);
    }
    return nlen;
}


int main()
{
    /* 修改点6:连续输入 */
    while(1)
    {
        tmd gs0[100];
	char result0[128];
	tmd tmrec[1024];
	char stmp[128];
	char lastreason[128]="";
	string r01="假言推理";
	int i=0,j=0,k=0;
	int np=1,np0=0,is0k=0;
	int i0=0,nposletter=0,nposcond=0;

	np0=inputprimary(gs0);
	printf("输入要推理的结论,结论只能是文字,\n若是条件式、析取式请先手工转换为条件,将前件作为附加前提:\n");
    gets(result0);
    fflush(stdin);

    for(i=0;i<np0;++i)
        tmrec[i]=gs0[i];

    np=i;
    nposletter=0;
    nposcond=0;
    is0k=0;
    i0=-1;
    while(1)
    {
        i=i0+1;
        while(i<np&&tmrec[i].isletter!=1)
            i++;
        if(i>=np)
            break;
        i0=i;
        nposletter=i;
        strcpy(stmp,tmrec[i].gs);
        np0=np-1;
        while(np>np0)
        {
            np0=np;
            for(i=0;i<np;++i)
                if(tmrec[i].iscond==1&&tmrec[i].nused==0)
                    break;
            if(i==np)
                break;
            while(i<np)
            {
                if(tmrec[i].iscond==1)
                    if((strcmp(lastreason,tmrec[i].reason)!=0)||
                       (strcmp(lastreason,tmrec[i].reason)==0&&tmrec[i].reason[0]!='('))
                        if(strcmp(tmrec[i].gs,stmp)==0)
                        {
                            strcpy(lastreason,tmrec[i].reason);
                            tmrec[nposletter].nused++;
                            tmrec[i].nused++;
                            strcpy(stmp,tmrec[i].gslast);
                            strcpy(tmrec[np].gs,stmp);
                            tmrec[np].gslast[0]='\0';
                            setreason(tmrec,np,r01,nposletter,i,0,0,1);
                            nposletter=np;
                            np++;
                            if(strcmp(result0,stmp)==0)
                            {
                                is0k=1;
                                break;
                            }
                        }
                i++;
            }
        }
        if(is0k==1)
            break;
    }
    if(is0k==1)
        printf("推理成立,推理过程如下:\n");
    else
        printf("推理不成立,推理过程如下:\n");
    print(tmrec,np);
    printf("\n\n");
    }

	return 0;
}

实验四

/*
 * 实验四
 * 利用消解法进行推理
 * by ljkjk
 */

#include <string.h>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>

struct tmd
{
	char gs[120], gsLast[120], niyou[120];//前件与后件及理由
	int nLitter, nUsed, isLitter, isCond;
};

void nonoop2( char aa[] )
{
	//!!p=p
	int i = 0, j = 0;
	while (i < strlen( aa ) - 2)
	{
		//至少还有两个字符
		if (((i + 1) < strlen( aa )) && (aa[i] == '!') && (aa[i + 1] == '!'))
		{
			j = i;
			while (j < strlen( aa ) - 2)
			{
				aa[j] = aa[j + 2];
				j++;
			}
			aa[j] = '\0';
			break;
		}
		else
			i++;
	}
}

void printYsh( struct tmd tmdrec[], int np )
{
	int i = 0;
	for (i = 0; i < np; i++)
	{
		if (tmdrec[i].isLitter == 1)
			printf( "(%d)\t%s为真\t\t\t%s---文字\n", i + 1, tmdrec[i].gs, tmdrec[i].niyou );
		else if (tmdrec[i].isCond == 1)
			printf( "(%d)\t%s+%s为真\t\t\t%s---析取式\n", i + 1, tmdrec[i].gs, tmdrec[i].gsLast, tmdrec[i].niyou );
		else
			printf( "(%d)\t%s为真\t\t\t%s\n", i + 1, tmdrec[i].gs, tmdrec[i].niyou );
	}
}

/* 修改点1:调换函数位置,否则会出现调用未定义函数的情况 */
int setNiyou( struct tmd tmdrec[], int np, char ny0[], int j0, int j1, int nUsed0, int isCond0, int isLitter0 )
{
	//将字符串ny0与j0赋到推理意见中
	char stmdpj0[20], stmdpj1[20];
	int nLen1 = 0, j = 0, nLenj0 = 0, nLenj1 = 0;
	nLen1 = strlen( ny0 );
	itoa( j0 + 1, stmdpj0, 10 );
	nLenj0 = strlen( stmdpj0 );//前一个依据
	itoa( j1 + 1, stmdpj1, 10 );
	nLenj1 = strlen( stmdpj1 );//后一个依据
	if (j0 == -1)
	{
		//原始前提
		for (j = 0; j < nLen1; j++)
			tmdrec[np].niyou[j] = ny0[j];
		tmdrec[np].niyou[j] = '\0';
	}
	else if (j1 == -1)//由前一步推理所得结论
	{
		tmdrec[np].niyou[0] = '(';
		for (j = 0; j < nLenj0; j++)
			tmdrec[np].niyou[j + 1] = stmdpj0[j];
		tmdrec[np].niyou[j + 1] = ')';

		for (j = 0; j < nLen1; j++)
			tmdrec[np].niyou[j + 2 + nLenj0] = ny0[j];
		tmdrec[np].niyou[j + 2 + nLenj0] = '\0';
	}
	else
	{
		//由前二步推理所得
		tmdrec[np].niyou[0] = '(';
		for (j = 0; j < nLenj0; j++)
			tmdrec[np].niyou[j + 1] = stmdpj0[j];
		tmdrec[np].niyou[j + 1] = ')';

		tmdrec[np].niyou[nLenj0 + 2] = '(';
		for (j = 0; j < nLenj1; j++)
			tmdrec[np].niyou[nLenj0 + 3 + j] = stmdpj1[j];
		tmdrec[np].niyou[nLenj0 + 3 + j] = ')';

		for (j = 0; j < nLen1; j++)
			tmdrec[np].niyou[nLenj0 + nLenj1 + 4 + j] = ny0[j];
		tmdrec[np].niyou[nLenj0 + nLenj1 + 4 + j] = '\0';
	}

	tmdrec[np].nUsed = nUsed0;//附加前提从未使用过nUsed0,int isCond0,int isLitter0
	tmdrec[np].isCond = isCond0;//是条件式
	tmdrec[np].isLitter = isLitter0;//是文字
}

void swaptmd(tmd &a,tmd &b)
{
    tmd temp;
    temp=a;
    a=b;
    b=temp;
}


int inputPrimary( struct tmd gs0[] )
{
	struct tmd tmdp;
	char pstate[120];
	char *ny0 = "前提条件";
	char *ny1 = "条件式转为析取式";
	char *ny2 = "双条件导出的析取式";
	int i = 0, j = 0, nLen = 0, k = 0;
	int i0 = 0;//原始条件
	printf( "输完一个前提条件请按回车,不输直接回车则结束\n析+,合*,条-,双=,否定!\n前提中只能为双条件、单条件、析取式,\n若为2个条件的合取,请输入2个前提,文字请在最前面输入:\n" );
	while (1)
	{
		gets( pstate );
		nLen = strlen( pstate );
		if (nLen == 0)
		{
			break;
		}//设置nUsed,isLitter,isCond,nLittle的值
		//判断是否为文字
		if (nLen == 1)//标注单个文字
		{
			gs0[i].nLitter = strlen( pstate );
			gs0[i].gs[0] = pstate[0];
			gs0[i].gs[1] = '\0';
			gs0[i].gsLast[0] = '\0';
			setNiyou( gs0, i, ny0, -1, -1, 0, 0, 1 );//前提类型,无,无,未使用,不是条件式,是文字
		}
		else if ((nLen == 2) && (pstate[0] == '!')) //标注!p
		{
			gs0[i].nLitter = strlen( pstate );
			gs0[i].gs[0] = pstate[0];
			gs0[i].gs[1] = pstate[1];
			gs0[i].gs[2] = '\0';
			gs0[i].gsLast[0] = '\0';
			setNiyou( gs0, i, ny0, -1, -1, 0, 0, 1 );//前提类型,无,无,未使用,不是条件式,是文字
		}
		else
		{
			for (j = 0; j < nLen; j++)
			{
				if (pstate[j] == '-')//标注条件式p-q
				{
					gs0[i].nLitter = strlen( pstate );
					for (k = 0; k < nLen; k++)
						gs0[i].gs[k] = pstate[k];//整个表达式进入gs
					gs0[i].gs[k] = '\0';
					gs0[i].gsLast[0] = '\0';
					setNiyou( gs0, i, ny0, -1, -1, 0, 0, 0 );//前提类型,无,无,未使用,不是析取式,不是文字

					i++;
					gs0[i].nLitter = gs0[i - 1].nLitter;
					gs0[i].gs[0] = '!';
					for (k = 0; k < j; k++)
						gs0[i].gs[k + 1] = pstate[k];
					gs0[i].gs[k + 1] = '\0';
					nonoop2( gs0[i].gs );

					for (k = j + 1; k < nLen; k++)
						gs0[i].gsLast[k - j - 1] = pstate[k];
					gs0[i].gsLast[k - j - 1] = '\0';
					setNiyou( gs0, i, ny1, i - 1, -1, 0, 1, 0 );//前提类型,无,无,未使用,是条件式,不是文字
					break;
				}

				else if (pstate[j] == '=')//标注双条件p=q
				{
					//先保存双条件
					gs0[i].nLitter = strlen( pstate );
					for (k = 0; k < strlen( pstate ); k++) { gs0[i].gs[k] = pstate[k]; }//双条件全部进gs
					gs0[i].gs[k] = '\0';
					gs0[i].gsLast[0] = '\0';
					setNiyou( gs0, i, ny0, -1, -1, 0, 0, 0 );//前提类型,无,无,未使用,是条件式,不是文字
															 //p-q即!p+q
					i++;
					gs0[i].nLitter = strlen( pstate );
					gs0[i].gs[0] = '!';
					for (k = 0; k < j; k++) { gs0[i].gs[k + 1] = pstate[k]; }//p进gs
					gs0[i].gs[k + 1] = '\0';
					for (k = j + 1; k < nLen; k++) { gs0[i].gsLast[k - j - 1] = pstate[k]; }//q进gsLast
					gs0[i].gsLast[k - j - 1] = '\0';
					setNiyou( gs0, i, ny2, i - 1, -1, 0, 1, 0 );//前提类型,无,无,未使用,是条件式,不是文字
					nonoop2( gs0[i].gs );//去掉可能存在的!!?
										 //q-p=p+!q
					i++;
					gs0[i].nLitter = gs0[i - 1].nLitter;
					for (k = 0; k < j; k++) { gs0[i].gs[k] = pstate[k]; }//条件前件p进gs
					gs0[i].gs[k] = '\0';
					gs0[i].gsLast[0] = '!';
					for (k = j + 1; k < nLen; k++) { gs0[i].gsLast[k - j - 1 + 1] = pstate[k]; }//条件后件!q进gsLast
					gs0[i].gsLast[k - j - 1 + 1] = '\0';
					setNiyou( gs0, i, ny2, i - 2, -1, 0, 1, 0 );//前提类型,无,无,未使用,是条件式,不是文字
					nonoop2( gs0[i].gsLast );//去掉可能存在的!!?
					break;

				}

				else if (pstate[j] == '+')//标注析取式p+q,也要分解到gs与gsLast中
				{
					gs0[i].nLitter = strlen( pstate );
					for (k = 0; k < j; k++)
						gs0[i].gs[k] = pstate[k];    //前件进gs
					gs0[i].gs[k] = '\0';
					for (k = j + 1; k < nLen; k++)
						gs0[i].gsLast[k - j - 1] = pstate[k];    //条件全部进gs
					gs0[i].gsLast[k - j - 1] = '\0';
					setNiyou( gs0, i, ny0, -1, -1, 0, 1, 0 );//前提类型,无,无,未使用,是条件式,不是文字
					break;
				}
			}
			if (j >= nLen)//不是条件式,也不是文字,则是普通的条件
			{
				gs0[i].nLitter = strlen( pstate );
				for (k = 0; k < nLen; k++)
					gs0[i].gs[k] = pstate[k];    //公式全进gs
				gs0[i].gs[k] = '\0';
				gs0[i].gsLast[0] = '\0'; //gsLast为空串
				setNiyou( gs0, i, ny0, -1, -1, 0, 0, 0 );//前提类型,无,无,未使用,不是条件式,不是文字
			}
		}
		i++;//当前公式处理完以后,指针i的值增1
	}
	nLen = i;//按字符串的长度排序
	for (i = 0; i < nLen - 1; i++)
	{
		k = i;
		//for (j = i + 1; j < nLen - 1; j++)
		/* 修改点2:修改循环条件使得最后的元素可排序 */
		for (j = i + 1; j < nLen; j++)
			if (gs0[k].nLitter > gs0[j].nLitter)
				k = j;
		if (k > i)
		{
			/* 修改点3:使用自定义的swaptmd排序 */
			swaptmd(gs0[i],gs0[k]);
//			tmdp = gs0[i];
//			gs0[i] = gs0[k];
//			gs0[k] = tmdp;
		}
	}
	return nLen;
}

int main()
{
	struct tmd gs0[100];//推理前提条件
	char result0[128]; //结论
	struct tmd tmdrec[1024];//最多1000步

	char stmdp[128];
	char lastNiYou[128] = " ";//上一个推理式的理由
	char *ny01 = "消解";
	int i = 0, j = 0, k = 0;
	int np = 1, np0 = 0, isOk = 0;
	int i0 = 0, nPosLitter = 0, nPosCond = 0;//文字起始的位置,首个文字的位置,消解式的位置
	np0 = inputPrimary( gs0 );
	//输入结论
	printf( "输入要推理的结论,结论只能是文字,\n若是条件式,析取式请先手工转换为条件,将前件作为附加前提:" );
	gets( result0 );
	fflush( stdin );
	for (i = 0; i < np0; i++)
	{
		tmdrec[i] = gs0[i];//所有原始公式转抄到tmdrec中
	}
	np = i;//推理队列的尾部指针
	nPosLitter = 0;//文字的位置号
	nPosCond = 0;//条件的位置号
	isOk = 0;
	i0 = -1;
	while (1)
	{
		i = i0 + 1;//寻找下一个文字,i是起始位置,np是命令串的长度
		while ((i < np) && (tmdrec[i].isLitter != 1))
			i++;
		if (i >= np)
			break;//找不到文字我就没法推理了
		i0 = i;//记录从源头查询的首个文字的位置号,下次从此号往后寻找
		nPosLitter = i;//记录文字的位置
		strcpy( stmdp, tmdrec[i].gs );//保存当前文字的内容
		np0 = np - 1;
		while (np > np0) //从当前文字的下一个位置起寻找析取式,则一路往下走
		{
			np0 = np;
			for (i = 0; i < np; i++)//找到一个没有用过的戏曲式
				if ((tmdrec[i].isCond == 1) && (tmdrec[i].nUsed == 0))
					break;
			if (i == np)
				break;//没有找到则结束推理,所有条件式都用到了
			while (i < np)//若找到了这样的条件式
			{
				if ((tmdrec[i].isCond == 1))//若是条件式
				{
					//与上条命令的来源不同,或者但是同为前提条件也是可以的,即首个字符不是(
					if (((strcmp( lastNiYou, tmdrec[i].niyou ) != 0) || ((strcmp( lastNiYou, tmdrec[i].niyou ) == 0) && tmdrec[i].niyou[0] != '(')))
					{

						if ((tmdrec[i].gs[0] == '!') && (stmdp[0] != '!') && (strlen( tmdrec[i].gs ) - strlen( stmdp ) == 1))    // !p+q p cuo
						{
							//如果析取式的前件与stmdp即可消解,则将后件保存的stmdp中
							j = 0;
							while (j < strlen( stmdp ))//依次比较每个字符
							{
								if (tmdrec[i].gs[j + 1] != stmdp[j])
									break;//有一个不相等则结束比较
								j++;
							}

							if (j >= strlen( stmdp ))  //如果比到最后仍然相等,则这二个可消解
							{
								strcpy( lastNiYou, tmdrec[i].niyou );
								tmdrec[nPosLitter].nUsed++;  //这个文字用过一次了
								tmdrec[i].nUsed++;  //这个析取式用过一次了

								strcpy( stmdp, tmdrec[i].gsLast );  //将次消解结果保存到推导序列中
								strcpy( tmdrec[np].gs, stmdp );  //将当前推出来的结果保存起来
								tmdrec[np].gsLast[0] = '\0';  //后件清空,保存当前条件
								setNiyou( tmdrec, np, ny01, nPosLitter, i, 0, 0, 1 );  //前提类型,有,无,未使用,不是条件
								nPosLitter = np;  //记录当前文字的序号
								np++;
								if (strcmp( result0, stmdp ) == 0)
								{
									isOk = 1;    //推出结论同条原是调节的下一轮
									break;
								}
							}
						}
						else if ((tmdrec[i].gsLast[0] == '!') && (stmdp[0] != '!') && (strlen( tmdrec[i].gsLast ) - strlen( stmdp ) == 1))		//a+!b  b dui
						{
							//如果析取式的后件与stmdp即可消解,则将前件保存到stmdp中
							j = 0;
							while (j < strlen( stmdp ))  //依次比较每一个字符
							{
								if (tmdrec[i].gsLast[j + 1] != stmdp[j])
									break;    //有一个不相等则结束比较
								j++;
							}
							if (j >= strlen( stmdp ))  //如果比到最后仍然相等,则这两个可消解
							{
								strcpy( lastNiYou, tmdrec[i].niyou );
								tmdrec[nPosLitter].nUsed++;  //这个文字用过一次了
								tmdrec[i].nUsed++;  //这个析取式用过一次了

								strcpy( stmdp, tmdrec[i].gs );  //将次消解结果保存到推导序列中
								strcpy( tmdrec[np].gs, stmdp );  //将当前推出来的结果保存起来
								tmdrec[np].gsLast[0] = '\0';  //后件清空,保存当前条件
								setNiyou( tmdrec, np, ny01, nPosLitter, i, 0, 0, 1 );  //前提类型,有,无,未使用,不是条件
								nPosLitter = np;  //记录当前文字的序号
								np++;
								if (strcmp( result0, stmdp ) == 0)
								{
									isOk = 1;    //推出结论同条原是调节的下一轮
									break;
								}
							}
						}
						else if ((tmdrec[i].gs[0] != '!') && (stmdp[0] == '!') && (strlen( tmdrec[i].gs ) - strlen( stmdp ) == -1))		//	p+q !p
						{
							//如果析取式的后件与stmdp即可消解,则将前件保存到stmdp中
							j = 0;
							while (j < strlen( tmdrec[i].gs ))  //依次比较每一个字符
							{
								if (stmdp[j + 1] != tmdrec[i].gs[j])
									break;    //有一个不相等则结束比较
								j++;
							}
							if (j >= strlen( tmdrec[i].gs ))
							{
								strcpy( lastNiYou, tmdrec[i].niyou );
								tmdrec[nPosLitter].nUsed++;  //这个文字用过一次了
								tmdrec[i].nUsed++;  //这个析取式用过一次了

								strcpy( stmdp, tmdrec[i].gsLast );  //将次消解结果保存到推导序列中
								strcpy( tmdrec[np].gs, stmdp );  //将当前推出来的结果保存起来
								tmdrec[np].gsLast[0] = '\0';  //后件清空,保存当前条件
								setNiyou( tmdrec, np, ny01, nPosLitter, i, 0, 0, 1 );  //前提类型,有,无,未使用,不是条件
								nPosLitter = np;  //记录当前文字的序号
								np++;
								if (strcmp( result0, stmdp ) == 0)
								{
									isOk = 1;    //推出结论同条原是调节的下一轮
									break;
								}
							}

						}
						else if ((tmdrec[i].gsLast[0] != '!') && (stmdp[0] == '!') && (strlen( tmdrec[i].gsLast ) - strlen( stmdp ) == -1))		//p+q !q
						{
							//如果析取式的后件与stmdp即可消解,则将前件保存到stmdp中
							j = 0;
							while (j < strlen( tmdrec[i].gsLast ))//依次比较每一个字符
							{
								if (stmdp[j + 1] != tmdrec[i].gsLast[j])
									break;    //有一个不相等则结束比较
								j++;
							}
							if (j >= strlen( tmdrec[i].gsLast ))//如果比到最后仍然相等,则这两个可消解
							{
								strcpy( lastNiYou, tmdrec[i].niyou );
								tmdrec[nPosLitter].nUsed++;	//这个文字用过一次了
								tmdrec[i].nUsed++;			//这个条件用过一次了

								strcpy( stmdp, tmdrec[i].gs );	    //将此中间结果保存到推导序列中
								strcpy( tmdrec[np].gs, stmdp );		//将当前推出来的结果保存起来
								tmdrec[np].gsLast[0] = '\0';		//后件清空,保存当前条件
								setNiyou( tmdrec, np, ny01, nPosLitter, i, 0, 0, 1 );//前提类型,有,无,未使用,不是条件式
								nPosLitter = np;		            //记录当前文字的序号
								np++;
								if (strcmp( result0, stmdp ) == 0)
								{
									isOk = 1;    //推出结论同原始条件的下一轮
									break;
								}
							}
						}
					}
				}
				i++;//判断下一个表达式是否为条件,是否为可推理的条件式
			}
		}
		if (isOk == 1)
			break;    //我推出来了,不要再找下一个文字了
	}
	if (isOk == 1)
		printf( "我推出来了,推理过程如下:\n" );
	else
		printf( "我推不出来,推理过程如下:\n" );
	printYsh( tmdrec, np );
}

实验五 

/*
 * 实验五
 * 计算两个集合的若干运算
 * by ljkjk
 */

#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int max0 = 1e8;
/* 修改点1:改进print函数,优化了代码质量 */
int print(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]);
    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");
    return nlen;
}

int input(char a[])
{
    char nlen=0,i=0,j=0,k=0;
    char stmp[1024];
    printf("集合元素只能是A-Z,a-z,0-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'))
            /* 修改点2:使用strchr函数代替循环搜索,优化了运行速度 */
            if(strchr(a,stmp[i])==NULL)
            {
                a[j]=stmp[i];
                j++;
            }
    /* 修改点3:使用sort函数将集合排序,方便了使用 */
    sort(a,a+j);
    a[j]='\0';
    return j;
}

int setjiao(char a[],char b[],char c[])
{
    int i=0,j=0,k=0,nlen1=0,nlen2=0;
    nlen1=strlen(a);
    nlen2=strlen(b);
    for(i=0;i<nlen1;++i)
        if(strchr(b,a[i])!=NULL)
        {
            c[k]=a[i];
            ++k;
        }
    sort(c,c+k);
    c[k]='\0';
    return k;
}

int setbin(char a[],char b[],char c[])
{
    int i=0,j=0,k=0,nlen1=0,nlen2=0;
    nlen1=strlen(a);
    nlen2=strlen(b);
    /* 修改点4:使用strcpy函数复制数组 */
    strcpy(c,a);
    k=nlen1;
    for(i=0;i<nlen2;++i)
        if(strchr(c,b[i])==NULL)
        {
            c[k]=b[i];
            ++k;
        }
    sort(c,c+k);
    c[k]='\0';
    return k;
}

int setsub(char a[],char b[],char c[])
{
    int i=0,j=0,k=0,nlen1=0,nlen2=0;
    nlen1=strlen(a);
    nlen2=strlen(b);
    for(i=0;i<nlen1;++i)
        if(strchr(b,a[i])==NULL)
        {
            c[k]=a[i];
            ++k;
        }
    sort(c,c+k);
    c[k]='\0';
    return k;
}

int setdc(char a[],char b[],char c[])
{
    int i=0,j=0,k=0,nlen1=0,nlen2=0;
    nlen1=strlen(a);
    nlen2=strlen(b);
    for(i=0;i<nlen1;++i)
    {
        for(j=0;j<nlen2;++j)
            if(a[i]==b[j])
                break;
        if(j>=nlen1)
        {
            c[k]=a[i];
            ++k;
        }
    }
    for(i=0;i<nlen2;++i)
    {
        for(j=0;j<nlen1;++j)
            if(b[i]==a[j])
                break;
        if(j>=nlen1)
        {
            c[k]=b[i];
            ++k;
        }
    }
    c[k]='\0';
    return k;
}

int setdicarl(char a[],char b[],char c[][3])
{
    int i=0,j=0,k=0,nlen1=0,nlen2=0;
    nlen1=strlen(a);
    nlen2=strlen(b);
    for(i=0;i<nlen1;++i)
    {
        for(j=0;j<nlen2;++j)
        {
            c[k][0]=a[i];
            c[k][1]=b[j];
            c[k][2]='\0';
            ++k;
        }
    }
    return k;
}

int main()
{
	char a[1024],b[1024],c[1024],dcar[1024][3];
	int nlen=0;
	int i=0;
	printf("输入集合a:");
	input(a);
	printf("输入集合b:");
	input(b);
	printf("A:");
	print(a);
	printf("B:");
	print(b);
	printf("集合的交:");
	setjiao(a,b,c);
	print(c);
	printf("集合的并:");
	setbin(a,b,c);
	print(c);
	printf("集合的差:");
	setsub(a,b,c);
	print(c);
	printf("集合的对称差:");
	setdc(a,b,c);
	print(c);
	nlen=setdicarl(a,b,dcar);
	if(nlen>0)
        printf("<%c,%c>",dcar[0][0],dcar[0][1]);
    for(i=1;i<nlen;++i)
        printf(",<%c,%c>",dcar[i][0],dcar[i][1]);
	return 0;
}

实验六

 #include <iostream>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <algorithm>
#define INF 0x3f3f3f3f
#define N 100
using namespace std;
struct stree{
    int pointa,pointb,weight;
};

/* 修改点1:合并两个矩阵的输入 */
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 print(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);
}

int iseuler(int d[],int n)
{
    int n0dd=0,i=0;
    int i0dd1=0,j0dd2=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)
        {
            n0dd++;
            if(i0dd1==0) i0dd1=i;
            else j0dd2=i;
        }
    if(n0dd==0)
        printf("\n存在Euler回路,即为Euler图\n");
    else if(n0dd==1)
        printf("\n存在Euler路,起点为%d 终点为%d\n",i0dd1,j0dd2);
    else
        printf("\n不存在Euler路与回路\n");
}

void ishamilton(int d[],int n)
{
    int ishp=1,ishg=1;
    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)
        printf("存在Hamilton路\n");
    else
        printf("不存在Hamilton路\n");
}

void caldegreeb(int b[][N],int n,int m,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<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)
            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)
{
    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];
        }
    print(a0,n,n,strcat(msg,"长度为1的路情况即直接相连的情况"));
    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,"的路情况");
        print(t2,n,n,msg);
    }
    print(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);
    /* 修改点2:sort排序 */
    sort(d,d+n);
    sort(subindex,subindex+n);
//    for(i=0;i<n-1;++i)
//        for(j=0;j<n-1-i;++j)
//        {
//            if(d[j]<d[j+1])
//            {
//                swap(d[j],d[j+1]);
//                swap(subindex[j],subindex[j+1]);
//            }
//        }
    printf("排序后的结点度数:\n");
    for(i=0;i<n;++i)
        printf("%4d[%1d]",d[i],subindex[i]);
    itmp=0;
    for(i=0;i<n;++i)
    {
        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;
        thiscolor[nthiscolor]=k0;
        printf("\nk0=%d j=%d nthiscolor=%d itmp=%d\n",k0,j,nthiscolor,itmp);

        nthiscolor++;
        j++;

        while(1)
        {
            while(d[j]==-1&&j<n)
                j++;
            if(j==n)
                break;
            k=subindex[j];
            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,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(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(stree t[],int nt)
{
    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)
                /* 修改点3:中间元交换值改为swap */
                swap(t[j],t[j+1]);
}

int kruskal(stree t0[],int nt0,int n,stree t[])
{
    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)
        {
            b[t[j].pointa][j]=1;
            b[t[j].pointb][j]=1;
        }
        b[t[i].pointa][j]=1;
        b[t[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");
        }

        for(k=0;k<=nt;++k)
        {
            for(j=k;j<n;++j)
                if(b[j][k]!=0)
                {
                    if(j>k)
                        for(m=0;m<=nt;++m)
                            swap(b[j][m],b[k][m]);
                    break;
                }
            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");
        }
        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(stree t0[],int nt0,int n,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;

    u[nt]=0;
    printf("u[%d]=%d\n",nt,u[nt]);
    nt++;
    while(nt<n)
    {
        mdis=999999;
        idis=-1;
        for(i=0;i<nt;++i)
        {
            k=u[i];
            for(j=0;j<nt0;++j)
            {
                if(t0[j].pointa==k)
                    if(mdis>t0[j].weight)
                    {
                        mdis=t0[j].weight;
                        idis=t0[j].pointb;
                        jtree=j;
                    }
                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;
}

int main()
{
	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,nt0=0,nt=0;
    /* 修改点4:优化交互 */
	bool flag1=false;
	while(1)
    {
        printf("\n===========================\n");
        if(!flag1)
            printf("1.输入邻接矩阵及关联矩阵\n");
        if(flag1)
        {
            printf("2.邻接矩阵求每点度数及短短图形性质\n3.关联矩阵求每点度数及判断图形性质\n4.用warshall算法判断是否连通\n");
            printf("5.计算A,A^2,A^3,...\n6.用Powell染色算法对结点染色\n");
            printf("7.用kruskal求最小生成树\n8.用prim求最小生成树\n");
        }

        printf("\n===========================\n");
        printf("您的选择(输入0结束):\n");
        
        /* 修改点5:判断输入是否合法 */
        while(scanf("%d",&nchoice))
            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);
                    print(A,n,n,"邻接矩阵");
                    flag1=true;
                    break;
                }
//            case 11:
//                {
//                    inputedge(B,n,&m);
//                    print(B,n,m,"关联矩阵");
//                    flag11=true;
//                    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;
                }
        }
    }

	return 0;
}

实验七

/*
 * 实验七
 * by ljkjk
 */

/*
 * 共 6 个修改点
 * 修改点1:万能头文件
 * 修改点2:合并if和for语句,使代码简洁易懂
 * 修改点3:用strchr函数来代替搜索过程
 * 修改点4:使用memset函数替代双重循环初始化数组
 * 修改点5:利用布尔函数优化交互
 * 修改点6:利用while判断输入是否合法
 */

/* 修改点1:万能头文件 */
#include <bits/stdc++.h>
#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中出现过
			/* 修改点3:用strchr函数来代替搜索过程 */
			if(strchr(a,stmp[i])==NULL)
            {
                a[j]=stmp[i];
                j++;
            }
	}
	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为止
	{
		//将[email protected]的复合函数暂存到T
		printRelaYsh(T, nT);
		printRelaYsh(R, nR);
		nT2 = relaCompose(T, R, T2, nT, nR);
		printRelaYsh(T2, nT2);
		printf("\n");
		//将复合以后的添加到R中,得到[email protected],剔除重复的元素
		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为止
	{
		//将[email protected]的复合暂存到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;
	/* 修改点5:利用布尔函数优化交互 */
	bool flag=false;
	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);
		/* 修改点6:利用while判断输入是否合法 */
		while(scanf("%d",&nChoice))
            if((nChoice>=0&&nChoice<=8)) break;
            else printf("请重新输入\n");
        
		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("[email protected]:");
				printRelaYsh(T, nT);
				break;
			}
			case 9:
			{
				nT = relaCompose(R2, R1, T, nLen2, nLen1);
				printf("[email protected]:");
				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>
			*/
		}
	}
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/HNUCSEE_LJK/article/details/87207627

智能推荐

云计算时代,企业IT资产安全运维利器——行云管家堡垒机_suancaiyu66的博客-程序员秘密

为了保障网络和数据不受来自外部和内部用户的入侵和破坏,企业通常通过部署堡垒机来管理企业内部IT资产。但随着云计算逐渐发展成为企业IT架构的基础设施,传统堡垒机很难适应云的变化,已经无法对企业IT资产进行更好更全面的系统运维和安全审计管控。不仅如此,由于传统堡垒机过于关注IT管理者层面的安全管理、权限控制,导致运维工程师在使用时不够简捷方便,大大降低了IT运维效率。由此,在云计算的浪潮下,行...

linux下usb驱动接口中端点介绍_枫_在路上的博客-程序员秘密

端点 USB 通讯的最基本形式是通过一个称为端点的东西。一个USB端点只能向一个方向传输数据(从主机到设备(称为输出端点)或者从设备到主机(称为输入端点))。端点可被看作一个单向的管道。 一个 USB 端点有 4 种不同类型, 分别具有不同的数据传送方式: 控制CONTROL 控制端点被用来控制对 USB 设备的不同部分访问. 通常用作配置设备、获取设备信息、发送命令到设备或获取

Java核心基础第1篇-走进Java世界_普通网友的博客-程序员秘密

一、Java简介1.1 Java概述Java从一开始就以友好的语法、面向对象、内存管理和最棒的跨平台可移植性来吸引程序员。写一次就可以在所有地方执行( write-once/run-anywhere)的特性简直太厉害了。image-202105061122543701.2 Java名称的由来Java是印度尼西亚爪哇岛的英文名称,因盛产咖啡而闻名。Java语言中的许多库类名称,...

apex在windows上的安装_Git-Csdn的博客-程序员秘密

第一天,用官网最下面那个命令不行,https://github.com/NVIDIA/apex/最后直接用这个命令装上了:python setup.py install删除的时候除了要把apex-master删除,C:\Users\Administrator\Anaconda3\envs\slimyolo\Lib\site-packages路径下apex-0.1-py3.6-w...

Overleaf v2 评测_stay_foolish12的博客-程序员秘密

Overleaf v2 评测去年,两个著名的Latex在线编辑器Overleaf和Sharelatex合并了,强强联手,让我们对他们合并之后的新产品充满了期待。最近,他们的新产品发布了!这就是Overleaf v2。现在,你可以访问v2.overleaf.com试用可能是迄今最强大的Latex在线编辑器。如果你以前注册过Overleaf或者Sharelatex,你不需要注册新的...

TEE(Trusted Execution Environment)简介_butterfly的博客-程序员秘密

TEE(Trusted Execution Environment)简介TEE(Trusted Execution Environment),可信执行环境,该环境可以保证不被常规操作系统干扰的计算,因此称为”可信”。这是通过创建一个可以在TrustZone的”安全世界”中独立运行的小型操作系统实现的,该操作系统以系统调用(由TrustZone内核直接处理)的方式直接提供少数的服务。另外,TrustZone内核可以安全加载并执行小程序”Trustlets”,以便在扩展模型中添加”可信”功能。T..

随便推点

前端架构模式:支持前端的后端_普通网友的博客-程序员秘密

英文 |https://medium.com/frontend-at-scale/frontend-architectural-patterns-backend-for-fronten...

Windows上远程访问MySQL数据库_琅琊Team的博客-程序员秘密_mysql windows 远程访问

最近有个项目,多台机器需要共享条码信息,又不想额外写一个程序去进行调度,就想到用远程访问数据库的方式来实现多台机器之间的条码共享。 数据库安装完成后,默认的localhost登录。远程电脑如果要访问肯定是需要添加IP地址的。(代码为Python3) 接下来讲重点,就是主机数据库设置(上面代码可以看出如果把host放到config里面,可以保证每台机的代码都一样) 1.Win+R,打开输入cmd,打开命令行 2.将工作目录切换到My...

HDU2040-亲和数_joeycom2的博客-程序员秘密

题目出自杭电 首先解释何谓亲和数 亲和数是对于两个数来说的。如果两个数a和b,a的所有除本身以外的因数之和等于b,b的所有除本身以外的因数之和等于a,则称a,b是一对亲和数。 思路:对于输入的数A,算出它的所有真约数的和C,若C=B,则A和B是亲和数。反之不是。 上代码#include <stdio.h>int n,m;int sum(int n){ int sum =1,

TIFF图像文件格式详解_smilestone322的博客-程序员秘密

该文转自:http://blog.csdn.net/dcraw/archive/2011/05/24/6443537.aspx 1 什么是TIFF? TIFF是Tagged Image File Format的缩写。在现在的标准中,只有TIFF存在, 其他的提法已经舍弃不用了。做为一种标记语言,TIFF与其他文件格式最大的不同在于除了图像数据,它还可以记录很多图像的其他信息。它记录图像

Linux usb子系统_杨Jun的博客-程序员秘密

一、USB协议基础知识  前序:USB概念概述  USB1.0版本速度1.5Mbps(低速USB) USB1.1版本速度12Mbps(全速USB)  USB2.0版本速度480Mbps(高速USB)。  USB 分为主从两大体系,一般而言, PC 中的 USB 系统就是作主,而一般的 USB 鼠标, U 盘则是典型的 USB 从系统。  USB主控制器这一块,我们至少要开发出 US

微信浏览器唤醒App_紫轩阁的博客-程序员秘密_微信浏览器打开app

实现效果如下图所示,顶部会有一个广告图,点击这个广告图,如果手机上已经安装了App,则直接打开,如果没有安装,则开始下载,如果在微信公众号中,则跳转应用宝第三方平台跳转。html&lt;span @click="openAppClick" class="see-btn"&gt;打开APP&lt;/span&gt;jsopenclient(){ let ua = navigator.userAgent.toLowerCase(); //config 配置文件 JS 传递