【正文】 動借助計算機系統(tǒng)完成。2）實驗要求：作為演示系統(tǒng)，不必使用文件，全部數據可以在內存中存放。3) 實現提示：建立 B 樹結構，利用 B 樹插入、刪除算法做入庫、出庫操作。六、選做實驗內容（可利用課外實驗學時完成）實驗六 排序一、實驗目的 掌握常見的排序算法(插入排序、交換排序、選擇排序、歸并排序、基數排序等)的思想、特點及其適用條件。 能夠分析各種算法的效率 熟練掌握常見的排序算法的程序實現。二. 實驗學時：課內實驗學時：2 學時課外實驗學時：4 學時三、備選實驗題目1．常見排序算法實現（實驗類型：驗證型）1）問題描述：輸入一組關鍵字序列分別實現下列排序: （1）實現簡單選擇排序、直接插入排序和冒泡排序。 （2）實現希爾排序算法。 （3）實現快速排序算法。 （4）實現堆排序算法。 *（5 ）快速排序的非遞歸算法。 （6）實現折半插入排序。（7）在主函數中設計一個簡單菜單，分別測試上述算法。2) 實現提示： ? 數據類型定義（C 語言） define MAXSIZE 100 /*參加排序元素的最大個數*/ typedef struct list { int key。 }RedType。 typedef struct { RedType r[MAXSIZE+1]。 int length。 /*參加排序元素的實際個數*/ }SqList。? 算法 5 可以借助棧實現。3）注意問題：? 在 RedType 中增加一個數據項驗證各種排序算法的穩(wěn)定性。? 注意理解各種算法的思想、了解算法的適用情況及時間復雜度，能夠根據實際情況選擇合適的排序方法。2．統(tǒng)計成績：（實驗類型：綜合型）1）問題描述：給出 n 個學生的考試成績表，每條信息由姓名和分數組成，試設計一個算法：? 按分數高低次序，打印出每個學生在考試中獲得的名次，分數相同的為同一名次；? 按名次列出每個學生的姓名與分數。2）基本要求：學生的考試成績表必須通過鍵盤輸入數據而建立，同時要對輸出進行格式控制。實驗七 數組和廣義表一、實驗目的 掌握稀疏矩陣的表示方法及其運算的實現 實現稀疏矩陣在三元組、十字鏈表等表示下的各運算并分析其效率二. 實驗學時：課外實驗學時：4 學時三、備選實驗題目：1．稀疏矩陣運算器（實驗類型：綜合型）1）問題描述：稀疏矩陣是指那些多數元素為零的矩陣。利用“ 稀疏 ”特點進行存儲和計算可以大大節(jié)省存儲空間，提高計算效率。本實驗的主要任務是實現一個能進行稀疏矩陣基本運算的運算器。 2）實驗要求：? 以“帶行邏輯鏈接信息” 的三元組順序表表示稀疏矩陣，實現兩個矩陣相加、相減和相乘的運算。稀疏矩陣的輸入形式采用三元組表示，而運算結果的矩陣則以通常的陣列形式列出。? 測試數據： 3）實現提示? 首先應輸入矩陣的行數和列數，并判別給出的兩個矩陣的行、列數對于所要求作的運算是否相匹配?？稍O矩陣的行數和列數均不超過 20。? 程序可以對三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書 節(jié)中的算法，以便提高計算效率。10 0 0 0 0 0 10 0 00 0 9 + 0 0 1 = 0 0 81 0 0 1 0 3 0 0 310 0 0 0 10 00 9 + 0 1 = 0 101 0 1 3 2 34 3 0 0 1 0 0 0 8 0 0 0 1 0 0 0 0 0 0 70 3 0 04 2 00 1 01 0 00 0 00 6 0 = 8 0 0 0 1 0 0 0 0 ? 在用三元組表示稀疏矩陣時，相加或相減所得結果矩陣應該另生成，乘積矩陣也可用二維數組存放。實驗八 串一、實驗目的 理解串的模式匹配算法（包括 KMP 算法） 。 明確串也是特殊的線性表，掌握其特殊性所在。 熟悉一般文字處理軟件的設計方法、較復雜問題的分解方法。二. 實驗學時：課外實驗學時：6 學時三、備選實驗題目：1．實現一個簡單行編輯程序（實驗類型：綜合型）1）問題描述：文本編輯程序利用計算機進行文字加工的基本軟件工具，實現對文本文件的插入、刪除等修改操作。限制這些操作以行為單位進行的編輯程序為行編輯程序。被編輯的文本文件可能很大，全部讀入編輯程序的數據空間（內存）的作法既不經濟，也不總能實現。一種解決逐段編輯。任何時刻只把待編輯文件的一段放在內存，稱為活區(qū)。試按照這種方法實現一個簡單的行編輯程序。設文件每行不超過 320個字符，很少超過 80 個字符。2）實驗要求：實現以下 4 條基本編輯命令：? 行插入。格式：i 行號 回車 文本 ，回車 將文本插入活區(qū)中第行號行之后。? 行刪除。格式：d行號 1[空格 行號 2]回車刪除活區(qū)中第行號 1行（到第行號 2行） 。例如：“d10Enter”和“d10 14Enter”。? 活區(qū)切換。格式：n回車將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。? 活區(qū)顯示。格式：p回車逐頁地（每頁 20 行）顯示活區(qū)內容，每顯示一頁之后請用戶決定是否繼續(xù)顯示以后各頁（如果存在） 。印出的每一行要前置行號和一個空格符，行號固定占 4 位，增量為 1。? 各條命令中行號均須在活區(qū)中各行行號范圍之內，只有插入命令的行號要以等于活區(qū)第一行行號減 1，表示插入當前屏幕中第一行之前，否則命令參數非法。3）實現提示? 設活區(qū)的大小用行數 ActiveMaxLen（可設為 100）來描述。考慮到文本文件行長通常為正態(tài)分布，且峰值在 60 到 70 之間，用 320ActuveMaxLen 大小的字符數組實現存儲將造成大量浪費。可以以標準行塊為單位為各行分配存儲，每個標準行塊可含 81 個字符。這些行塊可以組成一個數組，也可以利用動態(tài)鏈表連接起來。一行文字可能占多個行塊。行尾可用一個特殊的 ASCII 字符（如（ 012）8）標識。此外，還應記住活區(qū)起始行號。行插入半引起隨后各行行號的順序下推。? 初始化函數包括：請用戶提供輸入文件名（空串表示無輸入文件）和輸出文件名，兩者不能相同。然后盡可能多地從輸入文件中讀入各行，但不超過ActiveMaxLenx。x 的值可以自定，例如 20。? 在執(zhí)行行插入命令的過程中，每接收到一行時都要檢查活區(qū)大小是否已達 ActiveMaxLen。如果是，則為了在插入這行之后仍保持活區(qū)大小 不超過ActiveMaxLen,應將播入點之前的活區(qū)部分中第一行輸出到輸出 文件中，若插入點為第一行之前，則只得將新插入的這一行輸出。? 若輸入文件尚未讀完，活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部，以保持閱讀連續(xù)性；否則，它意味著結束編輯或開始編輯另一個文件?？闪钋叭龡l命令執(zhí)行后自動調用活區(qū)顯示。?