数据结构实验报告1.docx

数据结构实验报告一1.4 长整数的四则运算电信提高0901班 吕祺U200913911一.需求分析1.本程序中采用双向链表实现对长整数的存储与运算，每个节点含一个整型变量，每四位一组，组间可用逗号隔开。2.程序由用户输入数据（长整数可正可负），选择加法或减法运算，计算机计算出结果并反馈。3.程序由多个函数组成，函数见概要设计。二.概要设计本实验采用双向链表实现长整数存储。抽象数据类型定义：ADT LNode数据对象：整型数数据关系：R1=| ai-1,aiD，ai-1ai,i=2,3,n ADT LNode2.链表的抽象数据类型：ADT List：D=ai|aiDSLNode，i=1,2，.n，n0数据关系：R1=| ai-1,aiD，ai-1k-data*a; /a只能为逗号或者分号，分号代表结束if(k-data0)L.head=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-data0)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=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)/若为两正数相加或两负数相加，直接从后往前相加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(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;/while if(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=(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直接到结尾，否则下面判断语句不适用，将出错（判断条件被修改） / 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?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;/while else if(A-prior-data=-1) 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;/while goto end; /if(A-prior-prior=NULL&B-prior-prior!=NULL if(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(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;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/ 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!=-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+B-data+C-carryin)-10000;/carryin是C的，故不可先令C指向C的priorC-prior-carryin=temp2prior-data=(temp2+10000)%10000;C-prior-next=C;C=C-prior;/while if(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)-10000;/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;C-prior=( LNode *)malloc(sizeof(LNode);int temp2=(-1)*A-data+B-data+C-carryin)-10000;/carryin是C的，故不可先令C指向C的priorC-prior-carryin=temp2prior-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;/while goto end2; /if(A-prior-prior=NULL&B-prior-prior!=NULL if(A-prior-prior!=NULL&B-prior-prior=NULL)/B结束，与A同 A=A-prior;B=B-prior;C-prior=( LNode *)malloc(sizeof(LNode);int temp2=(-1)*A-data+B-data+C-carryin)-10000;/carryin是C的，故不可先令C指向C的priorC-prior-carryin=temp2prior-data=(10000+B-data-A-data)%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-data+C-carryin;C=C-prior;c.head=C;C-carryin=0;/while /if(A-prior-prior!=NULL&B-prior-prior=NULL) end2: ;/ if(a.head-data=-1&b.head-data!=-1)5输出函数思路：void displaylist(list l)Link p;p=l.head;if(p-data!=-1)coutdata;else coutnext;/while(p-next!=NULL)coutdata;if (i10)cout000i;else if(i100)cout00i;else if(i1000)cout0i;else coutnext;coutdata;if (i10)cout000iendl;else if(i100)cout00iendl;else if(i1000)cout0iendl;else coutiendl;6主函数思路：void main()coutplease enter two adders in the form as 1,0343,0001 ended with ; endl;list L,LA,LB;coutenter A:endl;Creatlist(LA);coutA=;displaylist(LA);coutenter B:endl;Creatlist(LB);coutB=;displaylist(LB);Addlist(L, LA, LB);coutA+B=;displaylist(L);四.完整程序与调试分析# include using namespace std;# include # include # include # include #include #include # define ElemType int typedef struct LNode ElemTypedata,carryin; struct LNode*next,*prior; *Link;typedef struct Link head; Link tail;list;void Initlist(list &L) struct LNode *p;if(p=( LNode *)malloc(sizeof(LNode)=NULL) exit(0); L.head=L.tail=p;void Creatlist(list &L)char *a;char ss1;a=ss;Initlist(L); struct LNode *k;if(k=( LNode *)malloc(sizeof(LNode)=NULL) exit(0); cink-data*a;if(k-data0)L.head=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-data0)else L.head-data=-1;L.head-next=( LNode *)malloc(sizeof(LNode);L.tail=L.head-next;L.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=L.tail; L.tail=q; L.tail-next=NULL;break; q-prior=L.tail; L.tail-next=q; L.tail=L.tail-next; /while /else/Creatlist(list &L)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)/若为两正数相加或两负数相加，直接从后往前相加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(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;/while if(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=(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; / 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?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;/while else if(A-prior-data=-1) 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;/while goto end; /if(A-prior-prior=NULL&B-prior-prior!=NULL if(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(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;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/ 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!=-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+B-data+C-carryin)-10000;/carryin是C的，故不可先令C指向C的priorC-prior-carryin=temp2prior-data=(temp2+10000)%10000;C-prior-next=C;C=C-prior;/while if(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)-10000;/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;C-prior=( LNode *)malloc(sizeof(LNode);int temp2=(-1)*A-data+B-data+C-carryin)-10000;/carryin是C的，故不可先令C指向C的priorC-prior-carryin=temp2prior-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;/while goto end2; /if(A-prior-prior=NULL&B-prior-prior!=NULL if(A-prior-prior!=NULL&B-prior-prior=NULL)/B结束，与A同 A=A-prior;B=B-prior;C-prior=( LNode *)malloc(sizeof(LNode);int temp2=(-1)*A-data+B-data+C-carryin)-10000;/carryin是C的，故不可先令C指向C的priorC-prior-carryin=temp2prior-data=(10000+B-data-A-data)%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-data+C-carryin;C=C-prior;c.head=C;C-carryin=0;/wh