《2022年数据结构课程长整数四则运算设计报告》由会员分享,可在线阅读,更多相关《2022年数据结构课程长整数四则运算设计报告(8页珍藏版)》请在金锄头文库上搜索。
1、长整数的四则运算1. 问题描述设计一个实现任意长的整数进行加法运算的演示程序。2. 需求分析1. 本程序实现计算任意长的整数的四则运算. 以用户和计算机对话的方式,先后输入数字的最多位数,然后程序就计算并显示出这两个数的运算。2. 利用双向循环链表现实长整数的存储,每个结点含一个整形变量。 输入的形式以回车结束,可以直接输入正数或负数,程序会过滤掉无效的字符。按中国对于长整数的表示习惯,每四位一组,除数字和位于首位置的负号外,其它一切字符都将作为分隔符,连续多个分隔符当一个处理。但不使用分隔符也不影响结果。3. 测试数据(1)0; 0; 输出“0”;(2)-2345,6789; -7654,3
2、211; 输出 “- 1,000,000 ”;(3)-9999,9999; 1,0000,0000,0000; 输出 “9999,0000,0001 ”;(4)1,0001,0001; -1,0001,0001; 输出 “0”;(5)1,0001,0001; -1,0001,0001; 输出 “1”;(6)-9999,9999,9999;-9999,9999,9999;输出“ -1,9999,9999,99 98”;(7)1,0000,9999,9999; 1; 输出 1,0001,0000,0000. 3. 概要设计为实现上述程序功能,应以双向循环链表表示长整数。为此,需要定义一个抽象数据类
3、型。1. 抽象数据类型定义为: ADT OrderedList 2. 数据对象: D=ai|aiint,i=1,2,.n, n0 基本操作:init(&a,digit4) 操作结果:构造一个位数是digit4*4长整数。pass(&a,&b,&c) 初始条件: a,b,c 都已存在操作结果: c 等于 a 和 b 的和。nep(&a) 初始条件: a 已存在。操作结果: a 变为输入参数的相反数。printlong(&a) 初始条件: a 已存在。操作结果:按四位一组,分隔符为, 的格式,在屏幕上输出a。ston(&S,&a) 初始条件: a 已存在。操作结果:把字符串形式的长数字赋给a。AD
4、T OrderedList 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 8 页 - - - - - - - - - 3. 本程序包含两个模块:1)主程序模块:Void main() 选择操作:1:帮助。2:加法。3:减法。4:乘法。5:除法。6:退出。打印结果; 4. 详细设计1. 元素类型,结点类型,指针类型#define NULL 0 #include #include #include typedef struct longnode /* 每个节点的结构 */
5、int num; /* 数字*/ struct longnode *low1; /* 指向低一位节点 */ struct longnode *high1; /* 指向高一位节点 */ longnode; typedef struct xlong /* 每个长整数的结构 */ longnode *High; /* 每个长整数的最高节点 */ longnode *Low; /* 每个长整数的最低节点 */ int digit4; /* 每个长整数的总位数 ( 不包括高位的 0)/4 */ *xlong; int init(xlong *a,int digit4) int I; /*.init.*/
6、 longnode *j; (*a)=(xlong)malloc(sizeof(struct xlong);/*为 a 的头结构申请空间 , 并赋初始值 */ (*a)High=NULL;(*a)-Low=NULL; (*a)-High=NULL; (*a)-Low=NULL; (*a)-digit4=0;for(i=0;inum=0;j-high1=NULL; j-low1=(*a)-High; if(*a)-High) (*a)-High-high1=j; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整
7、理 - - - - - - - 第 2 页,共 8 页 - - - - - - - - - (*a)-Low=j;(*a)-High=j;(*a)-digit4+; int pass(xlong a,xlong b,xlong c) int cf=0; /* 两个数字的相加 */ longnode *a1=a-Low,*b1=b-Low,*c1=c-Low; while(a1)c1-num=a1-num+b1-num+cf; if(c1-num9999) cf=1; /* 如果产生进位 (借位) */ c1-num-=10000; elsecf=0; a1=a1-high1;b1=b1-hig
8、h1;c1=c1-high1; return cf; /* 最高位的进位 ( 借位) */ int passa(xlong a,xlong b,xlong c) int cf=0; /* 两个数字的相减 */ longnode *a1=a-Low,*b1=b-Low,*c1=c-Low; while(a1)c1-num=a1-num-b1-num-cf; if(c1-num9999)cf=1;/* 如果产生进位 (借位) */ c1-num-=10000; elsecf=0; a1=a1-high1;b1=b1-high1;c1=c1-high1; return cf; /* 最高位的进位 (
9、 借位) */ int passb(xlong a,xlong b,xlong c) int cf=0;/* 两个数字的相乘 */ longnode *a1=a-Low,*b1=b-Low,*c1=c-Low; while(a1)c1-num=a1-num*b1-num*cf; if(c1-num9999) cf=1; /* 如果产生进位 ( 借位) */ c1-num=10000; elsecf=0; a1=a1-high1;b1=b1-high1;c1=c1-high1; return cf; /* 最高位的进位 (借位) */ int passc(xlong a,xlong b,xlon
10、g c) int cf=0;/* 两个数字的相除 */ longnode *a1=a-Low,*b1=b-Low,*c1=c-Low; while(a1) c1-num=a1-num/b1-num/cf; if(c1-num9999) cf=1; /* 如果产生进位 ( 借位) */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 8 页 - - - - - - - - - c1-num-=10000; else cf=0; a1=a1-high1;b1=b1-high1
11、;c1=c1-high1; return cf; /* 最高位的进位 ( 借位) */ nep(xlong a) /* 求 a 的相反数 */ int cf=1; /* 因为求相反数是取反加一 , 所以这里 cf=1; */ longnode *a1=a-Low; while(a1) a1-num=9999-(a1-num)+cf; if(a1-num9999) a1-num=10000; elsecf=0;a1=a1-high1; return; printlong(xlong a) longnode *i=a-High;/* 打印长整数 a */ if(i-num=5000) printf
12、(-); /* 最高位 (bit)=1表示负数 , 即用补码表示 */ nep(a); /* 求反打印其绝对值 */ while(i&i-num=0) i=i-low1; /* 跳过最位的 0 */ if(i)printf(%d,i-num); i=i-low1; if(i) printf(“, ”);else printf(“0”);/* a=0 打 0 */ while(i)printf(%04d,i-num); if(i-low1) printf(,); i=i-low1; int ston(char in,xlong out) /* 把字符串转化为数字赋给a */ int bit,i,
13、jishu=1,num0=0; longnode *j=out-Low; i=strlen(in)-1;while(i=0 & j) /* 循环每一个字节 */ bit=ini-0;/*把字符形式的值赋给整数形式的bit */ if(bit=0 & bit 1&(jishu=10000|bit9) /* 数字以外的字符 */ j-num=num0; j=j-high1; /* 存入一个节点 */ num0=0; jishu=1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页
14、,共 8 页 - - - - - - - - - i-; if(num0) j-num=num0;j=j-high1;/* 把最后一个没存入节点的数存入节点 */ for(;j;j=j-high1) j-num=0; /* 最位不足补 0 */ if(out-High-num=5000) return 1; /* 如果最高位是 1, 返回 1 表示出 */ if(in0=-) nep(out); /* 如果最后一个字符是 则取反 */ return 0; int add() char *a1,*b1; /*加*/ int digit4,cf=0; xlong a,b,c; do printf(
15、How much digits do you need?);/* 输入最多位数 */ scanf(%d,&digit4); while(digit4=0); a1=(char*)malloc(digit4+1); b1=(char*)malloc(digit4+1); digit4=digit4/4+1; init(&a,digit4); init(&b,digit4); init(&c,digit4); /* 初始化 a,b,c */ do cf=0; printf(Enter 2 number:n); scanf(%s,a1);printf(+n); scanf(%s,b1);cf|=st
16、on(a1,a); cf|=ston(b1,b); while(cf);/* 输入被加数和加数 , 如果转换出错 , 则重输 */ pass(a,b,c); /* 执行相加运算 */ printlong(a);printf(+); /* 打印结果 */ printlong(b);printf(=); printlong(c);printf(n); printf(n);bioskey(0); int subtract()/*减*/ char *a1,*b1; int digit4,cf=0; xlong a,b,c; doprintf(How much digits do you need?);
17、/* 输入最多位 */ scanf(%d,&digit4); while(digit4=0); a1=(char*)malloc(digit4+1); b1=(char*)malloc(digit4+1); digit4=digit4/4+1; init(&a,digit4); init(&b,digit4); init(&c,digit4); /* 初始化 a,b,c */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 8 页 - - - - - - - - - do
18、 cf=0;printf(Enter2number:n); scanf(%s,a1); printf(n); scanf(%s,b1); cf|=ston(a1,a); cf|=ston(b1,b); while(cf); /* 输入被减数和减数 , 如果转换出错 , 则重输 */ passa(a,b,c); /* 执行相减运算 */ printlong(a);printf(-); /* 打印结果 */ printlong(b);printf(=); printlong(c);printf(n); printf(n);bioskey(0); int multiply() /*乘*/ char
19、*a1,*b1; int digit4,cf=0; xlong a,b,c; do printf(How much digits do you need?); /* 输入最多位数 */ scanf(%d,&digit4); while(digit4=0); a1=(char*)malloc(digit4+1); b1=(char*)malloc(digit4+1); digit4=digit4/4+1; init(&a,digit4); init(&b,digit4); init(&c,digit4); /* 初始化 a,b,c */ do cf=0; printf(Enter2number:
20、n); scanf(%s,a1);printf(*n); scanf(%s,b1); cf|=ston(a1,a); cf|=ston(b1,b); while(cf);/* 输入被乘数和乘数 , 如果转换出错 , 则重输 */ passb(a,b,c); /* 执行相乘运算 */ pr intlong(a);printf(“*”);/* 打印结果 */ printlong(b);printf(=); printlong(c);printf(n); printf(n);bioskey(0); int division() /*除*/ char *a1,*b1; int digit4,cf=0;
21、 xlong a,b,c; do printf(How much digits do you need?); /* 输入最多位数 */ scanf(%d,&digit4); while(digit4=0); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 8 页 - - - - - - - - - a1=(char*)malloc(digit4+1); b1=(char*)malloc(digit4+1); digit4=digit4/4+1; init(&a,digit
22、4); init(&b,digit4); init(&c,digit4); /* 初始化 a,b,c */ do cf=0;printf(Enter 2 number:n); scanf(%s,a1);printf(/n); scanf(%s,b1); cf|=ston(a1,a); cf|=ston(b1,b); while(cf); /* 输入被除数和除数 , 如果转换出错 , 则重输 */ passc(a,b,c); /* 执行相除运算 */ printlong(a);printf(/); /* 打印结果 */ printlong(b);printf(=); printlong(c);p
23、rintf(n); printf(n);bioskey(0); 2. 主函数代码void main() /*main*/ int c; clrscr(); textcolor(BLUE); printf(*n); printf(*Welcome to Thunder studio!*n); printf(*n); printf(*本程序实现长整数四则运算*n); one: printf(1: -HELPn); printf(2: -ADDn); printf(3: -SUBTRACTn); printf(4: -MULTIPLYn); printf(5: -DiVISIONn); printf
24、(6: -EXITn); for(;)c=getch(); switch(atoi(&c) case 1: clrscr(); goto one; break; case 2: add(); break; case 3: subtract(); break; case 4: multiply(); break; case 5: division(); break; case 6: textcolor(BLUE); printf(n-n); printf(Thanks cws work!n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -
25、- - - 名师精心整理 - - - - - - - 第 7 页,共 8 页 - - - - - - - - - break; default: textcolor(4); printf(Sorry please input right number!n); break; 5. 编码实现6. 系统测试(对各功能模块进行测试,给出截图)7. 结果分析(对所采用的数据结构和算法,给出时间复杂度和空间复杂度的分析)8. 学习体会9. 源程序清单参考文献:1 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 8 页 - - - - - - - - -