任意長(zhǎng)整數(shù)的四則運(yùn)算

1、 1 題目介紹和功能要求1.1 課程設(shè)計(jì)題目要求【問(wèn)題描述】： 設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加法運(yùn)算的演示程序 ?！绢}目?jī)?nèi)容】：利用雙向循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整形變量。任何整形變量的范圍是 -(- 1)(- 1)。輸入和輸出形式：按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開(kāi)?！净疽蟆浚海?）利用所學(xué)知識(shí)，設(shè)計(jì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu)；（2）熟練運(yùn)用開(kāi)發(fā)環(huán)境；（3）完成軟件的設(shè)計(jì)與編碼； （4）熟練地掌握基本的調(diào)試方法。1.2 題目分析【需求分析】： （1）本程序?qū)崿F(xiàn)計(jì)算任意長(zhǎng)的整數(shù)的加法運(yùn)算. 以用戶(hù)和計(jì)算機(jī)對(duì)話(huà)的方式，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶(hù)在鍵盤(pán)上

2、輸入演示程序中規(guī)定的運(yùn)算命令，然后程序就計(jì)算并顯示出這兩個(gè)數(shù)的運(yùn)算。 （2）本演示程序中，數(shù)字字符限定為09和字符，輸入字符可以任意長(zhǎng)，輸入形式以“回車(chē)符”為結(jié)束標(biāo)志，串中字符順序不限，且允許出現(xiàn)重復(fù)字符。 （3）利用雙向循環(huán)鏈表現(xiàn)實(shí)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整形變量。輸入的形式以回車(chē)結(jié)束，可以直接輸入正數(shù)或負(fù)數(shù)。按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，除數(shù)字和位于首位置的負(fù)號(hào)外，其它一切字符都將作為分隔符，連續(xù)多個(gè)分隔符當(dāng)一個(gè)處理,但不使用分隔符也不影響結(jié)果。 2 系統(tǒng)功能模塊結(jié)構(gòu)圖2.1 系統(tǒng)功能結(jié)構(gòu)框圖 主調(diào)程序模塊 系統(tǒng)功能模塊 雙向循環(huán)鏈表處理模塊 長(zhǎng)整數(shù)運(yùn)算模塊 界 面 模 塊

3、圖2.1 系統(tǒng)功能結(jié)構(gòu)圖2.2主要模塊的功能說(shuō)明： （1）主調(diào)程序模塊： void main() 初始化； do 接受命令； 處理命令； while(“命令”=”退出”) （2）雙向循環(huán)鏈表處理模塊 /cmplinklen.h /Creat.h /compare 說(shuō)明：進(jìn)行鏈表的存儲(chǔ)和處理 （3）長(zhǎng)整數(shù)運(yùn)算模塊 /add.h / sub.h /imul.h /idiv.h 說(shuō)明:對(duì)長(zhǎng)整數(shù)進(jìn)行四則運(yùn)算 （4）界面模塊 /title.h /welcome.h 說(shuō)明：控制系統(tǒng)運(yùn)行操作界面 3 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)及用法說(shuō)明3.1 概要說(shuō)明為了實(shí)現(xiàn)上述功能，采取雙向循環(huán)鏈表表示長(zhǎng)整數(shù)，每個(gè)結(jié)點(diǎn)含一個(gè)整型變量

4、，僅絕對(duì)值不超過(guò)9999的整數(shù)，整個(gè)鏈表用十進(jìn)制數(shù)表示。利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)表示長(zhǎng)整數(shù)的符號(hào)，相加過(guò)程不破壞兩個(gè)操作數(shù)鏈表，對(duì)長(zhǎng)整數(shù)位數(shù)不作上限。為此需要兩個(gè)結(jié)構(gòu)數(shù)據(jù)類(lèi)型：雙向循環(huán)鏈表和長(zhǎng)整數(shù)。3.2用法說(shuō)明 3.2.1 雙向循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)定義：typedef struct Node /雙向循環(huán)鏈表結(jié)點(diǎn) int data;struct Node *prior,*next;Node,*NodeList; 3.2.2 基本操作: Status conversion(char str,NodeList &oprh); /將字符串形式的操作數(shù)轉(zhuǎn)換成所需的類(lèi)型 int cmplinklen(Nod

5、eList opr1,NodeList opr2); /opr1鏈比opr2鏈長(zhǎng)則返回1，短則返回-1，否則返回0 int length(NodeList oprr); /求鏈表長(zhǎng)度 Status Creat(NodeList &oprr,int len); /生成指定長(zhǎng)度鏈表 int compare(NodeList opr1,NodeList opr2); /比較opr1、opr2絕對(duì)值的大小 4 涉及到的函數(shù)的描述 4.1長(zhǎng)整數(shù)操作函數(shù)Status input(NodeList &opr1,NodeList &opr2,char str)； /從鍵盤(pán)輸入兩個(gè)長(zhǎng)整數(shù)，存至opr1和opr2

6、中Status output(NodeList oprr,char str)； /在屏幕打印長(zhǎng)整數(shù)oprrStatus add_bas(NodeList opr1,NodeList opr2,NodeList &oprr)； /本算法實(shí)現(xiàn)A,B相加的操作Status sub_bas(NodeList opr1,NodeList opr2,NodeList &oprr)； /本算法實(shí)現(xiàn)A,B相減的操作Status imul(NodeList opr1,NodeList opr2,NodeList &oprr)； /本算法實(shí)現(xiàn)A,B相乘的操作Status idiv(NodeList opr1,No

7、deList opr2,NodeList &quti,NodeList &remand)； /本算法實(shí)現(xiàn)A,B相除的操作4.2主要函數(shù) 主程序模塊: /int main()雙向循環(huán)鏈表處理模塊: /Status conversion(char str,NodeList &oprh); /int cmplinklen(NodeList opr1,NodeList opr2); /Status Creat(NodeList &oprr,int len); /int compare(NodeList opr1,NodeList opr2);長(zhǎng)整數(shù)四則運(yùn)算模塊: /Status add_bas(Nod

8、eList 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 程序流程圖加法運(yùn)算

9、退 出減法運(yùn)算 開(kāi) 始?xì)g迎界面 主調(diào)函數(shù) 輸入數(shù)據(jù) 操作界面 除法運(yùn)算 乘法運(yùn)算 輸出數(shù)據(jù) 輸出數(shù)據(jù) 退出？ 否 退出？ 是 程序結(jié)束程序結(jié)束 圖5.1 主要算法流程圖 6 程序測(cè)試(1) 程序運(yùn)行環(huán)境為DOS界面，執(zhí)行文件為“長(zhǎng)整數(shù)四則運(yùn)算.exe”(2) 進(jìn)入演示程序后即顯示文本方式的用戶(hù)界面 圖6.1 用戶(hù)界面(3) 輸入命令，執(zhí)行相應(yīng)的功能： 1-加法運(yùn)算 2-減法運(yùn)算 3-乘法運(yùn)算 4-除法運(yùn)算 5-退出系統(tǒng) 圖6.2 執(zhí)行界面(4) 加法運(yùn)算測(cè)試 圖6.3 加法運(yùn)算界面 (5) 減法運(yùn)算測(cè)試 圖6.4 減法運(yùn)算界面(6) 乘法運(yùn)算測(cè)試 圖6.5 乘法運(yùn)算界(7) 除法運(yùn)算測(cè)試 圖6

10、.6 除法運(yùn)算界面7 參考文獻(xiàn)1 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）M.北京：清華大學(xué)出版社，20062 呂國(guó)英.算法設(shè)計(jì)與分析M.北京：清華大學(xué)出版社，20063 徐寶文，李志.C程序設(shè)計(jì)語(yǔ)言M.北京：機(jī)械工業(yè)出版社，20044 滕國(guó)文.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)M.北京：清華大學(xué)出版社，20105 蘇仕華.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（第2版）M.北京：機(jī)械工業(yè)出版社，20106 李建學(xué)，李光.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)案例精編M.北京：清華大學(xué)出版社，20107 汪沁，奚李峰.數(shù)據(jù)結(jié)構(gòu)與算法M.北京：清華大學(xué)出版社，20128 奚小玲，敖廣武.數(shù)據(jù)結(jié)構(gòu)理論與實(shí)踐M.北京：東北大學(xué)出版社，2010 附錄：程序清單(帶有

11、必要的注釋)#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;/=輸入模塊=/求指數(shù)函數(shù)值int axp(int a,int k)int

12、 r=1;if(k=0)return 1;for(;k0;k-)r=r*a;return r;/輸入轉(zhuǎn)換函數(shù)Status conversion(char str,NodeList &oprh)/將字符串形式的操作數(shù)轉(zhuǎn)換成所需的類(lèi)型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-)/若輸入的數(shù)不合法就返回重新輸入if(i!=0 | (str0!=- & str0!=+)&(stri9 | strinext

13、-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;/輸入函數(shù)Status input(NodeList &opr1,NodeList &opr2,char str)int flag=OK,i,n=0,l; char bMAX; printf(n請(qǐng)輸入第一個(gè)操作數(shù):n);scanf(%s,b);getchar();l=strlen(b);for(i=0;il;i+)if(bi!=,)strn

14、+=bi;strn=0;flag=conversion(str,opr1); while(!flag) printf(ERROR!Input again:n); scanf(%s,str); getchar(); flag=conversion(str,opr1);printf(n請(qǐng)輸入第二個(gè)操作數(shù):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)/若要輸出的數(shù)為0則執(zhí)行stri+=0;else while(p!=oprr) num0=p-da

15、ta/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;/=預(yù)處理及雜項(xiàng)操作模塊=/緩沖區(qū)部分初始化函數(shù)Status initbuf(char str)int i;for(i=0;iprior;p2=opr2-prior;while(p1-prior!=opr1

16、& p2-prior!=opr2)p1=p1-prior;p2=p2-prior;if(p1-prior!=opr1)return 1;if(p2-prior!=opr2)return -1;return 0;/求鏈表長(zhǎng)度int length(NodeList oprr)int count=0;NodeList p=oprr-next;while(p!=oprr)count+;p=p-next;return count;/生成指定長(zhǎng)度鏈表Status Creat(NodeList &oprr,int len)NodeList p;oprr=(NodeList)malloc(LEN);p=opr

17、r;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絕對(duì)值的大小int compare(NodeList opr1,NodeList opr2)NodeList p1,p2;p1=opr1-next;p2=opr2-next;if(cmplinklen(opr1,opr2)=1)/opr1比較長(zhǎng)return 1;else if(cmplinklen(opr1,opr2)=-1)/opr

18、2比較長(zhǎng)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)/本算法實(shí)現(xiàn)A,B相加的操作。int CF,buffer; NodeList p1,p2,p3;oprr=(Nod

19、eList)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則產(chǎn)生進(jìn)位，賦給CF /將新建結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后 p3=(NodeList)malloc(LEN); oprr-next-prior=p3; p3-prior=oprr;p3-next=oprr-next;oprr-next=p3;p3-data=b

20、uffer%10000;/應(yīng)該將buffer的第四位賦給p3-datap1=p1-prior;p2=p2-prior;while(p1!=opr1)/處理opr1鏈的剩余部分buffer=p1-data+CF;CF=buffer/10000;p3=(NodeList)malloc(LEN);/將新建結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后 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-dat

21、a+CF;CF=buffer/10000;p3=(NodeList)malloc(LEN);/將新建結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后 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;/減法基本操作Stat

22、us sub_bas(NodeList opr1,NodeList opr2,NodeList &oprr)/本算法實(shí)現(xiàn)A,B相減的操作。/將A鏈分成與B鏈長(zhǎng)相等的底位部分,和剩余的高位部分,并做相應(yīng)處理。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鏈的長(zhǎng)度小于等于opr1鏈的if(p1-datadat

23、a+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鏈?zhǔn)Ｏ碌牟糠謎f(p1-datadata-CF;CF=1;elsebuffer=p1-data-CF;CF=0;p3=(NodeLi

24、st)malloc(LEN); oprr-next-prior=p3; p3-prior=oprr;p3-next=oprr-next;oprr-next=p3; p3-data=buffer;p1=p1-prior;/處理鏈表開(kāi)頭結(jié)點(diǎn)值為0的無(wú)意義情況，若鏈表本身表示0，則不做如下處理 p3=oprr-next;while(p3-data=0 & p3-next!=oprr)p3=p3-next;flag=1;if(flag)qh=oprr-next;/保存無(wú)用結(jié)點(diǎn)的頭尾指針 qt=p3-prior;/為釋放做準(zhǔn)備 oprr-next=p3;/重接next鏈 p3-prior=oprr;/重

25、接prior鏈qt-next=NULL; while(qh!=NULL)/重接prior鏈 qq=qh; qh=qh-next; free(qq);oprr-data=+;return OK;/-帶符號(hào)加法函數(shù)-Status add(NodeList opr1,NodeList opr2,NodeList &oprr)if(opr1=NULL | opr2=NULL)return ERROR;if(opr1-data=opr2-data)/opr1,opr2符號(hào)相同add_bas(opr1,opr2,oprr);if(opr1-data=+)/opr1與opr2均為正數(shù)，即A+B的形式(A,B

26、均是正數(shù)，下同)oprr-data=+;else/opr1與opr2均為負(fù)數(shù)，即(-A)+(-B)的形式oprr-data=-;else/符號(hào)不相同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;/-帶符號(hào)減法函數(shù)-Status

27、sub(NodeList opr1,NodeList opr2,NodeList &oprr)if(opr1=NULL | opr2=NULL)return ERROR;if(opr1-data=opr2-data)/opr1,opr2符號(hào)相同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

28、-data=-;else/Adata=+;else/opr1,opr2符號(hào)不同add_bas(opr1,opr2,oprr);if(opr1-data=+)oprr-data=+;elseoprr-data=-;return OK;/=乘法模塊=/乘法函數(shù)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小則被乘數(shù)跟乘數(shù)調(diào)換ph

29、1=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+

30、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;/處理鏈表開(kāi)頭結(jié)點(diǎn)值為0的無(wú)意義情況，若鏈表本身表示0，則不做如下處理flag=0; p3=oprr-next;while(p3-data=0 & p3-next!=oprr)p3=p3-next;flag=1;if(flag)qh=oprr-next;/保存無(wú)用結(jié)點(diǎn)的頭尾指針 qt=p3-prior;/為釋放做準(zhǔn)備 oprr-next=p3;/重接ne

31、xt鏈 p3-prior=oprr;/重接prior鏈qt-next=NULL; while(qh!=NULL)/釋放無(wú)用結(jié)點(diǎn) qq=qh; qh=qh-next; free(qq);if(opr1-data=opr2-data | oprr-next-data=0)oprr-data=+;elseoprr-data=-;return OK;/=除法模塊=/除法子函數(shù)int idiv_sub(NodeList &opr1,NodeList opr2)NodeList p1,p2,qh,qt,qq;int count,CF,buffer,flag;count=0;while(compare(op

32、r1,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鏈?zhǔn)Ｏ碌牟糠輇uffer=p1-data-CF;p1-data=buffer;/清頭0flag=0; p1=opr1-next; while(

33、p1-data=0 & p1-next!=opr1) p1=p1-next; flag=1; if(flag) qh=opr1-next;/保存無(wú)用結(jié)點(diǎn)的頭尾指針 qt=p1-prior;/為釋放做準(zhǔn)備 opr1-next=p1;/重接next鏈 p1-prior=opr1;/重接prior鏈 qt-next=NULL; while(qh!=NULL)/釋放無(wú)用結(jié)點(diǎn) qq=qh; qh=qh-next; free(qq);count+;return count;/除法函數(shù)Status idiv(NodeList opr1,NodeList opr2,NodeList &quti,NodeLis

34、t &remand)/quti為商數(shù)鏈，remand為余數(shù)鏈int len_quti,len_reman,buffer;NodeList q1,q2,pq;if(compare(opr1,opr2)=-1)/除數(shù)比被除數(shù)大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);/開(kāi)辟商數(shù)鏈 Creat(reman

35、d,len_reman);/開(kāi)辟余數(shù)鏈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