数据结构课程实习报告

课程名称：指导老师：学生姓名：班级：学号：实习题一1.需求规格说明【问题描述】大数运算——计算n的阶乘（n大于等于20）【基本要求】数据的表示和存储：累积运算的中间结果和最终的计算结果的数据类型要求是整型，试设计合适的存储结构，要求每个元素或结点最多存储数据的3位数值。数据的操作及其实现：基于设计的存储结构实现乘法操作，要求从键盘上输入n值；在屏幕上显示最终计算结果。2.总体分析与设计【设计思想】因为大数的阶乘算出来的数值比较大，位数远远超过一个int或double行的位数，为了精确性的考虑，阶乘后的结果要用一种存储结构来存储并且累加和处理。所以要设计一个这样的数据结构实现对数据的存储，例如让每个存储单元只存储一部分的数值，在也运算的时候采用算数运算的进位方法来运算。【设计表示】抽象数据类型Chain{实例链表头指针操作Chain()：将链表头指针赋值为零；Delete(k,x)：删除第k个元素并且把它存在x中；Insert(k,x)：把x存到第k个节点；};定义一个ChainNode模板类来表示链表类的成员变量，其主要包含两个数据域，data和link，data表示节点的数值域，link表示链接域。然后在定义一个Chain类模板来表示要存储数据的数据类型包含first头指针和insert还有delete函数，insert用来添加节点，delete用来删除节点，first永远指向链表的头指针，以保存这个链表的完整性。在主函数中加一些代码来实现大数的阶乘过程中链表的操作，在进位时，如果没有高位，就insert一个节点并且将进位的数据插到生成的节点当中，当向高位进位的时候，如果有高位就将仅为的数值和原高位相加，判断是否需要在进位，循环上述判断。3.编码开始做的时候每一个节点中的数值运算不太好处理，毕竟不是int，乘法的时候进位的判断和加法，循环等十分复杂，判断语句很难实现好。解决方法就是调试了一个星期，把每个判断与循环做好注释，在跟踪的时候看哪个判断出了问题，在注意解决，这题还比较简单，所以比较好调。4.程序及算法分析在main函数开头输入运算阶乘的数据number，然后从2开始做乘法运算，如果超过10就向前进位，如果没有前节点就insert，如果有就加在前节点的data域上面，如果加了之后有大于10，就循环前面的步骤，然后将链表的数值一个个给数组，倒过来输出就是结果了。链表的insert是往前面插，所以输出的时候有点麻烦，所以我引进了一个中间的数组来帮助输出，要是做的链表是向后插的话就比较好输出，这是值得改进的。还有就是在main里写代码不是太好，所以吧那部分放到一个函数里就比较简洁了。体会是想清楚了控制判断，把程序写出来还是比较容易的。需要花时间、5.附录【代码】#includestdafx.h#includeiostream.htemplateclassTclassChain;templateclassTclassChainNode{//将chain声明为chainnode的友元以//使其访问chainnode的私有变量friendChainT;public:Tdata;ChainNodeT*link;};templateclassTclassChain{public:Chain(){first=0;}~Chain();ChainT&Delete(intk,T&x);ChainT&Insert(intk,constT&x);ChainNodeT*first;};templateclassTChainT::~Chain(){ChainNodeT*next;while(first){next=first-link;deletefirst;first=next;}}templateclassTChainT&ChainT::Delete(intk,T&x){//delete的实现ChainNodeT*p=first;if(k==1){first=first-link;}else{ChainNodeT*q=first;for(intindex=1;indexk-1&&q;index++){q=q-link;}p=q-link;q-link=p-link;}x=p-data;deletep;return*this;}templateclassTChainT&ChainT::Insert(intk,constT&x){//insert的实现if(k0){coutoutofbound!endl;}ChainNodeT*p=first;for(intindex=1;indexk&&p;index++){p=p-link;}if(k0&&!p){coutoutofbound!endl;}ChainNodeT*y=newChainNodeT;y-data=x;if(k){y-link=p-link;p-link=y;}else{y-link=first;first=y;}return*this;}intmain(intargc,char*argv[]){//i为临时变量total是表示和的大小//rest是看进位的数值大小inti=0,count=2,number,total,rest=0,j=0;intNO[100];//在最后要倒置是用到的临时数组coutEnteraNumber:endl;cinnumber;Chainintchain;chain.Insert(0,1);ChainNodeint*currentfirst=chain.first;//保存chain的first以免破坏chainfor(count=2;count=number;count++){while(currentfirst){total=(currentfirst-data)*count+rest;//total是当前节点的值大小从小到大乘//直到乘到输入数据numberrest=0;if(total9){//如果大于十取余currentfirst-data=total%10;rest=total/10;//rest表示取余后的大小if(!(currentfirst-link)){//如果没有上一节点，insertj++;i++;chain.Insert(i,0);}}else{//total小于10currentfirst-data=total;}currentfirst=currentfirst-link;}currentfirst=chain.first;rest=0;//清零，不然下次加的时候受上次运算的影响total=0;}currentfirst=chain.first;for(i=0;i=j;i++){NO[i]=currentfirst-data;//currentfirst只有有限个，不一定有100个！currentfirst=currentfirst-link;}//输出for(i=0;i=j;i++){coutNO[j-i];}coutendl;return0;}【输出】实习题二1.需求规格说明【问题描述】对一个合法的中缀表达式求值假设表达式只包含+，-，*，/四个双目运算符，并且运算符本身不具有二义性。【基本要求】1.正确的解释表达式；2.符合四则运算法则；3.输出后计算结果；2.总体分析与设计【设计思想】为每一个运算符设定一个优先级，然后根据输入的中序表达式将其变成后序表达式，在根据后序表达式求得表达式的值。【设计表示】抽象数据类型Stake{实例元素线性表，栈回底，栈顶操作IsEmpty（）：如果栈为空，返回true，否则回falseIsFull（）：如果栈满，返回true，否则返回falseTop（）：返回栈顶指针；Add（x）：向栈中加元素x;Delete（x）：删除栈顶元素存在x中；}顶点i的入度先写级函数，这里写的是level函数，传入的是操然后返回其优先级，左括号‘（’的优先级最大。设置为2，右括号‘）’和‘#’的优先级最小，设置为-1.在就是加法还有减法的优先级相同为0乘法和除法的优先级比加减法大为1.这是所有比较的依据，最基本的寒素，然后是比较函数，在入栈和出栈过程中频繁调用，其传入的是两个运算符（char型），然后调用level函数，判断其返回值的大小，如果前一个的优先级大就返回1，否则返回0，如果相等也返回0，但是如果传入的值有‘（’或‘）’，则再加特殊判断。然后是后续表达式函数，这里是postpix函数。将用户输入的字符型数组传入，然后将后续表达式的数组传出。中间根据栈的一系列特性和运算符优先级关系进行出栈和入栈操作，最后保存在结果数组中。最后一步就是将后续表达式传入计算函数这里是calculate函数，将后续表达式也通过运算和栈操作实现计算值的功能。在详细设计表示主要讲calculate函数和postpix函数，postpix函数有两个传入参数，charstr[]和charstrResult[]，其中前者是用户输入的数组，后者是需要得到的结果后缀表达式数组。首先在自定义的栈中压入‘#’，因为开始的时候栈中是没有符号的，也就没有优先级的分别，这里把‘#’压倒里面去就是为了后面可以比较符号优先级。然后优先级高的压栈，优先级低的直接放到结果数组中，如果是数字也是直接放到结果数组中。如果有括号，出栈或者入栈但是不放到结果数组中，因为他们不需要操作。这样就得到了后缀表达式。Calculata则是一个根据得到的后缀表达式求值的函数，其函数参数是后缀表达式和一个浮点数的变量的引用。在strResult传入函数中去之后将结果保存在result中，当然，在用这个函数的时候是要在函数体外声明这样一个参数的。然后从左到右依次扫描表达式的个单词，如果是操作数，存入栈中，如果是运算符，就提取前面的两个操作数（从栈中弹出两个数）进行运算，中间结果同样存入栈中作为下一个运算的操作数。如此反复直到表达式处理完毕。3.编码计算器做起来比较复杂，我做了将近两个星期才做好。主要是calculate函数和postpix函数。在ppt上面的基础上想好思路倒是不难，但是实现起来总会不如意，这时候调试的功能就来了，也是在这一次我真正开始调试，因为每次总要先看看栈顶的东西是什么。所以根据调试来发现错误是解决这一个题目的关键，我认为。在发现了栈顶的错误跟if判断的局限性之后才好改动compare函数和level函数。所以最终这题是调试出来的。4.程序及算法分析使用的时候输入要求的算式的中缀表达式，然后就按回车键，屏幕上就可以输出计算得到的后缀表达式和计算的结果。虽然在大多数情况下可以正常输出，但是，总有一些时候他得不到正确的结果。就是表明这个程序并不是稳定的。有出错的可能，像这样的不完整的程序是比较危险的。但由于时间和精力有限。我到现在只能调试到这个地步。在此基础上仍有很大的提升空间。开始的时候我是想用MFC做的。但是太麻烦加上时间也不够。就只能退而求其次。如果有时间我回继续做的。【代码】intlevel(chara){//level函数，返回某个操作符的优先级intlevelresult=-2;switch(a){case'+':levelresult=0;break;case'-':levelresult=0;break;case'*':levelresult=1;break;case'/':levelresult=1;break;case'(':levelresult=2;break;case')':levelresult=-1;break;case'#':levelresult=-1;break;default:coutlevelerror!endl;//优先级错误}returnlevelresult;//返回优先级}intcompare(chara