数据结构
实验报告
实验题目： 班 级：
学 号： 姓 名： 完成日期：
一、需求分析
1. 问题描述（Problem Description）：
给定两个不超过10000位的非负整数A 和B, 计算出A+B的值。要求计算并输出A+B的值。
2. 根据实验任务的要求分析：
大整数要利用两个顺序表存储大整数，然后对存储于顺序表的两个大整数，根据数据加法的要求，通过对顺序表的操作，使两个大整数的和存储于顺序表，最后输出两个大整数的和，即输出经加发运算后“和”顺序表中的内容。 除了顺序表外，单链表也能达到一样的效果，编程大致也与顺序表相似，本次实验我们只用顺序表的思路来做。
（注：要正确输入2个大整数）
3. 测试数据总共有三组：
第一组
9和1
第二组
[**************]21和[***********]7654321
第三组
[***********][1**********]888
和[***********][***********]6666
4. 实验输出：
10
[***********]5308642
[***********][***********]5554
二、概要设计(数据类型的定义、算法思想、主程序和子程序(或功能) 模块的说明及各程序模块之间的层次(调用) 关系)
1. 顺序表的数据类型
根据题意定义一个Node 的指针指向这个结构体
struct Node
{
int data;
Node *next;
};
或者用string 类型字符串，来进行单链表的建立
typedef struct node
{ //动态链表的节点结构
int data;
node *next;
}*linklist;
2. 算法思想
第一步：
主函数中开始输入两个整数，用字符串的数据类型来接受输入的两个整数。（为了防止其整数位数可能超过整数数据类型可以存储的范围） 第二步：
对于存储在字符串里的整数，首先要建立一个只有头结点的空链表L ，可调用算法initlist_l完成，为了使新结点能够插入到表尾，需要增加一个尾指针r 指向链表的尾结点。
初始时，r 与L 均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点r 之后，然后使r 指向新的尾结点。
因此可以用前插法建立单链表的方法，依次根据字符串中从高位到低位的数值位，将整数存储于带头结点的单链表中，这时，为了方便加法的运算，从单链表的第一个结点到尾结点依次是：从个位到最高位的整数。
也可用后插法建立单链表的方法，依次根据字符串中从低位(字符串的右端) 到高位(字符串的左端) 的数值位，将整数存储于带头结点的单链表中。
以上过程可从前插法和后插法中选择其一进行链表的建立工作。（本人用了在这次实验中选择的是前插法）
第三步：
用一个Sum 的结构体对两个从单链表的第一个结点到尾结点依次是从个位到最高位存储的两个整数，从第一个结点开始，依次扫描到长度短的单链表的尾结点，每次把扫描到的两个结点中的数值及前面相加留下的进位相加，把和的个位存储到长度长的单链表对应的结点中，同时记录进位；然后把可能有
的进位依次与长单链表还未相加过的结点依次相加，若到最后一个结点相加后仍有进位，则要新增加一个结点，以存放进位。至此，两个整数的和已经存储在原来长的单链表中了。
第四步：对于已经存储好的和的单链表要先进行逆置，通过自己定义的一个Traverse 函数，将其单链表中结点的值输出。
第五步：在主函数中要设置相关的数据结构，以存放两个整数和单链表，输入两个整数后，依次可调用单链表初始化模块、建立单链表模块、两个整数相加模块、单链表逆置模块和输出单链表中结点的值的模块。中间可确定好较长整数所对应的单链表指针，以供两个整数相加模块使用。
3. 主程序
int main()
{
cin >> T;
for (int t = 0; t
{
string s1, s2;
cin >> s1 >> s2;//输入两个整数； Node *H1, *H2, *H3;
//调用相关结构体
H1 = Linkstring(s1);//确定较长整数的单链表；
H2 = Linkstring(s2);//确定较长整数的单链表；
H3 = Sum(H1, H2);//对2个结构体进行相加
Traverse(H3);//输出
}
return 0;
}
}
三、详细设计(实现概要设计中定义的数据类型，对主程序和其他模块写出算法，说明子模块的调用关系)
首先是对这次链表结构体的建立，同时在这个结构体中为了简化程序，在此整合了对链表输入的代码，让编程语句看起来更简练
Node* Linkstring(string s)
{
Node *head,*p;
head=new Node;
p=new Node;
head->next=NULL;
//在这里开始输入
int len=s.size(),i;
for(i=0;i
{ //这里使用的是前插法建立单链表结构体 p=new Node;
p->data=s[i]-'0'; //转换为整型
p->next=head->next;
head->next=p;
}
return head;
}
然后是本次实验的重点代码部分，Sum 函数来实现2个结构体的相加，其中H1，H2分别指向的是存放两个整数的单链表
Node* Sum(Node *H1,Node *H2)
{
Node *p=H1->next,*q=H2->next;
Node *head,*r;
head=new Node;
//指针指向两个整数单链表的头结点
r=new Node;
head->next=NULL;
int d=0;
while(p && q) //两个整数单链表均不空
{
r=new Node;
d+=p->data+q->data; //计算两个整数单链中的数值和进位的和 r->data=d%10; //开始记录进位
d=d/10;
r->next=head->next;//把和的个位存储于较长整数单链表的截点 head->next=r;
p=p->next; //开始各指针均向后移动一个结点
q=q->next;
}
//延续上面的思路，有进位且较长整数单链表不空的情况
while(p)
{
r=new Node;
d+=p->data;
r->data=d%10;
d=d/10;
r->next=head->next;
head->next=r;
p=p->next;
}
while(q)
{
r=new Node;
d+=q->data;
r->data=d%10;
d=d/10;
r->next=head->next;
head->next=r;
q=q->next;
}
if(d>0) //如果还有进位的话就开始做如下处理
{ // 较长整数单链表增加结点，存放最后的进位。
r=new Node;
r->data=d;
r->next=head->next;
head->next=r;
}
return head;
}
最后是输出函数Traverse
void Traverse(Node *head)
{
Node *q=head->next;
while(q)
{
coutdata;
q=q->next;
}
cout
}
四、调试分析(调试过程中遇到的问题是如何解决的、对设计与实现简要回顾或分析、经验和体会、经验和不足等，至少写三条)
回顾整个实验过程，大整数的加法可以通过用不同的储存结构对其进行存储再运算得到（可以推广到其他问题）。
而本次实验我试验了2种存储结构，即链式存储方式和顺序存储方式，对于用链表作为存储结构，感觉到这种方式可以适应不定长度的大数的好处。
唯一遗憾的就是没有进一步去研究其他的运算方式，如“减乘除”，或者更繁杂的开根号，N 次方等。以后有空余时间一定要去好好了解一下。
通过本次课程设计，我对大整数的理解和认识又有了进一步的提高，对之前学过的链表和顺序表的知识进行了一次复习巩固，更难得的是对这些理论知识进行了一次映像深刻的应用实践，通过同学间的交流，个人去图书馆或是网上的资料的查阅完成了本次数据结构的第一次的实验。只要有信心，不断努力就能够解决遇到的问题。
五、测试结果(列出测试数据和结果，说明是否通过测试
)
六、实验成绩(教师填写)
教师签名：
数据结构
实验报告
实验题目： 班 级：
学 号： 姓 名： 完成日期：
一、需求分析
1. 问题描述（Problem Description）：
给定两个不超过10000位的非负整数A 和B, 计算出A+B的值。要求计算并输出A+B的值。
2. 根据实验任务的要求分析：
大整数要利用两个顺序表存储大整数，然后对存储于顺序表的两个大整数，根据数据加法的要求，通过对顺序表的操作，使两个大整数的和存储于顺序表，最后输出两个大整数的和，即输出经加发运算后“和”顺序表中的内容。 除了顺序表外，单链表也能达到一样的效果，编程大致也与顺序表相似，本次实验我们只用顺序表的思路来做。
（注：要正确输入2个大整数）
3. 测试数据总共有三组：
第一组
9和1
第二组
[**************]21和[***********]7654321
第三组
[***********][1**********]888
和[***********][***********]6666
4. 实验输出：
10
[***********]5308642
[***********][***********]5554
二、概要设计(数据类型的定义、算法思想、主程序和子程序(或功能) 模块的说明及各程序模块之间的层次(调用) 关系)
1. 顺序表的数据类型
根据题意定义一个Node 的指针指向这个结构体
struct Node
{
int data;
Node *next;
};
或者用string 类型字符串，来进行单链表的建立
typedef struct node
{ //动态链表的节点结构
int data;
node *next;
}*linklist;
2. 算法思想
第一步：
主函数中开始输入两个整数，用字符串的数据类型来接受输入的两个整数。（为了防止其整数位数可能超过整数数据类型可以存储的范围） 第二步：
对于存储在字符串里的整数，首先要建立一个只有头结点的空链表L ，可调用算法initlist_l完成，为了使新结点能够插入到表尾，需要增加一个尾指针r 指向链表的尾结点。
初始时，r 与L 均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点r 之后，然后使r 指向新的尾结点。
因此可以用前插法建立单链表的方法，依次根据字符串中从高位到低位的数值位，将整数存储于带头结点的单链表中，这时，为了方便加法的运算，从单链表的第一个结点到尾结点依次是：从个位到最高位的整数。
也可用后插法建立单链表的方法，依次根据字符串中从低位(字符串的右端) 到高位(字符串的左端) 的数值位，将整数存储于带头结点的单链表中。
以上过程可从前插法和后插法中选择其一进行链表的建立工作。（本人用了在这次实验中选择的是前插法）
第三步：
用一个Sum 的结构体对两个从单链表的第一个结点到尾结点依次是从个位到最高位存储的两个整数，从第一个结点开始，依次扫描到长度短的单链表的尾结点，每次把扫描到的两个结点中的数值及前面相加留下的进位相加，把和的个位存储到长度长的单链表对应的结点中，同时记录进位；然后把可能有
的进位依次与长单链表还未相加过的结点依次相加，若到最后一个结点相加后仍有进位，则要新增加一个结点，以存放进位。至此，两个整数的和已经存储在原来长的单链表中了。
第四步：对于已经存储好的和的单链表要先进行逆置，通过自己定义的一个Traverse 函数，将其单链表中结点的值输出。
第五步：在主函数中要设置相关的数据结构，以存放两个整数和单链表，输入两个整数后，依次可调用单链表初始化模块、建立单链表模块、两个整数相加模块、单链表逆置模块和输出单链表中结点的值的模块。中间可确定好较长整数所对应的单链表指针，以供两个整数相加模块使用。
3. 主程序
int main()
{
cin >> T;
for (int t = 0; t
{
string s1, s2;
cin >> s1 >> s2;//输入两个整数； Node *H1, *H2, *H3;
//调用相关结构体
H1 = Linkstring(s1);//确定较长整数的单链表；
H2 = Linkstring(s2);//确定较长整数的单链表；
H3 = Sum(H1, H2);//对2个结构体进行相加
Traverse(H3);//输出
}
return 0;
}
}
三、详细设计(实现概要设计中定义的数据类型，对主程序和其他模块写出算法，说明子模块的调用关系)
首先是对这次链表结构体的建立，同时在这个结构体中为了简化程序，在此整合了对链表输入的代码，让编程语句看起来更简练
Node* Linkstring(string s)
{
Node *head,*p;
head=new Node;
p=new Node;
head->next=NULL;
//在这里开始输入
int len=s.size(),i;
for(i=0;i
{ //这里使用的是前插法建立单链表结构体 p=new Node;
p->data=s[i]-'0'; //转换为整型
p->next=head->next;
head->next=p;
}
return head;
}
然后是本次实验的重点代码部分，Sum 函数来实现2个结构体的相加，其中H1，H2分别指向的是存放两个整数的单链表
Node* Sum(Node *H1,Node *H2)
{
Node *p=H1->next,*q=H2->next;
Node *head,*r;
head=new Node;
//指针指向两个整数单链表的头结点
r=new Node;
head->next=NULL;
int d=0;
while(p && q) //两个整数单链表均不空
{
r=new Node;
d+=p->data+q->data; //计算两个整数单链中的数值和进位的和 r->data=d%10; //开始记录进位
d=d/10;
r->next=head->next;//把和的个位存储于较长整数单链表的截点 head->next=r;
p=p->next; //开始各指针均向后移动一个结点
q=q->next;
}
//延续上面的思路，有进位且较长整数单链表不空的情况
while(p)
{
r=new Node;
d+=p->data;
r->data=d%10;
d=d/10;
r->next=head->next;
head->next=r;
p=p->next;
}
while(q)
{
r=new Node;
d+=q->data;
r->data=d%10;
d=d/10;
r->next=head->next;
head->next=r;
q=q->next;
}
if(d>0) //如果还有进位的话就开始做如下处理
{ // 较长整数单链表增加结点，存放最后的进位。
r=new Node;
r->data=d;
r->next=head->next;
head->next=r;
}
return head;
}
最后是输出函数Traverse
void Traverse(Node *head)
{
Node *q=head->next;
while(q)
{
coutdata;
q=q->next;
}
cout
}
四、调试分析(调试过程中遇到的问题是如何解决的、对设计与实现简要回顾或分析、经验和体会、经验和不足等，至少写三条)
回顾整个实验过程，大整数的加法可以通过用不同的储存结构对其进行存储再运算得到（可以推广到其他问题）。
而本次实验我试验了2种存储结构，即链式存储方式和顺序存储方式，对于用链表作为存储结构，感觉到这种方式可以适应不定长度的大数的好处。
唯一遗憾的就是没有进一步去研究其他的运算方式，如“减乘除”，或者更繁杂的开根号，N 次方等。以后有空余时间一定要去好好了解一下。
通过本次课程设计，我对大整数的理解和认识又有了进一步的提高，对之前学过的链表和顺序表的知识进行了一次复习巩固，更难得的是对这些理论知识进行了一次映像深刻的应用实践，通过同学间的交流，个人去图书馆或是网上的资料的查阅完成了本次数据结构的第一次的实验。只要有信心，不断努力就能够解决遇到的问题。
五、测试结果(列出测试数据和结果，说明是否通过测试
)
六、实验成绩(教师填写)
教师签名：