數(shù)據(jù)結(jié)構(gòu)上機(jī)基本習(xí)題

《數(shù)據(jù)結(jié)構(gòu)上機(jī)基本習(xí)題》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)上機(jī)基本習(xí)題（44頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、單 元 實(shí) 驗(yàn) 二 排 序 算 法 排序的分類內(nèi) 部 排 序 外 部 排 序 插 入 排 序 （ 直 插 排 序 、 二 分 插 入 排 序 、 希 爾 排 序 ） 交 換 排 序 （ 冒 泡 排 序 、 快 速 排 序 ） 選 擇 排 序 （ 簡 單 選 擇 排 序 、 樹 型 排 序 、 堆 排 序 ） 歸 并 排 序 （ 二 路 歸 并 排 序 、 多 路 歸 并 排 序 ） 分 配 排 序 （ 多 關(guān) 鍵 字 排 序 、 基 數(shù) 排 序 ） 多 路 平 衡 歸 并 排 序 置 換 選 擇 排 序 最 佳 歸 并 樹排 序 直接插入排序n 直 接 插 入 排 序 (Straight In

2、sertion Sorting)的 基 本 思想 是 ： n個 待 排 序 的 元 素 由 一 個 有 序 表 和 一 個 無 序 表 組 成 ，開 始 時 有 序 表 中 只 包 含 一 個 元 素 。 排 序 過 程 中 ， 每 次 從無 序 表 中 取 出 第 一 個 元 素 ， 將 其 插 入 到 有 序 表 中 的 適 當(dāng)位 置 ， 使 有 序 表 的 長 度 不 斷 加 長 ， 完 成 排 序 過 程 。有 序 序 列 R1.i-1 Ri 無 序 序 列 Ri.n有 序 序 列 R1.i 無 序 序 列 Ri+1.n 冒泡排序n 冒 泡 排 序 (Bubble Sorting)的

3、基 本 思 想 是 ： 將 相 鄰 位 置的 關(guān) 鍵 字 進(jìn) 行 比 較 ， 若 為 逆 序 則 交 換 之 。無 序 序 列 R1.n-i+1 有 序 序 列 Rn-i+2.nn-i+1無 序 序 列 R1.n-i 有 序 序 列 Rn-i+1.n比 較 相 鄰 記 錄 ， 將 關(guān) 鍵 字 最 大 的 記錄 交 換 到 n-i+1 的 位 置 上 第 i 趟 起 泡 排 序 若 在 一 趟 排 序 過 程 中 沒 有 進(jìn) 行 過 交 換 記 錄 的 操 作 ， 則整 個 排 序 過 程 終 止 。 簡單選擇排序n 簡 單 選 擇 排 序 的 基 本 思 想 是 ： 第 一 趟 在 n個 記

4、錄 中 選 取 最小 記 錄 作 為 有 序 序 列 的 第 一 個 記 錄 ， 第 二 趟 在 n-1個 記 錄中 選 取 最 小 記 錄 作 為 有 序 序 列 的 第 二 個 記 錄 ， 第 i趟 在 n-i+1個 記 錄 中 選 取 最 小 的 記 錄 作 為 有 序 序 列 多 中 的 第 i個記 錄 。有 序 序 列 R1.i-1 無 序 序 列 Ri.n 第 i 趟簡 單 選 擇 排 序 從 中 選 出 關(guān) 鍵 字 最 小 的 記 錄有 序 序 列 R1.i 無 序 序 列 Ri+1.n 基 本 要 求1 用 隨 機(jī) 函 數(shù) 產(chǎn) 生 1000個 （ 或 更 多 ） 整 數(shù) （ 或

5、 浮 點(diǎn) 數(shù) ） ， 保存 在 文 件 （ intfile.dat / realfile.dat） 中 ， 然 后 將 文 件 中 的 所有 整 數(shù) （ 或 浮 點(diǎn) 數(shù) ） 讀 入 一 個 數(shù) 組 A。 （ 1） 用 冒 泡 法 對 數(shù) 組 A排 序 ； （ 2） 用 簡 單 選 擇 排 序 方 法 對 數(shù) 組 A排 序 ； （ 3） 用 直 接 插 入 排 序 法 對 數(shù) 組 A排 序 ； 將 上 述 排 序 算 法 分 別 用 函 數(shù) 實(shí) 現(xiàn) ， 輸 出 每 種 排 序 過 程 中 元 素的 比 較 次 數(shù) 、 交 換 （ 或 移 動 ） 次 數(shù) ， 以 及 排 序 過 程 所 消 耗 的

6、時 間 （ 以 s或 ms為 單 位 ） ； 基 本 要 求 2 將 問 題 1中 所 有 1000個 （ 或 更 多 ） 整 數(shù) 讀 入 數(shù) 組 A， 用 快 速排 序 算 法 對 數(shù) 組 A中 的 元 素 排 序 ， 輸 出 排 序 結(jié) 果 、 排 序 過 程中 元 素 的 比 較 和 交 換 （ 移 動 ） 次 數(shù) 、 排 序 算 法 消 耗 的 時 間 ;3. 利 用 上 面 實(shí) 現(xiàn) 的 任 意 一 種 排 序 算 法 ， 對 實(shí) 驗(yàn) 題 目 一 所 產(chǎn) 生 的學(xué) 生 信 息 文 件 studinfo.dat， 讀 取 其 中 的 所 有 學(xué) 生 信 息 ： （ 1） 按 學(xué) 號 排

7、序 輸 出 學(xué) 生 信 息 ； （ 2） 按 姓 名 排 序 輸 出 學(xué) 生 信 息 ； （ 3） 按 三 門 課 程 的 平 均 分 從 高 到 低 排 序 輸 出 學(xué) 生 信 息 （ 除了 學(xué) 生 基 本 信 息 外 ， 還 要 輸 出 每 個 學(xué) 生 的 平 均 成 績 ） ， 最 后再 加 一 行 輸 出 信 息 ： 每 門 課 程 的 平 均 成 績 。 快速排序n 快 速 排 序 (Quick Sorting)是 迄 今 為 止 所 有 內(nèi) 排 序 算 法 中速 度 最 快 的 一 種 。 其 基 本 思 想 是 ： 取 待 排 序 序 列 中 的 某個 元 素 作 為 基 準(zhǔn) （

8、 也 成 為 樞 軸 元 素 ， 一 般 取 第 一 個 元素 ） ， 通 過 一 趟 排 序 ， 將 待 排 序 列 劃 分 為 左 右 兩 個 子 序列 ， 左 子 序 列 元 素 的 關(guān) 鍵 字 均 小 于 或 等 于 基 準(zhǔn) 元 素 的 關(guān)鍵 字 ， 右 子 序 列 的 關(guān) 鍵 字 則 大 于 或 等 于 基 準(zhǔn) 元 素 的 關(guān) 鍵字 ， 然 后 分 別 對 兩 個 子 序 列 繼 續(xù) 進(jìn) 行 排 序 ， 直 至 整 個 序列 有 序 。 無 序 的 記 錄 序 列無 序 的 左 子 序 列 無 序 的 右 子 序 列樞 軸一次劃分分別進(jìn)行快速排序 38 65 97 13 27 49

9、551 2 3 4 5 6 7 849 049pivot i j快速排序中的一趟劃分38 65 97 13 27 49 551 2 3 4 5 6 7 8 04949pivot i jaj與 pivot比 較 ， aj小 則 ajai 38 65 97 13 27 49 551 2 3 4 5 6 7 804 949pivot i j快速排序中的一趟劃分i38 65 97 13 27 49 551 2 3 4 5 6 7 804 949pivot jai與 pivot比 較 ，ai大 則 ai aj； 否 則 i增 1 38 65 97 13 27 49 551 2 3 4 5 6 7 804

10、 949pivot i j快速排序中的一趟劃分i38 6597 13 27 49 551 2 3 4 5 6 7 804 949pivot jai與 pivot比 較 ，ai大 則 ai aj； 否 則 i增 1 快速排序中的一趟劃分i38 6597 13 27 49 551 2 3 4 5 6 7 804 949pivot jaj與 pivot比 較 ，aj小 則 aj ai； 否 則 j減 11 2 3 4 5 6 7 8 9 i38 6597 13 27 49 550449pivot j 快速排序中的一趟劃分i38 6597 1327 49 551 2 3 4 5 6 7 804 949

11、pivot j ai與 pivot比 較 ，ai大 則 ai aj； 否 則 i加 11 2 3 4 5 6 7 8 9i38 6597 13 49 550449pivot j27 快速排序中的一趟劃分i38 65971327 49 551 2 3 4 5 6 7 804 949pivot j aj與 pivot比 較 ，aj小 則 ai aj； 否 則 j減 1i38 65971327 49 551 2 3 4 5 6 7 804 949pivot j 快速排序中的一趟劃分i38 65971327 49 551 2 3 4 5 6 7 804 949pivot j i與 j相 等 時 ， 完

12、 成 一 次 劃 分 ，樞 軸 元 素 歸 位 i38 65971327 49 551 2 3 4 5 6 7 804 49 9j 快 速 排 序 中 的 一 趟 劃 分 38 27 13 49 97 49 551 2 3 4 5 6 7 804 659int Partition(SqList pivotkey = L.r0.key; /元 素 移 動 i = low; j = high; while (ij) while (i= pivotkey) j-; L.ri = L.rj; / 元 素 移 動 while (ij L.rj = L.ri; / 元 素 移 動 L.ri = L.r0;

13、 / 元 素 移 動 return i; / 返 回 樞 軸 元 素 最 后 確 定 的 位 置 /Partition 38 65 97 13 27 49 5549 04 8 40 30 20 15 9 251 2 3 4 5 6 7 810 59pivot i j快速排序中的一趟劃分 8 40 30 20 15 9 25 55 i j10 8 40 30 20 15 9 25i j5 408 30 20 15 9 25 40i j5 98 9 30 20 15 25 40 i j5 308 9 30 20 15 30 25 40i j51 2 3 4 5 6 7 8 91 快 速 排 序in

14、t Partition(SqList /返 回 樞 軸 元 素 的 位 置/Partitionvoid QSort(SqList -i) / 把 H 建 成 大 頂 堆 H eapAdjust ( H , i, H . length); for ( i = H . length; i 1; -i) H .r1 H .ri; /堆 頂 記 錄 和 當(dāng) 前 未 排 子 序 列 中 最 后 一 個 記 錄 相 交 換 H eapAdjust (H , 1, i - 1); /將 H . rl . i - 1 重 新 調(diào) 整 為 大 頂 堆 / H eapSort for ( i = H . leng

15、th; i 1; -i) H .r1H .ri; /堆 頂 記 錄 和 當(dāng) 前 未 排 子 序 列 中 最 后 一 個 記 錄 相 交 換 / 三 次 移 動 元 素 H eapAdjust (H , 1, i - 1); /將 H . rl . i - 1 重 新 調(diào) 整 為 大 /小 頂 堆 示 例 將 H 建 成 大 /小 頂 堆 for ( i = H . length/2; i 0; -i) / 把 H 建 成 大 /小 頂 堆 H eapAdjust ( H , i, H . length); 123685 47 2430 5391 93685 47 30 5312 473691

16、12 5330 2485 堆排序算法(篩選算法)v typedef SqList HeapType; /堆 采 用 順 序 存 儲 結(jié) 構(gòu)void H eapAdjust (H eapType /元 素 移 動 for ( j=2*s; j=m; j*=2) /沿 key較 小 的 孩 子 結(jié) 點(diǎn) 向 下 篩 選 if ( j H .rj+l.key) + j; /j為 key較 小 的 記 錄 的 下 標(biāo) if (rc. Key 1) MergeSort(待 排 序 列 的 前 半 區(qū) 間 )； MergeSort(待 排 序 列 的 后 半 區(qū) 間 )； 已 排 好 序 的 前 半 區(qū) 間

17、 、 后 半 區(qū) 間 合 并 成 一 個 有 序 序 列 ； /if / MergeSort v 采 用 順 序 存 儲 結(jié) 構(gòu) ， 對 于 由 下 標(biāo) st界 定 的 一 個 序 列 ， 前半 區(qū) 間 為 s (s+t)/2， 后 半 區(qū) 間 為 (s+t)/2+1 tvoid MergeSort(SqList MergeSort(L, s, m)； MergeSort(L, m+1, t)； Merge(L, s, m, t);/合 并 L.rsL.rm與 L.rm+1L.rt /if / MergeSort 兩路歸并算法v 以 順 序 表 作 為 存 儲 結(jié) 構(gòu)void Merge(Sq

18、List for(j = m+1,k =1; i =m +k) /for/ifi if (L.ri.key L.rj.key) temp.rk = L.ri+; else temp.rk = L.rj+; for (; i = m; ) temp.rk+ = L.ri+; for (; j = n; ) temp.rk+ = L.rj+; for(i = b, k = 1; i = n; ) L.ri+ = temp.rk+; 隨 機(jī) 數(shù)n 隨 機(jī) 函 數(shù) rand()n #include RAND_MAX在 stdlib.h中 定 義 ， 不 大 于 雙 字 節(jié) 整 數(shù) 的 最大 值 327

19、67n 產(chǎn) 生 0,RAND_MAX 之 間 的 隨 機(jī) 數(shù)magic = rand(); n 產(chǎn) 生0,b-1 之 間 的 隨 機(jī) 數(shù)magic = rand()%b;n 產(chǎn) 生a,a+b-1 之 間 的 隨 機(jī) 數(shù)magic = rand()%b + a; 隨 機(jī) 數(shù)n 隨 機(jī) 函 數(shù)srand 為 函 數(shù) rand()設(shè) 置 隨 機(jī) 數(shù) 種 子 來 實(shí) 現(xiàn) 對 函 數(shù) rand所 產(chǎn) 生的 偽 隨 機(jī) 數(shù) 的 “ 隨 機(jī) 化 ”n 通 過 鍵 入 隨 機(jī) 數(shù) 種 子 ， 產(chǎn) 生 0,100之 間 的 隨 機(jī) 數(shù)scanf(%u, srand(seed); magic = rand() %

20、 100 + 1; n 使 用 計(jì) 算 機(jī) 讀 取 其 時 鐘 值 并 把 該 值 自 動 設(shè) 置 為 隨 機(jī) 數(shù) 種 子 ，產(chǎn) 生 0,100之 間 的 隨 機(jī) 數(shù)n 函 數(shù) time()返 回 以 秒 計(jì) 算 的 當(dāng) 前 時 間 值 ， 該 值 被 轉(zhuǎn) 換 為 無符 號 整 數(shù) 并 用 作 隨 機(jī) 數(shù) 發(fā) 生 器 的 種 子 #include srand(unsigned)time(NULL); magic = rand() % 100 + 1; 計(jì) 算 代 碼 段 運(yùn) 行 時 間 示 例#include clock_t CLK_1, CLK_2;/typedef long clock_t;CLK_1 = clock(); /此 處 為 需 要 測 試 運(yùn) 行 時 間 的 代 碼 段CLK_2 = clock(); printf(duration_time: %d, CLK_2 CLK_1);#include time_t start_time, end_time;start_time =time(0); /此 處 為 需 要 測 試 運(yùn) 行 時 間 的 代 碼 段end_time = time(0);printf(duration_time: %lf, difftime(end_time,start_time);