數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用new

1、PASCAL語(yǔ)言教程第七章數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用數(shù)字，字符，聲音，圖像，表格等信息，均可輸入計(jì)算機(jī)中進(jìn)行處理。在計(jì)算機(jī)科學(xué)中，象這種能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的信息，都可稱為數(shù)據(jù)。 數(shù)據(jù)的基本單位是數(shù)據(jù)元素。數(shù)據(jù)之間存在有線性與非線性兩種基本的邏輯結(jié)構(gòu)，同時(shí)在存儲(chǔ)結(jié)構(gòu)上還有順序和鏈?zhǔn)街帧?數(shù)據(jù)結(jié)構(gòu)則是研究數(shù)據(jù)元素的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)和與之有關(guān)的各種基本操作的一門學(xué)科。作為一個(gè)程序設(shè)計(jì)者，應(yīng)當(dāng)掌握好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識(shí)，在解題時(shí)針對(duì)問題的特點(diǎn)，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，并構(gòu)造算法，編出優(yōu)美高效的好程序。 本章將介紹一些線性的數(shù)據(jù)結(jié)構(gòu)及其基本操作。第一節(jié)線性表“線性表”是指由有限多個(gè)類型相同的數(shù)據(jù)元素

2、組成的集合，它有以下的特點(diǎn)：(1)有唯一的頭結(jié)點(diǎn)(即第一個(gè)數(shù)據(jù)元素)和尾結(jié)點(diǎn)(即最后一個(gè)數(shù)據(jù)元素)；(2)除結(jié)點(diǎn)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)；(3)除尾結(jié)點(diǎn)外，集合中的每一個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。“線性表”是一種運(yùn)用非常廣范的數(shù)據(jù)結(jié)構(gòu)。例一、某旅館有100個(gè)房間，以1到100編號(hào)，第一個(gè)服務(wù)員來(lái)了，他將所有的房門都打開，第二個(gè)服務(wù)員再把所有編號(hào)是2的倍數(shù)的房門都關(guān)上，第三個(gè)服務(wù)員對(duì)編號(hào)是3的倍數(shù)的房門原來(lái)開的關(guān)上，原來(lái)關(guān)上的打開，此后的第四，五.服務(wù)員均照此辦理。問第100個(gè)服務(wù)員走進(jìn)后，有哪幾扇門是開著的。解：Pascal程序：Program lt7_1_1；uses crt；v

3、ar door：array1.100 of boolean； 1到100號(hào)房門狀態(tài)，false-關(guān)，true-開 i，j：integer；begin clrscr； fillchar(door，sizeof(door)，true)； 第一個(gè)服務(wù)員打開全部房門 for i：=2 to 100 do i表示服務(wù)員號(hào)碼 for j：=1 to 100 div i do doori*j：=not doori*j； 對(duì)房號(hào)為i的倍數(shù)的房門進(jìn)行相反處理 write(The code of opening door is ： )； for i：=1 to 100 do if doori then write

4、(i， )；end.分析：(1)這里用door1.100來(lái)存儲(chǔ)1到100號(hào)房門的開關(guān)狀態(tài)，即是一種線性表，其中：door1可以看成是頭結(jié)點(diǎn)，而door100是尾結(jié)點(diǎn)；同時(shí)由于數(shù)組在內(nèi)存中是按順序占有一片連續(xù)的內(nèi)存空間，因此這種存儲(chǔ)結(jié)構(gòu)即是順序存儲(chǔ)結(jié)構(gòu)。 (2)這里用布爾變量true和false分別表示開和關(guān)兩種狀態(tài)，對(duì)某一房門進(jìn)行相反處理時(shí)只要取反(not)即可，比如：若door10為false，not door10則為true。例二、插入排序：在一個(gè)文本文件中存放的N個(gè)人的姓名，文本文件的格式為：第一行為N，以下第二至第N+1行分別是N個(gè)人的姓名(姓名不重復(fù)，由英文字母組成，長(zhǎng)度不超過10)

5、，請(qǐng)編一個(gè)程序，將這些姓名按字典順序排列。解：Pascal程序：Program lt7_1_2；uses crt；type point=people； 定義結(jié)點(diǎn)類型 people=record name：string10； name-數(shù)據(jù)域，存放姓名 next：point； next-指針域，存放后繼結(jié)點(diǎn)的地址 end；var head：point； n：integer；procedure init； 初始化 begin new(head)；head.next：=nil； 定義頭結(jié)點(diǎn)，初始鏈表為空 end；procedure insert(p：point)； 將P指向的結(jié)點(diǎn)插入以head開頭的

6、線性表中 var q1，q2：point； begin if head.next=nil then head.next：=p 將P指向的結(jié)點(diǎn)插入空鏈表 else begin q1：=head；q2：=q1.next； while (q2nil) and () do begin q1：=q2；q2：=q1.next； end； 查找結(jié)點(diǎn)p應(yīng)插入的位置 q1.next：=p；p.next：=q2；將p插入q1之后q2之前 end； end；procedure work； var i：integer； fn：string； f：text； p：point； begin wr

7、ite(Filename：)；readln(fn)； assign(f，fn)；reset(f)； readln(f，n)； for i：=1 to n do begin new(p)；p.next：=nil； readln(f，)； insert(p)； end； end；procedure print； 打印 var p：point； begin p：=head.next； while pnil do begin writeln()； p：=p.next； end； end；begin clrscr； init； work； print；end.分析：(1)排序有多

8、種方法，插入排序是其中的一種，其原理同摸撲克牌類似：摸到一張牌，把它按大小順序插入牌中，每一張都如此處理，摸完后，得到的就是一副有序的撲克牌。本題可以用插入排序求解； (2)為了減少移動(dòng)數(shù)據(jù)的工作，可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。每個(gè)結(jié)點(diǎn)由兩個(gè)域構(gòu)成，數(shù)據(jù)域(用來(lái)存放姓名)和指針域(用來(lái)存放后繼結(jié)點(diǎn)的地址)。如圖A是將1，3，6，7按順序構(gòu)成一個(gè)線性鏈表的示意圖。這樣在這個(gè)有序表中插入一個(gè)5時(shí)，只需對(duì)指針進(jìn)行相應(yīng)地操作即可，如下圖B： 頭結(jié)點(diǎn)1 -3 -6 -7 尾結(jié)點(diǎn) 圖 A 頭結(jié)點(diǎn)1 -3 6 -7 尾結(jié)點(diǎn) 5 插入的結(jié)點(diǎn) 圖 B練習(xí)一1、求1987乘冪的尾數(shù)： M和N是自然數(shù)，NM=1，而1987

9、M與1987N的末三位數(shù)相同，求最小的M和N。分析：(1)本題只須記錄1987的乘冪的末三位數(shù)，故不必高精度計(jì)算；(2)用數(shù)組a1.n存儲(chǔ)1987的1至n次冪的末三位數(shù)；(3)n的初始值為2，計(jì)算1987的n次冪的末三位數(shù)，并和1987的1至n-1次冪進(jìn)行比較，若無(wú)相等的，則n=n+1，重復(fù)(3)；否則，第一次找到相等的，即是所求的m，n值。2、一個(gè)特殊的數(shù)列： 寫出兩個(gè)1，然后在它們中間插入2成為121，下一步是在任意兩個(gè)相鄰的和數(shù)為4的數(shù)之間插入3，成為13231；再下一步又在任意兩個(gè)相鄰的和數(shù)為4的數(shù)之間插入4，成為1432341，.，由鍵盤輸入N(1=N=9)，求出用上面方法構(gòu)造出來(lái)的

10、序列，其最后插入的數(shù)為N。分析：字符串也可以看做是一個(gè)特殊的線性表，本題初始串是11，對(duì)應(yīng)N=1時(shí)的情況；然后在串中尋找相應(yīng)的位置，依次插入2，3，.，K。3、求序列的第300項(xiàng)： 把所有3的方冪及互不相等的3的方冪和排列成一個(gè)遞增序列：1，3，4，9，10，12，13，.，求這個(gè)序列的第300項(xiàng)。分析：本題可以用一個(gè)線性表來(lái)記錄這個(gè)遞增的序列，通過遞推可以將整個(gè)序列構(gòu)造出來(lái)。方法如下： (1)數(shù)組a存放線性表，t為尾指針，b存放3的冪，初始時(shí)t=1，b=1； (2)將b放入表尾，尾指針加1；atb；tt+1； (3)將b依次與1至t-1的元素相加，按順序放入表尾； (4)重復(fù)(2)，(3)，

11、直至第300項(xiàng)放入表中。4、約瑟夫環(huán)(Joseph) 編號(hào)為1，2，.，N的N個(gè)人按順時(shí)針方向圍成一圈，每人持有一個(gè)密碼(正整數(shù))。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值M，從第一個(gè)人開始按順時(shí)針方向自1開始報(bào)數(shù)，報(bào)到M時(shí)停止，報(bào)M的人出列，將他的密碼作為新的M值，從他在順時(shí)針方向上的第一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有有人全部出列為止。試設(shè)計(jì)一個(gè)程序求出列的順序。分析：這是一個(gè)數(shù)學(xué)游戲。N個(gè)人圍成一圈，依次報(bào)數(shù)，可以用一個(gè)循環(huán)鏈表模擬這一過程。將鏈表的表尾指向表頭，即形成循環(huán)鏈表。從某個(gè)人開始報(bào)數(shù)，報(bào)到M的人出列，也就是在在循環(huán)鏈表中刪除相應(yīng)的結(jié)點(diǎn)，然后依次刪除完所有的結(jié)點(diǎn)，此時(shí)鏈表為空

12、，頭指針與尾指針相等。在具體操作中，要注意刪除頭結(jié)點(diǎn)和尾結(jié)點(diǎn)時(shí)指針的處理，謹(jǐn)防出錯(cuò)。5、多項(xiàng)式的加法：試編程完成兩個(gè)一元多項(xiàng)式的加法。分析：大家都知道，兩個(gè)一元多項(xiàng)式相加實(shí)際上就是合并同類項(xiàng)，最后結(jié)果一般要求按字母的升冪或降冪排列，比如：(2X10+4X+1)+(3X5-4X+2)=2X10+3X5+3。那么一元多項(xiàng)式在計(jì)算機(jī)中如何表示呢?為了節(jié)省空間，一個(gè)元多項(xiàng)式一般用一個(gè)線性表表示，線性表的每一個(gè)結(jié)點(diǎn)包括兩個(gè)域：一個(gè)用來(lái)存放系數(shù)，一個(gè)用來(lái)存放指數(shù)，比如，上面相加的兩個(gè)一元多項(xiàng)式可以分別表示為： 2 10 4 1 1 0 3 5 -41 2 0 這樣兩個(gè)一元多項(xiàng)式相加就可以看成是歸并兩個(gè)鏈表

13、。第二節(jié)隊(duì)列 在日常生活中有許多“隊(duì)列“的例子，如車站售票口買票的隊(duì)伍，排在前面的人先買到票離開隊(duì)伍，后來(lái)的人則加入隊(duì)伍的末尾等候買票；其特點(diǎn)是“先進(jìn)先出”(First In First Out)或“后進(jìn)后出”(Last In Last Out)。 “隊(duì)列”是在一端插入，另一端刪除的特殊的線性表。進(jìn)行刪除的一端稱為“隊(duì)首”，進(jìn)行插入的一端稱為“隊(duì)尾”(如下圖)；插入也叫入隊(duì)，刪除則叫出隊(duì)；在對(duì)隊(duì)列進(jìn)行操作時(shí)，一定要注意一頭一尾。 出隊(duì) a1 a2 . an 入隊(duì) 隊(duì)頭 隊(duì)尾例1、有N張牌，記為1，2，.，N，應(yīng)當(dāng)怎樣排放，才能使：打開第一張是1，然后報(bào)兩張依次放在末尾；打開上面一張，剛好是2，

14、再依次打開上面一張，剛好是3；如此繼續(xù)下去，直至打開最后一張是N。寫一個(gè)程序解決這個(gè)問題。解：Pascal程序：Program lt7_2_1；uses crt；var a，b：array1.1000 of integer； i，j，t，h，n：integer；begin clrscr； write(N=)；readln(n)； for i：=1 to n do ai：=i； a1：=1；h：=2；t：=n；b1：=1； for i：=2 to n do begin for j：=1 to i do begin inc(t)；at：=ah；inc(h)； end； bah：=i；inc(h)；

15、 end； for i：=1 to n do write(bi：5)；end.分析：這是一個(gè)典型隊(duì)列的例子，請(qǐng)大家仔細(xì)體會(huì)在隊(duì)列操作過程中頭指針和尾指針的變化。例2、集合的前N個(gè)元素：編一個(gè)程序，按遞增次序生成集合M的最小的N個(gè)數(shù)，M的定義如下： (1)數(shù)1屬于M； (2)如果X屬于M，則Y=2*X+1和Z=3*1也屬于M； (3)此外再?zèng)]有別的數(shù)屬于M。解：Pascal程序：Program lt7_2_1；uses crt；var a，b：array1.1000 of integer； x，ha，hb，t，total，n：integer；begin clrscr； write(N=)；rea

16、dln(n)； x：=1；a1：=1； ha：=1；hb：=1；t：=0；total：=1； while totalbhb then begin x：=bhb；inc(hb)； end else begin x：=aha； if aha=bhb then inc(hb)； inc(ha)； end； inc(total)； end；end.分析：可以用兩個(gè)隊(duì)列來(lái)存放Y和Z中的數(shù)，分別用數(shù)組a和數(shù)組b存放。然后遞推求出第N項(xiàng)，方法如下： (1)令ha和hb分別為隊(duì)列a和隊(duì)列b的頭指針，它們的尾指針為t。初始時(shí)，X=1，ha=hb=t=1； (2)將2*x+1和3*x+1分別放入隊(duì)列a和隊(duì)列b的隊(duì)

17、尾，尾指針加1。即： at2*x+1，bt3*x+1，tt+1； (3)將隊(duì)列a和隊(duì)列b的頭結(jié)點(diǎn)進(jìn)行比較，可能有三種情況： (A)ahabhb (B)aha=bhb (C)aha0) or (hb0) do begin if ha0 then x：=ord(aha)-48 else x：=0； if hb0 then y：=ord(bhb)-48 else y：=0； mlm：=x+y+c； c：=mlm div 10； mlm：=mlm mod 10； inc(lm)；dec(ha)；dec(hb)； end； if c0 then mlm：=c else dec(lm)； write(a，

18、+，b，=)； for i：=lm downto 1 do write(mi)；end.2、基數(shù)排序： 將278，109，063，930，589，184，505，269，008，083利用基數(shù)排序法按從小到大的順序排列。分析：基數(shù)排序法是一種基于對(duì)關(guān)鍵字進(jìn)行分配和收集的排序法，常用最低位優(yōu)先法(Least Significant Digit first)，簡(jiǎn)稱LSD法。它先從最低位的關(guān)鍵字開始進(jìn)行排序，然后對(duì)次低位關(guān)鍵字進(jìn)行排序，依此類推，直到對(duì)最高位進(jìn)行排序?yàn)橹埂＠绫绢}，關(guān)鍵字是各位上的數(shù)碼，從0到9共10個(gè)。首先，將需要排序的數(shù)放在隊(duì)列A中，如圖：3、有1至2N的自然數(shù)，按從小到大的順序

19、排成一列，對(duì)這2N個(gè)數(shù)進(jìn)行如下操作： （1）將這2N個(gè)數(shù)等分成A，B兩組，即： A組：1，2，.，N； B組：N+1，N+2，.，2N （2）輪流從A，B兩組中按順序取數(shù)： 1，N+1，2，N+1，.，N，2N （3）再將取過的數(shù)等分為兩組，并重復(fù)上述操作，直到這2N個(gè)數(shù)又按從小到大的順序排好為止。 例如：當(dāng)N=3時(shí)，操作如下： 初始序列為：1，2，3，4，5，6 (1) 1，4，2，5，3，6 (2) 1，5，4，3，2，6 (3) 1，3，5，2，4，6 (4) 1，2，3，4，5，6分析：將1至2N的自然數(shù)分成兩組，用兩個(gè)隊(duì)列來(lái)模擬上述過程即可。4、有一個(gè)數(shù)，它的末位數(shù)字是N，將N移到這

20、個(gè)數(shù)的首位，得到的新數(shù)恰好是原數(shù)的N倍，現(xiàn)輸入N的值，求滿足條件的最小的數(shù)。第三節(jié)棧 “?！笔且环N先進(jìn)后出(First In Last Out)或后進(jìn)先出(Last In First Out)的數(shù)據(jù)結(jié)構(gòu)。日常生活中也常能見到它的實(shí)例，如壓入彈夾的子彈，最先壓進(jìn)去的子彈最后射出，而最后壓入的子彈則最先發(fā)射出來(lái)。 “?！笔且环N只能在一端進(jìn)行插入和刪除的特殊的線性表，進(jìn)行插入和刪除的一端稱為“棧頂”，而不動(dòng)的一端稱為棧底(如下圖)。插入的操作也稱為進(jìn)棧(PUSH)，刪除的操作也稱為出棧(POP)。 出棧 進(jìn)棧 棧頂 an . a2 棧底 a1 例1、算術(shù)表達(dá)式的處理：由鍵盤輸入一個(gè)算術(shù)表達(dá)式(含有+

21、，-，*，/，(，)運(yùn)算)，且運(yùn)算結(jié)果為整數(shù))，編一程序求該算術(shù)表達(dá)式的值。分析：表達(dá)式的運(yùn)算是程序設(shè)計(jì)中一個(gè)基本的問題，利用棧求解是一種簡(jiǎn)單易行的方法，下面介紹的是算符優(yōu)先法。 比如：4+2*3-10/5 我們都知道，四則運(yùn)算的法則是：(1)先乘除后加減，同級(jí)運(yùn)算從左到右；(2)有括號(hào)先算括號(hào)。 因此上例的結(jié)果是8。 算符優(yōu)先法需要兩個(gè)棧：一個(gè)是操作數(shù)棧，用來(lái)存放操作數(shù)，記為SN；另一個(gè)是操作符棧用來(lái)存放運(yùn)算符，記為SP。具體處理方法如下： (1)將SN，SP置為空棧； (2)從左開始掃描表達(dá)式，若是操作數(shù)壓入SN中；若是操作符則與SP的棧頂操作符比較優(yōu)先級(jí)有兩種可能： （a）優(yōu)先級(jí)小于棧頂

22、算符，此時(shí)從SN中彈出兩個(gè)操作數(shù)，從SP彈出一個(gè)操作符，實(shí)施運(yùn)算，結(jié)果壓入SN的棧頂。 （b）優(yōu)先級(jí)大于棧頂算符，此時(shí)將操作符壓入SP中。 (3)重復(fù)操作(2)直至表達(dá)式掃描完畢，這時(shí)SP應(yīng)為空棧，而SN只有一個(gè)操作數(shù)，即為最后的結(jié)果。 為了方便起見，可以將#作為表達(dá)式的結(jié)束標(biāo)志，初始化時(shí)在SP的棧底壓入#，并將其優(yōu)先級(jí)規(guī)定為最低。下面給出的是計(jì)算4+2*3-10/5#的示意圖步驟 SN SP 讀入字符 說(shuō)明1 空 # 4 將4壓入SN2 4 # + 將+壓入SP3 4 # + 2 將2壓入SN4 4 2 # + * 將*壓入SP5 4 2 # + * 3 將3壓入SN6 4 2 3 # +

23、* - -的優(yōu)先級(jí)小于*，因此將SN中的3，2彈出， 將SP中的*彈出，將2*3的結(jié)果壓入SN中7 4 6 # + - -的優(yōu)先級(jí)小于其左邊的+，因此將SN中的 4，6彈出，將SP中的+彈出，將4+6的結(jié)果壓 入SN中8 10 # - -壓入SP中9 10 # - 10 10壓入SN中10 10 10 # - / 將/壓入SP中11 10 10 # - / 5 將5壓入SN中12 10 10 5 # - / # #優(yōu)先級(jí)小于/，故SN中的10，5彈出，SP中 的/彈出，將10/5的結(jié)果壓入SN中13 10 2 # - # #優(yōu)先級(jí)小于-，故SN中的10，2彈出，SP中 的-彈出，將10-2的結(jié)

24、果壓入SN中14 8 # # #與#相遇，運(yùn)算結(jié)束，SN中的8是最后計(jì)算 的結(jié)果解：Pascal程序：Program lt7_3_1；uses crt；const number：set of char=0.9； op：set of char=+，-，*，/，(，)；var expr：string； sp：array1.100 of char； sn：array1.100 of integer； t，tp，n，tn：integer；function can_cal(ch：char)：boolean； begin if (ch=#) or (ch=) or (sptp in *，/) and (c

25、h in +，-) then can_cal：=true else can_cal：=false； end；procedure cal； begin case sptp of +：sntn-1：=sntn-1+sntn； -：sntn-1：=sntn-1-sntn； *：sntn-1：=sntn-1*sntn； /：sntn-1：=sntn-1 div sntn； end； dec(tn)；dec(tp)； end；begin clrscr； write(Expression ： )；readln(expr)； write(expr+=)； expr：=expr+#； tn：=0；tp：=1；

26、sp1：=#；t：=1； repeat if exprt in number then begin n：=0； repeat n：=n*10+ord(exprt)-48； inc(t)； until not (exprt in number)； inc(tn)；sntn：=n； end else begin if (exprt=() or not can_cal(exprt) then begin inc(tp)；sptp：=exprt；inc(t)； end else if exprt=) then begin while sptp( do cal； dec(tp)；inc(t)； end else cal； end； until (exprt=#) and (sptp=#)； writeln(sn1)；end.練習(xí)三1、假設(shè)一個(gè)算術(shù)表達(dá)式中可包含三種括號(hào)：圓括號(hào)“(”和“)”；方括號(hào)“”和“”以及花括號(hào)“”和“”，且這三種括號(hào)可按任意的次序嵌套使用，試?yán)脳５倪\(yùn)算，判別給定的表達(dá)式中所含括號(hào)是否正確配對(duì)出現(xiàn)。分析：如果括號(hào)只有一種，比如說(shuō)是“(”和“)”，則判斷是否正確匹配可以這樣進(jìn)行：用一個(gè)計(jì)數(shù)器T來(lái)記錄左括號(hào)與右括號(hào)比較的情況，初始時(shí)T=0，表達(dá)式從左向右掃描，如果遇到左括號(hào)則TT+1，遇到右括號(hào)則TT