打印版 课程设计 长整数四则运算.doc

数据结构课程设计报告 题目：长整数四则运算 学 院 计算机学院 专 业 计算机科学与技术 年级班别 2009级 2班 学 号 3109005945 学生姓名 彭伟湘 指导教师 吴伟民 成 绩 _2011年7月数据结构课程设计报告1实验报告：1.4 长整数四则运算3一、 实验内容3【问题描述】3【基本要求】3【实现基本功能】3【实现加强版本的功能】3【加强版的实现原理】【特色分析】3二、 实验目的4三、实验文档4四、 概要设计4五、 详细设计61、头文件的定义部分62、输入模块：73、输出模块：84、 预处理相关项操作模块（双向链表的相关ADT的操作）：95、 加减法模块115、 乘法模块156、 除法模块177、 乘方与阶乘运算模块：198、 主操作模块：20六、 调试分析23七、 用户手册23八、测试结果23九、附录27十、实验总结27十一、源代码附录27实验报告：1.4 长整数四则运算1、 实验内容【问题描述】 设计一个实现任意长的整数进行加法运算的演示程序【基本要求】利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(215 - 1)(215 - 1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。【实现基本功能】(i)是想长整数的四则运算；(ii)实现长整数的乘方和阶乘运算；(iii)整形量范围是-（2n-1）（2n-1），其中n是由程序读入的参量。输入数据的分组方法另行规定；【实现加强版本的功能】(i)四则运算在原来版本的基础上支持小数运算，除法还可以通过输入整数后加小数点与相应要求取的精确位数求出精确值，如：求取3666除以7的后三位精确值，可以在输入时将除数输入为3666.000或3666.0000，就能得出相应的精确位数，当然求取后，没有余数的输出；(ii)乘方的功能也进行了强化，支持小数操作；(iii)添加了多个出错处理（即输入重操作）对相应数据输入与输出进行提示；【加强版的实现原理】(i)加减法运算加强：在原来版本的基础上依照基本的加减法操作将数据用小数点进行分隔，记录下连个输入数的小数位长度，并将小数位较短的一个数据后补0直至小数位数相同，然后用函数处理输出的数据；(ii)乘除法、乘方：其处理方法较为简单，主要是记录数据中小数位数的长度，然后通过每种运算方式不同的运算原理截取小数位，再按照输出格式将数据处理进行输出；(iii)根据定义，阶乘保持不变；【特色分析】(i)加强版程序加上了简单的声音提示，无论是输入与输出均会有八个音符的其中之一对输入与输出与否进行提示，同时在输入输出数据出错时，还会用三个音符对重输入进行提示，增强了人性化操作；【测试数据】 （1）0；0；应输出“0”。（2）-2345,6789；-7654,3211；应输出“-1,0000,0000”。（3）-9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。（4）1,0001,0001；-1,0001,0001；应输出“0”。（5）1,0001,0001；-1,0001,0000；应输出“1”。（6）-9999,9999,9999；-9999,9999,9999；应输出“1,9999,9999,9998”。（7）1,0000,9999,9999；1；应输出“1,0001,0000,0000”。2、 实验目的、熟悉掌握双向循环链表的基本操作；、熟悉任意长字符串的输入，并实现把字符串转化为整数；、熟悉任意长整数的加法运算；、更进一步掌握有关类的操作三、实验文档长整数四则运算需求分析 (i)本程序实现计算任意长的整数的加法运算. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就计算并显示出这两个数的运算。(ii)本演示程序中，集合的元素限定为数字字符09和字符，与；，输入字符可以任意长，输入形式以“回车符”为结束标志，串中字符顺序不限，且允许出现重复字符。(iii)利用双向循环链表现实长整数的存储，每个结点含一个整形变量。输入的形式以回车结束，可以直接输入正数或负数。按中国对于长整数的表示习惯，每四位一组，除数字和位于首位置的负号外，其它一切字符都将作为分隔符，连续多个分隔符当一个处理。但不使用分隔符也不影响结果。(iv)自行定义的测试数据(1)0; 0; 输出“0”;(2)-2345,6789;；-7654,3211;；加法输出 “-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,0000;；减法输出 ”1”；(6)-9999,9999,9999;；-9999,9999,9999； 加法输出“-1,9999,9999,9998”；(7)1,0000,9999,9999； 1； 加法输出 1,0001,0000,0000；(8)10；8；乘方输出1,0000,0000；(9) -98,9997；3；除法输出-32,9999；6；阶乘输出720；4、 概要设计为实现上述程序功能，应以双向循环链表表示长整数。为此，需要定义一个抽象数据类型1、抽象数据类型定义为：ADT OrderedOperation数据对象：D=ai|aiint,i=1,2,.n, n0数据关系：R1=|ai-1,aiD|=2,n 基本操作：Status conversion(str,oprh)/操作结果：输入转换函数，将字符串形式的操作数转换成所需的类型cmplinklen( opr1, opr2)/操作结果：比较链表长度函数,opr1链比opr2链长则返回1，短则返回-1，否则返/回0length( oprr)/操作结果：求链表长度Status Creat(oprr,len)/操作结果：生成指定长度链表compare(opr1,opr2)/操作结果：比较opr1、opr2绝对值的大小Status init(oppr)/初始化链表函数Status distroy(oprr)/销毁链表函数Status evaluate(opri,i)/操作结果：链表短赋值函数，将i的值转换成万进制类型，i为整形变量Status add_bas(opr1,opr2,oprr)/操作结果：加法基本操作，本算法实现A,B相加的操作。Status sub_bas(opr1,opr2,oprr)/减法基本操作，本算法实现A,B相减的操作Status add(opr1,opr2,oprr)/操作结果：带符号加法运算Status sub(opr1,opr2,oprr)/操作结果：带符号减法函数Status imul(opr1,opr2,oprr)/操作结果：乘法运算Status idiv(opr1,opr2,quti,remand)/操作结果：除法运算Status imul_power(opr1,n,oprr)/操作结果：乘方运算，运用了二分思想，时间长度为lgN Status imul_factorial(opr1,oprr)/操作结果：阶乘运算Status output(oprr,str)/操作结果：输出的数据按四位一组，分隔符为,的格式ADT OrderedOperation链表抽象数据类型的定义：ADT List数据对象：D=ai|aiElemSet, i=1,2, ,n, n0数据关系：R1=|ai-1,aiD, i=1,2, ,n 基本操作：Status initbuf(char str)/操作结果：缓冲区部分初始化函数，返回OKint cmplinklen(NodeList opr1,NodeList opr2)/操作结果：opr1链比opr2链长则返回1，短则返回-1，否则返回0int length(NodeList oprr)/操作结果：计算链表长度，并返回链表长度的操作数Status Creat(NodeList &oprr,int len)/操作结果：生成指定长度链表，返回OKint compare(NodeList opr1,NodeList opr2)/操作结果：比较opr1、opr2绝对值的大小Status init(NodeList &oppr)/操作结果：初始化链表函数Status distroy(NodeList &oprr)/操作结果：销毁链表函数，返回OKStatus evaluate(NodeList &opri,int i)/操作结果：链表短赋值函数，将i的值转换成万进制类型，i为整形变量ADT OrderedList2、 本程序大体包含三个模块：(i)主程序模块：void main() 初始化；do 接受命令； 处理命令；while(“命令”=”退出”)(ii)集合单元模块实现集合的抽象数据类型(iii)结点结构单元模块定义集合的结点结构主程序各模块之间的关系如下：集合单元模块结点结构单元模块3、本程序细分为以下几大功能模块：(i)输入模块；(ii)输出模块；(iii)预处理及相关操作模块(iv)四则预算模块及(包含乘方、阶乘)；(v)主操作模块；5、 详细设计1、头文件的定义部分#include #include#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 0typedef char _TCHAR; typedef int Status;2、输入模块：/求指数函数值int axp(int a,int k)if(k=0)return 1; /k指数为零的情况for(;k0;k-) /指数结果处理r=r*a;return r;/输入转换函数Status conversion(char str,NodeList &oprh)/将字符串形式的操作数转换成所需的类型k=buffer=0;oprh=(NodeList)malloc(LEN); /申请长整数由字符串转换为链表的存储空间oprh-next=oprh;oprh-prior=oprh;/初始化链表的前驱指针prior指针与后驱指针nextfor(i=strlen(str)-1;i=0;i-) /出错判断处理，规范输入格式；若输入格式出错，则跳出转换程，并序重新输入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;/根据字符串输入的首位字符，确定链表的数据类型是正整数还是负整数，返回OK/输入函数Status input(NodeList &opr1,NodeList &opr2,char str) /分别输入连个字符串并进行判断，直至输入成功则返回OKStatus input1(NodeList &opr1,int &n,char str)/分别输入乘方的底数和指数两个操作数，直至输入成功返回OKStatus input2(NodeList &oprr,char str)/只是输入阶乘的一个正整数，直至输入成功返回OK3、输出模块：/输出函数Status output(NodeList oprr,char str)if(!oprr)return ERROR; /判断用链表记录的运算结果是否为空（出错），返回FALSEp=oprr; /指针对链表进行遍历initbuf(str); /清空字符串数组str的内容 /符号位判断，若为负数，在字符串的首位加p=p-next;if(p-next=oprr & p-data=0)/若要输出的数为0则执行stri+=0;else while(p!=oprr)/每千位进行取余数运算 while(jnext;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-next!=opr1这个条件 p1=p1-next; p2=p2-next;/比较长度，分别返回操作值-1,0,1Status init(NodeList &oppr)/初始化链表函数Status distroy(NodeList &oprr)/销毁链表函数，返回OK/distroyStatus evaluate(NodeList &opri,int i)/链表短赋值函数，将i的值转换成万进制类型，i为整形变量opri=(NodeList)malloc(LEN);opri-data=+;opri-next=(NodeList)malloc(LEN);opri-next-data=i;opri-next-next=opri;opri-prior=opri-next;opri-next-prior=opri;return OK;/evaluate5、 加减法模块/加法基本操作Status add_bas(NodeList opr1,NodeList opr2,NodeList &oprr)/本算法实现A,B相加的操作。oprr=(NodeList)malloc(LEN); /初始化前驱指针prior与后驱指针next，并用p1,p2进行指针操作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-data=buffer%10000;/应该将buffer的第四位赋给p3-data /./指针进入下一个双向链表的结点 while(p1!=opr1)/处理opr1链的剩余部分buffer=p1-data+CF;CF=buffer/10000;/将新建结点插入到头结点之后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;/将新建结点插入到头结点之后p3=(NodeList)malloc(LEN); oprr-next-prior=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;/添加长整数类型符号，并返回OK/减法基本操作Status sub_bas(NodeList opr1,NodeList opr2,NodeList &oprr)/本算法实现A,B相减的操作。 /将A链分成与B链长相等的底位部分,和剩余的高位部分,并做相应处理。oprr=(NodeList)malloc(LEN); /前驱指针prior与后驱指针next置空，并用p1,p2进行指针操作CF=buffer=flag=0;while(p2!=opr2)/opr2链的长度小于等于opr1链的if(p1-datadata+CF)/判断进位CF，并进行进位操作p3=(NodeList)malloc(LEN); oprr-next-prior=p3; /前驱指针与后驱指针互换 p3-data=buffer;p1=p1-prior;p2=p2-prior;while(p1!=opr1)/处理opr1链剩下的部分if(p1-datanext-prior=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); /-/添加符号，返回OK/带符号加法函数Status add(NodeList opr1,NodeList opr2,NodeList &oprr)/出错处理：若opr1或opr2为空，返回FALSEif(opr1-data=opr2-data)/opr1,opr2符号相同add_bas(opr1,opr2,oprr);if(opr1-data=+)/opr1与opr2均为正数，即A+B的形式(A,B均是正数，下同)oprr-data=+;else/opr1与opr2均为负数，即(-A)+(-B)的形式oprr-data=-;/if(opr1-data=opr2-data)else/符号不相同if(opr1-data=+)/A+(-B)的情况if(compare(opr1,opr2)=-1)/Adata=-;/if(compare(opr1,opr2)=-1)else/A=B的情况sub_bas(opr1,opr2,oprr);oprr-data=+;/else/if(opr1-data=+ & opr2-data=-)else/(-A)+B的情况if(compare(opr1,opr2)=1)/AB的情况sub_bas(opr1,opr2,oprr);oprr-data=-;/if(compare(opr1,opr2)=1)else/Adata=+;/else/else/elsereturn OK;/add/带符号减法函数Status sub(NodeList opr1,NodeList opr2,NodeList &oprr)if(opr1=NULL | opr2=NULL)return ERROR;if(opr1-data=opr2-data)/opr1,opr2符号相同if(opr1-data=+)/A-B的情况if(compare(opr1,opr2)=-1)/Adata=-;/if(compare(opr1,opr2)=-1)else/A=B的情况sub_bas(opr1,opr2,oprr);oprr-data=+;/else/if(opr1-data=+)else/(-A)-(-B)的情况if(compare(opr1,opr2)=1)/AB的情况sub_bas(opr1,opr2,oprr);oprr-data=-;/if(compare(opr1,opr2)=1)else/Adata=+;/else/else/if(opr1-data!=opr2-data)else/opr1,opr2符号不同add_bas(opr1,opr2,oprr);if(opr1-data=+)/A-(-B)oprr-data=+;else/(-A)-Boprr-data=-;/elsereturn OK;/sub6、 乘法模块/乘法函数Status imul(NodeList opr1,NodeList opr2,NodeList &oprr)if(compare(opr1,opr2)=-1)/若opr1比opr2小则被乘数跟乘数调换，否则直接取指针操作len=length(opr1)+length(opr2);/创建指定长度的链表oprrqq=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;/处理链表开头结点值为0的无意义情况，若链表本身表示0，则不做如下处理flag=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);/链表符号位的添加7、 除法模块/除法子函数int idiv_sub(NodeList &opr1,NodeList opr2)count=0;while(compare(opr1,opr2)!=-1)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;/清头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 idiv(NodeList opr1,NodeList opr2,NodeList &quti,NodeList &remand)/quti为商数链，remand为余数链if(compare(opr1,opr2)=-1)/比较除数与被除数，若除数比被除数大，则进行余数处理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;/初始化remand链while(q2!=remand)q2-data=q1-data;q1=q1-next;q2=q2-next;pq=quti-next;q1=q1-prior;/指针退回一步while(q1!=opr1)buffer=idiv_sub(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;/余数与商的操作数符号添加8、 乘方与阶乘运算模块：/*Status imul_power(NodeList &opr1,int n,NodeList &oprr) /乘方的枚举版本 ,时间为N imul(opr1,opr1,oprr); for(i=3;i1; if(n=2 | n=3) imul(opr1,opr1,oprr); if(n=3) imul(oprr,opr1,oprr); else power(opr1,oprr,n1); imul(oprr,oprr,oprr); if(m%2) imul(opr1,oprr,oprr); Status imul_power(NodeList &opr1,int n,NodeList &oprr) if(n%2) power(opr1,oprr,n-1); imul(opr1,oprr,oprr); else power(opr1,oprr,n); return OK; /用二分递归的方式进行操作Status imul_factorial(NodeList &opr1,NodeList &oprr) char *str1=0; char *str2=1; NodeList oper1,oper2,oper3; int i,flag; flag=conversion(str1,oper1); flag=conversion(str2,oper2); sub(oprr,oper2,opr1); while(compare(opr1,oper1)!=0) imul(oprr,opr1,oprr); sub(opr1,oper2,opr1); return OK;9、 主操作模块：void title()/格式调整/打印欢迎屏幕void welcome()printf(=nn); printf(ttt欢迎使用长整数四则运算程序nn); printf(请按如下提示进行操作:nn);printf(首先，根据屏幕的提示选择您想进行的操作。nn);printf(其次，根据提示输入两个操作数。nn);printf(注意：请不要输入类似-0、0012、0X0d之类的操作数。否则程序会提示错误，请从新输入。n);printf(ttt作者：彭伟湘(09计算机科学以技术2班，学号:3109005945)n); printf(=nn); /主调用函数Status main_do()/解析操作命令与相应的运算操作/输入1-7的指令并进入相应的运行界面switch(ch)case 1:input(opr1,opr2,str);printf(n相加的和为：n);add(opr1,opr2,oprr);/输出并附加输错判断break;case 2:input(opr1,opr2,str);printf(n相减的差为：n);sub(opr1,opr2,oprr);/输出并附加输错判断break;case 3:input(opr1,opr2,str);printf(n相乘的积为：n);imul(opr1,opr2,oprr);/输出并附加输错判断break;case 4:input(opr1,opr2,str);while(opr2-next-data=0)printf(除数不能为0!n请重新输入：n);scanf(%s,str);conversion(str,opr2);idiv(opr1,opr2,quti,remand);printf(n商