数据结构课程设计利用线性表进行算式计算.doc

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

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

3、且下面输出”Continue?(y/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基本操作：

4、InitStack（&S）操作结果：构造一个空栈DestoryStack（&S）初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack（&S）初始条件：栈S已存在。操作结果：将S清为空栈。 StackEmpty（&S）初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE,否则返回FALSE。StackLength（&S）初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop（S，&e）初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push（S，&e）初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop（S，&e）初始条件：栈S已存

5、在且非空。操作结果：删除S的栈顶元素，并用e返回其值。StackTraverse（S，visit()）初始条件：栈S已存在且非空。操作结果：从栈底到栈顶一次对S的每个元素调用函数visit（）。一旦visit（）失败，则操作失败。ADT stack队列的抽象数据类型定义：ADT Queue 数据对象：D=ai| ai ElemSet,i=1,2,3n,n0 数据关系：R1= -*(=%#=3、各模块间的层次调用（1）.算法思路 a.若导入的是操作数，则直接输出到队列。 b.若当前运算符的优先级高于栈顶运算符的优先级，则入栈。 c.若当前运算符的优先级低于栈顶运算符的优先级，则栈顶运算符退栈，并

6、输出到队列，当前运算符再与新的栈顶运算符比较。 d.若当前运算符的优先级等于栈顶运算符的优先级，且栈顶运算符为左括号，当前运算符为右括号，则栈顶运算符退栈，继续读下一个符号。 e.若当前运算符的优先级等于栈顶运算符的优先级，且栈顶运算符为“#“，当前运算符也为”#“，则栈顶运算符退栈，输出队列中的数值即可。 （2）.各个函数的含义 头函数结束以后用typedef struct snode 定义栈的结构体，void initiatels(slnode *h) 此函数是对栈的初始化，即构造一个空栈，void pushls( slnode *h,char *x) 、char *popls( slno

7、de *h,char *x) ，分别是进栈出栈函数的实现。typedef struct qnode 队列的结构体定义，typedef struct 此函数是对队列的初始化，即构造一个空队列，void initiatelq(lqtype *q) 、void enterlq(lqtype *q,char *x) ，分别是入队列以及出队列的实现。这就是函数模块的实现，除此之外在主函数main（）函数中利用函数while（c！=“#“） 即可获取屏幕上输入的字符，数据和运算符并分别将其存放在结点中，利用函数while（x【0】！=35） 来判断x进入符号栈还是队列，enterlq（operand，x）

8、；说明x是数据则进入队列，利用函数if（a=b） 判断如果x的优先级大于当前栈顶元素的优先级，则进栈。利用函数if（y【0】=40） 判断如果x是”）“，则依次输出符号栈的元素，放进队列中，直到遇到”（“为止，否则else函数表示mid为空后，一次输出符号栈的元素至队列中，直到遇到”#“为止。五：调试分析本实验要调试成功在此之前肯定遇到很多困难经常会出现一些说明语法错误以及出现一些语法错误等各种各样的问题，此时要检查自己的代码，找到自己代码的问题所在，不折不挠多次调试即可。本实验的时间复杂度是O（n），空间复杂度为O（n）。此实验是利用一个栈和一个队列，可以改进为两个栈的运算，一个栈存放运算符

9、，另外一个栈存放运算数据。本实验算法采用了链式存储结构，以开辟新空间为代价，有效降低了算法时间复杂度和空间复杂度，并且对表达式的长度没有要求。六：测试结果 调试成功后进入的页面为输入正确的表达式后点击y重新进入主页面若输入错误的表达式后七：附录源程序#include#include #include#include#include#include#define null 0typedef struct snode /定义结构体 char data11;struct snode *next;slnode;void initiatels(slnode *h) /初始化 h-next = null;

10、 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 struct qnode /定义链队列结构体 char data11;struct qno

11、de *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); /新结点数据域赋值 p-next = null;if(q-h=null)q-h = p;q-rear-next = p;q-rear =

12、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; return(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;

13、lqtype *mid,*operand; qlnode *ee; int mm;operater = (slnode *)malloc(sizeof(slnode); mid = (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); oper

14、and-rear = (qlnode *)malloc(sizeof(qlnode); textmode(C80); textbackground(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;i11;i+) xi=0; clrscr(); cprintf( nPlease in

15、put the biaodashi(begin by#from left and 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(c48&c!=46) if(x0!=0) enterlq(mid,x); for(i = 0;i rear; if(ee-data0!=() enterlq(mid,x);

16、 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 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; el

17、se if(cc =y|cc=Y) continue; 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-data0next-data0 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 ERRO

18、E!Please input another time!); printf(n Continue?(y/n):,x); cc = getchar(); getchar(); if(cc =n|cc=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(x047|x147) enterlq(operand,x);/x是数据则

19、进入队列 else if(x0!=41) pp=operater-next; strcpy(y,pp-data); while(y0!=40) for(i=6;i=0;i-) if(chi=x0) a=i; if(chi=y0) b=i; if(anext; strcpy(y,pp-data); continue; /如果x的优先级大于当前栈顶元素的优先级，则进栈 pushls(operater,x); break; if(y0=40) pushls(operater,x); strcpy(x,deletelq(mid,z); continue; /x是“）“，则依次输出符号栈的元素，放进队列

20、中，知道遇到”（“为止 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为空后，一次输出符号栈的元素至队列中，直到遇到“#“为止 while (y0!=35) enterlq(operand,popls

21、(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-next-next-data); else ee=operand-h-next; continue; if(x047|x147)&(y047|y147)&(z0data,gcvt(mm

22、,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(operand,z); /输出最终结果 printf(n The end:%sn,x); printf( Continue?(y/n),x); cc=getchar(); getchar(); if(cc=n|cc=N) break; 利用树进行哈弗曼编码一：问题描述 利用哈弗曼编码进行通信可以大大提高信道的利用率，

23、缩短信息传输时间，降低传输成本，但是，这要求发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，对于双工通道（即可以双向传输的信道），每端都要有一个完整的编码译码系统，因此可以设计一个编码译码系统解决这样一个问题。二：实验内容文件conf.txt中保存了若干字母及其出现的频度，要求所有频度加起来要为1，否则载入时报错。字母及其频度保存的格式为：a:0.1b:0.2c:0.3界面上，首先出现一个按钮，点击，载入conf.txt。然后输入一个字符串，由这些字母组成。点击按钮，显示哈夫曼编码的结果。同时，界面上如果输入哈夫曼编码，也能被翻译成相应的字母。如果输入格式错误，要求给予

24、提示。三：概要设计 1、系统结构图（功能模块图） 哈弗曼编码译码器编 码译 码退 出2、功能模块说明 （1）、编码：读取文件建立哈夫曼树对文本进行哈弗曼编码并输出编码（2）、译码：提示输入需要译码的字符利用建好的哈夫曼树进行译码(3)、退出：退出系统，程序运行结束。四：详细设计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初始化哈弗

25、曼链表且有2n-1个结点for(i=n;i2*n-1;i+)iParent-LChildhc.cdhc.start-=0p=p-nexti=n时结束译码开 始P！=Rootp=p-RchildCodei=0p=p-LChildif(htc.lchild=-1)c=2*n-2结 束五：调试分析1. 从叶子节点开始向上遍历树，获得哈弗曼编码；2. 根据哈弗曼编码遍历哈夫曼树直到叶子结点，得到译码；3. 算法时间复杂度的分析：时间复杂度为O(n2);4. 算法空间复杂度的分析：空间复杂度为O（n）。六：测试结果 由于本实验是图形化界面，故无法得到完整的图形界面，但进入主页面以后即可看到以下界面。 这将是进入之后点击译码所得到的界面再次点击回车即可看到如图所示七：附录#incl