课程设计1线性表课程设计

课程设计1线性表课程设计组长：邬萍二、组员：周婷、马玲三、实验日期：2011/4/13四、实验任务（2分）：任务7：设计两个任意长的整数加减法的运算器（2分）基本功能要求：（1）输入两个长整数。（2）利用双向循环链表存储长整数，每个结点存储四位数。（3）计算结果存储于双向循环链表。（4）输出运算式子及结果。五、实验原理：（1）采用循环双链表存储长整数A,B,及二者的和差。（2）程序中包含四个函数。分别为：1.用于创建循环双向链表来存储长整数和处理每个节点存四位数的GreatList函数2.用于输出的DisplayList函数3.用于计算长整数的加法的plus函数4.用于计算长整数的减法的subtraction函数5.用于主函数main函数此题的难点突破分析：题中需要将一个结点存放4位数，然后逐个结点构成的循环双向链表来存放长整数，所以要利用用字符串来存放长整数，利用指针统计所输入的长整数的位数，随后再转化为整数型。（4）用到的主要算法和知识点1.循环双向链表特点的应用2.运用c语言中的函数：atoi函数(arraytointeger的缩写)它的主要功能:把字符串转换成整型数.原型:intatoi(constchar*nptr)函数说明:参数nptr字符串，如果第一个非空格字符不存在或者不是数字也不是正负号则返回零，否则开始做类型转换，之后检测到非数字或结束符\0时停止转换，返回整型数。3.此题中需要创建一片新内存并初始化，并使用内存比较之类的内存操作功能，需要用#include<memory>4.运用strcmp(X,Y)函数来判断X和Y的大小。实验源程序：#include<iostream>#include<stdlib.h>#include<memory>#include<cstring>usingnamespacestd;constMaxSize=100;typedefstructDNode{ intdata; structDNode*next; structDNode*prior;}DLinkList;voidGreatList(DLinkList*&L,chara[],intn)//创建循环双向链表来存储长整数和处理每个节点存四位数{ DLinkList*s;inti=0,j=0,k=0; charX[5]; L=(DLinkList*)malloc(sizeof(DLinkList)); L->prior=L->next=L; if(n<4) { s=(DLinkList*)malloc(sizeof(DLinkList)); for(i=n-1;i>=0;i--) X[j++]=a[i]; s->data=atoi(X); s->next=L->next; s->prior=L; L->next->prior=s; L->next=s; } else { while(i<n&&n-k>=4) { s=(DLinkList*)malloc(sizeof(DLinkList)); for(j=3;j>=0;j--) { X[j]=a[i++]; k++; } s->data=atoi(X); s->next=L->next; s->prior=L; L->next->prior=s; L->next=s; } charY[4]; for(j=n-k-1;j>=0;j--) if(i<n) Y[j]=a[i++]; s=(DLinkList*)malloc(sizeof(DLinkList)); s->data=atoi(Y); if(s->data!=0) { s->next=L->next; s->prior=L; L->next->prior=s; L->next=s; } }}voidDisplayList(DLinkList*L)//输出函数{ DLinkList*p=L->next; inti=0; if(p->data==0)p=p->next; while(p!=L) { if(p!=L->next&&p->data==0)cout<<"000"; cout<<p->data; p=p->next; } cout<<endl;}voidplus(DLinkList*L1,DLinkList*L2,DLinkList*&Lp)//任意长整数的加法{ DLinkList*p1=L1->prior,*p2=L2->prior,*s; intx=0; Lp=(DLinkList*)malloc(sizeof(DLinkList)); Lp->prior=Lp->next=Lp; while(p1!=L1&&p2!=L2) { s=(DLinkList*)malloc(sizeof(DLinkList)); s->data=(p1->data+p2->data+x)%10000; x=(p1->data+p2->data+x)/10000; s->next=Lp->next; s->prior=Lp; Lp->next=s; p1=p1->prior; p2=p2->prior; } while(p1!=L1) { s=(DLinkList*)malloc(sizeof(DLinkList)); s->data=p1->data; s->next=Lp->next; s->prior=Lp; Lp->next=s; p1=p1->prior; } while(p2!=L2) { s=(DLinkList*)malloc(sizeof(DLinkList)); s->data=p2->data; s->next=Lp->next; s->prior=Lp; Lp->next=s; p2=p2->prior; }}voidsubtraction(DLinkList*L1,DLinkList*L2,DLinkList*&Ls)//任意长整数的减法{ DLinkList*p1=L1->prior,*p2=L2->prior,*s; Ls=(DLinkList*)malloc(sizeof(DLinkList)); Ls->prior=Ls->next=Ls; while(p1!=L1&&p2!=L2) { s=(DLinkList*)malloc(sizeof(DLinkList)); if(p1->data>=p2->data) s->data=p1->data-p2->data; else { s->data=p1->data+10000-p2->data; p1->prior->data=p1->prior->data-1; } s->next=Ls->next; s->prior=Ls; Ls->next=s; p1=p1->prior; p2=p2->prior; } while(p1!=L1) { s=(DLinkList*)malloc(sizeof(DLinkList)); s->data=p1->data; s->next=Ls->next; s->prior=Ls; Ls->next=s; p1=p1->prior; } while(p2!=L2) { s=(DLinkList*)malloc(sizeof(DLinkList)); s->data=p2->data; s->next=Ls->next; s->prior=Ls; Ls->next=s; p2=p2->prior; }}voidmain(){ DLinkList*L1,*L2,*Lp,*Ls; intc; charX[MaxSize],Y[MaxSize],string1[MaxSize],string2[MaxSize]; char*p; cout<<"此为两位任意长的整数加减法器!"; cout<<endl<<endl; cout<<"1:begin!\n2:beginagain!\n3:over!\n"; cin>>c; while(c!=3) { intn=0,n1=0; cout<<"请输入整数A:"; cin>>string1; p=string1; while(*p) { n++; p++; } p=string1; for(inti=n-1;i>=0;i--) { X[i]=*p; p++; } GreatList(L1,X,n); cout<<"请输入整数B:"; cin>>string2; p=string2; while(*p) { n1++; p++; } p=string2; for(i=n1-1;i>=0;i--) { Y[i]=*p; p++; } GreatList(L2,Y,n1); plus(L1,L2,Lp); cout<<"A+B="; DisplayList(Lp); cout<<"A-B="; if(strcmp(X,Y)==0) { cout<<"0"; } elseif(n==n1&&strcmp(X,Y)>0||n>n1) { subtraction(L1,L2,Ls); DisplayList(Ls); } else { subtraction(L2,L1,Ls); cout<<"-"; DisplayList(L