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