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

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

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

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

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

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

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

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

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

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

10、(n!=0) r=m % n; m=n; n=r; return m;其對應(yīng)的其對應(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)兵”問題的求解方法問題的求解方法有一隊士兵，確切人數(shù)不知，但若每人一組，則余人；有一隊士兵，確切人數(shù)不知，但若每人一組，則余人；每人一組，余人；每人一組，余人；每人一組，每人一組，余人；每人一組，余人；每人一組，余人。余人。請解答下列問題：請解答下列問題：至少有多少人？至少有多少人？若已知人數(shù)在若已知人

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

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

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

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

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

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

17、則時間復(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. 求下列語句段的時間復(fù)雜度：求下列語句段的時間復(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. 編寫算法以計算在給定各系數(shù)和變量x的值時的多項式fn(x)的值，要求時間盡可能少。 （提示：可將各系數(shù)存儲在數(shù)組A中； 另外，乘法運(yùn)算的時間是加法運(yùn)算時間的數(shù)倍） fn(x)=a0+a1x+a2x2+a3x3+.+anxn3. 設(shè)計算法求集合1,2,.,n的冪集。28練習(xí)：練習(xí)：4.背包問題：設(shè)有個物品，其重量分別為背包問題：設(shè)有個物品，其重量分別為w1，w2，w3，wn，所，所有物品的重量之和有物品的重量之和背包所能放置的重量。設(shè)計算法從中找出若背包所能放置的重量。設(shè)計算法從中找出若干物品放入背包中，使得其重量之和正好為。干物品放入背包中，使得其重量之和正好為。 例如，例如，S=50, n=10, w=( 29 26 18 16 13 10 8 5 3 1)（