数据结构课程设计多项式相乘与魔王语言

西安郵電學院数据结构课程设计报告题 目： 多项式相乘与魔王语言 系部名称：专业名称：班 级：学号：学生姓名 ：指导教师：时间：2010年12月6日 至2010年12月15日一、课程设计目的通过对数据结构这门课一学期的学习，运用所学知识完成课程设计，进而掌握并巩固所学知识点，将所学真正与实际问题结合起来。二、课程设计内容1.多项式相乘 以动态单链表为存储结构，使用排序等操作实现多项式的乘法运算。2.魔王语言 以栈和队列为数据结构，使用文件读写查找等操作，完成对魔王语言的解释。三、需求分析（对所开发系统功能、性能的描述，想要实现的目标）1.多项式相乘应用该系统可以进行系数任意，指数任意的多项式相乘，在输入过程中还可以进行多项式相同指数项的合并，输出时按降幂排列。2.魔王语言应用该系统可以对魔王所说的话进行翻译，事先要建立好rule与mean文件，用来存放转换规则与对应意思，输入模块可任意输入魔王的语言，再通过转换与翻译模块将其语言翻译为人类语言。四、概要设计1.多项式相乘主函数合并函数乘法运算函数创建函数打印函数排序函数创建函数：用来创建多项式。乘法运算函数：用来进行多项是相乘的运算。合并函数：用来将相乘后所得多项式合并同类项。排序函数：将合并后的多项式暗降幂排列。打印函数：将最初输入的多项式与最终输出的多项式打印出来。2.魔王语言主函数字母转换函数翻译函 数主体函 数打印规则2函数打印规则1函数去括号函数写入函 数读规则2函数读规则1函数读规则1函数：读取规则1。读规则2函数：读取规则2。写入函数：将魔王所说的话写入文件并保存。去括号函数：将魔王所说话中的括号按要求去掉。翻译函数：将魔王所说的话翻译为人类语言。字母转换函数：将大写字母转换为小写字母。打印规则1函数：将规则1打印出来。打印规则2函数：将规则2打印出来。主体函数：与主函数共同调用模块。五、详细设计及运行结果（流程图， 函数之间相互调用的图示 ，程序设计及编码, 运行结果）1.多项式相乘/*乘法运算函数*/开 始L=headp=polya-next;p!=NULL; 假 真q=polyb-next;q!=NULL 假真r=(Polylist)malloc(sizeof(Polynode);r-coef=p-coef*q-coef; r-exp=p-exp+q-exp;L-next=r;L=r;q=q-next;p=p-next;L-next=NULL;结 束/*合并函数*/开 始r=Lr-next!=NULL; 是a=r-next-exp;p=r-next;p-next!=NULL; 否 是b=p-next-exp;a=b 否 是temp1=(Polylist)malloc(sizeof(Polynode);r-next-coef=r-next-coef+p-next-coef; temp1=p-next;p-next=temp1-next;free(temp1);p=p-next; r-next-coef=0否 是temp2=(Polylist)malloc(sizeof(Polynode);temp2=r-next;r-next=temp2-next;free(temp2); r=r-next结 束/*排序函数*/开 始r=L-next;r!=NULL; 否 是p=r-next;p!=NULL; 否 (r-exp)exp)否 是a=r-exp; r-exp=p-exp; p-exp=a; b2=p-coef; p-coef=r-coef; r-coef=b2; 结 束 r=r-nextp=p-next运行结果：2.魔王语言/*去括号函数*/开 始i=0;inext-data!=( 否EnterQueue(Q,e); PoP(S1,&e);c=e; PoP(S1,&k);Q-rear!=Q-front 否 Push(S1,c); DeleteQueue(Q,&e); Push(S1,e);Push(S1,c);Push(S1,ai);i+结 束开 始/*大小写转换函数*/S1-next!=NULL 否 是PoP(S1,&x);x=a&x=A&x=Z 否 是 i=0inext-element 否 是 r=Pi-next-nextr!=NULL; 否 是r=r-next 否r-element=a&r-elementelement); r-element=A&r-elementnext!=NULL 否 是PoP(S2,&e); mni=e; i+; save(mn,S);i=0否inext;r!=NULL 否 是r-element=mni 否 是 printf(%s,r-chinese); break;r=r-next;i+结 束运行结果： 六、调试情况，设计技巧及体会1.在本次课程设计中，虽然可以按照要求完成，但在某些设计上较为繁琐，可以加以修改，让其更加精简完善。2.此次课程设计，不仅是对所学数据结构知识的加以巩固，更是对自己动手能力的锻炼，将理论与实际真正结合起来，对以后要学习的专业知识也做好了一定的铺垫，对自己有一个较大的提升。七、参考文献C语言程序设计 谭浩强 清华大学出版社C语言程序设计 王曙燕等 科学出版社数据结构使用C语言 陈一华等 电子科技大学出版社数据结构题集 严蔚敏 吴伟民 清华大学出版社八、附录：源代码1.多项式相乘#include stdio.h#include stdlib.h#include math.htypedef struct Polynode int coef; /*系数*/ int exp; /*指数*/ struct Polynode *next;Polynode,*Polylist;/*创建函数*/void polycreate(Polylist head) Polylist rear,s; int c,e; rear=head; /*rear始终指向但链表的尾，便于尾插法进行建表*/ printf(请输入每一项的系数和指数:n); scanf(%d,%d,&c,&e); while(c!=0) s=(Polylist)malloc(sizeof(Polynode);s-next=NULL; s-coef=c; s-exp=e; rear-next=s; /*尾插法进行创建*/ rear=s; scanf(%d,%d,&c,&e); printf(建立结束!n);/*乘法运算函数*/void cheng(Polylist polya,Polylist polyb,Polylist head) Polylist p,q,r,L; L=head; for(p=polya-next;p!=NULL;p=p-next) for(q=polyb-next;q!=NULL;q=q-next) r=(Polylist)malloc(sizeof(Polynode); r-coef=p-coef*q-coef; r-exp=p-exp+q-exp; L-next=r;L=r; L-next=NULL;/*合并函数*/void combine(Polylist L) Polylist r,p,temp1,temp2; int a,b; for(r=L;r-next!=NULL;r=r-next) a=r-next-exp;p=r-next; /*r指向第一个元素的指数*/ while(p-next!=NULL) b=p-next-exp; /*指向第二个元素的指数*/ if(a=b) temp1=(Polylist)malloc(sizeof(Polynode); r-next-coef=r-next-coef+p-next-coef; temp1=p-next; /*合并后删掉后面一项*/ p-next=temp1-next;free(temp1); /*指针后移*/ else p=p-next; if(r-next-coef=0) /*若系数为0 ，则删除该结点*/temp2=(Polylist)malloc(sizeof(Polynode); temp2=r-next;r-next=temp2-next;free(temp2);/*排序函数*/void order(Polylist L) /*合并后的多项式中指数只存在大于和小于的关系*/ Polylist r,p; int a;float b2; r=(Polylist)malloc(sizeof(Polynode); p=(Polylist)malloc(sizeof(Polynode); for(r=L-next;r!=NULL;r=r-next) for(p=r-next;p!=NULL;p=p-next) /*按从大到小的顺序排列*/ if(r-exp)exp) a=r-exp; r-exp=p-exp; /*交换指数*/ p-exp=a; b2=p-coef; /*交换系数*/ p-coef=r-coef; r-coef=b2; /*打印函数*/void printf1(Polylist S) Polylist r; for(r=S-next;r;r=r-next) if(r-coefcoef,r-exp); else printf(%dx%d,r-coef,r-exp); if(r-next&r-next-coef0) printf(+); /*主函数*/void main() char flag=a; Polylist head,polya,polyb; head=(Polylist)malloc(sizeof(Polynode);head-next=NULL; polya=(Polylist)malloc(sizeof(Polynode);polya-next=NULL; polyb=(Polylist)malloc(sizeof(Polynode);polyb-next=NULL; while(flag=a) printf(n创建第一个多项式n); polycreate(polya); order(polya); combine(polya);printf1(polya); printf(n创建第二个多项式n); polycreate(polyb); order(polyb);combine(polyb); printf1(polyb); printf(n); printf(n输出多项式相乘n); printf();printf1(polya);printf(); printf(*);printf();order(polyb);printf1(polyb);printf(); printf(=);cheng(polya,polyb,head); combine(head);order(head);printf1(head); flushall(); printf(n需要继续进行多项式相乘运算吗?需要请按a键，否则任意其他键退出n); scanf(%c,&flag); 2.魔王语言#include stdio.h#include string.h#include stdlib.h#include conio.h#define MAX 100typedef struct nodechar data;struct node *next;LinkStackNode,*LinkStack;typedef struct Nodechar data;struct Node *next;LinkQueueNode; typedef struct LinkQueueNode *front;LinkQueueNode *rear;LinkQueue;struct perschar element;char chinese50;struct pers *next;void Push(LinkStack top,char x) /*头插法*/LinkStack temp;temp=(LinkStack)malloc(sizeof(LinkStackNode);temp-data=x;temp-next=top-next;top-next=temp; void PoP(LinkStack top,char *x)LinkStack temp;temp=top-next;top-next=temp-next;*x=temp-data;free(temp);void EnterQueue(LinkQueue *Q,char x) /*尾插法*/LinkQueueNode *NewNode; /*队列的结点*/NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode);if(NewNode!=NULL)NewNode-data=x;NewNode-next=NULL;Q-rear-next=NewNode;Q-rear=NewNode;void DeleteQueue(LinkQueue *Q,char *x)LinkQueueNode *p;p=Q-front-next;Q-front-next=p-next;if(Q-rear=p) Q-rear=Q-front;*x=p-data;free(p);/*读规则1函数*/void read1(struct pers *P26)FILE *fp;int i;char x;if(fp=fopen(H:课程设计quyingrule.txt,rt)=NULL)printf(nn *读规则文件出错，按任意键返回!*);getchar();exit(1);while(!feof(fp)for(i=0;ielement=x;p-next=r;p=r;fscanf(fp,%c ,&x);p-next=NULL;fclose(fp);printf(nn *文件1中信息已正确读出，按任意键继续!*n);getchar();/*读规则2函数*/void read2(struct pers *S)FILE *fp;struct pers *r,*head;int i=0;head=S;if(fp=fopen(H:课程设计quyingmean.txt,rt)=NULL)printf(nn *读翻译文件出错，按任意键返回*);getchar();exit(1);while(ielement);fscanf(fp,%s ,r-chinese);i+;head-next=r;head=r;head-next=NULL;fclose(fp);printf(nn *文件2中信息已正确读出，按任意键继续!*n);getchar();/*写入函数*/void save(char chMAX,struct pers *S)FILE *fp;struct pers *r;int i=0,l;if(fp=fopen(H:课程设计quyingresults.txt,at+)=NULL)/*可追加读入*/printf(写文件出错，按任意键返回);getchar();exit(1);l=strlen(ch);for(i=0;il;i+)/*存放字母翻译*/fprintf(fp,%c,chi);for(i=0;inext;while(r!=NULL)if(r-element=chi)/*找到该字母的汉语意思，输出*/fprintf(fp,%s,r-chinese);break;else r=r-next;printf(恭喜您保存成功，按任意键继续!n);getchar();fclose(fp);/*去括号函数*/void change(char a50,LinkStack S1,LinkQueue *Q,int l)int i;char c,e,k;for(i=0;inext-data!=()/*S1有头指针*/EnterQueue(Q,e);PoP(S1,&e);c=e;/*标记首字母*/PoP(S1,&k);/*去掉左括号*/while(Q-rear!=Q-front)Push(S1,c);DeleteQueue(Q,&e);Push(S1,e);Push(S1,c); else Push(S1,ai);/*利用递归进行大小写代换*/void exchange(char x,struct pers *P26,LinkStack S3)int i;struct pers *r;r=(struct pers*)malloc(sizeof(struct pers);r-next=NULL;for(i=0;inext-element) for(r=Pi-next-next;r!=NULL;r=r-next)if(r-element=a&r-elementelement);else if(r-element=A&r-elementelement,P,S3);break;/*大小写代换，大写字母调用exchange函数*/void translate(LinkStack S1,LinkStack S,struct pers *P26)char x,m;LinkStack S3;S3=(LinkStack)malloc(sizeof(LinkStackNode);S3-next=NULL; while(S1-next!=NULL) PoP(S1,&x);if(x=a&x=A&xnext!=NULL)PoP(S3,&m);Push(S,m);/*大写字母入栈*/*打印规则1函数*/void printf1(struct pers *P26)int i,j=0;char m;struct pers *r;for(i=0;inext;/*大写字母*/m=r-element;printf(%c=,m);while(r-next!=NULL)printf(%c,r-next-element);r=r-next;printf(t);j+;if(j%7=0) printf(n);/*打印规则2函数*/void printf2(struct pers *S)int i=0,j=0;struct pers *r;r=S-next;while(jelement,r-chinese);r=r-next;i+;j+;if(i%10=0)printf(n);/*主体函数*/void center(struct pers *P26,struct pers *S)struct pers *r;char mnMAX=0;/*mn放翻译后的人类语言*/char a50,m50,e;/*放魔王语言*/int i=0,l;LinkStack S1,S2;LinkQueue *Q;/*定义两个栈，一个队*/S1=(LinkStack)malloc(sizeof(LinkStackNode);S1-next=NULL;S2=(LinkStack)malloc(sizeof(LinkStackNode);S2-next=NULL;Q=(LinkQueue *)malloc(sizeof(LinkQueue);Q-front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode);Q-rear=Q-front;Q-front-next=NULL;flushall();printf(魔王说的话是:);gets(a);l=strlen(a);change(a,S1,Q,l);/*调用函数，去掉括号，存入栈S1中，话首在栈底*/translate(S1,S2,P);/*话首在栈2头*/flushall();while(S2-next!=NULL)PoP(S2,&e);mni=e;i+;save(mn,S);printf(魔王语言翻译成人类语言是:);l=strlen(mn); puts(mn);printf(即:);for(i=0;inext;while(r!=NULL)if(r-element=mni)/*找到该字母的汉语意思，输出*/printf(%s,r-chinese);break;else r=r-next;void main()struct pers *S,*P26;/*S放字母的汉语意思，P放规则*/char flag=n;/*放魔王语言*/S=(struct pers*)malloc(sizeof(struct pers);S-next=NULL;read1(P);/*S表示英语字母的汉语意思，P表示魔王语言的规则*/printf(以下是魔王语言的规则n);printf1(P);read2(S);printf(以下是每个字母代表的汉语意思n);printf2(S);getchar();printf(nn);while(flag=n)system(cls);center(P,S);/*把规则传进函数*/printf(nn您还需要继续进行翻译吗?若需要请按回车键，否则按其他任意键退出n); scanf(%c,&flag);