軟件技術(shù)基礎(chǔ)

1、第二章第二章 基本數(shù)據(jù)結(jié)構(gòu)及其運算基本數(shù)據(jù)結(jié)構(gòu)及其運算第第 2 2 章章 基本數(shù)據(jù)結(jié)構(gòu)及其運算基本數(shù)據(jù)結(jié)構(gòu)及其運算（有（有 * * 號的標題表示最基本的內(nèi)容）號的標題表示最基本的內(nèi)容） 2.1數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念 * 2.1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)2.2 線性表線性表 2.2.1 線性表的基本概念線性表的基本概念 2.2.2 線性順序表及其運算線性順序表及其運算 2.2.3 線性鏈表及其運算線性鏈表及其運算 2.2.4 棧及其應(yīng)用棧及其應(yīng)用 2.2.5 隊列及其應(yīng)用隊列及其應(yīng)用教學(xué)內(nèi)容一、數(shù)據(jù)結(jié)構(gòu)概述一、數(shù)據(jù)結(jié)構(gòu)概述 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)

2、、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、 物理結(jié)構(gòu)、物理結(jié)構(gòu)、 算法、特征、評價算法、特征、評價二、順序表二、順序表 線性表、順序表、描述、線性表、順序表、描述、 創(chuàng)建、插入、刪除等算法創(chuàng)建、插入、刪除等算法三、鏈表三、鏈表 單鏈表、循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表單鏈表、循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表 判空、插入、刪除、定位等操作判空、插入、刪除、定位等操作 指針域、數(shù)據(jù)域、頭節(jié)點、頭指針指針域、數(shù)據(jù)域、頭節(jié)點、頭指針2.1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)n數(shù)據(jù)（數(shù)據(jù)（Data） 能存于計算機、并能被計算機處理的符號集合。能存于計算機、并能被計算機處理的符號集合。 它是客觀事物的一種符號表示。它是客觀事物

3、的一種符號表示。n數(shù)據(jù)元素（數(shù)據(jù)元素（Element） 是數(shù)據(jù)的基本單位、數(shù)據(jù)集合中的個體。是數(shù)據(jù)的基本單位、數(shù)據(jù)集合中的個體。n數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（Data Structure） 是帶有結(jié)構(gòu)特征的數(shù)據(jù)元素的集合；它有三個要素：是帶有結(jié)構(gòu)特征的數(shù)據(jù)元素的集合；它有三個要素： DS=數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)+存儲結(jié)構(gòu)存儲結(jié)構(gòu)+數(shù)據(jù)的運算數(shù)據(jù)的運算一一. .基本概念基本概念二二. . 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)概念概念：客觀事物本身存在的結(jié)構(gòu)形式及關(guān)系。：客觀事物本身存在的結(jié)構(gòu)形式及關(guān)系。特點特點：描述數(shù)據(jù)間的順序（邏輯）關(guān)系，抽象地反映數(shù)描述數(shù)據(jù)間的順序（邏輯）關(guān)系，抽象地反映數(shù)據(jù)元素的結(jié)

4、構(gòu)，而不管它們在計算機中如何存放。據(jù)元素的結(jié)構(gòu)，而不管它們在計算機中如何存放。 與物理存放位置無關(guān)與物理存放位置無關(guān)描述方法描述方法：用二元組來描述：用二元組來描述： DS=（D，R）其中：其中： D：是數(shù)據(jù)元素的有限集合；：是數(shù)據(jù)元素的有限集合； R：是數(shù)據(jù)元素之間關(guān)系的集合。：是數(shù)據(jù)元素之間關(guān)系的集合。成員：由成員：由1名教師、名教師、13名研究生、名研究生、16名本科生組成；名本科生組成；n成員關(guān)系是：教師指導(dǎo)研究生、研究生指導(dǎo)成員關(guān)系是：教師指導(dǎo)研究生、研究生指導(dǎo)12名名本科生。本科生。n數(shù)據(jù)結(jié)構(gòu)的形式化描述：定義數(shù)據(jù)結(jié)構(gòu)的形式化描述：定義DS如下：如下： Group=（D，R） 其中

5、：其中： D=T，G1，,Gn,S11,Snm 1 n 3 , 1 m 2 R=R1,R2 R1=|1 i n , 1 n 3 R2=|1 i n ,1 j m , 1 n 3 , 1 m 2 1. 1.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)- -舉例舉例n（1）線性結(jié)構(gòu)：一對一的次序關(guān)系）線性結(jié)構(gòu)：一對一的次序關(guān)系n（2）樹形結(jié)構(gòu)：一對多的層次關(guān)系）樹形結(jié)構(gòu)：一對多的層次關(guān)系n（3）圖或網(wǎng)狀結(jié)構(gòu)：多對多的關(guān)系）圖或網(wǎng)狀結(jié)構(gòu)：多對多的關(guān)系n（4）集合：屬性相同，元素間沒有關(guān)系）集合：屬性相同，元素間沒有關(guān)系2. 2.數(shù)據(jù)邏輯結(jié)構(gòu)的類別數(shù)據(jù)邏輯結(jié)構(gòu)的類別三、數(shù)據(jù)的存儲結(jié)構(gòu)三、數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)

6、是指數(shù)據(jù)結(jié)構(gòu)在計算機中的表數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在計算機中的表示示( (又稱映象又稱映象) )，即數(shù)據(jù)在計算機中的存放形式。，即數(shù)據(jù)在計算機中的存放形式。 邏輯結(jié)構(gòu)在存儲器中的映射，又稱物理結(jié)構(gòu)。邏輯結(jié)構(gòu)在存儲器中的映射，又稱物理結(jié)構(gòu)。數(shù)據(jù)存儲結(jié)構(gòu)分類數(shù)據(jù)存儲結(jié)構(gòu)分類1. 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)2. 鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)3. 索引存儲結(jié)構(gòu)索引存儲結(jié)構(gòu) （略）（略）4. 散列存儲結(jié)構(gòu)散列存儲結(jié)構(gòu) （略）（略）1. 1. 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)概念概念：把數(shù)據(jù)元素按某種順序存放在一塊連續(xù)的存：把數(shù)據(jù)元素按某種順序存放在一塊連續(xù)的存 儲單元中的存儲形式。儲單元中的存儲形式。數(shù)據(jù)結(jié)點結(jié)構(gòu)數(shù)

7、據(jù)結(jié)點結(jié)構(gòu): d1 d2 dn數(shù)據(jù)域數(shù)據(jù)域特點特點: : 連續(xù)存放；邏輯上相鄰連續(xù)存放；邏輯上相鄰, ,物理上也相鄰。物理上也相鄰。 結(jié)構(gòu)簡單，易實現(xiàn)。結(jié)構(gòu)簡單，易實現(xiàn)。 插入、刪除操作不便（需大量移動元素）。插入、刪除操作不便（需大量移動元素）。2. 2. 鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)概念概念：以鏈表形式將數(shù)據(jù)元素存放于任意存儲單元以鏈表形式將數(shù)據(jù)元素存放于任意存儲單元 中，可連續(xù)存放，也可以不連續(xù)存放，以指中，可連續(xù)存放，也可以不連續(xù)存放，以指 針實現(xiàn)鏈表間的聯(lián)系。針實現(xiàn)鏈表間的聯(lián)系。數(shù)據(jù)結(jié)點結(jié)構(gòu)數(shù)據(jù)結(jié)點結(jié)構(gòu): d1. d2dn 特點特點: : 非連續(xù)存放，借助指針來表示元素間的關(guān)系；非連續(xù)存

8、放，借助指針來表示元素間的關(guān)系； 插入、刪除操作簡單，只要修改指針即可；插入、刪除操作簡單，只要修改指針即可； 結(jié)構(gòu)較復(fù)雜，需要額外存儲空間。結(jié)構(gòu)較復(fù)雜，需要額外存儲空間。數(shù)據(jù)域數(shù)據(jù)域 指針域指針域 總結(jié)：（1）邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的關(guān)系 數(shù)據(jù)的數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是從邏輯關(guān)系（某種順序）上觀察數(shù)是從邏輯關(guān)系（某種順序）上觀察數(shù)據(jù)，它是獨立于計算機的；可以在理論上、形式上進據(jù)，它是獨立于計算機的；可以在理論上、形式上進行研究、推理、運算等各種操作。行研究、推理、運算等各種操作。 數(shù)據(jù)的數(shù)據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機中的實現(xiàn)，是依是邏輯結(jié)構(gòu)在計算機中的實現(xiàn)，是依 賴于計算機的；離開了計

9、算機，則無法進行任何操作。賴于計算機的；離開了計算機，則無法進行任何操作。 任何一個任何一個算法的設(shè)計算法的設(shè)計取決于選定的邏輯結(jié)構(gòu)；而取決于選定的邏輯結(jié)構(gòu)；而算法算法的最終實現(xiàn)的最終實現(xiàn)又依賴于所采用的存儲結(jié)構(gòu)。又依賴于所采用的存儲結(jié)構(gòu)。邏輯結(jié)構(gòu)：獨立于計算機；存儲結(jié)構(gòu)：依賴于計算機邏輯結(jié)構(gòu)：獨立于計算機；存儲結(jié)構(gòu)：依賴于計算機算法設(shè)計考慮邏輯結(jié)構(gòu)，算法實現(xiàn)依賴存儲結(jié)構(gòu)。算法設(shè)計考慮邏輯結(jié)構(gòu)，算法實現(xiàn)依賴存儲結(jié)構(gòu)。總結(jié)：（2）數(shù)據(jù)結(jié)構(gòu)分類線性表線性表堆棧堆棧隊列隊列串串?dāng)?shù)組數(shù)組樹樹二叉樹二叉樹圖圖線性結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)非線性結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)DSDS 2.2 線性表線性表2.2.1 2

10、.2.1 線性表的基本概念線性表的基本概念n線性表是指數(shù)據(jù)元素之間的關(guān)系為一一對應(yīng)的線性線性表是指數(shù)據(jù)元素之間的關(guān)系為一一對應(yīng)的線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 例如例如，一星期七天的英文縮寫表示：，一星期七天的英文縮寫表示： （Sun，Mon，Tue，Wed，Thu，F(xiàn)ri，Sat） 是一個線性表，其中的元素是字符串，表的長度為是一個線性表，其中的元素是字符串，表的長度為7。n 線性表雖然簡單，但是應(yīng)用范圍非常廣泛。線性表雖然簡單，但是應(yīng)用范圍非常廣泛。一、線性表的邏輯結(jié)構(gòu)一、線性表的邏輯結(jié)構(gòu)定義：定義： 線性表是線性表是n（n0）個元素）個元素a1,a2,an 的有限序的有限序列；表中

11、每個數(shù)據(jù)元素，除第一個外，有且只有一列；表中每個數(shù)據(jù)元素，除第一個外，有且只有一個前件；除最后一個外，有且只有一個后件。即線個前件；除最后一個外，有且只有一個后件。即線性表或是一個空表，或可以表示為性表或是一個空表，或可以表示為 ),.,.,(21niaaaa例如：例如：一一星期七天的英文縮寫表示：星期七天的英文縮寫表示： （Sun，Mon，Tue，Wed，Thu，F(xiàn)ri，Sat） 是一個線性表，其中的元素是字符串，表的長度為是一個線性表，其中的元素是字符串，表的長度為7。二、元素關(guān)系描述二、元素關(guān)系描述1）L的長度為的長度為n（n 0），當(dāng)），當(dāng)n為為0時，表示是時，表示是空表；空表； 2）

12、每個元素（除了第）每個元素（除了第1個和最后一個元素外），個和最后一個元素外），有唯一的前件和后件；有唯一的前件和后件；3）線性表中各元素間存在著線性關(guān)系；）線性表中各元素間存在著線性關(guān)系；4）均勻性；各元素數(shù)據(jù)類型必須相同；）均勻性；各元素數(shù)據(jù)類型必須相同；5）有序性；各元素是有序的，不可交換次序。）有序性；各元素是有序的，不可交換次序。2.2.2 2.2.2 線性順序表存儲結(jié)構(gòu)線性順序表存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu) 將表中元素一個接一個地存入一組連續(xù)的存儲單元將表中元素一個接一個地存入一組連續(xù)的存儲單元中，這種存儲結(jié)構(gòu)稱為順序存儲結(jié)構(gòu)中，這種存儲結(jié)構(gòu)稱為順序存儲結(jié)構(gòu)。順

13、序表順序表 采用順序存儲結(jié)構(gòu)的線性表簡稱為采用順序存儲結(jié)構(gòu)的線性表簡稱為“順序表順序表”。順序表的存儲特點：順序表的存儲特點：只要確定了起始位置，表中任只要確定了起始位置，表中任一元素的地址都可以通過下列公式得到：一元素的地址都可以通過下列公式得到： LOC（ai）=LOC（a1）+（i-1）*L 1 i n 其中，其中，L是每個元素占用存儲單元的長度是每個元素占用存儲單元的長度。一、定義一、定義二、線性表元素存儲示意圖二、線性表元素存儲示意圖 a1a2.ai.元素序號元素序號 內(nèi)存狀態(tài)內(nèi)存狀態(tài) 存儲地址存儲地址2 i1.LOC(a1)LOC(a1)+1L.LOC(a1)+(i-1)L.三、三

14、、 線性表的基本操作線性表的基本操作Setnull（L） 置空表置空表Length（L） 求表長度；求表中元素個數(shù)求表長度；求表中元素個數(shù)Get（L，i） 取表中第取表中第i個元素（個元素（1 i n）Prior（L，i） 取取i的前件元素的前件元素Next（L，i） 取取i的后件元素的后件元素Locate（L，x） 返回指定元素在表中的位置返回指定元素在表中的位置Insert（L，i，x）插入元素）插入元素Delete（L，x） 刪除元素刪除元素Empty（L） 判別表是否為空判別表是否為空1.1.插入算法插入算法線性表的存放形式線性表的存放形式：采用一維數(shù)組存放。：采用一維數(shù)組存放。操作要

15、求：操作要求：將將X插入線性表（插入線性表（a1,a2,an）中）中 的第的第i個位置個位置算法步驟算法步驟: step1 將第將第n至第至第i個元素后移一個存儲位置；個元素后移一個存儲位置； step2 將將x插入到插入到ai-1之后；之后； step3 表的長度加表的長度加1。長度為長度為n n的線性表中的第的線性表中的第i i個元素之前插入新元素個元素之前插入新元素b b。PROCEDURE INSL（V，m，n，i，b）IF（n=m）THENOVERFLOW；RETURNIF(in) THEN in1IF（i1)THEN i1FOR j=n TO i BY 1 DO V（j+1）=V（

16、j）V(i)=bnn1RETURN2.2.刪除算法刪除算法線性表的存放形式：采用一維數(shù)組存放。線性表的存放形式：采用一維數(shù)組存放。操作要求：操作要求：刪除線性表刪除線性表(a1,a2,an)中的第中的第i個元素個元素算法步驟算法步驟: step1 判別指定的位置是否合法；判別指定的位置是否合法； step2 若合法，則將位置若合法，則將位置i+1至至n上的元素前移一個存上的元素前移一個存儲位置儲位置; step3 表的長度減表的長度減 1。在長度為在長度為n n的線性表中刪除第的線性表中刪除第i i個元素個元素PROCEDURE DEL（V，m，n，i）IF（n=0）THENUNDERFLOW

17、；RETURNIF(in) THEN “Not this element in the list”；RETURNFOR j=i TO n-1 DO V（j）=V（j+1）nn-1RETURN總結(jié)：順序存儲結(jié)構(gòu)的優(yōu)缺點n數(shù)據(jù)連續(xù)存放、隨機存取數(shù)據(jù)連續(xù)存放、隨機存取n邏輯上相鄰，物理上也相鄰邏輯上相鄰，物理上也相鄰n存儲結(jié)構(gòu)簡單、易實現(xiàn)存儲結(jié)構(gòu)簡單、易實現(xiàn)n插入、刪除操作不便插入、刪除操作不便n存儲密度大，空間利用率高存儲密度大，空間利用率高： 順序存儲結(jié)構(gòu)適合于表中元素變動較少的情況。順序存儲結(jié)構(gòu)適合于表中元素變動較少的情況。 1. 線性表及相關(guān)概念和特征線性表及相關(guān)概念和特征 線性表、長度、空

18、表、前驅(qū)、后繼、線性表、長度、空表、前驅(qū)、后繼、 均勻性、有序性、形式化定義均勻性、有序性、形式化定義 2. 順序表順序表 概念、特征、描述概念、特征、描述 3. 順序表的操作順序表的操作 （1）判空、判滿、判合法）判空、判滿、判合法 ；（；（2）插入；（）插入；（3）刪除）刪除 。 4.順序表的優(yōu)缺點及適用場合順序表的優(yōu)缺點及適用場合n數(shù)據(jù)連續(xù)存放、隨機存取數(shù)據(jù)連續(xù)存放、隨機存取n邏輯上相鄰，物理上也相鄰邏輯上相鄰，物理上也相鄰n存儲結(jié)構(gòu)簡單、易實現(xiàn)存儲結(jié)構(gòu)簡單、易實現(xiàn)n插入、刪除操作不便插入、刪除操作不便n存儲密度大，空間利用率高存儲密度大，空間利用率高總結(jié)總結(jié)2.2.3 2.2.3 線性

19、表的鏈式存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)n線性表的順序存儲結(jié)構(gòu)容易實現(xiàn)，可以隨機存線性表的順序存儲結(jié)構(gòu)容易實現(xiàn)，可以隨機存取表中的任意元素。取表中的任意元素。n順序順序表表缺點是：缺點是：n難于插入、刪除操作；難于插入、刪除操作；n需要預(yù)先分配空間，不管這些空間能否最大限度地需要預(yù)先分配空間，不管這些空間能否最大限度地利用。利用。n鏈表存儲結(jié)構(gòu)鏈表存儲結(jié)構(gòu)在這兩個方面恰好是它的優(yōu)點：在這兩個方面恰好是它的優(yōu)點：n容易插入、刪除操作容易插入、刪除操作n不需要預(yù)分空間。不需要預(yù)分空間。一、鏈表的基本概念一、鏈表的基本概念定義定義 ： 線性表的鏈式存儲結(jié)構(gòu)稱為線性鏈表線性表的鏈式存儲結(jié)構(gòu)稱為線性鏈表 結(jié)

20、點（結(jié)點（NODE） ：表中元素的存儲單元。由數(shù)據(jù)域：表中元素的存儲單元。由數(shù)據(jù)域和指針域組成。數(shù)據(jù)域存放元素數(shù)據(jù)，指針域存和指針域組成。數(shù)據(jù)域存放元素數(shù)據(jù)，指針域存放指向下一結(jié)點位置的指針。放指向下一結(jié)點位置的指針。結(jié)點形式為：結(jié)點形式為： data next數(shù)據(jù)域 指針域鏈表（鏈表（Link）：）：由結(jié)點組成的表。由結(jié)點組成的表。頭指針（頭指針（head）：）：指向鏈表中第指向鏈表中第1個結(jié)點的指針。個結(jié)點的指針。 頭結(jié)點頭結(jié)點 ：為方便操作，在頭指針和第為方便操作，在頭指針和第1個結(jié)點之個結(jié)點之 間設(shè)置的結(jié)點。間設(shè)置的結(jié)點。首元結(jié)點首元結(jié)點 ：第一個結(jié)點（第一個結(jié)點（a1）。）。head

21、頭指針頭指針a1首元結(jié)點首元結(jié)點 ai.第第i i個結(jié)點個結(jié)點頭結(jié)點頭結(jié)點舉例舉例n由食品組成的單鏈表由食品組成的單鏈表（biscuit,butter,cheese,eggs,grapes,jam) 不帶頭結(jié)點。不帶頭結(jié)點。grapesbiscuitbuttercheesejameggshead 頭指針單鏈表的物理存儲單鏈表的物理存儲 存儲地址存儲地址 數(shù)據(jù)域（數(shù)據(jù)域（datadata） 指針域（指針域（nextnext）grapes 60biscuit 61cheese 13eggs 1jam NULLbutter 121111213606111頭指針頭指針 headheadl（biscui

22、t,butter,cheese,eggs,grapes,jam)二、二、C C語言實現(xiàn)語言實現(xiàn) struct node int data ; struct node *next ; ; typedef struct node NODE；設(shè)置頭結(jié)點的優(yōu)點是設(shè)置頭結(jié)點的優(yōu)點是表示形式的統(tǒng)一表示形式的統(tǒng)一空表和非空表表示形式在頭結(jié)點上得到統(tǒng)一空表和非空表表示形式在頭結(jié)點上得到統(tǒng)一空表的形式空表的形式 : head . next = NULL head頭結(jié)點頭結(jié)點head頭結(jié)點頭結(jié)點非空表的形式非空表的形式: head . Next = Address三、單鏈表的基本操作三、單鏈表的基本操作 1. 指

23、針的基本操作指針的基本操作2. 單鏈表的查找單鏈表的查找get3. 單鏈表的的插入單鏈表的的插入insert4. 單鏈表的刪除單鏈表的刪除delete1. 1. 指針的基本操作指針的基本操作n設(shè)指針變量設(shè)指針變量p、q的定義為：的定義為： NODE *p，*q；n對鏈表的操作實際上是對指針的操作。例如，對鏈表的操作實際上是對指針的操作。例如，要刪除結(jié)點要刪除結(jié)點ai，首先要使指針，首先要使指針p指向指向ai，即：，即：a1.headaianp指針指針p p是存儲單元的地址，地址內(nèi)的內(nèi)容可以通過是存儲單元的地址，地址內(nèi)的內(nèi)容可以通過V(pV(p) )得到，指向下個元素的指針用得到，指向下個元素的

24、指針用next(pnext(p) )得到。得到。2. 2. 指針基本操作的列表指針基本操作的列表np=（NODE*）malloc（sizeof（NODE） 申請一個結(jié)點空間，并將地址送入申請一個結(jié)點空間，并將地址送入p中。中。nfree（p） 釋放釋放p指針所指結(jié)點的空間指針所指結(jié)點的空間np=q 指針指針p指向指針指向指針q所指的結(jié)點所指的結(jié)點np=q-next 指針指針p指向指針指向指針q所指結(jié)點的后件所指結(jié)點的后件np=p-next 指針指針p向后移動一個結(jié)點向后移動一個結(jié)點 np-next=q 將指針將指針q所指結(jié)點改接為指針所指結(jié)點改接為指針p所指結(jié)點所指結(jié)點 的后件的后件np-ne

25、xt=NULL 將指針將指針p所指結(jié)點與后件結(jié)點斷開所指結(jié)點與后件結(jié)點斷開3. 3. 指針操作舉例指針操作舉例p=next(q) p指向指向q所指結(jié)點的后件所指結(jié)點的后件操作前狀態(tài)aiai-1ai+1qpaiai-1ai+1qp操作后狀態(tài)4. 4. 單鏈表的查找算法單鏈表的查找算法查找第查找第i個元素，返回指向它的指針個元素，返回指向它的指針算法操作步驟算法操作步驟:nstep1 初始化，指針初始化，指針P指向頭指針，指向頭指針， 計數(shù)器置計數(shù)器置0；nstep2 P非空且計數(shù)器小于非空且計數(shù)器小于i循環(huán)；循環(huán)；nstep3 每循環(huán)一次，每循環(huán)一次，P后移一個位置，后移一個位置， 計數(shù)器加計數(shù)

26、器加1；nstep4 循環(huán)結(jié)束，返回指向循環(huán)結(jié)束，返回指向ai 的指針的指針P。 NODE *get(NODE *head, int）(無頭結(jié)點無頭結(jié)點) NODE *p; int counter = 0; /計數(shù)器計數(shù)器 p=head; /p指向第指向第1個結(jié)點個結(jié)點 while(p!=NULL)&(counternext; counter+; /查找查找 if(p!=NULL)&(counter = i) return p; /找到找到 else return NULL; /沒找到?jīng)]找到 5. 5. 單鏈表插入算法單鏈表插入算法在第在第i個位置插入個位置插入算法操作步驟算法

27、操作步驟:nstep1 找到找到ai-1的位置，使指針的位置，使指針p指向指向ai-1nstep2 申請并生成新結(jié)點申請并生成新結(jié)點snstep3 使使s插入到插入到ai-1和和ai之間之間 s-next=p-next p-next=ss-data=x（3）（2）pxai-1ais（1） insert(NODE *head, int i, int x) NODE *p,*s; if(i=1) p=head; else p=get(head,i-1); if(p=NULL) printf(“插入位置錯插入位置錯n”); exit(0); else s=(NODE*)malloc(sizeof(N

28、ODE); s-data=x; s-next=p-next; p-next=s; /* 令令P指向指向A i-1 */* 若若i=1，P指向頭指針指向頭指針 */* P為空，說明找不到為空，說明找不到i位置位置 */* P定位成功定位成功 */* P定位操作定位操作*/ 6.單鏈表刪除算法算法算法1-4操作步驟操作步驟:nstep1 找到找到ai-1的位置，使指針的位置，使指針p指向指向ai-1；nstep2 使指針使指針t指向指向p所指結(jié)點的后繼；所指結(jié)點的后繼；nstep3 使使t所指結(jié)點所指結(jié)點ai 脫鏈；脫鏈；nstep4 釋放釋放t。a i-1aia i+1t=p-nextp-nex

29、t=t-nextfree(t)p1t23 delete(NODE *head, int i) NODE *p,*t; if(i=1) p=head; else p=get(head,i-1); if(p=NULL) printf(“i表長表長+1, 無此結(jié)點無此結(jié)點n”); exit(0); if(p-next=NULL) printf(“i=表長表長+1,無此結(jié)點無此結(jié)點n”); exit(0); else t = p- next; p-next = t-next; free(t) ; /* P定位操作定位操作*/* P定位成功定位成功 */四、循環(huán)單鏈表和雙向鏈表n鏈表檢索只能從頭指針開始

30、，且只能順鏈表方鏈表檢索只能從頭指針開始，且只能順鏈表方向移動。向移動。n在單鏈表中，從表的任一結(jié)點在單鏈表中，從表的任一結(jié)點ai找其前驅(qū)結(jié)點，找其前驅(qū)結(jié)點，時間復(fù)雜度是時間復(fù)雜度是O（n）。）。n如果讓鏈表首尾相接，構(gòu)成環(huán)形，這就是如果讓鏈表首尾相接，構(gòu)成環(huán)形，這就是單循單循環(huán)鏈表環(huán)鏈表。n如果在結(jié)點中增加一個指向前一個結(jié)點的指針如果在結(jié)點中增加一個指向前一個結(jié)點的指針域，鏈表可以從兩個方向檢索，效果更佳；這域，鏈表可以從兩個方向檢索，效果更佳；這就是就是雙向循環(huán)鏈表雙向循環(huán)鏈表。1. 循環(huán)單鏈表(1)單循環(huán)鏈表表示形式：單循環(huán)鏈表表示形式：headhead.a1a2an單循環(huán)鏈表為空的條件

31、單循環(huán)鏈表為空的條件: head .next=head表示形式為表示形式為:(2)單循環(huán)鏈表特點：單循環(huán)鏈表特點：n從表中任一結(jié)點出發(fā)，均可以找到表中其它結(jié)點。從表中任一結(jié)點出發(fā)，均可以找到表中其它結(jié)點。n找其前趨結(jié)點的時間復(fù)雜度是找其前趨結(jié)點的時間復(fù)雜度是O（n）。）。2. 雙向循環(huán)鏈表n在單向循環(huán)鏈表中，也存在檢索前驅(qū)結(jié)點費時的在單向循環(huán)鏈表中，也存在檢索前驅(qū)結(jié)點費時的問題（所需時間是問題（所需時間是O（n）。）。n雙向循環(huán)鏈表，其存儲結(jié)構(gòu)：雙向循環(huán)鏈表，其存儲結(jié)構(gòu)： struct dnode int data； struct dnode *prior，*next； ； typedef s

32、truct dnode DNODE；（1）雙向循環(huán)鏈表結(jié)點結(jié)構(gòu)指向后繼結(jié)點指針域數(shù)據(jù)域指向前驅(qū)結(jié)點指針域 prior data next（2）雙向循環(huán)鏈表表示形式雙向循環(huán)鏈表表示形式：雙向循環(huán)鏈表表示形式：headhead.ana2a1雙向循環(huán)鏈表為空的條件雙向循環(huán)鏈表為空的條件: head .prior = head .next = head表示形式為表示形式為:總結(jié):雙向循環(huán)鏈表特點n 適合于兩個方向的移動。適合于兩個方向的移動。n 找其前驅(qū)結(jié)點的時間復(fù)雜度是找其前驅(qū)結(jié)點的時間復(fù)雜度是O(1)。3. 鏈表結(jié)點及標識符約定：約定： 設(shè)指針設(shè)指針p指向結(jié)點指向結(jié)點ai ， ai作為一個變量，其

33、標識符為作為一個變量，其標識符為p 由于由于p 是記錄類型，它的分量分別表示為：是記錄類型，它的分量分別表示為： 數(shù)據(jù)域標識符為數(shù)據(jù)域標識符為 p .data 后繼結(jié)點指針域為后繼結(jié)點指針域為 p .next paip p .datap .nextai 鏈表結(jié)點及各分量標識符(雙鏈表)約定：約定： 設(shè)指針設(shè)指針p指向結(jié)點指向結(jié)點ai ， ai作為一個變量，其標識符為作為一個變量，其標識符為p p 的分量分別表示為：的分量分別表示為： 數(shù)據(jù)域標識符為數(shù)據(jù)域標識符為 p .data, 后繼結(jié)點指針域為后繼結(jié)點指針域為 p .next , 前驅(qū)結(jié)點指針域為前驅(qū)結(jié)點指針域為p .prior。a ai-

34、1i-1的標識符為的標識符為: p .prior，a ai-1i-1的數(shù)據(jù)域為的數(shù)據(jù)域為: p .prior .dataa ai+1i+1的標識符為的標識符為: p .next， a ai+1i+1的數(shù)據(jù)域為的數(shù)據(jù)域為: p . next .datapa i+1aia i-1五、 鏈表存儲結(jié)構(gòu)的特點n插入、刪除操作極為方便插入、刪除操作極為方便n數(shù)據(jù)非連續(xù)存放、順序存取數(shù)據(jù)非連續(xù)存放、順序存取n邏輯上相鄰，物理上不一定相鄰邏輯上相鄰，物理上不一定相鄰n存儲結(jié)構(gòu)較復(fù)雜、需要額外的存儲空間存儲結(jié)構(gòu)較復(fù)雜、需要額外的存儲空間結(jié)論結(jié)論： 鏈表存儲結(jié)構(gòu)適合于表中元素頻繁變動鏈表存儲結(jié)構(gòu)適合于表中元素頻繁

35、變動的線性表。的線性表。六、鏈表的動態(tài)生成n鏈表是一種動態(tài)存儲結(jié)構(gòu)。因此，建立鏈鏈表是一種動態(tài)存儲結(jié)構(gòu)。因此，建立鏈表的過程是動態(tài)生成的過程。按鏈表結(jié)點表的過程是動態(tài)生成的過程。按鏈表結(jié)點建立的順序、方向不同，分為兩種方法：建立的順序、方向不同，分為兩種方法：算法算法2-6）（算法（算法2-7）從前往后算法操作步驟：算法操作步驟：nstep1 初始化；頭指針置初始化；頭指針置NULLnstep2 輸入結(jié)點數(shù)據(jù)非輸入結(jié)點數(shù)據(jù)非0循環(huán)循環(huán) 1) 使使s指向新生成的結(jié)點，指向新生成的結(jié)點，s-data = num 2) 若若 head=NULL(第第1個結(jié)點個結(jié)點)，head=s 3) 否則否則 p

36、-next=s 4) 指針指針p始終指向始終指向s，p=snstep3 結(jié)束循環(huán)，結(jié)束循環(huán)，p-next =NULL，返回頭指針，返回頭指針head。.head ai-1a2a1s2p34 a i1從后往前step1 初始化；頭指針置初始化；頭指針置NULL，線性表元素存于，線性表元素存于AN中，中，i=N-1nstep2 i = 0 循環(huán)循環(huán) 1) 使使s指向新生成的結(jié)點，指向新生成的結(jié)點， 2) s-data = Ai，s-next = head 3) 指針指針s始終指向頭指針始終指向頭指針 head=sn step3 結(jié)束循環(huán)，返回頭指針結(jié)束循環(huán)，返回頭指針head。 head . sa

37、i-1aianai-1總結(jié)：總結(jié)： 1.單鏈表單鏈表 結(jié)點、指針域、數(shù)據(jù)域、頭指針、頭結(jié)點。結(jié)點、指針域、數(shù)據(jù)域、頭指針、頭結(jié)點。 2.單鏈表的描述單鏈表的描述 3.單鏈表的操作單鏈表的操作 （1）指針操作、指針說明、分配存儲空間、判空、）指針操作、指針說明、分配存儲空間、判空、判滿、釋放空間判滿、釋放空間 （2）查找操作）查找操作 （3）插入）插入 （4）刪除）刪除 4.單鏈表的特點及適用場合單鏈表的特點及適用場合 5.單循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表單循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表 描述、建立、判空、查找、插入、刪除描述、建立、判空、查找、插入、刪除2.2.4 棧及其應(yīng)用內(nèi)容提要一、棧

38、一、棧 棧、棧頂指針棧、棧頂指針順序存儲、共享棧、鏈棧、入棧、出棧操作順序存儲、共享棧、鏈棧、入棧、出棧操作二、隊列二、隊列 隊列、順序存儲、隊頭指針、隊尾指針、約定隊列、順序存儲、隊頭指針、隊尾指針、約定 循環(huán)隊列、鏈式隊列（帶頭結(jié)點）、入隊、出隊循環(huán)隊列、鏈式隊列（帶頭結(jié)點）、入隊、出隊三、數(shù)組：行、列優(yōu)先順序存儲，矩陣的壓縮存儲三、數(shù)組：行、列優(yōu)先順序存儲，矩陣的壓縮存儲2.2.4 棧及其應(yīng)用1. 1. 棧及相關(guān)概念棧及相關(guān)概念 堆棧堆棧(Stack)n棧是允許在同一端進行插入和刪除操作的特殊線性表。棧是允許在同一端進行插入和刪除操作的特殊線性表。 n允許進行插入和刪除操作的一端稱為允許

39、進行插入和刪除操作的一端稱為棧頂棧頂(top)，另一端，另一端為為棧底棧底(bottom)；棧底固定，而棧頂浮動；棧底固定，而棧頂浮動；n棧中元素個數(shù)為零時稱為棧中元素個數(shù)為零時稱為空?？諚！棧結(jié)構(gòu)也稱為后進先出表（棧結(jié)構(gòu)也稱為后進先出表（LIFO）。）。 棧、棧頂、棧底、空棧棧、棧頂、棧底、空棧后進先出表后進先出表 棧底固定，而棧頂浮動棧底固定，而棧頂浮動一、基本概念2.現(xiàn)實中的例子物料倉庫中的儲存物料倉庫中的儲存機器零部件的裝配與拆卸機器零部件的裝配與拆卸3. 棧有關(guān)概念棧頂指針棧頂指針 在棧操作過程中，有一個專門的棧指針在棧操作過程中，有一個專門的棧指針(習(xí)慣上稱它為習(xí)慣上稱它為TOP

40、)， 指出棧頂元素所在的位置。指出棧頂元素所在的位置。?？盏臈l件：?？盏臈l件：top = 0 (top=-1)棧滿的條件：棧滿的條件：top = MAXSIZE（ MAXSIZE-1）棧上溢棧上溢 ?？臻g是有限的，若棧已滿，再進行入棧操作時，就要產(chǎn)生上?？臻g是有限的，若棧已滿，再進行入棧操作時，就要產(chǎn)生上溢溢棧下溢棧下溢 若?？眨僖獔?zhí)行出棧操作，則會發(fā)生下溢若?？?，再要執(zhí)行出棧操作，則會發(fā)生下溢。二、棧的順序存儲結(jié)構(gòu)（1）棧的順序存儲結(jié)構(gòu)）棧的順序存儲結(jié)構(gòu)：實際上是一維數(shù)組。實際上是一維數(shù)組。（2）順序棧）順序棧：棧的順序存儲結(jié)構(gòu)稱為順序棧。棧的順序存儲結(jié)構(gòu)稱為順序棧。棧的操作只能在一端進行

41、；即棧頂位置隨進棧和出棧棧的操作只能在一端進行；即棧頂位置隨進棧和出棧而變化。而變化。（3）順序棧的）順序棧的C語言描述為語言描述為： #define MAXSIZE n int stackMAXSIZE; int top = -1; 三、棧的基本運算nSetNull（Stack） 置棧為空；置棧為空；nEmpty（Stack） 判定棧是否為空；判定棧是否為空；nPush（Stack，x）進棧操作，在棧頂插入元素；）進棧操作，在棧頂插入元素；nPop（Stack） 出棧操作，刪除棧頂元素；出棧操作，刪除棧頂元素；nGettop（Stack） 取棧頂元素取棧頂元素舉例（1） 有三個元素的進棧序列

42、是有三個元素的進棧序列是1，2，3。寫出可能的。寫出可能的出棧序列。出棧序列。 出棧序列 操作序列 1 2 3 s x s x s x 1 3 2 s x s s x x 2 1 3 s s x x s x 2 3 1 s s x s x x 3 2 1 s s s x x x棧操作舉例（2）棧底棧底棧頂棧頂a1 a2 anMAXSIZETOPtop=-11.(空?？諚? A B C2.top=2(A、B、C進棧）進棧）A B3.top=1(C出棧）出棧）4.A B C D E Ftop=MAXSIZE-1(棧滿）棧滿）1. 進棧算法n算法步驟算法步驟:nstep1 判別棧滿否，若滿，則顯示棧

43、溢出信息，停止執(zhí)行；否則，執(zhí)行step 2； nStep2 棧頂指針top上移(加1)；nStep3 在top所指的位置插入元素x。PROCEDURE PUSH（s,m,top,x）If (topm) Then Stack overflow; RETURN;top=top+1；S(top)=x；RETURN 在容量為在容量為m的棧的棧S中插入一個元素中插入一個元素x（入棧運算）（入棧運算）void push（s，m，top，x）ET s,x；int m, *top；if (*topm-1） printf(“Stackoverflown”)； return； *top*topl； s*top1=

44、x； return；2. 出棧算法n算法步驟算法步驟:n step1 判別棧是否為空；若空，則輸出判別棧是否為空；若空，則輸出 棧下溢信息，并停止執(zhí)行；否則，棧下溢信息，并停止執(zhí)行；否則， 執(zhí)行執(zhí)行step2；n step2 彈出（刪除）棧頂元素；彈出（刪除）棧頂元素； n step3 棧頂指針棧頂指針top下移下移(減減1)。 n step4 返回出棧元素返回出棧元素PROCEDURE POP（S，m，top，y）IF（top=0）THEN Stack-UNDERFLOW；RETURNy=S（top）top=top-1RETURN在容量為在容量為m的棧的棧S中刪除棧頂元素（退棧運算）中刪除棧

45、頂元素（退棧運算）void pop（s，m，top，y）ET s，*y；int m，*top; if (*top=-1) printf(“Stack-underflown”)；return；*y=s*top-1；*top=*top-1；return； 四、多棧共享問題n如何充分利用?？臻g，這是解決存儲空間緊張這如何充分利用?？臻g，這是解決存儲空間緊張這樣一個實際矛盾所要考慮的問題。樣一個實際矛盾所要考慮的問題。n作為一種策略，就是多棧共享一個?？臻g。作為一種策略，就是多棧共享一個?？臻g。n具體作法是：具體作法是： 對兩棧共享情況來說，對兩棧共享情況來說，將兩個棧底分別設(shè)在兩將兩個棧底分別設(shè)在兩

46、端，兩個棧頂指針端，兩個棧頂指針top1和和top2相對中間位置動相對中間位置動態(tài)移動，兩個棧之間的分界線是不定的。態(tài)移動，兩個棧之間的分界線是不定的。棧棧1 1、棧、棧2 2均有若干元素均有若干元素top1top2top1 =0 top2=MAXSIZE+1 空?？諚op1top2棧滿的情況棧滿的情況五、 棧的鏈式存儲結(jié)構(gòu)n由前面介紹的鏈表結(jié)構(gòu)可知，鏈結(jié)構(gòu)操作靈由前面介紹的鏈表結(jié)構(gòu)可知，鏈結(jié)構(gòu)操作靈活。對棧結(jié)構(gòu)也是一樣的?；?。對棧結(jié)構(gòu)也是一樣的。n順序棧最多可用于順序棧最多可用于2個棧的共享，對于更多個棧的共享，對于更多的棧就難于表達了。的棧就難于表達了。n對于最大空間需要量事先不知的情況

47、，就不對于最大空間需要量事先不知的情況，就不能使用順序棧了。這時，就需要采用鏈棧。能使用順序棧了。這時，就需要采用鏈棧。鏈棧：棧的鏈式存儲結(jié)構(gòu)鏈棧：棧的鏈式存儲結(jié)構(gòu)1. 鏈棧存儲結(jié)構(gòu)n鏈棧存儲結(jié)構(gòu)的鏈棧存儲結(jié)構(gòu)的C語言描述：語言描述： struct snode intdata; struct snode *link; ; typedef struct snode SNODE ;n 鏈棧為空的條件：鏈棧為空的條件： top = NULLn 鏈棧為滿的條件鏈棧為滿的條件(無法繼續(xù)申請新結(jié)點無法繼續(xù)申請新結(jié)點): t = NULL t 為申請的結(jié)點為申請的結(jié)點,為為NULL表示失敗。表示失敗。 2.

48、 鏈棧示意圖a1a2a3棧底棧底top棧頂棧頂.ai3.鏈棧進棧操作操作步驟操作步驟:nstep1 ：申請一個鏈棧結(jié)點，若：申請一個鏈棧結(jié)點，若t=NULL，則表示鏈滿；否則，執(zhí)行則表示鏈滿；否則，執(zhí)行step2 ；nstep2 ：在：在top所指結(jié)點之前插入新結(jié)點，所指結(jié)點之前插入新結(jié)點，并將并將top指向新申請的結(jié)點指向新申請的結(jié)點t。 push(SNODE *top , int x) SNODE *t; t=(SNODE * )malloc(sizeof(SNODE)； if(t = = NULL ) printf(“內(nèi)存中已無可用空間內(nèi)存中已無可用空間n”); exit(1); els

49、e t - data = x; t - link = top; top= t; 4. 鏈棧出棧操作操作步驟操作步驟:nstep1 若鏈棧為空，則輸出棧溢出信息；否若鏈棧為空，則輸出棧溢出信息；否則，執(zhí)行則，執(zhí)行step 2。nstep2 (保存保存top)并使并使top 指向被刪除結(jié)點的指向被刪除結(jié)點的后繼結(jié)點，刪除后繼結(jié)點，刪除top所指結(jié)點。所指結(jié)點。nstep 3 釋放被刪除結(jié)點的存儲空間。返回出釋放被刪除結(jié)點的存儲空間。返回出棧元素值。棧元素值。int pop (SNODE * top) SNODE *p; int x; if( top = = NULL ) printf(“棧溢出棧溢

50、出n”）；）； exit(1); else p = top； top = top- link ； x = p- data ； free(p) ; return x; 六、棧的應(yīng)用1. 例例1 ： 表達式計算表達式計算 計算表達式，首先要正確地定義運算規(guī)則：計算表達式，首先要正確地定義運算規(guī)則：n為了讓計算機能識別表達式，規(guī)定：為了讓計算機能識別表達式，規(guī)定：n表達式由操作數(shù)（表達式由操作數(shù)（Operand）和操作符（）和操作符（Operator）和定界符（和定界符（Delimiter）組成。）組成。 例如，例如，#3*（7-2）#；n實際處理表達式是用兩個棧結(jié)構(gòu)實際處理表達式是用兩個棧結(jié)構(gòu)OP

51、TR（運算符）（運算符）和和OPND（操作數(shù)）加運算規(guī)則組成；（操作數(shù)）加運算規(guī)則組成；四則運算四則運算n先乘除、后加減先乘除、后加減n從左到右從左到右n先括號內(nèi)，再括號外先括號內(nèi)，再括號外2.計算表達式算法步驟nStep1 初始化，清空初始化，清空OPTR和和OPND，將左定界符壓，將左定界符壓OPTR棧；棧；nStep2 循環(huán)輸入表達式中的每個字符循環(huán)輸入表達式中的每個字符n若輸入操作數(shù)，則進若輸入操作數(shù)，則進OPND棧棧n若是算符，則和若是算符，則和OPTR棧頂元素進行比較，按規(guī)則進行相應(yīng)操作棧頂元素進行比較，按規(guī)則進行相應(yīng)操作n操作服從優(yōu)先關(guān)系表操作服從優(yōu)先關(guān)系表nQ1Q2 Q1出出O

52、PTR棧，從棧，從OPND中取兩個數(shù)運算中取兩個數(shù)運算nStep3 直到出現(xiàn)右定界符為止。直到出現(xiàn)右定界符為止。n舉例，計算：舉例，計算： 3*（7-2） 輸入：輸入： # 3*（7-2）# 1 # 3 PUSH（OPND，3） 2 # 3 * PUSH（OPTR，*） 3 # * 3 （ PUSH（OPTR，（） 4 #*（ 3 7 PUSH（OPND，7） 5 #*（ 3 7 - PUSH（OPTR，-） 6 #*（- 3 7 2 PUSH（OPND，2） 7 #*（- 3 7 2 ） Operate（7，-，2） 8 #*（ 3 5 POP（OPTR，（） 9 #* 3 5 # Oper

53、ate（3，*，5）10 # 15 RETURN（GETTOP（OPND）步驟步驟 OPTR棧棧 OPND棧棧 輸入字符輸入字符 主要操作主要操作例2（遞歸過程實現(xiàn)）（2）遞歸過程的實現(xiàn)）遞歸過程的實現(xiàn)計算計算5的階乘（的階乘（5！=54321） int f(n) if ( n = = 1) return (1); else return ( n * f(n-1); f(1)f(1)f(2)f(2)f(3)f(3)f(4)f(4)f(5)f(5)top1 f(1)=11 f(1)=1 2 2* *f(1) f(2)=2f(1) f(2)=2* *f(1)f(1)3 3* *f(2) f(3)=

54、3f(2) f(3)=3* *f(2)f(2)4 4* *f(3) f(4)=4f(3) f(4)=4* *f(3)f(3)5 5* *f(4) f(5)=5f(4) f(5)=5* *f(4)f(4)例 N階Hanoi塔問題n假設(shè)有假設(shè)有A、B、C三座塔。在三座塔。在X塔上插有塔上插有n個直徑大小個直徑大小不同、以小到大編號為不同、以小到大編號為1、2、n的圓盤?，F(xiàn)要求的圓盤?，F(xiàn)要求將將A軸上的軸上的n個圓盤移至個圓盤移至C塔上，并按同樣順序疊排。塔上，并按同樣順序疊排。移動圓盤的規(guī)則為：移動圓盤的規(guī)則為： 1）每次只能移動一個圓盤；）每次只能移動一個圓盤； 2）圓盤可以插在）圓盤可以插在A

55、、B、C的任意一個上；的任意一個上； 3）任何時刻都不能將較大的圓盤壓在較小的圓盤之上。）任何時刻都不能將較大的圓盤壓在較小的圓盤之上。移動方法：先將移動方法：先將(n-1)個圓盤從移到，將第個圓盤從移到，將第n個個圓盤從移到，再將（圓盤從移到，再將（n-1）個圓盤從移到）個圓盤從移到void f(int n, int a1, int b1, int c1) if(n=1) /* there is only one element ,a1-c1 */ pop(a1); push(c1); else f(n-1,a1,c1,b1); /* (n-1) from a1 to b1 */ pop(a

56、1); /* the last one from a1 to c1 */ push(c1); f(n-1,b1,a1,c1); /* last : (n-1) from b1 to c1 */ 將盤從將盤從a1移到移到c1，利用中介，利用中介b1一、棧一、棧 棧、棧頂指針棧、棧頂指針 順序存儲、共享棧、鏈棧、入棧、順序存儲、共享棧、鏈棧、入棧、出棧操作出棧操作總結(jié)2.2.5 隊列及其應(yīng)用n隊列是一種特殊的線性表，它只允許在表的前端隊列是一種特殊的線性表，它只允許在表的前端（front）進行刪除操作，而在表的后端（）進行刪除操作，而在表的后端（rear）進行插入操作。進行插入操作。n進行插入操作

57、的端稱為隊尾，進行刪除操作的端進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。稱為隊頭。n隊列中沒有元素時，稱為空隊列。隊列中沒有元素時，稱為空隊列。n隊列具有先進先出（隊列具有先進先出（FIFO）的特點。）的特點。a1 a2 an入隊插入出隊出隊刪除刪除frontrear一、 隊列的基本概念 二二、隊列的順序存儲結(jié)構(gòu)(1)描述描述 C語言中順序存儲結(jié)構(gòu)采用一維數(shù)組結(jié)構(gòu)，描述如下：語言中順序存儲結(jié)構(gòu)采用一維數(shù)組結(jié)構(gòu)，描述如下： #define MAXSIZE n int queueMAXSIZE； int front,rear;(2)約定約定nfront為為隊頭指針隊頭指針，指示隊頭元素的

58、，指示隊頭元素的前一個位置前一個位置。nrear 為為隊尾指針，隊尾指針，指示隊尾元素的位置。指示隊尾元素的位置。 三三、隊列的操作SetNull（Q） 清空隊列清空隊列Empty（Q） 判別隊列是否為空；空，取判別隊列是否為空；空，取T; 非空，取值為非空，取值為F。AddQueue（Q） 插入操作插入操作DelQueue（Q） 刪除操作刪除操作FrontQueue（Q）取隊頭元素）取隊頭元素 基本操作初初 始始 時時：front=-1; rear=-1; front= =rear 隊空隊空X入隊操作入隊操作：rear=rear+1; queuerear=x; 出隊操作出隊操作：front=

59、front+1; x=queuefront; return x;隊隊 空空：front= =rear;隊隊 滿滿: rear= =(MAXSIZE-1); 舉例：順序隊列的入隊、出隊操作（C）A、B、C出隊出隊 D E frontrear出隊時，出隊時，front在變在變frontrear（A）空隊列）空隊列A B C D E frontrear（B）A、B、C、D、E入隊入隊入隊時，入隊時，rear在變在變 舉例：順序隊列的入隊、出隊操作注：一方面隊列中是空的，另一方面又出現(xiàn)溢出。注：一方面隊列中是空的，另一方面又出現(xiàn)溢出。顯然，這是邏輯設(shè)計上的問題。顯然，這是邏輯設(shè)計上的問題。front

60、frontrear D E F G H rear（D）F、G、H入隊入隊(E）D、E、F、G、H出隊，出現(xiàn)假出隊，出現(xiàn)假“溢出溢出”四、循環(huán)隊列循環(huán)隊列的概念循環(huán)隊列的概念n如果使當(dāng)如果使當(dāng)rear = MAXSIZE 時，即超過隊列末端時，即超過隊列末端時，令時，令rear = 0；從而使隊列的首尾相連接，只有；從而使隊列的首尾相連接，只有當(dāng)隊列中真正沒有空位置時，才產(chǎn)生溢出。當(dāng)隊列中真正沒有空位置時，才產(chǎn)生溢出。n設(shè)定設(shè)定 queue0接在接在queueMAXSIZE-1之后之后,使得使得 if （rear MAXSIZE-1 ） rear = 0 ; else rearrear + 1; 這樣就構(gòu)成了循