【導讀】數(shù)據(jù)結(jié)構(gòu)是對程序中數(shù)據(jù)信息的結(jié)構(gòu)組織，供給定問題求。解算法的控制結(jié)構(gòu)來處理。Niklauswirth曾經(jīng)給出“算法+數(shù)據(jù)結(jié)構(gòu)=程序”的公式，得到了計算機科學界的普遍認可。在程序設計語言中如何表示數(shù)據(jù)和控制，很大程度上決定了。程序設計的主要任務就是在選取或組織適當?shù)臄?shù)據(jù)結(jié)構(gòu)的基?！端惴ㄅc數(shù)據(jù)結(jié)構(gòu)》課程討論數(shù)據(jù)結(jié)構(gòu)的目的，就。本章將從幾個不同的角度討論如何在程序中實現(xiàn)各。構(gòu)，但沒有也不可能提供所有的數(shù)據(jù)結(jié)構(gòu)。一方面，受科學技術(shù)和生產(chǎn)力發(fā)展水平的限制，人類認知世。語言和語言翻譯系統(tǒng)。構(gòu)的基本設施和方法手段。諸如整型數(shù)據(jù)、實型數(shù)據(jù)、布爾型數(shù)據(jù)和字符型數(shù)。程序設計人員只要在程序中用相應的類型標識符直。字符串、結(jié)構(gòu)體、共同體、文件等。計人員不能夠在程序中用類型說明的辦法直接引入。數(shù)據(jù)元素的結(jié)點類型，如說明成記錄、結(jié)構(gòu)體等，樹可通過左孩子右兄弟表示法轉(zhuǎn)。靜態(tài)分配、部分采用動態(tài)分配的數(shù)據(jù)結(jié)構(gòu)。模擬實現(xiàn)靜態(tài)鏈表的數(shù)組可如下定義：

　　

【正文】 最多的匹配稱作 G的 最大匹配（ maximal matching） 。 如果在圖 G的一個匹配中 ， 圖中每個頂點都是該匹配中某條邊的端點 ， 則稱該匹配為圖 G的完全匹配 （ plete matching） 。 圖 G的任何一個完全匹配 ，一定都是圖 G的 最大匹配 。 二分圖 TCG的匹配和最大匹配示例 ?下圖 (a)和 (b)的實線邊分別給出了前例中二分圖 TCG的一個匹配和一個最大匹配的示例 。 二分圖 TCG的匹配和最大匹配 ? 為了求出一個圖的最大匹配 ， 顯而易見的辦法是列舉出該圖的全部匹配 ， 然后選出邊數(shù)最多的一個匹配 。 然而 ， 這種方法的時間復雜度是邊數(shù)的指數(shù)階函數(shù) 。 因此 ， 需要一種更有效的匹配算法 。 ? 下面介紹一種利用增廣路徑求最大匹配的有效算法 。 ?設 M是圖 G的一個匹配 ， 我們將 M中的邊所關聯(lián)的頂點稱為已匹配頂點 ， 其余頂點稱為未匹配頂點 。 若 P是圖 G中一條連通兩個未匹配頂點的路徑 ， 并且在 P上屬于 M的邊和不屬于 M 的邊交替出現(xiàn) ， 則稱 P為一條關于 M的增廣路徑 （ augmenting path） 。 二分圖 TCG的匹配和最大匹配（續(xù)） ?由利用增廣路徑求最大匹配的有效算法的定義可有如下結(jié)論： ⑴ 一條關于 M的增廣路徑的長度必為奇數(shù) ， 且路徑上的第一條邊和最后一條邊都不屬于 M。 ⑵ 對于一條關于 M的增廣路徑 P， 由對稱差集運算 M⊕ P可以得到一個比 M更大的匹配 。 即這個更大的匹配包括所有在 M中但不在 P中和在 P中但不在 M 中的邊的集合構(gòu)成 。 ⑶ M為 G的一個最大匹配 ， 當且僅當不存在關于 M的增廣路徑 。 ? 結(jié)論 ⑴ 和 ⑵ 是顯而易見的 。 ?對于結(jié)論 ⑶ ， 當存在一條關于 M的增廣路徑時 ， 由結(jié)論 ⑵ 知M不是最大匹配；反之 ， 當 M不是最大匹配時 ， 一定可以找到一條關于 M的增廣路徑 。 二分圖 TCG的匹配和最大匹配（續(xù)） ?事實上 ， 設 N是一個比 M更大的匹配 ， 并令 =(V， M⊕ N)；因為 M和 N都是 G的一個匹配 ， 所以 V中的頂點最多和 M中的一條邊相關聯(lián) ， 也最多和 N 中的一條邊相關聯(lián)；于是的每個連通分量都是由 M和 N中的邊交替組成的一條簡單路徑或環(huán) ， 每個環(huán)中所含 M和 N的邊數(shù)相等 ， 而每條簡單路徑是一條關于 M的增廣路徑或關于 N的增廣路徑 ， 由于中的邊 M⊕ N所含 N的邊數(shù)較 M多 ， 所以中必含一條關于 M的增廣路徑 。 ? 由此 ， 求圖 G=(V， E)的最大匹配 M的算法可描述如下： ⑴ 置 M為空集； ⑵ 找出一條關于 M的增廣路徑 P， 并用 M⊕ P代替 M； ⑶ 重復步驟 ⑵ 直至不存在關于 M的增廣路徑 ， 此時得到的匹配 M即為 G的最大匹配 。 二分圖 TCG的匹配和最大匹配（續(xù)） ? 在上述算法中 ， 關鍵問題是如何根據(jù)已有匹配 M找出 G中關于 M 的一條增廣路徑 。 為簡化起見 ， 我們只討論 G是二分圖的情形 。 ?設 M是 G的一個匹配 ， 用類似于圖的廣度優(yōu)先搜索過程構(gòu)造一棵樹 。設層號為 i， 當 i=0時取 G的一個未匹配頂點作為樹根；當 i為奇數(shù)時 ，將那些與第 i1層中一個頂點相關聯(lián)但不屬于 M的邊 ， 連同該邊相關聯(lián)的另一個頂點一起添加到樹上；當 i為偶數(shù)時 ， 則是添加那些與第 i1層中一個頂點相關聯(lián)且屬于 M的邊以及該邊所關聯(lián)的另一個頂點 。 ?如果在上述樹的構(gòu)造過程中 ， 發(fā)現(xiàn)一個未匹配頂點 v被作為樹的奇數(shù)層頂點 ， 則從樹根到頂點 v的路徑就是一條關于 M的增廣路徑；如果在樹的構(gòu)造過程中既沒有找到增廣路徑 ， 又無法按要求往樹上添加新的邊和頂點 ， 則可在剩余頂點中再取一個未匹配頂點作樹根構(gòu)造新的一棵樹 。 這個過程一直進行下去 ， 如果不存在其它未匹配頂點 ， 即最終仍未得到任何增廣路徑 ， 就說明 M已為一個最大匹配了 。 二分圖 TCG的匹配和最大匹配舉例 ? 例如 ， 對前例圖 (a)中實線邊 （ 圖 TCG的匹配 M） ： ?按上述方法取未匹配頂點 t5作為樹根 ， 頂點 c1是樹上惟一的第一層中的頂點 ， 未匹配邊 （ t5， c1） 是樹上的一條邊； ?頂點 t2處于樹的第二層 ， 邊 （ c1， t2） 屬于 M且關聯(lián)于 c1是樹上的又一條邊； ?與 t2相關聯(lián)但不屬于 M的邊有 （ t2， c4） 和 （ t2， c5） 添加到樹中 ， 同時頂點 c4和 c5添加到樹中作為第三層； ?由于 c5是未匹配頂點 ， ?所以到此找到了一條增廣路徑 P： t5→c 1→t 2→c 5。 ?由此增廣路徑得到圖 G的一個更大的匹配 M⊕ P如前例圖 (b)中實線邊所示 ， 此時的 M⊕ P是一個完全匹配 ， 從而也是 G的最大匹配 。 二分圖 TCG的匹配和最大匹配（續(xù)） ? 設二分圖 G有 n個頂點和 e條邊 ， M是 G的一個匹配 。如果用 鄰接表 表示 G， 那么求一條關于 M的增廣路徑需要 O(e)的時間； ?由于每找出一條新的增廣路徑都將得到一個更大的匹配 ， 所以最多求 n/2條增廣路徑就可以求出圖 G的最大匹配 。 ?因此 ， 求圖 G的最大匹配所需時間為 O(ne)。 數(shù)據(jù)結(jié)構(gòu)在問題建模中的應用 Josephus問題 教務管理與二分圖 學籍管理系統(tǒng)中的數(shù)據(jù)組織 學籍管理系統(tǒng)中的數(shù)據(jù)組織 ?在一個約四千名學生的學院中 ， 學生的學籍檔案就構(gòu)成了一個學籍文件 ， 該文件中包含學生的標識信息和當前學期所學課程的信息 ， 當然還可以包含諸如入學考試成績 、 學費支付情況 、 健康狀況和專長等其它數(shù)據(jù)信息 ， 為了簡化討論假定這些信息不包含在文件中 ， 并假定文件較小足以在內(nèi)存中處理不需要訪問外存儲器 。 學籍管理系統(tǒng)中的數(shù)據(jù)組織（續(xù)） ? 對于一個學生而言 ， 需要標識學生的信息 （ 學生數(shù)據(jù) ） 和該生學習課程的說明數(shù)據(jù) （ 課程數(shù)據(jù) ） 。 ?學生數(shù)據(jù)有姓名 、 性別 、 年齡 、 住址和學號等 。 其中學號由兩個部分組成：注冊年號和編號 。 注冊年號為入學登記時的年號 ， 如 2020年入學的注冊年號為 00；編號是某一年內(nèi)入學登記的順序號 ， 從 0001開始編號 。 ?課程數(shù)據(jù)有本學期所學課程門數(shù)和每一門課程的課程說明 。 每門課程的說明包括課程標識符 （ 學科代碼 、 年級號 、 編號 ） ， 各周安排情況和成績記載等 。 學科代碼即專業(yè)或系名稱代碼 ， 年級號為 1~4， 編號為具體課程的編號 。 ?每周安排情況包括上課方式 （ L：講課 ， T：輔導 ， Y：實驗 ） 、 節(jié)數(shù) 、 時間 （ 星期幾 、 幾點上 ） 、 地點 （ 表示樓號 、 教室號 ） 和指導教師 。 成績記載包括平時成績 、 考試成績和總評成績 。 對于每個學生都有這樣一張表；表的集合就構(gòu)成了學籍文件 。 一個學生記錄結(jié)構(gòu)舉例 學籍管理系統(tǒng)中的運算 ?對于上圖的記錄構(gòu)成的學籍文件可以相應定義一些運算 。 如： ⑴ 打印指定學生所學全部課程的名稱； ⑵ 對指定學生增添或刪除一門課程； ⑶ 更改指定學生指定課程的分數(shù)； ⑷ 找出指定學生在指定時間上課的教室； ⑸ 修改指定學生其它域的值； ⑹ 在指定學科指定年級中求學生的平均成績； ⑺ 按字母順序列出學習指定學科指定課程的所有學生名； ⑻ 更改學習指定課程的所有學生的成績； ⑼ 按字母順序列出指定注冊年份的所有學生名； ⑽ 列出指定學科指定年級所開設的全部課程 。 ?這些運算涉及到學生數(shù)據(jù) 、 課程數(shù)據(jù) ， 或是數(shù)據(jù)中某個域的值 ， 都是頻繁出現(xiàn)的最常用運算 。 學籍管理系統(tǒng)中的運算（續(xù)） ? 對于任何實際問題 ， 都應該從效率的觀點和經(jīng)濟的觀點出發(fā)考慮設計方法 ， 一般都有一些限制條件 ， 如本例可以做如下兩點限制： ? ① 在每次執(zhí)行運算時 ， 不允許遍歷整個文件；因為這樣做的代價太高了； ? ② 同一數(shù)據(jù)不應重復存放在內(nèi)存中 ， 即不允許數(shù)據(jù)冗余 。 ?前一個限制對于小文件似乎不必要 ， 但對于大文件（ 例如數(shù)萬人的大學 ） 就十分必要了；后一個限制在實踐中常常被放寬 ， 因為有時需要把一個記錄的同一部分保存在若干地方 ， 以加快運算執(zhí)行減少運行時間提高算法效率 。 學籍管理系統(tǒng)中的運算（續(xù)） ?考察前面的十種常用運算可以看出 ， 前五種運算主要是訪問學生數(shù)據(jù) ， 后五種運算主要是訪問課程數(shù)據(jù) 。 ?不同的訪問路徑將決定一個文件的某些部分重新組織而形成的子結(jié)構(gòu) ， 以便于實現(xiàn)相應的運算；各個子結(jié)構(gòu)相互獨立 ， 共享學生數(shù)據(jù)和課程數(shù)據(jù)的有關部分 。 ?此外 ， 還可根據(jù)其它運算設立其它子結(jié)構(gòu) ， 如列出指定教師講授哪些課程的運算 ， 若不允許查找整個文件則需在教師數(shù)據(jù)的一條路徑或子結(jié)構(gòu)中檢索 。 ?類似地 ， 另一個運算列出指定教室被占用的時間 ， 此時教室數(shù)據(jù)的子結(jié)構(gòu)就十分重要了 。 下一章討論的各種檢索方法都是可行的 ， 可以將數(shù)據(jù)用數(shù)組 、 鏈接表 、 多重表 、 哈希表 、 樹等任一結(jié)構(gòu)表示 ， 子結(jié)構(gòu)也使用相應的某種結(jié)構(gòu)形式構(gòu)成；至于具體采用何種結(jié)構(gòu)形式 ， 要視具體問題的需要而定 。 ? 標識一個學生通?？墒褂脤W生名字和學生號碼兩種方式 。 在某個訪問中若不明確指出采用哪一種標識 ， 可隨意使用其中一種標識方式訪問 ， 所以在學生數(shù)據(jù)子結(jié)構(gòu)中應該準備兩種方式 。 學生名字一般是不同的 ， 但也偶然有重名情況；而學生號碼的是惟一的 ， 可以作為主關鍵字 。 ? 首先考慮按學號訪問 。 假設學號是六位數(shù)字組成： Y1Y2X1X2X3X4。Y1Y2注冊年號 ， 是從某一年開始的連續(xù)數(shù)； X1X2X3X4為注冊年內(nèi)的順序編號 ， 從 0001開始連續(xù)編號直到該年注冊學生總數(shù) TYR為止 。 這樣 ，對于學號可以用一個二維數(shù)組來表示 ， Y1Y2作為第一維的下標 ，X1X2X3X4作為第二維的下標 ， 數(shù)組中的每一個元素就標識一位學生 ，顯然這種表示對于訪問來說是相當高效的 。 ?如果給數(shù)組元素的值賦以對應學生記錄的地址 ， 則此數(shù)組就成為學號索引；為了訪問任何一個學生 ， 都能根據(jù)學號隨機訪問數(shù)組得到學生記錄的起始地址 ， 從而快速得到該生的全部信息 。 學生數(shù)據(jù)子結(jié)構(gòu)舉例 學生數(shù)據(jù)子結(jié)構(gòu)（續(xù)） ?現(xiàn)在討論用學生名訪問的問題 。 由于學生名是一字符串 ， 不同學生的名字一般不同且無順序 ， 還有重名情況 ， 所以不宜用數(shù)組結(jié)構(gòu)表示不同學生的數(shù)據(jù)起始地址 。 ?如果采用二叉樹構(gòu)成學生名字索引 ， 需要 次比較才能確定一個學生名的記錄地址；若不是完全二叉樹比較次數(shù)還要多 。 ?采用什么樣的結(jié)構(gòu)較好呢 ？ 當關鍵字范圍很寬而實際關鍵字值較少時 ， 采用下一章要介紹的哈希技術(shù)最為有效 。 ?這里 ， 建立含有 5000項的學生名字哈希表索引 ， 每一項存放與一個學生名字的哈希值相對應記錄的起始地址；當學生名字相同時采用鏈地址法 （ 拉鏈法 ） 消解沖突 ， 即在學生數(shù)據(jù)多重表中設立指向哈希值相同的另一個學生數(shù)據(jù)的鏈域 。 學生數(shù)據(jù)子結(jié)構(gòu)（續(xù)） ? 學生子結(jié)構(gòu)的其它部分包括學生數(shù)據(jù)和課程數(shù)據(jù) 。 其中學生數(shù)據(jù)用多重表結(jié)構(gòu)表示 ， 名字的哈希函數(shù)值相同者組成一個鏈表；由于在一個學期中允許學生改變已登記所學課程的門數(shù) ， 所以課程數(shù)據(jù)構(gòu)成一個鏈表 ， 便于增添和刪減 。 課程數(shù)據(jù)結(jié)構(gòu)鏈表 ， 是學生數(shù)據(jù)多重表的一個子表；在學生數(shù)據(jù)多重表的每個元素中設立一個鏈域指向所學課程鏈表的第一個元素 。 ?根據(jù)前例圖的學生數(shù)據(jù)子結(jié)構(gòu) ， 前五個運算的大部分都能有效地實現(xiàn) 。 然而如找出指定學生指定時間的上課教室 ， 由于要訪問的信息不在學生數(shù)據(jù)子結(jié)構(gòu)中 ， 需要訪問下面介紹的課程數(shù)據(jù)子結(jié)構(gòu) 。 ?由于課程是由學科開設的 ， 所以課程數(shù)據(jù)子結(jié)構(gòu)往往又稱為學科 /課程子結(jié)構(gòu) 。 它是學籍文件中十分重要的子結(jié)構(gòu) ， 對于訪問指定學科 /課程的所有學生信息是很有用的 。 ?學科 /課程子結(jié)構(gòu) ， 可以采用索引倒排文件或索引多重表結(jié)構(gòu) ， 兩者都有各自的優(yōu)點和不足之處；對于某些運算而言 ， 選取倒排文件可能比把信息深深嵌放在多重表中要容易實現(xiàn)一些 。 課程數(shù)據(jù)子結(jié)構(gòu)運算舉例 ? 例如 ， 某學生要求刪減一門課程 ， 需執(zhí)行： ① 尋找指定課程 ， ② 查找注冊表直到找出指定的學生 ， ③ 刪減該學生的指定課程 。 ?執(zhí)行 ① 需要在課程索引的倒排文件中檢索所指定課程 ， 若索引是多重表結(jié)構(gòu)檢索過程類似；執(zhí)行 ②需檢索由 ① 所確定課程的倒排文件 ， 若是多重表結(jié)構(gòu)需從頭檢索學生數(shù)據(jù)；執(zhí)行 ③ 修改課程索引所指的倒排文件和學生數(shù)據(jù)的有關項 ， 若是多重表結(jié)構(gòu)則需要修改學生數(shù)據(jù) ， 其修改過程稍微復雜一些 。 課程數(shù)據(jù)子結(jié)構(gòu)（續(xù)） ?比上述兩種形式都更為合適的學科 /課程子結(jié)構(gòu) ，是采用一種二叉樹的結(jié)構(gòu)形式 。 ?按照學科 /課程編碼 ， 構(gòu)造一棵按字典序的中序二叉檢索樹索引； ?樹中每個結(jié)點表