數(shù)據(jù)結(jié)構(gòu)實驗報告二.doc

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