數(shù)據(jù)結(jié)構(gòu)與算法 第3版 教學(xué)課件 作者 張小莉第8章 擴(kuò)展應(yīng)用舉例

第8章擴(kuò)展應(yīng)用舉例2023/2/201.教學(xué)內(nèi)容求最大子段和、表達(dá)式樹的構(gòu)造、由等價(jià)關(guān)系求劃分2.教學(xué)目的

理解窮舉的思想，能夠應(yīng)用窮舉思想設(shè)計(jì)算法以及進(jìn)行算法分析的。理解分治策略的思想，以及分治與遞歸的關(guān)系；并能舉出在數(shù)據(jù)結(jié)構(gòu)課程中應(yīng)用分治策略的算法。理解動(dòng)態(tài)規(guī)劃策略的思想，以及其求解過程與分治策略的不同之處。理解表達(dá)式與二叉樹的對應(yīng)關(guān)系；鞏固對字符串、棧和二叉樹存儲和遍歷知識的掌握。掌握用樹表示集合的方法，理解其便利之處和存在的問題與解決思路。3.教學(xué)重點(diǎn)

窮舉法、分治策略和動(dòng)態(tài)規(guī)劃策略在算法設(shè)計(jì)中的應(yīng)用。表達(dá)式與二叉樹的對應(yīng)關(guān)系。采用樹結(jié)構(gòu)表達(dá)集合的應(yīng)用。4.教學(xué)難點(diǎn)

動(dòng)態(tài)規(guī)劃的策略思想2023/2/208.1求最大子段和問題的描述

給定有n個(gè)整數(shù)(可能為負(fù)整數(shù))組成的序列a1,a2,...,an，求該序列連續(xù)的子段和的最大值；如果這個(gè)最大值是負(fù)整數(shù)，則定義其最大子段和為0。即根據(jù)下面的公式進(jìn)行求解。

例如：

(a1,a2,a3,a4,a5)=(-5,11,-4,13,-4-2)

最大子段和為11+(-4)+13=20。2023/2/20問題分析與解決1．?dāng)?shù)據(jù)的存儲

這個(gè)應(yīng)用要處理的數(shù)據(jù)是線性結(jié)構(gòu)，由于要對不確定長度的數(shù)據(jù)進(jìn)行求和，因此采用順序存儲比較方便，這里用一維數(shù)組List存放數(shù)據(jù)，每個(gè)數(shù)據(jù)元素為整型。

2．簡單窮舉法【算法8-1】簡單窮舉法求解最大子段和2023/2/203．改進(jìn)的窮舉法

通過分析，可以看到，從位置i到位置j的子列和等于從位置i到位置j－1的子列和加上List[j]，即

2023/2/204．分治法

所謂分治法就是將一個(gè)難以解決的問題拆分成若干小問題或規(guī)模較小的相同問題，分別解決后原問題便得到解決，即所謂各個(gè)擊破分而治之。本問題采用的是類似歸并排序的遞歸算法的拆分方法，簡要描述如下。步驟1：將所給序列List[0]~List[n-1]分為兩段List[0]~List[n/2-1]和List[n/2]~List[n-1]；步驟2：分別遞歸求得兩段的最大子列和MaxLeftSum和MaxRightSum；步驟3：從中分點(diǎn)分別向左、右兩邊掃描，找出中間跨分界線的最大子列和MaxMidSum；步驟4：MaxSum＝max{MaxLeftSum，MaxMidSum，MaxRightSum}。2023/2/202023/2/205．動(dòng)態(tài)規(guī)劃法

動(dòng)態(tài)規(guī)劃方法是一種自底向上的求解方法，即根據(jù)得到的遞歸式，按照遞歸返回的順序計(jì)算所要求的值。從上述基于分治思想的求解分析中可看出，若記則所求的最大子段和為：由b[j]的定義知，當(dāng)b[j－1]>0時(shí)，b[j]=b[j－1]＋a[j]，否則b[j]=a[j]。由此可得計(jì)算b[j]的動(dòng)態(tài)規(guī)劃遞歸式：2023/2/202023/2/20問題描述可以用二叉樹的形式表示表達(dá)式，這樣就可以通過對二叉樹的遍歷完成表達(dá)式的計(jì)算，那么如何將一串字符構(gòu)成的算術(shù)表達(dá)式轉(zhuǎn)換為二叉樹形式的存儲就是首先要解決的問題。假設(shè)一串字符構(gòu)成的算術(shù)表達(dá)式是僅含有二目運(yùn)算的前綴、中綴和后綴表達(dá)式，考慮如何將它們轉(zhuǎn)換成二叉樹的表示形式。

8.2表達(dá)式樹的構(gòu)造2023/2/20問題分析與解決

本問題的輸入數(shù)據(jù)是一串字符，在轉(zhuǎn)換過程中，該串字符不需要改變，只需要順次讀取，因此可采用一維字符數(shù)組存儲。本問題的輸出是棵二叉樹，二叉樹中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)橐粋€(gè)運(yùn)算對象或運(yùn)算符。將順序存儲的前綴表達(dá)式轉(zhuǎn)換為表達(dá)式的二叉樹存儲時(shí)，需要借助一個(gè)棧空間幫助實(shí)現(xiàn)，用于暫存構(gòu)造二叉樹存儲過程中形成的子樹的根結(jié)點(diǎn)。2023/2/201．順序存儲的前綴表達(dá)式轉(zhuǎn)換為表達(dá)式的二叉樹存儲

步驟1：讀取表達(dá)式串的第一個(gè)字符。

步驟2：如果當(dāng)前讀入的字符是運(yùn)算符，則將其作為單個(gè)結(jié)點(diǎn)構(gòu)造一棵二叉樹，并將這棵二叉樹結(jié)點(diǎn)壓入堆棧。步驟3：如果當(dāng)前讀入的字符是運(yùn)算對象，則將其作為單個(gè)結(jié)點(diǎn)構(gòu)造一棵二叉樹，然后讀取棧頂元素，根據(jù)如下判斷進(jìn)行處理：

如果當(dāng)前棧頂元素為運(yùn)算符結(jié)點(diǎn)，則將構(gòu)造的運(yùn)算對象結(jié)點(diǎn)二叉樹入棧；

如果當(dāng)前棧頂元素為運(yùn)算對象結(jié)點(diǎn)，則彈出棧頂?shù)那皟蓚€(gè)元素，第二個(gè)彈出的結(jié)點(diǎn)必為運(yùn)算符結(jié)點(diǎn)，將彈出的第一個(gè)結(jié)點(diǎn)和構(gòu)造的結(jié)點(diǎn)分別作為運(yùn)算符結(jié)點(diǎn)的左子樹和右子樹，此時(shí)形成了一棵以運(yùn)算符結(jié)點(diǎn)為根的二叉樹，再準(zhǔn)備將該二叉樹的根結(jié)點(diǎn)作為運(yùn)算對象入棧，回到步驟3開始處繼續(xù)。

步驟4：若表達(dá)式串未讀完，讀取表達(dá)式串的下一個(gè)字符，回到步驟2繼續(xù)處理；若表達(dá)式串已讀完，則當(dāng)前棧頂元素的值為二叉樹存儲表達(dá)式的根結(jié)點(diǎn)，彈出并返回之即可。

2023/2/20例如，將前綴表達(dá)式串－*3^2－＋4*22*135構(gòu)造成表達(dá)式的二叉樹存儲過程如圖8-1所示，圖中在的堆棧中畫出的標(biāo)記“1”的子樹，是指當(dāng)前得到的子樹，它還沒有入棧，需要根據(jù)情況執(zhí)行入棧或從棧中彈出元素，構(gòu)成新的子樹。

2023/2/20

2023/2/202．順序存儲的中綴表達(dá)式轉(zhuǎn)換為表達(dá)式的二叉樹存儲

步驟1：讀取表達(dá)式串的第一個(gè)字符。

步驟2：如果當(dāng)前讀入的字符是運(yùn)算對象，則將其作為單個(gè)結(jié)點(diǎn)構(gòu)造一棵二叉樹，并將這棵二叉樹結(jié)點(diǎn)壓入子樹棧。

步驟3：如果當(dāng)前讀入的字符是運(yùn)算符，則將其作為單個(gè)結(jié)點(diǎn)構(gòu)造一棵二叉樹，然后讀取運(yùn)算符棧頂元素，根據(jù)如下判斷進(jìn)行處理：

如果當(dāng)前運(yùn)算符棧的棧頂結(jié)點(diǎn)存儲的運(yùn)算符優(yōu)先級低于當(dāng)前構(gòu)造結(jié)點(diǎn)的運(yùn)算符，則將構(gòu)造的運(yùn)算符結(jié)點(diǎn)二叉樹入運(yùn)算符棧；

如果當(dāng)前運(yùn)算符棧的棧頂結(jié)點(diǎn)存儲的運(yùn)算符優(yōu)先級高于當(dāng)前構(gòu)造結(jié)點(diǎn)的運(yùn)算符，則從運(yùn)算符棧出棧一個(gè)結(jié)點(diǎn)，以該結(jié)點(diǎn)為根構(gòu)造二叉子樹，從子樹棧中彈出前兩棵子樹，分別作為根結(jié)點(diǎn)的左孩子和右孩子，然后將新構(gòu)成的子樹入子樹棧，回到步驟3開始處，繼續(xù)處理。

步驟4：若表達(dá)式串未讀完，讀取表達(dá)式串的下一個(gè)字符，回到步驟2繼續(xù)處理；若表達(dá)式串已讀完，則當(dāng)前棧頂元素的值為二叉樹存儲表達(dá)式的根結(jié)點(diǎn)，彈出并返回之即可。2023/2/203．順序存儲的后綴表達(dá)式轉(zhuǎn)換為表達(dá)式的二叉樹存儲

步驟1：讀取表達(dá)式串的第一個(gè)字符。

步驟2：如果當(dāng)前讀入的字符是運(yùn)算對象，則將其作為單個(gè)結(jié)點(diǎn)構(gòu)造一棵二叉樹，并將這棵二叉樹結(jié)點(diǎn)壓入堆棧。

步驟3：如果當(dāng)前讀入的字符是運(yùn)算符，則將其作為單個(gè)結(jié)點(diǎn)構(gòu)造一棵二叉樹，然后彈出棧中的前兩個(gè)元素，將它們分別作為所構(gòu)造二叉樹運(yùn)算符結(jié)點(diǎn)的左子樹和右子樹，并將這個(gè)運(yùn)算符結(jié)點(diǎn)入棧。

步驟4：若表達(dá)式串未讀完，讀取表達(dá)式串的下一個(gè)字符，回到步驟2繼續(xù)處理；若表達(dá)式串已讀完，則當(dāng)前棧頂元素的值為二叉樹存儲表達(dá)式的根結(jié)點(diǎn)，彈出并返回之即可。2023/2/20問題描述

已知集合S及其上的等價(jià)關(guān)系R，求R在S上的一個(gè)劃分{S1,S2,…,Sn}，其中，S1,S2,…,Sn分別為R的等價(jià)類，它們滿足：

設(shè)集合S中有n個(gè)元素，關(guān)系R中有m個(gè)序偶對。

8.3由等價(jià)關(guān)系求劃分2023/2/20問題分析與解決

集合S上的等價(jià)關(guān)系R是指由集合S中的元素構(gòu)成的序偶的集合，且該序偶的集合在S上滿足自反的、對稱的和可傳遞的。該問題的輸入是m個(gè)序偶，輸出是若干個(gè)子集，處理思路如下。（1）令S中每個(gè)元素各自形成一個(gè)單元素的子集，記作S1，S2，…，Sn；（2）重復(fù)讀入m個(gè)序偶對，對每個(gè)讀入的序偶對<x,y>，判定x和y所屬子集。不失一般性，假設(shè)x∈Si，y∈Sj，若Si≠Sj，則將Si并入Sj，并置Si為空（或?qū)j并入Si，并置Sj為空）；若Si＝Sj，則不做什么操作，接著讀入下一對序偶。直到m個(gè)序偶對都被處理過后，S1，S2，…，Sn中所有非空子集即為S的R等價(jià)類，這些等價(jià)類的集合即為集合S的一個(gè)劃分。

2023/2/20

通過前面的分析可知，本算法在實(shí)現(xiàn)過程中所用到的基本操作有以下兩個(gè)。（1）Find(S，x)查找函數(shù)。確定集合S中的單元素x所屬子集Si，函數(shù)的返回值為該子集樹根結(jié)點(diǎn)在雙親表示法數(shù)組中的序號；（2）Union(S，i，j)集合合并函數(shù)。將集合S的兩個(gè)互不相交的子集合并，i和j分別為兩個(gè)子集用樹表示的根結(jié)點(diǎn)在雙親表示法數(shù)組中的序號。合并時(shí)，將一個(gè)子集的根結(jié)點(diǎn)的雙親域的值由沒有雙親改為指向另一個(gè)子集的根結(jié)點(diǎn)。2023/2/20

下面就本問題的解決算法步驟給出描述：

步驟1：k=1；

步驟2：若k>m則轉(zhuǎn)步驟7，否則轉(zhuǎn)步驟3；

步驟3：讀入一序偶對<x,y>；

步驟4：i=Find(S,x)，j=Find(S,y)；

步驟5：若i≠j，則Union(S,i,j)；

步驟6：++k;轉(zhuǎn)步驟2

步驟7：輸出結(jié)果,結(jié)束。2023/2/20算法的時(shí)間復(fù)雜度：

集合元素的查找算法和不相交集合的合并算法的時(shí)間復(fù)雜度分別為O(d)和O(1)，其中d是樹的深度。這種表示集合的樹的深度和樹的形成過程有關(guān)。

在極端的情況下，每讀入一個(gè)序偶對，就需要合并一次，即最多進(jìn)行m次合并，若假設(shè)每次合并都是將含成員多的根結(jié)點(diǎn)指向含成員少的根結(jié)點(diǎn)，則最后得到的集合樹的深度為n，而樹的深度與查找有關(guān)。這樣全部操作的時(shí)間復(fù)雜性可估計(jì)為O(mn)。

一般有下述四種策略。2023/2/20第一種策略：

按照輸入序偶對的順序順次合并。即將序偶對的第一個(gè)元素所在的樹作為序偶第二個(gè)元素所在樹的根結(jié)點(diǎn)的一棵子樹，或?qū)⑿蚺紝Φ牡诙€(gè)元素所在的樹作為序偶第一個(gè)元素所在樹的根結(jié)點(diǎn)的一棵子樹。

2023/2/20第二種策略：

按照規(guī)模合并。即根據(jù)樹中元素的個(gè)數(shù)確定合并的方式，如果序偶對的第一個(gè)元素所在的樹的元素個(gè)數(shù)不小于序偶第二個(gè)元素所在樹的元素個(gè)數(shù)，則將序偶對的第二個(gè)元素所在的樹作為序偶第一個(gè)元素所在樹的根結(jié)點(diǎn)的一棵子樹；否則將序偶對的第一個(gè)元素所在的樹作為序偶第二個(gè)元素所在樹的根