【2017年整理】数据结构实验一.doc

数据结构与算法 实验报告 实验题目： 大整数加法 班 级： 信息与计算科学141 姓 名： xx 学 号： 141021xx 完成日期： 2014.11.03  一、需求分析 1、实验任务是利用线性表的链式存储及其相应操作对两个非负整数（位数可能超过整数类型数据存储的范围）进行相加，求出结果。 2、输入的形式和输入值的范围： 输入的形式为字符，输入值的范围为整数。 3、输出的形式：整型 。 4、程序功能：实现任意位数的两个整数相加。 5、测试数据： 第一组 666666666666666666666666 222 第二组 12345678987654321 9876543212345678987654321 第三组 1333333333333333333333333333333333333333 2555555555555555555555555555555555555555 二、概要设计 1、数据类型 储存整数的单链表中的结点结构可以是： typedef struct line { int data; struct line *next; }list,*linklist; 2、算法思想 （1）输入两个正确的整数，由于输入整数位数可能超过整数数据类型可以存储的范围，所以要用字符数组的数据类型来接受输入的两个整数。考虑到每个长整型数的长度在输入之间是无法预知的，因此使用链表在存储空间的分配上更方便一些。 （2）对于存储在字符数组里的整数，可以根据字符数组中从高位到低位的数值位，用前插法建立单链表的方法，将整数存储于带头结点的单链表中每个结点存放一位数字，这时，从单链表的第一个结点到尾结点依次是从个位到最高位的整数，以便相加运算。 （3）对两个单链表依次扫描到尾结点，将尾结点的数值及前面相加留下的进位相加，把和的个位存储到长度长的单链表对应的结点中，同时记录进位， 3、各子模块 （1）输入整数，存入链表模块 该模块根据字符数组从高位到低位的数值位，用前插法建立单链表。 （2）链表输出模块 输出链表使得从第一个结点到尾结点依次是从个位到最高位的整数，这样便可以进行相加。 （3）整数相加模块 对两个单链表依次扫描到尾结点，将尾结点的数值及前面相加留下的进位相加，把和的个位存储到长度长的单链表对应的结点中，同时记录进位， 三、详细设计 1、数据结构 typedef struct line { int data; struct line *next; }list,*linklist; 2、输入整数，存入链表 void initList(linklist l)//输入整数，存入链表 { char c; linklist p; l=(linklist)malloc(sizeof(list)); l-next=0; while((c=getchar())!=\n) { p=(linklist)malloc(sizeof(list)); p-data=c-48; p-next=l-next; l-next=p; } } 3、输出单链表中的元素值 void print(linklist l)//输出链表 { l=l-next; while(l!=0) { printf(%d,l-data); l=l-next; } } 4、整数相加 void add(linklist l,linklist l1,linklist l2)//求和 { int a,b=0; linklist p; l1=l1-next; l2=l2-next; l=(linklist)malloc(sizeof(list)); l-next=0; while(l1!=0l2!=0) { a=l1-data+l2-data+b; l1=l1-next; l2=l2-next; b=a/10; a=a%10; p=(linklist)malloc(sizeof(list)); p-data=a; p-next=l-next; l-next=p; } if(!l1!l2) { if(b==1) { p=(linklist)malloc(sizeof(list)); p-data=1; p-next=l-next; l-next=p; } } if(l1) { while(l1!=0) { a=l1-data+b; l1=l1