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

沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目： 长整数的代数计算长整数的代数计算 院（系）：计算机学院 专 业：计算机科学与技术 班 级： 学 号： 姓 名： 指导教师： 沈阳航空航天大学课程设计报告 I 目目 录录 1 题目介绍和功能要求题目介绍和功能要求.1 1.1 题目介绍 .1 1.2 功能要求 .1 1.3 基本功能 .1 2 系统功能模块结构图系统功能模块结构图.2 2.1 系统功能结构框图.2 2.2 系统主要模块的功能说明.2 3 使用的数据结构的描述使用的数据结构的描述.4 3.1 数据结构设计 .4 3.2 数据结构用法说明 .4 4 函数的描述函数的描述.5 4.1 主要函数设计.5 4.2 主要函数流程图.6 5 程序测试和运行的结果程序测试和运行的结果.11 5.1 程序测试.11 5.2 运行结果.12 6 参考文献参考文献.14 附附 录（关键部分程序清单）录（关键部分程序清单）.15 沈阳航空航天大学课程设计报告 1 1 题目介绍和功能要求 1.1 题目介绍题目介绍 设计数据结构完成长整数的表示和存储，并编写算法来实现两个长整数的 加、减、乘、除等基本代数运算。 1.2 功能要求功能要求 1) 长整数长度在一百位以上。 2） 实现两长整数在同余代数下的加、减、乘、除操作。即实现算法来求解 a+b mod n，a-b mod n，a*b mod n，ab mod n。 3）输入输出均在文件中。 （选作） 1.3 基本功能基本功能 1.jiafa(); 将一百位以上的长整数进行加法运算，计算出和。 2.jianfa(); 将一百位以上的长整数进行减法运算，计算出差。 3.chenfa(); 将一百位以上的长整数进行乘法运算，计算出积。 4.chufa(); 将一百位以上的长整数进行除法运算，计算出商和余数。 沈阳航空航天大学课程设计报告 2 2 系统功能模块结构图 2.1 系统功能结构框图系统功能结构框图 主模块 输入模块 减 法 模 块 加 法 模 块 乘 法 模 块 除 法 模 块 输出模块 图图 2.12.1 系统功能结构框图系统功能结构框图 2.2 系统主要模块的功能说明系统主要模块的功能说明 1. 主模块 kongzhi()； 沈阳航空航天大学课程设计报告 3 控制输入模块、加法模块、减法模块、乘法模块、除法模块、输出模块 的循环使用。 2. 输入模块 shuru(); 将输入的两组长整数分别通过转换将其转换成所需要的形式存储到两个 链表（opr1、opr2）中保存起来。 3. 加法模块 jiafa(); 将链表 opr1、opr2 中的数据进行加法运算，并且二者的将加和保存到链 表 oprr 中。 4. 减法模块 jianfa(); 将链表 opr1、opr2 中的数据进行减法运算，并且将二者的差保存到链表 oprr 中。 5. 乘法模块 chengfa(); 将链表 opr1、opr2 中的数据进行乘法运算，并且将二者的乘积保存到链 表 oprr 中。 6. 除法模块 chufa(); 将链表 opr1、opr2 中的数据进行加法运算，并且将二者的商和余数分别 保存到链表 quti、remand 中。 7. 输出模块 shuchu(); 将链表 oprr、quti、remand 中的数据保存到字符数组中，并且将字符数组 中的数据输出到屏幕上。 沈阳航空航天大学课程设计报告 2 4 3 使用的数据结构的描述 3.1 数据结构设计数据结构设计 将输入的两个长整数首先保持到字符数组中，然后将字符数组中的字符转换 每四个一组，利用双向循环链表来实现每一组字符的存储，并且高位在前、低位 在后。每个结点中只存储四位十进制数字，即不超过 9999 的非负整数。利用两 个双向循环链表分别保持了两个非负长整数。加法：由低位的结点开始相加，加 和大于 9999 时，加和除以一万取余数保存到新的双向循环链表结点中，并且加 和除以一万取整数作为进位加到下两个结点相加中，依次循环相加；减法：同加 法有些相似，保证第一个长整数不小于于第二个长整数，结点相减，不能相减就 相前一结点借位，差保存到新的双向循环链表结点中，依次循环；乘法：由低位 的结点开始相乘，乘积大于 9999 时，乘积除以一万取余数保存到新的双向循环 链表结点中，并且乘积除以一万取整数作为进位加到下两个结点乘积中，依次循 环相乘；除法：开辟两个新的链表，保存商数和差。用第一个长整数循环减去第 二个长整数，没减一次计数加一，计数保存到商数链表中。直到差小于第二个长 整数停止循环，最后的计数为商值，差值为余数。 选择该数据结构来完成长整数的加减乘除运算是因为要对长整数进行运算， 需要对长整数进行存储，所以选择用链表对长整数存储，又由于存储的顺序是从 左到右，而运算的顺序则是从右到左，这样位了操作方便选择循环链表，在运算 过程中有进位和借位的操作，所以最终选择双向循环链表的数据结构。 3.2 数据结构用法说明数据结构用法说明 输入的两个长整数必须为非负长整数。加法计算时只要保证两个数都为非负 数即可，减法、乘法、除法时需要保证第一个长整数大于第二个长整数。同时乘 法、除法计算时第二个数不能为零，并且输入的数一定要合法，最高位不能为零， 否则程序会提示输入有误。 沈阳航空航天大学课程设计报告 5 4 函数的描述 4.1主要函数设计主要函数设计 1. shuru ()； 作用作用：将输入的两个长整数分别保存到两个链表中。 2. jiafa()； 作用作用：将两个长整数进行加法运算，计算出二者的和。 3. jianfa(); 作用作用：将两个长整数进行减法运算，计算出二者的差。 4. chengfa ()； 作用作用：将两个长整数进行乘法运算，计算出二者的积。 5. chufa(); 作用作用: 将两个长整数进行除法运算，计算出二者的商和余数。 6. shuchu(); 作用作用: 将保存到链表中的计算结果输出。 沈阳航空航天大学课程设计报告 6 4.2 主要函数流程图主要函数流程图 1. kongzhi(): 开始 判断ch 输入ch 调 用 加 法 函 数 调 用 减 法 函 数 调 用 乘 法 函 数 调 用 除 法 函 数 退 出 程 序 结束 输出和输出差输出积输出商 1 2345 图图 4.2.14.2.1 控制函数流程图控制函数流程图 沈阳航空航天大学课程设计报告 7 2. jiafa(); 开始 NodeList p1=opr1,p2=opr2,p3=oprr； 将链表opr1、opr2中 的对应结点中数据加 和并加上进位 移动指针p1、p2 判断指针p1,p2 是否指向头指针 若p1没有指向头指针 和除以一万取 整保存为进位 和保存到链表 oprr中 和大于一万 是否有进位 和除以一万取余保 存到链表oprr中 将链表opr1、opr2 中的对应结点中数 据加和 若p2没有指向头指针 将opr1中剩余结点 数据保存到oprr中 将opr2中剩余结点 数据保存到oprr中 结束 YN YN Y N Y N N Y 图图 4.2.24.2.2 加法函数流程图加法函数流程图 沈阳航空航天大学课程设计报告 8 3. jianfa(); 开始 NodeList p1=opr1,p2=opr2,p3=oprr； 将链表opr1、opr2 中的对应结点中数 据作差并减去1 移动指针p1、p2 判断指针p2是否 指向头指针 若p1没有指向头指针 差保存到链表 oprr中 是否有借位 将链表opr1中结点数据 加上一万后减去opr2中 的对应结点中数据 将opr1中剩余结点 数据保存到oprr中 结束 Y N N Y N Y 判断链表opr1中结点的数 据大于opr2中对应结点的 数据 将链表opr1、opr2 中的对应结点中数 据作差 YN 图图 4.2.34.2.3 减法函数流程图减法函数流程图 沈阳航空航天大学课程设计报告 9 4、chengfa(); 开始 NodeList p1=opr1,p2=opr2,p3=oprr； 将链表opr1、opr2中 的结点中数据相乘并 加上进位 移动指针p1 若p1没有指向头指针 和除以一万取 整保存为进位 积保存到链表 oprr中 和大于一万 是否有进位 积除以一万取余保 存到链表oprr中 将链表opr1、opr2 中的结点中数据相 乘 若p2没有指向头指针 结束 Y N Y N Y N Y N N Y 是否有进位 保存进位 进位为零 移动指针p2 图图 4.2.44.2.4 乘法函数流程图乘法函数流程图 沈阳航空航天大学课程设计报告 10 5、chufa(); 开始 NodeList P1=opr1,p2=opr2,quti,remand； 将链表opr1结点中数 据加一万后减去opr2 结点数据并减借位 移动指针p2 链表remand中数据是否 大于链表opr2中数据 是否需要借位 差保存到链表remand中 将链表opr1、opr2 中的结点中数据相 减 若p2没有指向头指针 结束 Y N Y N Y N 计数加一并将计数 保存到链表quti 图图 4.2.54.2.5 除法函数流程图除法函数流程图 沈阳航空航天大学课程设计报告 11 5 程序测试和运行的结果 5.1 程序测试程序测试 1、程序开始菜单： 图图 5.1.15.1.1 菜单图菜单图 2、程序退出： 图图 5.1.25.1.2 退出程序图退出程序图 沈阳航空航天大学课程设计报告 12 5.2 运行结果运行结果 1、加法运算： 图图 5.2.15.2.1 除法运算图除法运算图 2、减法运算： 图图 5.2.25.2.2 除法运算图除法运算图 沈阳航空航天大学课程设计报告 13 3、乘法运算： 图图 5.2.35.2.3 除法运算图除法运算图 4、除法运算： 图图 5.2.45.2.4 除法运算图除法运算图 沈阳航空航天大学课程设计报告 2 14 6 参考文献 1谭浩强著. C 程序设计（ 第三版）. 北京: 清华大学出版社,2005 2严蔚敏 吴伟明.数据结构（C 语言版）.北京:清华大学出版社,2007 3 王裕明.数据结构与程序设计.北京:清华大学出版社，2010 4 谭浩强.C 语言程序设计M.北京:清华大学出版社,2005 5 王敬华 林萍 张清国.C 语言程序设计教程M.北京:清华大学出版社,2005 沈阳航空航天大学课程设计报告 15 附 录（关键部分程序清单） #include stdafx.h #include #include #include #include #define LEN sizeof(struct Node) #define MAX 1000 #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define TRUE 1 #define FALSE 0 typedef 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 int i,k,buffer; 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!=- p-prior=oprh; p-next=oprh-next; oprh-next=p; p-data=buffer; buffer=k=0; return OK; Status shuru(NodeList 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); 沈阳航空航天大学课程设计报告 17 scanf(%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 else while(p!=oprr) num0=p-data/1000; num1=(p-data-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)/缓冲区部分初始化函数 沈阳航空航天大学课程设计报告 18 int i; for(i=0;iprior; p2=opr2-prior; while(p1-prior!=opr1 p2=p2-prior; 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=(NodeList)malloc(LEN); p=oprr; while(len0) p-next=(NodeList)malloc(LEN); p-next-data=?; p-next-prior=p; 沈阳航空航天大学课程设计报告 19 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 -1; else/长度相等的情况 while(p1-data=p2-data p2=p2-next; if(p1-datap2-data) return 1; else if(p1-datadata) return -1; else return 0; /-初始化链表函数- Status init(NodeList return OK; /=加法模块= Status jiafa(NodeList opr1,NodeList opr2,NodeList NodeList p1,p2,p3; oprr=(NodeList)malloc(LEN); 沈阳航空航天大学课程设计报告 20 oprr-next=oprr; oprr-prior=oprr; p1=opr1-prior; p2=opr2-prior; CF=buffer=0; while(p1!=opr1 CF=buffer/10000;/若 buffer 的值大于 9999 则产生进位，赋给 CF /将新建结点插入到头结点之后 p3=(NodeList)malloc(LEN); oprr-next-prior=p3; p3-prior=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; 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; 沈阳航空航天大学课程设计报告 21 oprr-next=p3; p3-data=buffer%10000; p2=p2-prior; 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 NodeList p1,p2,p3,qh,qt,qq; oprr=(NodeList)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; else buffer=p1-data-(p2-data+CF); CF=0; p3=(NodeList)malloc(LEN); oprr-next-prior=p3; p3-prior=oprr; p3-next=oprr-next; 沈阳航空航天大学课程设计报告 22 oprr-next=p3; p3-data=buffer; p1=p1-prior; p2=p2-prior; while(p1!=opr1) /处理 opr1 链剩下的部分 if(p1-datadata-CF; CF=1; else buffer=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，则不做如下处理 p3=oprr-next; while(p3-data=0 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; 沈阳航空航天大学课程设计报告 23 free(qq); return OK; /=乘法模块= Status chengfa(NodeList opr1,NodeList opr2,NodeList 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(pt1!=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; 沈阳航空航天大学课程设计报告 24 /=除法模块= /除法子函数 int chufa_zi(NodeList int count,CF,buffer,flag; count=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; /清头 0 flag=0; p1=opr1-next; while(p1-data=0 flag=1; if(flag) 沈阳航空航天大学课程设计报告 25 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 chufa(NodeList opr1,NodeList opr2,NodeList 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; else len_quti=length(opr1)-length(opr2); len_reman=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; 沈阳航空航天大学课程设计报告 26 q2=q2-next; pq=quti-next; q1=q1-prior;/指针退回一步 while(q1!=opr1) buffer=chufa_zi(remand,opr2); pq-data=buffer; 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=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; opr1=opr2=oprr=quti=remand=NULL; printf(=n); print