《数据结构实验报告1》由会员分享，可在线阅读，更多相关《数据结构实验报告1（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告一1.4 长整数的四则运算电信提高 0901 班吕祺U200913911一.需求分析1.本程序中采用双向链表实现对长整数的存储与运算，每个节点含一个整型变量，每四位一组，组间可用逗号隔开。2.程序由用户输入数据（长整数可正可负） ，选择加法或减法运算，计算机计算出结果并反馈。3.程序由多个函数组成，函数见概要设计。二.概要设计本实验采用双向链表实现长整数存储。抽象数据类型定义：ADT LNode数据对象：整型数数据关系：R1=| ai-1,aiD，a i-1| ai-1,aiD，a i-1k-data*a; /a 只能为逗号或者分号，分号代表结束if(k-data0)L.hea
2、d=L.tail=k;L.tail-next=NULL;L.tail-prior=NULL; /若为正数直接设之为头结点while(*a!=;) /输入不为；时不断循环struct LNode *q;if(q=( LNode *)malloc(sizeof(LNode)=NULL) exit(0);cinq-data*a;if(q-data10000|q-datanext=q;q-prior=L.tail;L.tail=q;L.tail-next=NULL;break;q-prior=L.tail;L.tail-next=q;L.tail=L.tail-next;/while/if(k-dat
3、a0)else L.head-data=-1;L.head-next=( LNode *)malloc(sizeof(LNode);L.tail=L.head-next; /头结点数据域设为-1L.tail-data=-1*k-data;L.tail-prior=L.head;L.tail-next=NULL;L.head-prior=NULL;while(*a!=;)struct LNode *q;if(q=( LNode *)malloc(sizeof(LNode)=NULL) exit(0);cinq-data*a;if(q-data10000|q-datanext=q;q-prior=
4、L.tail;L.tail=q;L.tail-next=NULL;break;q-prior=L.tail;L.tail-next=q;L.tail=L.tail-next; /修改尾节点，将 q 插入/while/else/Creatlist(list &L)4加法函数思路void Addlist(list &c,list a,list b)Initlist(c); Link A=a.tail;Link B=b.tail;Link C=c.tail;/设三个指针，依次往前c.head=c.tail;if(a.head-data*b.head-data0)/若为两正数相加或两负数相加，直接从后
5、往前相加c.tail=( LNode *)malloc(sizeof(LNode);C=c.tail;c.tail-next=NULL;int temp=(a.tail-data+b.tail-data)-10000;/看是否有进位c.tail-carryin=temp0?1:0;c.tail-data=(a.tail-data+b.tail-data)%10000;/不管进位与否，数据域都是取余的结果while(A-prior-prior!=NULL&B-prior-prior!=NULL)A=A-prior;B=B-prior;C-prior=( LNode *)malloc(sizeof
6、(LNode);int temp2=(A-data+B-data+C-carryin)-10000;/carryin 是 C 的，故不可先令 C 指向 C 的priorC-prior-carryin=temp20?1:0;C-prior-data=(temp2+10000)%10000;C-prior-next=C;C=C-prior;/whileif(A-prior-prior=NULL&B-prior-prior=NULL)/不为头结点，无符号域，直接求和C-prior=( LNode *)malloc(sizeof(LNode);A=A-prior;B=B-prior;C-prior-n
7、ext=C;int temp4=(A-data+B-data+C-carryin)-10000;/carryin 是 C 的，故不可先令 C 指向 C 的 priorC-prior-carryin=temp40?1:0;C-prior-data=(temp4+10000)%10000;C-prior-next=C;C=C-prior;c.head=C;if (temp40) C-prior=( LNode *)malloc(sizeof(LNode);C-prior-data=1;C-prior-next=C;C=C-prior;c.head=C;goto end;/不得已用 goto 直接到
8、结尾，否则下面判断语句不适用，将出错（判断条件被修改）/ if(A-prior-prior=NULL&B-prior-prior=NULL)if(A-prior-prior=NULL&B-prior-prior!=NULL)if(A-prior-data!=-1)/A 结束，与 B 同A=A-prior;B=B-prior;C-prior=( LNode *)malloc(sizeof(LNode);int temp2=(A-data+B-data+C-carryin)-10000;/carryin 是 C 的，故不可先令 C 指向 C 的priorC-prior-carryin=temp20
9、?1:0;C-prior-data=(temp2+10000)%10000;C-prior-next=C;C=C-prior;while(B-prior!=NULL) C-prior=( LNode *)malloc(sizeof(LNode);B=B-prior;C-prior-next=C;/carryin 不是 C 的，故可先令 C 指向 C 的 priorC-prior-data=B-data; C=C-prior;c.head=C;/whileelse if(A-prior-data=-1)while(B-prior!=NULL) C-prior=( LNode *)malloc(s
10、izeof(LNode);B=B-prior;C-prior-next=C;/carryin 不是 C 的，故可先令 C 指向 C 的 priorC-prior-data=B-data; C=C-prior;c.head=C;/whilegoto end; /if(A-prior-prior=NULL&B-prior-prior!=NULLif(A-prior-prior!=NULL&B-prior-prior=NULL)/A 结束，与 B 同if(B-prior-data!=-1)A=A-prior;B=B-prior;C-prior=( LNode *)malloc(sizeof(LNod
11、e);int temp2=(A-data+B-data+C-carryin)-10000;/carryin 是 C 的，故不可先令 C 指向 C 的priorC-prior-carryin=temp20?1:0;C-prior-data=(temp2+10000)%10000;C-prior-next=C;C=C-prior;while(A-prior!=NULL) C-prior=( LNode *)malloc(sizeof(LNode);A=A-prior;C-prior-next=C;/carryin 不是 C 的，故可先令 C 指向 C 的 priorC-prior-data=A-d
12、ata;C=C-prior;c.head=C;/while/else if(B-prior-data=-1)while(A-prior!=NULL) C-prior=( LNode *)malloc(sizeof(LNode);A=A-prior;C-prior-next=C;/carryin 不是 C 的，故可先令 C 指向 C 的 priorC-prior-data=A-data;C=C-prior;c.head=C;/while/if(A-prior-prior=NULL&B-prior-prior!=NULL)end: ; if(a.head-data=-1&b.head-data!=
13、-1)c.tail=( LNode *)malloc(sizeof(LNode);C=c.tail;c.tail-next=NULL;int temp=(-1)*a.tail-data+b.tail-data);c.tail-carryin=tempdata=(-1)*a.tail-data+b.tail-data+10000)%10000; while(A-prior-prior!=NULL&B-prior-prior!=NULL)A=A-prior;B=B-prior;C-prior=( LNode *)malloc(sizeof(LNode);int temp2=(-1)*A-data+
14、B-data+C-carryin)-10000;/carryin 是 C 的，故不可先令 C 指向 C 的priorC-prior-carryin=temp2prior-data=(temp2+10000)%10000;C-prior-next=C;C=C-prior;/whileif(A-prior-prior=NULL&B-prior-prior=NULL)C-prior=( LNode *)malloc(sizeof(LNode);A=A-prior;B=B-prior;C-prior-next=C;int temp4=(-1)*A-data+B-data+C-carryin)-1000
15、0;/carryin 是 C 的，故不可先令 C 指向 C 的 priorC-prior-carryin=temp4prior-data=(temp4+10000)%10000;C-prior-next=C;C=C-prior;c.head=C;if (temp4prior=( LNode *)malloc(sizeof(LNode);C-prior-data=-1;C-prior-next=C;C=C-prior;c.head=C;goto end2; / if(A-prior-prior=NULL&B-prior-prior=NULL)if(A-prior-prior=NULL&B-prior-prior!=NULL)if(A-prior-data!=-1)/A 结束，与 B 同A=A-prior;B=B-prior;nts
