32數(shù)據(jù)與結(jié)構(gòu)（課件）高一上學(xué)期高中信息技術(shù)必修1教科版

第3單元認(rèn)識(shí)數(shù)據(jù)

3.2數(shù)據(jù)與結(jié)構(gòu)授課教師一、數(shù)據(jù)類型【做中悟】活動(dòng)1了解訂單數(shù)據(jù)，填表網(wǎng)站名稱訂單中的數(shù)據(jù)Python中對(duì)應(yīng)的數(shù)據(jù)類型某電商網(wǎng)站商品名稱字符串單價(jià)浮點(diǎn)型數(shù)量整型某學(xué)生學(xué)籍網(wǎng)姓名字符串出生日期日期型是否團(tuán)員布爾型（邏輯型）數(shù)據(jù)類型簡(jiǎn)單數(shù)據(jù)類型：不能分解成更小的數(shù)據(jù)類型例如：整數(shù)，浮點(diǎn)數(shù)，字符串，布爾等復(fù)合數(shù)據(jù)類型：簡(jiǎn)單數(shù)據(jù)類型或復(fù)合數(shù)據(jù)類型組成例如：列表，字典，元組，集合等bool（邏輯型）True（真）和False（假）listdicttuplesetintfloatstr字符串3浮點(diǎn)型2布爾4整型1int,不包含小數(shù)點(diǎn)的整數(shù)就是整型，例：5，6，7float,包含小數(shù)的數(shù)據(jù)類型時(shí)浮點(diǎn)型，例：3.14，5.2str,包含除數(shù)字以外的其他符號(hào)，例：￥%……&*bool,邏輯型，只表示真或者假簡(jiǎn)單數(shù)據(jù)類型元組3字典2集合4列表1復(fù)合數(shù)據(jù)類型可變的，元素是有序的。OrderList=[1，2，3，4，5]可變的，由索引(key)和它對(duì)應(yīng)的值value組成。

OrderDict={‘a(chǎn)’:1，‘b’:2，‘c’:3}不可變的，元素是有序的。

OrderTuple=（1，2，3，4，5）可變的，元素是唯一的，無(wú)序的。Set1={2,3,1,5,7}Set2={2,3,4,6}①列表訂單匯總，也可以按訂單產(chǎn)生的先后順序組成一個(gè)列表(列表里的項(xiàng)是有順序編號(hào)的)：>>>BookList=[BookInfo0,BookInfo1]>>>type(BookList)<class'list'>#返回列表類型>>>BookList[0]('ID0010230',15.68,36)>>>BookList[1]('ID2315937',20,2)>>>BookList[0][1]*BookList[0][2]+BookList[1][1]*BookList[1][2]604.48#返回計(jì)算結(jié)果②字典>>>tinydict={'a':1,'b':2,'b':'3'}>>>tinydict['b']'3'>>>tinydict{'a':1,'b':'3'}③元組某用戶預(yù)訂的商品編號(hào)為ID0010230、單價(jià)為15.68元，數(shù)量為36，可將這3個(gè)不同類型的簡(jiǎn)單數(shù)據(jù)組織成“元組”復(fù)合數(shù)據(jù)類型：>>>BookInfo0=('ID0010230',15.68,36)>>>type(BookInfo0)<class'tuple'>#返回元組類型另一用戶預(yù)訂的商品編號(hào)為ID2315937、單價(jià)為20元，數(shù)量為2，可記作：>>>BookInfo1=('ID2315937',20,2)>>>BookInfo1[1]20#返回元組BookInfo1中索引為1的項(xiàng)的值④集合訂單匯總,可以定義為一個(gè)集合(集合里的項(xiàng)稱為元素，彼此之間沒(méi)有順序)：>>>BookSet={BookInfo0,BookInfo1}>>>type(BookSet)<class'set'>#返回集合類型>>>BookSet{('ID2315937',20,2),('ID0010230',15.68,36)}#返回集合的值>>>BookInfo0inBookSet#測(cè)試元素BookInfo0是否屬于集合BookSetTrue#返回邏輯真（屬于）數(shù)據(jù)結(jié)構(gòu)：存在特定關(guān)系的數(shù)據(jù)元素的組合體線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)分類：集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹(shù)結(jié)構(gòu)、圖結(jié)構(gòu)二、數(shù)據(jù)結(jié)構(gòu)1、隊(duì)列(Queue)是一種操作有限制的線性結(jié)構(gòu)，它的數(shù)據(jù)元素只能在一端(隊(duì)尾)依次添加(入隊(duì))，在另一端(隊(duì)首)依次刪除(出隊(duì))。隊(duì)列是先進(jìn)先出(FIFO:FirstInFirstOut)表。排隊(duì)候車a0,a1,a2,…

,an出隊(duì)入隊(duì)隊(duì)首隊(duì)尾典型的例子如超市里排隊(duì)付款的隊(duì)伍。二、數(shù)據(jù)結(jié)構(gòu)在Python中，隊(duì)列一般用列表(list)實(shí)現(xiàn)，常用操作：q=[]#定義空列表qq.append(x)#元素x入隊(duì)q.pop(0)#返回隊(duì)首元素,隊(duì)首元素出隊(duì)(刪除)

len(q)#返回隊(duì)列q的長(zhǎng)度(元素個(gè)數(shù))q[i]#返回列表q中索引(index)為i的元素.索引有2套編號(hào)方

式：正編號(hào)(從左到右編號(hào)依次為0,1,2,…)和負(fù)編號(hào)(從

右到左編號(hào)依次為-1,-2,-3,…)隊(duì)列的計(jì)算機(jī)實(shí)現(xiàn)：二、數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)結(jié)構(gòu)【做中悟】活動(dòng)2編制訂單數(shù)據(jù)處理程序P65-661345627進(jìn)隊(duì)順序1234567此處進(jìn)隊(duì)此處出隊(duì)出隊(duì)順序1234567小練習(xí)活動(dòng)1：了解快遞配送線路請(qǐng)同學(xué)們結(jié)合課本P67，小組討論完成下圖派送點(diǎn)學(xué)校收發(fā)室某單位傳達(dá)室職工小李職工小王收件人A同學(xué)觀察一下：這些線路的形狀像什么？任務(wù)二：探究快遞配送過(guò)程收件人B同學(xué)2、樹(shù)結(jié)構(gòu)是一種具有層次關(guān)系的非線性結(jié)構(gòu)。由n(n>=0)個(gè)節(jié)點(diǎn)組成的有限集合。

（1）僅有一個(gè)稱為根的節(jié)點(diǎn)；

（2）當(dāng)n>0時(shí)，其余節(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的集合，其中每個(gè)集合又是一棵樹(shù)，并稱為根的子樹(shù)。典型的例子如快遞到達(dá)目的地城市后，物流圖的結(jié)構(gòu)。二、數(shù)據(jù)結(jié)構(gòu)活動(dòng)2：了解物流網(wǎng)絡(luò)結(jié)合課本P69，將下圖補(bǔ)充完整岳陽(yáng)市揚(yáng)州市南通市長(zhǎng)沙市南京市泰州市任務(wù)二：探究快遞配送過(guò)程思考：這又是什么結(jié)構(gòu)呢？3、圖結(jié)構(gòu)是由一組節(jié)點(diǎn)（稱為頂點(diǎn)）和一組節(jié)點(diǎn)間的連線（稱為邊或?。?gòu)成的一種數(shù)據(jù)結(jié)構(gòu)。圖結(jié)構(gòu)中數(shù)據(jù)元素之間是多對(duì)多的關(guān)系。二、數(shù)據(jù)結(jié)構(gòu)活動(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í)間，詳見(jiàn)表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ò)程的圖形是樹(shù)結(jié)