數(shù)據(jù)結(jié)構(gòu)課程設計實習報告(已修改)
2025-01-30 21:54 本頁面
【正文】 數(shù)據(jù)結(jié)構(gòu)課程設計實習報告（排序操作）學 院：計算機學院 專 業(yè)： 班 級： 學 號： 姓 名： 指導教師： 完成日期： 目錄一、 需求分析……………………………………………… 11. 運行環(huán)境…………………………………………… 12. 程序所實現(xiàn)的功能………………………………… 13. 程序的輸入………………………………………… 14. 程序的輸出………………………………………… 1二、 設計說明……………………………………………… 11. 算法設計的思想…………………………………… 12. 主要的數(shù)據(jù)結(jié)構(gòu)設計說明………………………… 23. 程序的主要流程圖………………………………… 34. 程序的主要模塊 ………………………………… 35. 程序的主要函數(shù)及其偽代碼說明………………… 4三、 上機結(jié)果及體會……………………………………… 71. 實際完成的情況說明……………………………… 72. 程序算法的性能分析……………………………… 73. 程序運行時的初值和運行結(jié)果…………………… 84. 程序中可以改進的地方說明……………………… 115. 收獲及體會………………………………………… 116. 源程序及注釋……………………………………… 12四、 參考文獻……………………………………………… 19一、需求分析1. 運行環(huán)境：軟件環(huán)境：Microsoft Visual C++ 。2. 程序所實現(xiàn)的功能 本程序?qū)崿F(xiàn)了直接插入排序、折半插入排序、冒泡排序、簡單選擇排序、快速排序、堆排序、歸并排序等多種排序算法的功能，并且對每一種而言，都能輸出每一趟的排序結(jié)果。3. 程序的輸入： 本程序的輸入的格式為：元素+空格+元素，并按回車鍵結(jié)束輸入。如（49_38_65_97_76_13_27_49回車鍵），且本程序僅適用于整形數(shù)據(jù)。4. 程序的輸出： 本程序能輸出每一趟的排序結(jié)果，且輸出的格式和輸入的格式基本一致。 二、設計說明1. 算法設計的思想：(1)直接插入排序的算法設計思想為：將一個記錄插入到已排好的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。一般情況下，第i趟直接插入排序的操作為：在含有i1個記錄的有序子序列R[1...i1]中插入一個記錄R[i]后，變成含有i個記錄的有序的子序列R[1...i]；并且，和順序表類似，為了在查找插入位置的過程中避免數(shù)組下標出界，在R[0]出設置監(jiān)視哨。(2)折半插入排序的算法思想為：在一個有序表中進行折半查找和插入。第1頁(3)冒泡排序的算法思想為：首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進行比較，若為逆序（即LR[1].keyLR[2].key），則將兩個記錄交換之，然后比較第二個記錄的關(guān)鍵字和第三個記錄的關(guān)鍵字。依次類推，直至第n1個記錄和第n個記錄的關(guān)鍵字進行過比較為止。一般地，第i趟冒泡排序是從LR[1]到LR[ni+1]依次比較相鄰事物兩個記錄的關(guān)鍵字，并在“逆序”是交換記錄，其結(jié)果是這ni+1個記錄中關(guān)鍵字最大的記錄被交換到第ni+1的位置上。(4)簡單選擇排序的算法設計思想為：通過ni次關(guān)鍵字之間的比較，從ni+1個記錄中選擇出關(guān)鍵字最小的記錄，并和第i個記錄交換之。(5)快速排序的算法設計思想為：通過每一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。(6)堆排序的算法設計思想為：將初始序列建成一個堆，若在輸出堆頂?shù)淖钚≈岛?，使得剩余的n1個元素的序列重又建成一個堆，則得到n個元素中的次小值，如此反復執(zhí)行，便能得到一個有序的序列。(7)歸并排序的算法設計思想為：假設初始序列含有n個記錄，則可看成n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到[n2]個長度為2或1的有序子序列；再兩兩歸并，……，如此重復，直至得到一個長度為n的有序序列為止。2. 主要的數(shù)據(jù)結(jié)構(gòu)設計說明：(1) 本程序的儲存結(jié)構(gòu)主要采用順序表儲存結(jié)構(gòu)：typedef struct{ int key。 //關(guān)鍵字}RedType。 //記錄類型typedef struct{ RedType R[MAXSIZE+1]。//R[0]閑置為哨兵 int length。 //順序表長度}*SqList,sq。 //順序表類型(2)本程序的輸入與輸出均采用了“dowhile”語句，而主函數(shù)的功能選擇采用了“case”語句。如下是輸入函數(shù)的一段代碼： do { i++。 scanf(%d%c,amp。LR[i].key,amp。ch)。 第2頁 }while(ch!=39。\n39。)。 3. 程序的主要流程圖：菜單退出堆 排 序直接插入排序折半插入排序冒 泡 排 序歸 并 排 序快 速 排 序簡單選擇排序輸入待排序列按任意鍵返回輸出每一趟結(jié)果4. 程序的主要模塊： (1)菜單模塊由Menu()函數(shù)實現(xiàn)。第3頁 (2)各排序功能：直接插入排序模塊由InsertSort(SqList L)函數(shù)實現(xiàn)，折半插入排序模塊由BInsertSort(SqList L)函數(shù)實現(xiàn)，冒泡排序模塊由BubbleSort(SqList L)函數(shù)實現(xiàn)，簡單選擇排序模塊由SelectSort(SqList L)函數(shù)和SelectMinKey(SqList L,int i)函數(shù)實現(xiàn)，快速排序模塊由QSort(SqList L,int low ,int high)函數(shù)、QuickSort(SqList L)函數(shù)和Partition(SqList L,int low ,int high)函數(shù)實現(xiàn)，堆排序模塊由HeapAdjust(SqList L,int s,int m)函數(shù)和HeapSort(SqList L)函數(shù)實現(xiàn)，歸并排序模塊由MergeSort(SqList L, int length)函數(shù)實現(xiàn)。 (3)輸入與輸出模塊：輸入模塊由CreatSqList(SqList L)函數(shù)實現(xiàn)，輸出模塊由PrintSort(SqList L)函數(shù)和FiPrintSort(SqList L)函數(shù)實現(xiàn)。5. 程序的主要函數(shù)及其偽代碼說明： (1)直接插入排序： void InsertSort(Sq
公司管理相關(guān)推薦
鄂ICP備17016276號-1