數(shù)據(jù)結構上機基本習題-資料下載頁
2025-05-13 21:27本頁面
【正文】 , 48*, 60, 75, 80] [60, 80] [12, 75] [26, 48*] [12, 26, 48*, 75] [34, 48] 第二趟歸并： ? 合并兩個序列時，將合并得到的序列與原序列分開存放 ? 也可以用分治思路處理 先分解再歸并 ? 設初始關鍵字序列為 : [48 34 60 80 75 12 26 48*] [48 34 6O 80 75 12 26 48*] [75 12 26 48*] [48 34 60 80] [48 34] [60 80] [75 12] [26 48*] [48] [34] [60] [80] [75] [12] [26] [48*] [34 48] [60 80] [12 75] [26 48*] [12 26 48* 75] [34 48 60 80] [12 26 34 48 48* 60 75 80] 分解 歸并 兩路歸并排序算法 ? 遞歸算法 void MergeSort(待排序列 ) {//歸并排序 if (待排序列長度 1) { MergeSort(待排序列的前半?yún)^(qū)間 )； MergeSort(待排序列的后半?yún)^(qū)間 )； 已排好序的前半?yún)^(qū)間、后半?yún)^(qū)間合并成一個有序序列； }//if } // MergeSort ? 采用順序存儲結構，對于由下標 s~t界定的一個序列，前半?yún)^(qū)間為 s ~ (s+t)/2，后半?yún)^(qū)間為 (s+t)/2+1 ~ t void MergeSort(SqList amp。L, int s, int t) {//歸并排序 if (s t) { m = (s+t)/2。 MergeSort(L, s, m)； MergeSort(L, m+1, t)； Merge(L, s, m, t)。//合并 [s]~[m]與 [m+1]~[t] }//if } // MergeSort 兩路歸并算法 ? 以順序表作為存儲結構 void Merge(SqList amp。L, int i, int m, int n) {//兩路歸并 //引入輔助數(shù)組空間 temp，有序序列為 r[i..m]和 r[m+1..n] } // Merge b = i。 for(j = m+1,k =1。 i =m amp。amp。 j=n。 ++k) { } //for//ifi] if ([i].key [j].key) [k] = [i++]。 else [k] = [j++]。 for (。 i = m。 ) [k++] = [i++]。 for (。 j = n。 ) [k++] = [j++]。 for(i = b, k = 1。 i = n。 ) [i++] = [k++]。 隨機數(shù) ? 隨機函數(shù) rand() ? include ? RAND_MAX在 ，不大于雙字節(jié)整數(shù)的最大值 32767 ? 產(chǎn)生 [0,RAND_MAX] 之間的隨機數(shù) ? magic = rand()。 ? 產(chǎn)生 [0,b1] 之間的隨機數(shù) ? magic = rand()%b。 ? 產(chǎn)生 [a,a+b1] 之間的隨機數(shù) ? magic = rand()%b + a。 隨機數(shù) ? 隨機函數(shù) srand ? 為函數(shù) rand()設置隨機數(shù)種子來實現(xiàn)對函數(shù) rand所產(chǎn)生的偽隨機數(shù)的 “隨機化” ? 通過鍵入隨機數(shù)種子，產(chǎn)生 [0,100]之間的隨機數(shù) scanf(%u, amp。seed)。 srand(seed)。 magic = rand() % 100 + 1。 ? 使用計算機讀取其時鐘值并把該值自動設置為隨機數(shù)種子，產(chǎn)生 [0,100]之間的隨機數(shù) ? 函數(shù) time()返回以秒計算的當前時間值，該值被轉換為無符號整數(shù)并用作隨機數(shù)發(fā)生器的種子 include srand((unsigned)time(NULL))。 magic = rand() % 100 + 1。 計算代碼段運行時間示例 include clock_t CLK_1, CLK_2。 //typedef long clock_t。 CLK_1 = clock()。 … // 此處為需要測試運行時間的代碼段 CLK_2 = clock()。 printf(duration_time: %d, CLK_2 – CLK_1)。 include time_t start_time, end_time。 start_time =time(0)。 … // 此處為需要測試運行時間的代碼段 end_time = time(0)。 printf(duration_time: %lf, difftime(end_time,start_time))。
研究報告相關推薦
鄂ICP備17016276號-1