数据结构上机实验报告.docx

数据结构上机实验报告 欢迎交流（760135448）2015年11月20日上机实验一1 上机实验简介1）实验目的 当用户输入一个合法的算术表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的操作数要求在实数范围内；对于异常表达式能给出错误提示。2）开发工具C+语言，Microsoft Visual C+ 6.0开发软件3）测试数据分别对一位数、多位数以及小数的四则运算进行检验，我选取了下面几个式子： 3+4-5*(12/6)# 100+20*(26/13)# 1.3+3.4-(5.6/1.2)# 正确计算结果应分别为-3.00、140.00与0.03，用所做程序计算并与正确结果比较。2 算法说明(1)概要说明：为实现上述程序功能： 1. 首先置操作数栈为空栈，表达式起始符为运算符栈的栈底元素； 2. 依次扫描表达式中每个字符，若是操作数则进OPND栈；若是运算符，则 和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。3. 先做一个适合个位的+-*/运算, 其次就要考虑到对n位和小数点的运算。(2)程序主要模块 主要模块有：头文件、栈定义及栈函数、运算符判断与优先级比较函数、实现计算函数 InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S已存在。 操作结果：用P返回S的栈顶元素。 Push(&S，e) 初始条件：栈S已存在。 操作结果：插入元素ch为新的栈顶元素。 Pop(&S，e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素。 In(c) 操作结果：判断字符是否是运算符，运算符即返回1。Precede(c1, c2) 初始条件：c1,c2为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate(a,op,b)初始条件：a,b为整数，op为运算符。操作结果：a与b进行运算，op为运算符，返回其值。 EvaluateExpression() 初始条件：输入表达式合法。 操作结果：返回表达式的最终结果。1.栈定义及栈函数：用结构体定义栈，并实现对栈的以下操作：构造栈、取栈顶元素、入栈、出栈2.运算符优先级比较，返回优先级高的：算符间的优先关系如下：+-*/()#+-*/(#=表 13.主要操作函数。算法概要流程图：各函数具体定义见附1程序清单。3 实验总结 这次实验的目的主要是在表达式求值中应用栈这种线性数据结构。DOS框实现实验操作虽然更加本质，但是却不利于与用户，尤其是非编程人员的交互，因此我设计了简单的人机交互对话框，显得更加人性化。实验结果还有许多可以改进之处，例如使程序可以接受矩阵并作一些运算，对话框界面也有必要做进一步的功能添加。4 附1：程序清单（实验结果与实验程序已分享到网址/s/1ohzNC）#include using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -1#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status; typedef structdouble *base;double *top;int stacksize;SqStack1;typedef structchar *base;char *top;int stacksize;SqStack2;Status InitStack1(SqStack1 &S)S.base=(double *)malloc(STACK_INIT_SIZE*sizeof(double);if(!S.base) exit (OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack1Status InitStack2(SqStack2 &S)S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!S.base) exit (OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack2Status GetTop1(SqStack1 S,double &e)/若栈不空，则用e返回S的栈顶元素，并返回OK;否则返回ERRORif(S.top=S.base) return ERROR; e= *(S.top-1); /返回栈顶元素return OK;/GetTop1char GetTop2(SqStack2 S)/若栈不空，则用e返回S的栈顶元素，并返回OK;否则返回ERRORif(S.top=S.base) /coutaaa; return ERROR;char e= *(S.top-1); /返回栈顶元素/coute wwendl;return e;/GetTop2Status Push1(SqStack1 &S,double e)/插入元素e为新的栈顶元素/coutxinshuise=S.stacksize) /栈满，追加存储空间S.base=(double*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(float); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;/if*S.top+=e;return OK;/Push1Status Push2(SqStack2 &S,char e)/插入元素e为新的栈顶元素if(S.top-S.base=S.stacksize) /栈满，追加存储空间S.base=(char*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;/if*S.top+=e;return OK;/Push2Status Pop1(SqStack1 &S,double &e)/若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top=S.base) /coutaaaa; return ERROR; e=*-S.top;/coutthis ise,!,!,=;switch(ch1)/i为下面array的横标 case+:i=0;break; case-:i=1;break; case*:i=2;break; case/:i=3;break; case(:i=4;break; case):i=5;break; case#:i=6;break;switch(ch2)/j为下面array的纵标 case+:j=0;break; case-:j=1;break; case*:j=2;break; case/:j=3;break; case(:j=4;break; case):j=5;break; case#:j=6;break;return(array7*i+j);/返回运算符double Operate(double a,char theta,double b)switch(theta) case+:return(a+b);break; case-:return(a-b);break; case*:return(a*b);break; case/:return(a/b);break; default: cout输入错误！;return ERROR;break;Status EvaluateExpression()/算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，/OP为运算符集合SqStack1 OPND;SqStack2 OPTR;char c,x,theta,y,d;double a=0,b=0,k=0,z=0;InitStack1(OPND);InitStack2(OPTR); Push2(OPTR,#);cout请输入您要求解的表达式并以“#”结尾：=0&c=0&c=9) d2/=10; c-=0; e+=d2*c;c=getchar();/while/if Push1(OPND,e);else y=GetTop2(OPTR); d=Precede(y,c);switch(d) case:/退栈并将运算结果入栈 Pop2(OPTR,theta); Pop1(OPND,b); Pop1(OPND,a); Push1(OPND,Operate(a,theta,b); break; case!: cout请输入正确的表达式：endl; break; /switch/while GetTop1(OPND,k); cout表达式结果为： kendl; return OK;/EvaluateExpressionint main()EvaluateExpression(); /system(pause);return 0;5 附2：运行结果分别对实验简介中的三个式子进行结果检验(一）DOS框： （二）界面优化（MFC）：上机实验二1 上机实验简介1）实验目的 对用户指定的.htm文件，将文件中的所有TAG及TAG中所包含的内容全部去掉。2）开发工具C+语言，Microsoft Visual C+ 6.0开发软件3）测试数据对简单的个人网页qingtianzhe的个人主页与下载的西安交通大学数学与统计学院首页（4/sxtjxy/index.jsp）.htm文件做测试， 其中qingtianzhe的个人主页内容如下：atext-decoration:none; color:#FFF; font-size:16px; font-family:微软雅黑;position:relative; float:left; display:block;.nav background-color:#000; overflow:hidden; height:50px;a:hover border-bottom:5px solid #09F; font-size:18px; font-family:迷你简菱心;.navbox width:610px; margin:auto;.navbox amargin:15px 20px; padding-bottom:12px;qingtianzhe的个人主页.qingtianzhe的个人主页 . . . 基本信息 作品 兴趣爱好 足迹 学习生活 我的非诚勿扰 2 算法说明(1)概要说明：为实现上述程序功能，我们利用栈的数据结构，首先新建一个字符型栈，依次读入目标.htm文件的字符，当遇到左标签符“”时，后面的内容写入新文件new.htm中，循环这个过程，当原文件结束时，得到去除tag符的新文件new.htm。(2)程序主要模块 主要模块有：头文件、栈定义及栈函数、实现读取与写入非tag内容操作的主函数 InitStack(&S) 操作结果：构造一个空栈S。 Push(&S，e) 初始条件：栈S已存在。 操作结果：插入元素ch为新的栈顶元素。1.栈定义及栈函数：用结构体定义栈，并实现对栈的以下操作：构造栈、入栈2.实现读取与写入非tag内容操作的主函数：这一步借助C+的文件流实现，定义两个文件流，人流与出流，入流读取.htm文件，做完入栈操作到了非tag内容时将字符写入new.htm文件中。3 实验总结 上次实验是对栈的初次计算机程序实现，需要的栈操作也更多，而这次可以说是对栈操作的一次熟练。需要注意的就是实验之前需要将需要读取的文件放在程序目录下以便读取，结果文件是同样目录下的new.htm，可以用记事本打开查看。还有一点美中不足的就是，.htm文件通常在开头会包括很多设置性语句，如语句atext-decoration:none; color:#FFF; font-size:16px; font-family:微软雅黑;position:relative; float:left; display:block;用来设置字体，当前实现的程序没有考虑这种问题。与实验一相同，程序的界面化、可交互也是没有完全实现的问题，问题在于edit控件无法显示.htm文件中的中文字符，会显示乱码，而这样做的好处在于可以不用管待读取文件的目录问题，可以在对话框中选择路径。4 附1：程序清单#define OK 1#define ERROR 0#define OVERFLOW -1#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#include / 输入输出需要#include using namespace std;/结构体部分typedef int Status; typedef structchar *base;char *top;int stacksize;SqStack;Status InitStack(SqStack &S)S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!S.base) exit (OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStackStatus Push(SqStack &S,char e)/插入元素e为新的栈顶元素if(S.top-S.base=S.stacksize) /栈满，追加存储空间S.base=(char*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;/if*S.top+=e;return OK;/Pushint main()SqStack label;InitStack(label); char c;ifstream in;in.open(index.htm); / 待读取文件if (!in)coutcannot open old file.;return 1;ofstream out;out.open(new.htm); / 去除tag文件if (!out)coutcannot open new file.;return 1;in.get(c);while (in) while (c=) Push(label,c);in.get(c);Push(label,c);in.get(c);if (in) out.put(c);in.get(c);in.close();out.close();return 0;5 附2：运行结果分别对实验简介中的两个.htm文件做测试：(一）qingtianzhe的个人主页atext-decoration:none; color:#FFF; font-size:16px; font-family:微软雅黑;position:relative; float:left; display:block;.nav background-color:#000; overflow:hidden; height:50px;a:hover border-bottom:5px solid #09F; font-size:18px; font-family:迷你简菱心;.navbox width:610px; margin:auto;.navbox amargin:15px 20px; padding-bottom:12px;qingtianzhe的个人主页.qingtianzhe的个人主页 . . . 基本信息 作品 兴趣爱好 足迹 学习生活 我的非诚勿扰如下图：（二）学院主页：由于文件较长，只给出部分截图：去除tag前去除tag后：上机实验三1 上机实验简介1）实验目的设计一程序，先随机产生10000个整数(分别小于100000)，然后分别使用选择排序、希尔排序、快速排序方法对其进行排序，再比较一下三种方法进行排序时的性能差异。2）开发工具C+语言，Microsoft Visual C+ 6.0开发软件3）测试数据2 算法说明(1)概要说明：需要实现的操作有：先随机产生10000个整数(分别小于100000)；分别做选择排序、希尔排序与快速排序；计算各个排序所花时间。(2)程序主要模块 主要模块有：头文件、三种排序函数实现、随机生成数组、分别排序并记时。1.int *SelectSort(int *s,int n) /选择排序，排序数组s，n为数组长度void ShellInsert(int *s,int dk,int n)/对顺序表做一趟希尔排序，增量为dk，选取的dk=pow（2，t-k+1）int *ShellSort(int *s,int *dk,int t,int n) /按增量序列对顺序表做希尔排序int Partition(int *s,int low,int high) /交换顺序表s中子表记录，枢轴记录到位，返回其所在位置int *QSort(int *s,int low,int high)/对顺序表s中子序列做快速排序2.生成随机数组使用rand函数与srand函数3.记录时间使用头文件中的clock_t类 4.利用c+的ofstream文件流将随机数组与排序后数组分别写入txt文件中，data.txt文件为生成的随机数组数据；selectsort_data.txt存放选择排序后数据；shellsort_data.txt与quicksort_data.txt分别存放希尔排序与快速排序数据。3 实验总结 这次实验主要是实现了三种排序方法，由最后的运行时间来看，希尔排序耗时最少，效率最高，这是因为选用的“增量”序列较好。快速排序的结果不是很令人满意，分析原因可能主要是交换次数太多浪费了时间。至于改进的方面主要的依然是程序的交互性不好，dos界面不是特别人性化。4 附1：程序清单#include #include #include #include #include #include #include using namespace std;int *SelectSort(int *s,int n) /选择排序，排序数组s，返回ss，n为数组长度 int tmp;for (int i=0;in;i+)for (int j=i+1;jsj)tmp=sj;sj=si;si=tmp;return s;void ShellInsert(int *s,int dk,int n) /对顺序表做一趟希尔排序，增量为dk int tmp;for (int i=dk;in;i+)if (si=0 & tmpsj;j-=dk)sj+dk=sj;sj+dk=tmp;int *ShellSort(int *s,int *dk,int t,int n) /按增量序列对顺序表做希尔排序for (int k=0;kt;+k)ShellInsert(s,dkk,n);return s;int Partition(int *s,int low,int high) /交换顺序表s中子表记录，枢轴记录到位，返回其所在位置int tmp=slow;int piv=slow;while (lowhigh)while (low=piv)high-; slow=shigh;while (lowhigh & slow=piv) low+; shigh=slow;slow=tmp;return low;int *QSort(int *s,int low,int high) /对顺序表s中子序列做快速排序int pivt;if (lowhigh) pivt=Partition(s,low,high);QSort(s,low,pivt-1);QSort(s,pivt+1,high);return s;int main()int n;cout输入需要随机生成数个数n：n;int *s=new intn,i=0;ofstream fout(data.txt);if (!fout)coutcant open fileendl;for (i=0;in;i+)srand(i);si=rand()%n+1;foutsi ;fout.close(); /选择排序 clock_t ss_time_start=cl