孫魏東_實(shí)驗(yàn)一.doc

《孫魏東_實(shí)驗(yàn)一.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)預(yù)習(xí)實(shí)驗(yàn)報(bào)告1、問題分析實(shí)驗(yàn)任務(wù)：用指向指針的指針的方法對n個(gè)整數(shù)排序并輸出。要求將排序單獨(dú)寫成一個(gè)函數(shù)，n和個(gè)整數(shù)在主函數(shù)中輸入，最后在主函數(shù)中輸出。即用鍵盤輸入若干個(gè)數(shù)據(jù)，運(yùn)用快速排序?qū)斎氲臄?shù)據(jù)進(jìn)行排序，然后將排序后的數(shù)據(jù)全部的輸出到屏幕上。關(guān)鍵問題：（1）如何定義一個(gè)指向指針的指針來指向n個(gè)整數(shù)序列（2）用什么算法進(jìn)行排序（3）排序時(shí)單獨(dú)定義一個(gè)函數(shù)，其從主函數(shù)中如何將需要排序的參數(shù)傳遞到子函數(shù)中去。（4）所采用的算法的時(shí)間復(fù)雜度如何，以及算法是否會(huì)浪費(fèi)內(nèi)存空間和運(yùn)行時(shí)耗費(fèi)大量的時(shí)間。數(shù)據(jù)類型：因?yàn)橹皇菍?shù)據(jù)進(jìn)行排

2、序操作，所以程序中的輸入的數(shù)據(jù)的類型為整型變量，輸入的數(shù)據(jù)的范圍為整型變量int的取值范圍，個(gè)數(shù)可以從鍵盤輸入任意數(shù)。測試數(shù)據(jù)：第一組：3，2，1預(yù)計(jì)輸出：1,2,3第二組：3,2,1，-2,8預(yù)計(jì)輸出：-2,1,2,3,8第三組：3,2,0，1，4，-1,8,6預(yù)計(jì)輸出：-1,0,1,2,3,4,6,8第四組：j，15，1，m，10，5，6，8預(yù)計(jì)輸出：程序崩潰2、概要設(shè)計(jì)（1）該算法的主要問題就在于如何定義一個(gè)指向指針的指針來指向n個(gè)整數(shù)序列以及如何對數(shù)據(jù)進(jìn)行操作。（2）在這里我們本程序采用快速排序算法，可以將給定的若干個(gè)無序

3、的數(shù)據(jù)數(shù)組任選其中的一個(gè)元素，比如第一個(gè)，首先找到該元素的對應(yīng)的位置的下標(biāo)，然后再以該元素的下標(biāo)為基準(zhǔn)，將數(shù)組分為兩段，再尋找第二個(gè)元素的下標(biāo)位置，依次類推就可以完成所有的數(shù)據(jù)的排序操作了。（3）本程序主要包含3個(gè)函數(shù)1）主函數(shù)main()2）快速排序函數(shù)Quicksort()3）找到第一個(gè)元素下標(biāo)函數(shù)Quickpass()（4）函數(shù)調(diào)用關(guān)系如下：1、詳細(xì)設(shè)計(jì)（1）由于本程序只是一個(gè)排序的算法，所以在程序的數(shù)據(jù)結(jié)構(gòu)上可以采用數(shù)組這種順序存儲(chǔ)結(jié)構(gòu)，首先定義一個(gè)長度為n的數(shù)組，再定義int*a，a為指向該數(shù)組的指針變量，然后輸入n的值

4、，a=newint[n];此時(shí)a為指向數(shù)組的首地址的指針變量。再定義一個(gè)指向a指針變量的指針數(shù)組q,可以先對其數(shù)組的大小賦初值int*q[100];再把指針a的地址傳遞給q，用指針q數(shù)組來分別指向a指針，從而實(shí)現(xiàn)指向指針的指針指向了整數(shù)序列。（2）在排序上利用快速排序算法來實(shí)現(xiàn)對整型數(shù)據(jù)的排序操作，首先定義一個(gè)函數(shù)voidQuicksort(int*r[],intlow,inthigh);函數(shù)的形參部分（int*r[]）傳遞了指針數(shù)組q，和數(shù)組的第一個(gè)元素下標(biāo)（low）和最后一個(gè)元素的下標(biāo)（high）。再定義一個(gè)可以找到元素某位置

5、下標(biāo)的函數(shù)intQuickpass(int*r[],intlow,inthigh)，函數(shù)的形參部分（int*r[]）傳遞了指針數(shù)組q，和數(shù)組的第一個(gè)元素下標(biāo)（low）和最后一個(gè)元素的下標(biāo)（high）。（3）首先在這組無序的整型數(shù)據(jù)中找到第一個(gè)數(shù)據(jù)正確排序后所對應(yīng)的下標(biāo)。再以剛剛找到的元素的下標(biāo)為基準(zhǔn)把數(shù)據(jù)分為兩段，分別找出這兩段數(shù)據(jù)中第一個(gè)元素所對應(yīng)的數(shù)據(jù)的下標(biāo)，最終當(dāng)所有的元素位置都找到時(shí)，循環(huán)結(jié)束，輸出整型數(shù)據(jù)的排序。2、調(diào)試分析（1）程序中遇到的一些問題和解決辦法:在編寫程序的過程中基本都很順利，唯一一個(gè)遇到的問題就是在輸出

6、結(jié)果的時(shí)候出現(xiàn)過結(jié)果全部都是類似隨機(jī)數(shù)隨機(jī)數(shù)的值，也就是在指針傳遞數(shù)據(jù)的過程中發(fā)生了錯(cuò)誤，導(dǎo)致輸出的指針?biāo)鶎?yīng)的值出現(xiàn)類似隨機(jī)數(shù)的值，即指針為空，經(jīng)過一些調(diào)試發(fā)現(xiàn)在輸出語句中，printf("%d",*q[h]);中的‘*’忘記寫了，導(dǎo)致輸出的結(jié)果并不是該指針對應(yīng)的數(shù)據(jù)，而是該指針的地址，也就是一串類似于隨機(jī)數(shù)的值。（1）算法的時(shí)空分析：1）空間性能：在整個(gè)程序中，由于利用了指向指針的指針指向的數(shù)組，所以在存儲(chǔ)空間上造成了一定的浪費(fèi)，但是相對是比較少的。2）時(shí)間性能：本程序采用的是快速排序算法來進(jìn)行對數(shù)據(jù)的排序操作，所以在對數(shù)據(jù)的

7、操作上相對于普通的冒泡排序等算法快了很多，經(jīng)過大量的數(shù)據(jù)測試發(fā)現(xiàn)，當(dāng)數(shù)據(jù)量越大時(shí)，快速排序在時(shí)間上的優(yōu)越性體現(xiàn)的越明顯。（2）經(jīng)驗(yàn)體會(huì)：通過本次的程序編寫，讓我第一次對于程序的時(shí)間和空間性能有了新的理解，懂得了在程序開發(fā)中，我們不僅僅要實(shí)現(xiàn)程序預(yù)期的功能，同時(shí)也應(yīng)該注重程序在時(shí)間和空間上性能。1、用戶使用說明（1）程序運(yùn)行的環(huán)境為dos環(huán)境下，程序執(zhí)行開始時(shí)顯示如圖1所示：圖1開始程序（2）輸入需要排序的數(shù)據(jù)的個(gè)數(shù)，按回車鍵結(jié)束。（3）按提示輸入該組數(shù)據(jù)中第幾個(gè)元素的數(shù)據(jù)，按回車鍵結(jié)束。（4）輸入完成后自動(dòng)打印出排序結(jié)果。（5）程

8、序結(jié)束，按任意鍵退出程序。2、測試結(jié)果（1）輸入排序數(shù)據(jù)個(gè)數(shù)3，分別輸入（3,2,1）幾個(gè)測試數(shù)據(jù)，所得排序后數(shù)據(jù)為（1,2,3），運(yùn)行結(jié)果如下：（2）輸入測試輸入排序數(shù)據(jù)個(gè)數(shù)5，分別輸入（3,2,1，-2,8）幾個(gè)測試數(shù)據(jù)，所得排序后數(shù)據(jù)為（-2