數(shù)據(jù)與結(jié)構(gòu)第二課時(shí) 課件-2023-2024學(xué)年高中信息技術(shù)教科版（2019）必修1

1、下列選項(xiàng)不屬于Python語(yǔ)言中的數(shù)據(jù)類型是（

）A.整數(shù) B.列表 C.數(shù)組 D.字典2、下列選項(xiàng)屬于Python語(yǔ)言中的簡(jiǎn)單數(shù)據(jù)類型是（

）A.布爾 B.元組 C.列表 D.數(shù)組知識(shí)回顧C(jī)A3.2數(shù)據(jù)與結(jié)構(gòu)（二）項(xiàng)目：網(wǎng)絡(luò)購(gòu)物數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是存在特定關(guān)系的數(shù)據(jù)元素的集合。在解決有些問(wèn)題時(shí)，一些相關(guān)聯(lián)的數(shù)據(jù)集中在一起，形成一個(gè)數(shù)據(jù)的集合，這種集合能夠單獨(dú)或作為一個(gè)整體被訪問(wèn)和處理。線性數(shù)據(jù)結(jié)構(gòu)線性數(shù)據(jù)結(jié)構(gòu)又稱為線性表。當(dāng)前元素前驅(qū)元素后繼元素在線性數(shù)據(jù)結(jié)構(gòu)中，除首元素沒(méi)有前趨元素、尾元素沒(méi)有后繼元素外，其他元素都只有一個(gè)前趨元素和一個(gè)后繼元素。隊(duì)列隊(duì)列是一種有限制的線性結(jié)構(gòu)，它的數(shù)據(jù)元素只能在一端一次添加(進(jìn)隊(duì))，在另一端依次刪除(出隊(duì))。alphabat=[“A”，“B”，“C”，“D”，“E”，“F”，“G”，“H”]例如:結(jié)尾添加字母“I”:alphabat.append(“I”)；刪除首字母“A”:alphabat.pop(0)ABCDEFGH我們可以通過(guò)對(duì)應(yīng)的方法對(duì)列表進(jìn)行操作:pop(0)方法可以刪除列表的首元素，append方法可以在列表尾部添加一個(gè)數(shù)據(jù);活動(dòng)1了解快遞派送路線

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

“G”),(“H”，“I”,“J”)]Print（list[2][1]）霍城縣第二中學(xué)語(yǔ)文教研組數(shù)學(xué)教研組英語(yǔ)教研組物理教研組生化教研組政史地教研組信息技術(shù)教研組音體美教研組高二年級(jí)部高一年級(jí)部高三年級(jí)部宿管部食堂管理教務(wù)處教研室德育處平安辦后勤財(cái)務(wù)室霍城縣第二中學(xué)組織構(gòu)架樹行政劃區(qū)構(gòu)架樹活動(dòng)2了解物流網(wǎng)絡(luò)

由于需要綜合考慮運(yùn)營(yíng)成本，商品在城市間運(yùn)輸?shù)穆肪€是需要計(jì)算和規(guī)劃的。請(qǐng)你查看圖3.2.5中的物流過(guò)程，嘗試用圓圈表示城市，用線段表示城市之間的送達(dá)關(guān)系，將圖3.2.6補(bǔ)充完整，了解商品配送的路線特點(diǎn)。岳陽(yáng)市南通市揚(yáng)州市3.2.3物流數(shù)據(jù)圖形化示意圖：長(zhǎng)沙南京泰州圖結(jié)構(gòu)

圖結(jié)構(gòu)是由一組節(jié)點(diǎn)(稱為項(xiàng)點(diǎn))和一組節(jié)點(diǎn)問(wèn)的連線(稱為邊或弧)構(gòu)成的一種數(shù)據(jù)結(jié)構(gòu)。圖結(jié)構(gòu)中的每個(gè)頂點(diǎn)都可以與其他頂點(diǎn)有邊相連，圖結(jié)構(gòu)中數(shù)據(jù)元素之間是多對(duì)多的關(guān)系。123548796標(biāo)為“1”的頂點(diǎn)與兩條邊相連，頂點(diǎn)“4”與“2”，“8”，“9”相連。圖結(jié)構(gòu)應(yīng)用——網(wǎng)絡(luò)管理系統(tǒng)流程圖圖結(jié)構(gòu)的應(yīng)用——運(yùn)輸?shù)缆?/p>

在物流網(wǎng)絡(luò)中，分撥中心、配送中心、貨物需求點(diǎn)等可以抽象為圖的頂點(diǎn)，城市道路、各級(jí)鐵路等可以抽象為圖的邊，如城市以及城市之間的運(yùn)輸?shù)缆肪褪菆D結(jié)構(gòu)。利用圖結(jié)構(gòu)，我們還可以解決物流中的許多問(wèn)題，如道路網(wǎng)絡(luò)分析、車輛運(yùn)營(yíng)安排等。南京大學(xué)理工學(xué)院地圖圖結(jié)構(gòu)的應(yīng)用——校園地圖中國(guó)高鐵地圖圖結(jié)構(gòu)的應(yīng)用——高鐵地圖活動(dòng)3規(guī)劃取快遞最快路線

某同學(xué)網(wǎng)購(gòu)的書已經(jīng)到達(dá)家附近的快遞門店，需要他自己去取。不巧的是，這次購(gòu)買的三本書是三個(gè)不同的物流公司派送的，他家與各快遞門店的位置如右圖所示地點(diǎn)——地點(diǎn)時(shí)間/分家——快遞門店A2家——快遞門店B5家——快遞門店C10快遞門店A——快遞門店B4快遞門店A——快遞門店C6快遞門店B——快遞門店C4該同學(xué)估算了在這些地點(diǎn)之間步行需要的時(shí)間，詳見表3.2.2.快遞門店B快遞門店A快遞門店C家活動(dòng)3規(guī)劃取快遞最快路線

請(qǐng)你幫他規(guī)劃最省時(shí)的路線，然后設(shè)計(jì)算法解決問(wèn)題并在下框中描述你的算法。

從起點(diǎn)出發(fā)，把當(dāng)前可以到達(dá)的下一個(gè)位置列舉出來(lái)，再?gòu)牧信e出的新位置出發(fā)，繼續(xù)列舉下一步可以到達(dá)。地點(diǎn)——地點(diǎn)時(shí)間/分家——快遞門店A2家——快遞門店B5家——快遞門店C10快遞門店A——快遞門店B4快遞門店A——快遞門店C6快遞門店B——快遞門店C4家快遞門店C快遞門店A快遞門店BPython中的復(fù)合數(shù)據(jù)類型我們發(fā)現(xiàn)分析過(guò)程的圖形是樹結(jié)構(gòu)，樹中的節(jié)點(diǎn)表示當(dāng)前所在的位置,邊表示選擇的線路。利用樹結(jié)構(gòu)，我們能夠更清晰地實(shí)現(xiàn)不重復(fù)、不遺漏地列舉所有做法,更利千通過(guò)比較得到最優(yōu)解。分析隊(duì)列、樹、圖三種結(jié)構(gòu)的區(qū)別結(jié)構(gòu)類型數(shù)據(jù)（節(jié)點(diǎn)）之間的關(guān)系生活中相應(yīng)結(jié)構(gòu)應(yīng)用舉例隊(duì)列（線性）樹圖一對(duì)一排隊(duì)一對(duì)多行政區(qū)劃、書本目錄結(jié)構(gòu)多對(duì)多全國(guó)航運(yùn)圖、鐵路運(yùn)輸、電話網(wǎng)絡(luò)、互聯(lián)網(wǎng)等小結(jié)數(shù)據(jù)與結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)舉例集合結(jié)構(gòu)線性結(jié)構(gòu)（隊(duì)列）樹結(jié)構(gòu)圖結(jié)構(gòu)線性結(jié)構(gòu)：排隊(duì)樹結(jié)構(gòu)：行政區(qū)劃圖結(jié)構(gòu)：交通運(yùn)輸課堂練習(xí)1、樹結(jié)構(gòu)是存在特定（

）的數(shù)據(jù)元素的集合。2、隊(duì)列的插入操作是在（

）3、樹最適用于組織什么關(guān)系的非線性結(jié)構(gòu)？（

）A.結(jié)構(gòu) B.關(guān)系 C.運(yùn)算 D.算法BA.隊(duì)尾

B.隊(duì)首 C.隊(duì)列任意位置 D.隊(duì)列中間位置AA.有序的 B.分層次的 C.無(wú)序的 D.無(wú)關(guān)系的B課堂練習(xí)4、一個(gè)隊(duì)列的出隊(duì)順序是4,3,2,1，則隊(duì)列入隊(duì)序列是（

）。5、中國(guó)圖書館圖書分類法將所有學(xué)科的圖書按其學(xué)科內(nèi)容分成幾個(gè)大類，每一大類下又許多小類，每一小類下再細(xì)分子小類。最后，每一種書都可以分到某一類目下，每一個(gè)都有一個(gè)類號(hào)。下列哪種數(shù)據(jù)結(jié)構(gòu)適合處理這種數(shù)據(jù)關(guān)系?( )A.線性表 B.隊(duì)列 C.樹結(jié)構(gòu) D.圖結(jié)構(gòu)A.1,2,3,4 B.4,3,2,1 C.1,3,2,4 D.3,4,1,2BC課堂練習(xí)判斷題1.線性表中的數(shù)據(jù)元素之間是一對(duì)多的關(guān)系。( )2.在隊(duì)列中，只能在一端依次添加數(shù)據(jù)元素，在另一端依次刪除數(shù)據(jù)元素。( )3.在Python語(yǔ)言中，列表和字符串屬于復(fù)合數(shù)據(jù)類型。( )4.在樹結(jié)構(gòu)中，一棵樹可以有多個(gè)根節(jié)點(diǎn)。( )5.