数据结构
实验报告
实验题目： 班 级：
学 号： 姓 名： 完成日期：
一、需求分析
1.问题描述（Problem Description）：
给定两个不超过10000位的非负整数A和B,计算出A+B的值。要求计算并输出A+B的值。
2.根据实验任务的要求分析：
大整数要利用两个顺序表存储大整数，然后对存储于顺序表的两个大整数，根据数据加法的要求，通过对顺序表的操作，使两个大整数的和存储于顺序表，最后输出两个大整数的和，即输出经加发运算后“和”顺序表中的内容。 除了顺序表外，单链表也能达到一样的效果，编程大致也与顺序表相似，本次实验我们只用顺序表的思路来做。
（注：要正确输入2个大整数）
3.测试数据总共有三组：
第一组
9和1
第二组
12345678987654321和9876543212345678987654321
第三组
88888888888888888888888888888888
和6666666666666666666666666666666666666666
4.实验输出：
10
9876543224691357975308642
6666666755555555555555555555555555555554
二、概要设计(数据类型的定义、算法思想、主程序和子程序(或功能)模块的说明及各程序模块之间的层次(调用)关系)
1.顺序表的数据类型
根据题意定义一个Node的指针指向这个结构体
struct Node
{
2
int data;
Node *next;
};
或者用string类型字符串，来进行单链表的建立
typedef struct node
{ //动态链表的节点结构
int data;
node *next;
}*linklist;
2.算法思想
第一步：
主函数中开始输入两个整数，用字符串的数据类型来接受输入的两个整数。（为了防止其整数位数可能超过整数数据类型可以存储的范围） 第二步：
对于存储在字符串里的整数，首先要建立一个只有头结点的空链表L，可调用算法initlist_l完成，为了使新结点能够插入到表尾，需要增加一个尾指针r指向链表的尾结点。
初始时，r与L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点r之后，然后使r指向新的尾结点。
因此可以用前插法建立单链表的方法，依次根据字符串中从高位到低位的数值位，将整数存储于带头结点的单链表中，这时，为了方便加法的运算，从单链表的第一个结点到尾结点依次是：从个位到最高位的整数。
也可用后插法建立单链表的方法，依次根据字符串中从低位(字符串的右端)到高位(字符串的左端)的数值位，将整数存储于带头结点的单链表中。
以上过程可从前插法和后插法中选择其一进行链表的建立工作。（本人用了在这次实验中选择的是前插法）
第三步：
用一个Sum的结构体对两个从单链表的第一个结点到尾结点依次是从个位到最高位存储的两个整数，从第一个结点开始，依次扫描到长度短的单链表的尾结点，每次把扫描到的两个结点中的数值及前面相加留下的进位相加，把和的个位存储到长度长的单链表对应的结点中，同时记录进位；然后把可能有 3
的进位依次与长单链表还未相加过的结点依次相加，若到最后一个结点相加后仍有进位，则要新增加一个结点，以存放进位。至此，两个整数的和已经存储在原来长的单链表中了。
第四步：对于已经存储好的和的单链表要先进行逆置，通过自己定义的一个Traverse函数，将其单链表中结点的值输出。
第五步：在主函数中要设置相关的数据结构，以存放两个整数和单链表，输入两个整数后，依次可调用单链表初始化模块、建立单链表模块、两个整数相加模块、单链表逆置模块和输出单链表中结点的值的模块。中间可确定好较长整数所对应的单链表指针，以供两个整数相加模块使用。
3.主程序
int main()
{
cin >> T;
for (int t = 0; t < T; 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;
}
}
4
三、详细设计(实现概要设计中定义的数据类型，对主程序和其他模块写出算法，说明子模块的调用关系)
首先是对这次链表结构体的建立，同时在这个结构体中为了简化程序，在此整合了对链表输入的代码，让编程语句看起来更简练
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<len;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;
5
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;
}
6
最后是输出函数Traverse
void Traverse(Node *head)
{
Node *q=head->next;
while(q)
{
cout<<q->data;
q=q->next;
}
cout<<endl;
}
四、调试分析(调试过程中遇到的问题是如何解决的、对设计与实现简要回顾或分析、经验和体会、经验和不足等，至少写三条)
回顾整个实验过程，大整数的加法可以通过用不同的储存结构对其进行存储再运算得到（可以推广到其他问题）。
而本次实验我试验了2种存储结构，即链式存储方式和顺序存储方式，对于用链表作为存储结构，感觉到这种方式可以适应不定长度的大数的好处。
唯一遗憾的就是没有进一步去研究其他的运算方式，如“减乘除”，或者更繁杂的开根号，N次方等。以后有空余时间一定要去好好了解一下。
通过本次课程设计，我对大整数的理解和认识又有了进一步的提高，对之前学过的链表和顺序表的知识进行了一次复习巩固，更难得的是对这些理论知识进行了一次映像深刻的应用实践，通过同学间的交流，个人去图书馆或是网上的资料的查阅完成了本次数据结构的第一次的实验。只要有信心，不断努力就能够解决遇到的问题。 7
五、测试结果(列出测试数据和结果，说明是否通过测试
)
六、实验成绩(教师填写)
教师签名： 8
第二篇：数据结构实验报告一(链表)
数据结构实验报告（一）
20095182 刘宗明 信息管理与信息系统09-3班
一、实验目的
（1）理解线性表的链式存储结构。
（2）熟练掌握动态链表结构及有关算法的设计。
（3）根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。
二、实验内容
编写算法实现下列问题的求解。
<1>求链表中第i个结点的指针（函数），若不存在，则返回NULL。
实验测试数据基本要求：
第一组数据：链表长度n≥10，i分别为5，n，0，n+1，n+2
第二组数据：链表长度n=0，i分别为0，2
<2>在第i个结点前插入值为x的结点。
实验测试数据基本要求：
第一组数据：链表长度n≥10，x=100, i分别为5,n,n+1,0,1,n+2
第二组数据：链表长度n=0，x=100，i=5
<3>删除链表中第i个元素结点。
实验测试数据基本要求：
第一组数据：链表长度n≥10，i分别为5,n,1,n+1,0
第二组数据：链表长度n=0， i=5
<4>在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序特性。 实验测试数据基本要求：
链表元素为 （10,20,30,40,50,60,70,80,90,100）,
x分别为25，85，110和8
<5>将单链表Ｌ中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。 实验测试数据基本要求：
第一组数据：链表元素为 （1,2,3,4,5,6,7,8,9,10,20,30,40,50,60） 第二组数据：链表元素为 （10,20,30,40,50,60,70,80,90,100）
<6>求两个递增有序链表L1和L2中的公共元素，并以同样方式连接成链表L3。 实验测试数据基本要求：
第一组
第一个链表元素为 （1，3，6，10，15，16，17，18，19，20）
第二个链表元素为 （1，2，3，4，5，6，7，8，9，10，18，20，30） 第二组
第一个链表元素为 （1，3，6，10，15，16，17，18，19，20）
第二个链表元素为 （2，4，5，7，8，9，12，22）
第三组
第一个链表元素为 （）
第二个链表元素为 （1，2，3，4，5，6，7，8，9，10）
三、算法实现
（一）实验中，各个程序基本上都要实现结点结构体定义、建造链表、主函数实现，故首先将除特定程序所涉及到的具体算法外的公共程序部分（具体操作或有不同）写出如下：
（1）结点结构体定义：
typedef struct LNode
{
int data;//定义元素值类型
struct LNode *next;//递归实现next节点结构体的定义
} node;
（2）建造链表：
node *creatlist()
{
node * L;
node * u;int x;
L=new node;
L->next=NULL;
puts("Please use '0' to end the imput!"); //**头插法建造链表**//
cin>>x;
while(x!=0)
{
u=new node;
u->data=x;
u->next=L->next;L->next=u;
cin>>x;
}
return L;
}
（3）主函数实现：
void main()
{
定义变量；
调用所需函数； //不同实验要求有不同主函数实现
}
（二）具体算法以及部分运行界面截图
<1>查找：
a. 计量长度函数listlen(node *L)
其具体实现为：
int listlen(node *L)
{ node *p=L->next;
int num=0;
while (p!=NULL) //计量链表长度的算法 //**计量链表长度**// {num++;p=p->next; }
return num; //返回长度值}
b. 查找算法：
node *getele(node *L,int i)
{ node *p=L->next;int j=1;
while(j!=i&&p!=NULL) //查找算法
{ p=p->next; j++;} //**实现查找元素**//
if(p==NULL)
return NULL;
else return p; //返回链表头结点地址
}
<2>插入算法：
void listinsert (node *L,int i,int x)
{ node *S;
node *P=L;
node *Q=P;
int k=0;
while(k!=i-1&&P!=NULL) //**插入操作的实现**// { P=P->next; k++; }
if(P==NULL)
printf("序号溢出！");//异常处理
}
else { S=new node; S->data=x; S->next=P->next; P->next=S; //插入算法 } Q=Q->next; puts("The result is:"); while(Q!=NULL) { printf("%d\t",Q->data); Q=Q->next; } //打印 puts("\t");
<3>删除算法：
void listdelete(node *L,int i)
{ node *P=L,*u;
node *Q=L;
int k=0;
while(k!=i-1&&P!=NULL)
{ P=P->next; k++; }
if(P==NULL||P->next==NULL)
puts("删除序号出错啦！"); //删除算法的实现 else
{ u=P->next;
P->next=u->next; //删除算法
delete u;
}
Q=Q->next;
while(Q!=NULL)
{ printf("%d\t",Q->data); Q=Q->next; puts("\t");}
}
<4>顺序插入算法：
void listinsert (node *L,int x)
{ node *u;
node *P=L;
node *Q=L;
while(P->next!=NULL&&P->next->data<x)
P=P->next; //查找插入位置 //插入操作的实现
if(P->next==NULL||P->next->data>x)
{ u=new node;
u->data=x;
u->next=P->next;//具体插入算法
P->next=u;
}
Q=Q->next;
puts("The final output is as below:");
while(Q!=NULL)
{ printf("%d\t",Q->data);//打印
Q=Q->next;
}
puts("\t");
}
<5>分解链表：
void part(node *L)
{ node *A,*B,*P=L->next,*Q,*R;
node *linshi;
A=new node;
B=new node;
Q=A;R=B;
while(L->next!=NULL)
{
if(L->next->data%2==0)
{ linshi=new node;
linshi->data=L->next->data;//偶数值赋给偶数链表
A->next=linshi;
A=linshi; L=L->next;
}
else
{ linshi=new node;
linshi->data=L->next->data;//奇数值赋给奇数链表
B->next=linshi;
B=linshi;L=L->next;
};
}
A->next=NULL;B->next=NULL;
//以下皆为打印实现
puts("The original input is："); //分解链表的实现 while(P!=NULL)
{ printf("%d\t",P->data); P=P->next; }
puts("\t");
puts("The first output is(偶数)：");
if(Q->next==NULL)
} { puts("None!(为空！)"); } else { while(Q->next!=NULL) { printf("%d\t",Q->next->data);Q=Q->next; } } puts("\t"); puts("The second output is(奇数):"); if(R->next==NULL) { puts("None!(为空！)"); } else { while(R->next!=NULL) { printf("%d\t",R->next->data); R=R->next; } } puts("\t");
<6>两链表求交集：
node *Findsame(node *L1,node *L2)
{ node *P1=L1->next,*P2=L2->next,*P3,*U,*T;
P3=new node;T=P3;
while(P1!=NULL&&P2!=NULL)
if(P1->data<P2->data)
P1=P1->next;
else if(P1->data>P2->data) //判断是否同值 //求交集的实现 P2=P2->next;
} else { U=new node; U->data=P1->data; P3->next=U; P3=U;//把两链表中的共同元素赋给链表3 P1=P1->next; P2=P2->next; } P3->next=NULL; return T;
四、实验总结
本次实验，重点是链表的构建及构建前提下各种其他操作的实现。链表实验的顺利进行有助于我们更好的掌握链表的使用。在本次实验中，我采用的是表头插入法建造链表，这样的构造方式在本次实验中有其优点，但也有不足：输出时逆序输出，若要获得顺序输出，则输入时应逆序输入。当然，对链表进行就地转置后也可实现顺序输出。
通过这次实验，我增进了对链表的了解与应用，当然，其中还存在很大不足，希望能在日后的学习中不断改进，不断提高！