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

2、輸入演示程序中規(guī)定的運(yùn)算命令，然后程序就計(jì)算并顯示出這兩個(gè)數(shù)的運(yùn)算。 （2）本演示程序中，數(shù)字字符限定為09和字符，輸入字符可以任意長，輸入形式以“回車符”為結(jié)束標(biāo)志，串中字符順序不限，且允許出現(xiàn)重復(fù)字符。 （3）利用雙向循環(huán)鏈表現(xiàn)實(shí)長整數(shù)的存儲，每個(gè)結(jié)點(diǎn)含一個(gè)整形變量。輸入的形式以回車結(jié)束，可以直接輸入正數(shù)或負(fù)數(shù)。按中國對于長整數(shù)的表示習(xí)慣，每四位一組，除數(shù)字和位于首位置的負(fù)號外，其它一切字符都將作為分隔符，連續(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)鏈表處理模塊 長整數(shù)運(yùn)算模塊 界 面 模 塊

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

4、，僅絕對值不超過9999的整數(shù)，整個(gè)鏈表用十進(jìn)制數(shù)表示。利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號表示長整數(shù)的符號，相加過程不破壞兩個(gè)操作數(shù)鏈表，對長整數(shù)位數(shù)不作上限。為此需要兩個(gè)結(jié)構(gòu)數(shù)據(jù)類型：雙向循環(huán)鏈表和長整數(shù)。3.2用法說明 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)換成所需的類型 int cmplinklen(nod

5、elist 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 涉及到的函數(shù)的描述 4.1長整數(shù)操作函數(shù)status input(nodelist &opr1,nodelist &opr2,char str)； /從鍵盤輸入兩個(gè)長整數(shù)，存至opr1和opr2

6、中status output(nodelist oprr,char str)； /在屏幕打印長整數(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);長整數(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)算 開 始?xì)g迎界面 主調(diào)函數(shù) 輸入數(shù)據(jù) 操作界面 除法運(yùn)算 乘法運(yùn)算 輸出數(shù)據(jù) 輸出數(shù)據(jù) 退出？ 否 退出？ 是 程序結(jié)束程序結(jié)束 圖5.1 主要算法流程圖 6 程序測試(1) 程序運(yùn)行環(huán)境為dos界面，執(zhí)行文件為“長整數(shù)四則運(yùn)算.exe”(2) 進(jìn)入演示程序后即顯示文本方式的用戶界面 圖6.1 用戶界面(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)算測試 圖6.3 加法運(yùn)算界面 (5) 減法運(yùn)算測試 圖6.4 減法運(yùn)算界面(6) 乘法運(yùn)算測試 圖6.5 乘法運(yùn)算界(7) 除法運(yùn)算測試 圖6

10、.6 除法運(yùn)算界面7 參考文獻(xiàn)1 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（c語言版）m.北京：清華大學(xué)出版社，20062 呂國英.算法設(shè)計(jì)與分析m.北京：清華大學(xué)出版社，20063 徐寶文，李志.c程序設(shè)計(jì)語言m.北京：機(jī)械工業(yè)出版社，20044 滕國文.數(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)換成所需的類型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請輸入第一個(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請輸入第二個(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;/求鏈表長度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=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絕對值的大小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)/opr

18、2比較長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鏈長相等的底位部分,和剩余的高位部分,并做相應(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鏈的長度小于等于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;/處理鏈表開頭結(jié)點(diǎn)值為0的無意義情況，若鏈表本身表示0，則不做如下處理 p3=oprr-next;while(p3-data=0 & p3-next!=oprr)p3=p3-next;flag=1;if(flag)qh=oprr-next;/保存無用結(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;/-帶符號加法函數(shù)-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均為正數(shù)，即a+b的形式(a,b

26、均是正數(shù)，下同)oprr-data=+;else/opr1與opr2均為負(fù)數(shù)，即(-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;/-帶符號減法函數(shù)-status

27、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

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

31、xt鏈 p3-prior=oprr;/重接prior鏈qt-next=null; while(qh!=null)/釋放無用結(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;/保存無用結(jié)點(diǎn)的頭尾指針 qt=p1-prior;/為釋放做準(zhǔn)備 opr1-next=p1;/重接next鏈 p1-prior=opr1;/重接prior鏈 qt-next=null; while(qh!=null)/釋放無用結(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);/開辟商數(shù)鏈 creat(reman

35、d,len_reman);/開辟余數(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-ne