数据结构实验报告-线性表.doc

实验一 线性表实现方法题目：编制一个长整数加减运算实现的程序班级： 姓名： 学号： 完成日期：2011年11月17日一、需求分析1、 本实验中演示中，长整数的每位上的数字必须为数字09之间，长整数的位数要求无限长。测试的时候输入数据，当输入回车键的时候结束输入，如果输入的字符不符合题目要求，则程序能过滤这些不符合要求的字符。2、演示程序以用户和计算机的对话方式执行，即在计算机显示“提示信息”后之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中不符合要求的字符）和运算结果显示在其后。3、程序执行的命令包括：（1）创建第一个长整数；（2）执行加法或者减法；（3）创建第二个长整数；（4）结束。4、测试数据（1）Please Enter the First long Integer：12345678999999999999999+ or - ：+Please Enter the Second long Integer：98765432ht1111111111k1111111111112345678999999999999999+98765432111111111111111111111=98765444456780111111111111110（2）Please Enter the First long Integer：1234567899hu99999fg99999999+ or - ：-Please Enter the Second long Integer：98765432hr1111111ky1111111111111112345678999999999999999-98765432111111111111111111111=-98765419765432111111111111112二、概要设计为实现上述程序功能，可以用链表或者长数组表示长整数，如果用数组表示长整数有个缺点就是长整数不能无限长，而链表能动态开辟空间，它克服了这个缺点，所以次试验用链表来表示长整数。1、链表的抽象数据类型定义为：ADT Number数据对象：D=ai| ai（0，1，9），i=0,1，2，n，n0数据关系：R=| ai-1, aiD,i=1,2，n基本操作：CreateList（&L）操作结果：创建一个链表L。PrintList（L）初始条件：链表L已存在。操作结果：在屏幕上输出链表的值。PlusList（L1，L2，a）初始条件：链表L1，L2已存在，a为+ or 表示加减。操作结果：将两链表的值相加然后在屏幕上输出。DestroyList（&L）初始条件：链表L已存在。操作结果：销毁链表L。 ADT Number2、本程序包含五个模块：（1）主程序模块：int main()定义变量；接受命令；处理命令；退出（return 0）；（2）创建链表模块产生一个长整数；（3）输出链表模块把链表产生的一个长整数输出；（4）两链表加减模块即求两个由链表产生的长整数的加减并输出结果；（5）销毁链表模块程序结束后释放链表开辟的空间。各模块之间的调用关系如下：主程序模块 L1 L2创建链表模块创建链表模块 +or - ： L2 L1输出链表模块输出链表模块 +or - =两链表加减模块 L1 L2销毁链表模块结束销毁链表模块三、详细设计#include#include#define LEN sizeof(Number)typedef struct number Number;struct numberint data;Number *next;Number *prior;/void main()void DestoryList(Number *);/释放链表void PutNumber(Number *);/将求得的结果输出Number *GetNumber();/创建链表，放被加数与加数Number *JiaFa(Number *num_1,Number *num_2);/加法函数Number *JianFa(Number *num_1,Number *num_2);/减法函数Number *number_1,*number_2,*number;char ch;/存放运算符号printf(Enter the first long number:);number_1=GetNumber();printf(put +or-:);ch=getchar();fflush(stdin);/吸收不相关的字符printf(Enter the second long number:);number_2=GetNumber();if(ch=+)number=JiaFa(number_1,number_2);elseif(ch=-)number=JianFa(number_1,number_2);printf(n=n);PutNumber(number);DestoryList(number);DestoryList(number_1);DestoryList(number_2);printf(链表释放完成。n);/Number *GetNumber()Number *p,*q,*List;char ch;p=(Number *)malloc(LEN);List=p;List-prior=NULL;List-data=0;/加法时，放最高位进的1，否者999+1=000ch=getchar();while(ch!=n)if(ch=0&chdata=ch-0;p-next=q;q-prior=p;p=q;ch=getchar();p-next=NULL;List-prior=NULL;return List;/加法分两种情况长度相同与不同/返回的数据为逆序Number *JiaFa(Number *num_1,Number *num_2)Number *p,*q,*r,*s,*num=NULL;int i=0,j=0;r=num;p=num_1;while(p-next!=NULL)i+;p=p-next;/i表示number1数字的长度 p指向number节点q=num_2;while(q-next!=NULL)j+;q=q-next;/j表示number2数字的长度 q指向number节点s=(Number *)malloc(LEN);s-prior=NULL;s-next=NULL;num=s;while(i-&j-)s-data=p-data+q-data;if(s-data9)s-data-=10;/*处理两数相加大于9的情况，后面还有if(ij)/在长的数据上调整p-prior-data+;elseq-prior-data+;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;r=s=s-prior;/去掉最后一个没数据的节点free(s-next);s-next=NULL;if(ij)while(i-)if(p-data9)p-data-=10;/*p-prior-data+;s=(Number *)malloc(LEN);s-data=p-data;p=p-prior;r-next=s;s-prior=r;r=s;if(p-data0)/*s=(Number *)malloc(LEN);s-data=p-data;r-next=s;s-prior=r;r=s;elsewhile(j-)if(q-data9)/*q-data-=10;q-prior-data+;s=(Number *)malloc(LEN);s-data=q-data;q=q-prior;r-next=s;s-prior=r;r=s;if(q-data0)/*s=(Number *)malloc(LEN);s-data=q-data;r-next=s;s-prior=r;r=s;s-next=NULL;/将最后一个next置空return num;/减法分3中情况：被减数长度大于、小于、等于减数长度/返回的数据也为逆序Number *JianFa(Number *num_1,Number *num_2)Number *p,*q,*r,*s,*num=NULL;int i=0,j=0;r=num;p=num_1;while(p-next!=NULL)/i表示number1数字的长度 p指向number节点i+;p=p-next;q=num_2;while(q-next!=NULL)/j表示number2数字的长度 q指向number节点j+;q=q-next;s=(Number *)malloc(LEN);s-prior=NULL;s-next=NULL;num=s;if(idata=q-data-p-data;if(s-datadata+=10;q-prior-data-;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;j-;/使i，j同时变化r=s=s-prior;/去掉最后一个没数据的节点free(s-next);s-next=NULL;while(j-)if(q-datadata+=10;q-prior-data-;s=(Number *)malloc(LEN);s-data=q-data;q=q-prior;r-next=s;s-prior=r;r=s;s-data=0-s-data;/反号，因为节点里不能放符号，而直接在最高位前加负号最简单s-next=NULL;elseif(i=j)i=j=1;p=num_1;q=num_2;while(p-data=q-data)p=p-next;q=q-next;num_1=(Number *)malloc(LEN);num_1-prior=NULL;num_1-data=0;num_1-next=p;num_2=(Number *)malloc(LEN);num_2-prior=NULL;num_2-data=0;num_2-next=q;while(p-next!=NULL)/i表示number1数字的长度 p指向number节点i+;p=p-next;q=num_2;while(q-next!=NULL)/j表示number2数字的长度 q指向number节点j+;q=q-next;if(num_1-next-datanum_2-next-data)while(i-)s-data=p-data-q-data;if(s-datadata+=10;p-prior-data-;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;r=s=s-prior;/去掉最后一个没数据的节点free(s-next);while(s-data=0&s-prior!=NULL)/去掉前面多余的0，否则111112-111111=000001s=s-prior;free(s-next);if(num_1-next-datanext-data)while(i-)s-data=q-data-p-data;if(s-datadata+=10;q-prior-data-;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;r=s=s-prior;/去掉最后一个没数据的节点free(s-next);while(s-data=0&s-prior!=NULL)/去掉前面多余的0，否则111112-111111=000001s=s-prior;free(s-next);s-data=0-s-data;/反号，因为节点里不能放符号，而直接在最高位前加负号最简单s-next=NULL;elseif(ij)while(j-)s-data=p-data-q-data;if(s-datadata+=10;p-prior-data-;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;i-;r=s=s-prior;/去掉最后一个没数据的节点free(s-next);s-next=NULL;while(i-)if(p-datadata+=10;p-prior-data-;s=(Number *)malloc(LEN);s-data=p-data;p=p-prior;r-next=s;s-prior=r;r=s;while(s-data=0&s-prior!=NULL)/去掉前面多余的0，否则1000-1=0999s=s-prior;free(s-next);/s-data=0-s-data;/反号，因为节点里不能放符号，而直接在最高位前加负号最简单s-next=NULL;return num;/void PutNumber(Number *num)Number *p;int k=1,i;/k为数据长度，i控制,p=num;while(p-next!=NULL)p=p-next;k+;i=4-k%4;while(k-)i+;printf(%d,p-data);p=p-prior;if(k!=0&i%4=0)/长度为k的数据，在k%4个数字后开始输出,数据输出完后不输出,putchar(,);putchar(n);/void DestoryList(Number *list)Number *p,*q;p=list;while(p)q=p-next;fre