合工大數(shù)據(jù)結(jié)構(gòu) 01-概述

1、1數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)（第一章第一章 概述概述） Data Structures張晶張晶計(jì)算機(jī)與信息學(xué)院計(jì)算機(jī)與信息學(xué)院 2022-2-122022-2-122v計(jì)算機(jī)相關(guān)專(zhuān)業(yè)的一門(mén)重要的專(zhuān)業(yè)基礎(chǔ)課計(jì)算機(jī)相關(guān)專(zhuān)業(yè)的一門(mén)重要的專(zhuān)業(yè)基礎(chǔ)課v主要研究主要研究v是學(xué)習(xí)計(jì)算機(jī)其他相關(guān)課程的必備條件，是提高編程是學(xué)習(xí)計(jì)算機(jī)其他相關(guān)課程的必備條件，是提高編程能力的必要條件能力的必要條件v需程序設(shè)計(jì)類(lèi)課程的支撐（需程序設(shè)計(jì)類(lèi)課程的支撐（C/C+/Java）課程背景3全課程的章節(jié)安排o 第一章第一章 概述概述 o 第二章第二章 順序棧順序棧 o 第三章第三章 順序隊(duì)列順序隊(duì)列 o 第四章第四章 鏈棧和鏈隊(duì)列鏈

2、棧和鏈隊(duì)列 o 第五章第五章 線(xiàn)性表線(xiàn)性表 o 第六章第六章 遞歸技術(shù)遞歸技術(shù) o 第七章第七章 數(shù)組和廣義表數(shù)組和廣義表o 第八章第八章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)o 第九章第九章 圖結(jié)構(gòu)圖結(jié)構(gòu)o 第十章第十章 查找查找o 第十一章第十一章 排序排序4v數(shù)據(jù)結(jié)構(gòu)的基本概念;v線(xiàn)性表、棧和隊(duì)列、串和數(shù)組;v樹(shù)形結(jié)構(gòu);v圖結(jié)構(gòu);v查找；v排序;v其他本課程的主要內(nèi)容5一個(gè)問(wèn)題引發(fā)的 將將10個(gè)數(shù)據(jù)排序個(gè)數(shù)據(jù)排序冒泡排序？選擇排序？冒泡排序？選擇排序？時(shí)間如何？時(shí)間如何？空間如何？空間如何？將將100、1000、1000000個(gè)數(shù)據(jù)排序個(gè)數(shù)據(jù)排序課后作業(yè)：課后作業(yè)： 完成完成50005000數(shù)據(jù)排序，并

3、顯示運(yùn)行時(shí)間。數(shù)據(jù)排序，并顯示運(yùn)行時(shí)間。6一個(gè)問(wèn)題引發(fā)的 國(guó)際象棋發(fā)明人的報(bào)酬國(guó)際象棋發(fā)明人的報(bào)酬印度的一個(gè)古老傳說(shuō)印度的一個(gè)古老傳說(shuō): : 舍罕王打算重賞象棋發(fā)明人舍罕王打算重賞象棋發(fā)明人- -宰相宰相 西薩西薩班班達(dá)依爾。達(dá)依爾。西薩指著面前的棋盤(pán)奏道：“陛下，就請(qǐng)您賞給我一些麥子吧，它們只要這樣放在棋盤(pán)里就行了：第一個(gè)格里放一顆，第二個(gè)格里放兩顆，第三個(gè)格里放四顆，以后每一個(gè)格里都比前一個(gè)格里的麥粒增加一倍。圣明的王啊，只要把這樣擺滿(mǎn)棋盤(pán)上全部六十四格的麥粒都賞給你的仆人，他就心滿(mǎn)意足了?！? 5如果一升小麥按如果一升小麥按150150，000000粒計(jì)算，這大約是粒計(jì)算，這大約是140

4、140萬(wàn)億升小麥，按萬(wàn)億升小麥，按目前的平均產(chǎn)量計(jì)算，這竟然是全世界生產(chǎn)兩千年的全部小麥！目前的平均產(chǎn)量計(jì)算，這竟然是全世界生產(chǎn)兩千年的全部小麥！7一個(gè)問(wèn)題引發(fā)的 公元公元8世紀(jì)的數(shù)學(xué)邏輯問(wèn)題世紀(jì)的數(shù)學(xué)邏輯問(wèn)題過(guò)河問(wèn)題過(guò)河問(wèn)題一個(gè)農(nóng)夫攜帶一只狼，一只羊和一棵白菜，要借助一條小船一個(gè)農(nóng)夫攜帶一只狼，一只羊和一棵白菜，要借助一條小船過(guò)河。小船上除了農(nóng)夫只能再帶狼、羊、白菜中的一樣。而過(guò)河。小船上除了農(nóng)夫只能再帶狼、羊、白菜中的一樣。而農(nóng)夫不在時(shí)，狼會(huì)吃羊，羊會(huì)吃白菜。農(nóng)夫如何過(guò)河呢？農(nóng)夫不在時(shí)，狼會(huì)吃羊，羊會(huì)吃白菜。農(nóng)夫如何過(guò)河呢？先帶羊過(guò)去，回來(lái)帶白菜，再把羊帶回來(lái)，白菜放在對(duì)面，先帶羊過(guò)去，回

5、來(lái)帶白菜，再把羊帶回來(lái)，白菜放在對(duì)面，然后把狼帶過(guò)去，羊放這邊，最后回來(lái)帶羊。然后把狼帶過(guò)去，羊放這邊，最后回來(lái)帶羊。8第一章第一章 概概 述述 第一章第一章 概概 述述 1.1 研究?jī)?nèi)容 1.2 術(shù)語(yǔ) 1.3 算法及其描述 1.4 算法分析 91.1 研究?jī)?nèi)容o 軟件設(shè)計(jì)中常用的基本技術(shù)軟件設(shè)計(jì)中常用的基本技術(shù)實(shí)際問(wèn)題抽象 數(shù)學(xué)模型求解方法構(gòu)造求解算法 測(cè)試 程序設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu)組織 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)101.2 術(shù)語(yǔ) o數(shù)據(jù)（數(shù)據(jù)（data） 能夠輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)識(shí)別、存儲(chǔ) 分解 和處理的符號(hào)的集合.（廣義） o數(shù)據(jù)元素（數(shù)據(jù)元素（data element） 構(gòu)成數(shù)據(jù)的基本單元（具有

6、完整的 描述 獨(dú)立意義）。某些場(chǎng)合還被稱(chēng)為元素、記錄、 結(jié)點(diǎn)、頂點(diǎn)等。o數(shù)據(jù)項(xiàng)（字段）數(shù)據(jù)項(xiàng)（字段） 元素的具體信息o數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（data structures）構(gòu)成數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。 線(xiàn)性結(jié)構(gòu) 樹(shù)狀結(jié)構(gòu)（樹(shù)型結(jié)構(gòu)） 圖結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)） 集合 111.2 術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)示例：(a) 工資表示例編號(hào)姓名基本工資獎(jiǎng)金(b) 成績(jī)表示例序號(hào)學(xué)號(hào)姓名成績(jī)備注121.2 術(shù)語(yǔ)AA2A1A11A3A12A311A21A32A31A121A1A2A3A5A4A6A8A7(c) 家族關(guān)系示例(d) 群體間關(guān)系示例（連線(xiàn)表示相互認(rèn)識(shí)關(guān)系）131.2 術(shù)語(yǔ)o 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 線(xiàn)性、樹(shù)形（樹(shù)型）、圖（

7、網(wǎng)狀）、集合o 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中的實(shí)現(xiàn)形式 n同樣的邏輯結(jié)構(gòu)同樣的存儲(chǔ)結(jié)構(gòu)o 運(yùn)算運(yùn)算（判斷存儲(chǔ)結(jié)構(gòu)的好壞） 有關(guān)數(shù)據(jù)結(jié)構(gòu)幾個(gè)方面的聯(lián)系圖邏輯結(jié)構(gòu)測(cè)試與分析 運(yùn)算實(shí)現(xiàn)（算法） 存儲(chǔ)結(jié)構(gòu)運(yùn)算定義 抽象數(shù)據(jù)類(lèi)型（ADT） 141.3 算法及其描述 o 算法算法 特定問(wèn)題的求解方法, 指令的有限序列， 滿(mǎn)足： (1) 輸入 0n個(gè) (2) 輸出 1n 個(gè) 與輸入有特定聯(lián)系 (3) 確定性（無(wú)二義性） 相同的輸入只能有相同的輸出 (4) 有限性 執(zhí)行次數(shù)有限 (5) 可行性 算法可用計(jì)算機(jī)在有限時(shí)間內(nèi)實(shí)現(xiàn)算法設(shè)計(jì)是計(jì)算機(jī)專(zhuān)業(yè)的核心能力，是區(qū)別于其他專(zhuān)業(yè)的最核心能力之一。算法設(shè)計(jì)是計(jì)算

8、機(jī)專(zhuān)業(yè)的核心能力，是區(qū)別于其他專(zhuān)業(yè)的最核心能力之一。151.3 算法及其描述o算法描述語(yǔ)言算法描述語(yǔ)言 易懂，靈活 自然語(yǔ)言 不準(zhǔn)確 準(zhǔn)確，嚴(yán)格 計(jì)算機(jī)語(yǔ)言 死板 偽語(yǔ)言（類(lèi)語(yǔ)言）：類(lèi)pascal、類(lèi)C、類(lèi)C+o 算法舉例：算法舉例： 1.求最大公因子（輾轉(zhuǎn)相除法） 2.韓信點(diǎn)兵問(wèn)題 3.幻方問(wèn)題（縱橫圖）161.3 算法及其描述 例例1.求最大公因子（輾轉(zhuǎn)相除法）求最大公因子（輾轉(zhuǎn)相除法）求任意兩個(gè)整數(shù)求任意兩個(gè)整數(shù)M,N最大公因子最大公因子(M,N)的方法如下：的方法如下： 若若M=N*Q+R 其中其中: R為為余數(shù)余數(shù),滿(mǎn)足滿(mǎn)足 ORN-1 則則(M,N)=(N,R) 且當(dāng)且當(dāng)R=0時(shí)，

9、時(shí)， (M,N)=N按照這種方法，可以快速而方便地求出任意兩個(gè)整數(shù)的最大公因子。按照這種方法，可以快速而方便地求出任意兩個(gè)整數(shù)的最大公因子。 例如，例如，（1500，550）的求解過(guò)程如下：的求解過(guò)程如下： （1500，550）=（550，400）=（400，150）=（150，100）=（100，50）=（50，0）=50 最終求得最終求得1500和和550的最大公因子為。的最大公因子為。171.3 算法及其描述由此，可得到求任意兩個(gè)整數(shù)由此，可得到求任意兩個(gè)整數(shù)M和和N最大公因子的算法的語(yǔ)言函數(shù)如下：最大公因子的算法的語(yǔ)言函數(shù)如下： int hcf(int m, int n) while

10、(n!=0) r=m % n; m=n; n=r; return m;其對(duì)應(yīng)的其對(duì)應(yīng)的遞歸函數(shù)遞歸函數(shù)如下：如下：int hcf(int m, int n) if (n=0) return m; else return hcf(n, m % n);181.3 算法及其描述例例2.“韓信點(diǎn)兵韓信點(diǎn)兵”問(wèn)題的求解方法問(wèn)題的求解方法有一隊(duì)士兵，確切人數(shù)不知，但若每人一組，則余人；有一隊(duì)士兵，確切人數(shù)不知，但若每人一組，則余人；每人一組，余人；每人一組，余人；每人一組，每人一組，余人；每人一組，余人；每人一組，余人。余人。請(qǐng)解答下列問(wèn)題：請(qǐng)解答下列問(wèn)題：至少有多少人？至少有多少人？若已知人數(shù)在若已知人

11、數(shù)在500010000之間，問(wèn)有多少個(gè)答案？之間，問(wèn)有多少個(gè)答案？解解：初學(xué)者容易想到用逐個(gè)試探的方法來(lái)求解，這樣顯然很耗：初學(xué)者容易想到用逐個(gè)試探的方法來(lái)求解，這樣顯然很耗時(shí)間，特別是在所求解的值非常大時(shí)。時(shí)間，特別是在所求解的值非常大時(shí)。求解方法求解方法是：逐個(gè)滿(mǎn)足條件，在尋找滿(mǎn)足下一個(gè)條件的解時(shí)保是：逐個(gè)滿(mǎn)足條件，在尋找滿(mǎn)足下一個(gè)條件的解時(shí)保證前面條件繼續(xù)成立。證前面條件繼續(xù)成立。如何做到這一點(diǎn)？如何做到這一點(diǎn)？可以這樣實(shí)現(xiàn)：探索滿(mǎn)足下一個(gè)條件的的值時(shí)，以累加可以這樣實(shí)現(xiàn)：探索滿(mǎn)足下一個(gè)條件的的值時(shí)，以累加前面各數(shù)的最小公倍數(shù)來(lái)試探。由此得到求解的程序段。前面各數(shù)的最小公倍數(shù)來(lái)試探。由此

12、得到求解的程序段。191.3 算法及其描述o問(wèn)題（）的語(yǔ)言程序段如下：?jiǎn)栴}（）的語(yǔ)言程序段如下： n=2; / 滿(mǎn)足滿(mǎn)足 3人一組余人一組余2 while （n % 5！=3） n=n+3; / 在保證在保證 3人一組余人一組余2的前提下尋找滿(mǎn)足的前提下尋找滿(mǎn)足5人一組余人一組余3的的n值值 while （n % 7！=5） n=n+15; /在滿(mǎn)足前兩個(gè)條件的前提下尋找滿(mǎn)足在滿(mǎn)足前兩個(gè)條件的前提下尋找滿(mǎn)足7人一組余人一組余5的的n值值 while （n % 11！=4） n=n+105; /在滿(mǎn)足前三個(gè)條件的前提下尋找滿(mǎn)足在滿(mǎn)足前三個(gè)條件的前提下尋找滿(mǎn)足11人一組余人一組余4的的n值值其中每

13、次所加上的是前面數(shù)的最小公倍數(shù)其中每次所加上的是前面數(shù)的最小公倍數(shù)3，15，105 o問(wèn)題（）的語(yǔ)言程序段如下：?jiǎn)栴}（）的語(yǔ)言程序段如下：while （n5000 ） n=n+1155; while （n=10000） coutn;n=n+1155;/輸出滿(mǎn)足條件的各解輸出滿(mǎn)足條件的各解201.3 算法及其描述3.幻方問(wèn)題（縱橫圖）幻方問(wèn)題（縱橫圖）將將1n放在放在nn（n為奇數(shù)）為奇數(shù)） 的方陣中，使得任意一行任意一的方陣中，使得任意一行任意一列以及兩條對(duì)角線(xiàn)上的所有元素之和均相等。如列以及兩條對(duì)角線(xiàn)上的所有元素之和均相等。如n=5時(shí)的方時(shí)的方陣如下圖所示。陣如下圖所示。211.3 算法及其

14、描述o 這一問(wèn)題如果采用試探的方法，在值較大時(shí)，將這一問(wèn)題如果采用試探的方法，在值較大時(shí)，將難以求出，因?yàn)榭赡艿臓顟B(tài)數(shù)是難以求出，因?yàn)榭赡艿臓顟B(tài)數(shù)是！個(gè)。！個(gè)。o 經(jīng)典的經(jīng)典的構(gòu)造方法構(gòu)造方法如下：如下：n 將數(shù)將數(shù)1 1 放在第一行的中間元素，放在第一行的中間元素， 然后往左上的位置然后往左上的位置上放入下一個(gè)數(shù)。上放入下一個(gè)數(shù)。n 若左上的位置已有數(shù)，則將其放入該數(shù)的下一行中若左上的位置已有數(shù)，則將其放入該數(shù)的下一行中的同一列的位置上。的同一列的位置上。n 若已是最左或最上面位置上的元素，則其下一個(gè)位若已是最左或最上面位置上的元素，則其下一個(gè)位置的尋找方法是：置的尋找方法是： 將方陣卷成一

15、個(gè)紙筒，將方陣卷成一個(gè)紙筒， 然后依然后依此再按同樣的方向再找下一個(gè)位置，直到此再按同樣的方向再找下一個(gè)位置，直到n nn n個(gè)元個(gè)元素全部放入為止。素全部放入為止。221.3 算法及其描述時(shí)的求解過(guò)程如下： 231.4 算法分析 o 算法的衡量指標(biāo)算法的衡量指標(biāo)：在正確性的前提下n 時(shí)間性能運(yùn)行算法的時(shí)間開(kāi)銷(xiāo)n 空間性能運(yùn)行算法的輔助空間規(guī)模n 其它性能如可讀性/可移植性 241.4 算法分析 u 時(shí)間性能（時(shí)間復(fù)雜度）：時(shí)間性能（時(shí)間復(fù)雜度）： 以算法運(yùn)行時(shí)間開(kāi)銷(xiāo)來(lái)度量 改進(jìn)改進(jìn) 與具體機(jī)器相關(guān)與具體機(jī)器相關(guān) 以算法中語(yǔ)句的執(zhí)行次數(shù)來(lái)衡量 簡(jiǎn)化簡(jiǎn)化 計(jì)算麻煩計(jì)算麻煩 以算法中語(yǔ)句的執(zhí)行次數(shù)

16、的數(shù)量級(jí)來(lái)替代 數(shù)量級(jí)：數(shù)量級(jí)：如果變量n的函數(shù)f(n)和g(n)滿(mǎn)足：lim f(n)/g(n)=常數(shù) k (k,0)，則稱(chēng)f(n)和g(n) 是同一數(shù)量級(jí)的，并用f(n)=O(g(n)的形式來(lái)表示。 O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)| O(2n) O(n!) 難以實(shí)現(xiàn)251.4 算法分析o 例子：求解以下程序段的時(shí)間復(fù)雜度： for（i=1; i=n; i+）x=x+1; i = n0非非0i=1x=x+1i+語(yǔ)句執(zhí)行次數(shù)語(yǔ)句執(zhí)行次數(shù) 1次 n+1次 n次 n次 共：3n+2次 數(shù)量級(jí)為：lim f(n)/g(n)= lim (3n+2)/n = 3，

17、則時(shí)間復(fù)雜度為為O (n)o練習(xí)： (1) for (i=1; in; i+) for (j=1; j= i; j+) x+; (2) i = 1; while (in) i = i*2; 26練習(xí)：練習(xí)：1. 求下列語(yǔ)句段的時(shí)間復(fù)雜度：求下列語(yǔ)句段的時(shí)間復(fù)雜度： (1) for (i=1; in; i+) for (j=1; j= i; j+) x+; (2) i = 1; while (in) i = i*2; (3) for (i=1; i=n; i+) for (j=1; j=n; j+) for (k=1; k=n; k+) x+; （4）for (i=1; in; i+) for

18、(j=1; jn; j+) x+; for (k=1; kn;k+) x+;27練習(xí)：練習(xí)：2. 編寫(xiě)算法以計(jì)算在給定各系數(shù)和變量x的值時(shí)的多項(xiàng)式fn(x)的值，要求時(shí)間盡可能少。 （提示：可將各系數(shù)存儲(chǔ)在數(shù)組A中； 另外，乘法運(yùn)算的時(shí)間是加法運(yùn)算時(shí)間的數(shù)倍） fn(x)=a0+a1x+a2x2+a3x3+.+anxn3. 設(shè)計(jì)算法求集合1,2,.,n的冪集。28練習(xí)：練習(xí)：4.背包問(wèn)題：設(shè)有個(gè)物品，其重量分別為背包問(wèn)題：設(shè)有個(gè)物品，其重量分別為w1，w2，w3，wn，所，所有物品的重量之和有物品的重量之和背包所能放置的重量。設(shè)計(jì)算法從中找出若背包所能放置的重量。設(shè)計(jì)算法從中找出若干物品放入背包中，使得其重量之和正好為。干物品放入背包中，使得其重量之和正好為。 例如，例如，S=50, n=10, w=( 29 26 18 16 13 10 8 5 3 1)（