數據結構實驗報告二.doc

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