數據結構課程設計報告畢業論文(已修改)

　

【正文】 《數據結構課程設計》報告書2012/2013 第1學期 專業班級：_________ 學 號：_________ 學生姓名：_________ 計算機信息工程學院一．課程認識數據結構課程主要是研究非數值計算的程序設計問題中所出現的計算機操作對象以及它們之間的關系和操作的學科。數據結構是介于數學、計算機軟件和計算機硬件之間的一門計算機專業的核心課程，它是計算機程序設計、數據庫、操作系統、編譯原理及人工智能等的重要基礎，廣泛的應用于信息學、系統工程等各種領域。學習數據結構是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。通過課程設計可以提高學生的思維能力，促進學生的綜合應用能力和專業素質的提高。通過此次課程設計主要達到以下目的：n 了解并掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力；n 初步掌握軟件開發過程的問題分析、系統設計、程序編碼、測試等基本方法和技能；n 提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力； 訓練用系統的觀點和軟件開發一般規范進行軟件開發，培養軟件工者所應具備的科學的工作方法和作風。二．課題選擇內部排序演示（一）問題描述及分析：設計一個測試程序比較幾種內部排序算法的關鍵字比較次數和移動次數以取得直觀感受。(1) 對起泡排序、直接排序、簡單選擇排序、快速排序、希爾排序、堆排序算法進行比較；(2) 待排序的元素的關鍵字為整數。其中的數據要用偽隨機產生程序產生(如10000個)，至少用5組不同的輸入數據做比較，再使用各種算法對其進行排序，記錄其排序時間，再匯總比較。（gettickcount()）（二）數據結構描述： 本程序采用順序表結構，具體結構定義如下：typedef struct { ElemType *elem。 int length。}SqList。（三）主要算法流程描述： addlist(SqList amp。L)//初始化順序表 random(SqList amp。L)//隨機數產生程序3. void memory(SqList amp。M,SqList amp。L)//記錄L，使每個排序算法都用一組相同的隨機數4. void BubbleSort(SqList amp。L)//冒泡排序5. void InsertSort(SqList amp。L)//直接插入排序6. void SelectSort(SqList amp。L)//選擇排序7. int Partition(SqList amp。L,int low,int high)//快速排序8. void QSort(SqList amp。L,int low,int high)//對順序表的子序列作快速排序9. void ShellSort(SqList amp。L)//希爾排序10. void HeapAdjust(SqList amp。L,int s,int m )//[s]的關鍵字，[s…..m]成為一個大根堆11. void HeapSort(SqList amp。L)//對順序表L進行堆排序12. void main()主函數2. 主要代碼及程序說明includeiostreamincludeincludeincludeincludeusing namespace std。define LIST_INIT_SIZE 50000int bj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0,n。//yd，bj為記錄關鍵字比較和移動的次數typedef struct { int key。 }ElemType。typedef struct { ElemType *elem。 int length。}SqList。void addlist(SqList amp。L)//初始化順序表{a: printf(請輸入你要輸入的個數:)。 scanf(%d,amp。n)。 if(n50000) { printf(超出范圍重新輸入!!!\n)。 goto a。 } =(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType))。 if(!)exit(0)。}void random(SqList amp。L)//隨機數產生程序{ =0。static bool first=true。if(first){srand(time(0))。first=false。}//使輸入相同個數時每次產生的隨機數不同for(int i=1。in+1。i++)a: { [i].key=rand()。 if([i].key30000) goto a。 ++。 }}void memory(SqList amp。M,SqList amp。L)//記錄L，使每個排序算法都用一組相同的隨機數{ =0。 for(int i=1。in+1。i++) {[i].key=[i].key。 ++。 }}void BubbleSort(SqList amp。L)//冒泡排序{ int i,j。 for(i=1。i。i++) { for(j=1。j+1。j++) {bj1++。 if([j].key[j+1].key) { [0].key=[j].key。 [j].key=[j+1].key。 [j+1].key=[0].key。 yd1+=3。 } } }}void In