1、第七天 簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)類型應(yīng)用,二維數(shù)組，隊(duì)列，棧，樹，圖,用計(jì)算機(jī)解決問(wèn)題一般步驟：,具體問(wèn)題,數(shù)學(xué)模型,算法,編程、調(diào)試,得到答案,今天主要內(nèi)容,二維數(shù)組和線性表 隊(duì)列 棧 樹 圖,線性表表示（一）,N個(gè)數(shù)據(jù)元素的有限序列（一般用數(shù)組表示） 存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),20,12345678,線性表表示（二）,鏈?zhǔn)酱鎯?chǔ)（不要求掌握，有興趣可以閱讀指針一章）,L,head,二維數(shù)組,二維數(shù)組的一個(gè)形象比喻 多個(gè)縱隊(duì)形成的方塊 m * n,二維數(shù)組在內(nèi)存的存 儲(chǔ)方式是線性的。1：按照行存儲(chǔ)：即先 存儲(chǔ)第一行然后在存 儲(chǔ)第二行，那么aij的值應(yīng) 該是A11+（i-1)*n+j-1 2:

2、 1：按照列存儲(chǔ)：即先 存儲(chǔ)第一列然后在存 儲(chǔ)第二列，那么aij的值應(yīng) 該是A11+（j-1)*m+i-1 (很好記啊，I,j調(diào)換位置 *的值n-m）,思考：如果數(shù)組的定義為var num:array2.n,2.m，要求AIJ的位置，結(jié)果應(yīng)該是是什么呢！,另外數(shù)組地址計(jì)算問(wèn)題,題目描述：已知N*(N+1) / 2個(gè)數(shù)據(jù)，按行的順序存入數(shù)組b1,b2,中。其中第一個(gè)下標(biāo)表示行，第二個(gè)下標(biāo)表示列。若aij (i=j ,j=1,2,n)存于bk中，問(wèn)：k,i,j之間的關(guān)系如何表示？給定k值，寫出能決定相應(yīng)i,j的算法。, K=i*(i-1)/2+j Read(k); For i:=1 to k do

3、 for j:=1 to i do if k=(trunc(I*(I-1)/2)+j) then writeln(k,對(duì)應(yīng)的i,j為：,i,j),棧,特殊的線性表 操作特點(diǎn)：后進(jìn)先出（Last In First Out） 棧頂表尾 棧底表頭 空棧（top=bottom),A,B,C,D,棧頂指針： 指想下一個(gè)元素的存放位置,棧底指針,棧 （考題分析）,（1998） 棧S初始狀態(tài)為空，現(xiàn)有5個(gè)元素組成的序列1，2，3，4，5，對(duì)該序列在棧S上一次進(jìn)行如下操作（從序列中的1開始，出棧后不再進(jìn)棧）：進(jìn)棧、進(jìn)棧、進(jìn)棧、出棧、進(jìn)棧、出棧、進(jìn)棧。問(wèn)出棧的元素序列是_ (A) 5,4,3,2,1 (B) 2

4、,1 (C) 2,3 (D) 3,4,隊(duì)列,特點(diǎn)：先進(jìn)先出 允許插入的一端稱為隊(duì)尾(rear)，允許刪除的一端稱為隊(duì)頭(front)。,出隊(duì)列,入隊(duì)列,循環(huán)隊(duì)列,REAR,FRONT,現(xiàn)在棧中存放的元素個(gè)數(shù)：(R-F+N) mod N,樹,根、葉子、子樹 結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù) 二叉樹(每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn)的樹）,層次 1 2 3,二叉樹,特點(diǎn)：每個(gè)結(jié)點(diǎn)至多只有二棵子樹，并且二叉樹的子樹有左右之分。 第i層至多有 個(gè)結(jié)點(diǎn)（i=1） 深度為K的二叉樹最多有 個(gè)結(jié)點(diǎn)（K=1）,滿二叉樹,完全二叉樹,二叉樹的遍歷,先（根）序遍歷 中（根）序遍歷 后（根）序遍歷 先（根）序遍歷 ABDFGC

5、EH 中（根）序遍歷 BFDGACHE 后（根）序遍歷 FGDBHECA 若左子樹非空先訪問(wèn)左子樹 訪問(wèn)根節(jié)點(diǎn) 若左子樹非空先訪問(wèn)左子樹,中序遍歷的程序,Procedure (I,j:integer)I表示層數(shù)，j表示第幾個(gè)節(jié)點(diǎn) Begin If in then如果非根節(jié)點(diǎn) begin procedure(i+1,2*i-1);遍歷左子樹 write(aI,j; 遍歷子樹節(jié)點(diǎn) procedure (i+1,2*i); 遍歷右子樹 end； end.;,例題分析,給出一棵二叉樹的中序遍歷：DBGEACHFI 與后序遍歷：DGEBHIFCA ，畫出此二叉樹。,思考過(guò)程 先在后序中找到最后面的節(jié)點(diǎn)A

6、，那我們 知道這棵樹的根目錄是A，A將中序的遍 歷分成兩個(gè)部分前面部分“DBGE”是左子 樹的中序遍歷，后面部分“CHFI”是右子 樹的中序遍列，在后序遍歷中找到這兩個(gè) 字符串中最先出現(xiàn)的字符，那就是左子樹 和右子樹的根節(jié)點(diǎn)，再在中序遍歷中劃分 .,圖,無(wú)向圖,有向圖,圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣,鄰接矩陣（二維數(shù)組）,遍歷是指從圖的某個(gè)點(diǎn)出發(fā)，沿著與之相連的邊訪問(wèn)圖中的每個(gè)一次且僅一次?；痉椒ㄓ袃煞N：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。 深度優(yōu)先和廣度優(yōu)先遍歷，與前面所說(shuō)的樹的深度與廣度優(yōu)先遍歷是類似的：比下圖中，如果從點(diǎn)V1出發(fā)，那么： 深度優(yōu)先遍歷各點(diǎn)的順序?yàn)椋簐1，v2，v4，v7，v5，v3，v6

7、，v8。 廣度優(yōu)先遍歷各點(diǎn)的順序?yàn)椋簐1，v2，v3，v4，v5，v6，v7，v8。,圖的遍歷,學(xué)生練習(xí)題一（2004）,利用今天學(xué)習(xí)的知識(shí)解決下列問(wèn)題 1：二叉樹T，已知其前序遍歷序列為1 2 4 3 5 7 6，中序遍歷序列為4 2 1 5 7 3 6，則其后序遍歷序列為（ ）。 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 1 2：滿二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)為N，則它的結(jié)點(diǎn)總數(shù)為（ ）。 N B. 2 * N C. 2 * N 1 D. 2 * N + 1 E. 2N 1 某個(gè)車站

8、呈狹長(zhǎng)形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從這一時(shí)刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，出”。假設(shè)車輛入站的順序?yàn)?，2，3，則車輛出站的順序?yàn)椋?）。 A：1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7,學(xué)生練習(xí)題二（2004）,3：某大學(xué)計(jì)算機(jī)專業(yè)的必修課及其先修課程如下表所示： 請(qǐng)你判斷下列課程安排方案哪個(gè)是不合理的（ ）。 A. C0, C6, C7, C1, C2, C3, C4, C5 B. C0, C1,

9、 C2, C3, C4, C6, C7, C5 C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3, C4 E. C0, C1, C2, C3, C6, C7, C5, C4,二問(wèn)題求解 （每題5分，共10分）2004,一個(gè)家具公司生產(chǎn)桌子和椅子?，F(xiàn)在有113個(gè)單位的木材。每張桌子要使用20個(gè)單位的木材，售價(jià)是30元；每張椅子要使用16個(gè)單位的木材，售價(jià)是20元。使用已有的木材生產(chǎn)桌椅（不一定要把木材用光），最多可以賣 元錢。 75名兒童到游樂(lè)場(chǎng)去玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西

10、都玩過(guò)，55人至少玩過(guò)其中的兩種。若每樣乘坐一次的費(fèi)用是5元，游樂(lè)場(chǎng)總共收入700，可知有 名兒童沒(méi)有玩過(guò)其中任何一種。,問(wèn)題求解 （每題5分，共10分）2004,編號(hào)為1到13的紙牌順時(shí)針排成一圈，有人從編號(hào)為1的牌從數(shù)字1開始順時(shí)針數(shù)下去，1、2、3、20、21、，一圈又一圈。問(wèn)：當(dāng)數(shù)到數(shù)字N時(shí)，所在紙牌的編號(hào)為多少?,Noip2008相應(yīng)的題目,7設(shè)棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧S，出棧的序列為b，d，f，e，c，a，則棧S的容量至少應(yīng)該是（ ）。 A. 6 B. 5 C. 4 D. 3 完全二叉樹共有2*N-1個(gè)結(jié)點(diǎn)，則它的葉節(jié)點(diǎn)數(shù)是（ ）。 A. N-1 B.

11、 N C. 2*N D. 2N-1 設(shè)A=true，B=false，C=true，D=false，以下邏輯運(yùn)算表達(dá)式值為真的是（ ）。 A. (AB)(CDA) B. (AB)C)D C. (BCD)DA D. A(DC)B 13. 二叉樹T，已知其先根遍歷是1 2 4 3 5 7 6（數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同），中根遍歷是2 4 1 5 7 3 6，則該二叉樹的后根遍歷是（ ）。 A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3 1,Noip2008相應(yīng)的題目,18. 設(shè)T是一棵有n個(gè)頂點(diǎn)的樹，下列說(shuō)法不正確的

12、是（ ）。 A. T有n條邊 B. T是連通的 C. T是無(wú)環(huán)的 D. T有n-1條邊,二問(wèn)題求解（共2題，每題5分，共計(jì)10分）,1. 書架上有4本不同的書A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這4本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有_種。滿足 A必須比C靠左，所有紅皮的書要擺放在一起，所有黑皮的書要擺放在一起，共有_種擺法。 2有6個(gè)城市，任何兩個(gè)城市之間都有一條道路連接，6個(gè)城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為_。,四完善程序,1（字符串替換）給定一個(gè)字符串S（S僅包含大小寫字母），下面的程序?qū)中的每個(gè)字母用規(guī)定的字母替換，并輸出S經(jīng)

13、過(guò)替換后的結(jié)果。程序的輸入是兩個(gè)字符串，第一個(gè)字符串是給定的字符串S，第二個(gè)字符串S由26個(gè)字母組成，它是a-z的任一排列，大小寫不定，S規(guī)定了每個(gè)字母對(duì)應(yīng)的替換字母：S中的第一個(gè)字母是字母A和a的替換字母，即S中的A用該字母的大寫替換，S中的a用該字母的小寫替換；S中的第二個(gè)字母是字母B和b的替換字母，即S中的B用該字母的大寫替換，S中的b用該字母的小寫替換； 以此類推。,var change:string; str:string; procedure CheckChangeRule; var i:integer; begin for i:=1 to 26 do begin if then changei:= chr(ord(changei) - ord(A) + ord(a); end; end; procedure ChangeString; var len,i:integer;