大整数加法实验报告
幽默搞笑-孔雀东南飞全文
实验报告
题目：大整数加法
班级：计算机111班
姓名：XXX 学号：11136103 完成日期：2012.04.12
一、
目的与要求
1、线性表的链式存储结构及其基本运算、实现方法和技术的训练。
2、单链表的简单应用训练
3、熟悉标准模版库STL中的链表相关的知识
二、 需求分析
1、本实验要求实现线性表的链式储存及其相应操作，而这也是解决大整数加法
的基础。 2、对于给出的两个大整数，若要对其进行加法（或减法运算），可以先将两个大
整数用线性表的链
式储存起来，再对其进行运算。
三、 概要设计
1、线性表的抽象数据类型定义
ADT List {
数据对象：D＝{ ai | ai
∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：R1＝{
{设线性表为（a1，a2，…，ai，…，an），称i为ai在线性表
中的位序。}
基本操作：
InitList(&L)
操作结果：构造一个空的线性表L。
DestroyList(&L)
初始条件：线性表L已存在。
操作结果：销毁线性表L。
ClearList(&L)
初始条件：线性表L已存在。
操作结果：将线性表L重置为空表。
PriorElem(L，cur_e,&pre_e) (求元素前驱)
初始条件：线性表L 已存在。
操作结果：若 cur_e
是L的元素，但不是第一个，则用pre_e 返回它的前驱，
否则操作失败，pre_e无定义。
NextElem( L, cur_e, &next_e ) （求元素后继）
初始条件：线性表 L 已存在。
操作结果：若 cur_e 是 L
的元素，但不是最后一个，则用 next_e 返回它的后
继，否则操作失败，next_e无定义。
LocateElem( L, e, compare( ) ) （定位函数）
初始条件：线性表 L 已存在，e 为给定值，compare( )是元素判定函数。
操作结果： 返回 L 中第 1 个与 e 满足关系 compare(
)的元素的位序。若元
素不存在，返回0。
GetElem( L, i, &e
) （求线性表中某个元素）
初始条件：线性表 L 已存在，且
1≤i≤LengthList(L)
操作结果：用 e 返回 L 中第 i 个元素的值。
PutElem( &L, i, e ) （改变数据元素的值）
初始条件：线性表 L 已存在，且 1≤i≤LengthList(L) 。
操作结果：L 中第 i 个元素赋值同 e 的值。
} ADT List
2、主程序的处理流程
int main(){
线性表初始化；
读入大整数序列 n；
if(!(cin>>n)) break； ；
进行加（减）运算；
输出结果；
return 0;
}
四、详细设计
1线性表的实现（链式结构）
struct LNode{
定义节点
int data;
LNode *next;
};
struct LinkList 单链表的基本操作
{
LNode *head,*tail;
void Init(); 初始化
void Clear(); 链表清空
void Create(int n);
创建链表
int Locate(int e); 查找元素 e 在链表中的位子
bool InsertBefore(int i,int e); 在位子 i 之前插入元素 e
bool Delete(int i); 删除 i 位子的元素
void
Traverse(); 遍历输出
bool Empty(); 判断单链表是否为空
};
void LinkList::Init(){
head=new
LNode;
head->next=NULL;
}
void
LinkList::Create(int n){
tail=head;
for(int i=0;i
LNode *p=new
LNode;
cin>>p->data;
p->next =NULL;
tail->next =p;
tail=p;
}
}
int LinkList::Locate(int e){
int i=1;
LNode *p=head->next;
while(p!=NULL) {
if(p->data==e) break;
else {
p=p->next;
i++;
}
}
if(p==NULL) return 0;
else return i;
}
bool LinkList::Delete(int i){
LNode *p=head;
while(i>1&&p->next!=NULL){
p=p->next
i--;
}
if(i<1||p->next ==NULL) return false;
LNode *q=p->next;
p->next =p->next->next;
delete q;
}
bool
LinkList::InsertBefore(int i,int e){
LNode
*p=head;
while(i>1 && p->next!=NULL) {
p=p->next;
i--;
}
if(p->next
==NULL || i<1) return false;
LNode *q=new
LNode;
q->data=e;
q->next=p->next;
p->next=q;
return true;
}
void
LinkList::Traverse(){
LNode *p=head->next;
while(p!=NULL){
cout<
if(p->next !=NULL) cout<<
p=p->next
}
cout<
2、利用单链表储存大整数
（大整数的位数不限）
Void（） 将大整数保存在 lt 中
{
string s;
cin>>s;
LinkList lt;
();
for(int j=()-1;j>=0;j--)
{
Before(1,s[j]-'0');
}
}
bool
run(){
LinkList lst;
int n,cnt=0;
if(!(cin>>n)) return false;
();
(n);
LNode *p=;
se ();
Before(1,5);
se ();
(3);
se ();
cout<<(3)<
}
3、利用单链表实现两个大整数的相加、相减运算（减法运算可选做）
LinkList
BigAdd(LinkList lt1,LinkList lt2)
it1，it2为单链表储存
的大整数
{
LinkList lt;
();
LNode *p1=->next;
LNode
*p2=->next;
int carry=0;
while(p2!=NULL){
int
k=p1->data+p2->data+carry;
p1->data=k%10;
carry=k10;
p1=p1->next; p2=p2->next;
}
if(p1!=NULL)p1->data+=carry;
else
if(carry>0){
LNode *n=new LNode;
n->data=carry;
n->next=p1->next;
p1->next=n;
}
p1=->next;
p2=;
while(p1!=NULL){
Before(1,p1->data);
p1=p1->next;
}
return lt;
}
Void run(){
string s,t;
cin>>s>>t;
LinkList lt1,lt2;
();
();
if(()<()) swap(s,t);
for(int
j=0;j<();j++){
Before(1,s[j]-'0');
Before(1,t[j]-'0');
}
for(int i=();i<();i++)
Before(1,s[i]-'0');
LinkList
lt=BigMinus(lt1,lt2);
se();
}
4
、
用STL之stack完成上面的任务。
#include
struct LNode{int
data;};
list
list
list
list
it1=();
it2=();
int carry=0;
while(it2!=()){
int k=it1->data+carry+it2->data;
it1->data=k%10; carry=k10;
it1++; it2++;
}
if(it1!=()) it1->data+=carry;
else
if(carry>0){
LNode n;
=carry;
_front(n);
}
it1=();
while(it1!=()){
_front(*it1); it1++;
}
return
lt;
}
void Traverselist(){
list
while(it!=()){
cout<
}
cout<
bool run()
{
string s,t;
cin>>s>>t;
list
if(s
for(int j=0;j<();j++){
=s[j]-'0'; =t[j]-'0';
_front(t1); _front(t2);
}
for(int i=();i<();i++){
=s[i]-'0';
_front(t1);
}
Lt=BigAdd(lt1,lt2);
Traverselist();
return true;
}
5
、
尝试完成 HLoj 1020。
#include
#include
#include
using namespace
std;
const int MaxLen = 1000;
const int DIGIT = 4;
const int MOD =
10000;
typedef int BigInt[MaxLen];
void give(BigInt a, BigInt& b)
{
int i = 0;
while(i<=a[0])
{
b[i] =
a[i];
i++;
}
}
void give(int a, BigInt& b){
b[1] = a%MOD;
a = MOD;
int pos=2;
while(a>0)
{
b[pos++] = a%MOD;
a =
MOD;
}
b[0]=pos-1;
}
void BigAdd(BigInt a, BigInt b, BigInt& c)
{
int i,carry=0;
for
(i=1; i<=a[0] || i<=b[0] || carry>0; i++)
{
if(i<=a[0]) carry += a[i];
if(i<=b[0]) carry += b[i];
c[i] = carry%MOD;
carry = MOD;
}
c[0] = i-1;
}
void output(const BigInt a){
printf(
for (int i=a[0]-1; i>0; i--)
{
for(int j=MOD10; j>0;
j=10)
{
printf(
}
}
}
BigInt F[1001];
int main()
{
int T;
cin>>T;
give(1,F[1]);
give(1,F[2]);
for(int i=3; i<1001; i++)
{
BigAdd(F[i-1],F[i-2],F[i]);
}
for(int t=0; t
int n;
cin>>n;
output(F[n]);
cout<
return 0;
}
五、调试分析
⑴时间复杂度：（3n）（n为最大大整数的长度）
⑵经验和体会：大整数的加法或减法可
以通过用不同的储存结构对其进行存储再
运算得到（可以推广到其他问题）
五、测试结果
测试通过