长整数的代数计算数据结构课程设计

1、课课 程程 设设 计计 报报 告告课程设计名称：数据结构课程设计数据结构课程设计课程设计题目： 长整数的代数计算长整数的代数计算院（系）：专 业：计算机科学与技术 班 级： 学 号： 姓 名： 指导教师： 沈阳航空航天大学课程设计报告 目目 录录1 题目介绍和功能要求题目介绍和功能要求.11.1 题目介绍 .11.2 功能要求 .11.3 基本功能 .12 系统功能模块结构图系统功能模块结构图.22.1 系统功能结构框图.22.2 系统主要模块的功能说明.23 使用的数据结构的描述使用的数据结构的描述.43.1 数据结构设计 .43.2 数据结构用法说明 .44 函数的描述函数的描述.54.1

2、 主要函数设计.54.2 主要函数流程图.65 程序测试和运行的结果程序测试和运行的结果.115.1 程序测试.115.2 运行结果.126 参考文献参考文献.14附附 录（关键部分程序清单）录（关键部分程序清单）.15沈阳航空航天大学课程设计报告 0 1 题目介绍和功能要求1.1 题目介绍题目介绍 设计数据结构完成长整数的表示和存储，并编写算法来实现两个长整数的加、减、乘、除等基本代数运算。1.2 功能要求功能要求1) 长整数长度在一百位以上。2） 实现两长整数在同余代数下的加、减、乘、除操作。即实现算法来求解a+b mod n，a-b mod n，a*b mod n，ab mod n。3）

3、输入输出均在文件中。 （选作）1.3 基本功能基本功能1.jiafa();将一百位以上的长整数进行加法运算，计算出和。2.jianfa();将一百位以上的长整数进行减法运算，计算出差。3.chenfa();将一百位以上的长整数进行乘法运算，计算出积。4.chufa(); 将一百位以上的长整数进行除法运算，计算出商和余数。沈阳航空航天大学课程设计报告 1 2 系统功能模块结构图2.1 系统功能结构框图系统功能结构框图主模块输入模块减法模块加法模块乘法模块除法模块输出模块图图 2.12.1 系统功能结构框图系统功能结构框图2.2 系统主要模块的功能说明系统主要模块的功能说明1. 主模块kongzh

4、i()；沈阳航空航天大学课程设计报告 2 控制输入模块、加法模块、减法模块、乘法模块、除法模块、输出模块的循环使用。2. 输入模块shuru();将输入的两组长整数分别通过转换将其转换成所需要的形式存储到两个链表（opr1、opr2）中保存起来。3. 加法模块 jiafa();将链表 opr1、opr2 中的数据进行加法运算，并且二者的将加和保存到链表 oprr 中。4. 减法模块 jianfa();将链表 opr1、opr2 中的数据进行减法运算，并且将二者的差保存到链表oprr 中。5. 乘法模块 chengfa();将链表 opr1、opr2 中的数据进行乘法运算，并且将二者的乘积保存到

5、链表 oprr 中。6. 除法模块 chufa();将链表 opr1、opr2 中的数据进行加法运算，并且将二者的商和余数分别保存到链表 quti、remand 中。7. 输出模块 shuchu(); 将链表 oprr、quti、remand 中的数据保存到字符数组中，并且将字符数组中的数据输出到屏幕上。沈阳航空航天大学课程设计报告 3 3 使用的数据结构的描述3.1 数据结构设计数据结构设计将输入的两个长整数首先保持到字符数组中，然后将字符数组中的字符转换每四个一组，利用双向循环链表来实现每一组字符的存储，并且高位在前、低位在后。每个结点中只存储四位十进制数字，即不超过 9999 的非负整数

6、。利用两个双向循环链表分别保持了两个非负长整数。加法：由低位的结点开始相加，加和大于 9999 时，加和除以一万取余数保存到新的双向循环链表结点中，并且加和除以一万取整数作为进位加到下两个结点相加中，依次循环相加；减法：同加法有些相似，保证第一个长整数不小于于第二个长整数，结点相减，不能相减就相前一结点借位，差保存到新的双向循环链表结点中，依次循环；乘法：由低位的结点开始相乘，乘积大于 9999 时，乘积除以一万取余数保存到新的双向循环链表结点中，并且乘积除以一万取整数作为进位加到下两个结点乘积中，依次循环相乘；除法：开辟两个新的链表，保存商数和差。用第一个长整数循环减去第二个长整数，没减一次

7、计数加一，计数保存到商数链表中。直到差小于第二个长整数停止循环，最后的计数为商值，差值为余数。选择该数据结构来完成长整数的加减乘除运算是因为要对长整数进行运算，需要对长整数进行存储，所以选择用链表对长整数存储，又由于存储的顺序是从左到右，而运算的顺序则是从右到左，这样位了操作方便选择循环链表，在运算过程中有进位和借位的操作，所以最终选择双向循环链表的数据结构。3.2 数据结构用法说明数据结构用法说明输入的两个长整数必须为非负长整数。加法计算时只要保证两个数都为非负数即可，减法、乘法、除法时需要保证第一个长整数大于第二个长整数。同时乘法、除法计算时第二个数不能为零，并且输入的数一定要合法，最高位

8、不能为零，否则程序会提示输入有误。沈阳航空航天大学课程设计报告 4 4 函数的描述4.1主要函数设计主要函数设计1. shuru ()；作用作用：将输入的两个长整数分别保存到两个链表中。2. jiafa()；作用作用：将两个长整数进行加法运算，计算出二者的和。3. jianfa();作用作用：将两个长整数进行减法运算，计算出二者的差。4. chengfa ()；作用作用：将两个长整数进行乘法运算，计算出二者的积。5. chufa(); 作用作用: 将两个长整数进行除法运算，计算出二者的商和余数。6. shuchu();作用作用: 将保存到链表中的计算结果输出。沈阳航空航天大学课程设计报告 5

9、4.2 主要函数流程图主要函数流程图1. kongzhi():开始判断ch输入ch调用加法函数调用减法函数调用乘法函数调用除法函数退出程序结束输出和输出差输出积输出商12345 图图 4.2.14.2.1 控制函数流程图控制函数流程图 沈阳航空航天大学课程设计报告 6 2. jiafa(); 开始nodelist p1=opr1,p2=opr2,p3=oprr；将链表opr1、opr2中的对应结点中数据加和并加上进位移动指针p1、p2判断指针p1,p2是否指向头指针若p1没有指向头指针和除以一万取整保存为进位和保存到链表oprr中和大于一万是否有进位和除以一万取余保存到链表oprr中将链表op

10、r1、opr2中的对应结点中数据加和若p2没有指向头指针将opr1中剩余结点数据保存到oprr中将opr2中剩余结点数据保存到oprr中结束ynynynynny 图图 4.2.24.2.2 加法函数流程图加法函数流程图 沈阳航空航天大学课程设计报告 7 3. jianfa();开始nodelist p1=opr1,p2=opr2,p3=oprr；将链表opr1、opr2中的对应结点中数据作差并减去1移动指针p1、p2判断指针p2是否指向头指针若p1没有指向头指针差保存到链表oprr中是否有借位将链表opr1中结点数据加上一万后减去opr2中的对应结点中数据将opr1中剩余结点数据保存到oprr

11、中结束ynnyny判断链表opr1中结点的数据大于opr2中对应结点的数据将链表opr1、opr2中的对应结点中数据作差yn 图图 4.2.34.2.3 减法函数流程图减法函数流程图沈阳航空航天大学课程设计报告 8 4、chengfa();开始nodelist p1=opr1,p2=opr2,p3=oprr；将链表opr1、opr2中的结点中数据相乘并加上进位移动指针p1若p1没有指向头指针和除以一万取整保存为进位积保存到链表oprr中和大于一万是否有进位积除以一万取余保存到链表oprr中将链表opr1、opr2中的结点中数据相乘若p2没有指向头指针结束ynynynynny是否有进位保存进位进

12、位为零移动指针p2图图 4.2.44.2.4 乘法函数流程图乘法函数流程图沈阳航空航天大学课程设计报告 9 5、chufa(); 开始nodelist p1=opr1,p2=opr2,quti,remand；将链表opr1结点中数据加一万后减去opr2结点数据并减借位移动指针p2链表remand中数据是否大于链表opr2中数据是否需要借位差保存到链表remand中将链表opr1、opr2中的结点中数据相减若p2没有指向头指针结束ynynyn计数加一并将计数保存到链表quti图图 4.2.54.2.5 除法函数流程图除法函数流程图沈阳航空航天大学课程设计报告 10 5 程序测试和运行的结果5.1

13、 程序测试程序测试1、程序开始菜单： 图图 5.1.15.1.1 菜单图菜单图 2、程序退出：图图 5.1.25.1.2 退出程序图退出程序图沈阳航空航天大学课程设计报告 11 5.2 运行结果运行结果1、加法运算：图图 5.2.15.2.1 除法运算图除法运算图2、减法运算：图图 5.2.25.2.2 除法运算图除法运算图沈阳航空航天大学课程设计报告 12 3、乘法运算：图图 5.2.35.2.3 除法运算图除法运算图4、除法运算：图图 5.2.45.2.4 除法运算图除法运算图沈阳航空航天大学课程设计报告 13 6 参考文献1谭浩强著. c 程序设计（ 第三版）. 北京: 清华大学出版社,

14、20052严蔚敏 吴伟明.数据结构（c 语言版）.北京:清华大学出版社,20073 王裕明.数据结构与程序设计.北京:清华大学出版社，20104 谭浩强.c 语言程序设计m.北京:清华大学出版社,20055 王敬华 林萍 张清国.c 语言程序设计教程m.北京:清华大学出版社,2005沈阳航空航天大学课程设计报告 14 附 录（关键部分程序清单）#include stdafx.h#include#include#include#include#define len sizeof(struct node)#define max 1000#define ok 1#define error 0#def

15、ine overflow -1#define true 1#define false 0typedef int status;typedef struct node int data;struct node *prior,*next;node,*nodelist;int axp(int a,int k) /求指数函数值int r=1;if(k=0)return 1;for(;k0;k-)r=r*a;return r;status zhuanhuan(char str,nodelist &oprh) /输入转换函数/将字符串形式的操作数转换成所需的类型nodelist p;int i,k,buf

16、fer;k=buffer=0;oprh=(nodelist)malloc(len);oprh-next=oprh;oprh-prior=oprh;for(i=strlen(str)-1;i=0;i-)if(i!=0 | (str0!=- & str0!=+)&(stri9 | strinext-prior=p; p-prior=oprh; p-next=oprh-next; oprh-next=p; p-data=buffer; buffer=k=0;return ok;status shuru(nodelist &opr1,nodelist &opr2,char str)/输入函数int f

17、lag=ok; printf(nn 请输入第一个操作数:n);scanf(%s,str);getchar();flag=zhuanhuan(str,opr1); while(!flag) printf(整数输入有误，请重新输入:n); scanf(%s,str);getchar(); flag=zhuanhuan(str,opr1);printf(nn 请输入第二个操作数:n);scanf(%s,str);getchar();flag=zhuanhuan(str,opr2); while(!flag) printf(整数输入有误，请重新输入：n);沈阳航空航天大学课程设计报告 16 scanf

18、(%s,str);getchar(); flag=zhuanhuan(str,opr2);return ok;/输出函数status shuchu(nodelist oprr,char str)status initbuf(char str);nodelist p;int i,j,num4;if(!oprr)return error;p=oprr;i=j=0;initbuf(str);p=p-next;if(p-next=oprr & p-data=0)/若要输出的数为 0 则执行stri+=0;else while(p!=oprr) num0=p-data/1000; num1=(p-dat

19、a-num0*1000)/100; num2=(p-data-num0*1000-num1*100)/10; num3=p-data-num0*1000-num1*100-num2*10; while(jnext; j=0;stri=0;printf(%s,str);printf(n);return ok;status initbuf(char str)/缓冲区部分初始化函数沈阳航空航天大学课程设计报告 17 int i;for(i=0;iprior;p2=opr2-prior;while(p1-prior!=opr1 & p2-prior!=opr2)p1=p1-prior;p2=p2-pr

20、ior;if(p1-prior!=opr1)return 1;if(p2-prior!=opr2)return -1;return 0;int length(nodelist oprr) /求链表长度int count=0;nodelist p=oprr-next;while(p!=oprr)count+;p=p-next;return count;status creat(nodelist &oprr,int len) /生成指定长度链表nodelist p;oprr=(nodelist)malloc(len);p=oprr;while(len0)p-next=(nodelist)mallo

21、c(len);p-next-data=?;p-next-prior=p;沈阳航空航天大学课程设计报告 18 p=p-next;len-;p-next=oprr;oprr-prior=p;return ok;int compare(nodelist opr1,nodelist opr2) /比较 opr1、opr2 绝对值的大小nodelist p1,p2;p1=opr1-next;p2=opr2-next;if(cmplinklen(opr1,opr2)=1)/opr1 比较长return 1; else if(cmplinklen(opr1,opr2)=-1)/opr2 比较长return

22、-1; else/长度相等的情况 while(p1-data=p2-data & p1-next!=opr1) p1=p1-next; p2=p2-next;if(p1-datap2-data)return 1;else if(p1-datadata)return -1;else return 0;/-初始化链表函数-status init(nodelist &oppr)oppr=null;return ok;/=加法模块=status jiafa(nodelist opr1,nodelist opr2,nodelist &oprr)/本算法实现 a,b 相加的操作int cf,buffer;

23、 nodelist p1,p2,p3;oprr=(nodelist)malloc(len);沈阳航空航天大学课程设计报告 19 oprr-next=oprr;oprr-prior=oprr;p1=opr1-prior;p2=opr2-prior;cf=buffer=0;while(p1!=opr1 & p2!=opr2)buffer=p1-data+p2-data+cf;cf=buffer/10000;/若 buffer 的值大于 9999 则产生进位，赋给 cf/将新建结点插入到头结点之后 p3=(nodelist)malloc(len); oprr-next-prior=p3; p3-pr

24、ior=oprr;p3-next=oprr-next;oprr-next=p3;p3-data=buffer%10000;/应该将 buffer 的第四位赋给 p3-data /.p1=p1-prior;p2=p2-prior;while(p1!=opr1)/处理 opr1 链的剩余部分buffer=p1-data+cf;cf=buffer/10000;/若 buffer 的值大于 9999 则产生进位，赋给 cf/将新建结点插入到头结点之后p3=(nodelist)malloc(len); oprr-next-prior=p3; p3-prior=oprr;p3-next=oprr-next

25、;oprr-next=p3;p3-data=buffer%10000;/.p1=p1-prior;while(p2!=opr2)/处理 opr2 链的剩余部分buffer=p2-data+cf;cf=buffer/10000;/若 buffer 的值大于 9999 则产生进位，赋给 cf/将新建结点插入到头结点之后p3=(nodelist)malloc(len); oprr-next-prior=p3; p3-prior=oprr;p3-next=oprr-next;沈阳航空航天大学课程设计报告 20 oprr-next=p3;p3-data=buffer%10000;p2=p2-prior;

26、if(cf)p3=(nodelist)malloc(len); oprr-next-prior=p3; p3-prior=oprr;p3-next=oprr-next;oprr-next=p3;p3-data=cf;return ok;/=减法基本操作=status jianfa(nodelist opr1,nodelist opr2,nodelist &oprr)/本算法实现 a,b 相减的操作 /将 a 链分成与 b 链长相等的底位部分,和剩余的高位部分,并做相应处理。int cf,buffer,flag;nodelist p1,p2,p3,qh,qt,qq;oprr=(nodelist)

27、malloc(len); oprr-next=oprr;oprr-prior=oprr;p1=opr1-prior;p2=opr2-prior;cf=buffer=flag=0;while(p2!=opr2)/opr2 链的长度小于等于 opr1 链的if(p1-datadata+cf)buffer=10000+p1-data-(p2-data+cf);cf=1;elsebuffer=p1-data-(p2-data+cf);cf=0;p3=(nodelist)malloc(len); oprr-next-prior=p3; p3-prior=oprr;p3-next=oprr-next;沈阳

28、航空航天大学课程设计报告 21 oprr-next=p3; p3-data=buffer; p1=p1-prior;p2=p2-prior;while(p1!=opr1)/处理 opr1 链剩下的部分if(p1-datadata-cf;cf=1;elsebuffer=p1-data-cf;cf=0;p3=(nodelist)malloc(len); oprr-next-prior=p3; p3-prior=oprr;p3-next=oprr-next;oprr-next=p3; p3-data=buffer;p1=p1-prior;/处理链表开头结点值为 0 的无意义情况，若链表本身表示 0，

29、则不做如下处理 p3=oprr-next;while(p3-data=0 & p3-next!=oprr)p3=p3-next;flag=1;if(flag)qh=oprr-next;/保存无用结点的头尾指针 qt=p3-prior;/为释放做准备 oprr-next=p3;/重接 next 链 p3-prior=oprr;/重接 prior 链qt-next=null; while(qh!=null)/释放无用结点 qq=qh; qh=qh-next;沈阳航空航天大学课程设计报告 22 free(qq);return ok;/=乘法模块=status chengfa(nodelist opr

30、1,nodelist opr2,nodelist &oprr)nodelist ph1,ph2,pt1,pt2,p3,pt3,qq;int len,cf;long buffer;ph1=opr1;pt1=ph1-prior;ph2=opr2;pt2=ph2-prior;len=length(opr1)+length(opr2);creat(oprr,len);qq=oprr-next;while(qq!=oprr)qq-data=0;qq=qq-next;buffer=cf=0;p3=oprr-prior;while(pt2!=ph2)pt1=ph1-prior;pt3=p3;while(pt

31、1!=ph1)buffer=pt1-data*pt2-data+pt3-data+cf;cf=(int)buffer/10000;pt3-data=(int)buffer%10000;pt1=pt1-prior;pt3=pt3-prior;pt3-data=cf;cf=0;pt2=pt2-prior;p3=p3-prior; return ok;沈阳航空航天大学课程设计报告 23 /=除法模块=/除法子函数int chufa_zi(nodelist &opr1,nodelist opr2)nodelist p1,p2,qh,qt,qq;int count,cf,buffer,flag;coun

32、t=0;while(compare(opr1,opr2)!=-1)/opr2 链长cf=buffer=0;p1=opr1-prior; p2=opr2-prior;while(p2!=opr2) if(p1-datadata+cf) buffer=10000+p1-data-(p2-data+cf); cf=1; else buffer=p1-data-(p2-data+cf); cf=0; p1-data=buffer;p1=p1-prior;p2=p2-prior; if(p1!=opr1)/处理 opr1 链剩下的部份buffer=p1-data-cf;p1-data=buffer; /

33、清头 0flag=0; p1=opr1-next; while(p1-data=0 & p1-next!=opr1) p1=p1-next; flag=1; if(flag)沈阳航空航天大学课程设计报告 24 qh=opr1-next;/保存无用结点的头尾指针 qt=p1-prior;/为释放做准备 opr1-next=p1;/重接 next 链 p1-prior=opr1;/重接 prior 链 qt-next=null; while(qh!=null)/释放无用结点 qq=qh; qh=qh-next; free(qq);count+;return count;/除法函数status ch

34、ufa(nodelist opr1,nodelist opr2,nodelist &quti,nodelist &remand)/quti 为商数链，remand 为余数链int len_quti,len_reman,buffer;nodelist q1,q2,pq;if(compare(opr1,opr2)=-1)/除数比被除数大creat(quti,1);quti-next-data=0;quti-next-next=quti;quti-prior=quti-next;remand=opr1;elselen_quti=length(opr1)-length(opr2); len_reman

35、=length(opr2); creat(quti,len_quti+1);/开辟商数链 creat(remand,len_reman);/开辟余数链q1=opr1-next;q2=remand-next;/q2 指向余数链 remand 的下一结点/初始化 remand 链while(q2!=remand)q2-data=q1-data;q1=q1-next;沈阳航空航天大学课程设计报告 25 q2=q2-next;pq=quti-next;q1=q1-prior;/指针退回一步while(q1!=opr1)buffer=chufa_zi(remand,opr2);pq-data=buffe

36、r;if(q1-next!=opr1)remand-prior-next=(nodelist)malloc(len);remand-prior-next-next=remand;remand-prior-next-prior=remand-prior;remand-prior=remand-prior-next;remand-prior-data=q1-next-data;if(remand-next-data=0 & remand-next-next!=remand)remand-next-next-prior=remand;remand-next=remand-next-next;q1=q1-next;pq=pq-next;pq=quti-prior;while(pq-data=?)pq=pq-prior;pq-next=quti;quti-prior=pq;return ok;/=主操作模块=status kongzhi()nodelist opr1,opr2,oprr,quti,remand;char strmax,ch;op