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

课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目： 长整数的代数计算院（系）：专 业：计算机科学与技术 班 级： 学 号： 姓 名： 指导教师： 目 录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参考文献14附 录（关键部分程序清单）15 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.1 系统功能结构框图图2.1 系统功能结构框图2.2 系统主要模块的功能说明1. 主模块kongzhi()；控制输入模块、加法模块、减法模块、乘法模块、除法模块、输出模块的循环使用。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中的数据保存到字符数组中，并且将字符数组中的数据输出到屏幕上。3 使用的数据结构的描述3.1 数据结构设计将输入的两个长整数首先保持到字符数组中，然后将字符数组中的字符转换每四个一组，利用双向循环链表来实现每一组字符的存储，并且高位在前、低位在后。每个结点中只存储四位十进制数字，即不超过9999的非负整数。利用两个双向循环链表分别保持了两个非负长整数。加法：由低位的结点开始相加，加和大于9999时，加和除以一万取余数保存到新的双向循环链表结点中，并且加和除以一万取整数作为进位加到下两个结点相加中，依次循环相加；减法：同加法有些相似，保证第一个长整数不小于于第二个长整数，结点相减，不能相减就相前一结点借位，差保存到新的双向循环链表结点中，依次循环；乘法：由低位的结点开始相乘，乘积大于9999时，乘积除以一万取余数保存到新的双向循环链表结点中，并且乘积除以一万取整数作为进位加到下两个结点乘积中，依次循环相乘；除法：开辟两个新的链表，保存商数和差。用第一个长整数循环减去第二个长整数，没减一次计数加一，计数保存到商数链表中。直到差小于第二个长整数停止循环，最后的计数为商值，差值为余数。选择该数据结构来完成长整数的加减乘除运算是因为要对长整数进行运算，需要对长整数进行存储，所以选择用链表对长整数存储，又由于存储的顺序是从左到右，而运算的顺序则是从右到左，这样位了操作方便选择循环链表，在运算过程中有进位和借位的操作，所以最终选择双向循环链表的数据结构。3.2 数据结构用法说明输入的两个长整数必须为非负长整数。加法计算时只要保证两个数都为非负数即可，减法、乘法、除法时需要保证第一个长整数大于第二个长整数。同时乘法、除法计算时第二个数不能为零，并且输入的数一定要合法，最高位不能为零，否则程序会提示输入有误。4 函数的描述4.1 主要函数设计1. shuru ()；作用：将输入的两个长整数分别保存到两个链表中。2. jiafa()；作用：将两个长整数进行加法运算，计算出二者的和。3. jianfa();作用：将两个长整数进行减法运算，计算出二者的差。4. chengfa ()；作用：将两个长整数进行乘法运算，计算出二者的积。5. chufa(); 作用: 将两个长整数进行除法运算，计算出二者的商和余数。6. shuchu();作用: 将保存到链表中的计算结果输出。4.2 主要函数流程图1. kongzhi(): 图4.2.1控制函数流程图 2. jiafa(); 图4.2.2加法函数流程图 3. jianfa(); 图4.2.3减法函数流程图4、chengfa();图4.2.4乘法函数流程图 5、chufa(); 图4.2.5除法函数流程图5程序测试和运行的结果5.1 程序测试1、程序开始菜单： 图5.1.1 菜单图 2、程序退出：图5.1.2退出程序图5.2 运行结果1、加法运算：图5.2.1除法运算图2、减法运算：图5.2.2除法运算图3、乘法运算：图5.2.3除法运算图4、除法运算：图5.2.4除法运算图6参考文献1谭浩强著. C程序设计（ 第三版）. 北京: 清华大学出版社,20052严蔚敏 吴伟明.数据结构（C语言版）.北京:清华大学出版社,20073 王裕明.数据结构与程序设计.北京:清华大学出版社，20104 谭浩强.C语言程序设计M.北京:清华大学出版社,20055 王敬华 林萍 张清国.C语言程序设计教程M.北京:清华大学出版社,2005附 录（关键部分程序清单）#include "stdafx.h"#include<string.h>#include<malloc.h>#include<conio.h>#include<stdlib.h>#define LEN sizeof(struct Node)#define MAX 1000#define OK 1#define ERROR 0#define 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(;k>0;k-)r=r*a;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' | stri<'0') /判断输入是否合法return ERROR;if(str0='0' && str1!='0')return ERROR;if(str0='-' | str0='+') && str1='0')return ERROR;if(stri!='-' && stri!='+') buffer=buffer+(stri-'0')*axp(10,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; 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"); 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 && p->data=0)/若要输出的数为0则执行stri+='0'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(j<4) if(numj!=0 | (str0='-' && str1!='0')|(str0!='-' && 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)/缓冲区部分初始化函数int i;for(i=0;i<=10;i+)stri='0'return OK;int cmplinklen(NodeList opr1,NodeList opr2) /比较链表长度函数/opr1链比opr2链长则返回1，短则返回-1，相等则返回0NodeList 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(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(len>0)p->next=(NodeList)malloc(LEN);p->next->data='?'p->next->prior=p;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 && p1->next!=opr1) p1=p1->next; p2=p2->next;if(p1->data>p2->data)return 1;else if(p1->data<p2->data)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; NodeList p1,p2,p3;oprr=(NodeList)malloc(LEN); 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->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;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 &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=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;oprr->next=p3; p3->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=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)/释放无用结点 qq=qh; qh=qh->next; 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->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;/=除法模块=/除法子函数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) 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; /清头0flag=0; p1=opr1->next; while(p1->data=0 && p1->next!=opr1) p1=p1->next; flag=1; if(flag) 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->next=quti;quti->prior=quti->next;remand=opr1;elselen_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;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->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;opr1=opr2=oprr=quti=remand=NULL;printf("=n"); printf(" 欢迎使用长整数代数计算程序n");printf("n=本程序的操作提示=n"); printf("=选择 1 将会进行加法操作=n");printf("=选择 2 将会进行减法操作=n");printf("=选择 3 将会进行乘法操作=n");printf("=选择 4 将会进行除法操作=n");printf("=选择 5 将会退出本程序 =n");printf("请选择："); ch=getche(); while(ch>'5'|ch<'1') printf("没有对应的操作选项，请重新选择：n"); ch=getchar();getchar(); switch(ch) case '1':shuru(opr1,opr2,str); printf("n相加的和为：n"); jiafa(opr1,opr2,oprr); shuchu(oprr,str);break;case '2':shuru(opr1,opr2,str); printf("n相减的差为：n"); jianfa(opr1,opr2,oprr); shuchu(oprr,str);break;case '3':shuru(opr1,opr2,str); printf("n相乘的积为：n"); chengfa(opr1,opr2,oprr); shuchu(oprr,str);break;case '4':shuru(opr1,opr2,str); while(opr2->next->data=0) printf("n除数不能为0！，请重新输入：n"); scanf("%s",str); zhuanhuan(str,opr2); printf("n商数为：n"); chufa(opr1,opr2,quti,remand); shuchu(quti,str); printf("n余数为：n"); shuchu(remand,str);break;case '5':exit(0);