課 程 設 計 報 告（2013 -2014第2學期）課程設計類型： 軟硬件設計 題 目： 通用排序程序 學 號： 121001260809 姓 名： 胡柳 專 業： 自動化，中美互認 指 導 教 師： 李建敦 課程設計日期： 2014.06.162014.06.20 目錄1. 課題分析11.1 背景介紹11.2 需求分析12. 總體設計32.1 總體思路32.2 相關技術33. 詳細設計43.1 設計原則43.2 模塊設計44. 實現與測試54.1 實現環境54.2 模塊實現54.3測試65. 總結與展望75.1 總結75.2 展望7參考文獻9附錄10答辯記錄131. 課題分析1.1 背景介紹排序是數據處理中經常使用的一種重要運算。設文件由n個記錄R1,R2,Rn組成，如n個學生記錄，每個學生記錄包括學號、姓名、班級等。n個記錄對應的關鍵字集合為K1,K2,Kn，如學生的學號。所謂排序就是將這n個記錄按關鍵字大小遞增或遞減重新排列。 當待排序記錄的關鍵字均不相同時，排序結果是唯一的，否則排序結果不唯一。如果文件中關鍵字相同的記錄經過某種排序方法進行排序后，仍能保持它們在排序之前的相對次序，則稱這種排序方法是穩定的；否則，這種排序方法是不穩定的。 由于文件大小不同使排序過程中涉及的儲存器不同，可將排序分成內部排序和外部排序兩類。整個排序過程都在內存進行的排序，稱為內部排序；反之，若排序過程中要進行數據的內、外存交換，則稱之為外部排序。內排序適用于記錄個數不是很多的小文件，而外排序則適用于記錄個數太多，不能一次性放入內存的大文件。 按策略劃分，內部排序方法可以分為五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。幾乎所有的排序都有兩個基本的操作： （1）關鍵字大小的比較。 （2）改變記錄的位置。具體處理方式依賴于記錄的存儲形式，對于順序型記錄，一般移動記錄本身，而鏈式存儲的記錄則通過改變指向記錄的指針實現重定位。 排序算法很多，不同的算法有不同的優缺點，沒有哪種算法在任何情況下都是最好的。評價一種排序算法好壞的標準主要有兩條： （1）執行時間和所需的輔助空間，即時間復雜度和空間復雜度； （2）算法本身的復雜程度，比如算法是否易讀、是否易于實現。在本次實驗設計程序中，編一通用排序程序，程序可以對任意類型的數值常數或字符串構成的行進行排序，通過人機對話選擇程序是按數值進行排序還是按字符順序進行排序。排序是針對數據文件的。例如初識數據為：12，24，9，128，3，76，345按數值大小排序應為：3，9，12，24，76，128，345按字符串大小排序應為：12，128，24，3，345，76，9需要將數據文件按數值大小進行排序，以及按字符大小進行排序。1.2 需求分析利用if-else語句根據輸入的代表不同功能的數字來用不同的方法處理數據。輸入數字1時用數值排序方式處理數據；輸入數字2時用字符方式排序法處理數據。輸入數字0時退出程序，輸入數字1時繼續程序。雖然排序有不同的方法，但是，其基本操作不外乎兩種： （1）關鍵字大小的比較。 2（2）改變記錄的位置。具體處理方式依賴于記錄的存儲形式，對于順序型記錄，一般移動記錄本身，而鏈式存儲的記錄則通過改變指向記錄的指針實現重定位。由本次課程設計的課題內容分析可得，解決問題的實際就是要建立一個單鏈表，將待排序的整型數據以結點的形式存儲在建立的單鏈表中。然后，依次對單鏈表中的結點數據進行簡單選擇排序，其中排序為從大到小排序用這種方法實現所要求的排序方式得到結果。162. 總體設計2.1 總體思路程序中要求利用人機對話實現選擇程序是按數值進行排序還是按字符順序進行排序，在這，可以利用if-else選擇語句對程序進行編寫，從而達到人機對話實現選擇程序是按數值進行排序還是按字符順序進行排序。本程序設計關于排序的基本思想是：鏈式簡單選擇排序的是每一趟在n-i+1（i=1,2,.,n-1)個記錄中選取關鍵字最大或最小的記錄作為有序序列中第i個記錄。本課程設計中以單鏈表為存儲結構，待排序的數據由偽隨機函數產生。因此，首先需要創建一個單鏈表，將待排序數據存儲在單鏈表中，然后用指針實現關鍵字的從大到小的排序。2.2 相關技術流程控制語句：for語句，switch，while語句等。這里用到了while語句和for語句。For語句的形式如下：for語句形式： for (表達式1； 表達式2； 表達式3) 語句； 執行過程： 首先計算“表達式1”（循環初值），且僅計算一次。每一次循環之前計算“表達 式2”（循環條件），如果其結果為真，則執行“語句”（循環體），并計算“表達式3”（循環增量）。否則，循環終止。While語句形式：while (表達式) 語句； 它的執行過程：首先計算“表達式” 的值，如果為真，則執行“語句” 。再次判斷，直至“表達式”的值為假結束循環。本程序的主函數通過定義一個鏈表結構體指針head，用以指向鏈表頭結點；設計一個循環輸入變量，控制相關方法的調用來實現鏈表的建立及對數據的排序。3. 詳細設計3.1 設計原則本程序的主函數通過定義一個鏈表結構體指針head，用以指向鏈表頭結點；設計一個循環輸入變量，控制相關方法的調用來實現鏈表的建立及對數據的排序。本程序通過if-else.選擇語句對程序進行編寫，從而達到人機對話實現選擇程序是按數值進行排序還是按字符順序進行排序。在控制流程過程中，選擇for語句和while語句達到對程序流程的循環控制。3.2 模塊設計可以用流程圖來展示函數流程圖選擇排序方式輸入數字1，2若是1若是2選擇數值排序方式選擇字符排序方式輸出排序結果選擇退出繼續若選擇0若選擇1結束4. 實現與測試4.1 實現環境本課程設計需要采用支持標準C/C+的Visual C+編譯器（6.0或更高版本），并采用最基礎的Windows xp控制臺程序。4.2 模塊實現1. 用戶可根據系統提示和用戶需要輸入12的操作數字。圖4.1 程序主界面2. 當用戶輸入1時，系統執行數值排序方式。圖4.2 輸出數值排序方式界面3. 當用戶輸入2時，系統執行字符順序排序。圖4.3 輸出字符排序方式界面4.3測試程序最后的測試結果輸出為：圖4.4 由上圖可得，當輸入的數據為12，24，9，128，3，76，345，選擇按數值大小排序是，輸出的排序結果為：3，9，12，24，76，128，345，與題目中所要求得到的結果一致，當輸入數據后選擇按字符大小排序得到的結果為：12，128，24，3，345，76，9，也題目所要求所得到的數據一致。說明程序編寫是正確的。5. 總結與展望5.1 總結本程序實現了對數據文件的排序功能，分別實現了按數值進行排序和按字符進行排序的功能，程序最后的運行結果，達到了題目所要求的通過人機對話實現選擇程序是按數值進行排序還是按字符順序進行排序。達到了課題的預期效果。此次課程設計中，我學習了簡單選擇排序。它是最基本的排序方法之一，比之于其他的排序方法而言思路更清晰操作更簡單。對于用線性順序表結構實現簡單選擇排序的算法描述，數據結構書本算法10.4已經給出了，而用鏈式存儲結構來實現的區別是循環方式的差別：順序表用一個for循環實現從下標1到n的排序，鏈式表的實現是一個while循環從頭結點開始直到最后一個結點。5.2 展望第一次做課程設計，因此感到期待而又非常緊張，一個星期，短暫而忙碌，但卻又充實、興奮。當我把程序寫出來，并運行正確后，我有種說不出的喜悅，雖然還有許多不足，但我對未來一片憧憬。 這次選課題，我選到的是“數據排序“，開始的我是無從下手，從網上搜了一氣后一無所獲，一味地依賴網上現成地答案使我毫無進展。后來，在同組同學地影響下，我開始靜下心來回憶學過的知識 。終于，經過反復調試后，我終于找到了思路，經過同組同學的幫助與網上資料，我逐漸將程序設計成型，雖然還有許多缺陷，比如，設計后還是不能人性化地滿足要求。雖然與想象中的還有很大差距，但我看到了希望，并決心一直努力下去。 一個星期的程序設計雖然馬上就要結束的，但是它帶給我的將會影響我今后的學習。在這次程序設計中，我不僅提高了編程的能力，也增加了我對這門課程的興趣，雖然一周的程序設計很忙，但過得的很充實、很有意義。但也有許多不足的地方，如界面設計的還不夠完美、還有一些最基本的知識沒有完全掌握等等。這為我以后的學習提出了要求。通過此次課程設計，使我更加扎實的掌握了有關C+方面的知識，在設計過程中雖然遇到了一些問題，但經過一次又一次的思考，一遍又一遍的檢查終于找出了原因所在，也暴露出了前期我在這方面的知識欠缺和對知識運用的不熟。在課程設計過程中，我不斷發現錯誤，不斷改正，不斷領悟，不斷獲取，最后終于調試成功。這次課程設計終于順利完成了，在設計中遇到了很多問題，通過查資料，終于游逆而解。課程設計誠然是一門專業課，給我很多專業知識以及專業技能上的提升，同時又是一門講道課，一門辯思課，給了我許多道，給了我很多思，給了我莫大的空間。同時，設計讓我感觸很深。通過這次課程設計，我掌握了if和for的循環語句。我認為，在這學期的學習中，不僅培養了獨立思考的能力，而且體現了合作的重要性。更重要的是，在課上，我們學會了很多學習的方法。而這是日后最實用的，真的是受益匪淺。要面對社會的挑戰，只有不斷的學習、實踐，再學習、再實踐。這對于我們的將來也有很大的幫助。回顧起此課程設計，至今我仍感慨頗多，從理論到實踐，在這段日子里，可以說得是苦多于甜，但是可以學到很多很多的東西，同時不僅可以鞏固了以前所學過的知識，而且學到了很多在書本上所沒有學到過的知識。通過這次課程設計使我懂得了理論與實際相結合是很重要的，只有理論知識是遠遠不夠的，只有把所學的理論知識與實踐相結合起來，從理論中得出結論，然后運用到生活中，最后才能真正為社會服務。在設計的過中遇到問題，可以說得是困難重重，但可喜的是最終都得到了解決。此次設計也讓我明白了思路即出路，有什么不懂不明白的地方要及時請教或上網查詢，只要認真鉆研，動腦思考，動手實踐，就沒有弄不懂的知識，收獲頗豐。參考文獻1 殷人昆. 數據結構用面向對象方法與C+語言描述. 2版, 北京: 清華大學出版社, 2009.2 嚴蔚敏, 吳偉民. 數據結構. C語言版, 北京: 清華大學出版社, 1997.3 蘇成, 姜薇, 蘇仁科. C+程序設計教程. 1版, 北京: 清華大學出版社, 2013.4 譚浩強. C+程序設計(第二版). 北京: 清華大學出版社, 2012.5 譚浩強. C+程序設計題解與上機指導(第二版). 北京: 清華大學出版社, 2012.附錄源程序為：#include#include struct string char str20;struct string *next;struct digital int dig;struct digital *next;void main() cout通用排序 n;int type,n,i,j,flag=1;while(flag)couttype;coutn;if(type=1) /數值排序struct digital *head,*tail,*newnode;int tp; /輸入數據head = new digital;tail = head;for(i=0;in;i+) newnode = new digital;couttp;newnode-dig=tp;tail-next=newnode;tail=newnode;tail-next=NULL;cout數據輸入完成. 開始排序.n; /排序struct digital *p;for(i=0;in-1;i+)p=head;for(j=0;jnext;if(p-dig p-next-dig) tp=p-dig;p-dig=p-next-dig;p-next-dig=tp;/輸出coutnext;while(p!=NULL) cout dig;p=p-next;else/字符串排序struct string *head,*tail,*newnode;char str20; /輸入數據head = new string;tail = head;for(i=0;in;i+) newnode = new string;coutstr;strcpy(newnode-str,str);tail-next=newnode;tail=newnode;tail-next=NULL;cout數據輸入完成. 開始排序.n; /排序struct string *p;char temp20;for(int i=0;in-1;i+)p=head;for(int j=0;jnext;if(strcmp(p-str,p-next-str)=1) strcpy(temp,p-str);strcpy(p-str,p-next-str);strcpy(p-next-str,temp);/輸出coutnext;while(p!=NULL) cout str;p=p-next;coutflag;另外一種程序編寫#include #include #include using namespace std;const int LEN=1000;const int NUMLEN=10;struct Ele int n; char numNUMLEN;eleLEN; /結構體里面兩個成員，n是整型，num是將n轉化成的字符串void deal(int m) /deal函數用來將int型轉化成字符串 int i; int tmpNUMLEN; int n=elem.n; int cou=0; while(n!=0) tmpcou=n%10; n=n/10; cou+; for(i=0;i0?1:-1;int cmpnum(const void *a,const void *b) return strcmp(*(struct Ele *)a).num,(*(struct Ele *)b).num)0?1:-1; /這兩個函數是qsort調用的，你可以百度下qsort的意思，我就不多加闡述了int main()