《数据结构课程设计》课程设计报告任意长的整数加减法运算

《数据结构课程设计》课程设计报告任意长的整数加减法运算任意长的整数加减法运算题目要求：设计算法，实现一个任意长的整数进行加法、减法运算的演示程序。例如：1234，5123，4512，3451，2345与-1111，1111，1111，1111，1111的加法结果为：0123，4012，3401，2340，1234。基本要求如下：利用链表实现长整数的存储，每个节点含一个整型变量；整型变量的范围：-（2^15-1）~（2^15-1）；输入与输出形式每四位一组，组间用逗号分隔开。如：1986,8213,1935,2736,3299；界面友好，每步给出适当的操作提示，并且系统具有一定的容错能力。至少给出下面的测试数据：（1）0；0（2）-2345,6789；-7654,3211（3）-9999,9999；1,0000,0000,0000（4）1,0001,0001；-1,0001,0001（5）1,0001,0001；-1,0001,0000（6）-9999,9999,9999；-9999,9999,9999（7）1,0000,9999,9999；1需求分析【问题描述】

设计一个实现任意长的整数进行加法运算的演示程序【基本要求】利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是-(2^15-1)~(2^15-1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。【实现基本功能】(i)是想长整数的四则运算；(ii)整形量范围是-（2^n-1）~（2^n-1），其中n是由程序读入的参量。输入数据的分组方法另行规定；

【测试数据】

（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”。【长整数四则运算】

(i)本程序实现计算任意长的整数的加法运算.以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就计算并显示出这两个数的运算。

(ii)本演示程序中，集合的元素限定为数字字符[‘0’~’9’]和字符‘，’与‘；’，输入字符可以任意长，输入形式以“回车符”为结束标志，串中字符顺序不限，且允许出现重复字符。

(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"；-98,9997；3；除法输出-32,9999；

概要设计为实现上述程序功能，应以双向循环链表表示长整数。为此，需要定义一个抽象数据类型

1、抽象数据类型定义为：

ADTOrderedOperation{

数据对象：D={ai|ai∈int,i=1,2,...n,n≥0}

数据关系：R1={|ai-1,ai∈D|=2,……n}

基本操作：Statusconversion(str,oprh)//操作结果：输入转换函数，将字符串形式的操作数转换成所需的类型cmplinklen(opr1,opr2)//操作结果：比较链表长度函数,opr1链比opr2链长则返回1，短则返回-1，否则返 //回0length(oprr)//操作结果：求链表长度StatusCreat(oprr,len)//操作结果：生成指定长度链表compare(opr1,opr2)//操作结果：比较opr1、opr2绝对值的大小Statusinit(oppr)//初始化链表函数Statusdistroy(oprr)//销毁链表函数Statusevaluate(opri,i)//操作结果：链表短赋值函数，将i的值转换成万进制类型，i为整形变量Statusadd_bas(opr1,opr2,oprr)//操作结果：加法基本操作，本算法实现A,B相加的操作。 Statussub_bas(opr1,opr2,oprr)//减法基本操作，本算法实现A,B相减的操作Statusadd(opr1,opr2,oprr)//操作结果：带符号加法运算 Statussub(opr1,opr2,oprr)//操作结果：带符号减法函数Statusimul(opr1,opr2,oprr)//操作结果：乘法运算Statusidiv(opr1,opr2,quti,remand)//操作结果：除法运算Statusimul_power(opr1,n,oprr)//操作结果：乘方运算，运用了二分思想，时间长度为lgNStatusimul_factorial(opr1,oprr)//操作结果：阶乘运算Statusoutput(oprr,str)//操作结果：输出的数据按四位一组，分隔符为","的格式

}ADTOrderedOperation链表抽象数据类型的定义：ADTList{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≧0}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=1,2,…,n}基本操作：Statusinitbuf(charstr[])//操作结果：缓冲区部分初始化函数，返回OKintcmplinklen(NodeListopr1,NodeListopr2)//操作结果：opr1链比opr2链长则返回1，短则返回-1，否则返回0 intlength(NodeListoprr) //操作结果：计算链表长度，并返回链表长度的操作数 StatusCreat(NodeList&oprr,intlen) //操作结果：生成指定长度链表，返回OK intcompare(NodeListopr1,NodeListopr2) //操作结果：比较opr1、opr2绝对值的大小 Statusinit(NodeList&oppr) //操作结果：初始化链表函数 Statusdistroy(NodeList&oprr) //操作结果：销毁链表函数，返回OK Statusevaluate(NodeList&opri,inti) //操作结果：链表短赋值函数，将i的值转换成万进制类型，i为整形变量}ADTOrderedList本程序大体包含三个模块：(i)主程序模块：

voidmain(){

初始化；

do{

接受命令；

处理命令；

}while(“命令”=”退出”)

}(ii)集合单元模块——实现集合的抽象数据类型

(iii)结点结构单元模块——定义集合的结点结构主程序各模块之间的关系如下：主程序集合单元模块集合单元模块结点结构单元模块

结点结构单元模块3、本程序细分为以下几大功能模块：(i)输入模块；(ii)输出模块；(iii)预处理及相关操作模块(iv)四则预算模块及(包含乘方、阶乘)；(v)主操作模块；详细设计1、头文件的定义部分#include<stdio.h>#include<cstdio>#include<cstring>#include<malloc.h>#include<conio.h>#include<stdlib.h>#defineLENsizeof(structNode)#defineMAX1000#defineOK1#defineERROR0#defineOVERFLOW-1#defineTRUE1#defineFALSE0typedefchar_TCHAR;typedefintStatus;2、输入模块：//求指数函数值intaxp(inta,intk){ if(k==0) return1;//k指数为零的情况 for(;k>0;k--)//指数结果处理 r=r*a; returnr;}//输入转换函数Statusconversion(charstr[],NodeList&oprh){//将字符串形式的操作数转换成所需的类型 k=buffer=0; oprh=(NodeList)malloc(LEN);//申请长整数由字符串转换为链表的存储空间 oprh->next=oprh; oprh->prior=oprh;//初始化链表的前驱指针prior指针与后驱指针next for(i=strlen(str)-1;i>=0;i--) {//出错判断处理，规范输入格式；若输入格式出错，则跳出转换程，并序重新输入 if(str[i]!='-'&&str[i]!='+') { buffer=buffer+(str[i]-'0')*axp(10,k); k++; if(k==4||str[i-1]=='-'||str[i-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}//输入函数Statusinput(NodeList&opr1,NodeList&opr2,charstr[]){//分别输入连个字符串并进行判断，直至输入成功则返回OK}Statusinput1(NodeList&opr1,int&n,charstr[]){ //分别输入乘方的底数和指数两个操作数，直至输入成功返回OK}Statusinput2(NodeList&oprr,charstr[]){ //只是输入阶乘的一个正整数，直至输入成功返回OK}3、输出模块：//输出函数Statusoutput(NodeListoprr,charstr[]){ if(!oprr) returnERROR;//判断用链表记录的运算结果是否为空（出错），返回FALSE p=oprr;//指针对链表进行遍历 initbuf(str);//清空字符串数组str的内容//符号位判断，若为负数，在字符串的首位加‘—’ p=p->next; if(p->next==oprr&&p->data==0)//若要输出的数为0则执行 str[i++]='0'; else while(p!=oprr) {//每千位进行取余数运算 while(j<4) { if(num[j]!=0||(str[0]=='-'&&str[1]!='\0')||(str[0]!='-'&&str[0]!='\0')) //此判断语句是为了避免输出诸如：00123…的情况//规范字符串的处理，消除长整数前面的0，每四位进行一个循环操作 } //指针后移，并重新计算操作位 } //取字符串长度//从低位到高位开始，按每四位数用一个‘，’将数据进行分割，并记录在新的字 //符串数组str1翻转输出，并返回OK}预处理相关项操作模块（双向链表的相关ADT的操作）：typedefstructNode{ intdata;//数据域 structNode*prior,*next;//前驱指针prior，后驱指针next}Node,*NodeList;双向链表的基本操作设计如下：Statusinitbuf(charstr[])//操作结果：缓冲区部分初始化函数，返回OKintcmplinklen(NodeListopr1,NodeListopr2)//操作结果：opr1链比opr2链长则返回1，短则返回-1，否则返回0 intlength(NodeListoprr) //操作结果：计算链表长度，并返回链表长度的操作数 StatusCreat(NodeList&oprr,intlen) //操作结果：生成指定长度链表，返回OK intcompare(NodeListopr1,NodeListopr2) //操作结果：比较opr1、opr2绝对值的大小 Statusinit(NodeList&oppr) //操作结果：初始化链表函数 Statusdistroy(NodeList&oprr) //操作结果：销毁链表函数，返回OK Statusevaluate(NodeList&opri,inti) //操作结果：链表短赋值函数，将i的值转换成万进制类型，i为整形变量其中部分操作的伪代码如下：Statusinitbuf(charstr[]){ //缓冲区部分初始化函数，返回OK}//比较链表长度函数intcmplinklen(NodeListopr1,NodeListopr2){//opr1链比opr2链长则返回1，短则返回-1，否则返回0}intlength(NodeListoprr){ //计算链表长度，并返回链表长度的操作数}StatusCreat(NodeList&oprr,intlen){ //生成指定长度链表，返回OK}intcompare(NodeListopr1,NodeListopr2){//比较opr1、opr2绝对值的大小 p1=opr1->next; p2=opr2->next;//取指针进行操作 if(cmplinklen(opr1,opr2)==1)//opr1比较长 return1; elseif(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,1 }}Statusinit(NodeList&oppr){ //初始化链表函数}Statusdistroy(NodeList&oprr){ //销毁链表函数，返回OK}//distroyStatusevaluate(NodeList&opri,inti){//链表短赋值函数，将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; returnOK;}//evaluate加减法模块//加法基本操作Statusadd_bas(NodeListopr1,NodeListopr2,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}//减法基本操作Statussub_bas(NodeListopr1,NodeListopr2,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->data<(p2->data+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->data<CF) //判断进位CF，并进行进位操作 p3=(NodeList)malloc(LEN); oprr->next->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}//带符号加法函数Statusadd(NodeListopr1,NodeListopr2,NodeList&oprr){ //出错处理：若opr1或opr2为空，返回FALSE 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='-'; }//if(opr1->data==opr2->data) else {//符号不相同 if(opr1->data=='+') {//A+(-B)的情况 if(compare(opr1,opr2)==-1) {//A<B的情况 sub_bas(opr2,opr1,oprr); oprr->data='-'; }//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) {//A>B的情况 sub_bas(opr1,opr2,oprr); oprr->data='-'; }//if(compare(opr1,opr2)==1) else {//A<=B的情况 sub_bas(opr2,opr1,oprr); oprr->data='+'; }//else }//else }//else returnOK;}//add//带符号减法函数Statussub(NodeListopr1,NodeListopr2,NodeList&oprr){ if(opr1==NULL||opr2==NULL) returnERROR; if(opr1->data==opr2->data) {//opr1,opr2符号相同 if(opr1->data=='+') {//A-B的情况 if(compare(opr1,opr2)==-1) {//A<B的情况 sub_bas(opr2,opr1,oprr); oprr->data='-'; }//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) {//A>B的情况 sub_bas(opr1,opr2,oprr); oprr->data='-'; }//if(compare(opr1,opr2)==1) else {//A<=B的情况 sub_bas(opr2,opr1,oprr); oprr->data='+'; }//else }//else }//if(opr1->data!=opr2->data) else {//opr1,opr2符号不同 add_bas(opr1,opr2,oprr); if(opr1->data=='+')//A-(-B) oprr->data='+'; else//(-A)-B oprr->data='-'; }//else

returnOK;}//sub主操作模块：voidtitle(){ //格式调整}//打印欢迎屏幕voidwelcome(){ printf("===============================================================================\n\n");printf("\t\t\t欢迎使用长整数四则运算程序\n\n");printf("请按如下提示进行操作:\n\n"); printf("首先，根据屏幕的提示选择您想进行的操作。\n\n"); printf("其次，根据提示输入两个操作数。\n\n"); printf("注意：请不要输入类似-0、0012、0X0d之类的操作数。否则程序会提示错误，请从新输入。\n");printf("\t\t\t作者：彭伟湘(09计算机科学以技术2班，学号:3109005945)\n"); printf("===============================================================================\n\n"); }//主调用函数Statusmain_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商数为：\n");//输出并附加输错判断 printf("\n余数为：\n"); //输出并附加输错判断 break;case'5':input1(opr1,n,str);printf("\n乘方的积为：\n"); imul_power(opr1,n,oprr);//输出并附加输错判断 break;case'6':input2(oprr,str);printf("\n阶乘的积为：\n");imul_factorial(opr1,oprr);//输出并附加输错判断 break; case'7':exit(0); } returnOK;}//主函数intmain(intargc,_TCHAR*argv[]){ intflag=1; charch; system("colorF0"); welcome(); printf("确认请按Enter键");getchar(); system("cls"); while(flag) { main_do(); printf("\n继续？(Y/N)"); ch=getchar(); getchar(); if(ch=='N'||ch=='n') flag=0; system("cls"); } return0;}调试分析及结果由于对任意长整数运算的算法推敲不足，是程序调试时费时不少

2、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性

3、本程序模块划分比较合理，且把指针全部封装在链表模块中，操作方便。

4、算法的时空分析。由于链表采用双向循环链表结构，可以从链表两头操作，各种操 作的算法时间复杂度比较合理，各函数以及确定链表中的结点位置都是O(n),n为链表 长度(其中乘方函数是O(lgN))。

5、本实验采用数据抽象的程序设计方法，将程序分为3个模块，使得设计时思路清晰， 实现时调试顺利，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。本程序使用起来简单方便，只要按照菜单提示进行即可。1.输入0；0；2.输入-2345,6789；-7654,3211；3.输入-9999,9999；1,0000,0000,0000；4.输入1,0001,0001；-1,0001,0001；5.输入1,0001,0001；-1,0001,0000；6.输入-9999,9999,9999；-9999,9999,9999；7.输入1,0000,9999,9999；1；减法输入0；0；输入-2345,6789；-7654,3211；输入-9999,9999；1,0000,0000,0000；输入1,0001,0001；-1,0001,0001；输入1,0001,0001；-1,0001,0000；输入-9999,9999,9999；-9999,9999,9999；输入1,0000,9999,9999；1；8.输入0；0；后输入0退出五、实验总结1、进一步熟悉掌握了双向循环链表的基本操作；

2、熟悉任意长字符串的输入，并实现把字符串转化为整数；

3、熟悉任意长整数的加法运算；

4、更进一步掌握有关类的操作

5、由于对任意长整数运算的算法推敲不足，是程序调试时费时不少

6、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性六、源代码附录//长整数四则运算.cpp:定义控制台应用程序的入口点。//#include<stdafx.h>#include<stdio.h>#include<cstdio>#include<cstring>#include<malloc.h>#include<conio.h>#include<stdlib.h>#defineLENsizeof(structNode)#defineMAX1000#defineOK1#defineERROR0#defineOVERFLOW-1#defineTRUE1#defineFALSE0typedefchar_TCHAR;typedefintStatus;typedefstructNode{ intdata; structNode*prior,*next;}Node,*NodeList;//=======================================输入模块===============================*///求指数函数值intaxp(inta,intk){ intr=1; if(k==0) return1; for(;k>0;k--) r=r*a; returnr;}//输入转换函数Statusconversion(charstr[],NodeList&oprh){//将字符串形式的操作数转换成所需的类型 NodeListp; inti,k,buffer; k=buffer=0; oprh=(NodeList)malloc(LEN); oprh->next=oprh; oprh->prior=oprh; for(i=strlen(str)-1;i>=0;i--) { //输入的数不合法就返回重新输入 if(str[i]==',')continue;//字符串的‘，’处理，不可缺 if((i!=0||(str[0]!='-'&&str[0]!='+'))&&(str[i]>'9'||str[i]<'0')) returnERROR; if(str[0]=='0'&&str[1]!='\0') returnERROR; if((str[0]=='-'||str[0]=='+')&&str[1]=='0') returnERROR; if(str[i]!='-'&&str[i]!='+') { buffer=buffer+(str[i]-'0')*axp(10,k); k++; if(k==4||str[i-1]=='-'||str[i-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; } } } if(str[0]=='-') oprh->data='-'; else oprh->data='+'; returnOK;}//输入函数Status input(NodeList&opr1,NodeList&opr2,charstr[]){ intflag=OK;printf("\n请输入第一个操作数:\n"); scanf("%s",str); getchar(); flag=conversion(str,opr1);while(!flag){ printf("ERROR!Inputagain:\n");scanf("%s",str); getchar(); flag=conversion(str,opr1); } printf("\n请输入第二个操作数:\n"); scanf("%s",str); getchar(); flag=conversion(str,opr2);while(!flag){ printf("ERROR!Inputagain:\n");scanf("%s",str); getchar(); flag=conversion(str,opr2); } returnOK;}Statusinput1(NodeList&opr1,int&n,charstr[]){ intflag=OK;printf("\n请输入第一个操作数:\n"); scanf("%s",str); getchar(); flag=conversion(str,opr1);while(!flag){ printf("ERROR!Inputagain:\n");scanf("%s",str); getchar(); flag=conversion(str,opr1); } printf("\n请输入第二个操作数:\n"); scanf("%d",&n); getchar(); returnOK;}Statusinput2(NodeList&oprr,charstr[]){ intflag=OK;printf("\n请输入第一个操作数:\n"); scanf("%s",str); getchar(); flag=conversion(str,oprr);while(!flag){ printf("ERROR!Inputagain:\n");scanf("%s",str); getchar(); flag=conversion(str,oprr); } returnOK;}/*====================================输出模块===============================*/Statusoutput(NodeListoprr,charstr[]){ Statusinitbuf(charstr[]); NodeListp; charstr1[10000];intt=0,t1=0,n; inti,j,num[4]; if(!oprr) returnERROR; p=oprr; i=j=0; initbuf(str); if(oprr->data=='-') str[i++]='-'; p=p->next; if(p->next==oprr&&p->data==0)//若要输出的数为0则执行 str[i++]='0'; else while(p!=oprr) { num[0]=p->data/1000; num[1]=(p->data-num[0]*1000)/100; num[2]=(p->data-num[0]*1000-num[1]*100)/10; num[3]=p->data-num[0]*1000-num[1]*100-num[2]*10; while(j<4) {//此判断语句是为了避 免输出诸如：00123…的情况 if(num[j]!=0||(str[0]=='-'&&str[1]!='\0')||(str[0]!='-'&&str[0]!='\0')) str[i++]=num[j]+'0'; j++; } p=p->next; j=0; } str[i]='\0'; n=strlen(str);for(i=n-1;i>=0;--i){if(t==4&&i>0&&str[i]!='-'){str1[t1++]=',';t=1;}else++t;str1[t1++]=str[i];}str1[t1]='\0';n=strlen(str1);for(i=n-1;i>=0;--i)putchar(str1[i]);// printf("%s",str); printf("\n"); returnOK;}/*====================================预处理及杂项操作模块==============================*/Statusinitbuf(charstr[]){ inti; for(i=0;i<=10;i++) str[i]='\0'; returnOK;}//比较链表长度函数intcmplinklen(NodeListopr1,NodeListopr2){//opr1链比opr2链长则返回1，短则返回-1，否则返回0 NodeListp1,p2; p1=opr1->prior; p2=opr2->prior; while(p1->prior!=opr1&&p2->prior!=opr2) { p1=p1->prior; p2=p2->prior; } if(p1->prior!=opr1) return1; if(p2->prior!=opr2) return-1; return0;}//求链表长度intlength(NodeListoprr){ intcount=0; NodeListp=oprr->next; while(p!=oprr) { count++; p=p->next; } returncount;}//生成指定长度链表StatusCreat(NodeList&oprr,intlen){ NodeListp; 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; returnOK;}//比较opr1、opr2绝对值的大小intcompare(NodeListopr1,NodeListopr2){ NodeListp1,p2; p1=opr1->next; p2=opr2->next; if(cmplinklen(opr1,opr2)==1)//opr1比较长 return1; elseif(cmplinklen(opr1,opr2)==-1) return-1; else//长度相等的情况{//注意不要少了p1->next!=opr1这个条件 while(p1->data==p2->data&&p1->next!=opr1) { p1=p1->next; p2=p2->next; } if(p1->data>p2->data) return1; elseif(p1->data<p2->data) return-1; else return0; }}//初始化链表函数Status init(NodeList&oppr){ oppr=NULL; returnOK;}//init//销毁链表函数Statusdistroy(NodeList&oprr){ NodeListq; if(oprr) { q=oprr->next; while(q!=oprr) { free(q->prior); q=q->next; } } oprr=NULL; returnOK;}//distroy//链表短赋值函数Statusevaluate(NodeList&opri,inti){//将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; returnOK;}//evaluate/*=======================================加减法模块=====================================*///加法基本操作Statusadd_bas(NodeListopr1,NodeListopr2,NodeList&oprr){//本算法实现A,B相加的操作。 intCF,buffer;NodeListp1,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; //将新建结点插入到头结点之后 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='+'; returnOK;}//减法基本操作Statussub_bas(NodeListopr1,NodeListopr2,NodeList&oprr){//本算法实现A,B相减的操作。//将A链分成与B链长相等的底位部分,和剩余的高位部分,并做相应处理。 intCF,buffer,flag; NodeListp1,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; } else { buffer=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; } 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&&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); } } oprr->data='+'; returnOK;}//带符号加法函数Statusadd(NodeListopr1,NodeListopr2,NodeList&oprr){ if(opr1==NULL||opr2==NULL) returnERROR; 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='-'; }//if(opr1->data==opr2->data) else {//符号不相同 if(opr1->data=='+') {//A+(-B)的情况 if(compare(opr1,opr2)==-1) {//A<B的情况 sub_bas(opr2,opr1,oprr); oprr->data='-'; }//if(compare(opr1,opr2)==-1) else {//A>=B的情况 sub_bas(opr1,opr2,oprr); oprr->data='+'; }//else } else {//(-A)+B的情况 if(compare(opr1,opr2)==1) {//A>B的情况 sub_bas(opr1,opr2,oprr); oprr->data='-'; }//if(compare(opr1,opr2)==1) else {//A<=B的情况 sub_bas(opr2,opr1,oprr); oprr->data='+'; }//else }//else }//else returnOK;}//add//带符号减法函数Statussub(NodeListopr1,NodeListopr2,NodeList&oprr){ if(opr1==NULL||opr2==NULL) returnERROR; if(opr1->data==opr2->data) {//opr1,opr2符号相同 if(opr1->data=='+') {//A-B的情况 if(compare(opr1,opr2)==-1) {//A<B的情况 sub_bas(opr2,opr1,oprr); oprr->data='-'; }//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) {//A>B的情况 sub_bas(opr1,opr2,oprr); oprr->data='-'; }//if(compare(opr1,opr2)==1) else {//A<=B的情况 sub_bas(opr2,opr1,oprr); oprr->data='+'; }//else }//else }//if(opr1->data!=opr2->data) else {//opr1,opr2符号不同 add_bas(opr1,opr2,oprr); if(opr1->data=='+')//A-(-B) oprr->data='+'; else//(-A)-B oprr->data='-'; }//else returnOK;}//sub//=========================================乘法模块===============================*/Statusimul(NodeListopr1,NodeListopr2,NodeList&oprr){ NodeListph1,ph2,pt1,pt2,p3,pt3,qh,qt,qq; intlen,CF,flag; longbuffer; if(compare(opr1,opr2)==-1) {//若opr1比opr2小则被䩘数跟乘数调换 0h1=opr2; pt1=ph1->prior; ph2=opr1; pt2=ph"->prior; } else { ph1=opr1; pt1=ph1->prior; `h2=opr2; pt2=ph2->prior; } len=length(opr1)+lenFth(opr2); Creat(oprr,len); qq=oprr->nexd; while(qq!=kprr) { 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='+'; el3e

oprr->data='-'; returnOK;}//====9=========9======================除法模块===============================*/intidiv_sub(NodeList&opr1,NodeListopr2){ NodeListp1,p2,qh,qt,qq; intcount,CF,buffer,flag; count=0; while(compare(opr1,opr)!=-1) { 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; } //清头0 flag=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++; } returncount;}//除法函数Statusidiv(NodeListopr1,NodeListopr2,NodeList&quti,NodeList&remand){//quti为商数链，remand为余数链 intlen_quti,len_reman,buffer; NodeListq1,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; //初始化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; } if(opr1->data=='-'&&remand->next->data!=0) remand->data='-'; else remand->data='+'; if(opr1->data==opr2->data||quti->next->data==0) quti->data='+'; else quti->data='-'; returnOK;}voidpower(NodeList&opr1,NodeList&oprr,intn){//乘方函数用二分思想进行改进，时间为lgNintm=n>>1;if(n==2||n==3){imul(opr1,opr1,oprr);if(n==3)imul(oprr,opr1,oprr);}else{power(opr1,oprr,n>>1);imul(oprr,oprr,oprr);if(m%2)imul(opr1,oprr,oprr);}}Statusimul_power(NodeList&opr1,intn,Node