數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告二.doc

XXX計(jì)算機(jī)學(xué)院數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)二姓 名 ： 學(xué) 號(hào) ： 專 業(yè) ： 完成日期 ： XXXX計(jì)算機(jī)學(xué)院一、實(shí)驗(yàn)?zāi)康?. 理解順序存儲(chǔ)和鏈接存儲(chǔ)的基本思想。2. 掌握順序表和鏈表基本操作的實(shí)現(xiàn)。3. 理解順序表和鏈表的優(yōu)缺點(diǎn)。二、實(shí)驗(yàn)內(nèi)容1. 利用順序表實(shí)現(xiàn)大整數(shù)求和。（必做）2. 利用單鏈表實(shí)現(xiàn)一元多項(xiàng)式求和。（必做）3. 約瑟夫環(huán)問(wèn)題：設(shè)有編號(hào)為1，2，n的n ( n 0 ) 個(gè)人圍成一個(gè)圈，每個(gè)人持有一個(gè)密碼m，從第1個(gè)人開(kāi)始報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出圈，再?gòu)乃南乱粋€(gè)人起重新報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的出圈，。如此下去，直到所有人全部出圈為止。當(dāng)任意給定n和m后，設(shè)計(jì)算法求n個(gè)人出圈的次序。（選做）三、算法描述第一道題：1.輸入兩個(gè)大整數(shù)給字符型數(shù)組，初始化順序表A和B。 2.字符型數(shù)組中的大整數(shù)由低位依次轉(zhuǎn)化整數(shù)并放入為順序表A 和B中。 3將大整數(shù)相加。 3.1.初始化進(jìn)位標(biāo)志flag=0和順序表C； 3.2.求大整數(shù)A和B的長(zhǎng)度：n=A.length; m=B.length; 3.3.從個(gè)位開(kāi)始逐位開(kāi)始第i位的加法，直到A或B計(jì)算完畢： 3.3.1 計(jì)算第i位的值：C.datai=(A.datai+B.datai+flag)%10; 3.3.2 計(jì)算該進(jìn)位的進(jìn)位：flag=(A.datai+B.datai+flag)/10; 3.4.計(jì)算大整數(shù)A或B余下的部分，與進(jìn)位flag相加； 3.5.計(jì)算結(jié)果的位數(shù)。 4.用逆遍歷arcPrintList()輸出C。第二道題：1.工作指針pre、p、qre、q初始化； 2.while（p存在且q存在）執(zhí)行下列三種情形之一 2.1 如果p-exp小于q-exp,則指針p后移； 2.2 如果p-exp大于q-exp,則 2.2.1 將結(jié)點(diǎn)q插入到結(jié)點(diǎn)p之前； 2.2.2指針q指向原指結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)； 2.3 如果p-exp等于q-exp，則 2.3.1 p-coef =p-coef+q-coef; 2.3.2 如果p-coef=0,則執(zhí)行下列操作，否則，指針p后移； 2.3.3 刪除結(jié)點(diǎn)q; 2.3.4 使指針q指向它原指結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)； 3.如果q不為空，將結(jié)點(diǎn)q鏈接在第一個(gè)單鏈表的后面；四、程序清單說(shuō)明第一題:在cpp文件中，strlen()函數(shù)用來(lái)求字符型數(shù)組的長(zhǎng)度。 在main.h頭文件中，1. SeqList(DataType a,int n)函數(shù)是建立長(zhǎng)度為n的順序表。2. Change(SeqList A,char B,int n)函數(shù)中A.datab=a*10+Bi-0是將字符串?dāng)?shù)組的內(nèi)容轉(zhuǎn)換成整數(shù)，并輸入順序表A中。3. friend SeqList Add(SeqList A,SeqList B) 友元函數(shù)是將順序表A與順序表B的值相加。在Add函數(shù)中，C.length=(nm?n:m)+flag是判斷A與B的哪個(gè)表長(zhǎng)度更長(zhǎng)和表C的長(zhǎng)度；if運(yùn)算到最后存在進(jìn)位flag=1，則 C.dataC.length-1=1。3.1 for(;in;i+)是計(jì)算大整數(shù)A與B相加后，余下的部分。3.2 for(;im;i+)是計(jì)算大整數(shù)B與A相加后，余下的部分。 4. arcPrintList()函數(shù)是用逆向，由高位到低位輸出表C。第二題：五、實(shí)驗(yàn)結(jié)果第一題：輸入第一個(gè)大整數(shù):123 輸入第二個(gè)大整數(shù):987; 輸出計(jì)算的結(jié)果為:1110; 第二題:六、實(shí)驗(yàn)總結(jié) 這次實(shí)驗(yàn)對(duì)我來(lái)說(shuō),很難.讓我糾結(jié)了好久。最后還是沒(méi)能把第二道題必做的一元多項(xiàng)式求和做出來(lái)。鏈表很難。邏輯性對(duì)我來(lái)說(shuō)有點(diǎn)復(fù)雜。做第一題用順序表求和，不是很難。對(duì)于我來(lái)說(shuō)，難在大整數(shù)的輸入后，高位是排在前面的，在用順序表求和時(shí)，是要把低位移前，這有點(diǎn)難度。最后我用字符型輸入，再轉(zhuǎn)化成整數(shù)，這字符數(shù)組轉(zhuǎn)化成整型的過(guò)程，我忘了，經(jīng)過(guò)網(wǎng)上查了和看了書本，才發(fā)現(xiàn)這過(guò)程很簡(jiǎn)單。從這方面，我知道我的C+基礎(chǔ)沒(méi)打好，這么簡(jiǎn)單的