數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實(shí)習(xí)報告-wenkub
2023-02-02 21:54:52 本頁面
【正文】 數(shù)實(shí)現(xiàn)，冒泡排序模塊由BubbleSort(SqList L)函數(shù)實(shí)現(xià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)。 第2頁 }while(ch!=39。如下是輸入函數(shù)的一段代碼： do { i++。 //記錄類型typedef struct{ RedType R[MAXSIZE+1]。(6)堆排序的算法設(shè)計思想為：將初始序列建成一個堆，若在輸出堆頂?shù)淖钚≈岛?，使得剩余的n1個元素的序列重又建成一個堆，則得到n個元素中的次小值，如此反復(fù)執(zhí)行，便能得到一個有序的序列。依次類推，直至第n1個記錄和第n個記錄的關(guān)鍵字進(jìn)行過比較為止。 二、設(shè)計說明1. 算法設(shè)計的思想：(1)直接插入排序的算法設(shè)計思想為：將一個記錄插入到已排好的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。2. 程序所實(shí)現(xiàn)的功能 本程序?qū)崿F(xiàn)了直接插入排序、折半插入排序、冒泡排序、簡單選擇排序、快速排序、堆排序、歸并排序等多種排序算法的功能，并且對每一種而言，都能輸出每一趟的排序結(jié)果。3. 程序的輸入： 本程序的輸入的格式為：元素+空格+元素，并按回車鍵結(jié)束輸入。一般情況下，第i趟直接插入排序的操作為：在含有i1個記錄的有序子序列R[1...i1]中插入一個記錄R[i]后，變成含有i個記錄的有序的子序列R[1...i]；并且，和順序表類似，為了在查找插入位置的過程中避免數(shù)組下標(biāo)出界，在R[0]出設(shè)置監(jiān)視哨。一般地，第i趟冒泡排序是從LR[1]到LR[ni+1]依次比較相鄰事物兩個記錄的關(guān)鍵字，并在“逆序”是交換記錄，其結(jié)果是這ni+1個記錄中關(guān)鍵字最大的記錄被交換到第ni+1的位置上。(7)歸并排序的算法設(shè)計思想為：假設(shè)初始序列含有n個記錄，則可看成n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到[n2]個長度為2或1的有序子序列；再兩兩歸并，……，如此重復(fù)，直至得到一個長度為n的有序序列為止。//R[0]閑置為哨兵 int length。 scanf(%d%c,amp。\n39。 (3)輸入與輸出模塊：輸入模塊由CreatSqList(SqList L)函數(shù)實(shí)現(xiàn)，輸出模塊由PrintSort(SqList L)函數(shù)和FiPrintSort(SqList L)函數(shù)實(shí)現(xiàn)。++i){ if(LR[i].keyLR[i1].key) //需將LR[i]插入有序子表 { LR[0]=LR[i]。j) LR[j+1]=LR[j]。} (2)折半插入排序： void BInsertSort(SqList L){ //折半插入排序 int i,j,m,low,high。 //將LR[i]暫存到LR[0] low=1。 //插入點(diǎn)在低區(qū) else low=m+1。 //記錄后移 LR[high+1]=LR[0]。 for(i=1。j++) { //選擇表L中最大的依次放到最后面的位置中去 if(LR[j].keyLR[j+1].keyamp。 LR[j+1].key=m。 int SelectMinKey(SqList L,int i)。 //在LR[i..Llength]中選擇key最小記錄 if(i!=j){ //與第i個記錄交換 m=LR[i].key。} a=1。 if(lowhigh){ pivotloc=Partition(L,low,high)。 for(i=Llength/2。i1。 PrintSort(L)。 int *tmp = (int*)malloc(sizeof(int) * length)。 i *= 2) {// i為步長，1,2,4,8…… for (left_min = 1。 if (right_max length){ right_max = length+1。 right_min right_max){ tmp[next++] = LR[left_min].key LR[right_min].key ? LR[right_min++].key : LR[left_min++].key。} a=1。2. 程序算法的性能分析：第7頁3. 程序運(yùn)行時的初值和運(yùn)行結(jié)果： (1)直接插入排序： (2)折半插入排序：第8頁 (3)冒泡排序： (4)簡單選擇排序：第9頁 (5)快速排序： (6)堆排序：第10頁 (7)歸并排序：4. 程序中可以改進(jìn)的地方說明 本程序?qū)φ`操作的處理不是很理想，而且對數(shù)據(jù)的要求也比較嚴(yán)格，只能是int類型的數(shù)據(jù)才行，另外，堆排序不能將生成的堆以二叉樹的形式輸出。雖然在算法完成的過程中出現(xiàn)了好多問題，但我對這次課程設(shè)計的成果還是非常滿意的。不像以前那樣開始就直接寫代碼。 6. 源程序及注釋：includeinclude define MAXSIZE 30 //順序表的最大長度int a=1。//R[0]閑置為哨兵 int length。printf(第%d 趟排序結(jié)果為:,a++)。 }void FiPrintSort(SqList L) { //輸出最終結(jié)果 int i=1。 i++。 char ch。 scanf(%d%c,amp。\n39。 printf(初始的待排序列為:)。 return 1。 while(lowhigh){ while(lowhighamp。 while(lowhighamp。} LR[low]=LR[0]。 for(i=2。 for(j=i2。 //插入到正
公司管理相關(guān)推薦
鄂ICP備17016276號-1