魔王语言实验报告

数据结构课程设计报告

题 目：系部名称 ：专业名称 ：班 级 ：学

号 ：学生姓名 ：指导教师 ：时

间 ： 魔王语言

通信工程

1

一、 课程设计目的

（1）熟练掌握C语言和数据结构的相关操作。

（2）综合应用C语言的知识和数据结构的知识，编写程序，并且对以前所

学的知识进行复习。

( 3 ) 培养学生独立完成课程设计的能力。

二、课程设计内容

1.用带头结点的动态单链表来存储多项式；在此基础上完成多项式乘法运算要求以动态链表为存储结构、使用到查找和排序等操作；在创建多项式的过程中，可以按指数的任意顺序输入，并且可在同一多项式中输入指数相同的多项； 在进行乘法操作之前，输出参与操作的两个多项式。要求输出的多项式按指数降序排列，同指数的多项合并，项数的正负号显示合理。。 2.魔王语言

有一个魔王总是使用自己的一种非常精炼而抽象的语言讲话，没有人能听懂。但他的语言是可以逐步解释成人能懂的语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的： (1)α→β1β2 …… βm

(2)(θδ1δ2 …… δn)→ θδnθδn-1 …… θδ1 θ

在这两种形式中，从左到右均表示解释；从右到左均表示抽象。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。 ",读取文件，并统计

1. 读取文本文件 (rule.txt), 将具体规则的对应关系读入数组或链中

2. 读取文本文件 (mean.txt), 将小写字母及其对应的含义读入数组或链表中 ",处理规则形式（2）

按照规则形式(2)处理魔王所说的话。处理完毕后，对应的解释语句不再含有（）。 处理规则形式（1）

按照读入的具体规则，对上一步处理的结果进行

规则形式（1）的处理，得到魔王所说的话的人类语言结果。 ", 写结果文件

按照所读入的小写字母对应的文字含义，将翻译成的人类语言转换成文字语句，写入文件result.txt中。",读取文件，并统计

1. 读取文本文件 (rule.txt),将具体规则的对应关系读入数组或链表中

2. 读取文本文件 (mean.txt), 将小写字母及其对应的含义读入数组或链表中 ",处理规则形式（2）

按照规则形式(2)处理魔王所说的话。处理完毕后，对应的解释语句不再含有（）。 处理规则形式（1）

按照读入的具体规则，对上一步处理的结果进行规则形式（1）的处理，得到魔王所说的话的人类语言结果。 ", 写结果文件

按照所读入的小写字母对应的文字含义，将翻译成的人类语言转换成文字语句，写入文件result.txt中。

2

三、需求分析

对所开发系统功能、性能的描述，想要实现的目标。

利用队列存储左括号之前的英文字母，遇到左括号了把括号后面的字母在栈里面，在存储时将括号里的第一个字母镶嵌存在栈里面，处理完右括号左边的字母后让进栈的元素依次出栈存储在队列中，然后接着扫描括号后面的元素让所有元素都进队列。

从头开始扫描队列，将队列中的大写字母用rule.txt文件里相应的小写字母替换，挂在原来队列的后面，与到小写字母直接挂在队列的尾部，一次处理后再进行循环如上的操作，直到把所有的大写字母换成小写字母。

此时队列里存储的是一串小写字母，再进行扫描将小写字母和mean.txt文件里存储的对应汉字进行替换，依次替换然后输出，再将替换后的汉字存储在result.txt文件里面

四、概要设计

1．系统结构图（功能模块图）

对系统进行分析，给出系统结构图； 主函数 调用读取含义输出人的语言 调用菜单函调用读取规则 文件函数 数 文件函数 调用保存文件 若文件为空，调函数 若文件为空， 添加含义文件调添加规则文 函数 件函数 若选1调用添加若选2调用添加若选0调用翻译 规则文件函数 含义文件函数 函数

3

2．功能模块说明

（1）定义结构体：定义链栈的结构体LinkStackNode；定义链表存储翻译结果的结构体RESULT；定义链队结构体LinkQueueNode和LinkQueue。分别对链栈和链对进行初始化、入栈（队）、出栈（队）操作。

（2）读取规则文件函数read_rule()：动态建立链表存放规则，将文件名为rule.txt的文件打开，用fscanf()函数将文件内容读入链表，将链表的头指针返回。

（3）读取含义文件函数read_mean()：动态建立链表存放规则，将文件名为mean.txt的文件打开，用fscanf()函数将文件内容读入链表，将链表的头指针返回。

（4）添加规则文件函数append_rule()：将存放规则文件内容的链表传递过来，用p2指针指向链表尾结点。循环按正确格式输入需添加的规则，动态建立结点存放输入的规则，将当前结点插入p2的下一个结点处，再让p2向后移动，推出循环添加结束。

（5）添加规则文件函数append_mean()：将存放含义文件内容的链表传递过来，用p2指针指向链表尾结点。循环按正确格式输入需添加的规则，动态建立结点存放输入的规则，将当前结点插入p2的下一个结点处，再让p2向后移动，推出循环添加结束。

（6）保存文件函数save_file()：将规则链表，含义链表，存放结果的链表分别传递过来，将各自所对应的文件打开，用fprintf()函数将添加的内容保存到文件里。

（7）菜单函数menu()：输出刚进入系统后要选择的菜单，分别是添加规则（一）、添加含义、翻译魔王语言，用户选择后调用相应的函数。

（8）去括号函数translate1()：首先要求用户输入需翻译的魔王语言，然后判断括号是否输入正确，若不正确，要求用户重新输入；若正确，开始进行翻译。初始化队q1,q2,q3,初始化栈s，将第一个左括号之前的字符全部入队q1，从下一个字符开始到第一个右括号结束，将此段字符入栈。然后出栈入队q2，碰到左括号时结束，出队q2入队q3，同时处理规则形式（二），栈不为空时将队3的字符入栈继续处理括号直到栈为空，处理后的字符在队3里面存放，最后将队3接到队1后面，去括号完成。

（9）大写字母翻译小写字母函数translate2()：将规则链表rear和存放去括号后的魔王语言链n表传递过来，遍历n，当碰到大写字母时开始处理，在rear中查找相应的字母，找到后将对应的小写字母插入链表n中。继续遍历链表n，直到所有大写字母处理完。

（10）小写字母翻译成汉语函数translate3()：将含义链表mean和存放去大写字母后的魔王语言链n表传递过来，遍历n，逐项在rear中查找相应的n中的字母，找到后将对应的汉语存放到结果链表（动态建立RESULT型的链表）中，若未找到，将此小写字母本身作为翻译后的结果存放在结果链表中。继续遍历链表n，直到所有小写字母遍历完。

（11）翻译函数tanslate()：将规则链表rule和含义链表mean传递过来，首先调用tanslate1()函数进行去括号处理，在调用tanslate2()函数进行大写字母处理，将处理后的魔王语言输出，最后调用tanslate3()函数进行翻译处理，将结果存放到链表中，将链表返回至主函数。

五、详细设计及运行结果

流程图， 函数之间相互调用的图示 ，程序设计及编码, 运行结果。

4

（1）如括号处理的流程图：

输入魔王语言ch

判断括号是否匹配

初始化队q1,q2,q3,初 始化栈s，i←0

Y ch[i]='\\0'与

ch[i]='('

N

EnterQueue(q1,ch[i++])

N

ch[i]='('

Y

与 Y Ch[++i]='\\0' ch[i]=')'

N

push(s,ch[i])

N ch[i]=')'

Y

Y S->next=NULL与

(Pop(s,&x),x)='('

5 开始

typedef struct mean /*定义链表存储字母含义*/ { char data1; char data2[20]; struct mean *next; }MEAN;

void InitStack(LinkStack top) /*链栈的初始化*/ { top->next=NULL; }

int Push(LinkStack top,char x) /*进栈操作*/ { LinkStack temp; temp=(LinkStack)malloc(sizeof(LinkStackNode)); if(temp==NULL) return FALSE;/*申请空间失败*/ temp->data1=x; temp->next=top->next; top->next=temp;/*修改当前栈顶指针*/ return TRUE; }

int Pop(LinkStack top,char *x) /*出栈操作*/ { LinkStack temp; temp=top->next; if(temp==NULL) return FALSE;/*栈为空*/ top->next=temp->next; *x=temp->data1; free(temp);/*释放存储空间*/ return TRUE; }

int InitQueue(LinkQueue *q) /*链队列初始化*/ { q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode)); if(q->front!=NULL) { q->rear=q->front; q->front->next=NULL; return TRUE; } else return FALSE; }

int EnterQueue(LinkQueue *q,char x) /*入队操作*/ { LinkQueueNode *NewNode;

11

NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode)); if(NewNode!=NULL) { NewNode->data1=x; NewNode->next=NULL; q->rear->next=NewNode; q->rear=NewNode; return TRUE; } else return FALSE; }

int DeleteQueue(LinkQueue *q,char *x) /*出队操作*/ { LinkQueueNode *p; if(q->front==q->rear) return FALSE; p=q->front->next; q->front->next=p->next; if(q->rear==p) /*如果队中只有一个元素p，则p出队后成为空队*/ q->rear=q->front; *x=p->data1; free(p); return TRUE; }

RULE *read_rule() /*读取规则文件*/ { FILE *fp; RULE *head,*p1,*p2; head=p2=(RULE *)malloc(sizeof(RULE)); fp=fopen(\ if(fp==NULL) { printf(\ 规则文件不存在，请建立\\n\ head->next=NULL; return head; }

while(1) { p1=(RULE *)malloc(sizeof(RULE)); if(fscanf(fp,\ { p2->next=p1; p2=p1; } else

12

{ p2->next=NULL; free(p1); return head; } } fclose(fp); }

MEAN *read_mean() { FILE *fp; MEAN *head,*p1,*p2; head=p2=(MEAN *)malloc(sizeof(MEAN)); fp=fopen(\ if(fp==NULL) { printf(\ 含义文件不存在，请建立\\n\ head->next=NULL; return head; } p1=(MEAN *)malloc(sizeof(MEAN)); while(1) { p1=(MEAN *)malloc(sizeof(MEAN)); if(fscanf(fp,\ { p2->next=p1; p2=p1; } else { p2->next=NULL; free(p1); return head; } } fclose(fp); }

RULE *append_rule(RULE *head) { RULE *p1,*p2; char x,a[8]; int n; p2=head;

13

/*读取含义文件*/ /*添加规则*/ while(p2->next!=NULL) p2=p2->next; while(n) { printf(\请已α->β1β2β3β4...形式输入规则\ p1=(RULE *)malloc(sizeof(RULE)); flushall(); scanf(\ p1->data1=x; strcpy(p1->data2,a); p1->next=NULL; printf(\输入的规则是%c->%s\ p2->next=p1; p2=p1; printf(\继续输入规则吗？\\n1-继续 0-不继续\\n请选择:[ ]\\b\\b\ scanf(\ flushall(); } return head; }

MEAN *append_mean(MEAN *head) /*添加含义*/ { MEAN *p1,*p2; int n; p2=head; while(p2->next!=NULL) p2=p2->next; while(n) { printf(\请输入（α->β）\ p1=(MEAN *)malloc(sizeof(MEAN)); flushall(); scanf(\ p1->next=NULL; printf(\输入的含义是 :%c->%s\ p2->next=p1; p2=p1; printf(\继续输入规则吗？\\n1-继续 0-不继续\\n请选择:[ ]\\b\\b\ scanf(\ flushall(); } return head; }

void save_file(RULE *p1,MEAN *p2,RESULT *p3) /*将规则、含义及翻译结果存入文件

14

*/ { FILE *fp; if((fp=fopen(\ {

printf(\读规则文件错误！\\n\ return; } while(p1) { if((fprintf(fp,\ { printf(\写规则文件错误！\\n\ break; } if(p1->next==NULL) break; else p1=p1->next; }

fclose(fp); if((fp=fopen(\ { printf(\读用户信息文件错误！\\n\ return; } while(p2) { if((fprintf(fp,\ { printf(\写含义文件错误！\\n\ break; } if(p2->next==NULL) break; else p2=p2->next; } fclose(fp); if((fp=fopen(\ { printf(\读翻译结果文件错误！\\n\ return; } while(p3) { if((fprintf(fp,\ {

15

case 2:append_mean(mean); break;/*添加含义*/ case 0:result=translate(mean,rule); break;/*开始翻译*/ } flushall(); }while(choice!=0); re=result->next; printf(\魔王说的话是: **\ while(re!=NULL) { printf(\ re=re->next; } printf(\ save_file(rule->next,mean->next,result->next);/*将规则、含义及翻译结果存入文件*/ }

21

本文来源：https://www.bwwdw.com/article/7xga.html