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

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

2、 .14附录（关键部分程序清单）. 15I沈阳航空航天大学课程设计报告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();将一

3、百位以上的长整数进行乘法运算，计算出积。4. chufa();将一百位以上的长整数进行除法运算，计算出商和余数。1沈阳航空航天大学课程设计报告2 系统功能模块结构图2.1 系统功能结构框图主模块输入模块减加乘除法法法法模模模模块块块块输出模块图 2.1系统功能结构框图2.2 系统主要模块的功能说明1. 主模块kongzhi()；2沈阳航空航天大学课程设计报告控制输入模块、加法模块、减法模块、乘法模块、除法模块、输出模块的循环使用。2. 输入模块shuru();将输入的两组长整数分别通过转换将其转换成所需要的形式存储到两个链表（ opr1、opr2）中保存起来。3. 加法模块 jiafa();将

4、链表 opr1、 opr2 中的数据进行加法运算，并且二者的将加和保存到链表 oprr 中。4. 减法模块jianfa();将链表 opr1、opr2 中的数据进行减法运算，并且将二者的差保存到链表oprr 中。5. 乘法模块chengfa();将链表 opr1、 opr2 中的数据进行乘法运算，并且将二者的乘积保存到链表 oprr 中。6. 除法模块chufa();将链表 opr1、 opr2 中的数据进行加法运算，并且将二者的商和余数分别保存到链表 quti、remand 中。7. 输出模块 shuchu();将链表 oprr、quti、remand中的数据保存到字符数组中，并且将字符数组

5、中的数据输出到屏幕上。3沈阳航空航天大学课程设计报告3 使用的数据结构的描述3.1数据结构设计将输入的两个长整数首先保持到字符数组中，然后将字符数组中的字符转换每四个一组，利用双向循环链表来实现每一组字符的存储，并且高位在前、低位在后。每个结点中只存储四位十进制数字， 即不超过 9999 的非负整数。利用两个双向循环链表分别保持了两个非负长整数。加法：由低位的结点开始相加，加和大于 9999 时，加和除以一万取余数保存到新的双向循环链表结点中， 并且加和除以一万取整数作为进位加到下两个结点相加中，依次循环相加；减法：同加法有些相似，保证第一个长整数不小于于第二个长整数，结点相减，不能相减就相前

6、一结点借位，差保存到新的双向循环链表结点中，依次循环；乘法：由低位的结点开始相乘，乘积大于 9999 时，乘积除以一万取余数保存到新的双向循环链表结点中，并且乘积除以一万取整数作为进位加到下两个结点乘积中， 依次循环相乘；除法：开辟两个新的链表，保存商数和差。用第一个长整数循环减去第二个长整数，没减一次计数加一，计数保存到商数链表中。直到差小于第二个长整数停止循环，最后的计数为商值，差值为余数。选择该数据结构来完成长整数的加减乘除运算是因为要对长整数进行运算，需要对长整数进行存储，所以选择用链表对长整数存储，又由于存储的顺序是从左到右，而运算的顺序则是从右到左，这样位了操作方便选择循环链表，在

7、运算过程中有进位和借位的操作，所以最终选择双向循环链表的数据结构。3.2数据结构用法说明输入的两个长整数必须为非负长整数。加法计算时只要保证两个数都为非负数即可，减法、乘法、除法时需要保证第一个长整数大于第二个长整数。同时乘法、除法计算时第二个数不能为零，并且输入的数一定要合法， 最高位不能为零，否则程序会提示输入有误。4沈阳航空航天大学课程设计报告4 函数的描述4.1主要函数设计1. shuru ()；作用：将输入的两个长整数分别保存到两个链表中。2. jiafa() ；作用：将两个长整数进行加法运算，计算出二者的和。3. jianfa();作用：将两个长整数进行减法运算，计算出二者的差。4

8、. chengfa ()；作用：将两个长整数进行乘法运算，计算出二者的积。5. chufa();作用 : 将两个长整数进行除法运算，计算出二者的商和余数。6. shuchu();作用 : 将保存到链表中的计算结果输出。5沈阳航空航天大学课程设计报告4.2 主要函数流程图1. kongzhi():开始输入 ch判断 ch12345调调调调用用用用退加减乘除出法法法法程函函函函序数数数数输出和输出差输出积输出商结束图 4.2.1控制函数流程图6沈阳航空航天大学课程设计报告2. jiafa();开始NodeList p1=opr1,p2=opr2,p3=oprr；是否有进位YN将链表opr1、 op

9、r2中将链表opr1、 opr2的对应结点中数据加中的对应结点中数和并加上进位据加和Y和大于一万N和除以一万取余保和保存到链表存到链表oprr中oprr 中和除以一万取整保存为进位移动指针p1 、 p2判断指针p1,p2NY是否指向头指针N若 p1 没有指向头指针若 p2 没有指向头指针YYN将 opr1 中剩余结点将 opr2中剩余结点数据保存到oprr中数据保存到oprr中结束图 4.2.2加法函数流程图7沈阳航空航天大学课程设计报告3. jianfa();开始NodeList p1=opr1,p2=opr2,p3=oprr；判断链表opr1 中结点的数Y据大于 opr2 中对应结点的数据

10、N是否有借位YN将链表 opr1、 opr2将链表 opr1、 opr2将链表 opr1 中结点数据中的对应结点中数中的对应结点中数加上一万后减去opr2中据作差并减去1据作差的对应结点中数据差保存到链表Noprr 中移动指针p1 、 p2判断指针p2 是否指向头指针Y若 p1 没有指向头指针YN将 opr1 中剩余结点数据保存到 oprr 中结束图 4.2.3减法函数流程图8沈阳航空航天大学课程设计报告4、 chengfa();开始NodeList p1=opr1,p2=opr2,p3=oprr；是否有进位YN将链表opr1、 opr2中将链表opr1、 opr2的结点中数据相乘并中的结点中

11、数据相加上进位乘和大于一万YN积除以一万取余保积保存到链表存到链表oprr中oprr中和除以一万取整保存为进位移动指针p1若 p1 没有指向头指针YNY是否有进位N保存进位进位为零移动指针p2Y若 p2 没有指向头指针N结束图 4.2.4乘法函数流程图9沈阳航空航天大学课程设计报告5、chufa();开始NodeList P1=opr1,p2=opr2,quti,remand；是否需要借位YN将链表 opr1 结点中数将链表 opr1 、 opr2据加一万后减去opr2中的结点中数据相结点数据并减借位减差保存到链表 remand中移动指针 p2计数加一并将计数保存到链表 qutiY若 p2没有

12、指向头指针NY链表 remand中数据是否大于链表 opr2 中数据N结束图 4.2.5除法函数流程图10沈阳航空航天大学课程设计报告5 程序测试和运行的结果5.1 程序测试1、程序开始菜单：图 5.1.1菜单图2、程序退出 ：图 5.1.2退出程序图11沈阳航空航天大学课程设计报告5.2 运行结果1、加法运算：图 5.2.1除法运算图2、减法运算：图 5.2.2除法运算图12沈阳航空航天大学课程设计报告3、乘法运算：图 5.2.3除法运算图4、除法运算：图 5.2.4除法运算图13沈阳航空航天大学课程设计报告6 参考文献1 谭浩强著 . C 程序设计（ 第三版） . 北京 : 清华大学出版社

13、 ,20052 严蔚敏 吴伟明 .数据结构（ C 语言版） .北京 :清华大学出版社 ,20073 王裕明 . 数据结构与程序设计 . 北京 : 清华大学出版社， 20104 谭浩强 .C 语言程序设计 M. 北京 : 清华大学出版社 ,20055 王敬华 林萍 张清国 .C 语言程序设计教程 M. 北京 : 清华大学出版社 ,200514沈阳航空航天大学课程设计报告附录（关键部分程序清单）#include "stdafx.h"#include<string.h>#include<malloc.h>#include<conio.h>#in

14、clude<stdlib.h>#define LEN sizeof(struct Node)#define MAX 1000#define OK1#define ERROR0#define OVERFLOW -1#define TRUE1#define FALSE 0typedef int Status;typedef struct Nodeint data;struct Node *prior,*next;Node,*NodeList;int axp(int a,int k) / 求指数函数值int r=1;if(k=0)return 1;for(;k>0;k-)r=r*a

15、;return r;Status zhuanhuan(char str,NodeList &oprh) /输入转换函数/ 将字符串形式的操作数转换成所需的类型NodeList p;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!='-' && str0!='+')&&(stri>'9

16、' | stri<'0') /判断输入是否合法return ERROR;15沈阳航空航天大学课程设计报告if(str0='0' && str1!='0')return ERROR;if(str0='-' | str0='+') && str1='0')return ERROR;if(stri!='-' && stri!='+')buffer=buffer+(stri-'0')*axp(10,

17、k);k+;if(k=4 | stri-1='-' | stri-1='+' | i=0)p=(NodeList)malloc(LEN);/将新建结点插入到头结点之后oprh->next->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 flag=OK;p

18、rintf("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);wh

19、ile(!flag)printf(" 整数输入有误，请重新输入：n");16沈阳航空航天大学课程设计报告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=o

20、prr && p->data=0)/若要输出的数为0 则执行stri+='0'elsewhile(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(j<4)if(numj!=0 | (str0='-' && str1!='0')|(str0!='-&

21、#39; && str0!='0')/此判断语句是为了避免输出诸如：00123 的情况stri+=numj+'0'/?j+;p=p->next;j=0;stri='0'printf("%s",str);printf("n");return OK;Status initbuf(char str)/ 缓冲区部分初始化函数17沈阳航空航天大学课程设计报告int i;for(i=0;i<=10;i+)stri='0'return OK;int cmplinklen(Nod

22、eList opr1,NodeList opr2) /比较链表长度函数/opr1 链比 opr2 链长则返回 1，短则返回 -1，相等则返回 0 NodeList p1,p2;p1=opr1->prior;p2=opr2->prior;while(p1->prior!=opr1 && p2->prior!=opr2)p1=p1->prior;p2=p2->prior;if(p1->prior!=opr1)return 1;if(p2->prior!=opr2)return -1;return 0;int length(NodeLi

23、st 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(len>0)p->next=(NodeList)malloc(LEN);p->next->data='?'p->next->prior=p;18沈

24、阳航空航天大学课程设计报告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

25、->data=p2->data && p1->next!=opr1)p1=p1->next;p2=p2->next;if(p1->data>p2->data)return 1;else if(p1->data<p2->data)return -1;elsereturn 0;/-初始化链表函数-Status init(NodeList &oppr)oppr=NULL;return OK;/=加法模块 =Status jiafa(NodeList opr1,NodeList opr2,NodeList &am

26、p;oprr)/本算法实现A,B 相加的操作int CF,buffer;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/

27、 将新建结点插入到头结点之后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 的值大于

28、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/ 将新建结点插入到头结点之后

29、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;if(CF)p3=(NodeList)malloc(LEN);oprr->next->prior=p3;p3->prior=oprr;p3->next=oprr->next;oprr->next=p3;p3->data

30、=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)malloc(LEN);oprr->next=oprr;oprr->prior=oprr;p1=opr1->prior;p2=opr2->prior;CF=buffer

31、=flag=0;while(p2!=opr2)/opr2链的长度小于等于opr1 链的if(p1->data<(p2->data+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;21沈阳航空航天大学课程设计报告oprr->next=p3;p3

32、->data=buffer;p1=p1->prior;p2=p2->prior;while(p1!=opr1)/ 处理 opr1 链剩下的部分if(p1->data<CF)buffer=10000+p1->data-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=

33、p1->prior;/ 处理链表开头结点值为 0 的无意义情况，若链表本身表示 0，则不做如下处理 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)/ 释放无用结

34、点qq=qh;qh=qh->next;22沈阳航空航天大学课程设计报告free(qq);return OK;/=乘法模块 =Status chengfa(NodeList opr1,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->nex

35、t;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->

36、;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;count=0;while(compare(opr1,opr2)!=-1)/opr2链长CF=buffer=0;p1=opr1->prior;p2=opr2->prior;while(p2!=opr2)if(p1->data<(p2->data+CF)b

37、uffer=10000+p1->data-(p2->data+CF);CF=1;elsebuffer=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;/ 清头 0flag=0; p1=opr1->next;while(p1->data=0 && p1->next!=opr1)p1=p1->

38、;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 chufa(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