数据结构课程设计报告---利用线性表进行算式计算

1、数据结构课程设计报告 利用线性表进行算式计算一：问题描述：在计算机中，算术表达式由常量、变量、运算符号和括号组成，由于不同的运算符具有不同的优先级，又要考虑到括号，因此，算术表达式的求值不可能严格地从左往右进行，因而在程序设计时，借助栈实现。算法要点：设置运算符栈和运算数队列辅助分析算符优先关系，在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。二：需求分析1、输入的形式和输入值的范围一个算术表达式，由常量、变量、运算符和括号组成以字符串的形式输入。为简化，规定操作数只能为整数，操作符为“+、“-、“*、“/、“%，用“#开始且用“#结束，优先级为：括号-%-*,/-+

2、,-。2、输出的形式即输出表达式运算结果，本算法中输出的形式为The end is：.3、程序所能到达的功能 界面上出现一个文本框，输入一个表达式以“#开始并以“#结束，此表达式包括“+、“-、“*、“/、“%、括号以及整数，点击回车，显示结果。4、测试结果 正确的输入一个表达式是指输入一个正确的表达式即不能连续输入两个运算符括号除外，切以“#开始以“#结束，点击回车界面上出现The end is：即此表达式的结果。输入表达式错误有两种形式：1、所输入的表达式未以“#开始那么点击回车，系统会提示“RROE!Please begin with "#“，“且下面输出Continue?(y

3、/n):“，假设输入Y或者y，那么再次进入主界面输入表达式，假设输入N或者n,那么跳出系统。2、所输入的表达式错误，即连续输入两个运算符，此时系统会提示“ERROE!Please input another time!“，三：概要设计 主程序的流程图为 YNNY开始输入表达式输出结果结束输入表达式有误是否继续四：详细设计1、本系统中所用到的抽象数据类型有栈的抽象数据类型以及队列的抽象数据类型。栈的抽象数据类型定义：ADT Stack 数据对象：D=ai| ai ElemSet,i=1,2,3n,n0 数据关系：R1= <ai-1, ai D,i=2,3n根本操作： InitStack&a

4、mp;S操作结果：构造一个空栈DestoryStack&S初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack&S初始条件：栈S已存在。操作结果：将S清为空栈。 StackEmpty&S初始条件：栈S已存在。操作结果：假设栈S为空栈，那么返回TRUE,否那么返回FALSE。StackLength&S初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTopS，&e初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。PushS，&e初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。PopS，&e初

5、始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。StackTraverseS，visit()初始条件：栈S已存在且非空。操作结果：从栈底到栈顶一次对S的每个元素调用函数visit。一旦visit失败，那么操作失败。ADT stack队列的抽象数据类型定义：ADT Queue 数据对象：D=ai| ai ElemSet,i=1,2,3n,n0 数据关系：R1= <ai-1, ai D,i=2,3n 约定其中ai端为队列头，an端为队列尾根本操作： InitQueue&Q操作结果：构造一个空队列Q。DestoryQueue&Q初始条件：队列Q已存在。操作

6、结果：队列Q被销毁。ClearQueue&Q初始条件：队列Q已存在。操作结果：将Q清为空队列。 QueuekEmpty&Q初始条件：队列Q已存在。操作结果：假设队列Q为空栈，那么返回TRUE,否那么返回FALSE。QueueLengthQ初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。GetHeadQ，&e初始条件：队列Q已存在且非空。操作结果：用e返回Q的队头元素。EnQueueQ，&e初始条件：队列Q已存在。操作结果：插入元素e为新的队尾元素。DeQueueQ，&e初始条件：队列Q已存在且非空。操作结果：删除Q的队头元素，并用e返回

7、其值。QueueTraverseQ，visit()初始条件：Q已存在且非空。操作结果：从队头到队尾一次对Q的每个元素调用函数visit。一旦visit失败，那么操作失败。ADT queue2、主要算法流程图算符间的优先关系为如下列图，其中#代表表达式的结束符，为了算法简洁，在表达式的最左边也虚设一个“#“构成整个表达式的一对括号。 +-*/%#+>><<<><>->><<<><>*>>>><>></>>>><>>

8、;<(<<<<<=<)>>>>>>%>>>><>>>#<<<<<<=3、各模块间的层次调用1.算法思路 a.假设导入的是操作数，那么直接输出到队列。 b.假设当前运算符的优先级高于栈顶运算符的优先级，那么入栈。 c.假设当前运算符的优先级低于栈顶运算符的优先级，那么栈顶运算符退栈，并输出到队列，当前运算符再与新的栈顶运算符比拟。 d.假设当前运算符的优先级等于栈顶运算符的优先级，且栈顶运算符为左括号，当前运算符为右括号，那么栈顶运算符

9、退栈，继续读下一个符号。 e.假设当前运算符的优先级等于栈顶运算符的优先级，且栈顶运算符为“#“，当前运算符也为#“，那么栈顶运算符退栈，输出队列中的数值即可。 2.各个函数的含义 头函数结束以后用typedef struct snode 定义栈的结构体，void initiatels(slnode *h) 此函数是对栈的初始化，即构造一个空栈，void pushls( slnode *h,char *x) 、char *popls( slnode *h,char *x) ，分别是进栈出栈函数的实现。typedef struct qnode 队列的结构体定义，typedef struct 此函

10、数是对队列的初始化，即构造一个空队列，void initiatelq(lqtype *q) 、void enterlq(lqtype *q,char *x) ，分别是入队列以及出队列的实现。这就是函数模块的实现，除此之外在主函数main函数中利用函数whilec！=“#“ 即可获取屏幕上输入的字符，数据和运算符并分别将其存放在结点中，利用函数whilex【0】！=35 来判断x进入符号栈还是队列，enterlqoperand，x；说明x是数据那么进入队列，利用函数ifa<=b 判断如果x的优先级大于当前栈顶元素的优先级，那么进栈。利用函数ify【0】=40 判断如果x是“，那么依次输出符

11、号栈的元素，放进队列中，直到遇到“为止，否那么else函数表示mid为空后，一次输出符号栈的元素至队列中，直到遇到#“为止。五：调试分析本实验要调试成功在此之前肯定遇到很多困难经常会出现一些说明语法错误以及出现一些语法错误等各种各样的问题，此时要检查自己的代码，找到自己代码的问题所在，不折不挠屡次调试即可。本实验的时间复杂度是On，空间复杂度为On。此实验是利用一个栈和一个队列，可以改良为两个栈的运算，一个栈存放运算符，另外一个栈存放运算数据。本实验算法采用了链式存储结构，以开辟新空间为代价，有效降低了算法时间复杂度和空间复杂度，并且对表达式的长度没有要求。六：测试结果 调试成功后进入的页面为

12、输入正确的表达式后点击y重新进入主页面假设输入错误的表达式后七：附录源程序#include<stdio.h>#include <conio.h>#include<stdlib.h>#include<math.h>#include<string.h>#include<graphics.h>#define null 0typedef struct snode /定义结构体 char data11;struct snode *next;slnode;void initiatels(slnode *h) /初始化 h->ne

13、xt = null; void pushls( slnode *h,char *x) /压栈 slnode *p; p = (slnode *)malloc(sizeof(slnode); strcpy(p->data,x); p->next = h->next; h->next = p; char *popls( slnode *h,char *x) /出栈 slnode *p; p = h->next; if(p!=null) h->next = p->next; return(p->data); return(x); typedef str

14、uct qnode /定义链队列结构体 char data11;struct qnode *next;qlnode;typedef struct qlnode *h; qlnode *rear; lqtype;void initiatelq(lqtype *q) /初始化 q->rear = q->h; q->h->next = null;void enterlq(lqtype *q,char *x) /入队qlnode *p; p = (qlnode *)malloc(sizeof(qlnode);/申请新结点strcpy(p->data,x); /新结点数据域

15、赋值 p->next = null;if(q->h=null)q->h = p;q->rear->next = p;q->rear = p; /修改尾指针char *deletelq(lqtype *q,char *x) /出队 qlnode *p; p = q->h->next; / 暂存原队头指针 if(q->h->next!=null) /队非空 q->h->next=p->next; /删除队头元素 if(q->h->next=null) q->rear->next=null; ret

16、urn(p->data); return(x); void main() char ch8='#','+','-','*','/','%','(',')' char c,cc, x11,y11,z11; int i,j,a,b,n; int t; slnode *operater,*pp; lqtype *mid,*operand; qlnode *ee; int mm;operater = (slnode *)malloc(sizeof(slnode); mi

17、d = (lqtype *)malloc(sizeof(lqtype); mid->h = (qlnode *)malloc(sizeof(qlnode); mid->rear = (qlnode *)malloc(sizeof(qlnode); operand = (lqtype *)malloc(sizeof(lqtype); operand->h = (qlnode*)malloc(sizeof(qlnode); operand->rear = (qlnode *)malloc(sizeof(qlnode); textmode(C80); textbackgrou

18、nd(3); clrscr(); window(8,8,70,18); textbackground(7); textcolor(18); clrscr();while(1) /初始化initiatelq(mid);initiatels(operater); initiatelq(operand); j = 0; a = 0; b = 0; n = 0;for(i=0;i<11;i+) xi='0' clrscr(); cprintf( "nPlease input the biaodashi(begin by"#"from left and

19、 stop by"#"from right)n"); cprintf("nThe string is:"); c = getchar(); x0=c; enterlq(mid,x); /将“#“进队 c=getchar(); x0=c; j=1; c=getchar(); while(c!='#') /获取屏幕上输入的字符，数据和运算符分别存放在结点中 if(c<48&&c!=46) if(x0!=0) enterlq(mid,x); for(i = 0;i < 11;i+) xi='0

20、9; j = 0; continue; else x0 = c; j = 1; ee=mid->rear; if(ee->data0!='(') enterlq(mid,x); for(i = 0;i < 11;i+) xi='0' j=0; else xj = c; j+; c=getchar(); if(x0!=0) enterlq(mid,x); for(i = 0; i < 11;i+) xi='0' x0 = c; enterlq(mid,x); for(i = 0;i <11; i+) xi='0

21、' getchar(); ee = mid->h->next; /表达式合法性检验 if(ee->data0!='#') printf("n ERROE!Please begin with "#"n"); printf(" Continue?(y/n):",x); cc = getchar(); getchar(); if(cc ='n'|cc='N') break; else if(cc ='y'|cc='Y') continu

22、e; while(ee->next!=null) if(strlen(ee->data)=1&&ee->data0='(') a+; if(strlen(ee->data)=1&&ee->data0=')') b+; if(strlen(ee->data)=1&&strlen(ee->next->data)= 1&&ee->data0<48&&ee->next->data0<48&&ee-&

23、gt; data0!=41&&ee->data0!=40&&ee->next->data0!= 41&&ee->next->data0!=40) n=1; break; ee = ee->next; if(a!=b|n!=0) printf("n ERROE!Please input another time!"); printf("n Continue?(y/n):",x); cc = getchar(); getchar(); if(cc ='n'|c

24、c='N') break; else if(cc ='y'|cc='Y') continue; strcpy(x,deletelq(mid,z); pushls(operater,x); /将“#“进入符号栈 strcpy(x,deletelq(mid,z);/依次将mid出队 while (x0!=35)/判断x进入符号栈还是进入队列 if(x0>47|x1>47) enterlq(operand,x);/x是数据那么进入队列 else if(x0!=41) pp=operater->next; strcpy(y,pp->

25、;data); while(y0!=40) for(i=6;i>=0;i-) if(chi=x0) a=i; if(chi=y0) b=i; if(a<=b) enterlq(operand,popls(operater,z); pp=operater->next; strcpy(y,pp->data); continue; /如果x的优先级大于当前栈顶元素的优先级，那么进栈 pushls(operater,x); break; if(y0=40) pushls(operater,x); strcpy(x,deletelq(mid,z); continue; /x是“，

26、那么依次输出符号栈的元素，放进队列中，知道遇到“为止 else pp=operater->next; strcpy(y,pp->data); while(y0!=40) enterlq(operand,popls(operater,z); pp=operater->next; strcpy(y,pp->data); strcpy(y,popls(operater,z); strcpy(x,deletelq(mid,z); pp=operater->next; strcpy(y,pp->data); /mid为空后，一次输出符号栈的元素至队列中，直到遇到“#“

27、为止 while (y0!=35) enterlq(operand,popls(operater,z); pp=operater->next; strcpy(y,pp->data); /最终operand为后缀表达式 ee=operand->h->next;/求出后缀表达式的值 while(operand->h->next->next!=null) strcpy(x,ee->data); strcpy(y,ee->next->data); if(ee->next->next!=null) strcpy(z,ee->n

28、ext->next->data); else ee=operand->h->next; continue; if(x0>47|x1>47)&&(y0>47|y1>47)&&(z0< 48&&strlen(z)=1) switch(z0) case '+':mm=atof(x)+atof(y); break; case '-':mm=atof(x)-atof(y); break; case '*':mm=atof(x)*atof(y); break

29、; case '/':mm=atof(x)/atof(y); break; case '%':mm=atoi(x)%atoi(y); break; strcpy(ee->data,gcvt(mm,11,z); ee->next=ee->next->next->next; ee=operand->h->next; continue; if(ee->next->next!=null) ee=ee->next; else ee=operand->h->next; strcpy(x,deletelq

30、(operand,z); /输出最终结果 printf("n The end:%sn",x); printf(" Continue?(y/n)",x); cc=getchar(); getchar(); if(cc='n'|cc='N') break; 利用树进行哈弗曼编码一：问题描述 利用哈弗曼编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输本钱，但是，这要求发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，对于双工通道即可以双向传输的信道，每端都要有一个完整的编码译码系统，因此可以

31、设计一个编码译码系统解决这样一个问题。二：实验内容文件conf.txt中保存了假设干字母及其出现的频度，要求所有频度加起来要为1，否那么载入时报错。字母及其频度保存的格式为：界面上，首先出现一个按钮，点击，载入conf.txt。然后输入一个字符串，由这些字母组成。点击按钮，显示哈夫曼编码的结果。同时，界面上如果输入哈夫曼编码，也能被翻译成相应的字母。如果输入格式错误，要求给予提示。三：概要设计 1、系统结构图功能模块图 哈弗曼编码译码器编 码译 码退 出2、功能模块说明 1、编码：读取文件建立哈夫曼树对文本进行哈弗曼编码并输出编码2、译码：提示输入需要译码的字符利用建好的哈夫曼树进行译码(3)

32、、退出：退出系统，程序运行结束。四：详细设计1. 主要算法流程图 创立哈夫曼树开 始htlnode.parent=i;htrnode.parent=i;hti.weight=htlnode.weight+htrnode.weight; hti.lchild=lnode;hti.rchild=rnode;p->weight=countip=p->nexti=1初始化哈弗曼链表且有2n-1个结点for(i=n;i<2*n-1;i+)i<n结 束编码开 始将字符存放入哈弗曼编码结构体数组的字符单元中hc.cdhc.start-='1'if(q=q->Pa

33、rent->LChildhc.cdhc.start-='0'p=p->nexti=n时结束译码开 始P！=Rootp=p->RchildCodei=0p=p->LChildif(htc.lchild=-1)c=2*n-2结 束五：调试分析1. 从叶子节点开始向上遍历树，获得哈弗曼编码；2. 根据哈弗曼编码遍历哈夫曼树直到叶子结点，得到译码；3. 算法时间复杂度的分析：时间复杂度为O(n2);4. 算法空间复杂度的分析：空间复杂度为On。六：测试结果 由于本实验是图形化界面，故无法得到完整的图形界面，但进入主页面以后即可看到以下界面。 这将是进入之后点击译

34、码所得到的界面再次点击回车即可看到如下图七：附录#include<stdio.h> #include<string.h> #include<graphics.h> #include<conio.h> #include<dos.h> #include<alloc.h>> #define UP 50 #define DOWN 90 #define LEFT 60 #define RIGHT 55 #define ENTER 40 #define N 50 #define M 2*N-1 #define SIZE 6typ

35、edef struct /定义结构体存放哈夫曼码 char data; float weight; int parent,lchild,rchild; HTNode; int choice; int key() union REGS lf; lf.h.ah=0; int86(0x16,&lf,&lf); return lf.h.ah; struct imformation char ch; float fre; imforSIZE='a',0.3,'b',0.2,'c',0.1,'d',0.2,'e'

36、;,0.1,'f',0.1;/给相关字符设置初值 typedef struct char cdN; int start; HCode; void CreateHT(HTNode ht,int n) int i,k,lnode,rnode; float min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; for (i=n;i<2*n-1;i+) /构造哈夫曼树 min1=min2=1.1; /使用两个最小权值的结点为左孩子和右孩子 lnode=rnode=-1; for (k=0;k

37、<=i-1;k+) if (htk.parent=-1) if (htk.weight<min1) min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weight<min2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; hti.weight=htlnode.weight+htrnode.weight; hti.lchild=lnode;hti.rchild=rnode; getchar(); void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,j,c; HCode hc; for (i=0;i<n;i+) /根据哈夫曼树求哈夫曼编码 hc.start=n; c=i; f=h