數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---排序算法的實(shí)現(xiàn)

1、<p>　　課 程 設(shè) 計(jì)（論文）</p><p>　　課程名稱(chēng) 數(shù)據(jù)結(jié)構(gòu) </p><p>　　題目名稱(chēng) 排序算法的實(shí)現(xiàn) </p><p>　　學(xué)生學(xué)部（系） 藝術(shù)設(shè)計(jì)與計(jì)算機(jī) </p><p>　　專(zhuān)業(yè)班級(jí) 10

2、計(jì)算機(jī)1班 </p><p>　　2011 年12月05日</p><p>　　課程設(shè)計(jì)（論文）任務(wù)書(shū)</p><p>　　一、課程設(shè)計(jì)（論文）的內(nèi)容 </p><p><b>　　排序算法的實(shí)現(xiàn)</b></p><p>　　二、課程設(shè)計(jì)（論文）的要求與數(shù)據(jù)</p>

3、<p><b>　　（1）需求分析</b></p><p><b>　?。?）概要設(shè)計(jì)</b></p><p><b>　?。?）詳細(xì)設(shè)計(jì)</b></p><p><b>　?。?）編程實(shí)現(xiàn)</b></p><p>　?。?）測(cè)試: 提供數(shù)個(gè)測(cè)試

4、用例</p><p>　　（6）符合撰寫(xiě)規(guī)范設(shè)計(jì)的必要說(shuō)明文檔</p><p>　　三、課程設(shè)計(jì)（論文）應(yīng)完成的工作</p><p>　　（1）根據(jù)要求完成課題；</p><p>　?。?）程序書(shū)寫(xiě)符合規(guī)范，程序設(shè)計(jì)完善；</p><p>　　（3）對(duì)程序進(jìn)行初步的測(cè)試；</p><p>　　（

5、4）程序運(yùn)行結(jié)果和過(guò)程的界面截圖；</p><p>　?。?）根據(jù)設(shè)計(jì)規(guī)范撰寫(xiě)報(bào)告并按時(shí)提交；</p><p>　?。?）設(shè)計(jì)內(nèi)容用A4紙打印并按要求裝訂。</p><p>　　四、課程設(shè)計(jì)（論文）進(jìn)程安排</p><p>　　五、應(yīng)收集的資料及主要參考文獻(xiàn)</p><p>　　[1] 朱戰(zhàn)立.數(shù)據(jù)結(jié)構(gòu).北京:電子工業(yè)

6、出版社，2010 </p><p>　　[2] 吳偉民，嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) .北京: 清華大學(xué)出版社，2009</p><p>　　發(fā)出任務(wù)書(shū)日期： 2011 年 12 月 12日 指導(dǎo)教師簽名：</p><p>　　計(jì)劃完成日期： 2011 年 12 月 30 日 教學(xué)單位責(zé)任人簽章：</p><p&

7、gt;<b>　　目錄 </b></p><p><b>　　1序言1</b></p><p><b>　　1.1內(nèi)容1</b></p><p><b>　　1.2目的1</b></p><p><b>　　2 需求分析1</b&g

8、t;</p><p><b>　　2.1需求分析1</b></p><p>　　2.2 功能分析2</p><p><b>　　3概要設(shè)計(jì)2</b></p><p><b>　　4詳細(xì)設(shè)計(jì)3</b></p><p><b>　　5 程序

9、實(shí)現(xiàn)4</b></p><p><b>　　總結(jié)8</b></p><p><b>　　參考文獻(xiàn)9</b></p><p><b>　　1序言</b></p><p><b>　　1.1內(nèi)容</b></p><p>

10、;　　排序是對(duì)數(shù)據(jù)元素序列建立某種有序序列的過(guò)程。排序的方法有許多種，不同的排序方法特點(diǎn)不同。學(xué)習(xí)排序，主要有兩點(diǎn)，一個(gè)是每種排序的算法思想，另一個(gè)是每種排序方法的性能特點(diǎn)。</p><p><b>　　1.2目的</b></p><p>　　通過(guò)學(xué)習(xí)排序算法，我們可以掌握各種排序的基本思想、掌握各種排序方法的算法實(shí)現(xiàn)、掌握各種排序方法的優(yōu)劣分析及花費(fèi)的時(shí)間計(jì)算、掌握

11、各種排序方法所適應(yīng)的不同場(chǎng)合等等。 </p><p><b>　　2 需求分析</b></p><p><b>　　2.1需求分析</b></p><p>　　排序是對(duì)數(shù)據(jù)元素序列建立某種有序排列的過(guò)程。準(zhǔn)確的說(shuō)，排序是把一個(gè)數(shù)據(jù)元素序列整理成按關(guān)鍵字遞增（或遞減）排列的過(guò)程。所以說(shuō)，排序在生活中隨處可見(jiàn)，并且非常重要。&

12、lt;/p><p><b>　　2.2 功能分析</b></p><p><b>　　3概要設(shè)計(jì)</b></p><p>　　【直接插入排序的基本思想】順序的把待排序的數(shù)據(jù)元素按其關(guān)鍵字值的大小插入到已排序數(shù)據(jù)元素子集合的適當(dāng)位置。子集合的數(shù)據(jù)元素個(gè)數(shù)從只有一個(gè)數(shù)據(jù)元素開(kāi)始，逐次增大，當(dāng)子集合大小最終和集合大小相同時(shí)排序完畢。

13、</p><p>　　【直接選擇排序的基本思想】從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第一個(gè)數(shù)據(jù)元素交換位置；然后從不包括第一個(gè)位置上數(shù)據(jù)元素的集合中選取關(guān)鍵字最小的數(shù)據(jù)元素，并將它與數(shù)據(jù)元素集合中的第二個(gè)數(shù)據(jù)元素交換位置；重復(fù)如此，直到數(shù)據(jù)元素集合中只剩一個(gè)數(shù)據(jù)元素為止。</p><p>　　【冒泡排序的基本思想】設(shè)數(shù)組a中存放了n個(gè)數(shù)據(jù)元素，循環(huán)進(jìn)

14、行n-1趟如下的排序過(guò)程：第一趟時(shí)，依次比較相鄰兩個(gè)數(shù)據(jù)元素a[i].key和a[i+1].key（i=0,1,2，···，n-2），若為逆序，即a[i].key>[i+1].key，則交換兩個(gè)數(shù)據(jù)元素，否則不交換，這樣數(shù)值最大的數(shù)據(jù)元素將被放置在a[n-1]中；第二趟時(shí)，數(shù)據(jù)元素個(gè)數(shù)減1，即數(shù)據(jù)元素個(gè)數(shù)為n-1，操作方法和第一趟的類(lèi)似，這樣整個(gè)n個(gè)數(shù)據(jù)元素集合中數(shù)值次大的數(shù)據(jù)元素將被放置在a[n-2

15、]中；當(dāng)?shù)趎-1趟結(jié)束時(shí)，整個(gè)n個(gè)數(shù)據(jù)元素集合中次小的數(shù)據(jù)元素將被放置在a[1]中，a[0]中放置了最小的數(shù)據(jù)元素。</p><p><b>　　4詳細(xì)設(shè)計(jì)</b></p><p>　　直接排序算法，在已經(jīng)排好序的序列中查找待插入的元素的插入位置，并將待插入元素插入到有序列表的過(guò)程。</p><p>　　直接插入排序是由兩層嵌套循環(huán)組成的。外層

16、循環(huán)標(biāo)識(shí)并決定待比較的數(shù)值。內(nèi)層循環(huán)為待比較數(shù)值確定其最終位置。直接插入排序是將待比較的數(shù)值與它的前一個(gè)數(shù)值進(jìn)行比較，所以外層循環(huán)是從第二個(gè)數(shù)值開(kāi)始的。當(dāng)前一數(shù)值比待比較數(shù)值大的情況下繼續(xù)循環(huán)比較，直到找到比待比較數(shù)值小的并將待比較數(shù)值置入其后一位置，結(jié)束該次循環(huán)。值得注意的是，我們必需用一個(gè)存儲(chǔ)空間來(lái)保存當(dāng)前待比較的數(shù)值，因?yàn)楫?dāng)一趟比較完成時(shí)，我們要將待比較數(shù)值置入比它小的數(shù)值的后一位 插入排序類(lèi)似玩牌時(shí)整理手中紙牌的過(guò)程。插入排序的

17、基本方法是：每步將一個(gè)待排序的記錄按其關(guān)鍵字的大小插到前面已經(jīng)排序的序列中的適當(dāng)位置，直到全部記錄插入完畢為止。</p><p>　　直接插入排序的作法是：每次從無(wú)序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序。第一趟比較前兩個(gè)數(shù),然后把第二個(gè)數(shù)按大小插入到有序表中; 第二趟把第三個(gè)數(shù)據(jù)與前兩個(gè)數(shù)從前向后掃描，把第三個(gè)數(shù)按大小插入到有序表中；依次進(jìn)行下去，進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)

18、排序過(guò)程。直接插入排序?qū)儆诜€(wěn)定的排序，時(shí)間復(fù)雜性為o(n^2)，空間復(fù)雜度為O(1)。</p><p>　　直接選擇排序也是一種簡(jiǎn)單的排序方法，它的基本思想是：第一次從R[0]~R[n-1]中選取最小值，與R[0]交換，第二次從R{1}~R[n-1]中選取最小值，與R[1]交換，....，第i次從R[i-1]~R[n-1]中選取最小值，與R[i-1]交換，.....，第n-1次從R[n-2]~R[n-1]中選取最

19、小值，與R[n-2]交換,總共通過(guò)n-1次,得到一個(gè)按排序碼從小到大排列的有序序列。</p><p>　　冒泡排序的基本概念是：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。在第二趟：仍從第一對(duì)數(shù)開(kāi)始比較（因?yàn)?/p>

20、可能由于第2個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第1個(gè)數(shù)不再小于第2個(gè)數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個(gè)數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個(gè)新的最大數(shù)（其實(shí)在整個(gè)數(shù)列中是第二大的數(shù)）。如此下去，重復(fù)以上過(guò)程，直至最終完成排序。 由于在排序過(guò)程中總是小數(shù)往前放，大數(shù)往后放，相當(dāng)于氣泡往上升，所以稱(chēng)作冒泡排序。用二重循環(huán)實(shí)現(xiàn)，外循環(huán)變量設(shè)為i，內(nèi)循環(huán)變量設(shè)為j。外循環(huán)重復(fù)9次，內(nèi)循環(huán)依次重復(fù)9，8，

21、...，1次。每次進(jìn)行比較的兩個(gè)元素都是與內(nèi)循環(huán)j有關(guān)的，它們可以分別用a[j]和a[j+1]標(biāo)識(shí)，i的值依次為1,2,...,9，對(duì)于每一個(gè)i, j的值依次為1,2,...10-i。</p><p><b>　　5 程序?qū)崿F(xiàn)</b></p><p><b>　　直接插入排序算法</b></p><p>　　#includ

22、e <stdio.h></p><p>　　typedef int KeyType;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　KeyType key;</p><p>　　} DataType;</p>

23、<p>　　void InsertSort(DataType a[],int n)</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　DataType temp;</p><p>　　for(i=0;i<n-1;i++

24、)</p><p><b>　　{</b></p><p>　　temp=a[i+1];</p><p><b>　　j=i;</b></p><p>　　while(j>-1 && temp.key<a[j].key)</p><p><b

25、>　　{</b></p><p>　　a[j+1]=a[j];</p><p><b>　　j--;}</b></p><p>　　a[j+1]=temp;</p><p><b>　　}</b></p><p><b>　　}</b>

26、</p><p>　　void main(void)</p><p><b>　　{</b></p><p>　　DataType test[6]={1,4,6,3,9,10};</p><p>　　int i,n=6;</p><p>　　InsertSort(test,n);</p>

27、;<p>　　for(i=0;i<n;i++)</p><p>　　printf("%d ",test[i].key);</p><p><b>　　}</b></p><p><b>　　直接選擇排序算法</b></p><p>　　#include &

28、lt;stdio.h></p><p>　　typedef int KeyType;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　KeyType key;</p><p>　　}DataType;</p><

29、;p>　　void SelectSort (DataType a[],int n)</p><p><b>　　{</b></p><p>　　int i,j,small;</p><p>　　DataType temp;</p><p>　　for(i=0;i<n-1;i++)</p><

30、;p><b>　　{</b></p><p><b>　　small=i;</b></p><p>　　for(j=i+1;j<n;j++)</p><p>　　if(a[j].key<a[small].key) small=j;</p><p>　　if(small!=i)<

31、;/p><p><b>　　{</b></p><p>　　temp=a[i];</p><p>　　a[i]=a[small];</p><p>　　a[small]=temp;</p><p><b>　　}</b></p><p><b>

32、　　}</b></p><p><b>　　}</b></p><p>　　void main(void)</p><p><b>　　{</b></p><p>　　DataType test[6]={1,6,0,9,4,6};</p><p>　　int i,

33、n=6;</p><p>　　SelectSort(test,n);</p><p>　　for(i=0;i<n;i++)</p><p>　　printf("%d ",test[i].key);</p><p><b>　　}</b></p><p><b&g

34、t;　　冒泡排序算法</b></p><p>　　#include <stdio.h></p><p>　　typedef int KeyType;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　KeyType

35、 key;</p><p>　　}DataType;</p><p>　　void BubbleSort (DataType a[],int n)</p><p><b>　　{</b></p><p>　　int i,j,flag=1;</p><p>　　DataType temp;</

36、p><p>　　for(i=0;i<n&&flag==1;i++)</p><p><b>　　{</b></p><p><b>　　flag=0;</b></p><p>　　for(j=0;j<n-i;j++)</p><p><b>

37、　　{</b></p><p>　　if(a[j].key>a[j+1].key)</p><p><b>　　{</b></p><p><b>　　flag=1;</b></p><p>　　temp=a[j];</p><p>　　a[j]=a[j+1

38、];</p><p>　　a[j+1]=temp;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p>

39、<p>　　void main(void)</p><p><b>　　{</b></p><p>　　DataType test[6]={1,6,0,9,4,6};</p><p>　　int i,n=6;</p><p>　　BubbleSort(test,n);</p><p>

40、　　for(i=0;i<n;i++)</p><p>　　printf("%d ",test[i].key);</p><p><b>　　}</b></p><p><b>　　總結(jié)</b></p><p>　　課程設(shè)計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí),發(fā)現(xiàn),提出,分析和解

41、決實(shí)際問(wèn)題,鍛煉實(shí)踐能力的重要環(huán)節(jié),是對(duì)我們的實(shí)際工作能力的具體訓(xùn)練和考察過(guò)程。隨著科學(xué)技術(shù)發(fā)展的日新月異，當(dāng)今計(jì)算機(jī)應(yīng)用在生活中可以說(shuō)得是無(wú)處不在。因此作為二十一世紀(jì)的大學(xué)來(lái)說(shuō)掌握程序開(kāi)發(fā)技術(shù)是十分重要的，因此做好課程設(shè)計(jì)是十分必要的。 回顧起此次課程設(shè)計(jì)，至今我仍感慨頗多，的確，自從拿到題目到完成整個(gè)編程，從理論到實(shí)踐，在整整一個(gè)月的日子里，可以學(xué)到很多很多的東西，同時(shí)不僅可以鞏固了以前所學(xué)過(guò)的知識(shí)，而且學(xué)到了很多在書(shū)本上所沒(méi)有學(xué)到

42、過(guò)的知識(shí)。</p><p>　　從這次的課程設(shè)計(jì)中，我發(fā)現(xiàn)我理解和解決問(wèn)題的能力以及實(shí)踐能力都有了很大的提高，</p><p>　　自學(xué)能力也獲得了提升。做了這次課程設(shè)計(jì)，我覺(jué)得課程設(shè)計(jì)這種形式才是我們需要的，可以讓我們學(xué)到很多，包括書(shū)本內(nèi)的，以及課外的。在學(xué)習(xí)排序算法的時(shí)候，讀了書(shū)上的算法描述，覺(jué)得自己都會(huì)了，但到真正到編譯去實(shí)現(xiàn)他的時(shí)候，卻不是那么簡(jiǎn)單就能成功的，總會(huì)有這樣那樣的差錯(cuò)，

43、只能一次一次改，等到程序終于正確運(yùn)行的時(shí)候，才算真正會(huì)了這些算法。理論和實(shí)際總是有差別的，不去做是體會(huì)不出來(lái)的。坐在電腦前才真正知道自己會(huì)不會(huì)，眼高手低是要不得的。</p><p>　　通過(guò)這次課程設(shè)計(jì)，使說(shuō)我明白到，要做好一個(gè)課程設(shè)計(jì)，首先那要有一個(gè)完整的思路，才能做出一個(gè)好的程序。并且一個(gè)好的程序不是一次就能完成的，這需要修改許多次才能完成的。而我這次的程序?qū)崿F(xiàn)則是排序，排序是對(duì)數(shù)據(jù)元素序列建立某種有序序列的

44、過(guò)程。準(zhǔn)確的說(shuō)，排序是把一個(gè)數(shù)據(jù)元素序列整理成按關(guān)鍵字遞增（或遞減）排列的過(guò)程。所以說(shuō)，排序在生活中隨處可見(jiàn)，并且非常重要。學(xué)習(xí)排序，主要有兩點(diǎn)，一個(gè)是每種排序的算法思想，另一個(gè)是每種排序方法的性能特點(diǎn)。</p><p>　　回想起此次的程序設(shè)計(jì)，我仍感慨頗多。從老師給程序設(shè)計(jì)題目到完成整個(gè)編程，從理論到實(shí)踐，在整整一個(gè)月的日子里，我學(xué)到很多很多的東西。通過(guò)此次的程序設(shè)計(jì)，我不僅鞏固了以前所學(xué)過(guò)的知識(shí)，而且學(xué)到了

45、很多在書(shū)本上所沒(méi)有學(xué)到過(guò)的知識(shí)。經(jīng)過(guò)這次程序設(shè)計(jì)，使我明白到理論與實(shí)際相結(jié)合非常重要，平時(shí)我們只是學(xué)到理論知識(shí)，回到宿舍也沒(méi)有去練習(xí)，導(dǎo)致我們動(dòng)手能力普遍偏弱。只有自己親自去做。才能提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考問(wèn)題的能力。</p><p>　　通過(guò)實(shí)踐的學(xué)習(xí)，我認(rèn)識(shí)到學(xué)好計(jì)算機(jī)要重視實(shí)踐操作，不僅僅是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，還是其它的計(jì)算機(jī)方面的知識(shí)都要重在實(shí)踐，所以后在學(xué)習(xí)過(guò)程中，我會(huì)更加注視實(shí)踐操作，使自己便好地學(xué)

46、好計(jì)算機(jī)。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 朱戰(zhàn)立.數(shù)據(jù)結(jié)構(gòu).北京:電子工業(yè)出版社，2010 </p><p>　　[2] 吳偉民，嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) .北京: 清華大學(xué)出版社，2009</p><p>　　[3] 朱戰(zhàn)立.數(shù)據(jù)機(jī)構(gòu)—使用C語(yǔ)言典型題解與上機(jī)實(shí)驗(yàn)指導(dǎo).