免费预览已结束,剩余26页可下载查看
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
长整数的四则运算存储说明:采用带有头结点的双向循环链表来存储长整数,从第一个结点开始,每个结点依次从高位到低位存储长整数的没四位。头结点中存储符号,“-”为1,“+”为0。例如:-1234567890存储后的格式为78903456121 L第一章:实现无符号长整数的四则运算说明:此处是无符号算法,在头结点中符号位用fh代替,而不作任何运算。算法的实现:1. 用字符串接收字符: 例如 S1 79798762399 S2 1234567890 2分别从字符串的末位开始一次取四位,并将其转换为数字存储在带头结点的双向循环链表中:23999876797fh hL2 3.进行运算,具体算法如下加法(实现见add(DuLinkList L,DuLinkList K,char fh) ) 算法描述:用实例来说明。 例:计算1234567890+425252457890345612fhL152454252fhL2从末位开始,依次取出结点里的数和前次的进位相加,并求出要存入表示结果的链表里的数temp和进位cf。 fh新创建一个链表用于保存结果。L1.从末位结点开始,7890+5245+0=13135,temp=3135,cf=1;fh3135L2.加数和被加数同时向前进一个结点:3456+4252+1=7709,temp=7709,cf=0;77093135fh L3.加数已经加完,则取出剩余结点中的被加数加上进位:12+0=12,cf=0;(被加数加完和次方法一致)31357709fh124.对结果的输出:从第一个结点开始,依次输出结点里存放的数,对于第一个结点里的数直接打印输出。其他结点里如23,则要在输出前通过Out(T)函数对23补0,即结果为0023。 此例的显示结果为1277093135.减法(实现见sub(DuLinkList L,DuLinkList K,char fh) )算法描述:用实例来说明。(为方便起见,用用加法用算的结果减去加数)例:1277093135-4252524531357709fh12 L152454252fh L2从末位开始,依次取出结点末位的数相减,如果不够可以借位(cf处置为0)。并存入表示结果的链表中。fh新创建一个用于保存结果的链表 L1. 取出末位节点的数3135和5245,此时cf=0,由于(3135-cf)=31354252,temp=(7709-1)-4252=3456。78903456fh L3继续处理剩下的节点,由于被减数的所有数位以运算完,故结点再向前进一位后,被减数结点值用0来处理。则此时cf=0,(12-0)=120,temp=(12-0)-0=0.将temp的值存入L。7890345612fh L4. 将结果打印输出,结果为:1234567890.乘法(实现见Mul(DuLinkList L,DuLinkList K,char fh) )算法实现例:12345678*65432156781234fh L1432165fh L21. 拆分链表,拆分后的链表为34fh561278 L1fh654321 L21. 计算循环次数,即为L2的结点数。建立中间链表T,以及结果链表result。fhfh T result 2. 第一次循环2.1 p=L1-prior,q=L2-prior,cf=0,fh38temp=(q-data=21)*(p-data=78)+cf=1638,cf=temp/100=16. Ttemp=temp-temp/100*100将temp写入中间链表T2.2 p=p-prior,cf=16,temp=21*56+12=11883882fhcf=1188/100=11 Ttemp=1182-1182/100*100=82将temp插如链表T的最前2.3 继续p=p-prior2.4 第一次循环结束后的链表T为59fh2529238 T2.5 将中间链表T用数组保存。a0=T2.6 q=q-prior,在链表L1后加一个0结点3. 执行第二次循环,此时,q=q-prior,其他均和第一次循环相同。这里仅给出第二次循环后的结果中间链表T,a1=T30fh865415400T第三次循环结束后的中间链表T,a2=T 0002fh468907000T4. 将三次所得到的中间链表的结果相加,的到结果resultresult07fh808363746385. 将结果链表合并,得到最终结果链表,Result0780fh363784638Result6. 打印输出结果,最终结果为8078036374638.除法(实现见Div(DuLinkList L,DuLinkList K,char fh) )算法描述 算出商的长度范围,然后进行循环。每次在除数末尾补零,估计商的值,与除数相乘后如果小于被除数则保存,如果大于则商的估计值减1.算法实现 例:423141789/1239874fh423151789L19874123fhL2fh31. 1.1 建立试商的链表V,并在V的next的data里随便存入一个数k V 1.2先将L2复制给K,计算位数,并且计算循环次数为3次9874123fhK2. 第一次循环2.1在K的后面补0,与L1的位数相同。fh123987400 K2.2 估商的值为4,将4存入V的next的data里fh4V 2.3 用V与K相乘,得到Tfh495949600T2.4 比较T与L1的大小,发现L1小于T,则-V-next-data,并且再次计算T,得到新的链表Tfh371962200T2.5 比较新的T与L1的大小,发现L1大于T,则保存k=V-next-data,保存k到数组ai。然后用L1-T,得到新的链表P,然后销毁L1,最后把新链表的值赋给L1。95895118fhL1=P3. 第二次循环95895118fhL19874123fhK操作与前面一样,所以不再重复。此次循环得到的结果为4,L1变为4629159fhL14. 第三次循环此时为最后一次循环,K不再在末位补零。通过估商函数计算,估计商的值为1,存入V-next-data,用V和K相乘得到链表T,与L1比较小于L1,然后将V-next-data存入保存商的数组中。9874123fhT和第一次循环一样,用L1-T的到新链表,操作的最后会将该链表重新赋给L1,此时的L1就是除法运算结束后的余数。475535fhL15. 计算中a0=3,a1=4,a2=1,将数组元素通过编写的函数转化为链表形式存储,该链表就是最终的商6. 打印输出结果,最终结果为341,余数为354755第二章:用带符号为的存储方式进行四则运算存储方式见开头存储说明。方法分析:通过computing()函数,判断符号的选择。 假设进行运算的两长整数链表为L1和L21. 加法:L1+L2(1):L1-data=0,L2-data=0,执行加法运算,结果为“+”;(2): L1-data=1,L2-data=1,执行加法运算,结果为“-”;(3):L1-data=1,L2-data=0,判断L1与L2的整数值大小:L1L2,执行减法运算,L1-L2,结果为“-”; L1data=0,L2-data=0,判断L1与L2的大小: L1L2,执行减法L1-L2,结果为“+”; (2):L1-data=0,L2-data=1,执行加法L1+L2,结果为“+”; (3):L1-data=1,L2-data=0,执行加法L1+L2,结果为“-”; (4):L1-data=1,L2-data=1,判断L1与L2的大小: L1L2,执行L1-L2,结果为“-”;3. 乘法:L1*L2 (1):L1-data=0,L2-data=0或者L1-data=1,L2-data=1,执行乘法运算,结果为“+” (2): L1-data=0,L2-data=1或者L1-data=1,L2-data=0,执行乘法运算,结果为“-”; 4.除法(同乘法) 第三章 程序清单一C1.h/ c1.h (文件名)#include / malloc()等#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0 / #define INFEASIBLE -1 没使用 typedef int Status; / Status是函数的类型,其值是函数结果状态代码,如OK等 typedef int Boolean; 二C2-4.h/ c2-4.h 线性表的双向链表存储结构。typedef struct DuLNode ElemType data; DuLNode *prior,*next; DuLNode,*DuLinkList;三Operation.cppStatus InistList(DuLinkList &L,char fh) /建立链表的头结点L=(DuLinkList)malloc(sizeof(DuLNode); if(fh=-) L-data=1; else L-data=0; L-prior=L; L-next=L; return OK;void ClearList(DuLinkList L) / 不改变L / 初始条件:L已存在。操作结果:将L重置为空表DuLinkList p=L-next; while(p!=L) p=p-next; free(p-prior); L-next=L-prior=L; void DestroyList(DuLinkList &L) / 操作结果:销毁双向循环链表L ClearList(L); free(L); L=NULL; Status Insfirst(DuLinkList &L,ElemType e) /在头结点后插入新结点DuLinkList p,q; p=(DuLinkList)malloc(sizeof(DuLNode); p-data=e; q=L-next; L-next=p; p-prior=L; p-next=q; q-prior=p; return OK;Status Inslast(DuLinkList &L,ElemType e) /在链表最后插入新结点 DuLinkList p,q; p=(DuLinkList)malloc(sizeof(DuLNode); p-data=e; q=L-prior; q-next=p; p-prior=q; p-next=L; L-prior=p; return OK;int ListLength(DuLinkList L) / 初始条件:L已存在。操作结果:返回L中数据元素个数 int i=0; / 计数器初值为0 DuLinkList p=L-next; / p指向第1个结点 while(p!=L) / p未指向头结点 i+; / 计数器+1 p=p-next; / p指向下一个结点 return i; Status Count(ElemType e) /算元素e的位数 int i,k; for(i=1,k=1000;e/k=0;i+,k=k/10); return i;Status Dzero(DuLinkList &L) /去掉无效0函数 DuLinkList p; if(ListLength(L)next; while(!p-data) p=p-next; L-next=p; p-prior=L; return OK;Status CountB(DuLinkList L) /计算位数函数if(L-next=L) return 0; Dzero(L); int i; i=5-Count(L-next-data)+(ListLength(L)-1)*4; return i;DuLinkList Copy(DuLinkList L) /复制函数 DuLinkList p,K; if(!L) return NULL; InistList(K,L-data); p=L-next; while(p!=L)Inslast(K,p-data); p=p-next; return K;Status Pan(DuLinkList L) /判断链表结点大于1?长整数为0?为1? if(ListLength(L)1) return 1; else if(L-next-data1) return 1; if(L-next-data=1) return 0; if(L-next-data=0) return -1;Status Highest(DuLinkList p) /求最高位 int temp,g=1000; temp=p-data; if(!temp) return 0; while(temp/gdata); p=L-next; while(p!=L)temp=p-data/100; Inslast(K,temp); temp=p-data-temp*100; Inslast(K,temp); p=p-next; return K;Status Merger(DuLinkList &L) /合并链表的函数 DuLinkList p,q,temp; p=L-prior; q=p; while(p!=L&p-prior!=L)q=p-prior; p-data=q-data*100+p-data; temp=q; q=q-prior; q-next=p; p-prior=q; free(temp); p=q; return OK;四function.cppStatus largestdiv(DuLinkList &L,DuLinkList &K) /估计除数 int i; Dzero(L); Dzero(K); i=Highest(L-next)-Highest(K-next); if(i9|i=0) return 9; else return i+1;DuLinkList InitDList(vector a,int i,char fh) /建立商的链表 DuLinkList L;int k,e; InistList(L,fh); for(k=i;k=3;k=k-4) e=ak+ak-1*10+ak-2*100+ak-3*1000; Insfirst(L,e); switch(k) case -1:break; case 0:Insfirst(L,ak);break; case 1:Insfirst(L,ak+ak-1*10);break; case 2:Insfirst(L,ak+ak-1*10+ak-2*100);break; return L;Status CreatL(DuLinkList &L,char *s) /通过相应的字符串建立链表 int i=0,a99999,e,len,n; InistList(L,s0); if(*s=-) len=strlen(s)-1; for(i=len;i0;i-) ai=int(si)-48;elselen=strlen(s);for(i=len;i=0;i-)ai+1=int(si)-48;for(n=len;n3;n=n-4)e=an+an-1*10+an-2*100+an-3*1000; Insfirst(L,e);switch(n)case 0:break;case 1:e=a1;Insfirst(L,e);break;case 2:e=a1*10+a2; Insfirst(L,e);break;case 3:e=a1*100+a2*10+a3; Insfirst(L,e);break; return OK;Status Out(DuLinkList L) /输出函数 int i; DuLinkList p; if(L-data=1) coutnext; while(p-data=0&p-next!=L) /跳过无效0 p=p-next; if(p=L) /输出0coutnext=L) /输出一个结点 coutdata; return OK; if(p-next!=L)coutdata; p=p-next; while(p-next!=L) /循环输出以后的结点if(p-data=0) cout0000; elsefor(i=1;idata);i+)cout0; coutdata; p=p-next; if(p-data=0) cout0000; elsefor(i=1;idata);i+) cout0; coutdata;return OK; DuLinkList InissL(int t) /以传过来的整数建立相应的链表 DuLinkList L; int i; InistList(L,+); if(!t) /建立1链表Inslast(L,1); return L; if(t0;i-) Inslast(L,0); return L; int g=1; for(i=t/4;i0;i-)Inslast(L,0); for(i=t-t/4*4;i1;i-,g*=10); Insfirst(L,g); return L;Status PanGS(char *s) /判断输入格式 int i=1; while(s+i)!=0) if(*(s+i)9)return ERROR;i+; return OK;Status Cmp(DuLinkList L,DuLinkList K) /结点相同时的比较函数 DuLinkList p,q; p=L-next; q=K-next; while(p!=L&q!=K)if(p-dataq-data) return 1; if(p-datadata) return -1; p=p-next; q=q-next; return 0;Status Cmp2(DuLinkList L,DuLinkList K) /两个链表的比较函数int i,k;DuLinkList p,q; i=ListLength(L); k=ListLength(K); if(ik) return 1; if(iprior; q=K-prior; while(p!=L&q!=K) /进行加法,进制10000temp=p-data+q-data+cf; if(temp=10000)Insfirst(R,temp-temp/10000*10000); cf=temp/10000; else Insfirst(R,temp); cf=0; p=p-prior; q=q-prior; while(p!=L) /加完,L还有没加的 temp=p-data+cf; cf=temp/10000; Insfirst(R,temp-temp/10000*10000); p=p-prior; while(q!=K) /K还有没加的 temp=q-data+cf; cf=temp/10000; Insfirst(R,temp-temp/10000*10000); q=q-prior; if(cf!=0) Insfirst(R,cf); /最后是否还有进位 if(Pan(R)=-1) R-data=0; return R;DuLinkList sub(DuLinkList L,DuLinkList K,char fh) /无符号减法函数DuLinkList p,q,R; int temp,cf=0; InistList(R,fh); p=L-prior; q=K-prior; while(p!=L&q!=K) /进行减法,不够减就借位temp=p-data-q-data-cf; if(tempprior; q=q-prior; while(p!=L&cf) /减完,还有借位 if(p-data-cf=0&p-prior=L) return R; temp=p-data-cf; if(temp0) Insfirst(R,temp); p=p-prior; break; else Insfirst(R,temp+10000); cf=1; p=p-prior; while(p!=L) /把剩下的都复制过结果链表 Insfirst(R,p-data); p=p-prior; if(Pan(R)=-1) R-data=0; return R;DuLinkList Mul(DuLinkList L0,DuLinkList K0,char fh) /无符号乘法Dzero(L0);Dzero(K0);DuLinkList L,K,R,T,p,q;L=Resolution(L0); /拆分函数,把一个结点拆成两个对应的结点K=Resolution(K0);int i=0,temp,cf=0,k;k=ListLength(K); /计算循环次数maxMsize=k;vector a(maxMsize); q=K-prior; for(i=0;iprior; InistList(T,fh); /做乘法. while(p!=L) temp=q-data*p-data+cf;cf=temp/100;Insfirst(T,temp-temp/100*100);p=p-prior; if(cf) Insfirst(T,cf);ai=T; /保存建立的中间链表 Inslast(L,0);q=q-prior; if(i=1)Merger(a0);return a0; temp=i-1;Merger(ai-1); /合并链表,再进行累加得出结果Merger(ai-2);R=add(a-i,a-i,fh);for(i=i-1;i=0;i-)Merger(ai);R=add(R,ai,fh);for(temp;temp=0;temp-) /销毁中间链表DestroyList(atemp); DestroyList(L);DestroyList(K);Dzero(R);return R;DuLinkList Div(DuLinkList L,DuLinkList K,char fh) /无符号除法函数DuLinkList p,R,T,G,V;int i,k,m,n,g,c; InistList(V,fh); /建立每次试商的链表 Inslast(V,9);T=Copy(L); m=CountB(L); /链表储存的长整数的位数n=CountB(K);g=m-n+1;maxDsize=g; /算出商的最大位数vector a(maxDsize); /动态分配的数组for(i=0;inext-data=k;for(c=k;c=1;c-) /试商 R=Mul(G,V,fh); if(Cmp2(R,T)!=1)break;DestroyList(R);-V-next-data;ai=c; /商保存数组p=sub(T,R,+);DestroyList(T);T=p;DestroyList(R);elseai=0;DestroyList(G);g-;cout余数为:;Out(T);coutdata&!K-data) R=add(L,K,+); /根据长整数的符号判别是进行加法还是else if(L-data&K-data) R=add(L,K,-); /减法,同时判断出结果的符号,再调用else if(!L-data&K-data) /无符号加法或者减法算出结果if(ListLength(L)ListLength(K) R=sub(L,K,+);else if(ListLength(L)ListLength(K) R=sub(L,K,-);else if(ListLength(L)data&K-data) R=add(L,K,+);else if(L-data&!K-data) R=add(L,K,-); else if(L-data&K-data)if(ListLength(L)ListLength(K) R=sub(L,K,-);else if(ListLength(L)ListLength(K) R=sub(L,K,+);else if(ListLength(L)data&!K-data) fh=+; /判断出结果的符号else if(L-data&K-data) fh=+;else fh=-;k=-1;if(!Pan(L) /乘数是否为1R=Copy(K); /复制K链表R-data=k;return R;if(!Pan(K)R=Copy(L);R-data=k;return R;if(Pan(L)=-1|Pan(K)=-1) /两数是否有为0的R=InissL(-1); /建立一个只有一个接点,且data为0的链表R-data=k;return R;R=Mul(L,K,fh);break;case /:int i,k=0;char fh;if(!L-data&!K-data) fh=+;else if(L-data&K-data) fh=+;else fh=-;k=-1;if(Pan(K)=-1) /判断除数是不是为0cout除数不能为零!d
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- (完整版)2026年节后复工安全教育培训试题及答案
- (2025)员额法官遴选面试试题(附答案)
- 《建设工程法规及相关知识》测试题(附答案)
- 《3-6岁儿童学习与发展指南》测试卷及答案
- “依法治校”普法试题(含答案)
- 2024年大学生安全知识竞赛试题库和答案
- 19期间核查的实施习题与参考答案
- (2025年)危重孕产妇救治试题及答案
- 《饲料质量安全管理规范》考核试题及答案
- (2025)保密教育测试题库完整参考答案
- 2026年注册安全工程师考试金属非金属矿山安全生产实务(初级)试题与参考答案
- 2027年高考地理复习:综合题 答题方向+答题模版汇编
- 2026年监理工程师继续教育人防工程监理测试题含答案
- 2025年控告申诉检察业务竞赛真题及答案解析
- 2026年慢性病防控岗位考试题库及答案
- 化工运行制冷过程工程分析培训课件
- GB/T 2423.68-2026环境试验第2部分:试验方法试验:覆冰融冰循环试验
- 数据资产价值评估指南及实践案例集
- 2025年ISO体外诊断试剂使用规范检测答案及解析
- 精神科护理实践中的人文关怀
- 苏州市住宅工程建安成本参考指标(2021年)
评论
0/150
提交评论