最小生成树.cpp

最小生成树问题 若要在n个城市之间建设通信网络

#include "conio.h"

#include "stdio.h"

#include "stdlib.h"

#define Null 0

#define MAXQSIZE 100

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

struct SqStack{

char *base;

char *top;

int stacksize;

}SqStack;

struct Squeue{

char *base;

int *front;

int *rear;

}Q;

struct Squeue q[31];                         

char *rule[31];

struct SqStack InStack()

{/*建立一个空栈*/

struct SqStack S1;

S1.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));

if(!S1.base) exit(0);

S1.top=S1.base;

S1.stacksize=STACK_INIT_SIZE;

return(S1);

}

void Push(struct SqStack S1,char ch)

{/*元素进栈*/

if(S1.top-S1.base>=S1.stacksize)

{ S1.base=(char *)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char));

if(!S1.base) exit(0);

S1.top=S1.base+S1.stacksize;

S1.stacksize+=STACKINCREMENT;

}

*S1.top++=ch;

}

char Pop(struct SqStack S1)

{/*栈顶元素出栈*/

char ch;

if(S1.top==S1.base) exit(0);

ch=*--S1.top;

return(ch);

}

struct Squeue InitQueue()

{ /*建立一个空队列*/

struct Squeue Q1;

Q1.base=(char *)malloc(MAXQSIZE*sizeof(char));

if(!Q1.base) exit(0);

Q1.front=(int *)malloc(MAXQSIZE*sizeof(int));

*Q1.front=0;

Q1.rear=(int *)malloc(MAXQSIZE*sizeof(int));

*Q1.rear=0;

return(Q1);

}

void EnQueue(struct Squeue Q1,char e)

{/*元素入队列*/

if((*Q1.rear+1)>MAXQSIZE)

Q1.base=(char *)realloc(Q1.base,(*Q1.rear-*Q1.front+STACKINCREMENT)*sizeof(char));

Q1.base[*Q1.rear]=e;

(*Q1.rear)++;

}

void readrules()

{/* 读入魔王语言的翻译规则*/

int i;

char ch;

for(i=0;i<=31;i++) rule[i]=Null;

printf("\n说明：输入任意一个非魔王语言的字符则循环结束\n");

printf("\n请输入一个魔王语言的字符:");

ch=getchar();

while(ch<='Z'&&ch>='A')

{

printf("\n请输入这个字符对应的人的语言:");

rule[ch-'A']=(char *)malloc(MAXQSIZE*sizeof(char));

scanf("%s",rule[ch-'A']);

printf("\n请输入魔王语言的一个字符:");

scanf("%c",&ch);

ch=getchar();

}

}

void copy(struct Squeue Q1,struct Squeue Q2)

{ int k;

char ch;

k=*Q2.front;

while(k!=*Q2.rear)

{ ch=Q2.base[k];

EnQueue(Q1,ch);

k++;

}

}

void changrules( )

{/*将魔王的语言全部转换为人的语言*/

int i;

char *p;

for(i=0;i<=31;i++)

{ p=rule[i];

if(p)

{ q[i]=InitQueue();

while(*p!='\0')

{ if(*p<='z'&&*p>='a') EnQueue(q[i],*p);

else copy(q[i],q[*p-'A']);

p++;

}

}

}

}

char *translate(char *mm)

{/*对应于带括号的魔王语言的翻译方法*/

char ch,th;

struct SqStack S;

S=InStack();

ch=*mm;

mm++;

while(*mm!=')'){ Push(S,*mm);S.top++;mm++;}

while(!(S.top==S.base))

{ EnQueue(Q,ch);

th=Pop(S);S.top--;

EnQueue(Q,th);

}

EnQueue(Q,ch);

return(mm);

}

void main()

{

int i;

char *elem,*tt;

Q=InitQueue();

readrules();

changrules();

printf("\n请输入一句魔王的语言:");

tt=(char *)malloc(MAXQSIZE*sizeof(char));

scanf("%s",tt);

elem=tt;

while(*elem!='\0')

{ if(*elem<='z'&&*elem>='a') EnQueue(Q,*elem);

else if(*elem<='Z'&&*elem>='A') copy(Q,q[*elem-'A']);

else if(*elem=='(') {elem++;

elem=translate(elem);}

elem++;

}

for(i=*Q.front;i<*Q.rear;i++)

printf("%c",Q.base[i]);

printf("\n");

for(i=*Q.front;i<*Q.rear;i++){

switch(Q.base[i])

{

case 'e':printf("鹅");break;

case 't':printf("天");break;

case 's':printf("上");break;

case 'a':printf("一只");break;

case 'd':printf("地");break;

case 'z':printf("追");break;

case 'g':printf("赶");break;

case 'x':printf("下");break;

case 'n':printf("蛋");break;

case 'h':printf("恨");break;

default:printf("%c",Q.base[i]);break;

}

}

printf("\n");

}