《數據結構課件.ppt》由會員分享，可在線閱讀，更多相關《數據結構課件.ppt(750頁珍藏版)》請在人人文庫網上搜索。

1、數 據 結 構,2 數據結構題集 ( C語言版) 嚴蔚敏 吳偉民 清華大學出版社, 參考教材 1 數據結構 ( C語言版) 嚴蔚敏 吳偉民 清華大學出版社,教學目錄,第一章 緒論 第二章 線性表 第三章 棧和隊列 第四章 串 第五章 數組和廣義表 第六章 樹和二叉樹 第七章 圖 第八章 動態存儲管理 第九章 查找 第十章 內部排序,第一章 緒論,第一章 緒論 1.1 本課程的研究對象； 1.2 數據結構的有關基本概念； 1.3 數據結構的分類及表示； 1.4 算法及算法分析(算法評價),1.1 本課程研究的問題,計算機的發展 硬件： 性能、容量、價格 應用領域：數值計算、非數值計算,數據處理的。

2、種類和能力,數值數據,非數值數據,數 (整數,實數) 字符、字符串、文字、圖形、圖象、聲音, 應用實例,已知：游泳池的長len和寬wide，求面積area,設計 求解問題的方法 編程main ( ) int len, wide ,area ;scanf (“%d %d%n”, , 建模型：問題涉及的對象：游泳池的長len,寬wide,面積area；對象之間的關系：area=lenwide,例1(數值問題),例2(非數值問題),在這類文檔管理的數學模型中, 計算機處理的對象之間通常存在著一種最簡單的線性關系 , 這類數學模型稱為線性模型。,已知某級學生情況 , 要求作如下操作： 1)查找姓名為李。

3、梅的學生的信息 2)查找學號為00202的學生的信息 3)分班按入學成績排列順序。,學號 姓名 性別 出生日期 籍貫 入學成績 所在班級 00201 楊潤生 男 82/06/01 廣州 561 00計算機200102 石磊 男 83/12/21 汕頭 512 00計算機100202 李梅 女 83/02/23 陽江 532 00計算機2 00301 馬耀先 男 82/07/12 廣州 509 00計算機3,例3 迷宮問題,在迷宮問題中，每走一步，下面的走法都會有三種可能，所有的可能試驗完畢，形成一棵樹,兩點間最短路經問題 關鍵點問題 連通問題,例4 城市間交通網問題,數據結構的研究問題 非數值。

4、數據之間的結構關系， 及如何表示，如何存儲，如何處理。,結 論,1.2 數據結構的有關概念,數據： 客觀對象的符號表示。 例如：學號，姓名，班名都是數據。 數據元素： 數據的基本單位。相當于“記錄”,在計算機程序 中通常作為一個整體考慮和處理。又稱結點、 表目等等 數據項: 相當于記錄中的“域”, 是數據的不可分割 的最小單位,如學號 數據對象： 性質相同的數據元素的集合. 例如: 所有班名相同的記錄集合,1.2 數據結構的有關概念,數據的邏輯結構： 數據之間的結構關系，是現實中具體關系的抽象。,數據結構:,數據結構的基本操作： 指對數據結構的加工處理,數據的存儲結構 (物理結構)： 數據結構。

5、在計算機內存中的表示,數據結構基本操作的實現： 基本操作在計算機上的實現(方法),數據結構的概念主要涉及以下基本概念：,數據的邏輯結構,關系： 非空集合X上的一個關系r是指X的笛卡爾乘積 上的一個子集合。即 例如： X是我們全班同學的集合。X上同鄉關系 X是數學系全體老師和同學構成的集合。X上的師生關系 實數集合上的小于“”關系。,兩個概念,設r是X上的一個關系。X的兩個元素x , y如果滿足r，則稱x和y有關系r。同時稱x是y在關系r下的前驅，稱y是x在關系r下的后繼。 一些特殊的關系：反身性、對稱性、傳遞性、反對稱性等,數據的邏輯結構的定義：,數據的邏輯結構是一個二元組(D，R)，其中D是。

6、數據元素的非空有限集，R是D上關系的有限集。即,在這個課程里，我們經常遇到的情況是：關系集R只包含一個關系,1) 集合 2) 線性結構 3) 樹結構 4) 圖結構 5)其它復雜結構,某班學生基本情況登記表，記錄了每個學生的學號 姓名 專業 政治 面貌 ，表中的記錄是按學生的學號順序排列的。,學號 姓名 專業 政治面藐 001 王洪 計算機 黨員 002 孫文 計算機 團員 003 謝軍 計算機 團員 004 李輝 計算機 團員 005 沈祥福 計算機 黨員 006 俞斌 計算機 團員 007 鞏力 計算機 團員 008 孔令輝 計算機 團員,學生基本情況登記表的圖示,學生間學號順序關系 是一種。

7、線性結構關系,例,常用的數據結構,邏輯結構的分類及表示,家族的族譜 假設某家族有10個成員A，B，C，D，E，F，G， H，I， J，他們之間的血緣關系可以用如下圖表示。,邏輯結構的分類及表示:樹結構,例,家族成員之間 構成的這種關系 稱為樹型結構,邏輯結構的表示,圖示表示 圖示表示是由頂點和邊構成的圖，其中頂點表示結點數據 ，邊表示數據之間的結構關系；,學生基本情況表的圖示表示,家族樹的圖示表示,D = 001，002，003，004，005，006，007，008 R = r r= , , ,學生基本情況表的二元組表示(D，R),家族樹的二元組表示(D，R),D = A，B，C，D，E，F。

8、，G，H，I，J R = r r = A,B, , ,其他表示法:,包含法:,凹入法:,A,B,C,D,數據的存儲結構,數據在計算機中的表示稱為數據的物理結構，又稱為數據的存儲結構。,存儲結構分為順序存儲結構和鏈式存儲結構。,在高級語言中，常常使用數據類型這個概念來作為高級語言中描述存儲結構的工具。,數據類型,數據類型是一個值的集合以及定義在這個集合上的一組操作的總稱。,按照值是否可以分解的特性，數據類型分為原子類型和結構類型兩大類。,抽象數據類型ADT(Abstract Data Type),數據類型 數據類型是一個值的集合和定義在這個集合上的一組操作的總稱 抽象數據類型 抽象數據類型是指一。

9、個數學模型以及定義在該模型上的一組操作。,抽象數據類型的定義僅取決于它的一組邏輯定義，而與其在計算機內部如何表示無關，即不論其在計算機內部如何表示，只要它的數學特性不變都不影響其外部的描述,抽象數據類型的定義規則,抽象數據類型ADT采用如下三元組進行描述 ( D，S，P ) 其中D是數據對象，S是D上的關系集，P是對D的基本操作的集合，格式如下：,ADT 抽象數據類型名 數據對象：數據對象的定義 ； 數據關系：數據關系的定義； 基本操作：基本操作的定義 ADT 抽象數據類型名；,例：抽象數據類型三元組的定義,ADT Triplet 數據對象：D= e1,e2,e3 | e1,e2,e3Elem。

10、Set； 數據關系：R=, ; 基本操作： InitTriplet(,求兩個正整數 m，n 中的最大數MAX的算法 (1)若 m n 則 max=m (2)若 m = n 則 max=n,一、算法的概念 算法是求解問題的操作序列,算法的基本特征： 1)輸入：0個或多個輸入； 2)輸出：1個或多個輸出； 3)有窮性：算法必須在有限步內結束； 4)確定性：組成算法的操作必須清晰無二義性。 5)可行性：組成算法的操作必須能夠在計算機上實現。,例,算法設計的要求,正確性算法應能滿足具體問題的要求 可讀性便于交流和維護 健壯性對各種輸入都能做出正確的反應 高效率和低存儲算法要速度快、效率高，對存儲需求盡。

11、可能的低,描述算法的書寫規則,所有算法均以函數形式給出, 算法的輸入數據來自參數表 參數表的參數在算法之前均進行類型說明 有關結點結構的類型定義,以及全局變量的說明等均在算法之前進行說明,算法書寫的規范(習題集),算法說明：在算法頭部以注視的形式對算法進行說明。其中包括算法的功能、參數的含義、輸入和輸出、對外部變量的引用等信息。 適當的加入注釋:注釋可以大大地增加算法的可讀性。,合理地設計輸入和輸出：算法的輸入和輸出主要通過以下三種方式來完成：一是通過scanf和printf之類的語句實現；其次是通過函數頭部的參數表實現；第三是通過全局變量或外部變量實現。 合理地使用函數返回值進行錯誤處理 基。

12、本運算的使用除非題目中允許使用某一個數據結構中的基本運算來編寫算法，否則算法中用到的所有基本運算都應該實現,算法書寫的規范,算法效率的度量,事后統計方法缺陷：必須先運行程序；依賴外部環境 事先分析估計一般情況下，算法中基本操作重復執行的次數是問題規模n的某個函數f(n)，算法的時間度量記作 T(n)=O(f(n)稱作算法的漸進時間復雜度，簡稱時間復雜度。,度量一個算法的效率通常有兩種方法：,O(n3 ) 稱為矩陣相乘算法時間復雜度； O(n3)表示矩陣相乘算法執行時間與n3成正比, 即O(n3)與n3 同一數量級；,n 階矩陣相乘的算法,For ( i = 1; i=n; i+ ) For (。

13、j = 1; j=n; j+ ) c i j = 0 ; For (k = 1; k= n; k+ ) c i j += a i k * b k j ,例,矩陣相乘的基本運算：乘法、加法；,有些算法，基本操作執行次數與問題的輸入數據有關，這時可考慮 (1) 算法平均時間復雜度 (2) 算法在最好和最壞情況下的時間復雜度,算法的時間復雜度 一般來說，設算法中基本操作的執行次數是問題規模n的某個函數f(n)，算法的時間復雜度記作： T(n) = O(f(n) 它表示隨問題規模n的增大，算法執行時間的增長率與f(n) 的增長率相同。,14 算法與算法分析,算法的時間復雜度為O (N3),解法2,# 。

14、define N 100 Void scheme( ) int i, j; for (i=0; i=N/3; i+) for (j=0; j=(N-3*i)/2; j+) if (3*i+2*j+0.5*(N-i-j)= =N) printf(“%d, %d, %dn%”, i, j, N-i-j); 時間復雜度為O(N2 ),14 算法與算法分析,2 算法空間復雜度 在本課程中，用執行算法所需的輔助空間的大小作為算法所需空間的度量。 設執行算法所需的輔助空間是問題規模n的某個函數g(n),則算法空間復雜度記作： S(n)= O(g(n),表示算法輔助空間的增長率 與g(n) 的增長率相同,空。

15、間復雜度舉例,計算 解法1： 先計算x 的冪, 存于power 中,再分別乘以相應的系數 # define N 100 float evaluate (float coef , float x , int n ) float powerN, f; int i; for (power 0=1, i = 1; i=n; i+ ) poweri=x*poweri-1; for (f = 0, i=0; i=N; i +) f=f+coefi*poweri; return(f); ,問題規模為n, 算法時間復雜度: O(n) 空間復雜度： O(N),解法2 # define N 100 float e。

16、valuate (float coef , float x , int n ) float f; int i; for (f = coefn, i=n-1; i=0; i -) f=f*x+coefi; return(f); 時間復雜度為O(n). 空間復雜度為O(1),返回目錄,第二章 線性表,線性表是最簡單常用的數據結構，順序存儲結構 鏈式存儲結構也是應用中最常用的存儲方法，這一部分內容和方法掌握了，有助于理解和掌握后續章節的內容，如棧隊列串是特殊的線性表，數組和廣義表是線性表的擴展；有助于理解和掌握樹和圖等復雜的數據結構 存儲結構和圖等復雜結構的操作算法，因為樹和圖的存儲結構大多或是這兩。

17、種存儲結構的擴充，或是它們的組合，因此這一章的內容非常重要，同學們要很好地學習理解和掌握。,2.1 線性表概念及基本操作 2.2 線性表的順序存儲和實現 2.3 線性表的鏈式存儲和實現 2.3.1 線性鏈表 2.3.2 循環鏈表 2.3.3 雙向鏈表 2.4 一元多項式的表示及相加,例子：,2. 1 線性表的概念(實例),例1、數學中的數列(11，13，15，17，19，21)例2、英文字母表(A, B, C, D, E Z )。例3、某單位的電話號碼簿。,線性表 的概念,說明：設 A=(a1, a2, . , an )是一線性表 1) 線性表的數據元素可以是各種各樣的，但同一線性表中的元素必。

18、須是同一類型的； 2)在表中 ai-1 領先于ai ，ai 領先于ai+1 ，稱ai-1 是ai 的直接前驅，ai+1 是ai 的直接后繼； 3) 線性表中元素的個數n 稱為線性表的長度，n=0 時稱為空表；,線性表的概念,4)在線性表中，除第一個元素和最后一個元素之外，其他元素都有且僅有一個直接前驅，有且僅有一個直接后繼，具有這種結構特征的數據結構稱為線性結構。線性表是一種線性數據結構； 5)ai是線性表的第i 個元素，稱i 為數據元素ai 的序號，每一個元素在線性表中的位置，僅取決于它的序號；,2.1 線性表的定義,一、二元組表示 L= ，其中D= a1,a2, a3, . an R= r。

19、 r=, , 圖示表示,頂點：表示數據 邊：表示是數據間的順序結構關系,2.1 線性表的ADT定義,線性表的抽象數據類型定義： ADT List 數據對象：D=ai | aiElemSet,i=1,2, ，n,n 0 數據關系：R=r,其中 r= | a i-1,a i D, ,i=1,2, ，n 基本操作： InitList( Lb_len=ListLength(Lb); for(i=1;i=Lb_len;i+) GetElem(Lb,i,e); if(!LocateElem(La,e,equal) ListInsert(La,La_len+1,e); ,例2：,已知線性表LA和LB中的數據。

20、元素按值遞增有序排列,現在要求將LA和LB兩個線性表歸并為一個新的線性表LC，且LC中的數據元素仍然按遞增排序。 主要思路： 1)從頭到尾分別掃描LA和LB，設定兩個指針i,j指向LA和LB的相應位置。 2)i,j處的元素進行比較，小的插入到LC，相應指針后移。 3)處理剩下的尾巴,i LA: 1 5 19 50 55 70 LB 6 7 51 52 53 54 j LC: 1 5 6 7 19 51 52 53 k,例2算法(部分1)：,void MergeList(List La, List Lb, List /end while,例2算法(部分2)：,/掃尾處理 while(i=La_l。

21、en) GetElem(La, i, a); ListInsert(Lc, +k, a); while(j=Lb_len) GetElem(Lb, i, b); ListInsert(Lc, +k, b); /end MergeList,為了存儲線性表，至少要保存兩類信息：1)線性表中的數據元素；2)線性表中數據元素的順序關系；,2.2 線性表的順序存儲和實現 一 線性表的順序存儲結構順序表 二 順序表的基本操作算法 三 效率分析,線性表的順序存儲結構，就是用一組連續的內存單元依次存放線性表的數據元素。,線性表(a1,a2, a3, . an ) 的順序存儲結構,用順序存儲結構存儲的線性表稱為。

22、順序表,2.2 線性表的順序存儲和實現,一 線性表的順序存儲結構順序表,線性表的順序存儲結構,2.2 線性表的順序存:地址,說明： 在順序存儲結構下，線性表元素之間的邏輯關系，通過元素的存儲順序反映(表示)出來； 假設線性表中每個數據元素占用 t 個存儲單元，那么，在順序存儲結構中，線性表的第i個元素的存儲位置與第1個元素的存儲位置的關系是： Loc(ai ) = Loc( a1 )+ ( i 1) t,2.2 線性表的順序存儲:C語言實現,可用C語言中的一維數組來表示,但數組不是線性表,數組存放的是線性表,數組的類型由線性表中的數據元素的性質決定.如: #define MAX 100 Ele。

23、mType vMAX;,2.2 線性表的順序存儲:C語言定義順序表,順序表的類型定義#define LIST_INIT_SIZE 100 / 線性表存儲空間的初始分配量 #define LISTINCREMENT 10 / 線性表存儲空間的分配增量typedef struct ElemType * elem; /線性表存儲空間基址 int length; /當前線性表長度 int listsize; /當前分配的線性表存儲空間大小 /(以sizeof(ElemType)為單位)SqList;,線性表的順序存儲,SqList ：類型名. SqList：類型的變量是結構變量，它的三個域分別是： *。

24、elem：存放線性表元素的一維數組基址；其存儲空間在初始化操作(建空表)時動態分配； length：存放線性表的表長； listsize：用于存放當前分配(存放線性表元素)的存儲空間的大小。,2.2 線性表的順序存儲：圖示,存放線性表元素 的一維數組,設 A = (a1,a2 , a3 , . an )是一線性表，L是SqList 類型的結構變量，用于存放線性表A，則L在內存中的狀態如圖所示：,順序表通過 元素的存儲順序 反映線性表元素間的邏輯關系,初始化算法,Status InitList_Sq( SqList ,初始化算法(C程序),Status InitList_Sq( SqList *。

25、L) L-elem = (ElemType *) malloc( LIST_INIT_SIZE*sizeof(ElemType) ; if( !L-elem) exit (OVERFLOW) ; L-length = 0 ; L-listsize = LIST_INIT_SIZE ; return OK; ,2.2 插入算法,ADT定義：ListInsert( 3)表長-1,2.2 刪除算法,2.2 刪除算法(算法),int ListDelete_Sq ( SqList ,2.2 線性表的順序存儲和實現:時間復雜度,插入位置 移動元素個數 1 n 2 n-1 i n-i+1 n 1 n+1 0。

26、,算法時間復雜度分析 算法時間復雜度取決于移動元素的個數，移動元素的個數不僅與表長有關，而且與插入位置有關。,2.2 線性表的順序存儲和實現,由此可見在順序表中插入一個元素 ，平均要移動表的一半元素。表長為n的順序表，插入算法的時間復雜度為 O(n),假設在線性表的任何位置插入元素的概率相同，即 pi= 1/(n+1),pi:在第i個元素之前插入元素的概率，在長度為n的順序表中插入一個元素，所需移動元素個數數學期望值為：,兩個有序表的合并(順序存儲)(1),void MergeList_Sq(SqList La, SqList Lb, SqList ,兩個有序表的合并(順序存儲)(2),pa_。

27、last=La.elem+La.length-1 ; pb_last=Lb.elem+Lb.length-1 ; while(pa=pa_last ,2.2 線性表的順序存儲和實現(小結),順序表是線性表最簡單的一種存儲結構,2.3 線性表的鏈式存儲和實現,線性表的鏈式存儲結構是用一組任意的存儲單元存儲線性表的各個數據元素。由于存儲單元位置的隨機性，為了表示線性表中元素的先后關系，每個元素除了需要存儲自身的信息外還需保存直接前趨元素或直接后繼元素的存儲位置。,2.3 線性表的鏈式存儲和實現 2.3.1 線性鏈表 一 線性鏈表的概念 二 線性鏈表的基本操作算法 三 線性鏈表的其它操作 2.3.2。

28、 循環鏈表 2.3.3 雙向鏈表 一 雙向鏈表的概念 二 雙向鏈表的基本操作算法,一 線性鏈表的概念1 線性鏈表,2. 3. 1 線性鏈表,用一組任意的存儲單元存儲線性表中的數據元素，對每個數據元素除了保存自身信息外，還保存了直接后繼元素的存儲位置。,用線性鏈表存儲線性表時，數據元素之間的關系是通過保存直接后繼元素的存儲地址來表示的,結點：數據元素及直接后繼的存儲位置(地址)組成一個數據元素的存儲結構，稱為一個結點； 結點的數據域 ：結點中用于保存數據元素的部分; 結點的指針域 ：結點中用于保存數據元素直接后繼存儲地址的部分;,線性鏈表有關術語,2. 3. 1 線性鏈表,存儲數據元素,存儲后繼。

29、結點 存儲地址,2. 3. 1 線性鏈表,頭指針：用于存放線性鏈表中第一個結點的存儲地址;空指針：不指向任何結點，線性鏈表最后一個結點的指針通常是指針;頭結點：線性鏈表的第一元素結點前面的一個附加結點，稱為頭結點；帶頭結點的線性鏈表：第一元素結點前面增加一個附加結點的線性鏈表稱為 帶頭結點的線性鏈表；,head是頭指針,頭結點,空指針,head,線性鏈表的每個結點中只有一個指針域 故也稱為單鏈表,2. 3. 1 線性鏈表,怎樣在計算機上 實現線性鏈表？,？,2. 3. 1 線性鏈表,結點變量圖示,typedef struct LNode ElemType data; struct LNode 。

30、*next;LNode, *LinkList;,LNode：結構類型名； LNode類型結構變量有兩個域： data：用于存放線性表的數據元素， next：用于存放元素直接后繼結點的地址；該類型結構變量用于表示線性鏈表中的一個結點；LinkList p： p為指向結點(結構)的指針變量；,data next,LNode類型 結構變量,p是LNode類型的指針變量,線性鏈表的結點類型定義,2.3 線性鏈表,兩個C 函數1) malloc(int size) 功能：在系統內存中分配size個的存儲單元，并返回該空間的基址。使用方法： p = ( LinkList ) malloc(sizeof(L。

31、Node ); 為p申請一個結點,p,p = ( LinkList )malloc(sizeof(LNode); 圖示,2.2 線性鏈表,2) free ( p ) 功能：將指針變量p所指示的存儲空間，回收到系統內存空間中去,使用方法： . LinkList p; p = ( LinkList ) malloc (sizeof (LNode); / 一旦p所指示的內存空間不再使用， /調用free( ) 回收之 free(p);,2. 3. 1 線性鏈表,二 線性鏈表基本操作的算法,如何在線性鏈表 上實現線性表的基本操作？ 如何建表？如何插入？刪除？,？,約定用帶頭結點的線性鏈表 存儲線性表,。

32、2.3.1 線性鏈表,head,算法：LinkList InitList_L ( ) LinkList * head = (LNODE *) malloc( sizeof( LNODE ) ); head-next = null; return (head);,1)初始化操作 功能： 建空線性鏈表主要步驟：調用malloc ( )分配一結點的空間,并將其地址返回；,問題：把獲得的頭結點地址通過參數形式返回來，函數的頭部怎么寫？,建立鏈表,void CreateList_L(LinkList *L , int n) /*建立有n個結點的線性單鏈表的算法 L=(LinkList)malloc(si。

33、zeof(LNode); L-next=NULL; for(i=n;i0;-i) p= (LinkList ) malloc(sizeof(LNode); scanf( ,p,L,在單鏈表中結點p的后面插入結點q,q=(LinkList)malloc(sizeof(LNode); q-deta=a; q-next=p-next; p-next=q;,head,y,x,p,head,2. 3. 1 插入操作,插入操作主要步驟：1)查找鏈表L的第 i-1個元素結點；2)為新元素建立結點；3)修改第 i-1個元素結點的指針和新元素結點指針完成插入；,在鏈表L的第i個結點前面插入一個新結點,Statu。

34、s ListInsert_L(LinkList *L, int i, ElemType e) p=L; j=0; while (p!=NULL) ,刪除結點p的后繼結點,q=p-next; p-next=q-next; free(q);,head,y,x,q,head,p,p,2. 3. 1 線性鏈表,刪除操作主要步驟： 1)查找鏈表的第 i-1個元素結點,使指針p指向它, 將指針q指向第i個結點；2)修改第 i-1個元素結點指針，使其指向第i個元素結點的后繼；3) 回收q指針所指的第i個結點空間；,2. 3. 1 線性鏈表,刪除前,刪除后,p,p,q,q,在線性鏈表中刪除第i個結點 Stat。

35、us ListDelete_L(LinkList *L, int i, ElemType e) p=L; j=0; while (p!=NULL) ,三 線性鏈表的其他操作的實現,例：將兩個遞增有序線性鏈表歸并成一個遞減有序表。 設線性表A、B分別用頭指針為head_a 、 head_b 的兩個帶頭結點的線性鏈表存儲, 歸并后的遞減有序表頭指針為head, 將兩表數據較小的結點依次取出插入到新表,利用基本操作 直接對鏈表進行操作,線性鏈表歸并操作圖示,7,3,n,9,5,2,n,7,head_a,head_b,7,9,head,3,8,5,LinkList MergeList_L(LinkLi。

36、st La, LinkList Lb , LinkList *Lc) pa=La-next ; pb=Lb-next ; Lc=pc=La ; while( pa ,2. 3. 1 線性鏈表小結,線性鏈表是線性表的一種鏈式存儲結構,線性鏈表的特點 1 通過保存直接后繼元素的存儲位置來 表示數據元素之間的邏輯關系； 2 插入刪除操作通過修改結點的指針實現； 3 不能隨機存取元素；,1 循環鏈表的概念 循環鏈表是線性表的另一種鏈式存儲結構，它的特點是將線性鏈表的最后一個結點的指針指向鏈表的第一個結點 2 循環鏈表圖示,2. 4 單向循環鏈表,(a)非空表 (b)空表,2. 4 單向 循環鏈表,說明。

37、 在解決某些實際問題時循環鏈表可能要比線性鏈表方便些。如將一個鏈表鏈在另一個鏈表的后面； 循環鏈表與線性鏈表操作的主要差別是算法中循環結束的條件不是p或p-link是否為NULL,而是它們是否等于首指針； 對循環鏈表，有時不給出頭指針，而是給出尾指針,a,a1,an,給出尾指針的循環鏈表,q,2. 4 單向 循環鏈表(合并),b,a,a1,an,b1,bn,q,p,p,p=a-next; q=b-next; a-next=q-next; b-next=p; free(q);,含有尾指針的單鏈循環表,在含有尾指針的單鏈循環表中，由于能夠很快地找到單鏈表的頭和尾，使得在一些同時涉及到單鏈表的頭和尾。

38、的操作時會很方便。,1 雙向鏈表的概念,2. 5 雙向鏈表,雙向鏈表中，每個結點有兩個指針域，一個指向直接后繼元素結點，另一個指向直接前趨元素結點。,2.5 雙向鏈表,雙向鏈表圖示,head,typedef struct DuLNode ElemType data struct DuLNode *prior, *next; DuLNode , *DuLinkList;,在雙向鏈表中刪除結點時指針變化情況,在雙向鏈表中插入一個結點時指針的變化情況,p,p,2.5 雙向鏈表,3、雙向鏈表的基本操作算法,2.5 雙向鏈表,1)插入操作算法 (在p 所指結點之后插入q 結點的過程 ) q=(DuLin。

39、kList)malloc(sizeof (DuLNode); q-data=e; q-prior=p;q-next=p-next; p-next=q; (q-next)-prior=q;,2.5 雙向鏈表,2)刪除操作算法 (p-prior)-next=p-next; (p-next)-prior=p-prior; free(p);,2. 4 一元多項式的表示及相加,計算機 領域： P= (p0, p1, p2 , pn) Q= (q0, q1, q2, qm) R= (p0+q0, p1+q1, , pm+qm, pm+1, , pn ),P (x) = p0 + p1 x + p2 x2 。

40、+ + pn xn Q (x) = q0 + q1 x + q2 x2+ + qm xm 不失一般性，設mn 則兩個多項式相加可表為 R (x) = (p0 +q0) + (p1+q1) x + +(pn+qm)xm + pm+1 xm + +pn xn,一、一元多項式的表示 數學上：,24 一元多項式的表示及相加,例： S (x) = 1 + 3 x 1000 + 2 x 2000,非零系數指數線性表: (1,0), (3,1000), (2,2000),系數線性表( 1,0,0,3,0,0,2),例：求兩多項式的和多項式 A (x) = 7 +3 x + 9 x 8 + 5 x 17 B 。

41、(x) = 8 x + 22 x 7 9 x 8,C (x) = A (x) + B (x) = 7 + 11x +22 x 7 + 5 x 17,A=( (7,0),(3,1),(9,8),(5,17) B=( (8,1),(22,7),(-9,8) C=(7,0),(11,1),(5,17),2.4 指數與系數,1)系數與指數的數據類型定義 typedef struct float coef ; /存儲項系數 int expn; /存儲項指數 term,ElemType; typedef LinkList polynomial;,2 一元多項式鏈式存儲結構 為用線性鏈表表示一元多項式，我們。

42、要給出數據元素的類型定義,24 一元多項式的表示及相加,例：求兩多項式的和多項式 A (x) = 7 +3 x + 9 x 8 + 5 x 17 B (x) = 8 x + 22 x 7 9 x 8,三、一元多項式的相加算法,C (x) = A (x) + B (x) = 7 + 11x +22 x 7 + 5 x 17,一元多項式的相加,24 一元多項式的表示及相加,和多項式鏈表,設多項式A (x) ，B (x)分別用帶表頭結點的線性鏈表ah,bh表示，和多項式C (x)用帶表頭結點的線性鏈表ch表示,ch=ah+bh ah=ah+bh bh=ah+bh,24 一元多項式的表示及相加,一元多。

43、項式的相加算法圖示,24 算法思路(1),一元多項式加法算法主要步驟 1、分別同時對兩個鏈表Pa 、Pb進行掃描，設pa、qb 分別指向線性鏈表Pa 、 Pb的當前進行比較的某個結點,同時pa 所指結點為和多項式中的當前結點.比較過程中根據一下比較結果分別做如下操作: 1)pa-data.expn data.expn ： 操作：pa 后移，qa不動,24 算法思路(2),2 ) pa-data.expn = qb-data.expn ： sum =pa-data.coef + qb-data.coef; a) sum!=0: 修改pa-data.coef為x，pa后移； 刪除qb，qb后移； 。

44、b)sum=0: 刪除qa,qb;同時qa,qb,后移；,24 算法思路(3),3) pa-data.expn qb-data.expn ： 把qb插入到pa之前，刪除qb同時向后移動 2、循環結束后，如果qb非空，把尾巴鏈接到qa的后面,線性表小結,本章學習了線性表的順序存儲結構順序表，鏈式存儲結構,線性鏈表,循環鏈表, 雙向鏈表，以及在這兩種存儲結構下如何實現線性表的基本操作。這里再一次需要強調：本課程不僅要從概念和方法上了解每一種數據結構的邏輯結構和基本操作，更重要的是要學習如何在計算機上實現，即如何在計算機上存儲線性表，如何在計算機上實現線性表的操作。 對于某一實際問題，如何選擇合適的。

45、存儲結構，如何在某種存儲結構下實現對數據對象的操作。,返回目錄,第三章 棧和隊列,第三章 棧和隊列,本章介紹在程序設計中常用的兩種數據結構 棧和隊列,第三章 棧和隊列 3.1 棧 3.2 棧的應用舉例 3.3 棧與遞歸 3.4 隊列,3.1 棧 3.1 .1 棧的概念 3.1 .2 棧的順序存儲和實現 3.1 .3 棧的鏈式存儲和實現,3.1 棧,棧是限定僅能在表尾一端進行插入、刪除操作的線性表,(a1, a2, . , ai -1, ai , ai+1, , an ),插入,刪除,3.1.1 棧的概念 一 什么是棧,3.1 棧,棧的示意圖,出棧,進棧,棧的特點 后進先出,第一個進棧的元素在棧。

46、底，最后一個進棧的元素在棧頂， 第一個出棧的元素為棧頂元素， 最后一個出棧的元素為棧底元素,3.1 棧,二 棧的基本操作 1)InitStack( SElemType *top; int stacksize; SqStack;,棧的基本操作-初始化棧,Status InitStack(SqStack ,棧的基本操作-入棧,Status Push(SqStack ,棧的基本操作-出棧,Status Pop( SqStack ,3.1 棧,2 棧的鏈式存儲和實現 棧的鏈式存儲結構，也稱鏈棧，如圖所示：,在前面學習了線性鏈表的 插入刪除操作算法， 不難寫出鏈式棧初始化、 進棧、出棧等操作的算法,小 。

47、結 1 棧是限定僅能在表尾一端進行插入、 刪除操作的線性表； 2 棧的元素具有后進先出的特點； 3 棧頂元素的位置由一個稱為棧頂指針的 變量指示， 進棧、出棧操作要修改棧頂指針；,3.1 棧,3.2 棧的應用舉例,例1 數制轉換 對于輸入的任意一個非負十進制數，顯示輸出與其等值的八進制數,數制轉換方法 N = (Ndiv8)10 8+N mod 8 N：十進制數，div：整除運算，mod：求余運算； (1348)10 = 283+582+08+4 = (2504)8 N 1348 168 21 2 N div 8 168 21 2 0 N mod 8 4 0 5 2,計算時從低位到高位 順序產。

48、生八進制數的各個數位,結果： 2 5 0 4,顯示時按從高位到低位的 順序輸出,3.2 棧的應用舉例,void conversion( ) InitStack(s); /建空棧 scanf(“%d”, ,3.2 棧的應用舉例,例2 表達式求值 1)問題的提出 設計一個小計算器: 對鍵入的表達式進行求值。,高級語言中的賦值語句：變量=表達式；,2) 表達式的構成 操作數+運算符+界符(如括號) 3) 表達式的求值： 例 5+6 (1+2)- 4 按照四則運算法則，上述表達式的計算過程為： 5+6 (1+2)- 4=5+6 3- 4 = 5+18-4= 23-4=19,3.2 棧的應用舉例,1,2。

49、,3,4,4) 算符優先關系表 表達式中任何相鄰運算符c1、c2的優先關系有： c1c2：c1的優先級高于c2,算符間的優先關系表,注： c1 c2是相鄰算符， c1在左， c2在右,從左向右掃描表達式： 遇操作數保存； 遇運算符號cj與前面的剛掃描過的運算符ci比較 若cicj 則說明ci是已掃描的運算符中優先級最高者，可進行運算； 若ci = cj 則ci為(，cj 為 )，說明括號內的式子已計算完，需要消去括號；,舉例：5 + 4 (1 + 2) - 6,5 算符優先算法,5 + 4 (1 + 2) - 6,后面也許有優先級更高的算符,+,+,(,后保存的算符有優先級高,用兩個棧分別保存。

50、掃描過程中遇到的操作數和運算符,算符比較函數：Precede,Char Precede( char c1, char c2) int c_temp1, c_temp2; switch(c1) case * : case / : c_temp1=4; break; case + : case - : c_temp1=2; break; . . . . . . switch(c2) case * : case / : c_temp2=3; break; case + : case - : c_temp2=1; break; . . . . . . ,續,if (c_temp1c_temp2) re。

51、turn( ); ,3.2 算符優先算法,在算符優先算法中，建立了兩個工作棧。一個是OPTR棧，用以保存運算符一個是OPND棧，用以保存操作數或運算結果。 OperandType EvaluateExpression( ) /運算數棧，OP為運算符集合。 InitStack(OPTR); Push (OPTR, # ); InitStack(OPND); c=getchar( ); While(c!= # | GetTop(OPTR)!=#) if ( !In(c,OP)Push(OPND,c);c=getchar(); /不是運算符則進棧 else / In(w, OP)判斷c是否 是運算符。

52、的函數,3.2 算符優先算法(續),switch (Precede(GetTop(OPTR), c) case : /新輸入的算符c優先級低，即棧頂算符優先權高， /出棧并將運算結果入棧OPND Pop(OPTR，op); Pop(OPND，b); Pop(OPND，a); Push(OPND，Operate(a, op, b) ); break; return GetTop(OPND); ,表達式求值示意圖：5+6(1+2)-4,#,5,+,6,(,1,+,2,3,18,23,-,4,19,5,讀入表達式過程：,+,6,(,1,+,2,),-,4,#,=19,1+2=3,63=18,5+18。

53、=23,23-4=19,3.3 棧與遞歸,一般函數的調用機制,A( ) B( ); ,C( ) ,B( ) C( ); ,后調用的函數先返回,函數調用機制可通過棧來實現,計算機正是利用棧來實現函數的調用和返回的,3.3 棧與遞歸,1什么是遞歸 遞歸是一個很有用的工具，在數學和程序設計等許多領域中都用到了遞歸。 遞歸定義：簡單地說，一個用自己定義自己的概念,稱為遞歸定義。 例 n!= 1* 2* 3* 4 * * (n-1)* n n!遞歸定義 n!= 1 當 n=0 時 n!= n (n-1)! 當n 0 時,用(n-1)!定義n!,3.3 棧與遞歸,2 遞歸函數：一個直接調用自己或通過一系列。

54、調用間接調用自己的函數稱 為遞歸函數。,A( ) A( ) ; ,B( ) C( ) C( ); B( ); ,A 直接調用自己,B間接調用自己,3.3 棧與遞歸,2遞歸算法的編寫 1)將問題用遞歸的方式描述(定義) 2)根據問題的遞歸描述(定義)編寫遞歸算法 問題的遞歸描述(定義) 遞歸定義包括兩項 基本項(終止項)：描述遞歸終止時問題的求解； 遞歸項：將問題分解為與原問題性質相同，但規模較小的問題； 例 n!的遞歸定義 基本項： n!=1 當 n=0 遞歸項： n!=n (n-1)! 當 n 0,用(n-1)!定義n!,3.3 棧與遞歸,例1 編寫求解 階乘n! 的遞歸算法 首先給出階乘n。

55、! 的遞歸定義 n!的遞歸定義 基本項： n!=1 當 n=1 遞歸項： n!=n (n-1)! 當 n 1 int fact(int n) /算法功能是求解并返回n的階乘 if(n=1) return(1)； else return(n*fact(n-1))； ,3.3 棧與遞歸,我們看一下n=3 階乘函數fact(n)的執行過程,Main( ) int n=3,y; L y= fact(n); ,L 3,L1 1,L1 2,1,n*fact (n-1),n*fact (n-1),fact(n),返回地址 實參,注意遞歸調用中 棧的變化,3.4 隊列 3.4 .1 隊列的概念 3.4 .2 。

56、循環隊列 隊列的順序存儲和實現 3.4 .3 隊列的鏈式存儲和實現,34 隊列,3.4.1 隊列的概念 一 什么是隊列,隊列是限定僅能在表頭進行刪除，表尾進行插入的線性表,(a1, a2, . , ai -1, ai , ai+1, , an ),插入,刪除,34 隊列,a1 a2 a3 an,入隊列,隊頭,隊尾,出隊列,隊 列 的 示 意 圖,隊列的特點 先進先出(FIFO),第一個入隊的元素在隊頭，最后一個入隊的元素在隊尾， 第一個出隊的元素為隊頭元素， 最后一個出隊的元素為隊尾元素,34 隊列,二 隊列的基本操作 1)InitQueue( struct QNode *next; QNod。

57、e，*QueuePtr; typedef struct QueuePtr front;/隊頭指針 QueuePtr rear; /隊尾指針 LinkQueue;,3.4.2 鏈式隊列：常用算法-1,Statua InitQueue_L ( LinkQueue ,3.4.2 鏈式隊列：常用算法-2,Status DeQueue_L(LinkQueue ,3.4.3 循環隊列-隊列的順序存儲,使用一個數組存儲隊列,隊頭,隊尾,幾種情況：,3.4循環隊列,3 . 循環隊列,(b)隊空,(c)隊滿,隊空、隊滿 都有front=rear,J7,3.4.3 循環隊列:空和滿的識別,有兩種方法：1)另設一個。

58、標志位以區分隊空、隊滿。例如計數器2)少用一個存儲單元，隊滿條件:front=rear+1;,front,rear,3.4.3 循環隊列的定義,#define MAXQSIZE 100 typedef struct QElemType *base; int front; int rear; SqQueue;,3.4.3 循環隊列的基本操作,1)初始化操作 功能：建一個空隊列Q； 算法： Status Initqueue_Sq ( SqQueue ,3.4.3 循環隊列的基本操作,Status EnQueue_Sq(SqQueue return OK ,3. 4 隊列,7)出隊操作 功能：刪除隊。

59、頭元素；,3. 4 隊列,三 隊列的應用,1)解決計算機主機與外設不匹配的問題；2)解決由于多用戶引起的資源競爭問題；,3)離散事件的模擬-模擬實際應用中的各種排隊現象；4)用于處理程序中具有先進先出特征的過程；,在操作系統課程中會講到,3.5 離散事件模擬,問題：銀行業務模擬，統計一天內客戶在銀行的平均逗留時間：,已知條件： 1)銀行有4個業務窗口 2)客戶到來后，選擇排隊人數最少的窗口辦理業務或排隊。 3)客戶描述：到達時間、辦理業務需要的時間。,實現思路：,1)在系統中設定兩種事件：顧客到達事件和顧客離開事件。 2)事件的屬性：發生時間、事件類型。 3)所有已知將要發生的事件存儲到一個線。

60、性表(事件隊列)，線性表按照事件發生的時間有序。 4)事件驅動:當事件隊列不空時，處理事件隊列的隊頭元素代表的事件(一般處理、根據事件類型和條件隨機設定新的事件的發生時間),主控程序描述：,OpenForDay; /初始 while(事件隊列不空時) 獲取隊頭事件(事件發生的時間、事件類別); switch(事件類別) case 到達：處理到達事件;break; case 離開：處理離開事件;break; CloseForDay; /計算平均逗留時間,處理到達事件：,設定下一個顧客的到達事件(根據當前時間隨機產生下一個顧客的到達時間和辦理業務需要的時間)。如果沒有到關門時間，則把這個新事件保序。

61、地插入到事件隊列中。 計算各個窗口隊列的長度，到隊列長度最短的窗口排隊或辦理業務(產生該顧客的離開事件),處理離開事件：,統計時間 相應窗口的隊列隊頭元素出列。如果該隊列不空，則產生新的隊頭元素的離開事件。,數據類型定義,typedef structint OccurTime; /事件發生時刻int Ntype; /事件類型，0：到達事件，1-4四個窗口的離開事件 Event , ElemType; typedef LinkList EventList ; typedef struct int ArrivalTime ; /到達時刻int Duration ; / 辦理業務需要的時間 QEle。

62、mType; /隊列中的元素，顧客,主要變量,EventList ev ; /事件表 Event en ;/事件 LinkQueue q4 ;/4個隊列 QElemType customer ;/客戶 int TotalTime , CustomerNum ; /統計數據,OpenForDay(),Void OpenForDay() TotalTime = 0 ; Customer = 0 ; InitList_L(ev) ; en.OccurTime = 0 ; en.Ntype = 0; /第一個顧客 OrderInsert( ev , en) ;/保序插入 for( i=0 ; i4 ;。

63、 +i) InitQueue( qi) ; ,CustomerArrived(),void CustomerArrived()+CustomerNum ;Random( durtime , intertime) ;t = en.OccurTime + intertime ;if( tCloseTime ) OrderInsert( ev , (t,0) ) ; i=Minimun(q) ; EnQueue( qi , ( en.OccurTime , durtime ) ) ; if(QueueLength(qi) = 1) OrderInsert(ev ,(en.OccurTime+durtime, i。

總結

以上是生活随笔為你收集整理的C语言去括号编程题,数据结构课件.ppt的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。