任意長(zhǎng)整數(shù)的加法數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告書題目:任意長(zhǎng)整數(shù)的加法院系:計(jì)算機(jī)科學(xué)與應(yīng)用班級(jí)：11級(jí)計(jì)算機(jī)科學(xué)與技術(shù)s目錄目錄21 概述32 系統(tǒng)分析32.1 抽象數(shù)據(jù)類型定義32.2 功能詳細(xì)描述及框圖43 概要設(shè)計(jì)53.1 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)53.2 主要功能邏輯過(guò)程和實(shí)現(xiàn)算法54詳細(xì)設(shè)計(jì)74.1 鏈表設(shè)計(jì)74.2 人機(jī)交互界面WView84.3 力口法計(jì)算函數(shù)Calculate104.4 字符串分析函數(shù)AnaAdd：125調(diào)試分析與測(cè)試135.1 調(diào)試分析135.2 測(cè)試結(jié)果186總結(jié)與心得216.1 課程設(shè)計(jì)過(guò)程中出現(xiàn)的技術(shù)難點(diǎn)和解決方法：216.2 課程設(shè)計(jì)期間的主要收獲：21參考文獻(xiàn):212

2、21概述課程設(shè)計(jì)是實(shí)踐性教學(xué)中的一個(gè)重要環(huán)節(jié)，它以某一課程為基礎(chǔ)，可以涉及和課程相關(guān)的各個(gè)方面，是一門獨(dú)立于課程之外的特殊課程。課程設(shè)計(jì)是讓同學(xué)們對(duì)所學(xué)的課程更全面的學(xué)習(xí)和應(yīng)用，理解和掌握課程的相關(guān)知識(shí)。數(shù)據(jù)結(jié)構(gòu)是一門重要的專業(yè)基礎(chǔ)課,是計(jì)算機(jī)理論和應(yīng)用的核心基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，要求學(xué)生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面，加深對(duì)課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。2系統(tǒng)分析為實(shí)現(xiàn)上述程序功能，應(yīng)以雙向循環(huán)鏈表表示長(zhǎng)整數(shù)。為此，需要定義一個(gè)抽象數(shù)據(jù)類型。2.1抽象數(shù)據(jù)類型定義抽象

3、數(shù)據(jù)類型定義為：ADTOrderedList數(shù)據(jù)對(duì)象：D=ai|aiGint,i=1,2，n,n0數(shù)據(jù)關(guān)系：R1=|ai-1,aiD|=2,n基本操作：Creat(stringa)操作結(jié)果：通過(guò)字符串a(chǎn)構(gòu)造兩個(gè)位數(shù)不限的長(zhǎng)整數(shù)。addtwo(head0,head1result)初始條件：head0,head1都已存在，且head。的絕對(duì)值比head1大操作結(jié)果：result等于head。和head1的和。Add(head0,head1)初始條件：head0,head1都已存在。操作結(jié)果：判斷head。與head1絕對(duì)值的大小，并使head0的絕對(duì)值比headl大Display(result)初

4、始條件：result已存在。操作結(jié)果：按四位一組，分隔符為,的格式，在屏幕上輸出resultADTOrderedList2.2功能詳細(xì)描述及框圖1)主程序模塊：voidmain()初始化；do接受命令；處理命令；while(“命令”=退出”)2)-集合單元模塊一一實(shí)現(xiàn)集合的抽象數(shù)據(jù)類型3)、結(jié)點(diǎn)結(jié)構(gòu)單元模塊一一定義集合的結(jié)點(diǎn)結(jié)構(gòu)各模塊之間的調(diào)用關(guān)系如下：圖2.1功能流程圖3概要設(shè)計(jì)3.1數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)1)主程序模塊：2)集合單元模塊一一實(shí)現(xiàn)集合的抽象數(shù)據(jù)類型3)結(jié)點(diǎn)結(jié)構(gòu)單元模塊一一定義集合的結(jié)點(diǎn)結(jié)構(gòu)LinkList:Creat(stringa)基本操作：Creat(stringa)操作結(jié)果：通

5、過(guò)字符串a(chǎn)構(gòu)造兩個(gè)位數(shù)不限的長(zhǎng)整數(shù)。addtwo(head0,head1result)初始條件：head0,head1都已存在，且head。的絕對(duì)值比headl大操作結(jié)果：result等于head。和headl的和。Add(head0,head1)初始條件：head0,head1都已存在。操作結(jié)果：判斷head。與headl絕對(duì)值的大小，并使head。的絕對(duì)值比headl大Display(result)初始條件：result已存在。操作結(jié)果：按四位一組，分隔符為,的格式，在屏幕上輸出resultADTOrderedList3.2主要功能邏輯過(guò)程和實(shí)現(xiàn)算法void LinkList:Add()/

6、實(shí)現(xiàn)兩個(gè)整數(shù)相加LinkNode*temp;if(abs(head0-pre-data)abs(head1-pre-data)/兩個(gè)整數(shù)中，絕對(duì)值大的為被加數(shù)addtwo();elseif(abs(head0-pre-data)pre-data)temp=head0;head0=head1;head1=temp;addtwo();elseif(abs(head0-pre-data)=abs(head1-pre-data)intk1,k2;LinkNode*p=head0,*q=head1;/如果節(jié)點(diǎn)數(shù)相同，則判斷節(jié)點(diǎn)中數(shù)值大小while(p-data=q-data&p!=head0-pre-p

7、re&q!=head1-pre-pre)p=p-next;q=q-next;k1=p-data;k2=q-data;if(k1k2)addtwo();elsetemp=head0;head0=head1;head1=temp;addtwo();4詳細(xì)設(shè)計(jì)4.1 鏈表設(shè)計(jì)根據(jù)需要，設(shè)計(jì)了一個(gè)雙向循環(huán)鏈表CircleDoubleChain,其抽象數(shù)據(jù)類型定義如下:AbstractDataTypeCircleDoubleChain數(shù)據(jù)對(duì)象:D=ai|aiElemSet,i=1,2，,n,n呈0數(shù)據(jù)關(guān)系:R1=|ai-1,aiD,i=2,n基本操作：CircleDoubleChain。操作結(jié)果：構(gòu)造一

8、個(gè)只有頭結(jié)點(diǎn)的空鏈表。CircleDoubleChain(charsign,intlen)初始條件：已知鏈表要保存的數(shù)據(jù)的符號(hào)和長(zhǎng)度。操作結(jié)果：構(gòu)造一個(gè)頭結(jié)點(diǎn)值為len或-len,長(zhǎng)度為len的空鏈表。CircleDoubleChain(charsign,intarray)初始條件：存在數(shù)組array口，且知道數(shù)組array口中存放數(shù)據(jù)的符號(hào)。操作結(jié)果：構(gòu)造一個(gè)存放有array口數(shù)組的鏈表。insertTail(intx)初始條件：雙向循環(huán)鏈表存在。操作結(jié)果：向該鏈表尾插入值為x的結(jié)點(diǎn)。insertHead(intx)初始條件：雙向循環(huán)鏈表存在。操作結(jié)果：向該鏈表頭插入值為x的結(jié)點(diǎn)。delHe

9、ad()初始條件：雙向循環(huán)鏈表存在。操作結(jié)果：刪除鏈表頭結(jié)點(diǎn)。destroy(CircleDoubleChainchain)初始條件：雙向循環(huán)鏈表存在。操作結(jié)果：刪除鏈表，釋放鏈表所占內(nèi)存空間。結(jié)點(diǎn)定義：publicclassCDNodepublicintvalue;/結(jié)點(diǎn)值publicCDNodeprev,next;/|fT后兩個(gè)指針4.2 人機(jī)交互界面WViewpublicclassWViewextendsFrameimplementsWindowListener,ActionListenerintleft=500,top=500,height=500,width=500;publicSt

10、ringwrongmsg1=您輸入的第一個(gè)加數(shù)有誤，請(qǐng)重新輸入！;/錯(cuò)誤提示信息publicStringwrongmsg2=您輸入的第二個(gè)加數(shù)有誤，請(qǐng)重新輸入！;/錯(cuò)誤提示信息TextFieldadder1,adder2,result;Labeltip1,tip2,add1,add2,show,nothing;Buttoncalculate,clean;WView（Strings）/定義部署窗口，添加組件以及監(jiān)聽器super（s）;tip1=newLabel（請(qǐng)按以下格式輸入兩個(gè)加數(shù)：*,*,*）;tip2=newLabel（每四位一組，組間用逗號(hào)隔開）；add1=newLabel（,力口數(shù)1

11、）;add2=newLabel（,力口數(shù)2）;calculate=newButton（計(jì)算）；show=newLabel（結(jié)果）；adderl=newTextField(15);adder2=newTextField(15);result=newTextField(15);clean=newButton(清屏)；setLayout(newFlowLayout();calculate.addActionListener(this);clean.addActionListener(this);setBounds(left,top,width,height);setVisible(true);val

12、idate。；addWindowListener(this);publicvoidactionPerformed(ActionEvente)if(e.getSource()=calculate)/用戶按下計(jì)算按鈕Stringstr1=adder1.getText();Stringstr2=adder2.getText();if(AnaAdd.check(s懺1)=false)/檢查加數(shù)1輸入格式是否正確JOptionPane.showMessageDialog(calculate,wrongmsg1,ERROR”,0);elseif(AnaAdd.check(str2)=false)/檢查加數(shù)

13、2輸入格式是否正確JOptionPane.showMessageDialog(calculate,wrongmsg2,ERROR,0);else/兩個(gè)輸入均正確，調(diào)用Calculate函數(shù)進(jìn)行計(jì)算，并將結(jié)果返回給用戶Stringstr=Calculate.Calcula(str1,str2);result.setText(str);return;elseif(e.getSource()=clean)/用戶按下清屏按鈕，將輸入輸出框清空adderl.setText(null);adder2.setText(null);result.setText(null);return;4.3 加法計(jì)算函數(shù)C

14、aCulate圖4.ICalcultate算法流程圖Calculate函數(shù)定義:publicclassCalculateprivatestaticintshorter;/記錄較短的表長(zhǎng)privatestaticintlonger;/記錄較長(zhǎng)的表長(zhǎng)privatestaticshortbignum;/記錄絕對(duì)值大的表的序號(hào)privatestaticshortsmallnum;/記錄絕對(duì)值小的表的序號(hào)privatestaticshortcases;/記錄異號(hào)情況，絕對(duì)值比較結(jié)果privatestaticintsum;/記錄當(dāng)前結(jié)點(diǎn)的和publicstaticbooleansignJudge(Circ

15、leDoubleChainchainl,CircleDoubleChainchain2)/判斷兩個(gè)鏈表的符號(hào)是否相同publicstaticvoidcompare(CircleDoubleChain口chain)/比較鏈表長(zhǎng)度,longer,shorter,bignum,smallnum賦值publicstaticCircleDoubleChainsameAdd(CircleDoubleChain口chain)同號(hào)相加Cpare(chain);chain2=newCircleDoubleChain(chainbignum.judgeSign(),longer);/新鏈表符號(hào)長(zhǎng)度與較長(zhǎng)鏈表符號(hào)相

16、同/*從低位向高位開始計(jì)算，若兩個(gè)數(shù)的和大于10000,前面結(jié)點(diǎn)中的值+1,同時(shí)還要考慮前面的結(jié)點(diǎn)是否為頭結(jié)點(diǎn)，若是頭結(jié)點(diǎn)，需要向前面插入結(jié)點(diǎn)。分為鏈表長(zhǎng)度相同和長(zhǎng)度不同兩種情況考慮，分開計(jì)算，寫完后，為了簡(jiǎn)化代碼，又把這兩種情況合并，逐步考慮，先計(jì)算相同的位數(shù)，然后將較長(zhǎng)的鏈表多出來(lái)的位數(shù)同新鏈表的對(duì)應(yīng)位相加。*/returnchain2;publicstaticvoidabsMax(CircleDoubleChain口chain)/異號(hào)情況，比較兩個(gè)數(shù)的絕對(duì)值，并給cases賦值,cases=0絕對(duì)值相同；cases=1chain0絕對(duì)值大；cases=2chain1絕對(duì)值大publics

17、taticCircleDoubleChaindiffAdd(CircleDoubleChain口chain)/異號(hào)相absMax(chain);switch(cases)case0:/結(jié)果為0case1:/鏈表長(zhǎng)度相同case2:/表長(zhǎng)不等returnchain2;publicstaticStringCalcula(Stringstrl,Stringstr2)/進(jìn)行加法計(jì)算CircleDoubleChain口chain;Stringresult;/存儲(chǔ)計(jì)算結(jié)果chain=newCircleDoubleChain3;chain0=newCircleDoubleChain(AnaAdd.sign(

18、str1),AnaAdd.toNums(str1);chain1=newCircleDoubleChain(AnaAdd.sign(str2),AnaAdd.toNums(str2);if(Calculate.signJudge(chain0,chain1)=true)符號(hào)判斷chain2=Calculate.sameAdd(chain);elsechain2=Calculate.diffAdd(chain);result=AnaAdd.toOutStr(chain2);/將計(jì)算結(jié)果轉(zhuǎn)化成字符串給resultchain=null;/銷毀數(shù)組鏈表，釋放空間returnresult;4.4 字符串

19、分析函數(shù)AnaAdd:publicclassAnaAddprivatestaticStringcheckregex=A(-?)+0-91,4+(,|,)0-94)*+$;/檢查輸入的正則表達(dá)式staticStringsplitstr;/存儲(chǔ)拆分后的字符串staticString口mergestr;/存儲(chǔ)鏈表中的數(shù)字轉(zhuǎn)化成的字符串，每組四位staticStringoutstr=;/存儲(chǔ)輸出字符串publicstaticbooleancheck(Strings)/利用正則表達(dá)式檢查輸入是否正確publicstaticcharsign(Strings)/將符號(hào)保存在sign中charsign;ret

20、urnsign;publicstaticinttoNums(Strings)/將字符串轉(zhuǎn)化為數(shù)組，存儲(chǔ)在nums口中int口nums;returnnums;publicstaticStringtoOutStr(CircleDoubleChainchain)/將鏈表中的數(shù)據(jù)轉(zhuǎn)化為字符串returnoutstr;5調(diào)試分析與測(cè)試5.1 調(diào)試分析雖然這次設(shè)計(jì)的僅僅是個(gè)簡(jiǎn)單的加法器，可是由于實(shí)踐比較少，設(shè)計(jì)過(guò)程中出現(xiàn)了很多問(wèn)題，修改了無(wú)數(shù)次，幾乎每行代碼都修改過(guò)。有時(shí)候陷入死角，找不出問(wèn)題所在，使我一度懷疑自己到底適不適合學(xué)計(jì)算機(jī)，可是往往到了第二天，問(wèn)題就解決了，更多的問(wèn)題又接踵而至。我用了十天的時(shí)

21、間，終于把這個(gè)項(xiàng)目做出來(lái)了。在項(xiàng)目開發(fā)過(guò)程中，一邊開發(fā)，一邊測(cè)試，前面的測(cè)試沒(méi)有問(wèn)題后才繼續(xù)后面的內(nèi)容1 .字符串分析模塊測(cè)試：測(cè)試數(shù)據(jù)：str0=12345678”;str1=123,4567”;str2=-1111,1111;測(cè)試方法：publicstaticvoidmain(String口args)Stringstr口=newString3;str0=12345678”;str1=123,4567;str2=-1111,1111;for(intj=0;j3;j+)AnaAddlyl=newAnaAdd();if(lyl.check(strj)=true)System.out.print(

22、lyl.sign(strj);intnm=lyl.toNums(strj);for(inti=0;ilyl.toNums(strj).length;i+)System.out.print(nmi+/);elseSystem.out.print(非法字符用!/);System.out.println(分析完成);測(cè)試結(jié)果：kniAdd.Jivakpjlica非法字苻串！分瀛成一V23/745674分析完成m11”分析完成圖5.1字符串分析測(cè)試結(jié)果2 .雙向循環(huán)鏈表測(cè)試(部分)測(cè)試方法：publicstaticvoidtest()intarray;array=newint10;for(inti=0

23、;i10;i+)arrayi=i;CircleDoubleChainchain=newCircleDoubleChain(-,array);System.out.println(chain.head.value);chain.current=chain.head.next;while(chain.current!=chain.head)System.out.print(/+chain.current.value);chain.current=chain.current.next;System.out.println(end);chain.delHead();/刪除首節(jié)點(diǎn)System.out.p

24、rintln(chain.head.value);chain.current=chain.head.next;while(chain.current!=chain.head)System.out.print(/+chain.current.value);chain.current=chain.current.next;System.out.println(end);測(cè)試結(jié)果：CiicLeDoulleChainJavaAplicationD：VMyEcL10圖5.2鏈表測(cè)試結(jié)果3 .加法計(jì)算函數(shù)Calculate這一部分是耗時(shí)最長(zhǎng)的一部分了，用了五、六天的時(shí)間寫這一部分。測(cè)試這部分的時(shí)候出現(xiàn)了很

25、多問(wèn)題。其中有一個(gè)問(wèn)題印象較深：當(dāng)測(cè)試1,0001,0001與-1,0001,0001進(jìn)行力口法計(jì)算的時(shí)候，總是出現(xiàn)死機(jī)情況，懷疑可能是循環(huán)出問(wèn)題了。便檢查diffAdd算法，開始調(diào)用了abxMax函數(shù)，該函數(shù)用到了delHead(刪除首節(jié)點(diǎn))函數(shù)，于是在delHead函數(shù)中插入了錯(cuò)誤警告語(yǔ)句：if(head.value=0)JOptionPane.showMessageDialog(null,刪除首節(jié)點(diǎn)時(shí)發(fā)生錯(cuò)誤,ERROR,0)；結(jié)果真是這里出現(xiàn)問(wèn)題，于是得出在鏈表為空時(shí)，調(diào)用了dealHead函數(shù)?？墒亲屑?xì)檢查abxMax函數(shù)，并沒(méi)有什么錯(cuò)誤，將其轉(zhuǎn)化成其它表達(dá)方式，還是出現(xiàn)同樣錯(cuò)誤，一

26、時(shí)陷入了困境，晚上睡覺(jué)都在想。后來(lái)檢查diffAdd算法，發(fā)現(xiàn)后面也用到了delHead函數(shù)，原來(lái)是后面的循環(huán)控制語(yǔ)句出現(xiàn)了錯(cuò)誤，將while(chain2.head.next.value=0)chain2.delHead();改為while(chain2.head.next.value=0&chain2.head.next!=chain2.head)chain2.delHead();后，問(wèn)題解決了。測(cè)試：根據(jù)算法設(shè)計(jì)，這部分測(cè)試實(shí)例應(yīng)該包括以下內(nèi)容：同號(hào)相加分4種情況：正數(shù)鏈表長(zhǎng)度相同，正數(shù)鏈表長(zhǎng)度不同，負(fù)數(shù)鏈表長(zhǎng)度相同，負(fù)數(shù)鏈表長(zhǎng)度不同；異號(hào)相加分5種情況：結(jié)果為0,正數(shù)與負(fù)數(shù)鏈表長(zhǎng)度相同

27、且正數(shù)絕對(duì)值大，正數(shù)與負(fù)數(shù)鏈表長(zhǎng)度相同且負(fù)數(shù)絕對(duì)值大，正數(shù)比負(fù)數(shù)鏈表長(zhǎng)度長(zhǎng)，負(fù)數(shù)比正數(shù)鏈表長(zhǎng)度長(zhǎng)；測(cè)試方法：publicstaticvoidmain(String口args)throwsExceptionString口s=null;s=newString9;s0=00;s1=1,0001,0001;s2=-1,0001,0001;s3=-123;s4=-2345,1200”;s5=1111,1111;s6=-1111,1111;s7=123,1299,0000”;s8=-1299,1212;CircleDoubleChain口chain;chain=newCircleDoubleChain3;

28、chain0=newCircleDoubleChain(AnaAdd.sign(s2),AnaAdd.toNums(s2);chain1=newCircleDoubleChain(AnaAdd.sign(s1),AnaAdd.toNums(s1);if(Calculate.signJudge(chain0,chain1)=true)chain2=Calculate.sameAdd(chain);elsechain2=Calculate.diffAdd(chain);System.out.println(chain2.head.value);chain2.current=chain2.head.

29、next;while(chain2.current!=chain2.head)System.out.println(chain2.current.value);chain2.current=chain2.current.next;/System.out.println(AnaAdd.toOutStr(chain2);/chain=null;4 .算法復(fù)雜度分析本程序中用到的數(shù)據(jù)結(jié)構(gòu)比較簡(jiǎn)單，時(shí)間復(fù)雜度也比較簡(jiǎn)單從低位向高位開始計(jì)算，逐位相加。時(shí)間復(fù)雜度T(n)=O(n),n為鏈表的長(zhǎng)度。該運(yùn)算需要用到三個(gè)鏈表，存放兩個(gè)加數(shù)的鏈表和存放結(jié)果的鏈表空間復(fù)雜度S(n)=O(3n),n為長(zhǎng)度5 .沒(méi)有

30、解決的問(wèn)題有時(shí)候，當(dāng)計(jì)算結(jié)果較長(zhǎng)時(shí)，會(huì)把上一次的計(jì)算結(jié)果一并顯示出來(lái)，如圖:宜取評(píng)使用民帝神法鐳請(qǐng)按以F格式輸入兩個(gè)加數(shù)：5M產(chǎn)圖5.3錯(cuò)誤結(jié)果68是上次計(jì)算的結(jié)果，-9999,0000,6660是本次計(jì)算的結(jié)果。當(dāng)計(jì)算結(jié)果較短時(shí)，就不會(huì)出現(xiàn)這樣的問(wèn)題，不知道是什么原因。6 .總結(jié)體會(huì)實(shí)踐出真知，這次算是體會(huì)到了。小到數(shù)組的初始化，正則表達(dá)式的編寫，大到鏈表的創(chuàng)建，算法的設(shè)計(jì)，每一步都有收獲。并且熟悉了構(gòu)造函數(shù)和類變量的應(yīng)用。由于個(gè)人能力有限，界面的設(shè)計(jì)比較簡(jiǎn)單，算法寫得也不夠簡(jiǎn)練，還有一些小問(wèn)題沒(méi)有解決。5.2測(cè)試結(jié)果請(qǐng)按以下格式輸入西個(gè)加數(shù)，*,*每四位一組，殂間用逗號(hào)隔開L111U0Q加數(shù)1加數(shù)2結(jié)果計(jì)算I清房圖5.4測(cè)試結(jié)果1請(qǐng)按以下格式構(gòu)入兩個(gè)加數(shù)：草出產(chǎn)*每四位一期，組間用逗號(hào)隔開圖5.5測(cè)試結(jié)果2我迎轉(zhuǎn)用后整財(cái)法與13叵區(qū)請(qǐng)按以下格式輸入兩個(gè)加數(shù);*,*清局圖5.6測(cè)試結(jié)果3E歐四作用長(zhǎng)整效加法事請(qǐng)按以下格式輸入西不加數(shù)：*/*,*每四但一歲，加數(shù)1加數(shù)2結(jié)果計(jì)算圖5.7測(cè)試結(jié)果4歡總使用k整數(shù)hi法鼻_n|x請(qǐng)按以下格式輸入