程序.c

数据结构课程设计的题目

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include"Chang.h"

typedef struct
{
	char c[10];//字符串名
	int n;//所赋的值
}Data;

typedef struct qnode 
{
        Data data;
        struct qnode *leftchild;
        struct qnode *rightchild;
}BiTree;
typedef struct
{
	
	char a;
	char b[10];
}Lpha;
int i;
int N;
char str[100][8];//存放表达式中所有的变元
Lpha  stu[100];//字符串与首个字符的对应关系
int Result[100];//存放不同的真值情况对应的不同的值，
//---------------------用后缀表达式构造二叉树 
BiTree *Creat(char str[])
{
    BiTree *p;
	Data s;
    i--;
	memset(s.c,0,sizeof(s.c));
    if(i<0)return NULL;//-----递归出口
	if(str[i]=='|'||str[i]=='&'||str[i]=='!')
    s.c[0]=str[i];
	else 
	{
		strcpy(s.c,stu[N].b);
		N--;
	}//---------给的将建立的二叉树结点的数据域赋值
    p=(BiTree*)malloc(sizeof(BiTree));//
    p->data=s;
	if(str[i]=='|'||str[i]=='&')
    { 
      p->rightchild=Creat(str);
       p->leftchild=Creat(str);
      
    }
	else if(str[i]=='!')
	{
		p->rightchild=Creat(str);
	    p->leftchild=NULL;//--------设左孩子为空
	}
     else {
          p->rightchild=NULL;
           p->leftchild=NULL;
          }
          return p;
} 
//-----------------------------------------------------打印二叉树 
void Print(BiTree *root,int n)
{
    int i;
    if(root==NULL)return;
    Print(root->rightchild,n+1);
    for(i=0;i<n;i++)
		printf("   ");
    printf("---");
    printf("%s\n",root->data.c);
    Print(root->leftchild,n+1);
}
//--------------------建立字符串名与首个字符映射表
int Simple(char str[],Lpha stu[],int n)
{
	int i=0,j=0,t=0,k;
	for(t=0;t<n;t++)
	{
	
     if(str[t]=='!'||str[t]=='&'||str[t]=='|'||str[t]=='('||str[t]==')')
		{
			while(t<n&&(str[t]=='!'||str[t]=='&'||str[t]=='|'||str[t]=='('||str[t]==')'))
		           t++;
		           t--;
		}

	else if(str[t]!='!'&&str[t]!='&'&&str[t]!='|'&&str[t]!='('&&str[t]!=')')
	{
		while(t<n&&str[t]!='!'&&str[t]!='&'&&str[t]!='|'&&str[t]!='('&&str[t]!=')')
		{
			stu[i].b[j++]=str[t];
			t++;
		}
		t--;
		i++;
		j=0;
	   }

	}
	for(k=0;k<i;k++)
		stu[i].a=stu[i].b[0];
return i;
}
 //--------------------------简化中缀表达式
        
int Mid(char c[],char a[],int n)
{
	int i,j,k;
	i=0;k=0;j=0;
	for(i=0;i<n;i++)
		if(c[i]=='!'||c[i]=='&'||c[i]=='|'||c[i]=='('||c[i]==')')
			a[j++]=c[i];
		else {
			a[j++]=c[i]; 
		while(c[i]!='!'&&c[i]!='&'&&c[i]!='|'&&c[i]!='('&&c[i]!=')')
            i++;
			i--;
		}
		return j;
}
//------------------给每个结点赋值

void FuZhi(BiTree *p,int a[],int n1)
{
	int j;
	if(p==NULL)
		return;
   FuZhi(p->leftchild ,a,n1 );
   if(p->data.c[0]!='!'&&p->data.c[0]!='&'&&p->data.c[0]!='|')
   {
	   if(p->data.c[0]=='0')
		   p->data.n=0;
	   else if(p->data.c[0]>='1'&&p->data.c[0]<='9')
		   p->data.n=1;
		   else {
		   for(j=0;j<n1;j++)
			   if(strcmp(p->data.c,str[j])==0)break;
			   //printf("%d %d\n",j,a[j]);
			   p->data.n=a[j];
				  
			   
		   }
   }
   FuZhi(p->rightchild,a,n1);
}
//---------------------打印赋值后的树

void Print2(BiTree *root,int n)
{
    int i;
    if(root==NULL)return;
    Print2(root->rightchild,n+1);
    for(i=0;i<n;i++)
		printf("   ");
    printf("---");
	if(root->data.c[0]=='!'||root->data.c[0]=='|'||root->data.c[0]=='&')
    printf("%s\n",root->data.c);
	else printf("%d\n",root->data.n);
    Print2(root->leftchild,n+1);
}
//--------------------跟据赋值的二叉树计算相关真值
//---------------注：计算表达式是后序遍历
void Compute(BiTree *p)
{
	BiTree *r,*l;
	if(p==NULL)return;
	Compute(p->leftchild);
   Compute(p->rightchild);
	r=p->rightchild;
	l=p->leftchild;

	if(p->data.c[0]=='!')
	{
		if(r->data.n==1)
		  p->data.n=0;
	  else if(r->data.n==0)
		  p->data.n=1;
	}
	 else if(p->data.c[0]=='&')
	 {
		 if(l->data.n==0&&r->data.n==0)
			 p->data.n=0;
		 else if(l->data.n==0&&r->data.n==1)
			 p->data.n=0;
        else if(l->data.n==1&&r->data.n==0)
			 p->data.n=0;
      else if(l->data.n==1&&r->data.n==1)
			 p->data.n=1;
	 }
	  else if(p->data.c[0]=='|')
	 {
		  if(l->data.n==0&&r->data.n==0)
			 p->data.n=0;
		 else if(l->data.n==0&&r->data.n==1)
			 p->data.n=1;
        else if(l->data.n==1&&r->data.n==0)
			 p->data.n=1;
         else if(l->data.n==1&&r->data.n==1)
			 p->data.n=1;
	 }
    
}

			 


//-------------建立和显示真值表
void Creat2(BiTree *p,int n)

{
	int i,j,a[100],m,k;
	m=(int)(pow(2,n)+0.5);
	//printf("%d\n",m);
	for(i=0;i<m;i++)
	{
		j=n-1;k=i;
      while(j>=0)
	  {
		  a[j--]=k%2;
		  k=k/2;
	 }
     //for(k=0;k<n;k++)
		 //printf("%-5d",a[k]);
	  
	 FuZhi(p,a,n);
	 //Print2(p,0);
	 Compute(p);
	 Result[i]=p->data.n;
	 
	}
}
 //-----------------------打印真值表
void Print3(int n)
{
	int j,k,m,a[50],h,b;
	m=(int)(pow(2,n)+0.5);
	for(j=0;j<n;j++)
		printf("%-5s",str[j]);
	printf("Result\n");
	for(j=0;j<m;j++)
	{//---------对变量不同的赋值情况有M种
		k=n-1;h=j;
		 while(k>=0)
	  {
		  a[k--]=h%2;
		  h=h/2;
		  //------a数组存放相应变量所赋的值
	 }
		 for(b=0;b<n;b++)
			  printf("%-5d",a[b]);
		 printf("%d\n",Result[j]);
	}
}


int main()
 {//--------------------------字母和字符串的对应表
     char a[100],b[100],c[100],strr[6];
    
     int na,ns,j,n,nc,nb,k,m,f,h;//n代表元的个数
     BiTree *p;
	 printf("请输入表达式中变元的个数:\n");
	     while(scanf("%d",&n)!=EOF)//输入变元的个数
//--------------------------转化为简化的中缀
    {

     memset(a,sizeof(a),0);
     memset(b,sizeof(b),0);
	 printf("请输入一个逻辑表达式:\n");
	 scanf("%s",c);
	  memset(stu,0,sizeof(stu));
	 nc=strlen(c);
	 
	 ns=Simple(c, stu,nc);
	// for(i=0;i<ns;i++)
		// printf("%s\n",stu[i].b);
	
//----------------------------
	 na=Mid(c,a,nc);
	 a[na]='#';a[na+1]='\0';
	 printf("简化的中缀表达式为:\n");
	 printf("%s\n",a);
//--------------转化为后缀
	 printf("转化的后缀表达式为:\n");
	 nb=Chang(a,na+1,b);
//--------------用后缀建立二叉树并打印
	 i=nb;
	 N=ns-1;
      p=Creat(b);
      Print(p,0);
   
//--------------剃除重复的变元和常元，以建立变量到常量的映射
	  k=0;
	memset(str,0,sizeof(str));
	for(j=0;j<ns;j++)
	{
	//	printf("dfagaga\n");
    if(stu[j].b[0]>='0'&&stu[j].b[0]<='9')continue;
       for(m=0;m<k;m++)
	   if(strcmp(str[m],stu[j].b)==0)break;
		 if(m==k)strcpy(str[k++],stu[j].b);
	}
	//for(j=0;j<k;j++)
     // printf("%s\n",str[j]);
//-------------------建立并显示真值表
	Creat2(p,n);
	f=0;
	printf("输入一个变量对应的真值序列\n");
	for(j=1;j<=k;j++)
	{
		printf("%s:",str[j-1]);
		scanf("%d",&h);
		f+=h*(int)(pow(2,n-j)+0.5);
	}
	//printf("%d\n",f);
	printf("对应的真值是:");
	printf("%d\n",Result[f]);
   printf("打印真值表与否?\n");
   scanf("%s",strr);
   if(strcmp(strr,"Yes")==0)
	   Print3(n);

printf("请输入表达式中变元的个数:\n");
}
     return 0;
 }