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