数据结构课程实习报告(共36页).doc

精选优质文档-倾情为你奉上 课程名称： 指导老师： 学生姓名： 班 级： 学 号： 实习题一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.附录【代码】#include "stdafx.h"#include "iostream.h"template<class T>class Chain;template<class T>class ChainNode/将chain声明为chainnode的友元以/使其访问chainnode的私有变量friend Chain<T> public:T data;ChainNode<T>* link; ;template<class T>class Chainpublic:Chain()first=0;Chain();Chain<T>& Delete(int k,T& x);Chain<T>& Insert(int k,const T& x);ChainNode<T>* first;template<class T>Chain<T>:Chain()ChainNode<T>* next;while (first)next=first->link;delete first;first=next;template<class T>Chain<T>& Chain<T>:Delete(int k,T& x)/delete的实现ChainNode<T>* p=first;if (k=1)first=first->link;elseChainNode<T>* q=first;for (int index=1;index<k-1 && q;index+)q=q->link;p=q->link;q->link=p->link;x=p->data;delete p;return *this;template<class T>Chain<T>& Chain<T>:Insert(int k,const T& x)/insert的实现if(k<0)cout<<"out of bound!"<<endl;ChainNode<T> *p=first;for(int index=1;index<k && p;index+)p=p->link;if(k>0 &&!p)cout<<"out of bound!"<<endl;ChainNode<T> *y=new ChainNode<T>y->data=x;if(k)y->link=p->link;p->link=y;elsey->link=first;first=y;return *this;int main(int argc, char* argv)/i为临时变量total是表示和的大小/rest是看进位的数值大小int i=0,count=2,number,total,rest=0,j=0;int NO100;/在最后要倒置是用到的临时数组cout<<"Enter a Number:"<<endl;cin>>number;Chain<int> chain;chain.Insert(0,1);ChainNode<int>* currentfirst=chain.first;/保存chain的first以免破坏chainfor (count=2;count<=number;count+)while (currentfirst)total=(currentfirst->data)*count+rest;/total是当前节点的值大小从小到大乘/直到乘到输入数据numberrest=0;if (total>9)/如果大于十取余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+)NOi=currentfirst->data;/currentfirst 只有有限个，不一定有100个！currentfirst=currentfirst->link; /输出for (i=0;i<=j;i+)cout<<NOj-i;cout<<endl;return 0;【输出】实习题二1.需求规格说明【问题描述】 对一个合法的中缀表达式求值 假设表达式只包含+，-，*，/四个双目运算符，并且运算符本身不具有二义性。【基本要求】1. 正确的解释表达式；2. 符合四则运算法则；3. 输出后计算结果；2.总体分析与设计【设计思想】 为每一个运算符设定一个优先级，然后根据输入的中序表达式将其变成后序表达式，在根据后序表达式求得表达式的值。【设计表示】抽象数据类型 Stake 实例元素线性表，栈回底，栈顶操作 IsEmpty（）：如果栈为空，返回true，否则回false IsFull（）：如果栈满，返回true，否则返回falseTop（）：返回栈顶指针；Add（x）：向栈中加元素x;Delete（x）：删除栈顶元素存在x中；顶点i的入度 先写级函数，这里写的是level函数，传入的是操然后返回其优先级，左括号（的优先级最大。设置为2，右括号）和#的优先级最小，设置为-1.在就是加法还有减法的优先级相同为0乘法和除法的优先级比加减法大为1.这是所有比较的依据，最基本的寒素，然后是比较函数，在入栈和出栈过程中频繁调用，其传入的是两个运算符（char型），然后调用level函数，判断其返回值的大小，如果前一个的优先级大就返回1，否则返回0，如果相等也返回0，但是如果传入的值有（或），则再加特殊判断。然后是后续表达式函数，这里是postpix函数。将用户输入的字符型数组传入，然后将后续表达式的数组传出。中间根据栈的一系列特性和运算符优先级关系进行出栈和入栈操作，最后保存在结果数组中。最后一步就是将后续表达式传入计算函数这里是calculate函数，将后续表达式也通过运算和栈操作实现计算值的功能。 在详细设计表示主要讲calculate函数和postpix函数，postpix函数有两个传入参数，char str和char strResult，其中前者是用户输入的数组，后者是需要得到的结果后缀表达式数组。首先在自定义的栈中压入#，因为开始的时候栈中是没有符号的，也就没有优先级的分别，这里把#压倒里面去就是为了后面可以比较符号优先级。然后优先级高的压栈，优先级低的直接放到结果数组中，如果是数字也是直接放到结果数组中。如果有括号，出栈或者入栈但是不放到结果数组中，因为他们不需要操作。这样就得到了后缀表达式。Calculata则是一个根据得到的后缀表达式求值的函数，其函数参数是后缀表达式和一个浮点数的变量的引用。在strResult传入函数中去之后将结果保存在result中，当然，在用这个函数的时候是要在函数体外声明这样一个参数的。然后从左到右依次扫描表达式的个单词，如果是操作数，存入栈中，如果是运算符，就提取前面的两个操作数（从栈中弹出两个数）进行运算，中间结果同样存入栈中作为下一个运算的操作数。如此反复直到表达式处理完毕。3.编码计算器做起来比较复杂，我做了将近两个星期才做好。主要是calculate函数和postpix函数。在ppt上面的基础上想好思路倒是不难，但是实现起来总会不如意，这时候调试的功能就来了，也是在这一次我真正开始调试，因为每次总要先看看栈顶的东西是什么。所以根据调试来发现错误是解决这一个题目的关键，我认为。 在发现了栈顶的错误跟if判断的局限性之后才好改动compare函数和level函数。所以最终这题是调试出来的。4.程序及算法分析 使用的时候输入要求的算式的中缀表达式，然后就按回车键，屏幕上就可以输出计算得到的后缀表达式和计算的结果。虽然在大多数情况下可以正常输出，但是，总有一些时候他得不到正确的结果。就是表明这个程序并不是稳定的。有出错的可能，像这样的不完整的程序是比较危险的。但由于时间和精力有限。我到现在只能调试到这个地步。在此基础上仍有很大的提升空间。开始的时候我是想用MFC做的。但是太麻烦加上时间也不够。就只能退而求其次。如果有时间我回继续做的。【代码】int level(char a)/level 函数，返回某个操作符的优先级int levelresult=-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:cout<<" level error!"<<endl;/优先级错误return levelresult;/返回优先级int compare(char a,char b)/比较两个操作符的优先级大小/如果操作符a>b,返回1。否则返回0int level1=0;int level2=0;level1=level(a);level2=level(b);if (level1>level2)return 1;else if (level1<=level2)if (b=')' && a!='(' )return 1;if (b='(')return 1;return 0;cout<<"compare error!"<<endl;/在比较中出现的错误return -1;/错误的比较void postfix(char str,char strResult)/变后缀表达式的函数/返回strresultStake<char> stake; stake.Add('#');char temp;bool seprate=false;int i=0;for (;stri!=0;i+)if (stri>='0' && stri<'9')strResultindex=stri;index+;if (stri+1>='0' && stri+1<'9')seprate=false;elsestrResultindex=' 'index+;/优先级大的压栈else if (compare(stri,stake.Top()=1)stake.Add(stri);/优先级小的出栈else if (compare(stri,stake.Top()=0)if (stake.Top()='(')stake.Delete(temp); /stake.Delete(temp); /have stored ')'!strResultindex=stake.Top();stake.Delete(temp);index+;if (stake.Top()='(')stake.Delete(temp);stake.Add(stri);if(stake.Top()=')')stake.Delete(temp);while (!stake.IsEmpty() && stake.Top()!='#')char temp;if (stake.Top()='(' )stake.Delete(temp);if (stake.Top()=')')stake.Delete(temp);/得到结果数组strResultindex=stake.Top();/删除topstake.Delete(temp);index+;void calculate(char strResult,double& result)/计算函数/从结果数组求得最后的结果Stake<double> numberstake;int i=0;double tempa,tempb,tempc, waste;char *temp;temp=new char ;for (;i<index;i+)int j=0;if (strResulti>='0' && strResulti<='9' )while (j>=0)tempj=strResulti;j+;if (strResulti+1=' ')j=-1;if(strResulti+1!=' ')i+; /atof的参数是char型数组不是char型数组数据tempc=atof(temp); numberstake.Add(tempc); if (strResulti='+')/如果是+就把栈顶两个数的和压入栈中tempa=numberstake.Top();numberstake.Delete(waste);tempb=numberstake.Top();numberstake.Delete(waste);numberstake.Add(tempa+tempb);else if (strResulti='-')/如果是+就把栈顶两个数的余压入栈中tempa=numberstake.Top();numberstake.Delete(waste);tempb=numberstake.Top();numberstake.Delete(waste);numberstake.Add(tempb-tempa);else if (strResulti='*')/如果是*就把栈顶两个数的积压入栈中tempa=numberstake.Top();numberstake.Delete(waste);tempb=numberstake.Top();numberstake.Delete(waste);numberstake.Add(tempa*tempb);else if (strResulti='/')/如果是/就把栈顶两个数的商压入栈中tempa=numberstake.Top();numberstake.Delete(waste);tempb=numberstake.Top();numberstake.Delete(waste);numberstake.Add(tempa/tempb);else if (strResulti=' ')/numberstake的栈顶就是结果result=numberstake.Top();int main(int argc, char* argv)int i=0;char *str,*strResult;str=new char ;strResult=new char ;cin>>str;postfix(str,strResult);for (;i<index;i+)cout<<strResulti;cout<<endl;double result;calculate(strResult,result);cout<<result<<endl;return 0;【输出】实习题三1.需求规格说明【问题描述】 以二叉链表作为二叉树的存储结构建立二叉树，并对其进行操作，基本功能要求： （1）建立一棵二叉树； （2 ）对该二叉树进行前序、中序、后序、层序遍历； （3）统计该二叉树叶子结点的个数。 （4 ）求二叉树的深度。 （5）用非递归方法实现二叉树的中序遍历。【基本要求】从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并 采用递归算法对其进行遍历（先序、中序、后序）、统计叶节点个数、求二叉树的深度并用 非递归方法实现二叉树的中序遍历和层序遍历，将结果打印输出，。2.总体分析与设计【设计思想】 建立BinaryTree类，并且在类中声明数据成员和函数成员，其中数据成员包括树的根节点，函数成员包括前序遍历，中序遍历和后续遍历，层序遍历。共有函数包括得到叶子节点函数和判等函数和改变叶子函数。实现对二叉树的操作。【设计表示】 抽象数据类型 BinaryTree实例根节点操作 Creat（）：创建一个空的二叉树； IsEmpty（）：如果二叉树为空，返回true，否则返回false； Root（x）：取x为根节点，如果操作失败，返回false否则返回true；Creat：创建树； PreOrder：前序遍历；InOrder：中序遍历；PostOrder：后续遍历；LevelOrder：层序遍历；Visit：访问树节点值；GetLeaveCount：得到树的叶节点数； Same：判断两棵树是否相等； ChangeTreeNode：改变树的叶节点； ChangeTree：改变整个树的叶节点 首先在main函数中声明一个char型树，然后调用creat函数，如果输入不是#就往树里面插，左子树插完了就往右边插。直到插满为止。树的高度计算就是不断的往左子树走和往右子树走，走一步就+一下，最后看谁最大，把最大的作为高度。前序遍历，中序遍历，后续遍历是用递归算法。层序遍历利用了队列操作。比较两个树是否相等的函数Same有两个参数，两个树的根节点的指针，递归调用这函数，一旦有一个节点的值不一样就return false；否则return true；对于得到叶子节点数的函数GetLeaveCount有两个参数就是这棵树的根节点和树的叶子节点树的int参数的引用，然后可以递归该函数并且没有左孩子和右孩子就count+。最后count就有叶子节点的数了。3.编码 其实这题挺简单的，当然是现在看来，但是这题的代码是自己加最多的，好多函数的实现都是自己想的。其他后面几题都是书上的代码。这题的遍历操作基本没有问题，主要是换节点和计算节点数目比较烦，但是实现起来也是比好的。调试也没有话太多时间。4.程序及算法分析类声明： template <class T>class BinaryTreeNodefriend void Visit(BinaryTreeNode<T>*);friend class BinaryTree<T>public:BinaryTreeNode()LeftChild=RightChild=0;BinaryTreeNode(const T& e,BinaryTreeNode<T>* l,BinaryTreeNode<T>* r)data=e;LeftChild=l;RightChild=r;T data; /根数据BinaryTreeNode<T>* LeftChild; /指向左子树指针BinaryTreeNode<T>* RightChild; /指向右子树指针;template<class T>class BinaryTreepublic:BinaryTree()root=0;BinaryTree()bool IsEmpty()constreturn (root)? false:true);bool Root(T& x)const;void MakeTree(const T& element,BinaryTree<T>& left,BinaryTree<T>& right);BinaryTreeNode<T>* Creat();int Height(BinaryTreeNode<T>* t)const;void PreOrder(void (*Visit)(BinaryTreeNode<T>* u)PreOrder(Visit,root);void InOrder(void (*Visit)(BinaryTreeNode<T>* u)InOrder(Visit,root);void PostOrder(void (*Visit)(BinaryTreeNode<T>* u)PostOrder(Visit,root);void LevelOrder(void(*Visit)(BinaryTreeNode<T> *u); void PreOrder(void (*Visit)(BinaryTreeNode<T>* u),BinaryTreeNode<T>* t);void InOrder(void (*Visit)(BinaryTreeNode<T>* u),BinaryTreeNode<T>* t);void PostOrder(void (*Visit)(BinaryTreeNode<T>* u),BinaryTreeNode<T>* t);BinaryTreeNode<T>* root;int main(int argc, char* argv)BinaryTree<char> tree;BinaryTreeNode<char>* treeroot=tree.Creat();int leaveNO=0;GetLeaveCount(treeroot,leaveNO);tree.root=treeroot;cout<<"高度："<<endl;cout<<tree.Height(treeroot); cout<<"前序"tree.PreOrder( Visit,treeroot);cout<<endl;cout<<"后序"tree.PostOrder(Visit,treeroot);cout<<endl;cout<<"中序"tree.InOrder(Visit,treeroot);cout<<endl;cout<<"层序"tree.LevelOrder(Visit);cout<<endl;tree.PreOrder( ct,treeroot);cout<<"节点总数："<<count<<endl;cout<<"叶子节点："<<leaveNO<<endl;cout<<"非叶子节点："<<count-leaveNO<<endl;cout<<" * 节点变换后 * "<<endl; count=0; ChangeTreefunction(tree);leaveNO=0;GetLeaveCount(treeroot,leaveNO);cout<<"高度："cout<<tree.Height(treeroot); cout<<"前序"tree.PreOrder( Visit,treeroot);cout<<endl;cout<<"后序"tree.PostOrder(Visit,treeroot);cout<<endl;cout<<"中序"tree.InOrder(Visit,treeroot);cout<<endl;cout<<"层序"tree.LevelOrder(Visit);cout<<endl;tree.PreOrder( ct,treeroot);cout<<"节点总数："<<count<<endl;cout<<"叶子节点："<<leaveNO<<endl;cout<<"非叶子节点："<<count-leaveNO<<endl;cout<<" * 判断两棵树 * "<<endl;cout<<"再输一个树"<<endl; BinaryTree<char> tree2;BinaryTreeNode<char>* tree2root=tree2.Creat();cout<<Same(treeroot,tree2root);return 0;template<class T>void ChangeTreefunction(BinaryTree<T> t)/改变孩子节点的顺序/调用子函数PreOrder和ChangeTreeNodeif(t.root->LeftChild && t.root->RightChild)t.PreOrder(ChangeTreeNode,t.root);template<class T>void ChangeTreeNode(BinaryTreeNode<T>* t)/被ChangeTreefunction调用/做前序遍历的visitT temp;if (t->LeftChild && t->RightChild)temp=t->LeftChild->data;t->LeftChild->data=t->RightChild->data;t->RightChild->data=temp;template<class T>bool Same(BinaryTreeNode<T>* t0,BinaryTreeNode<T>* t1)/判断两颗树是否相等/用递归连续调用if (!t0 | !t1)/如果传入不好return false;while (t0->LeftChild && t1->LeftChild)if (t0->LeftChild->data!=t1->LeftChild->data)return false;Same(t0->LeftChild,t1->LeftChild);while (t0->RightChild && t1->RightChild)if (t0->RightChild->data!=t1->RightChild->data)return false;Same(t0->RightChild,t1->RightChild);return true;template<class T>void GetLeaveCount(BinaryTreeNode<T>* t,int& count)/得到叶子节点数/如果左孩子和右孩子都没有就count+if (!t)return ;if (!t->LeftChild && !t->RightChild)