資料結構 實踐項目——資料結構、算法、程式設計

【項目1 - c/c++語言中函數參數傳遞的三種方式】

　　c語言提供了兩種函數參數傳遞的方式：傳值和傳位址。在c++中，又拓展了引用方式。通過本項目，确認自己已經掌握了這三種方式的原理，為後續學習做好準備。

　　下面是希望能夠交換兩個整型變量的swap函數的三個版本（從課程首頁中可以找到項目連結，複制後就能調試，不必費事敲代碼）：

　　下面是調用它們的main()函數：

　　請編制三個程式，分别調用三個版本的交換函數，觀察結果。釋出博文，展示程式及運作結果，解釋成功交換以及交換不成功的原因。請在紙上畫出調用過程中各變量的變化過程。

　　如果自己不能做出解釋，務必找“兄弟”幫忙，拿下這座小山頭。

【項目2 - 程式的多檔案組織】

　　學習資料結構，目标就是要編制出有相當規模的程式的。将所有的代碼放在一個檔案中的做法，不能适用現階段的需求了。

　　通過這個項目，确認有能力用多檔案組織程式。友善以後各章，我們就某一資料結構定義算法庫，并能引用算法庫進行實踐。

　　最簡單的多檔案組織，一個項目中有3個檔案：

　　(1) .h 頭檔案：定義資料類型、聲明自定義函數、定義宏等

　　(2).cpp 源檔案1：用于實作頭檔案中聲明的自定義函數

　　(3).cpp 源檔案2：定義main()函數，用于調用相關函數，實作問題求解目标。

　　請将例1.13中按方案3實作的程式，用多檔案形式組織并運作。 　　

　　在需要的地方，用 #include “自定義頭檔案”，使檔案之間的内容能“合起來”完成任務。

　　下面是寫在一個檔案中的程式：

【項目3 - 體驗複雜度】

　　（1）兩種排序算法的運作時間

　　排序是計算機科學中的一個基本問題，産生了很多種适合不同情況下适用的算法，也一直作為算法研究的熱點。本項目提供兩種排序算法，複雜度為o(n2)的選擇排序selectsort，和複雜度為o(nlogn)的快速排序quicksort，在main函數中加入了對運作時間的統計。

（2）漢諾塔

　　有一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的聖廟裡，一塊黃銅闆上插着三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次隻移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就将在一聲霹靂中消滅，而梵塔、廟宇和衆生也都将同歸于盡。

　　可以算法出，當盤子數為n個時，需要移動的次數是f(n)=2n−1。n=64時，假如每秒鐘移一次，共需要18446744073709551615秒。一個平年365天有31536000秒，閏年366天有31622400秒，平均每年31556952秒，移完這些金片需要5845.54億年以上，而地球存在至今不過45億年，太陽系的預期壽命據說也就是數百億年。真的過了5845.54億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。據此，2n從數量級上看大得不得了。

　　用遞歸算法求解漢諾塔問題，其複雜度可以求得為o(2n)，是指數級的算法。請到課程首頁下載下傳程式運作一下，體驗盤子數disccount為4、8、16、20、24時在時間耗費上的差異，你能忍受多大的disccount。

　　源程式見附後的程式3。

附：項目3的程式3——漢諾塔程式