《軟件技術(shù)基礎(chǔ)》實驗說明

《《軟件技術(shù)基礎(chǔ)》實驗說明》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、實驗一線性表的插入與刪除1.實驗?zāi)康恼莆站€性表在順序分配下的插入與刪除運算；掌握線性表的鏈式存儲結(jié)構(gòu)；掌握插入排序的方法；并掌握一種產(chǎn)生隨機數(shù)的方法。2.實驗內(nèi)容1．產(chǎn)生1000個0至999間的隨機整數(shù)，并以產(chǎn)生的次序存入一個數(shù)據(jù)文件中。2．編制一個程序，依次實現(xiàn)以下功能：(1)定義一個有序（非遞減）線性表，其最大容量為1000，初始時為空。(2)從由1產(chǎn)生的數(shù)據(jù)文件中依次取前N個隨機整數(shù)，陸續(xù)插入到此線性表中，并要求在每次插入后保持線性表的有序性。最后將此有序線性表打印輸出。(3)在由（2）產(chǎn)生的線性表中，依在1中產(chǎn)生的次序逐個將元素刪除，直至表空為止

2、。3．以N=100及N=400分別運行2的程序，并比較它們的運行時間。4．編寫一個程序，用插入排序依次將1中產(chǎn)生的1000個隨機整數(shù)鏈接成有序鏈表（不改變原隨機數(shù)在存儲空間中的順序）。3.實驗步驟和要求1．事先編制好實驗內(nèi)容中1、2、4的程序（可參考本實驗中的方法說明），并調(diào)試通過。2．運行1的程序，生成1000個0至999之間的隨機整數(shù)的數(shù)據(jù)文件，并打印輸出此數(shù)據(jù)文件。3．以N=100運行2的程序，并記下運行時間。4．以N=400運行2的程序，并記下運行時間。5．運行4的程序。6．整理程序清單和運行結(jié)果，寫出實驗報告。4.方法說明（1）隨機整數(shù)的產(chǎn)生產(chǎn)

3、生隨機整數(shù)的方法有很多，下面只介紹一種方法：設(shè)m=216，初值y0=0，則遞推公式y(tǒng)i=mod(2053yi-1+13849，m)產(chǎn)生0至65535之間的隨機整數(shù)。如要產(chǎn)生0至999之間的隨機整數(shù)，只需做運算xi=INT(1000yi/m)。其中mod（*）是模運算，INT（*）是取整函數(shù)。（2）線性表的插入與刪除在本實驗中線性表是動態(tài)增長的。插入一個新元素后，為了使線性表仍保持有序，必須要找到新元素應(yīng)插入的位置。實際上這是一個插入排序的問題。10為了要將新元素插入到一個有序的線性表中，可以從原有序表的最后一個元素開始，往前逐個與新元素比較，并將大于新元

4、素的所有元素都往后移動一個位置，直到找到新元素應(yīng)插入的位置為止。顯然，插入一個新元素后，表的長度也增加了1?，F(xiàn)假設(shè)用一個數(shù)組L(1:m)來存儲線性表，其中m為最大容量（在本實驗中為m=1000）；用一個變量n表示線性表的長度（在本實驗中，其初值為n=0）。則可以得到將新元素插入到有序線性表的算法如下。輸入：數(shù)組L(1:m)，有序線性表L(1:n)，需插入的新元素b。其中n

5、比較，直到發(fā)現(xiàn)一個元素與新元素相等。然后從當前位置的下一個元素開始，將后面所有元素都往前移動一個位置，直到線性表的最后一個位置為止。顯然，刪除一個元素之后，線性表的長度減小了1。其算法如下。輸入：線性表L(1:n)，n為線性表的長度，刪除的元素b（一定在線性表中）。輸出：刪除b后的線性表L(1:n)。在上述算法中，從線性表的第一個元素開始尋找要刪除的元素b,實際上我們還可以從線性表的最后一個元素開始尋找b，其算法留給讀者自行考慮。（3）線性鏈表的插入排序定義一個二列數(shù)組A(1:1000，1:2)，其中，A(i,1)(i=1,2,…,1000)依隨機數(shù)產(chǎn)生

6、的順序存放1000個數(shù)據(jù)，A(i,2)(i=1,2,…,1000)為鏈接指針，將1000個隨機數(shù)鏈接成有序鏈表。其插入排序的方法如下。依次從數(shù)據(jù)文件中讀入一個數(shù)據(jù)，將它按行順序存放到數(shù)組A的第一列中，然后通過相應(yīng)行的第二列將它鏈接到已經(jīng)有序的鏈表中。其過程為：將讀入的數(shù)據(jù)依次與鏈表中各元素進行比較，找到其應(yīng)該插入的位置后，適當改變鏈指針，將其插入。其算法如下：輸入：1000個隨機整數(shù)。10輸出：頭指針為H的有序鏈表。10實驗二二叉樹1.實驗?zāi)康恼莆斩鏄涞拇鎯Y(jié)構(gòu)2.實驗內(nèi)容1．對給定二叉樹用鏈式鏈式存儲結(jié)構(gòu)；利用隊列與棧對二叉樹進行運算。2．按層次輸出

7、所有結(jié)點。3．輸出所有葉子結(jié)點。4．將所有左右子樹值交換。3.實驗步驟和要求1．分別編制實驗內(nèi)容中題2、3、4的三個子程序。2．以上圖所示的二叉樹為例編制主程序，實現(xiàn)下述功能，并運行這個程序。（1）輸入二叉樹用鏈式結(jié)構(gòu)存儲；（2）調(diào)用題2的子程序，并輸出結(jié)果；（3）調(diào)用題3的子程序，并輸出結(jié)果；（4）調(diào)用題4的子程序，并輸出結(jié)果；3．自行設(shè)計一棵二叉樹，重復步驟2。4．整理程序清單與所有結(jié)果，并寫出實驗報告。4.方法說明（1）二叉樹的鏈式存儲結(jié)構(gòu)二叉樹的每一個結(jié)點i有三個域：值域V（i），左鏈域L（i），右鏈域R（i10）。我們分別用三個一維數(shù)組表示它們

8、，并用頭指針HBT指向二叉樹的根結(jié)點。具體存儲方案由讀者自行考慮。（2）按層次輸