线性表实现大整数运算实验报告

1、石家庄经济学院实 验 报 告网址：实验名称：线性表实现大整数运算学号：413109030111实验日期：2015.03姓名：孙晓颖设备编号：实验室：152一、 实验内容1. 实现线性表链式结构的插入、删除、查找以及合并等操作的算法、编程实现；2. 使用双向链表结构，设计并实现长整数数据类型的表示及相关运算二、 概要设计ADT Longint 数据对象：D=ai,bj|ai,bj0,1,2,3,4,5,6,7,8,9,i=1,2,n,n>=0,j=0,1,2,m,m>=0数据关系：R=<ai,ai+1>&&<ai+1,ai>,i=1,2,n基本

2、操作： shuru(DuLinkList &L) 操作结果：构造一个双向循环链表。 shuchu(DuLinkList L) 初始条件：双向链表s已存在。 操作结果：将输入双向循环链表输出。 shu(DuLinkList L) 操作结果：将操作结果双向循环链表输出。 add(DuLinkList LA, DuLinkList LB,DuLinkList &LC)初始条件：两双向循环链表p,q已存在。 操作结果：将存放长整型数据的两双向链表进行加法运算, 得到新的链表。 minus(DuLinkList LA, DuLinkList LB,DuLinkList &LC)初

3、始条件：两双向循环链表p,q已存在 操作结果：两双向循环链表进行减法运算，得到新的链表。mul(DuLinkList LA, DuLinkList LB,DuLinkList &LC)初始条件：两双向循环链表已存在。 操作结果：将存放长整型数据的两双向链表进行乘法运算，得到新链表。 ADT Longint三、 详细设计/-存储结构表示-typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next;DuLNode,*DuLinkList; /*定义链表结构*/ /-基本操作的实现-voi

4、d shuru(DuLinkList &L)/输入 建立LA LB 链表无空头节点char ch;int opra,i;DuLinkList p,q; printf("请输入长整数 每3位加'，' 输入以#结束 n"); L=(DuLinkList)malloc(sizeof(DuLNode);/新建空链表 L->prior=NULL; p=L; scanf("%d",&opra);/输入数据 p->data=opra;ch=getchar();while(ch!='#')/读取未结束q=(Du

5、LinkList)malloc(sizeof(DuLNode);q->data =0;for (i=0;i<3;i+)ch=getchar();q->data =q->data * 10 +(ch-'0');p->next =q;/连入链表q->prior =p;p=q;/后移ch=getchar();p->next =NULL; printf("提示：输入成功 ! n"); void shuchu(DuLinkList L)/输出 （无空头节点） DuLinkList p; int number,i; ElemTy

6、pe e; printf(" 输出结果n"); number=0;/计算元素个数 p=L; while(p!=NULL) number+; p=p->next; p=L; for(i=1;i<=number;i+) e=p->data;/对当前结点输出结果进行分情况讨论 p=p->next; if (i=1) /对最高位为0 if(e!=0) printf("%d",e); else/其他位分情况 if(e=0) /数值为0 printf("000");else if(e<10) /如果数值为1位 pri

7、ntf("00%d",e); else if(e<100)/如果数值为2位 printf("0%d",e); else printf("%d",e); /逗号 if(i!=number) if (i!=1) printf(","); else if (e!=0) printf(","); printf(" n 输出成功 !n ");void shu(DuLinkList L)/输出运算结果 DuLinkList p; int number,i; ElemType e;

8、printf(" 输出结果n"); number=0;/计算元素个数 p=L; while(p->next !=NULL) number+; p=p->next; p=L->next ; for(i=1;i<=number;i+) e=p->data;/对当前结点输出结果进行分情况讨论 p=p->next; if (i=1) /对最高位为0 if(e!=0) printf("%d",e); else/其他位分情况 if(e=0) /数值为0 printf("000");else if(e<10

9、) /如果数值为1位 printf("00%d",e); else if(e<100)/如果数值为2位 printf("0%d",e); else printf("%d",e); /逗号 if(i!=number) if (i!=1) printf(","); else if (e!=0) printf(","); printf(" n 输出成功 !n ");/加法void add(DuLinkList LA, DuLinkList LB,DuLinkList &

10、;LC) DuLinkList p,q,m,n,tail; ElemType tempa,tempb,tempc,temp;printf("提示： 加法运算 n"); p=LA; while (p->next !=NULL)/指向LA尾p=p->next ;q=LB; while (q->next!=NULL)/指向LB尾q=q->next ; /新建链表LC LC=(DuLinkList)malloc(sizeof(DuLinkList); LC->prior=NULL;m=(DuLinkList)malloc(sizeof(DuLinkLi

11、st);tail=m;temp=0;/进位 while( (p!=NULL)|(q!=NULL) )/当短链结束后，继续计算，视为当前结点运算数为0if(p!=NULL) tempa=p->data;else tempa=0; if(q!=NULL) tempb=q->data;else tempb=0;tempc=tempa+tempb+temp;if (tempc /1000 =0)/若不需要进位 temp=0; if (tempc/1000 >0 )/若需要进位 temp=1; tempc=tempc % 1000; n=(DuLinkList)malloc(sizeo

12、f(DuLinkList);/新建节点 m->data =tempc; n->next=m;m->prior=n;m=n; p=p->prior;/向前移一位q=q->prior;/向前移一位 tail->next=NULL; LC->next=m->next; m->next->prior =LC; free(m); shu(LC);/减法void minus(DuLinkList LA, DuLinkList LB,DuLinkList &LC) DuLinkList p,q,m,n,tail; ElemType temp

13、a,tempb,tempc,temp;printf("提示： 减法运算 n"); p=LA;/指向LA头结点 while (p->next !=NULL) p=p->next ;q=LB;/指向LB头结点 while (q->next !=NULL)q=q->next ;/新建链表LC LC=(DuLinkList)malloc(sizeof(DuLinkList); LC->prior=NULL; m=(DuLinkList)malloc(sizeof(DuLinkList);tail=m;temp=0;/借位 while( (p!=NULL

14、)|(q!=NULL) )/当短链结束后，继续计算，视为当前结点运算数为0if(p!=NULL) tempa=p->data;else tempa=0; if(q!=NULL) tempb=q->data;else tempb=0;tempc=tempa-tempb+temp; if (tempc >=0 )/若不需要借位 temp=0; if (tempc<0 )/若需要借位 temp=-1; tempc=tempc+1000; n=(DuLinkList)malloc(sizeof(DuLinkList);/新建节点 m->data =tempc;n->

15、next =m;m->prior=n;m=n;p=p->prior;/向前移一位q=q->prior;/向前移一位 tail->next=NULL; LC->next=m->next ; m->next->prior =LC;free(m); shu(LC);/乘法void mul(DuLinkList LA,DuLinkList LB,DuLinkList &LC) DuLinkList p,q,m,n,tail; int temp,s; p=LA; q=LB;LC=(DuLinkList)malloc(sizeof(DuLNode);

16、/新建LC->prior=NULL;LC->next=NULL;m=(DuLinkList)malloc(sizeof(DuLNode);m->next=NULL; tail=m; /末尾的值m->prior=NULL;m->data=0;n=m;while (q->next!=NULL) /乘数移至最后一个节点q=q->next ;temp=0; /进位while (q!=NULL) /乘数未结束m=tail;/LC尾部p=LA;while (p->next!=NULL)/被乘数移至最后一个节点p=p->next ;while (p!=N

17、ULL) /被乘数未结束if(m=NULL) m=(DuLinkList)malloc(sizeof(DuLNode);m->prior=NULL; m->data=(p->data*q->data+temp)%1000; temp=(p->data*q->data+temp)/1000; /进位n->prior=m;/相连m->next=n; n=m;m=m->prior ;/向前挪else s=m->data+p->data*q->data+temp; /存放相乘的数与需要进位的和m->data=s%1000;

18、if (m->next!=NULL) temp=s/1000; /判断是否是第一次运算 else temp=(p->data*q->data)/1000+temp; n=m;m=m->prior; p=p->prior ; /被乘数向前挪一位if (temp!=0) /判断进位m=(DuLinkList)malloc(sizeof(DuLNode);m->data=temp;m->prior=NULL;n->prior =m;m->next=n;n=m;m=m->prior;temp=temp/1000; /判断进位值是否大于1000

19、q=q->prior ; /乘数向前挪tail=tail->prior ; /错位相加LC->next=n; /与头节点相连n->prior=LC; shu(LC);四、 程序的调试与测试图1 双向链表1的建立图2 双向链表2的建立图3 加法运算图4 减法运算图5 乘法运算 图一表示输入数213100234链表的建立。以字符串形式输入转化为相应数值，保存至节点中。图二表示输入数100234456链表的建立，过程同链表一。图三表示213100234、100234456两数的加法运算结果，在进行加法运算的过程中，要从两链表从后往前对应节点数值相加，每个结点中只存放三位数字，

20、当相加的结果大于或者等于1000时，要进位，对该结果进行取余，结果即为该结点数值，整除后的结果即为当前进位数值。注意输出的过程中，零输出与逗号输出。图四表示213100234、100234456两数的减法运算结果，在进行减法运算的过程中，同样是要从两链表的尾部向前进行，在减法的过程中，若被减数大于减数，要向前一节点数值借位，同时前一结点数值减一，当减法结束后，输出时要从第一个非零数开始输出，注意零输出。图五表示213100234、100234456两数的乘法运算结果，在进行乘法运算的过程中，同样是要从两链表的尾部向前进行，乘数的最后一结点与被乘数的每一结点数值进行乘法运算，之后被乘数结点向前移位，再次与被乘数的每一节点进行乘法运算，乘数继续前移，直到移至第一个结点为止，同时将相乘结果进行错位相加，在乘法运算的过程中，当相乘所得大于等于1000时，要进位，对该结果取余，取余后的结果即为该结点保存数值，整除后的结果即为要进位的数，若输出的过程中注意零输出。五