高中信息技術(shù)教科版必修1課件3-2數(shù)據(jù)與結(jié)構(gòu)（第二課時）

數(shù)據(jù)與結(jié)構(gòu)第二課時第3單元3.2學(xué)習(xí)目標(biāo)★了解樹、圖結(jié)構(gòu)的基本概念及其特點?！锔鶕?jù)數(shù)據(jù)結(jié)構(gòu)的特點，會選用合適的數(shù)據(jù)結(jié)構(gòu)組織數(shù)據(jù)解決簡單的問題?！窘虒W(xué)重點】數(shù)據(jù)結(jié)構(gòu)中的樹結(jié)構(gòu)和圖結(jié)構(gòu)?！窘虒W(xué)難點】數(shù)據(jù)結(jié)構(gòu)中的樹結(jié)構(gòu)和圖結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是存在特定關(guān)系的數(shù)據(jù)元素的集合。在解決有些問題時，些相關(guān)聯(lián)的數(shù)據(jù)將集中在一起，形成一個數(shù)據(jù)的集合，這種集合能夠單獨或作為一個整休被訪問和處理。線性數(shù)據(jù)結(jié)構(gòu)又稱為線性表。在線性數(shù)據(jù)結(jié)構(gòu)中，除首元素沒有前趨元素、尾元素沒有后繼元素外，其他元素都只有個后繼元素。數(shù)據(jù)結(jié)構(gòu)線性數(shù)據(jù)結(jié)構(gòu)隊列隊列是一種有限制的線性結(jié)構(gòu)，它的數(shù)據(jù)元素只能在一端一次添加（進(jìn)隊），在另一端依次刪除（出隊）。ABCDEHGFalphabat=[A，B，C，D，E，F(xiàn)，G，H]我們可以通過對應(yīng)的方法對列表進(jìn)行操作：pop(0)方法可以刪除列表的首元素，append方法可以在列表尾部添加一個數(shù)據(jù);例如：結(jié)尾添加字母“I”：alphabat.append(“I”)；刪除首字母“A”：alphabat.pop(0)活動1

了解快遞派送線路每個快遞員只負(fù)責(zé)固定的派送范圍，他們從快件派送點領(lǐng)取快件后，分別送往各自負(fù)責(zé)的快件領(lǐng)取點（比如小區(qū)門衛(wèi)處、單位門衛(wèi)處）或者具體用戶。樹結(jié)構(gòu)樹結(jié)構(gòu)是一種具有層次關(guān)系的非線性結(jié)構(gòu)。樹是由n(n≥0)個節(jié)點組成的有限集合。若n=0,則稱為空樹。任何一個非空樹均滿足以下兩個條件：（1）僅有一個稱為根的節(jié)點；（2）當(dāng)n>0時，其余節(jié)點可分為m(m≥0)個互不相交的有限集合，其中每個集合又是一棵樹，并稱為根的子樹。1.A是B，C，D的根節(jié)點，B，C，D是A的子樹；2.B是E，F(xiàn)，G的根節(jié)點，E，F(xiàn)，G是B的子樹；樹結(jié)構(gòu)的特點樹根結(jié)點（簡稱“根結(jié)點”):每一個非空樹都有且只有一個被稱為根的結(jié)點。右下圖中，結(jié)點A就是整棵樹的根結(jié)點。樹根的判斷依據(jù)為:如果一個結(jié)點沒有父結(jié)點，那么這個結(jié)點就是整棵樹的根結(jié)點。如何創(chuàng)建圖結(jié)構(gòu)的數(shù)據(jù)？葉子結(jié)點:如果結(jié)點沒有任何子結(jié)點，那么此結(jié)點稱為葉子結(jié)點（葉結(jié)點）。例如下右圖中，結(jié)點K、L、F、G、M、I、J都是這棵樹的葉子結(jié)點。練一練創(chuàng)建圖結(jié)構(gòu)的數(shù)據(jù)：ABDCEKGFHIJLMlist=[“A”]……………list=[(“B”,“C”,“D”)]…………list=[(“E”.“F”），(“G”),(“H”,“I”,“J”)]打印字母“G”怎么辦？Print（list[1][0]）活動1

了解物流網(wǎng)絡(luò)由于需要綜合考慮運營成本，商品在城市間運輸?shù)穆肪€是需要計算和規(guī)劃的。請你查看圖中的物流過程，嘗試用圓圈表示城市，用線段表示城市之間的送達(dá)關(guān)系，將圖補充完整，了解商品配送的路線特點。長沙南京泰州圖結(jié)構(gòu)圖結(jié)構(gòu)是由一組節(jié)點（稱為頂點）和一組節(jié)點間的連線（稱為邊或?。?gòu)成的一種數(shù)據(jù)結(jié)構(gòu)。圖結(jié)構(gòu)中的每個頂點都可以與其他頂點有邊相連，圖結(jié)構(gòu)中數(shù)據(jù)元素之間是多對多的關(guān)系。標(biāo)為“1”的頂點與兩條邊相連，頂點“4”與2“，”8“，"9"相連。圖結(jié)構(gòu)的應(yīng)用場景在物流網(wǎng)絡(luò)中，分撥中心、配送中心、貨物需求點等可以抽象為圖的頂點，城市道路、各級鐵路等可以抽象為圖的邊，如城市以及城市之間的運輸?shù)缆肪褪菆D結(jié)構(gòu)。利用圖結(jié)構(gòu)，我們還可以解決物流中的許多問題，如道路網(wǎng)絡(luò)分析、車輛運營安排等。某同學(xué)網(wǎng)購的書已經(jīng)到達(dá)家附近的快遞門店，需要他自己去取。不巧的是，這次購買的三本書是三個不同的物流公司派送的，他家與各快遞門店的位置如右圖所示?；顒?

規(guī)劃取快遞最快路線該同學(xué)估算了在這些地點之間步行需要的時間，詳見表3.2.2?；顒?

規(guī)劃取快遞最快路線請你幫他規(guī)劃最省時的路線，然后設(shè)計算法解決問題并在下框中描述你的算法。從起點出發(fā)，把當(dāng)前可以到達(dá)的下一個位置列舉出來，再從列舉出的新位置出發(fā)，繼續(xù)列舉下一步可以到達(dá)的位置，以此類推，直到返回起點。Python中的復(fù)合數(shù)據(jù)類型我們發(fā)現(xiàn)分析過程的圖形是樹結(jié)構(gòu)，樹中的節(jié)點表示當(dāng)前所在的位置，邊表示選擇的線路。利用樹結(jié)構(gòu)，我們能夠更清晰地實現(xiàn)不重復(fù)、不遺漏地列舉所有做法，更利千通過比較得到最優(yōu)解。請分析隊列、樹、圖三種結(jié)構(gòu)的區(qū)別，并將結(jié)果填在表中結(jié)構(gòu)類型數(shù)據(jù)（節(jié)點）之間的關(guān)系生活中相應(yīng)結(jié)構(gòu)應(yīng)用舉例隊列（線性）一對一排隊