上机实习报告
班号： 116112
姓名： 李旭 学号： 20111003534
实习报告
【实习一】 线性表及其应用
n（n>20）的阶乘
【问题描述】 大数运算——计算n的阶乘（n>=20）。
【基本要求】
（1）数据的表示和存储: （1.1） 累积运算的中间结果和最终的计算结果的数据类型要求是整型——这是问题本身的要求；
（1.2）试设计合适的存储结构，要求每个元素或结点最多存储数据的3位数值。 （2）数据的操作及其实现：
基于设计的存储结构实现乘法操作，要求从键盘上输入n值，在屏幕上显示最终计算结果。
【问题分析】
（1）设计数据的存储结构：
介于乘运算的精确性以及实型数据表示的不精确性，本题不能采用实型表示累积运算的中间结果和最终的计算结果，而只能用整型。然而由于普通整型和长整型所能表述数的范围受其字长的限制，不能表示大数阶乘的累积结果，故必须设计一个合适的数据结构实现对数据的存储，例如可以让每个元素或结点存储数据的若干位数值。 从问题描述不难看出n值为任意值，故为使程序尽量不受限制，应采用动态存储结构。
累积运算的特点是当前的计算结果是下次乘法运算的乘数。 实现两个数的乘法运算须考虑：
（1）乘数的各位数都要与被乘数进行乘法运算；
（2）乘法过程中的进位问题及其实现；
（3）因每个元素或结点最多存储数据的3位数值，故当元素或结点中的数值大于
999，需向前一个元素或结点进位。
综合以上几点，我采用了单链表的储存结构形式。
（2）阶乘算法的实现： 1. 链表型数据乘法的具体实现描述：
（1）初始算法
顺序访问对每个节点上的数据乘以要乘的数后在顺序访问查看是否需要进位，
大于999则向前进位，如果前面没有节点则添加新节点储存进位的数
（2）改进算法 将原始算法的乘操作和进位操作合在一起进行，提高程序效率.
2. 数据输出算法具体实现描述
从高位向低位顺序输出节点上储存的数据，注意补零，最高位的节点不补，其它节点要补。对于最后的结果，因为我采用的是普通的单链表算法，因此我添加了
一个逆置的算法。
【算法实现的源代码】
1. 链表型数据乘法
void FacList::Fac(int n)//阶乘操作 { }
LinkNode *q=new LinkNode(1); first->link=q;
for(int i=1;i<=n;i++) { LinkNode *p=q; LinkNode *current; }
for(;p;p=p->link)
//声明一个指向头结点的指针
//对每一个节点中的数据乘以i
p->data=p->data*i;
for(LinkNode *p1=q;p1;p1=p1->link) { }
while(p1->data>=1000)//判断如果任何一个节点中的数据是否大于 { }
//如果大于则进位，并且保证所有节点数据皆小于
if(p1->link==NULL)
//如果节点数据大于且下一个节点为空则构造一个节点添加在其后 {
LinkNode *newNode=new LinkNode(0); //该节点中存放着数值0 p1->link=newNode;
} else;
//如果数据大于并且下一个节点可以储存数据
current=p1;
p1=p1->link;
p1->data=p1->data+current->data/1000;//进位后的下一个节点的数据 current->data=current->data00;
//进位后该节点的数据
output(first);
2. 数据输出算法
void FacList::output(LinkNode *current)//输出函数 { }
3. 逆置算法
LinkNode *FacList::ReverseList() {
if(first->link == NULL || first->link->link == NULL) { } else {
LinkNode *t = NULL, *p = first->link, *q = first->link->link; while(q != NULL)
{
t = q->link; q->link = p; p = q; q = t;
return first->link; //链表为空或只有一个元素则直接返回
current=current->link; }
ReverseList(); current=current->link; cout<
while (current!=NULL) { if (current->data>99&¤t->data<1000)//判断存储数据的大小 cout<
else if(current->data>9&¤t->data<100) cout<<\//如果是两位的，在数据前面加一个“0”输出 else cout<<\//如果是一位的，在数据前面加两个“0”输出
}
//此时q指向原始链表最后一个元素，也是逆转后的链表的表头元素
} }
first->link->link = NULL; //设置链表尾 first->link = p; //调整链表头 return first->link;
【测试数据】
（1）n=20，n！= 2432902008176640000
（2）n=25，n！=15511210043330985984000000 （3）n=30，n！=265252859812191058636308480000000
（4）n=40，n！=815915283247897734345611269596115894272000000000
【测试截图】
栈及队列的应用 【问题描述】 表达式求值。 【基本要求】
实现关键
栈的使用；
两位数以上、负数、小数点； 实现方式
控制台程序； MFC对话框；
【问题分析】
【实习二】 栈及队列的应用
百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典教育范文数据结构上机实习报告在线全文阅读。
相关推荐：
