数据结构课程设计报告魔王语言实验报告.doc

西安郵電學院数据结构课程设计报告 题 目： 魔王语言院系名称： 计算机学院 专业名称： 软件工程 班 级： 学生姓名： 学号（8位）： 指导教师： 设计起止时间：一. 设计目的1、 熟悉链表、队列、栈、排序、查找、文件等内容的的使用。2、 将数据结构的内容结合到一起使用。3、 熟悉掌握数据结构的内容。4、了解递归与非递归的使用。二. 设计内容以栈和队列为数据结构，使用文件读写、查找等操作，完成对魔王语言的解释。三概要设计 开始1功能模块图； 主函数 结束将结果保存到文件中将魔王语言翻译为汉语意思将魔王的话转化成小写字母 将栈中的元素存入数组中读取文件mean.txt读取文件rule.txt 调用取括号函数 输入魔王说的话2 各个模块详细的功能描述。1. 入栈操作函数 int push(Stack *s,char x) 讲传递过来的字符入栈；2. 出栈操作char pop(Stack *s) 将当前栈顶的字符出栈，并将其返回；3. 入队操作函数int queue_in(Queue *p,char ch) 将传递过来的ch中的字符入队；4. 出队操作char queue_out(Queue *p) 将当前队头的字符出队，并将其返回；5. 去除魔王语言中括号模块void deletenode(Stack *s,Queue *r,char a,int i) 利用队栈的进栈出栈操作，入队出队操作，将魔王语言中的括号去除，使之成为一个字母的序列； 6 .文件读取函数void read_file() ，void word_file()通过文件函数，读取rule和mean文件，并将其输出到终端；7. 将栈中的元素存入数组中void store(char a,Stack *s) 将栈中的元素按次序存入到数组中；8. 魔王语言转字母语言void change(char a)将输入的魔王语言通过循环判断转换成字母语言；9 .将字母语言翻译为人类语言void translate(char a,struct Word *h) 将已经由魔王语言转换成的字母语言通过对照转换成人类语言10. 文件保存函数void save_file(struct Word *h) 将已经转换好的魔王语言保存到自定义路径。四详细设计main函数1功能函数的调用关系图 将结果存文件魔王的话转化成小写从件中读入规则解释为汉意显示从文件中读入汉意调用取括号函数读入魔王所说的话2各功能函数的数据流程图(1)取括号函数deletenode(&s,&r,a,i);入A栈入F栈入目的队列结束将处理结果放回栈一层处理一层括号右括号左括号后非第一个字母左括号后第一个字母括号中内容从Q中弹出一个元素Q是否为空定义变量，初始化栈以及队列开始 流程图: Y N是否为括号中内容 N Y将处理结果放回队列 Y N（2）转化成小写字母函数change(a); 流程图：queue是否为空定义变量，初始化栈以及队列开始 Y N从队列Q中弹出元素放于data中Data为大写字母 N调用的函数执行递归 Y入队列Q结束开始（3）翻译为汉语意思函数translate(a,l); 初始化规则内容存在 N大写字母所对应的规则内容放于数组str中 Y Stri大写 Y 入队列Q，i+ NStri存在 Y结束 N （4) 读大小写对应规则void read_file(); 流程图:开始 打开文件rule.txt打开文件失败 Y从文件中读取信息 N文件结束 Y 保存链表 N 关闭文件结束 开始 (5) 将字母与汉字相匹配流程图开始 初始化dataQ是否为空 Y N弹出对头元素data查找data对应的汉字汉字保存到文件result.txt中结束1 重点设计及编码 1. 去括号函数deletenode(&s,&r,a,i);void deletenode(Stack *s,Queue *r,char a,int i)int j,flag;char ch,t;while(i>=0)while(i>=0)if(ai!='(')/用ASCII码比较，判断ai是否为'('push(s,ai);i=i-1;elsei=i-1;break;j=0;flag=0;for(j=0;j<=s->top;j+)if(s->elemj=')')flag+;if(flag)while(s->top+1&&s->elems->top!=')')ch=pop(s);queue_in(r,ch);if(s->elems->top=')')pop(s);if(r->rear!=r->front)ch=queue_out(r);while(r->front!=r->rear)push(s,ch);t=queue_out(r);push(s,t);push(s,ch);i=s->top;while(i+1)printf("%c",s->elemi);i-; 2 转化成小写字母函数change(a);void change(char a)char b100;int flag=0;int i,j,k,n;i=j=k=0;b0='0'while(ai)/判断是否有大写字母if(ai>='A'&&ai<='Z')flag=1;i+;if(flag=0)return;i=0;while(ai)if(ai>='a'&&ai<='z')bj+=ai+;bj='0'elsewhile(ai!=xxk.l0)k+;n=strlen(xxk.r);strcat(b,xxk.r);j+=n;i+;k=0;strcpy(a,b);aj='0' change(a);3翻译为汉语意思函数translate(a,l);void translate(char a,struct Word *h)struct Word *m,*n;int i,k;i=k=0;n=h;while(ai)m=(struct Word *)malloc(sizeof(struct Word);m->data=ai;m->word0='0'while(ai!=yyk.l0)k+;strcat(m->word,yyk.r);m->next=NULL;k=0;i+;n->next=m;n=m;for(m=h->next;m;m=m->next)printf("%s",m->word);4.写文件操作void save_file(struct Word *h)FILE *fp;struct Word *p;char filename20;printf("nn请输入所要保存文件的文件名:");gets(filename);fp=fopen(filename,"at"); if(fp=NULL)printf("n打开文件失败,%s可能不存在n",filename);exit(1);p=h->next;while(p)fprintf(fp,"%s",p->word);p=p->next;fprintf(fp,"n");fclose (fp);1正常测试数据和运行结果测试数据1:B(ehnxgz)B运行结果：测试数据2:A(hnxB(egz)xh)运行结果：测试数据3：A(egz)xh)B运行结果：2异常测试数据及运行结果测试数据1：A(egz)D因没有D规则，则出错不会执行下述步骤。运行结果：测试数据2：Aam(e(egz) 因为没有m所对应的字母所以在字母与汉字匹配的过程中出错，不会执行其后的步骤。运行结果：六调试情况，设计技巧及体会1、 在写程序的过程中没有考虑到这种情况；例如：Bsa(egz)BC没有考虑到小写字母也可以出现在括号的外面，则在处理括号后最终队列中的结果为;Q：BezegeBC直接忽略到了sa经修改条件后，有一个flags标记，只要遇到左括号flags=flags+1；若处理完一层括号，flags=flags-1;所以只要判断flags是否为零则可以将括号外的不论是大写还是小写都入到Q中。Q:BsaezegeBC2、 设计技巧：函数功能里最能让我满意的一个函数功能，只有处理规则形式(2),也就是去括号的时候。虽然我用的是两个队列两个栈，但是可以将两个队列用数组实现，主要是我不能确定魔王语言的字母的个数，所以用了两个链队列。用两个栈两个队列实现了别人使用递归实现的功能，我觉得自己的时间复杂度没有那么高，可以节省在递归过程中不断的数据入栈，保存现场(保存CPU中各个寄存器的内容)，然后恢复现场一系列的事情所花费的时间。不管是几层括号都可以处理。3、 体会:增强了自己动手编程能力，同时也可以提高自己分析问题，解决问题的能力。在实际的情况下灵活的使用各个数据类型。1改进方案自我评价：自己的程序可以完成老师的所有的要求，因为我是按照上面的要求来实现自己的程序的，有些功能函数我既给出来递归也给出了非递归。不合理和不足之处：有的函数功能我觉得自己的时间复杂度不够好，有一些功能，我是让它实现了模块独立化，但是每次查找都需从头开始，浪费时间，是采取了时间换空间的要求。有时候没能让查找一次定位。这是最大的不足之处。 改进方案：可以在此程序的基础上实现让时间复杂度小，同时也要让空间复杂度小的要求，更合理的满足要求。2体会(1)在写程序的过程中程序肯定是会出错的，我想应该没有人能虽顺着自己的思路往下写程序的过程中不出一点差错，直到程序的末尾。(2)在我的编程过程中，我不是从头开始一口气写完所有的程序，然后在编译运行，调试自己的程序的出错地方，从第一个函数功能开始，我就开始查看自己的程序有什么错误，调试结束后。我在开始下一个程序的编写。这样子不至于到最后我不知道该从何处开始调试，在那个功能函数处出现的错误。七参考文献C语言程序设计 谭浩强 清华大学出版社C语言程序设计 王曙燕等 科学出版社数据结构使用C语言 陈一华等 电子科技大学出版社数据结构题集 严蔚敏，吴伟民 清华大学出版社八附录：源代码（电子版）#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<string.h>#define Maxsize 200#define MAX 100int maxline1,maxline2;typedef struct Elemchar x;struct Elem *next;ElemSN;struct rule char l2;char r10;struct Wordchar data;char word20; struct Word *next;typedef structint top;char elemMaxsize;Stack;typedef structint front,rear;char queueMaxsize;Queue;struct rule xx20;struct rule yy20; /入栈操作int push(Stack *s,char x)if(s->top+1=Maxsize)printf("n栈已满，不能继续入栈n");return 0;s->top+=1;s->elems->top=x;return 1;/出栈操作char pop(Stack *s)if(s->top=-1)printf("n栈已空，不可继续出栈n"); return('0'); s->top-;return s->elems->top+1;/入队操作int queue_in(Queue *p,char ch)if(p->front=(p->rear+1)%Maxsize)printf("n队列已满，不能继续进行入队操作n");return 0;p->queuep->rear=ch; p->rear=(p->rear+1)%Maxsize;return 1;/出队操作char queue_out(Queue *p)char ch;if(p->rear=p->front)printf("n队列已空，无法继续进行出队操作n"); return 0; ch=p->queuep->front; p->front=(p->front+1)%Maxsize;return ch;/去括号void deletenode(Stack *s,Queue *r,char a,int i)int j,flag;char ch,t;while(i>=0)while(i>=0)if(ai!='(')/用ASCII码比较，判断ai是否为'('push(s,ai);i=i-1;elsei=i-1;break;j=0;flag=0;for(j=0;j<=s->top;j+)if(s->elemj=')')flag+;if(flag)while(s->top+1&&s->elems->top!=')')ch=pop(s);queue_in(r,ch);if(s->elems->top=')')pop(s);if(r->rear!=r->front)ch=queue_out(r);while(r->front!=r->rear)push(s,ch);t=queue_out(r);push(s,t);push(s,ch);i=s->top;while(i+1)printf("%c",s->elemi);i-;/读大小写对应规则void read_file()FILE *fp;int i=0;char filename20;printf("nn请输入大小写转换规则所在的文件名:");gets(filename);fp=fopen(filename,"rt");if(fp=NULL)printf("n打开文件失败,%s可能不存在n",filename);printf("-n");exit(1); printf("大小写转换所对应的规则为:n");while(fscanf(fp,"%s %s",xxi.l,xxi.r)!=EOF)printf("%s->%s ",xxi.l,xxi.r);i+;fclose (fp);/读汉字对应规则void word_file()FILE *fp;int i=0;char filename20;printf("nn请输入汉字转换规则所在的文件名:");gets(filename);fp=fopen(filename,"rt");if(fp=NULL)printf("n打开文件失败,%s可能不存在n",filename);exit(1); printf("汉字转换所对应的规则为:n");while(fscanf(fp,"%s %s",yyi.l,yyi.r)!=EOF)/printf("%s %sn",yyi.l,yyi.r);printf("%s-%s ",yyi.l,yyi.r);i+;printf("n");fclose (fp);/将栈中的元素存入数组中void store(char a,Stack *s)int i=0;while(s->top+1)ai+=pop(s);ai='0'/大小写转换void change(char a)char b100;int flag=0;int i,j,k,n;i=j=k=0;b0='0'while(ai)/判断是否有大写字母if(ai>='A'&&ai<='Z')flag=1;i+;if(flag=0)return;i=0;while(ai)if(ai>='a'&&ai<='z')bj+=ai+;bj='0'elsewhile(ai!=xxk.l0)k+;n=strlen(xxk.r);strcat(b,xxk.r);j+=n;i+;k=0;strcpy(a,b);aj='0' change(a);/翻译void translate(char a,struct Word *h)struct Word *m,*n;int i,k;i=k=0;n=h;while(ai)m=(struct Word *)malloc(sizeof(struct Word);m->data=ai;m->word0='0'while(ai!=yyk.l0)k+;strcat(m->word,yyk.r);m->next=NULL;k=0;i+;n->next=m;n=m;for(m=h->next;m;m=m->next)printf("%s",m->word);/写文件操作void save_file(struct Word *h)FILE *fp;struct Word *p;char filename20;printf("nn请输入所要保存文件的文件名:");gets(filename);fp=fopen(filename,"at"); if(fp=NULL)printf("n打开文件失败,%s可能不存在n",filename);exit(1);p=h->next;while(p)fprintf(fp,"%s",p->word);p=p->next;fprintf(fp,"n");fclose (fp);void main()Stack s;Queue r;int i;char aMAX;struct Word *l;s.top=-1;r.front=r.rear=0;printf("t *n"); printf("t *欢迎使用魔王语言解释系统*n");printf("t *n"); printf("t *班级： *n"); printf("t * 姓名:* *n"); printf("t * 学号: *n"); printf("t *n");/输入魔王的话 printf("请输入魔王说的话:n"); gets(a);i=strlen(a);ai='0'i=i-1; printf("n魔王的话对应的字母为(去掉括号后):n"); deletenode(&s,&r,a,i);read_file();word_file();store(a,&s);change(a);printf("n魔王的话转化成小写为: ");i=0;while(ai)printf("%c",ai);i+;l=(struct Word *)malloc(sizeof(struct Word);l->next=NULL;printf("n翻译为汉语意思：");translate(a,l);save_file(l);printf("程序结束!n");