合工大數據結構 01-概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、的數量級來替代 數量級：數量級：如果變量n的函數f(n)和g(n)滿足：lim f(n)/g(n)=常數 k (k,0)，則稱f(n)和g(n) 是同一數量級的，并用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 例子：求解以下程序段的時間復雜度： for（i=1; i=n; i+）x=x+1; i = n0非非0i=1x=x+1i+語句執(zhí)行次數語句執(zhí)行次數 1次 n+1次 n次 n次 共：3n+2次 數量級為：lim f(n)/g(n)= lim (3n+2)/n = 3，

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