数据结构课程实习报告.doc

《数据结构课程实习报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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头指针和i

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

4、好注释，在跟踪的时候看哪个判断出了问题，在注意解决，这题还比较简单，所以比较好调。2.程序及算法分析在main函数开头输入运算阶乘的数据number，然后从2开始做乘法运算，如果超过10就向前进位，如果没有前节点就insert，如果有就加在前节点的data域上面，如果加了之后有大于10，就循环前面的步骤，然后将链表的数值一个个给数组，倒过来输出就是结果了。链表的insert是往前面插，所以输出的时候有点麻烦，所以我引进了一个中间的数组来帮助输出，要是做的链表是向后插的话就比较好输出，这是值得改进的。还有就是在main里写代码不是太好，所以吧那

5、部分放到一个函数里就比较简洁了。体会是想清楚了控制判断，把程序写出来还是比较容易的。需要花时间、5.附录【代码】#include"stdafx.h"#include"iostream.h"templateclassChain;templateclassChainNode{//将chain声明为chainnode的友元以//使其访问chainnode的私有变量friendChain;public:Tdata;ChainNode*link;};templateclassChain{pub

6、lic:Chain(){first=0;}~Chain();Chain&Delete(intk,T&x);Chain&Insert(intk,constT&x);ChainNode*first;};templateChain::~Chain(){ChainNode*next;while(first){next=first->link;deletefirst;first=next;}}templateChain&Chain::Delete(intk,T&x){//dele

7、te的实现ChainNode*p=first;if(k==1){first=first->link;}else{ChainNode*q=first;for(intindex=1;indexlink;}p=q->link;q->link=p->link;}x=p->data;deletep;return*this;}templateChain&Chain::Insert(intk,constT&x){//insert的实现if(k<0){cout<<"outof

8、bound!"<*p=first;for(intindex=1;indexlink;}