《算法與數據結構(實踐)》

遼寧省高等教育 實踐考試 軟件技術 應用本科 專業(yè) 實 驗 報 告 書 課程名稱 助學單位 姓 名 準考證號 成 績 二 一一 年 四 月 1 實驗一 順序表的應用 一 實驗目的一 實驗目的 1 會定義線性表的順序存儲類型 2 熟悉 C 程序的基本結構 掌握程序中的用戶頭文件 實現文件和主文件之間的相互關 系及各自作用 3 熟悉對線性表的一些基本操作和具體的函數定義 4 熟悉 C 操作環(huán)境的使用以及多文件的輸入 編輯 調試和運行的全過程 二 實驗內容二 實驗內容 該程序的功能是對元素類型為整型的順序存儲的線性表進行一些操作 該程序包含三 個文件 一個為頭文件 用來存儲定義的線性表結構類型以及對線性表進行的各種操作的 函數聲明 第二個為線性表操作的實現文件 用來存儲每一種線性表操作的具體函數定義 第三種為主文件 用來定義線性表和調用線性表的一些操作 實現對給定線性表的具體運 算 整個程序如下 頭文件頭文件 linearlist1 hlinearlist1 h typedef int ElemType struct LinearList ElemType list 存線性表元素 int size 存線性表長度 int MaxSize 存 list 數組長度 void InitList LinearList void ClearList LinearList int ListSize LinearList bool ListEmpty LinearList bool ListFull LinearList void TraverList LinearList bool FindList LinearList bool UpdateList LinearList bool InsertList LinearList bool DeleteList LinearList void OrderOutputList LinearList 實現文件實現文件 linearlist1 cpplinearlist1 cpp include include include linearlist1 h void InitList LinearList if L list cerr Memory allocation failure ENDL exit 1 L size 0 L MaxSize ms 2 void ClearList LinearList int ListSize LinearList bool ListEmpty LinearList bool ListFull LinearList void TraverList LinearList i cout L list i cout ENDL bool FindList LinearList i if L list i item item L list i return true return false bool UpdateList LinearList i if L list i item L list i item return true return false bool InsertList LinearList if mark 0 for int i L size 1 i 0 i L list i 1 L list i L list 0 item else if mark 0 L list L size item 3 else for int i 0 i if item for int j L size 1 j i j L list j 1 L list j L list i item L size return true bool DeleteList LinearList if mark 0 item L list 0 for int i 1 i L list i 1 L list i else if mark 0 item L list L size 1 else for int i 0 i if L list i item break if i L size return false else item L list i for int j i 1 j L list j 1 L list j L size return true void OrderOutputList LinearList int i k for i 0 i b i i for i 1 i k i 1 for int j i j if mark 1 b i 1 b k b k x for i 0 i cout L LIST B I SPAN cout ENDL 主文件主文件 listmain1 cpplistmain1 cpp include 4 const int ML 10 include linearlist1 h void main LinearList a InitList a ML int i ElemType x cout 從鍵盤輸入 5 個整數 for i 0 i x InsertList a x 1 cout x InsertList a x 1 cin x InsertList a x 1 TraverList a OrderOutputList a 1 OrderOutputList a 0 LinearList b InitList b ML for i 0 i InsertList b a list i 0 TraverList b if DeleteList a x 1 cout Delete success ENDL else cout Delete fail ENDL if DeleteList a x 1 cout Delete success ENDL else cout Delete fail ENDL cout x if DeleteList a x 0 cout Delete success ENDL else cout Delete fail ENDL TraverList a 三 實驗步驟三 實驗步驟 1 進入 MICROSOFT VISUAL C 6 0 2 在主菜單上選擇 文件 新建 3 出現 新建 對話框 選擇 工程 頁面框 并選中 Win32 Console Application 類型 為該類工程取一名字 TEST1 依次按 確定 完成 按鈕 4 再次進入 新建 對話框 選擇 文件 頁面框 并選中 C C Header File 類型 為該類文件取一名字 linearlist1linearlist1 按 確定 5 出現該程序的輸入窗口 輸入 linearlist1 hlinearlist1 h 文件內容 并保存 6 再次進入 新建 對話框 選擇 文件 頁面框 并選中 C Source File 類型 為該類文件取一名字 linearlist1linearlist1 按 確定 7 出現該程序的輸入窗口 輸入 linearlist1 cpplinearlist1 cpp 文件內容 并保存 8 再次進入 新建 對話框 選擇 文件 頁面框 并選中 C Source File 類型 為該類文件取一名字 listmain1listmain1 按 確定 5 9 出現該程序的輸入窗口 輸入 listmain1 cpplistmain1 cpp 文件內容 并保存 10 在主菜單上選擇 編譯 編譯 listmain1 cpplistmain1 cpp 然后對出現的各種錯誤進行改正 直到編譯成功 即出現 0 errors 11 在主菜單上選擇 編譯 構件 test exe 然后對出現的各種錯誤進行改正 直 到鏈接成功 12 在主菜單上選擇 編譯 執(zhí)行 test exe 13 出現運行窗口 提示 從鍵盤輸入 5 個整數 輸入 5 10 2 8 20 14 提示 從鍵盤輸入 2 個整數 輸入 3 15 15 顯示出下列幾行結果 15 3 5 10 2 8 20 2 3 5 8 10 15 20 20 15 10 8 5 3 2 2 3 5 8 10 15 20 Delete success Delete success 分析 第 1 行是線性表 a 中元素原來的序列 第 2 行是 a 中的升序序列 第 3 行 是 a 中的降序序列 第 4 行是線性表 b 中元素的序列 第 5 行是在 a 中成功刪除 表頭的提示 第 6 行是在 a 中成功刪除表尾的提示 16 提示 從鍵盤上輸入一個待刪除的整數 輸入 8 17 顯示出下列 2 行結果 Delete success 3 5 10 2 分析 第 1 行是成功刪除 8 后的提示 第 2 行是表 a 中的當前元素 總結 程序執(zhí)行結果構符合主文件的設計和語句 6 實驗二 鏈表的應用 一 一 實驗目的實驗目的 1 熟悉 C 語言的上機環(huán)境 掌握 C 語言的基本結構 2 會定義線性表的鏈式存儲結構 3 熟悉對鏈表的一些基本操作和具體的函數定義 4 本章的主要任務是使用有關單鏈表的操作來實現通訊錄信息系統(tǒng)的管理 二 實驗內容實驗內容 1 創(chuàng)建和銷毀鏈表存儲結構 要求達到 熟練掌握 層次 2 實現鏈表的基本操作 要求達到 熟練掌握 層次 3 鏈表的簡單應用 要求達到 基本掌握 層次 現假設鏈表結點僅含一個數據域和一個指針域 數據域是為了描述通訊者的 相關信息 定義通訊者的結點類型 typedef struct char num 5 編號 char name 9 姓名 char sex 3 性別 char phone 13 電話 char addr 31 地址 DataType 因此 線性表的鏈式存儲結構定義如下 typedef struct node 結點類型定義 DataType data 結點數據域 struct node next 結點指針域 ListNode typedef ListNode LinkList ListNode p 定義一個指向結點的指針變量 LinkList head 定義指向單鏈表的頭指針 這里的 LinkList 和 ListNode 是不同名字的同一指針類型 取不同的名是為了在概念 上更明確 特別值得注意的是指針變量和指針指向的變量 結點變量 這兩個概念 指針 變量要么為空 Null 不指向任何結點 要么其值為非空 即它的值是一個結點的存儲地 址 指針變量所指向的結點并沒有具體說明 而是在程序執(zhí)行過程中 需要存儲結點時才 產生 它是通過 C 語言的標準函數 malloc 實現的 例如 給指針變量 p 分配一個結點的地 址 p ListNode malloc sizeof ListNode 該語句的功能是申請分配一個類型為 ListNode 的結點的地址空間 并將其首地址存入指針變量 p 中 當結點不需要時可以用標 準函數 free p 釋放結點的存儲空間 這時 p 為空值 Null 為了驗證算法 本章的設計分為兩個實驗 其一是通訊錄的管理 包括單通訊錄鏈表 的建立 通訊者的插入 通訊者的刪除 通訊者的查詢以及通訊錄表的輸出等 其二是利 用單循環(huán)鏈表解決約瑟夫游戲生者與死者的選擇問題 通訊錄管理 為了實現通訊錄管理的幾種操作功能 首先設計一個含有多個菜單的主控菜 單程序 然后再為這些菜單配上相應功能 三 三 實驗步驟實驗步驟 1 主控菜單設計要求 1 菜單內容 程序運行后 給出 6 個菜單項的內容和輸入提示 1 通訊錄鏈表的建立 7 2 通訊者結點的插入 3 通訊者結點的查詢 4 通訊者結點的刪除 5 通訊錄鏈表的輸出 6 退出管理系統(tǒng) 2 設計要求 使用數字 0 5 來選擇菜單項 其它輸入不起作用 完整程序清單 主控菜單處理測試程序 main2 c include stdio h include string h include stdlib h typedef struct 通訊錄結點類型 char num 5 編號 char name 9 姓名 char sex 3 性別 char phone 13 電話 char addr 31 地址 DataType typedef struct node 結點類型定義 DataType data 結點數據域 struct node next 結點指針域 ListNode typedef ListNode LinkList LinkList head ListNode p 函數說明 int menu select LinkList CreateList void Void InsertNode LinkList head ListNode p ListNode ListFind LinkList head Void DelNode LinkList head Void PrintList LinkList head 主函數 void main for switch menu select case 1 printf n printf 通 訊 錄 鏈 表 的 建 立 n printf n head CreateList break case 2 printf n printf 通 訊 者 信 息 的 添 加 n printf n printf 編號 4 姓名 8 性別 3 電話 11 地址 31 n 8 printf n p ListNode malloc sizeof ListNode 申請新結點 scanf s s s s s p data num p data name p data sex p data phone p data addr InsertNode head p break case 3 printf n printf 通 訊 錄 信 息 的 查 詢 n printf n p ListFind head if p NULL printf 編號 姓 名 性別 聯系電話 地址 n printf n printf s s s s s n p data num p data name p data sex p data phone p data addr printf n else printf 沒有查到要查詢的通訊者 n break case 4 printf n printf 通 訊 錄 信 息 的 刪 除 n printf n DelNode head 刪除結點 break case 5 printf n printf 通 訊 錄 鏈 表 的 輸 出 n printf n printList head break case 0 printf t 再 見 n return 菜單選擇函數程序 int menu select int sn printf 通訊錄管理系統(tǒng) n printf n printf 1 通訊鏈表的建立 n printf 2 通訊者結點的插入 n printf 3 通訊者結點的查詢 n printf 4 通訊者結點的刪除 n 9 printf 5 通訊錄鏈表的輸出 n printf 0 退出管理系統(tǒng) n printf n printf 請 選 擇 0 5 for scanf d if sn5 printf n t 輸入錯誤 重選 0 5 else break return sn LinkList CreateList void 尾插法建立帶頭結點的通訊錄鏈表算法 LinkList head ListNode malloc sizeof ListNode 申請頭結點 ListNode p rear int flag 0 結束標志置 0 rear head 尾指針初始指向頭結點 while flag 0 p ListNode malloc sizeof ListNode 申新結點 printf 編號 4 姓名 8 性別 電話 11 地址 31 n printf n scanf s s s s s p data num p data name p data sex p data phone p data addr rear next p 新結點連接到尾結點之后 rear p 尾指針指向新結點 printf 結束建表嗎 1 0 scanf d rear next NULL 終端結點指針置空 return head 返回鏈表頭指針 void InsertNode LinkList head ListNode p ListNode p1 p2 p1 head p2 p1 next while p2 NULL p2 指向表的下一個結點 p1 next p 插入 p 所指向的結點 p next p2 連接表中剩余的結點 有序通訊錄鏈表的查找 10 ListNode ListFind LinkList head 有序通訊錄鏈表上的查找 ListNode p char num 5 char name 9 int xz printf n printf 1 按編號查詢 n printf 2 按姓名查詢 n printf n printf 請 選 擇 p head next 假定通訊 錄表帶頭結點 scanf d if xz 1 printf 請輸入要查找者的編號 scanf s num while p if p NULL strcmp p data num num 0 p NULL 沒有查到要查找的通訊者 else if xz 2 printf 請輸入要查找者的姓名 scanf s name while p return p void DelNode LinkList head char jx ListNode p q P ListFind head 調用查找函數 if p NULL printf 沒有查到要刪除的通訊者 n return printf 真的要刪除該結點嗎 y n scanf c if jx y jx Y q head while q NULL q next p next 刪除結點 free p 釋放被刪結點空間 printf 通訊者已被刪除 n 11 void printList LinkList head ListNode p p head next printf 編號 姓 名 性別 聯系電話 地址 n printf n while p NULL printf s s s s s n p data num p data name p data sex p data phone p data addr printf n p p next 后移一個結點 12 實驗 3 棧和隊列的應用 一 實驗目的一 實驗目的 1 熟練掌握棧和隊列的結構 以及這兩種數據結構的特點 2 能夠在兩種存儲結構上實現棧的基本運算 特別注意棧滿和?？盏呐袛鄺l件及描 述方法 3 熟練掌握鏈隊列和循環(huán)隊列的基本運算 并特別注意隊列滿和隊列空的判斷條件 和描述方法 二 實驗內容二 實驗內容 計算表達式的值 以字符序列的形式從終端輸入語法正確的 不含變量的整數表達式 利用課堂講授時給出的算符優(yōu)先關系 實現對算術四則混合運算表達式的求值 只考慮運 算數為一位整數 0 9 的情況 三 三 實驗步驟實驗步驟 1 1 理解棧的基本工作原理 2 仔細分析實驗內容 給出其算法和流程圖 3 用 C 語言實現該算法 4 給出測試數據 并分析其結果 5 在實驗報告冊上寫出實驗過程 2 1 設置運算符棧和運算數棧輔助分析算符優(yōu)先關系 2 在讀入表達式的字符序列的同時 完成運算符和運算數的識別處理 以及相應的 運算 3 在識別出運算數的同時 要將其字符序列形式轉換成整數形式 4 在程序的適當位置輸出運算符棧 運算數棧 輸入字符和主要操作的內容 以幫 助你分析程序 3 測試數據 8 1 2 3 4 88 1 3 1024 8 16 1024 8 16 22 3 8 2 3 3 3 8 9 9 2 5 3 2 4 3 6 4 選做題 1 假設一個算術表達式中包含零對到多對圓括弧 括弧對之間允許嵌套但不允許交 叉 編寫一個算法并上機實現 判斷輸入的表達式是否正確配對 2 用棧實現一般表達式 即中綴表達式 到后綴表達式的轉換 3 某銀行有一個客戶辦理業(yè)務站 在單位時間內隨機地有客戶到達 設每位客戶的 業(yè)務辦理時間是某個范圍內的隨機值 設只有一個窗口 一位業(yè)務人員 要求程序模擬統(tǒng) 計在設定時間內 業(yè)務人員的總空閑時間和客戶的平均等待時間 假定模擬數據已按客戶 到達的先后順序依次存于某個正文數據文件中 對應每位客戶有兩個數據 到達時間和需 要辦理業(yè)務的時間 13 實驗 4 樹和二叉樹的應用 一 實驗目的一 實驗目的 1 熟練掌握樹的基本概念 二叉樹的基本操作及在鏈式存儲結構上的實現 2 重點掌握二叉樹的生成 遍歷及求深度等算法 3 掌握二叉樹的線索化及線索二叉樹的遍歷算法 掌握赫夫曼樹的含義及其應用 4 掌握運用遞歸方式描述算法及編寫遞歸 C 程序的方法 提高算法分析和程序設計 能力 二 實驗內容二 實驗內容 Huffman 編 譯碼器 利用 Huffman 編碼進行通信可以大大提高信道利用率 縮短信 息傳輸時間 降低傳輸成本 但是 這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數據預先編 碼 在接受端將傳來的數據編碼進行譯碼 復原 對于有些信道 每端都需要一個完整 的編 譯碼系統(tǒng) 試為這樣的信息收發(fā)站編寫一個 Huffman 的編 譯碼系統(tǒng) 三 三 實驗步驟實驗步驟 1 1 理解 Huffman 樹的基本工作原理 2 仔細分析實驗內容 給出其算法和流程圖 3 用 C 語言實現該算法 4 給出測試數據 并分析其結果 5 在實驗報告冊上寫出實驗過程 2 實驗幫助 一個完整的系統(tǒng)應具有以下功能 1 初始化 從鍵盤讀入 n 個字符 以及它們的權值 建立 Huffman 樹 具體算法 可參見教材算法 2 編碼 根據建立的 Huffman 樹 求每個字符的 Huffman 編碼 對給定的待編碼字 符序列進行編碼 3 譯碼 利用已經建立好的 Huffman 樹 對上面的編碼結果譯碼 譯碼的過程是分 解電文中的字符串 從根結點出發(fā) 按字符 0 和 1 確定找左孩子或右孩子 直至葉結點 便求得該子串相應的字符 4 打印 Huffman 樹 3 測試數據 1 根據運行提示 依次輸入待編碼的字符個數和這些字符 以及每個字符的權值 輸入 4 個字符 a b c 和 d 及 4 個對應的權值 7 5 2 和 4 輸出 a 0 b 10 c 110 d 111 3 讀者可根據運行提示 自行指定數據 觀察程序的運行結果 14 實驗 5 圖的應用 一 實驗目的一 實驗目的 1 掌握圖的鄰接矩陣和鄰接表兩種存儲方法 2 掌握有關圖的操作算法并用高級語言實現 3 熟悉圖的構造算法 了解實際問題的求解效率與采用何種存儲結構與算法有著密切 聯系 4 掌握圖的兩種搜索路徑的遍歷算法 5 掌握求圖的最小生成樹的普里姆算法和克魯斯卡爾算法 二 實驗內容二 實驗內容 1 創(chuàng)建給定圖的存儲結構 從鄰接表和鄰接矩陣兩種存儲方式中選擇一種 2 對所創(chuàng)建的圖進行深度和廣度優(yōu)先搜索遍歷 給出遍歷過程中的頂點序列 3 求圖的最小生成樹 按構造順序輸出邊的序列 兩種方法都要求 3 編寫一個主函數 將上面函數連在一起 構成一個完整程序 4 將實驗源程序調試并運行 三 實驗步驟三 實驗步驟 所建立的圖為 1 4 3 2 5 6 7 10 25 15 30 20 50 45 35 用鄰接表存儲結構時 所創(chuàng)建的單鏈表以結點的從小到大排列 注意標志數組 visited n 1 的定義和賦值 將頂點 1 作為起點 實驗結果 輸入輸出結果截圖 15 圖 圖的操作 實驗總結 通過本次實驗 我更好地掌握了圖的相關操作 能夠熟練地進行圖的建立 遍歷 在編寫程序時 遇到很多不大明白的地方 在得到同學們的鼎力相助后 基本解 決了這些問題 16 實驗六 散列表的應用 一 實驗目的一 實驗目的 1 復習 C 中的全局變量的概念 2 學習圖的鄰接矩陣和鄰接表兩種存儲方式 3 學習圖的兩種遍歷方法和求圖的最小生成樹的方法 二 實驗內容實驗內容 1 散列表存儲結構的創(chuàng)建和銷毀 2 實現散列表的基本操作 如插入 刪除和查找等 3 解決散列沖突方法的應用 如開放地址法和鏈地址法等 三 實驗步驟實驗步驟 1 散列表存儲結構的創(chuàng)建和銷毀 要求達到 熟練掌握 層次 2 實現散列表的基本操作 要求達到 熟練掌握 層次 3 解決散列沖突方法的應用 要求達到 基本掌握 層次 散列表的沖突現象 1 沖突 兩個不同的關鍵字 由于散列函數值相同 因而被映射到同一表位置上 該現象稱為 沖突 Collision 或碰撞 發(fā)生沖突的兩個關鍵字稱為該散列函數的同義詞 Synonym 2 安全避免沖突的條件 最理想的解決沖突的方法是安全避免沖突 要做到這一點必須滿足兩個條件 其一是 U m 其二是選擇合適的散列函數 這只適用于 U 較小 且關鍵字均事先已知的情況 此時 經過精心設計散列函數 h 有可能完全避免沖突 3 沖突不可能完全避免 通常情況下 h 是一個壓縮映像 雖然 K m 但 U m 故無論怎樣設計 h 也不可能 完全避免沖突 因此 只能在設計 h 時盡可能使沖突最少 同時還需要確定解決沖突的方 法 使發(fā)生沖突的同義詞能夠存儲到表中 4 影響沖突的因素 沖突的頻繁程度除了與 h 相關外 還與表的填滿程度相關 設 m 和 n 分別表示表長和 表中填人的結點數 則將 n m 定義為散列表的裝填因子 Load Factor 越大 表越滿 沖突的機會也越大 通常取 1 處理沖突的方法 通常有兩類方法處理沖突 開放定址 Open Addressing 法和拉鏈 Chaining 法 前者 是將所有結點均存放在散列表 T 0 m 1 中 后者通常是將互為同義詞的結點鏈成一個單鏈 表 而將此鏈表的頭指針放在散列表 T 0 m 1 中 開放定址法 1 開放地址法解決沖突的方法 用開放定址法解決沖突的做法是 當沖突發(fā)生時 使用某種探查 亦稱探測 技術在散列 表中形成一個探查 測 序列 沿此序列逐個單元地查找 直到找到給定的關鍵字 或者碰 到一個開放的地址 即該地址單元為空 為止 若要插入 在探查到開放的地址 則可將待 插入的新結點存人該地址單元 查找時探查到開放的地址則表明表中無待查的關鍵字 即查找失敗 注意 用開放定址法建立散列表時 建表前須將表中所有單元 更嚴格地說 是指單元中存儲的 關鍵字 置空 空單元的表示與具體的應用相關 總之 應該用一個不會出現的關鍵字來表示空單元 2 開放地址法的一般形式 17 開放定址法的一般形式為 h i h key d i m 1 i m 1 其中 h key 為散列函數 d i 為增量序列 m 為表長 h key 是初始的探查位置 后續(xù)的探查位置依次是 h l h 2 h m 1 即 h key h l h 2 h m 1 形成了一個探查序列 若令開放地址一般形式的 i 從 0 開始 并令 d 0 0 則 h 0 h key 則有 h i h key d i m 0 i m 1 探查序列可簡記為 h i 0 i m 1 3 開放地址法堆裝填因子的要求 開放定址法要求散列表的裝填因子 l 實用中取 為 0 5 到 0 9 之間的某個值為宜 4 形成探測序列的方法 按照形成探查序列的方法不同 可將開放定址法區(qū)分為線性探查法 二次探查法 雙重 散列法等 拉鏈法 1 拉鏈法解決沖突的方法 拉鏈法解決沖突的做法是 將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中 若選 定的散列表長度為 m 則可將散列表定義為一個由 m 個頭指針組成的指針數組 T 0 m 1 凡是散列地址為 i 的結點 均插入到以 T i 為頭指針的單鏈表中 T 中各分量的初值均應 為空指針 在拉鏈法中 裝填因子 可以大于 1 但一般均取 1 2 拉鏈法的優(yōu)點 與開放定址法相比 拉鏈法有如下幾個優(yōu)點 1 拉鏈法處理沖突簡單 且無堆積現象 即非同義詞決不會發(fā)生沖突 因此平均查找長度較短 2 由于拉鏈法中各鏈表上的結點空 間是動態(tài)申請的 故它更適合于造表前無法確定表長的情況 3 開放定址法為減少沖突 要求裝填因子 較小 故當結點規(guī)模較大時會浪費很多空間 而拉鏈法中可取 1 且 結點較大時 拉鏈法中增加的指針域可忽略不計 因此節(jié)省空間 4 在用拉鏈法構造的散 列表中 刪除結點的操作易于實現 只要簡單地刪去鏈表上相應的結點即可 而對開放地 址法構造的散列表 刪除結點不能簡單地將被刪結點的空間置為空 否則將截斷在它之后 填人散列表的同義詞結點的查找路徑 這是因為各種開放地址法中 空地址單元 即開放地 址 都是查找失敗的條件 因此在用開放地址法處理沖突的散列表上執(zhí)行刪除操作 只能在 被刪結點上做刪除標記 而不能真正刪除結點 3 拉鏈法的缺點 拉鏈法的缺點是 指針需要額外的空間 故當結點規(guī)模較小時 開放定址法較為節(jié)省空 間 而若將節(jié)省的指針空間用來擴大散列表的規(guī)模 可使裝填因子變小 這又減少了開放 定址法中的沖突 從而提高平均查找速度 散列函數的構造方法 1 散列函數的選擇有兩條標準 簡單和均勻 簡單指散列函數的計算簡單快速 均勻指對于關鍵字集合中的任一關鍵字 散列函數 能以等概率將其映射到表空間的任何一個位置上 也就是說 散列函數能將子集 K 隨機均 勻地分布在表的地址集 0 1 m 1 上 以使沖突最小化 2 常用散列函數 為簡單起見 假定關鍵字是定義在自然數集合上 其它關鍵字可以轉換到自然數集合上 1 平方取中法 具體方法 先通過求關鍵字的平方值擴大相近數的差別 然后根據表長度取中間的幾位 數作為散列函數值 又因為一個乘積的中間幾位數和乘數的每一位都相關 所以由此產生 的散列地址較為均勻 2 除余法 該方法是最為簡單常用的一種方法 它是以表長 m 來除關鍵字 取其余數作為散列地址 即 h key key m 該方法的關鍵是選取 m 選取的 m 應使得散列函數值盡可能與關鍵字 18 的各位相關 m 最好為素數 3 相乘取整法 該方法包括兩個步驟 首先用關鍵字 key 乘上某個常數 A 0 A 1 并抽取出 key A 的 小數部分 然后用 m 乘以該小數后取整 4 隨機數法 選擇一個隨機函數 取關鍵字的隨機函數值為它的散列地址 即 h key random key 其 中 random 為偽隨機函數 但要保證函數值是在 0 到 m 1 之間 5 數字分析法 設有 n 個 d 位數 每一位可能有 r 種不同的符號 這 r 種不同的符號在各位上出現的頻 率不一定相同 可能在某些位上分布均勻些 每種符號出現的幾率均等 在某些位上分布不 均勻 只有某幾種符號經常出現 可根據散列表的大小 選取其中各種符號分布均勻的若 干位作為散列地址 6 基數轉換法 將關鍵碼值看成另一種進制的數再轉換成原來進制的數 然后選其中幾位作為散列地址 7 折疊法 有時關鍵碼所含的位數很多 采用平方取中法計算太復雜 則可將關鍵碼分割成位數相同 的幾部分 最后一部分的位數可以不同 然后取這幾部分的疊加和 舍去進位 作為散 列地址 這方法稱為折疊法 8 ELFhash 字符串散列函數 ELFhash 函數在 UNIX 系統(tǒng) V 版本 4 中的 可執(zhí)行鏈接格式 Executable and Linking Format 即 ELF 中會用到 ELF 文件格式用于存儲可執(zhí)行文件與目標文件 ELFhash 函 數是對字符串的散列 它對于長字符串和短字符串都很有效 字符串中每個字符都有同樣 的作用 它巧妙地對字符的 ASCII 編碼值進行計算 ELFhash 函數對于能夠比較均勻地把 字符串分布在散列表中 五 散列表上的運算 散列表上的運算有查找 插入和刪除 其中主要是查找 這是因為散列表的目的主要 是用于快速查找 且插入和刪除均要用到查找操作 1 散列表類型說明 define NIL 1 空結點標記依賴于關鍵字類型 本節(jié)假定關鍵字均為非負整數 define M 997 表長度依賴于應用 但一般應根據 確定 m 為一素數 typedef struct 散列表結點類型 KeyType key InfoType otherinfo 此類依賴于應用 NodeType typedef NodeType HashTable m 散列表類型 2 基于開放地址法的查找算法 散列表的查找過程和建表過程相似 假設給定的值為 K 根據建表時設定的散列函數 h 計算出散列地址 h K 若表中該地址單元為空 則查找失敗 否則將該地址中的結點與 給定值 K 比較 若相等則查找成功 否則按建表時設定的處理沖突的方法找下一個地址 如此反復下去 直到某個地址單元為空 查找失敗 或者關鍵字比較相等 查找成功 為止 3 基于開放地址法的插入及建表 建表時首先要將表中各結點的關鍵字清空 使其地址為開放的 然后調用插入算法將給 定的關鍵字序列依次插入表中 插入算法首先調用查找算法 若在表中找到待插入的關鍵 字或表已滿 則插入失敗 若在表中找到一個開放地址 則將待插入的結點插入其中 即 插入成功 4 刪除 基于開放定址法的散列表不宜執(zhí)行散列表的刪除操作 若必須在散列表中刪除結點 則 19 不能將被刪結點的關鍵字置為 NIL 而應該將其置為特定的標記 DELETED 因此須對查找操 作做相應的修改 使之探查到此標記時繼續(xù)探查下去 同時也要修改插人操作 使其探查 到 DELETED 標記時 將相應的表單元視為一個空單元 將新結點插入其中 這樣做無疑增 加了時間開銷 并且查找時間不再依賴于裝填因子 因此 當必須對散列表做刪除結點的 操作時 一般是用拉鏈法來解決沖突 5 性能分析 插入和刪除的時間均取決于查找 故下面只分析查找操作的時間性能 雖然散列表在關鍵字和存儲位置之間建立了對應關系 理想情況是無須關鍵字的比較就 可找到待查關鍵字 但是由于沖突的存在 散列表的查找過程仍是一個和關鍵字比較的過 程 不過散列表的平均查找長度比順序查找 二分查找等完全依賴于關鍵字比較的查找要 小得多 1 查找成功的 ASL 散列表上的查找優(yōu)于順序查找和二分查找 2 查找不成功的 ASL 對于不成功的查找 順序查找和二分查找所需進行的關鍵字比較次數僅取決于表長 而 散列查找所需進行的關鍵字比較次數和待查結點有關 因此 在等概率情況下 也可將散 列表在查找不成功時的平均查找長度 定義為查找不成功時對關鍵字需要執(zhí)行的平均比較 次數 注意 由同一個散列函數 不同的解決沖突方法構造的散列表 其平均查找長度是不相同的 散列表的平均查找長度不是結點個數 n 的函數 而是裝填因子 的函數 因此在設 計散列表時可選擇 以控制散列表的平均查找 長度 的取值越小 產生沖突的機會就小 但 過小 空間的浪費就過多 只要 選 擇合適 散列表上的平均查找長度就是一個常數 即散列表上查找的平均時間為 O 1 散列法與其他查找方法的區(qū)別 除散列法外 其他查找方法有共同特征為 均是建立在比較關鍵字的基礎上 其中順序查 找是對無序集合的查找 每次關鍵字的比較結果為 或 兩種可能 其平均時間為 O n 其余的查找均是對有序集合的查找 每次關鍵字的比較有 三種可能 且每次 比較后均能縮小下次的查找范圍 故查找速度更快 其平均時間為 O lgn 而散列法是根 據關鍵字直接求出地址的查找方法 其查找的期望時間為 O 1 20 實驗 7 排序的應用 一 實驗目的一 實驗目的 1 掌握插入排序的應用 學習直接插入排序 有序表排序等 2 掌握交換排序的應用 如冒泡排序 快速排序等 3 學習選擇排序的應用 如直接選擇排序 堆排序等 4 學習歸并排序的應用 如二路歸并排序等 二 實驗要求二 實驗要求 1 熟練掌握插入排序的應用 能進行直接插入排序 有序表排序等 2 對交換排序達到熟練掌握的程度 會進行冒泡排序 快速排序 3 運用選擇排序 進行直接選擇排序 堆排序 4 綜合運用排序方法 能解決基本排序 三 實驗步驟三 實驗步驟 1 直接插入排序 直接插入排序 straight insertion sort 的作法是 每次從無序表中取出第一個元素 把它插入到有序表的合適位置 使有序表仍然有 序 第一趟比較前兩個數 然后把第二個數按大小插入到有序表中 第二趟把第三個數 據與前兩個數從后向前掃描 把第三個數按大小插入到有序表中 依次進行下去 進行 了 n 1 趟掃描以后就完成了整個排序過程 直接插入排序屬于穩(wěn)定的排序 時間復雜性為o n 2 空間復雜度為 O 1 直接插入排序是由兩層嵌套循環(huán)組成的 外層循環(huán)標識并決定待比較的數值 內層 循環(huán)為待比較數值確定其最終位置 直接插入排序是將待比較的數值與它的前一個數值 進行比較 所以外層循環(huán)是從第二個數值開始的 當前一數值比待比較數值大的情況下 繼續(xù)循環(huán)比較 直到找到比待比較數值小的并將待比較數值置入其后一位置 結束該次 循環(huán) 值得注意的是 我們必需用一個存儲空間來保存當前待比較的數值 因為當一趟比較 完成時 我們要將待比較數值置入比它小的數值的后一位 插入排序類似玩牌時整理手中紙 牌的過程 插入排序的基本方法是 每步將一個待排序的記錄按其關鍵字的大小插到前面 已經排序的序列中的適當位置 直到全部記錄插入完畢為止 序序列列 初始序列 i 1 46 58 15 45 90 18 10 62 i 2 46 58 15 45 90 18 10 62 i 3 15 46 58 45 90 18 10 62 i 4 15 45 46 58 90 18 10 62 i 5 15 45 46 58 90 18 10 62 i 6 15 18 45 46 58 90 10 62 21 i 7 10 15 18 45 46 58 90 62 i 8 10 15 18 45 46 58 62 90 C C 代碼實現直接插入排序 for i 1 i 0 j a j a j 1 a j temp Java 代碼實現直接插入排序 public class MainTest public static void main String args int a 46 58 15 45 90 18 10 62 int n a length int i j for i 0 i 0 j a j a j 1 a j temp for i 0 i a i 1 Then 若是遞減 改為 a i a i 1 temp a i 22 a i a i 1 a i 1 temp bSwap True End If Next If bSwap False Then Exit For End If Next For Each c In a Debug Print c Next End Sub 3 歸歸并并排排序序 歸并排序是建立在歸并操作上的一種有效的 排序算法 該算法是采用 分治法 Divide and Conquer 的一個非常典型的應用 將已有序的子序列合并 得到完全有序的序列 即先使每個子序列有序 再使子序 列段間有序 若將兩個有序表合并成一個有序表 稱為2 路歸并 歸并操作 歸并操作 merge 也叫歸并算法 指的是將兩個已經排序的序列合并成一個序列的 操作 如 設有數列 6 202 100 301 38 8 1 初始狀態(tài) 6 202 100 301 38 8 1 比較次數 i 1 6 202 100 301 8 38 1 3 i 2 6 100 202 301 1 8 38 4 i 3 1 6 8 38 100 202 301 4 總計 11 次 算法描述 歸并操作的工作原理如下 申請空間 使其大小為兩個已經排序序列之和 該空間用來存放合并后的序列 設定兩個指針 最初位置分別為兩個已經排序序列的起始位置 比較兩個指針所指向的元素 選擇相對小的元素放入到合并空間 并移動指針到下 一位置 重復步驟 3 直到某一指針達到序列尾 將另一序列剩下的所有元素直接復制到合并序列尾 示例代碼 示例代碼為 C 語言 輸入參數中 需要排序的 數組為 array 起始索引為 first 終止索引為 last 調用完成后 array 中從 first 到 last 處于升序排列 void MergeSort int array int first int last int mid 0 if first last mid first last 2 MergeSort array first mid MergeSort array mid 1 last Merge array first mid last 23 以下示例代碼實現了歸并操作 array 是元素序列 其中從索引 p 開始到 q 位 置 按照升序排列 同時 從 q 1 到 r 也已經按照升序排列 merge 函數將把這兩 個已經排序好的子序列合并成一個排序序列 結果放到array 中 0 p q r subarray array p q and array q 1 r are already sorted the merge function merges the two sub arrays into one sorted array void Merge int array int p int q int r int i k int begin1 end1 begin2 end2 int temp int malloc r p 1 sizeof int begin1 p end1 q begin2 q 1 end2 r k 0 while begin1 end1 begin1 else temp k array begin2 begin2 k while begin1 end1 temp k array begin1 while begin2 end2 temp k array begin2 for i 0 i r p 1 i array p i temp i free temp 24 實驗 8 典型算法的應用 一 實驗目的一 實驗目的 1 掌握分治算法的應用 學習靜態(tài)二分查找 順序統(tǒng)計和二叉排序樹等 2 掌握貪心算法的應用 如會議日程安排 0 1 背包問題等 3 學習動態(tài)規(guī)劃算法的應用 如最長公共子序列 關鍵路徑等 4 學習回溯與分支限界算法的應用 如迷宮問題 旅行售貨員問題等 二 實驗要求二 實驗要求 1 基本掌握分治算法的應用 熟練進行靜態(tài)二分查找 順序統(tǒng)計和二叉排序樹等 2 對貪心算法達到基本掌握的程度 會進行會議日程安排 3 運用動態(tài)規(guī)劃算法 進行最長公共子序列和關鍵路徑的查找 4 綜合運用算法知識 能解決迷宮問題等等 三 實驗步驟三 實驗步驟 1 分治算法 靜態(tài)二分查找 基基本本思思想想 當我們求解某些問題時 由于這些問題要處理的數據相當多 或求解過程相當復雜 使得直接求解法在時間上相當長 或者根本無法直接求出 對于這類問題 我們往往先 把它分解成幾個子問題 找到求出這幾個子問題的解法后 再找到合適的方法 把它們 組合成求整個問題的解法 如果這些子問題還較大 難以解決 可以再把它們分成幾個 更小的子問題 以此類推 直至可以直接求出解為止 這就是分治策略的基本思想 二二分分