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

《数据结构课程实习报告(共36页).doc》由会员分享，可在线阅读，更多相关《数据结构课程实习报告(共36页).doc（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上 课程名称： 指导老师： 学生姓名： 班 级： 学 号： 实习题一1. 需求规格说明【问题描述】 大数运算计算n的阶乘（n大于等于20）【基本要求】 数据的表示和存储：累积运算的中间结果和最终的计算结果的数据类型要求是整型，试设计合适的存储结构，要求每个元素或结点最多存储数据的 3 位数值。 数据的操作及其实现： 基于设计的存储结构实现乘法操作，要求从键盘上输入n 值；在屏幕上显示最终计算结果。2. 总体分析与设计【设计思想】 因为大数的阶乘算出来的数值比较大，位数远远超过一个int或double行的位数，为了精确性的考虑，阶乘后的结果要用一种存储结构来存储并且累加和

2、处理。所以要设计一个这样的数据结构实现对数据的存储，例如让每个存储单元只存储一部分的数值，在也运算的时候采用算数运算的进位方法来运算。【设计表示】抽象数据类型 Chain实例 链表头指针操作Chain()：将链表头指针赋值为零；Delete(k, x)：删除第k个元素并且把它存在x中；Insert(k, x)：把x存到第k个节点；; 定义一个ChainNode模板类来表示链表类的成员变量，其主要包含两个数据域，data和link，data表示节点的数值域，link表示链接域。然后在定义一个Chain类模板来表示要存储数据的数据类型包含first头指针和insert还有delete函数，inse

3、rt用来添加节点，delete用来删除节点，first永远指向链表的头指针，以保存这个链表的完整性。 在主函数中加一些代码来实现大数的阶乘过程中链表的操作，在进位时，如果没有高位，就insert一个节点并且将进位的数据插到生成的节点当中，当向高位进位的时候，如果有高位就将仅为的数值和原高位相加，判断是否需要在进位，循环上述判断。3. 编码开始做的时候每一个节点中的数值运算不太好处理，毕竟不是int，乘法的时候进位的判断和加法，循环等十分复杂，判断语句很难实现好。解决方法就是调试了一个星期，把每个判断与循环做好注释，在跟踪的时候看哪个判断出了问题，在注意解决，这题还比较简单，所以比较好调。4.

4、程序及算法分析在main函数开头输入运算阶乘的数据number，然后从2开始做乘法运算，如果超过10就向前进位，如果没有前节点就insert，如果有就加在前节点的data域上面，如果加了之后有大于10，就循环前面的步骤，然后将链表的数值一个个给数组，倒过来输出就是结果了。 链表的insert是往前面插，所以输出的时候有点麻烦，所以我引进了一个中间的数组来帮助输出，要是做的链表是向后插的话就比较好输出，这是值得改进的。还有就是在main里写代码不是太好，所以吧那部分放到一个函数里就比较简洁了。体会是想清楚了控制判断，把程序写出来还是比较容易的。需要花时间、5.附录【代码】#include std

5、afx.h#include iostream.htemplateclass Chain;templateclass ChainNode/将chain声明为chainnode的友元以/使其访问chainnode的私有变量friend Chain; public:T data;ChainNode* link; ;templateclass Chainpublic:Chain()first=0;Chain();Chain& Delete(int k,T& x);Chain& Insert(int k,const T& x);ChainNode* first;templateChain:Chain()

6、ChainNode* next;while (first)next=first-link;delete first;first=next;templateChain& Chain:Delete(int k,T& x)/delete的实现ChainNode* p=first;if (k=1)first=first-link;elseChainNode* q=first;for (int index=1;indexlink;p=q-link;q-link=p-link;x=p-data;delete p;return *this;templateChain& Chain:Insert(int k,

7、const T& x)/insert的实现if(k0)coutout of bound!endl;ChainNode *p=first;for(int index=1;indexlink;if(k0 &!p)coutout of bound!endl;ChainNode *y=new ChainNode;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,c

8、ount=2,number,total,rest=0,j=0;int NO100;/在最后要倒置是用到的临时数组coutEnter a Number:number;Chain chain;chain.Insert(0,1);ChainNode* currentfirst=chain.first;/保存chain的first以免破坏chainfor (count=2;countdata)*count+rest;/total是当前节点的值大小从小到大乘/直到乘到输入数据numberrest=0;if (total9)/如果大于十取余currentfirst-data=total%10;rest=t

9、otal/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;idata;/currentfirst 只有有限个，不一定有100个！currentfirst=cur

10、rentfirst-link; /输出for (i=0;i=j;i+)coutNOj-i;coutendl;return 0;【输出】实习题二1.需求规格说明【问题描述】 对一个合法的中缀表达式求值 假设表达式只包含+，-，*，/四个双目运算符，并且运算符本身不具有二义性。【基本要求】1. 正确的解释表达式；2. 符合四则运算法则；3. 输出后计算结果；2.总体分析与设计【设计思想】 为每一个运算符设定一个优先级，然后根据输入的中序表达式将其变成后序表达式，在根据后序表达式求得表达式的值。【设计表示】抽象数据类型 Stake 实例元素线性表，栈回底，栈顶操作 IsEmpty（）：如果栈为空，返

11、回true，否则回false IsFull（）：如果栈满，返回true，否则返回falseTop（）：返回栈顶指针；Add（x）：向栈中加元素x;Delete（x）：删除栈顶元素存在x中；顶点i的入度 先写级函数，这里写的是level函数，传入的是操然后返回其优先级，左括号（的优先级最大。设置为2，右括号）和#的优先级最小，设置为-1.在就是加法还有减法的优先级相同为0乘法和除法的优先级比加减法大为1.这是所有比较的依据，最基本的寒素，然后是比较函数，在入栈和出栈过程中频繁调用，其传入的是两个运算符（char型），然后调用level函数，判断其返回值的大小，如果前一个的优先级大就返回1，否则返

12、回0，如果相等也返回0，但是如果传入的值有（或），则再加特殊判断。然后是后续表达式函数，这里是postpix函数。将用户输入的字符型数组传入，然后将后续表达式的数组传出。中间根据栈的一系列特性和运算符优先级关系进行出栈和入栈操作，最后保存在结果数组中。最后一步就是将后续表达式传入计算函数这里是calculate函数，将后续表达式也通过运算和栈操作实现计算值的功能。 在详细设计表示主要讲calculate函数和postpix函数，postpix函数有两个传入参数，char str和char strResult，其中前者是用户输入的数组，后者是需要得到的结果后缀表达式数组。首先在自定义的栈中压入#

13、，因为开始的时候栈中是没有符号的，也就没有优先级的分别，这里把#压倒里面去就是为了后面可以比较符号优先级。然后优先级高的压栈，优先级低的直接放到结果数组中，如果是数字也是直接放到结果数组中。如果有括号，出栈或者入栈但是不放到结果数组中，因为他们不需要操作。这样就得到了后缀表达式。Calculata则是一个根据得到的后缀表达式求值的函数，其函数参数是后缀表达式和一个浮点数的变量的引用。在strResult传入函数中去之后将结果保存在result中，当然，在用这个函数的时候是要在函数体外声明这样一个参数的。然后从左到右依次扫描表达式的个单词，如果是操作数，存入栈中，如果是运算符，就提取前面的两个操

14、作数（从栈中弹出两个数）进行运算，中间结果同样存入栈中作为下一个运算的操作数。如此反复直到表达式处理完毕。3.编码计算器做起来比较复杂，我做了将近两个星期才做好。主要是calculate函数和postpix函数。在ppt上面的基础上想好思路倒是不难，但是实现起来总会不如意，这时候调试的功能就来了，也是在这一次我真正开始调试，因为每次总要先看看栈顶的东西是什么。所以根据调试来发现错误是解决这一个题目的关键，我认为。 在发现了栈顶的错误跟if判断的局限性之后才好改动compare函数和level函数。所以最终这题是调试出来的。4.程序及算法分析 使用的时候输入要求的算式的中缀表达式，然后就按回车键

15、，屏幕上就可以输出计算得到的后缀表达式和计算的结果。虽然在大多数情况下可以正常输出，但是，总有一些时候他得不到正确的结果。就是表明这个程序并不是稳定的。有出错的可能，像这样的不完整的程序是比较危险的。但由于时间和精力有限。我到现在只能调试到这个地步。在此基础上仍有很大的提升空间。开始的时候我是想用MFC做的。但是太麻烦加上时间也不够。就只能退而求其次。如果有时间我回继续做的。【代码】int level(char a)/level 函数，返回某个操作符的优先级int levelresult=-2;switch (a)case +:levelresult=0;break;case -:levelr

16、esult=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!b,返回1。否则返回0int level1=0;int level2=0;level1=level(a);level2=level(b);if (level1level2)return 1;else if (level1=level2)if (b=

17、) & a!=( )return 1;if (b=()return 1;return 0;coutcompare error!endl;/在比较中出现的错误return -1;/错误的比较void postfix(char str,char strResult)/变后缀表达式的函数/返回strresultStake stake; stake.Add(#);char temp;bool seprate=false;int i=0;for (;stri!=0;i+)if (stri=0 & stri=0 & stri+19)seprate=false;elsestrResultindex= ;in

18、dex+;/优先级大的压栈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.To

19、p()=)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 numberstake;int

20、i=0;double tempa,tempb,tempc, waste;char *temp;temp=new char ;for (;i=0 & strResulti=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

21、(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=*)/如果是*就把栈顶两个数的积压入栈中temp

22、a=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 i

23、f (strResulti= )/numberstake的栈顶就是结果result=numberstake.Top();int main(int argc, char* argv)int i=0;char *str,*strResult;str=new char ;strResult=new char ;cinstr;postfix(str,strResult);for (;iindex;i+)coutstrResulti;coutendl;double result;calculate(strResult,result);coutresultendl;return 0;【输出】实习题三1.需

24、求规格说明【问题描述】 以二叉链表作为二叉树的存储结构建立二叉树，并对其进行操作，基本功能要求： （1）建立一棵二叉树； （2 ）对该二叉树进行前序、中序、后序、层序遍历； （3）统计该二叉树叶子结点的个数。 （4 ）求二叉树的深度。 （5）用非递归方法实现二叉树的中序遍历。【基本要求】从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并 采用递归算法对其进行遍历（先序、中序、后序）、统计叶节点个数、求二叉树的深度并用 非递归方法实现二叉树的中序遍历和层序遍历，将结果打印输出，。2.总体分析与设计【设计思想】 建立BinaryTree类，并且在类中声明数据成员和函数成

25、员，其中数据成员包括树的根节点，函数成员包括前序遍历，中序遍历和后续遍历，层序遍历。共有函数包括得到叶子节点函数和判等函数和改变叶子函数。实现对二叉树的操作。【设计表示】 抽象数据类型 BinaryTree实例根节点操作 Creat（）：创建一个空的二叉树； IsEmpty（）：如果二叉树为空，返回true，否则返回false； Root（x）：取x为根节点，如果操作失败，返回false否则返回true；Creat：创建树； PreOrder：前序遍历；InOrder：中序遍历；PostOrder：后续遍历；LevelOrder：层序遍历；Visit：访问树节点值；GetLeaveCount：

26、得到树的叶节点数； Same：判断两棵树是否相等； ChangeTreeNode：改变树的叶节点； ChangeTree：改变整个树的叶节点 首先在main函数中声明一个char型树，然后调用creat函数，如果输入不是#就往树里面插，左子树插完了就往右边插。直到插满为止。树的高度计算就是不断的往左子树走和往右子树走，走一步就+一下，最后看谁最大，把最大的作为高度。前序遍历，中序遍历，后续遍历是用递归算法。层序遍历利用了队列操作。比较两个树是否相等的函数Same有两个参数，两个树的根节点的指针，递归调用这函数，一旦有一个节点的值不一样就return false；否则return true；对于

27、得到叶子节点数的函数GetLeaveCount有两个参数就是这棵树的根节点和树的叶子节点树的int参数的引用，然后可以递归该函数并且没有左孩子和右孩子就count+。最后count就有叶子节点的数了。3.编码 其实这题挺简单的，当然是现在看来，但是这题的代码是自己加最多的，好多函数的实现都是自己想的。其他后面几题都是书上的代码。这题的遍历操作基本没有问题，主要是换节点和计算节点数目比较烦，但是实现起来也是比好的。调试也没有话太多时间。4.程序及算法分析类声明： template class BinaryTreeNodefriend void Visit(BinaryTreeNode*);fri

28、end class BinaryTree;public:BinaryTreeNode()LeftChild=RightChild=0;BinaryTreeNode(const T& e,BinaryTreeNode* l,BinaryTreeNode* r)data=e;LeftChild=l;RightChild=r;T data; /根数据BinaryTreeNode* LeftChild; /指向左子树指针BinaryTreeNode* RightChild; /指向右子树指针;templateclass BinaryTreepublic:BinaryTree()root=0;Binar

29、yTree()bool IsEmpty()constreturn (root)? false:true);bool Root(T& x)const;void MakeTree(const T& element,BinaryTree& left,BinaryTree& right);BinaryTreeNode* Creat();int Height(BinaryTreeNode* t)const;void PreOrder(void (*Visit)(BinaryTreeNode* u)PreOrder(Visit,root);void InOrder(void (*Visit)(Binary

30、TreeNode* u)InOrder(Visit,root);void PostOrder(void (*Visit)(BinaryTreeNode* u)PostOrder(Visit,root);void LevelOrder(void(*Visit)(BinaryTreeNode *u); void PreOrder(void (*Visit)(BinaryTreeNode* u),BinaryTreeNode* t);void InOrder(void (*Visit)(BinaryTreeNode* u),BinaryTreeNode* t);void PostOrder(void

31、 (*Visit)(BinaryTreeNode* u),BinaryTreeNode* t);BinaryTreeNode* root;int main(int argc, char* argv)BinaryTree tree;BinaryTreeNode* treeroot=tree.Creat();int leaveNO=0;GetLeaveCount(treeroot,leaveNO);tree.root=treeroot;cout高度：endl;couttree.Height(treeroot); cout前序;tree.PreOrder( Visit,treeroot);coute

32、ndl;cout后序;tree.PostOrder(Visit,treeroot);coutendl;cout中序;tree.InOrder(Visit,treeroot);coutendl;cout层序;tree.LevelOrder(Visit);coutendl;tree.PreOrder( ct,treeroot);cout节点总数：countendl;cout叶子节点：leaveNOendl;cout非叶子节点：count-leaveNOendl;cout * 节点变换后 * endl; count=0; ChangeTreefunction(tree);leaveNO=0;GetL

33、eaveCount(treeroot,leaveNO);cout高度：;couttree.Height(treeroot); cout前序;tree.PreOrder( Visit,treeroot);coutendl;cout后序;tree.PostOrder(Visit,treeroot);coutendl;cout中序;tree.InOrder(Visit,treeroot);coutendl;cout层序;tree.LevelOrder(Visit);coutendl;tree.PreOrder( ct,treeroot);cout节点总数：countendl;cout叶子节点：lea

34、veNOendl;cout非叶子节点：count-leaveNOendl;cout * 判断两棵树 * endl;cout再输一个树endl; BinaryTree tree2;BinaryTreeNode* tree2root=tree2.Creat();coutSame(treeroot,tree2root);return 0;templatevoid ChangeTreefunction(BinaryTree t)/改变孩子节点的顺序/调用子函数PreOrder和ChangeTreeNodeif(t.root-LeftChild & t.root-RightChild)t.PreOrde

35、r(ChangeTreeNode,t.root);templatevoid ChangeTreeNode(BinaryTreeNode* t)/被ChangeTreefunction调用/做前序遍历的visitT temp;if (t-LeftChild & t-RightChild)temp=t-LeftChild-data;t-LeftChild-data=t-RightChild-data;t-RightChild-data=temp;templatebool Same(BinaryTreeNode* t0,BinaryTreeNode* t1)/判断两颗树是否相等/用递归连续调用if

36、(!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;templatevoid GetLeaveCount(BinaryTreeNode* t,int& count)/得到叶子节点数/如果左孩子和右孩子都没有就count+if (!t)return ;if (!t-LeftChild & !t-RightChild)