搜索
数据结构实验报告学院：班级：姓名：学号：实验一线性链表的实现与操作题目：设计一个100位以内的长整数加减运算的程序班级：姓名：学号：完成日期：一、需求分析1、本实验中，100位长整数的每位上的数字必须为数字[0——9]之间，长整数的位数并要求100位以内。测试的时候输入数据，当输入回车键的时候结束输入，如果输入的字符不符合题目要求，则程序能过滤这些不符合要求的字符。2、演示程序以用户和计算机的对话方式执行，即在计算机显示“提示信息”后之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中不符合要求的字符）和运算结果显示在其后。3、程序执行的命令包括：（1）创建第一个整数（100以内）；（2）执行加法或者减法；（3）创建第二个整数（100以内）；（4）结束。二、概要设计为实现上述程序功能，可以用链表或者长数组表示长整数，如果用数组表示长整数有个缺点就是长整数不能无限长，而链表能动态开辟空间，它克服了这个缺点，所以次试验用链表来表示长整数。1、链表的抽象数据类型定义为：ADTNumber{数据对象：D={ai|ai∈（0，1，…，9），i=0,1，2，…，n，n≥0}数据关系：R={ai-1,ai|ai-1,ai∈D,i=1,2，…，n}基本操作：CreateList（&L）操作结果：创建一个链表L。PrintList（L）初始条件：链表L已存在。操作结果：在屏幕上输出链表的值。PlusList（L1，L2，a）初始条件：链表L1，L2已存在，a为+or–表示加减。操作结果：将两链表的值相加然后在屏幕上输出。DestroyList（&L）初始条件：链表L已存在。操作结果：销毁链表L。}ADTNumber2、本程序包含五个模块：intmain(){定义变量；接受命令；处理命令；return0；}各模块之间的调用关系如下：L1L2+or-：L2L1+or-=L1L2三、详细设计1、定义头文件#includestdio.h#includestdlib.h#defineLENsizeof(Number)typedefstructnumberNumber;structnumber{intdata;Number*next;Number*prior;};///////////////////////////////////////////////////////////////////////////////////////////////////////voidmain(){voidDestoryList(Number*);//释放链表voidPutNumber(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;charch;//存放运算符号printf(Enterthefirstlongnumber:);number_1=GetNumber();printf(put+or-:);ch=getchar();fflush(stdin);//吸收不相关的字符主程序模块创建链表模块输出链表模块两链表加减模块销毁链表模块结束创建链表模块输出链表模块销毁链表模块printf(Enterthesecondlongnumber:);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;charch;p=(Number*)malloc(LEN);List=p;List-prior=NULL;List-data=0;//加法时，放最高位进的1，否者999+1=000ch=getchar();while(ch!='\n'){if(ch='0'&&ch='9')//过滤非数字字符{q=(Number*)malloc(LEN);q-data=ch-'0';p-next=q;q-prior=p;p=q;}ch=getchar();}p-next=NULL;List-prior=NULL;returnList;}//加法分两种情况长度相同与不同Number*JiaFa(Number*num_1,Number*num_2)//返回的数据为逆序{Number*p,*q,*r,*s,*num=NULL;inti=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;}}else{while(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置空returnnum;}//减法分3中情况：被减数长度大于、小于、等于减数长度Number*JianFa(Number*num_1,Number*num_2)//返回的数据也为逆序{Number*p,*q,*r,*s,*num=NULL;inti=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(ij)//对于被减数长度小于减数的，用减数减去被减数，最后反号{while(i--){s-data=q-data-p-data;if(s-data0)//**{s-data+=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-data0)//**{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;}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-data0)//**{s-data+=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=000001{s=s-prior;free(s-next);}}if(num_1-next-datanum_2-next-data){while(i--){s-data=q-data-p-data;if(s-data0)//**{s-data+=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=000001{s=s-prior;free(s-next);}}s-data=0-s-data;//反号，因为节点里不能放符号，而直接在最高位前加负号最简单s-next=NULL;}elseif(ij){while(j--){s-data=p-