任意长整数的四则运算.doc

沈阳航空航天大学课程设计报告 1 题目介绍和功能要求1.1 课程设计题目要求【问题描述】： 设计一个实现任意长的整数进行加法运算的演示程序 。【题目内容】：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(- 1)(- 1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。【基本要求】：（1）利用所学知识，设计相应的数据结构；（2）熟练运用开发环境；（3）完成软件的设计与编码； （4）熟练地掌握基本的调试方法。1.2 题目分析【需求分析】： （1）本程序实现计算任意长的整数的加法运算. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就计算并显示出这两个数的运算。 （2）本演示程序中，数字字符限定为09和字符，输入字符可以任意长，输入形式以“回车符”为结束标志，串中字符顺序不限，且允许出现重复字符。 （3）利用双向循环链表现实长整数的存储，每个结点含一个整形变量。输入的形式以回车结束，可以直接输入正数或负数。按中国对于长整数的表示习惯，每四位一组，除数字和位于首位置的负号外，其它一切字符都将作为分隔符，连续多个分隔符当一个处理,但不使用分隔符也不影响结果。 2 系统功能模块结构图2.1 系统功能结构框图 主调程序模块 系统功能模块 双向循环链表处理模块 长整数运算模块 界 面 模 块 图2.1 系统功能结构图2.2主要模块的功能说明： （1）主调程序模块： void main() 初始化； do 接受命令； 处理命令； while(“命令”=”退出”) （2）双向循环链表处理模块 /cmplinklen.h /Creat.h /compare 说明：进行链表的存储和处理 （3）长整数运算模块 /add.h / sub.h /imul.h /idiv.h 说明:对长整数进行四则运算 （4）界面模块 /title.h /welcome.h 说明：控制系统运行操作界面 3 数据结构的设计及用法说明3.1 概要说明为了实现上述功能，采取双向循环链表表示长整数，每个结点含一个整型变量，仅绝对值不超过9999的整数，整个链表用十进制数表示。利用头结点数据域的符号表示长整数的符号，相加过程不破坏两个操作数链表，对长整数位数不作上限。为此需要两个结构数据类型：双向循环链表和长整数。3.2用法说明 3.2.1 双向循环链表的数据结构定义：typedef struct Node /双向循环链表结点 int data;struct Node *prior,*next;Node,*NodeList; 3.2.2 基本操作: Status conversion(char str,NodeList &oprh); /将字符串形式的操作数转换成所需的类型 int cmplinklen(NodeList opr1,NodeList opr2); /opr1链比opr2链长则返回1，短则返回-1，否则返回0 int length(NodeList oprr); /求链表长度 Status Creat(NodeList &oprr,int len); /生成指定长度链表 int compare(NodeList opr1,NodeList opr2); /比较opr1、opr2绝对值的大小 4 涉及到的函数的描述 4.1长整数操作函数Status input(NodeList &opr1,NodeList &opr2,char str)； /从键盘输入两个长整数，存至opr1和opr2中Status output(NodeList oprr,char str)； /在屏幕打印长整数oprrStatus add_bas(NodeList opr1,NodeList opr2,NodeList &oprr)； /本算法实现A,B相加的操作Status sub_bas(NodeList opr1,NodeList opr2,NodeList &oprr)； /本算法实现A,B相减的操作Status imul(NodeList opr1,NodeList opr2,NodeList &oprr)； /本算法实现A,B相乘的操作Status idiv(NodeList opr1,NodeList opr2,NodeList &quti,NodeList &remand)； /本算法实现A,B相除的操作4.2主要函数 主程序模块: /int main()双向循环链表处理模块: /Status conversion(char str,NodeList &oprh); /int cmplinklen(NodeList opr1,NodeList opr2); /Status Creat(NodeList &oprr,int len); /int compare(NodeList opr1,NodeList opr2);长整数四则运算模块: /Status add_bas(NodeList opr1,NodeList opr2,NodeList &oprr)； /Status sub_bas(NodeList opr1,NodeList opr2,NodeList &oprr)； /Status imul(NodeList opr1,NodeList opr2,NodeList &oprr)； /Status idiv(NodeList opr1,NodeList opr2,NodeList &quti,NodeList &remand)； 界面模块: /void title(); /void welcome(); 5 主要算法程序流程图 5.1 程序流程图加法运算 退 出减法运算 开 始欢迎界面 主调函数 输入数据 操作界面 除法运算 乘法运算 输出数据 输出数据 退出？ 否 退出？ 是 程序结束程序结束 图5.1 主要算法流程图 6 程序测试(1) 程序运行环境为DOS界面，执行文件为“长整数四则运算.exe”(2) 进入演示程序后即显示文本方式的用户界面 图6.1 用户界面(3) 输入命令，执行相应的功能： 1-加法运算 2-减法运算 3-乘法运算 4-除法运算 5-退出系统 图6.2 执行界面(4) 加法运算测试 图6.3 加法运算界面 (5) 减法运算测试 图6.4 减法运算界面(6) 乘法运算测试 图6.5 乘法运算界(7) 除法运算测试 图6.6 除法运算界面7 参考文献1 严蔚敏，吴伟民.数据结构（C语言版）M.北京：清华大学出版社，20062 吕国英.算法设计与分析M.北京：清华大学出版社，20063 徐宝文，李志.C程序设计语言M.北京：机械工业出版社，20044 滕国文.数据结构课程设计M.北京：清华大学出版社，20105 苏仕华.数据结构课程设计（第2版）M.北京：机械工业出版社，20106 李建学，李光.数据结构课程设计案例精编M.北京：清华大学出版社，20107 汪沁，奚李峰.数据结构与算法M.北京：清华大学出版社，20128 奚小玲，敖广武.数据结构理论与实践M.北京：东北大学出版社，2010 附录：程序清单(带有必要的注释)#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 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(;k0;k-)r=r*a;return r;/输入转换函数Status conversion(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!=+)&(stri9 | strinext-prior=p; p-prior=oprh; p-next=oprh-next; oprh-next=p; p-data=buffer; buffer=k=0;if(str0=-)oprh-data=-;elseoprh-data=+;return OK;/输入函数Status input(NodeList &opr1,NodeList &opr2,char str)int flag=OK,i,n=0,l; char bMAX; printf(n请输入第一个操作数:n);scanf(%s,b);getchar();l=strlen(b);for(i=0;il;i+)if(bi!=,)strn+=bi;strn=0;flag=conversion(str,opr1); while(!flag) printf(ERROR!Input again:n); scanf(%s,str); getchar(); flag=conversion(str,opr1);printf(n请输入第二个操作数:n);scanf(%s,b);getchar();n=0;l=strlen(b);for(i=0;idata=-)stri+=-;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(jnext; j=0; stri+=,; if(str-i=,) stri=0;printf(%s,str);printf(n);return OK;/=预处理及杂项操作模块=/缓冲区部分初始化函数Status initbuf(char str)int i;for(i=0;iprior;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(len0)p-next=(NodeList)malloc(LEN);p-next-data=?;p-next-prior=p;p=p-next;len-;p-next=oprr;oprr-prior=p;return OK;/比较opr1、opr2绝对值的大小int compare(NodeList opr1,NodeList 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;elsewhile(p1-data=p2-data & p1-next!=opr1)/注意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 add_bas(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-datap1=p1-prior;p2=p2-prior;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-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;oprr-data=+;return OK;/减法基本操作Status sub_bas(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-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;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，则不做如下处理 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)/重接prior链 qq=qh; qh=qh-next; free(qq);oprr-data=+;return OK;/-带符号加法函数-Status add(NodeList opr1,NodeList opr2,NodeList &oprr)if(opr1=NULL | opr2=NULL)return ERROR;if(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=-;else/符号不相同if(opr1-data=+)/A+(-B)的情况if(compare(opr1,opr2)=-1)/Adata=-;else/A=B的情况sub_bas(opr1,opr2,oprr);oprr-data=+;else/(-A)+B的情况if(compare(opr1,opr2)=1)/AB的情况sub_bas(opr1,opr2,oprr);oprr-data=-;else/Adata=+;return OK;/-带符号减法函数-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=-;else/A=B的情况sub_bas(opr1,opr2,oprr);oprr-data=+;else/(-A)-(-B)的情况if(compare(opr1,opr2)=1)/AB的情况sub_bas(opr1,opr2,oprr);oprr-data=-;else/Adata=+;else/opr1,opr2符号不同add_bas(opr1,opr2,oprr);if(opr1-data=+)oprr-data=+;elseoprr-data=-;return OK;/=乘法模块=/乘法函数Status imul(NodeList opr1,NodeList opr2,NodeList &oprr)NodeList ph1,ph2,pt1,pt2,p3,pt3,qh,qt,qq;int len,CF,flag;long buffer;if(compare(opr1,opr2)=-1)/若opr1比opr2小则被乘数跟乘数调换ph1=opr2;pt1=ph1-prior;ph2=opr1;pt2=ph2-prior;elseph1=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;/处理链表开头结点值为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);if(opr1-data=opr2-data | oprr-next-data=0)oprr-data=+;elseoprr-data=-;return OK;/=除法模块=/除法子函数int idiv_sub(NodeList &opr1,NodeList opr2)NodeList p1,p2,qh,qt,qq;int count,CF,buffer,flag;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为余数链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;/初始化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-p