1、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)游光芒1/69一、數(shù)據(jù)二、數(shù)據(jù)結(jié)構(gòu)三、數(shù)據(jù)結(jié)構(gòu)應(yīng)用2/69一、數(shù)據(jù)digitalvaluedatabig data數(shù)字?jǐn)?shù)值數(shù)據(jù)大數(shù)據(jù) 在計算機(jī)科學(xué)中，數(shù)據(jù)是指全部能輸入到計算機(jī)并被計算機(jī)程序處理符號總稱。1.概念3/69（1）數(shù)字 ：砍一刀飄多少血，升一級需要多少經(jīng)驗（2） 數(shù)值 ： 砍死一個怪要多少刀 升一級需要多少時間（3） 數(shù)據(jù) ： 裝備、道具等與哪類場景匹配等，形式有文字、圖像、視頻、音頻等（4） 大數(shù)據(jù) ：大數(shù)據(jù)5V特點(diǎn)：Volume（大量）、Velocity（高速）、Variety（多樣）、Value（低價值密度）、Veracity（真實(shí)性）。4/692. 數(shù)據(jù)作用單

2、車信息，采集數(shù)據(jù)，影響公交線路制訂等。熱地圖，熱源，微信中熱點(diǎn)區(qū)域。依據(jù)時間段人數(shù)多區(qū)域，選擇性開什么店；移動帶寬適時調(diào)整：依據(jù)每個時段熱源多少，來確定帶寬適時往哪邊多放一些等。5/69二、數(shù)據(jù)結(jié)構(gòu)（一）數(shù)組與鏈表（二）字符串、隊列與棧（三）樹6/69（一）數(shù)組與鏈表同類型數(shù)據(jù)組成序列。1. 數(shù)組數(shù)組元素：a0a1a2a3a432124562數(shù)組名a：下標(biāo)：012347/69例1：神奇矩陣 以下列圖所表示，由19個數(shù)字組成3*3矩陣，其行列、對角線上三數(shù)和均相同。編程輸出全部神奇矩陣排列方式。8/691.結(jié)構(gòu)出全部三個數(shù)字之和15三位數(shù)，且三個位置上數(shù)字不相同。用數(shù)組存放。2.枚舉所得數(shù)組，每

3、三個三位數(shù)結(jié)構(gòu)一個神奇矩陣。每三個數(shù)fi,fj,fk 結(jié)構(gòu) 矩陣情況有以下所表示，需依次判斷這些情況下對角下之和是否為15。FiFjFkFiFkFjFjFiFkFjFkFiFkFiFjFkFjFi9/69f=number=0for i in range(123,1001): a=i / 100 b=i /10 % 10 c=i % 10 if (a+b+c=15) and (a!=b) and (a!=c) and (c!=b): number+=1 f.append(i)結(jié)構(gòu)三位數(shù)字之和為15三位數(shù)：10/69枚舉全部剛才得到三位數(shù)字：for i in range(number): for

4、j in range(i+1,number): for k in range(j+1,number): x1=fi / 100 y1=fi /10 % 10 z1=fi % 10 x2=fj / 100 y2=fj / 10 % 10 z2=fj % 10 x3=fk / 100 y3=fk / 10 % 10 z3=fk % 10 if (x1+x2+x3=15) and (y1+y2+y3=15) and (z1+z2+z3=15) and (x1*x2*x3*y1*y2*y3*z1*z2*z3=362880): if (x1+y2+z3=15) and (z1+y2+x3=15): pr

5、int(fi) print(fj) print(fk) print() #以下5種情況略11/69任務(wù)一：數(shù)組練習(xí)1.輸入一串值不一樣整數(shù)數(shù)列，輸出遞增和遞減子序列數(shù)目。如數(shù)列7，2，6，9，8，3，5，2，1可分為（7，2），（2，6，9），（9，8，3），（3，5），（5，2，1）5個子序列，其中遞增數(shù)列2個，遞減數(shù)列3個。2.數(shù)組元素插入。輸入n個整數(shù)及插入位置x和數(shù)字y。再輸出該數(shù)組。比如：輸入：57 2 3 4 529輸出：7 9 2 3 4 53.求n*n數(shù)陣中馬鞍數(shù)，輸出它位置。所謂馬鞍數(shù)，是指在行上最小 而在列上最大數(shù)。以下：（n=5） 5 6 7 8 9 4 5 6 7 8

6、3 4 5 2 1 2 3 4 9 0 1 2 5 4 8 則1行1列上數(shù)就是馬鞍數(shù)。輸入n及二維矩陣（數(shù)字都不一樣），輸出馬鞍數(shù)所在行列位置。12/694. 數(shù)學(xué)黑洞6174。已知：一個任意四位正整數(shù)。將數(shù)字重新組合成一個最大數(shù)和最小數(shù)相減，重復(fù)這個過程，最多七步，必得6174。即：764114676174。將永遠(yuǎn)出不來。輸出全部四位數(shù)及掉進(jìn)黑洞步數(shù)。5. 以下列圖，第1次按1，第2次隔1個按鈕按3，第3次隔2個按鈕按6，依這類推，按1000次后，把沒有按到數(shù)字從小到大升序輸出。6.求分?jǐn)?shù)準(zhǔn)確值。使用數(shù)組準(zhǔn)確計算M/N(0M s=abcdef s:abcdefstart: 從start 提取

7、到結(jié)尾 s=abcdef s0:abcdef:end 從開頭提取到end - 1 s=abcdef s:6abcdefstart:end 從start 提取到end - 1 s=abcdef s0:6abcdefstart:end:step 從start 提取到end - 1，每step 個字符提取一個 s=abcdef s0:6:2aceleft:right左側(cè)第一個字符位置/偏移量為0，右側(cè)最終一個字符位置/偏移量為-1 s=abcdef s2:4cd19/69字符串基本操作 連接（+）和重復(fù)（*）字符串連接：把兩個字符串連接成一個字符串str1=“Py”str2=“thon”s=str1

8、+str2print(s)輸出：Python字符串重復(fù)：把某個串重復(fù)n次str1=“Py”s=str1*3print(s)輸出：PyPyPy20/69字符串基本操作字符串比較in運(yùn)算符 in運(yùn)算符用于檢驗是否為子串。運(yùn)算符需要兩個參數(shù)：測試字符串和可能包含測試字符串字符串。因為是組員檢驗，所以它將返回布爾值，指示測試字符串是否包含在第二個字符串中。str1 = Hello if( H in str1):print(H 在變量 str1 中) else: print(H 不在變量 str1 中)運(yùn)行后顯示：H 在變量 str1 中21/69字符串基本操作字符串比較 依據(jù)英文字符ASCII碼值大小

9、來比較。分三種情況：第一個：串str1長度等于串str2長度時，即m=n，此時采取挨個比較串中字符。比如：str1=“word”，str2=“work”，從左往右，挨個比較，參考ASCII值。str1 = wordstr2 = workif(str1str2):print(str1)else: print(str2) 運(yùn)行后顯示：work22/69字符串基本操作字符串比較 依據(jù)英文字符ASCII碼值大小來比較。分三種情況：第二種：串str1長度小于串str2長度，且前面一部分相等，即mstr1。str1 = workstr2 = workingif(str1str2):print(str1)e

10、lse: print(str2)運(yùn)行后顯示：working23/69字符串基本操作字符串比較 依據(jù)英文字符ASCII碼值大小來比較。分三種情況：第三種：存在某個位置xstr2x+1時，則字符串str1str2。str1 = moonstr2 = monkeyif(str1str2):print(str1)else: print(str2)運(yùn)行后顯示：moon24/69字符串基本操作字符串慣用函數(shù)函數(shù)和方法功效實(shí)例len(x)輸出字符串x中字符個數(shù)x=”Hello!”print(len(x) 輸出為：6x.upper()將字符串x中小寫字母轉(zhuǎn)大寫x=”Hello!”print(x.upper()

11、輸出為：HELLO!x.lower()將字符串x中大寫字母轉(zhuǎn)小寫x=”Hello!”print(x.lower()輸出為：hello!x.swapcase()將字符串x中字母大寫轉(zhuǎn)小寫，小寫轉(zhuǎn)大寫x=”Hello!”print(x.swapcase()輸出為：hELLO!x.find(y)返回字符串x中子串y出現(xiàn)首字符下標(biāo)，若找不到子串則輸出-1x=”Hello!”y=”llo”print(x.find(y)輸出為：2x.index(y)返回字符串x中子串y出現(xiàn)首字符下標(biāo)，若找不到子串則輸出異常x=”Hello!”y=”llo”print(x.index(y)輸出為：2x.count(y)返回

12、字符串x中子串y重復(fù)出現(xiàn)次數(shù)x=”I like Python”y=” ”print(x.count(y)y=”like”print(x.count(y)第一個輸出為：2第二個輸出為：125/69字符串實(shí)例 輸入一個數(shù)字串s(長度小于100)，刪去其中k(k0: j=0 while jlen(s)-1 and sj1) and s0=0: temps=s1: s=tempsprint(s)請輸入數(shù)字串s，長度不超出100位：1298034請輸入k：3輸出：103429/69任務(wù)三：字符串實(shí)踐1.李雷收到了朋友發(fā)給他一封奇怪郵件，里面有段內(nèi)容是由一些數(shù)字和符號組成， 信上面說了，這段內(nèi)容是加密后內(nèi)

13、容，并給出了詳細(xì)加密方法（假定原文英文字母都是大 寫），詳細(xì)方法以下： （1）“ A”變?yōu)橐粋€ 1 到 100 內(nèi)隨機(jī)數(shù)*27+1，“ B”變?yōu)橐粋€ 1 到 100 內(nèi)隨機(jī)數(shù)*27+2， “Z”變?yōu)橐粋€ 1 到 100 內(nèi)隨機(jī)數(shù)*27+26； （2）每個字母變?yōu)閿?shù)字后會加上一個“-”用來分割數(shù)字； （3）其它空格和標(biāo)點(diǎn)字符都按原來表示密文1898-1462-1555-772-835-2084-49-2057-2205-1915-112-1108-2347-1原文任務(wù)：輸入密文，輸出原文。30/69任務(wù)三：字符串實(shí)踐2.某字符串（字節(jié)數(shù)為3倍數(shù)）編碼規(guī)則以下：（1）將該字符串內(nèi)碼分成3個字節(jié)一組

14、，順次連接后得到24位二進(jìn)制數(shù)；（2）將得到24位二進(jìn)制數(shù)字分成4組，每組6位；（3）在每組數(shù)字前補(bǔ)上兩個0，得到4個字節(jié)二進(jìn)制數(shù)；（4）將（3）中得到四個二進(jìn)制數(shù)分別轉(zhuǎn)換為十進(jìn)制數(shù)；（5）將每個十進(jìn)制數(shù)轉(zhuǎn)換為1個加密字符，對應(yīng)“密碼表”按數(shù)值由小到大依次為“ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyx0123456789+/” 小明按照上述方法，設(shè)計了一個字符串（僅包含ASCII字符）加密程序，依次將輸入字符串中每3個字符ASCII值按編碼規(guī)則轉(zhuǎn)換為四個加密字符，連接這些加密字符，最終輸出加密結(jié)果。原串This is an exam

15、ple密文VGhpcOBpcOBhbKBleGFtcGxl31/692.隊列 隊列是一個特殊線性表，它只允許在表前端（front）進(jìn)行刪除操作，而在表后端（rear）進(jìn)行插入操作。進(jìn)行插入操作端稱為隊尾，進(jìn)行刪除操作端稱為隊頭。32/69隊列存放 隊列普通按次序結(jié)構(gòu)進(jìn)行存放，能夠用數(shù)組來實(shí)現(xiàn)。因為隊首和隊尾位置均是改變，因而需要設(shè)置兩個數(shù)組下標(biāo)變量head和tail，head指向隊首元素，tail指向隊尾元素。33/69隊列基本操作： 建立隊列queue=“”*100head=-1tail=-1 入隊tail=tail+1queuetail=“一”出隊while headtail: head=

16、head+1 print(queuehead)34/69隊列實(shí)列模擬實(shí)現(xiàn)移動營業(yè)廳取號與叫號功效，用程序?qū)崿F(xiàn)。（1）取號，入隊操作（2）叫號，出隊操作35/69queue=-1*1000head=-1tail=-1print(請輸入詳細(xì)操作)print(請輸入詳細(xì)操作：)print(1.新到用戶（取號）)print(2.下一個用戶（叫號）)x=int(input(請輸入操作，輸入3結(jié)束：)while x!=3: if x=1: tail+=1 queuetail=tail print(你當(dāng)前號碼為：A%d%(tail) print(需等候人數(shù)為：%d%(tail-head-1) if x=2:

17、 if head=0:print(stacktop)棧基本操作出棧。while top=0:print(stacktop)top=top-140/69棧實(shí)例用棧實(shí)現(xiàn)一個十進(jìn)制轉(zhuǎn)二進(jìn)制程序。41/69stack=-1*100top=-1number=int(input(請輸入十進(jìn)制整數(shù)：)while number0: x=number % 2 top=top+1 stacktop=x number=number / 2while top=0: print(stacktop,end=) top=top-142/69棧實(shí)踐任務(wù)：1. 有六個元素FEDCBA 從左到右依次次序進(jìn)棧，在進(jìn)棧過程中會有元素

18、被彈出棧。問以下哪一個不可能是正當(dāng)出棧序列？A) EDCFABB) DECABFC) CDFEBAD) BCDAEF2. 元素R1、R2、R3、R4、R5入棧次序為R1、R2、R3、R4、R5。假如第1個出棧是R3，則第5個出棧不可能是A. R1 B. R2 C. R4 D. R53. 設(shè)棧S初始狀態(tài)為空，元素a, b, c, d, e, f, g依次入棧，以下出棧序列不可能出現(xiàn)是（ ）。A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, d, c, b, f, g D. g, e, f, d, c, b, a43/69棧實(shí)踐任務(wù)：1.

19、 編程求中綴表示式 值。如： (a+b)*c-d*e2. 編程將中綴表示式轉(zhuǎn)后綴表示式。對于題1中綴轉(zhuǎn)后綴為：ab+c*de*-44/69（三）樹課標(biāo)解讀：經(jīng)過列舉實(shí)例，認(rèn)識到抽象數(shù)據(jù)類型對數(shù)據(jù)處理主要性，了解抽象數(shù)據(jù)類型概念，了解二叉樹概念及其基本操作。1. 抽象數(shù)據(jù)類型數(shù)據(jù)類型。它是指一組性質(zhì)相同值集合及定義在此集合上一些操作總稱。如整型、字符串類型等抽象數(shù)據(jù)類型。是指一個數(shù)學(xué)模型及定義在該模型上一組操作，ADT基本思想是抽象。比如字符串len函數(shù)等。使用時，不用關(guān)系len是怎樣來，直接使用即能夠。45/69（三）樹1. 樹與二叉樹46/69（1）結(jié)點(diǎn)（Node）和邊（Edge）（2）結(jié)點(diǎn)

20、度（Degree）和樹度（3）根結(jié)點(diǎn)（Root）和葉子（Leaf）（4）孩子結(jié)點(diǎn)（Child）和雙親結(jié)點(diǎn)（Parents）（5）結(jié)點(diǎn)層數(shù)（Lever）和樹高度（Height）普通樹：47/69二叉樹：二叉樹是以結(jié)點(diǎn)為元素有限集，它或者為空，或者滿足以下條件：有一個特定結(jié)點(diǎn)稱為根；余下結(jié)點(diǎn)分為互不相交子集L和R，其中R是根左子樹；L是根右子樹；L和R又是二叉樹；樹每一個結(jié)點(diǎn)能夠有任意多個后件，而二叉樹中每個結(jié)點(diǎn)后件不能超出2；樹子樹能夠不分次序（除有序樹外）；而二叉樹子樹有左右之分。我們稱二叉樹中結(jié)點(diǎn)左后件為左兒子，右后件為右兒子。 二叉樹與樹不一樣地方：48/69二叉樹五種基本形態(tài) 49/69

21、二叉樹兩種特殊形態(tài)：滿二叉樹 假如一棵二叉樹任何結(jié)點(diǎn)，或者是樹葉，或者恰有兩棵非空子樹，則此二叉樹稱作滿二叉樹。（比如圖(a)）能夠驗證含有n個葉結(jié)點(diǎn)滿二叉樹共有2n-1個結(jié)點(diǎn)。50/69二叉樹兩種特殊形態(tài)：完全二叉樹 假如一棵二叉樹最多只有最下面兩層結(jié)點(diǎn)度數(shù)能夠小于2，而且最下面一層結(jié)點(diǎn)都集中在該層最左邊若干位置上，則稱此二叉樹為完全二叉樹（比如圖(b)）51/69二叉樹性質(zhì)：（1）在二叉樹第i（1）層上，最多有2i-1個結(jié)點(diǎn)（2）在深度為k(k1)二叉樹中最多有2k-1個 結(jié)點(diǎn)。（3）在任何二叉樹中，葉子結(jié)點(diǎn)數(shù)總比度為2結(jié)點(diǎn)多1。52/69證實(shí)： 設(shè)n0為二叉樹葉結(jié)點(diǎn)數(shù)；n1為二叉樹中度為

22、1結(jié)點(diǎn)數(shù)；n2為二叉樹中度為2結(jié)點(diǎn)數(shù)，顯然n=n0+n1+n2 （1） 因為二叉樹中除了根結(jié)點(diǎn)外，其余每個結(jié)點(diǎn)都有且僅有一個前件。設(shè) b為二叉樹前件個數(shù)，n=b+1（2） 全部這些前件同時又為度為1和度為2結(jié)點(diǎn)后件。所以又有b=n1+2n2 (3)除v0沒有前件外，v1、v2、v3、v4、v5都有一個前件，b=5。而v1和v2為v0后件，v3為v1后件，v4和v5為v2后件，所以b= b=n1+2n2=1+2*2=5。 我們將（3）代入（2）得出n=n1+2n2+1 (4) 比較（1）和（4），得出n0=n2+1,即葉子數(shù)比度為2結(jié)點(diǎn)數(shù)多1 53/69二叉樹基本操作：（1）二叉樹存放（線性存放

23、 完全二叉樹）ABCDEF12345654/69（1）二叉樹存放（線性存放 非完全二叉樹）ABCDEFGH123457101455/69（1）二叉樹存放（鏈?zhǔn)酱娣牛?6/69（2）二叉樹遍歷 就是按一定規(guī)則和次序走遍二叉樹全部結(jié)點(diǎn)，使每一個結(jié)點(diǎn)都被訪問一次，而且只被訪問一次。因為二叉樹是非線性結(jié)構(gòu)，所以，樹遍歷實(shí)質(zhì)上是將二叉樹各個結(jié)點(diǎn)轉(zhuǎn)換成為一個線性序列來表示。遍歷時，要求先左子樹后右子樹次序時，能夠分為三種遍歷：先序遍歷：先訪問根結(jié)點(diǎn)，再訪問左子樹，最終訪問右子樹。先序序列：a b d e h i c f g 57/69（2）二叉樹遍歷中序遍歷：先訪問左子樹，再訪問根結(jié)點(diǎn)，最終訪問右子樹。中

24、序序列：d b h e i a f c g 58/69（2）二叉樹遍歷后序遍歷：先訪問左子樹，再訪問右子樹，最終訪問根結(jié)點(diǎn)。后序序列：d h i e b f g c a59/69樹實(shí)踐任務(wù)：（1）寫出下面二叉樹先序遍歷、中序遍歷、后序遍歷60/69樹實(shí)踐任務(wù)：（2）假如根高度為 1，含有 61 個結(jié)點(diǎn)完全二叉樹高度為（ ） A. 5 B. 6 C. 7 D. 8（3）已知一棵二叉樹有 10 個節(jié)點(diǎn)，則其中至多有（ ）個節(jié)點(diǎn)有 2 個子節(jié)點(diǎn) 。A. 5 B. 6 C. 7 D. 4（4）二叉樹T，已知其先序遍歷是1 2 4 3 5 7 6（數(shù)字為節(jié)點(diǎn)編號，以下同），中序遍歷是4 2 1 7 5 3 6 ，則該二叉樹后序遍歷可能為（ A ）A4 2 7 5 6 3 1 B2 4 1 7 5 3 6 C4 2 1 7 5 6 4 D2 4 1 5 7 3 661/69三、數(shù)據(jù)結(jié)構(gòu)應(yīng)用（一）算法與數(shù)據(jù)結(jié)構(gòu)（二）迭代與遞歸（三）數(shù)據(jù)排序（四）數(shù)據(jù)查找62/69（一）算法與數(shù)據(jù)結(jié)構(gòu)1.算法效率分析 時間復(fù)雜度又稱計算復(fù)雜度，是指執(zhí)行程序計算工作量。同一問題，采取不一樣算法，程序計算工作量是不一樣。【例題】輸入100個整數(shù)，輸出其中