1、數據結構與算法Data Structure and algorithms 2 數據結構題集 （ C語言版） 嚴蔚敏 吳偉民 清華大學出版社 參考教材1 數據結構 （ C語言版） 嚴蔚敏 吳偉民 清華大學出版社第一章 緒論 第一章 緒論 1.1 數據結構討論的范疇； 1.2 數據結構的有關基本概念； 1.3 抽象數據類型的表示與實現； 1.4 算法及算法分析（算法評價） 數據結構是什么? Niklaus Wirth AlgorithmData Structures Programs 程序設計： 為計算機解題（處理問題）編制的一組 指令集。算法： 對某類信息進行處理，處理問題的策略。數據結構：處理

2、的信息怎么表示，問題的數學模型。任何問題都包括這兩個方面的問題，包括數值計算和非數值計算1.1 數據結構討論的范疇 數值問題與非數值問題1）數值計算中的程序設計的問題例1 已知：游泳池的長len和寬wide，求面積area? 建模型： 問題涉及的對象：游泳池的長len 寬wide，面積area； 對象之間的關系：area=lenwide （算法）設計求解問題的方法1.1 數據結構討論的范疇 編程 main ( ) int len, wide ,area ; scanf (“%d %d%n”, &l,&w); area=len*wide ; printf (“area=%d”,area); 例2

3、：結構靜力分析計算 線性代數方程組例3：全球天氣預報 環流模式方程組 學號 姓名 性別 出生日期 籍貫 入學成績 所在班級 00201 楊潤生 男 82/06/01 廣州 561 00計算機200102 石磊 男 83/12/21 汕頭 512 00計算機100202 李梅 女 83/02/23 陽江 532 00計算機200301 馬耀先 男 82/07/12 廣州 509 00計算機32）非數值計算的程序設計問題例 2 已知某級學生情況 , 要求分班按入學成績排列順序。 學生管理數據庫系統1.1 數據結構討論的范疇算法：？需要解決的問題？如何解決？用戶界面？模型：？各種各樣的表格和數據庫在

4、這類文檔管理的數學模型中, 計算機處理的對象之間通常存在著一種最簡單的線性關系 , 這類數學模型稱為線性模型。例 3 迷宮問題。在迷宮中，每走到一處，接下來可走的通路有三條。計算機處理的這類對象之間通常不存在線性關系。若把從迷宮入口處到出口的過程中所有可能的通路都畫出，則可得一棵“樹” 。入口 出口算法：？走迷宮的規則和策略模型：？迷宮、迷宮的每一處城市間交通網問題算法：？交通網中要解決的問題？模型：？每一條通路、每一個路口綜合各種程序設計問題，抽取它具體的物理含義，可以得到幾種數學模型，例如：1、與數值計算相關的問題： 線性代數方程、非線性代數方程、常微分方程（計算機求解的問題就是計算數學要

5、研究的問題）2、與非數值計算相關的問題： 問題的表示和求解的方法，就是數據結構要討論的內容。數據結構的研究問題： 非數值數據之間的結構關系，及如何表示，如何存儲，如何處理。本課程討論的問題： 應用中常用的幾種數據間的結構關系，及如何表示,如何存儲，如何處理。1.1 數據結構討論的范疇數據：所有能輸入到計算機中,且被計算機處理的符號的集合， 是計算機操作對象的總稱； 是計算機處理的信息的某種特定的符號表示形式。 數據元素：數據中的一個“個體”,數據結構中討論的基本單位。 相當于“記錄”,在計算機程序中通常作為一個整體考慮和處理。 1.2 數據結構的有關概念數據項: 相當于記錄的“域”, 是數據的

6、不可分割的最小單位,如學號。數據元素是數據項的集合。例如：運動員（數據元素）數據對象：性質相同的數據元素的集合. 例如: 所有運動員的記錄集合姓名俱樂部名稱出生日期參加日期職務業績年月日1.2 數據結構的有關概念數據結構：是相互間存在某種關系的數據元素集合。例如：一個含有12位數的十進制數，可以用三個4位的十進制數表示 3214,6587,9345-a1(3124),a2(6587),a3(9345) 在a1,a2和a3之間存在“次序”關系，次序不能顛倒 a1,a2,a3 != a2,a1,a3數據結構是帶結構的數據元素的集合1.2 數據結構的有關概念又例：2行3列二維數組a1,a2,a3,a

7、4,a5,a6 行的次序關系： row=, 列的次序關系: col=,a1a2a3a4a5a6數據結構是帶結構的數據元素的集合1.2 數據結構的有關概念再例，一維數組a1,a2,a3,a4,a5,a6存在次序關系： |i=1,2,3,4,5,6不同的關系構成不同的結構數據結構是帶結構的數據元素的集合1.2 數據結構的有關概念對每種數據結構，主要討論如下兩方面的問題： 1） 數據的邏輯結構，數據結構的基本操作； 2） 數據的存儲結構，數據結構基本操作的實現；數據的邏輯結構： 數據之間的結構關系，是具體關系的抽象。數據結構的基本操作： 指對數據結構的加工處理數據的存儲結構 (物理結構)： 數據結構

8、在計算機內存中的表示數據結構基本操作的實現： 基本操作在計算機上的實現（方法)1.2 數據結構的有關概念 1數據的邏輯結構 2、數據的存儲結構 3、數據的運算：檢索、排序、插入、刪除、修改等。 A線性結構 B非線性結構A 順序存儲 B 鏈式存儲 線性表棧隊樹形結構圖形結構數據結構的三個方面 1.2 數據結構的有關概念 某班學生基本情況登記表，記錄了每個學生的學號 姓名 專業 政治 面貌 ，表中的記錄是按學生的學號順序排列的。 學號 姓名 專業 政治面藐 001 王洪 計算機 黨員 002 孫文 計算機 團員 003 謝軍 計算機 團員 004 李輝 計算機 團員 005 沈祥福 計算機 黨員

9、006 余斌 計算機 團員 007 鞏力 計算機 團員 008 孔令輝 計算機 團員學生基本情況登記表的圖示學生間學號順序關系是一種線性結構關系例一 常用的數據邏輯結構 1） 集合 2） 線性結構 3） 樹結構 4） 圖結構 5）其它復雜結構 001003002004006005008007數據結構的分類及表示 家族的族譜 假設某家族有10個成員A， B， C， D， E， F， G， H，I， J，他們之間的血緣關系可以用如下圖表示。例家族的成員之間是一種樹型結構關系JIACBDHGFE數據結構的分類及表示JIACBDHGFEJIACBDHGFEJIACBDHGFEJIACBDHGFE142

10、3 D= 1 , 2 , 3 , 4 R=(1,2) , (1,3) , (1,4) , (2,3) (3,4) , (2,4) 213 D= 1 , 2 , 3 R= (1,2) , (2,3) , (3,2) , (1,3) 圖形結構節點間的連結是任意的例數據結構的分類及表示二數據結構的表示 圖示表示 圖示表示是由頂點和邊構成的圖，其中頂點表示數據 ，邊表示數據之間的結構關系； 001003002004006005008007學生基本情況表的圖示表示家族樹的圖示表示數據結構的分類及表示JIACBDHGFE學生基本情況表的二元組表示（D，S） 二元組表示 二元組表示是用一個二元組（D，S）表

11、示數據結構， 其中 D 是數據元素集合，S 是 D 上關系的集合。D = 001，002，003，004，005，006，007，008S = R R= , , 001003002004006005008007數據結構的分類及表示 家族樹的二元組表示（D，S） D = A，B，C，D，E，F，G，H，I，J S = R R = A,B, JIACBDHGFE.數據元素的映像方法：用二進制位(bit)的位串表示數據元素（321）10=(501)8=(101000001)2 A=(101)8=(001000001)2三 數據的存儲結構邏輯結構在存儲器中的映像2.關系的映像方法：（表示的方法） 有序

12、對是關系的基本單位，關系的映像就是有序對的映像JIACBDHGFE元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內容Loc(a)=Lo+（i-1)*m順序存儲每個元素所占用的存儲單元個數以存儲位置的相鄰來表示后繼關系y的存儲位置和x的存儲位置的次序關系數據的存儲結構元素n.元素i.元素2元素1存儲內容順序存儲結構常用于線性數據結構，將邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元里。順序存儲結構的三個弱點：1.作插入或刪除操作時，需移動大量元數。2.長度變化較大時，需按最大空間分配。3.表的容量難以擴充。數據的存儲結構1536元素21400元素11

13、346元素3 元素41345h 鏈式存儲 每個節點都由兩部分組成：數據域和指針域。數據域存放元素本身的數據，指針域存放指針。數據元素之間邏輯上的聯系由指針來體現。數據的存儲結構1536元素21400元素11346元素3 元素4head 1346 元素3 1536 . . . 1536 元素2 1400 . . . 元素4 1346 1400 元素1 1345 指針 存儲內容存儲地址 鏈式存儲 1345數據的存儲結構1536元素21400元素11346元素3 元素41345h 鏈式存儲 1.比順序存儲結構的存儲密度小 (每個節點都由數據域和指針域組成)。2.邏輯上相鄰的節點物理上不必相鄰。3.插

14、入、刪除靈活 (不必移動節點，只要改變節點中的指針)。鏈接存儲結構特點：數據的存儲結構 在不同的編程環境中，存儲結構可有不同的描述方法。 當用高級程序設計語言進行編程時，通常可用高級語言中提供的數據類型描述之。例如： 以三個帶有次序關系的整數表示一個長整數，可以利用C語言中提供的整數數組類型，定義長整數為： Typedef int long_int3 一、數據類型 在用高級程序語言編寫的程序中，必須對程序中出現的每個變量、常量或表達式，明確說明它們所屬的數據類型。1.3 抽象數據類型的表示與實現例如，C 語言中提供的基本數據類型有:整型 int浮點型 float字符型 char邏輯型 bool

15、 （ C+語言）雙精度型 double實型（ C+語言）數據類型 數據類型 是一個值的集合和定義在此集合上的一組操作的總稱。 不同類型的變量，其所能取的值的范圍不同，所能進行的操作不同。數據類型二、抽象數據類型 (Abstract Data Type 簡稱ADT) 是指一個數學模型以及定義在此數學模型上的一組操作。抽象數據類型例如，抽象數據類型復數的定義： 數據對象： De1,e2e1,e2RealSet 數據關系： R1 | e1是復數的實數部分 | e2 是復數的虛數部分 ADT Complex 抽象數據類型基本操作： AssignComplex( &Z, v1, v2 )操作結果：構造復

16、數 Z,其實部和虛部 分別被賦以參數 v1 和 v2 的值。 DestroyComplex( &Z)操作結果：復數Z被銷毀。 GetReal( Z, &realPart)初始條件：復數已存在。操作結果：用realPart返回復數Z的實部值。抽象數據類型 GetImag( Z, &ImagPart )初始條件：復數已存在。操作結果：用ImagPart返回復數Z的虛部值。 Add( z1,z2, &sum )初始條件：z1, z2是復數。操作結果：用sum返回兩個復數z1, z2 的和值。 ADT Complex抽象數據類型假設:z1和z2是上述定義的復數則 Add(z1, z2, z3) 操作的

17、結果z3 = z1 + z2即為用戶企求的結果抽象數據類型ADT 有兩個重要特征:數據抽象 用ADT描述程序處理的實體時，強調的是其本質的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。數據封裝 將實體的外部特性和其內部實現細節分離，并且對外部用戶隱藏其內部實現細節。抽象數據類型抽象數據類型的描述方法抽象數據類型可用（D，S，P）三元組表示。其中：D 是數據對象； S 是 D 上的關系集； P 是對 D 的基本操作集。 抽象數據類型ADT 抽象數據類型名 數據對象：數據對象的定義 數據關系：數據關系的定義 基本操作：基本操作的定義 ADT 抽象數據類型名其中基本操作的定義格

18、式為:基本操作名（參數表） 初始條件：初始條件描述 操作結果：操作結果描述 抽象數據類型賦值參數 只為操作提供輸入值。引用參數 以&打頭，除可提供輸入值外，還將返回操作結果。初始條件 描述了操作執行之前數據結構和參數應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息。操作結果 說明了操作正常完成之后，數據結構的變化狀況和應返回的結果。若初始條件為空，則省略之。抽象數據類型 抽象數據類型需要通過固有數據類型(高級編程語言中已實現的數據類型)來實現。例如，對以上定義的復數。typedef struct float realpart； float imagpart；complex；/ -存儲結構

19、的定義/ -基本操作的函數原型說明void Assign( complex &Z, float realval, float imagval )；/ 構造復數 Z,其實部和虛部分別被賦以參數 / realval 和 imagval 的值float GetReal( cpmplex Z )； / 返回復數 Z 的實部值float Getimag( cpmplex Z )； / 返回復數 Z 的虛部值void add( complex z1, complex z2, complex &sum )； / 以 sum 返回兩個復數 z1, z2 的和 / -基本操作的實現void add( compl

20、ex z1, complex z2, complex &sum ) / 以 sum 返回兩個復數 z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 其它省略 我們各章都是從抽象數據類型的角度開始討論數據結構，數據結構和它的操作是一個整體。一 算法的概念 算法是求解問題的操作序列 算法的基本特征：1）有輸入；2）有輸出；3）有窮性；4）確定性；5）可行性。 求兩個正整數 m，n 中的最大數MAX的算法 （1）若 m n 則 max=m （2）若 m = n 則

21、 max=n 例1.4 算法與算法分析.有窮性對于任意一組合法輸入值，在執行有窮步驟之后，一定能結束。即：算法中的每一個步驟都能在有限的時間內完成。.確定性在每種情況下所應執行的操作，在算法中都有確定的規定，使算法的執行者或閱讀者都能明確其含義及如何執行。并且在任何條件下，算法都只有一條執行路徑。.可行性算法中的所以操作都必須足夠基本，都可以通過已經實現的基本操作運算有限次實現之。4.有輸入作為算法加工對象的量值，通常體現為算法中的一組變量，有些輸入量需要在算法執行過程中輸入，而有的算法表面上可以沒有輸入，實際上已經被嵌入算法之中。5.有輸出它是一組與“輸入” 有確定關系的量值，是算法進行信息

22、加工后得到的結果，這種確定關系即為算法的功能。描述算法的書寫規則所有算法均以函數形式給出, 算法的輸入數據來自參數表參數表的參數在算法之前均進行類型說明有關結點結構的類型定義,以及全局變量的說明等均在算法之前進行說明評價算法標準（設計算法時，通常要考慮到達的目標） 算法的正確性，可讀性，可維護性，健壯性等.二、算法效率的衡量方法和準則 通常有兩種衡量算法效率的方法 （1）事后統計的方法 缺點：1、必須執行程序 2、其他因素掩蓋算法本質 （2）事前分析估算的方法與算法執行時間相關的因素：算法選用的策略問題的規模編寫程序的語言編譯程序產生的機器代碼的質量計算機執行指令的速度一個特定算法的“運行工作

23、量”的大小，只依賴于問題的規模（通常用整數n表示），或者說，它是問題規模的函數。假如，隨著問題規模n的增長，算法執行時間的增長率和f(n)的增長率相同。則可記作：T(n)=O(f(n)1.4 算法與算法分析如何估算算法的漸進時間復雜度： 算法控制結構原操作（固有數據類型的操作） 算法的執行時間原操作（i）的執行次數原操作（i）的執行時間（定值，可忽略） 算法的執行時間與原操作執行次數之和成正比，通稱為算法的時間復雜度。1 算法時間復雜度T（n） 從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作在算法中重復執行的次數作為算法運行時間的衡量標準。1.4 算法與算法分析O（n3）

24、 稱為矩陣相乘算法時間復雜度；O（n3）表示矩陣相乘算法執行時間與n3成正比, 即O（n3）與n3 同一數量級； n 階矩陣相乘的算法For ( i = 1; i=n; i+ ) For (j = 1; j=n; j+ ) c i j = 0 ; For (k = 1; k= n; k+ ) c i j += a i k * b k j 乘法 加法執行次數均為 n3 例 矩陣相乘的基本運算：乘法 加法；1.4 算法與算法分析 有些算法，基本操作執行次數與問題的輸入數據有關，這時可考慮 （1） 算法平均時間復雜度 （2） 算法在最壞情況下的時間復雜度 100元買100支筆, 其中鋼筆 3元/支, 圓珠筆 2元/支, 鉛筆 0.5元/支. 寫算法輸出各種組合方案。例?解法1 #define N 100void scheme() int i, j, k, count, money; for (i = 0; i=N; i+ ) for (j = 0; j=N; j