数据结构课程设计报告整理表达式

1、数据结构课程设计报告题目：编程整理表达式方法班 级： 计算机092 姓 名： 余海刚 指导教师： 董跃华 ，井福荣 成 绩：_ 2011年 6月 16日目录：摘 要21.引言 .22.需求分析.33.概要设计.34.详细设计.65.测试结果.116.调试分析.137.设计体会.148.结束语.14附录15参考文献摘要(题目):：键盘输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持与原表达式等价1.引言栈，是硬件。主要作用表现为一种数据结构，是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储

2、数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。 栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为先进后出表。 栈可以用来在函数调用的时候存储断点，做递归时要用到栈！文件是程序设计中的一个重要概念。所谓“文件”一般是指存储在外部介质上数据的集合。一批数据时以文件的形式存放在外部介质(如磁盘)上的。操作系统是以文件为单位对数据进行管理的，也

3、就是说，如果想找存在外部介质上的数据，必须先按文件名找到所指定的文件，然后从该文件中读取数据。要向外部介质上存储数据也必须先建立一个文件（以文件名标识），才能向它输出数据。本报告中所设计的整理表达式，实现了以线性表结构的单向表表示商场所需求的功能，将文件形式保存的数据恢复成线性表结构的单向表的流程中所需的功能。 2.需求分析输入字母和运算符号，输入数值也可以，但不好看，输出应输入对应。去掉所有多余的括号时，原表达式中所有变量和运算符相对位置保持不变，不能前移或是退后，并保持与原表达式等价。输入时也可以输入正确表达式。3.概要设计、 为包含的库函数 除此之外还有结构体和宏定义的应用系统流程图见图

4、 调用函数h;主函数main（）主界面menu（）函数kuanjia1（）函数delayMS函数Zlbds函数gotoTextPos函数strans4、详细设计4.1引用库函数及变量的定义 #include /*标准输入/输出头文件*/#include /*包含绘制图形函数等头文件*/#include /*包含字符串处理函数头文件*/#include /*包含动态存储与释放函数头文件*/#include #include #define Max 100 /*宏观定义栈的最大容量*/typedef struct stack /*栈结构定义*/ char dataMax; /*字符串定义，存储元素

5、*/int top; /*栈中指针，代表栈的长度*/liststack; 4.2 输入算法的实现void kuanjia1() /大框架 system(cls); printf(); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf(); gotoTextPos

6、(4,2); printf( ); gotoTextPos(4,3); printf( 整 理 表 达 式); gotoTextPos(4,4);printf( );void menu() /主界面 kuanjia1(); gotoTextPos(16,8); printf(1.Start); gotoTextPos(16,10); printf(2.Exit); gotoTextPos(2,14); printf(Please input your choice: );4.3输出算法的实现void zlbds() kuanjia1(); gotoTextPos(2,7); printf(In

7、put the primer expression:); gotoTextPos(2,8); char strMax,expMax,tranMax; scanf(%s,str); strans(str,exp,tran); gotoTextPos(2,10); printf(初步整理表达式:%s,exp); gotoTextPos(2,12); printf(最终整理表达式:%sn,tran); gotoTextPos(2,14); printf( Press any key to return!); getch();menu();int n; scanf(%d,&n); switch(n)

8、case 1:zlbds();break; case 2:return ; default:gotoTextPos(28,14);printf(Error!); gotoTextPos(2,16);printf( Press any key to try again!); getch(); menu(); 4.4 算法void strans(char str,char exp,char tran) /*子函数，删除字符串中多余项*/ liststack op; /*定义一个栈*/ int i=0,t=0,j=0,k=-1; op.top=-1; /*栈的初始位置*/ for(i=0;iMax;

9、i+) /*把输入的字符串存储在栈中*/ op.top+; /*指针移动*/ op.dataop.top=stri; /*第i个字符入栈*/ for(i=0;i=op.top;i+) /*从栈中查找元素*/ if(op.datai=() /*第i个元素若为“（”*/ if(op.datai-1=*|op.datai-1=/) /*如若第i个元素之前有“*”或“/”.即“（”前面有*或/*/ expi=op.datai; /*那么把第i个元素存在此数组里，即初始整理结果的存储位置*/ else if(i=0) /*如若第i个元素之前没有“*”或“/”，并且i=0*/ expi=op.datai;

10、 /*那么把第i个元素存在此数组里，也即初始整理结果的存储位置*/ k=i; /*i的直赋给k，k用于记录当前记录位置*/ else /*i！=0*/ expi=op.datai;/*那么把第i个元素存在此数组里，也即初始整理结果的存储位置*/ k=i; /*i的值赋给k，k用于记录当前记录位置*/ else if(op.datai=) /*第i个元素如不为“（”，而为“）”*/ if(op.datai+1=*|op.datai+1=/|k=-1) /*如果“）”后有*或/*/ expi=op.datai; /*那么把第i个元素存在此数组里，即初始整理结果的存储位置*/ else if(i=o

11、p.top&k=-1) /*“（”后面没有*或/ ，并且当前位置合法*/ expi=op.datai; /*那么把第i个元素存在此数组里，也即初始整理结果的存储位置*/ else /*当前位置不合法*/ expi= ; /*此数组存空*/ expk= ; /*此数组存空*/ k=-1; else /*第i各元素如若不为（，而不为“）”*/ expi=op.datai; /*那么把第i个元素存在此数组里，也即初始整理结果的存储位置*/ expop.top+1=0; /*最后一个存/0*/ while(expt!=0) if(expt!= ) /*第t个元素不为空*/ tranj=expt; /*

12、把它放在最终整理数组中*/ t+; j+; else if(expt= &t!=op.top) /*第t个元素为空 ，并且当前位置合法*/ tranj=expt+1; /*把下一个放在最终整理数组中*/ t=t+2; j+; else break; /*跳出循环*/ 4.5主函数int main() system(mode con:cols=40 lines=20); setConsoleTitle(整理表达式 by余海刚); system(color 0A); menu(); kuanjia1(); gotoTextPos(10,7); printf(拜); delayMS(600); go

13、toTextPos(19,7); printf(拜); delayMS(600); gotoTextPos(20,9); printf(b); delayMS(600); gotoTextPos(21,9); printf(y); delayMS(600); gotoTextPos(24,9); printf(余); delayMS(600); gotoTextPos(26,9); printf(海); delayMS(600); gotoTextPos(28,9); printf(刚); delayMS(600); return 0; 5、 测试结果 5.1输入界面 5.2.1输出界面 输入

14、选择1的运行界面。见1.10 图 1.10 输入程序的运行界面 5.2.2输入选择2的运行界面。见 5.2.3输入其它选择的运行界面。见 6、 调试分析 编译时，发现有的括号可删可不删时，会自动删除，这样导致程序不够紧密。刚刚接到这个题目的时候，我发现用栈做会更加的减少时间复杂度和空间复杂度，从而更好的方便使用，于是我的一切出发点都是围绕方便使用者进行。程序的开始我使用的是宏定义，使程序更加的简洁明了，其中贯穿程序大部分的是字符串和数组。登陆界面其实是利用判断语句做的，后面的输入输出没有什么特别的，是按照一般线性表的输入输出做的，。除此之外，我还花了一部分时间到美化界面上，现在的界面是在我的能

15、力范围之内最好的。7、 设计体会通过这个星期的课程设计，我的收获还是不少的。刚开始看到这个课程设计题目的时候，我觉得很有信心，因为我认为我的数据结构和C语言中我最喜欢也是学的最好的地方就是线性，但是随着对这个题目的细细探索，我发现这题目还是有一定的难度的，越看我觉得越急躁，但是这样反而更加的阻碍我的思路，直到我碰到一个在C语言方面颇有心得的同学，他帮我解决了很多问题，更主要的是他让我明白了耐性在一个程序中的重要作用，现在，借着这里我想真诚的对他说一声“谢谢！”我一定会更加的努力培养我的耐性，让我的人生更加的美好而成功！数据结构的很多算法没能熟练的掌握，以致在调试的时候花了很长时间，而且程序不够

16、工程化，功能不够完善。程序设计的过程中，代码的编写很不熟练，而且很容易犯一些低级的错误，如：语句后面的分号忽略了，括号不匹配等等。8、 结束语该系统我主要做了三个功能选项,，一个主界面。解决了编程整理表达式问题，当然此系统也可应用到其它表达式系统。它是利用了C语言实现的。此系统的作界面，操作员可以对某个指定的库存文件进行选择，文件名自定。非常感谢老师对我的教导。参考文献 1 严蔚敏 吴伟名 编著，数据结构， 清华大学出版社， 2001年1月 2 谭浩强 编著， C程序设计（第三版） ，新世纪计算机基础教育丛书 清华大学出版社 ，2005年7月第三版3张颖江，胡燕。c语言程序设计M。北京：科学出

17、版社。1985年。4 裔红艳 数据结构课程设计报告 , 计算机师范 5 知道 6 李春葆 编著，数据结构习题与解析（第三版），清华大学出版社，2006年10月20附录：#include#include#include#include#include#include strong.cpp#define Max 100void menu();typedef struct stack char dataMax; int top;liststack;void kuanjia1() /大框架 system(cls); printf(); printf( ); printf(

18、); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf( ); printf(); gotoTextPos(4,2); printf( ); gotoTextPos(4,3); printf( 整 理 表 达 式); gotoTextPos(4,4); printf( );void strans(char str,char e

19、xp,char tran) liststack s; int i=0,t=0,j=0,k=-1; s.top=-1; for(i=0;iMax;i+) s.top+; s.datas.top=stri; for(i=0;i=s.top;i+) if(s.datai=() if(s.datai-1=*|s.datai-1=/) expi=s.datai; else if(i=0) expi=s.datai; k=i; else expi=s.datai; k=i; else if(s.datai=) if(s.datai+1=*|s.datai+1=/|k=-1) expi=s.datai; e

20、lse if(i=s.top&k=-1) expi=s.datai; else expi= ; expk= ; k=-1; else expi=s.datai; exps.top+1=0; while(expt!=0) if(expt!= ) tranj=expt; t+; j+; else if(expt= &t!=s.top) tranj=expt+1; t=t+2; j+; else break; void zlbds() kuanjia1(); gotoTextPos(2,7); printf(Input the primer expression:); gotoTextPos(2,8

21、); char strMax,expMax,tranMax; scanf(%s,str); strans(str,exp,tran); gotoTextPos(2,10); printf(初步整理表达式:%s,exp); gotoTextPos(2,12); printf(最终整理表达式:%sn,tran); gotoTextPos(2,14); printf( Press any key to return!); getch(); menu();void menu() /主界面 kuanjia1(); gotoTextPos(16,8); printf(1.Start); gotoTextP

22、os(16,10); printf(2.Exit); gotoTextPos(2,14); printf(Please input your choice: ); int n; scanf(%d,&n); switch(n) case 1:zlbds();break; case 2:return ; default:gotoTextPos(28,14);printf(Error!); gotoTextPos(2,16);printf( Press any key to try again!); getch(); menu(); int main() system(mode con:cols=4

23、0 lines=20); setConsoleTitle(整理表达式 by余海刚); system(color 0A); menu(); kuanjia1(); gotoTextPos(10,7); printf(拜); delayMS(600); gotoTextPos(19,7); printf(拜); delayMS(600); gotoTextPos(20,9); printf(b); delayMS(600); gotoTextPos(21,9); printf(y); delayMS(600); gotoTextPos(24,9); printf(余); delayMS(600);

24、 gotoTextPos(26,9); printf(海); delayMS(600); gotoTextPos(28,9); printf(刚); delayMS(600); return 0; #include pcc32.hvoid delayMS(uint32 d)Sleep(d);return ;void clearText(void)system(cls);return ;int setTextColor(uint8 fColor)HANDLE hd = GetStdHandle(STD_OUTPUT_HANDLE);CONSOLE_SCREEN_BUFFER_INFO csbIn

25、fo;GetConsoleScreenBufferInfo(hd, &csbInfo);return SetConsoleTextAttribute(hd, fColor | (csbInfo.wAttributes&0x0F);PCCOLOR getTextColor(void)CONSOLE_SCREEN_BUFFER_INFO csbInfo;GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE), &csbInfo);return (PCCOLOR)(csbInfo.wAttributes&0x0F);int setBack

26、Color(uint8 bColor)HANDLE hd = GetStdHandle(STD_OUTPUT_HANDLE);CONSOLE_SCREEN_BUFFER_INFO csbInfo;GetConsoleScreenBufferInfo(hd, &csbInfo);return SetConsoleTextAttribute(hd, (bColor 4);int setColors(uint8 fColor, uint8 bColor)HANDLE hd = GetStdHandle(STD_OUTPUT_HANDLE);CONSOLE_SCREEN_BUFFER_INFO csb

27、Info;GetConsoleScreenBufferInfo(hd, &csbInfo);return SetConsoleTextAttribute(hd, fColor | (bColor 4) | (csbInfo.wAttributes&0xFF);int setSwapColors(bool b)HANDLE hd = GetStdHandle(STD_OUTPUT_HANDLE);CONSOLE_SCREEN_BUFFER_INFO csbInfo;GetConsoleScreenBufferInfo(hd, &csbInfo);if (!b)return SetConsoleT

28、extAttribute(hd, csbInfo.wAttributes | 0x4000);elsereturn SetConsoleTextAttribute(hd, csbInfo.wAttributes & 0x4000);int setUnderLine(bool b)HANDLE hd = GetStdHandle(STD_OUTPUT_HANDLE);CONSOLE_SCREEN_BUFFER_INFO csbInfo;GetConsoleScreenBufferInfo(hd, &csbInfo);if (!b)return SetConsoleTextAttribute(hd, csbInfo.wAttributes | 0x8000);elsereturn SetConsoleTextAttribute(hd, csbInfo.wAttributes & 0x8000);uint8 getLineWidth(void)CONSOLE_SCREEN_BUFFER_INFO csbInfo;GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE), &csbInfo);return csbInfo.dwSize.X;uint8 getCurs