軟件技術(shù)基礎(chǔ)完整版課件全套ppt教學(xué)教程最全整套電子講義幻燈片

22:10:57第1章緒論

第一章

緒論

計(jì)算機(jī)發(fā)展的初期，其應(yīng)用主要是數(shù)值計(jì)算問(wèn)題，即所處理的數(shù)據(jù)都是整型、實(shí)型及布爾型等簡(jiǎn)單數(shù)據(jù)。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的不斷擴(kuò)大，非數(shù)值計(jì)算問(wèn)題占據(jù)了目前計(jì)算機(jī)應(yīng)用的絕大部分，計(jì)算機(jī)所處理的數(shù)據(jù)也不再是簡(jiǎn)單的數(shù)值，而是擴(kuò)展到字符串、圖形、圖像、語(yǔ)音、視頻等復(fù)雜的數(shù)據(jù)。這些復(fù)雜的數(shù)據(jù)不僅量大，而且具有一定的結(jié)構(gòu)。例如，一幅圖像是由簡(jiǎn)單的數(shù)值組成的矩陣；一個(gè)圖形中的幾何坐標(biāo)可以組成表；語(yǔ)言編譯程序中使用的棧、符號(hào)表和語(yǔ)法樹，操作系統(tǒng)中所用到的隊(duì)列、樹形目錄等，都是有結(jié)構(gòu)的數(shù)據(jù)。為了有效地組織和管理好這些數(shù)據(jù)，設(shè)計(jì)出高質(zhì)量的程序以及高效率地使用計(jì)算機(jī)，就必須深入研究這些數(shù)據(jù)自身的特性以及它們之間的相互關(guān)系。本章內(nèi)容提要:數(shù)據(jù)結(jié)構(gòu)的概念

邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)算法與算法分析

第一章

緒論

1.1

數(shù)據(jù)結(jié)構(gòu)的概念

數(shù)據(jù)結(jié)構(gòu)的概念

數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)與數(shù)據(jù)元素

緒論

用計(jì)算機(jī)解決實(shí)際問(wèn)題的軟件開發(fā)一般分為下面幾個(gè)步驟：

數(shù)據(jù)結(jié)構(gòu)的概念

（1）分析階段：分析實(shí)際問(wèn)題，從中抽象出一個(gè)數(shù)學(xué)模型。

（2）設(shè)計(jì)階段：設(shè)計(jì)出解決數(shù)學(xué)模型的算法。

（3）編程階段：用適當(dāng)?shù)木幊陶Z(yǔ)言編寫出可執(zhí)行的程序。

（4）測(cè)試階段：測(cè)試、修改直到得到問(wèn)題的解答。

緒論數(shù)據(jù)結(jié)構(gòu)課程集中討論軟件開發(fā)過(guò)程中的設(shè)計(jì)階段，同時(shí)涉及分析階段和編程階段的若干基本問(wèn)題。此外，為了構(gòu)造出好的數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)，還需考慮數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)的評(píng)價(jià)與選擇。因此，數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容包括了下表所示的數(shù)據(jù)表示方面和數(shù)據(jù)處理方面的3個(gè)層次。

數(shù)據(jù)結(jié)構(gòu)的概念

方面層次數(shù)據(jù)表示數(shù)據(jù)處理抽象邏輯結(jié)構(gòu)基本運(yùn)算實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)算法評(píng)價(jià)不同數(shù)據(jù)結(jié)構(gòu)的比較與算法分析

緒論數(shù)據(jù)結(jié)構(gòu)的核心內(nèi)容是分解與抽象。通過(guò)對(duì)問(wèn)題的抽象，舍棄數(shù)據(jù)元素（含義見后）的具體內(nèi)容，就得到邏輯結(jié)構(gòu)；類似地，通過(guò)分解將處理要求劃分成各種功能，再通過(guò)抽象舍棄實(shí)現(xiàn)的細(xì)節(jié)，就得到基本運(yùn)算的定義。上述兩個(gè)方面的結(jié)合使人們將問(wèn)題轉(zhuǎn)換為數(shù)據(jù)結(jié)構(gòu)，這是一個(gè)從具體（即具體問(wèn)題）到抽象（即數(shù)據(jù)結(jié)構(gòu)）的過(guò)程。通過(guò)增加對(duì)實(shí)現(xiàn)細(xì)節(jié)的考慮，進(jìn)一步得到存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)算法，從而完成設(shè)計(jì)任務(wù)，這是一個(gè)從抽象（即數(shù)據(jù)結(jié)構(gòu)）到具體（即具體實(shí)現(xiàn)）的過(guò)程。熟練掌握這兩個(gè)過(guò)程是數(shù)據(jù)結(jié)構(gòu)課程在專業(yè)技能培養(yǎng)方面的基本目標(biāo)。在系統(tǒng)地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識(shí)之前，先對(duì)一些基本概念和術(shù)語(yǔ)予以說(shuō)明。

數(shù)據(jù)結(jié)構(gòu)的概念

1.1

數(shù)據(jù)結(jié)構(gòu)的概念

數(shù)據(jù)結(jié)構(gòu)的概念

數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)與數(shù)據(jù)元素

緒論

數(shù)據(jù)是人們利用文字符號(hào)、數(shù)學(xué)符號(hào)以及其他規(guī)定的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)所做的抽象描述。簡(jiǎn)言之，數(shù)據(jù)是信息的載體，是對(duì)客觀事物的符號(hào)化表示。從計(jì)算機(jī)的角度看，數(shù)據(jù)是計(jì)算機(jī)程序?qū)λ枋隹陀^事物進(jìn)行加工處理的一種表示，凡是能夠被計(jì)算機(jī)識(shí)別、存取和加工處理的符號(hào)、字符、圖形、圖像、聲音、視頻信號(hào)等都可以稱為數(shù)據(jù)。我們?nèi)粘Ｉ婕暗臄?shù)據(jù)主要分為兩類：一類是數(shù)值數(shù)據(jù)，包括整數(shù)、實(shí)數(shù)和復(fù)數(shù)等，它們主要用于工程和科學(xué)計(jì)算以及商業(yè)事務(wù)處理；另一類是非數(shù)值數(shù)據(jù)，主要包括字符和字符串以及文字、圖形、語(yǔ)音等，它們多用于控制、管理和數(shù)據(jù)處理等領(lǐng)域。

數(shù)據(jù)元素是數(shù)據(jù)集合中的一個(gè)“個(gè)體”，是數(shù)據(jù)的基本單位。在計(jì)算機(jī)中，數(shù)據(jù)元素通常被作為一個(gè)整體來(lái)進(jìn)行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)和記錄等。一個(gè)數(shù)據(jù)元素可以由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的數(shù)據(jù)最小單位，有時(shí)也稱為字段或域。

數(shù)據(jù)與數(shù)據(jù)元素

緒論

【例1.1】一個(gè)學(xué)生信息（數(shù)據(jù)）表如表1.2所示，請(qǐng)指出表中的數(shù)據(jù)、數(shù)據(jù)元素及數(shù)據(jù)項(xiàng)，并由此得出三者之間的關(guān)系。表1.2學(xué)生信息表

數(shù)據(jù)與數(shù)據(jù)元素

姓名性別年齡專業(yè)其他劉小平男21計(jì)算機(jī)…王紅女20數(shù)學(xué)…呂軍男20經(jīng)濟(jì)…...............馬文華女19管理…

緒論表1.1構(gòu)成了全部學(xué)生信息的數(shù)據(jù)。表中的每一行即為記錄一個(gè)學(xué)生信息的數(shù)據(jù)元素，而該行中的每一項(xiàng)則為一個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)實(shí)際上反映了數(shù)據(jù)組織的三個(gè)層次，數(shù)據(jù)可以由若干個(gè)數(shù)據(jù)元素構(gòu)成，而數(shù)據(jù)元素則又可以由若干數(shù)據(jù)項(xiàng)構(gòu)成。

數(shù)據(jù)與數(shù)據(jù)元素

1.1

數(shù)據(jù)結(jié)構(gòu)的概念

數(shù)據(jù)結(jié)構(gòu)的概念

數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)與數(shù)據(jù)元素

緒論數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。它可以看作是相互之間存在著某種特定關(guān)系的數(shù)據(jù)元素集合。因此，可以把數(shù)據(jù)結(jié)構(gòu)看成是帶結(jié)構(gòu)的數(shù)據(jù)元素集合。數(shù)據(jù)結(jié)構(gòu)包含以下三個(gè)方面的內(nèi)容。（1）數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。（2）數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）。（3）施加在數(shù)據(jù)上的操作，即數(shù)據(jù)的運(yùn)算。

數(shù)據(jù)結(jié)構(gòu)

緒論

數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上（主要指相鄰關(guān)系）來(lái)描述數(shù)據(jù)的，它與數(shù)據(jù)如何存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看成是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的映像表示，即在能夠反映數(shù)據(jù)邏輯關(guān)系的前提下數(shù)據(jù)在存儲(chǔ)器中的存儲(chǔ)方式。數(shù)據(jù)的運(yùn)算是在數(shù)據(jù)上所施加的一系列操作，稱為抽象運(yùn)算。它只考慮這些操作的功能，而暫不考慮如何完成，只有在確定了存儲(chǔ)結(jié)構(gòu)后，才會(huì)具體實(shí)現(xiàn)這些操作。也就是說(shuō)，抽象運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而實(shí)現(xiàn)則是建立在存儲(chǔ)結(jié)構(gòu)上的。最常用的運(yùn)算有檢索、插入、刪除、更新、排序等。

數(shù)據(jù)結(jié)構(gòu)1.2

邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)

邏輯結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)

緒論數(shù)據(jù)的邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間邏輯關(guān)系的描述。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，可以劃分為以下四種基本邏輯結(jié)構(gòu)。（1）集合結(jié)構(gòu)：數(shù)據(jù)元素之間除了“屬于同一集合”的聯(lián)系之外，沒(méi)有其他關(guān)系。（2）線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“一對(duì)一”的關(guān)系。（3）樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“一對(duì)多”的關(guān)系。（4）圖結(jié)構(gòu)（或稱網(wǎng)狀結(jié)構(gòu)）：數(shù)據(jù)元素之間存在著“多對(duì)多”的關(guān)系。

邏輯結(jié)構(gòu)

緒論

由于集合結(jié)構(gòu)的簡(jiǎn)單性和松散性，所以通常只討論其他三種邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。若數(shù)據(jù)元素之間的邏輯關(guān)系可以用一個(gè)線性序列簡(jiǎn)單地表示出來(lái)，則稱為線性結(jié)構(gòu)，否則稱為非線性結(jié)構(gòu)。樹形結(jié)構(gòu)和圖結(jié)構(gòu)就屬于非線性結(jié)構(gòu)。現(xiàn)實(shí)生活中的樓層編號(hào)就屬于線性結(jié)構(gòu)，而省、市、地區(qū)的劃分則屬于樹形結(jié)構(gòu)，城市交通圖則屬于圖結(jié)構(gòu)。

邏輯結(jié)構(gòu)

緒論關(guān)于邏輯結(jié)構(gòu)需要注意以下幾點(diǎn):（1）邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式和內(nèi)容無(wú)關(guān)。例如，給表1.1中的每個(gè)學(xué)生增加一個(gè)數(shù)據(jù)項(xiàng)“學(xué)號(hào)”，就得到另一個(gè)數(shù)據(jù)，但由于所有的數(shù)據(jù)元素仍是“一個(gè)接一個(gè)排列”，故新數(shù)據(jù)的邏輯結(jié)構(gòu)與原來(lái)數(shù)據(jù)的邏輯結(jié)構(gòu)相同，仍是一個(gè)線性結(jié)構(gòu)。（2）邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)位置無(wú)關(guān)。例如，將表1.1中的學(xué)生按年齡由大到小的順序重新排列就得到另一個(gè)表格，但這個(gè)新表格中的所有數(shù)據(jù)元素“一個(gè)接一個(gè)排列”的性質(zhì)并沒(méi)有改變，其邏輯結(jié)構(gòu)與原表格相同，還是線性結(jié)構(gòu)。（3）邏輯結(jié)構(gòu)與所含數(shù)據(jù)元素的個(gè)數(shù)無(wú)關(guān)。例如，在表1.1中增加或刪除若干學(xué)生信息（數(shù)據(jù)元素），所得到的表格仍為線性結(jié)構(gòu)。

邏輯結(jié)構(gòu)1.2

邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)

邏輯結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)

緒論

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素的表示以及數(shù)據(jù)元素之間關(guān)系的表示。數(shù)據(jù)元素及數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中可以有以下四種基本存儲(chǔ)結(jié)構(gòu)。（1）順序存儲(chǔ)結(jié)構(gòu)：借助于數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。通常順序存儲(chǔ)結(jié)構(gòu)是利用程序語(yǔ)言中的數(shù)組來(lái)描述。（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在數(shù)據(jù)元素上附加指針域，并借助指針來(lái)指示數(shù)據(jù)元素之間的邏輯關(guān)系。通常是利用程序語(yǔ)言中的指針類型來(lái)描述。（3）索引存儲(chǔ)結(jié)構(gòu)：在存儲(chǔ)所有數(shù)據(jù)元素信息的同時(shí)建立附加索引表。索引表中表項(xiàng)的一般形式是：（關(guān)鍵字，地址）；關(guān)鍵字是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，它唯一標(biāo)識(shí)該數(shù)據(jù)元素；地址則是指向該數(shù)據(jù)元素的指針。由關(guān)鍵字可以立即通過(guò)地址找到該數(shù)據(jù)元素。（4）哈希（或散列）存儲(chǔ)結(jié)構(gòu)：此方法的基本思想是根據(jù)數(shù)據(jù)元素的關(guān)鍵字通過(guò)哈希（或散列）函數(shù)直接計(jì)算出該數(shù)據(jù)元素的存儲(chǔ)地址。

存儲(chǔ)結(jié)構(gòu)

緒論

存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)的主要優(yōu)點(diǎn)是節(jié)省存儲(chǔ)空間，即分配給數(shù)據(jù)的存儲(chǔ)單元全部用于存放數(shù)據(jù)元素的數(shù)據(jù)信息，數(shù)據(jù)元素之間的邏輯關(guān)系沒(méi)有占用額外的存儲(chǔ)空間。采用這種存儲(chǔ)結(jié)構(gòu)可以實(shí)現(xiàn)對(duì)數(shù)據(jù)元素的隨機(jī)存取，即每個(gè)數(shù)據(jù)元素對(duì)應(yīng)有一個(gè)序號(hào)，并由該序號(hào)可以直接計(jì)算出數(shù)據(jù)元素的存儲(chǔ)地址（例如，對(duì)于數(shù)組A其序號(hào)為數(shù)組元素的下標(biāo)，數(shù)組元素A[i]可以通過(guò)*(A+i)進(jìn)行存?。ｍ樞虼鎯?chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不便于修改，對(duì)數(shù)據(jù)元素進(jìn)行插入、刪除運(yùn)算時(shí)，可能要移動(dòng)一系列的數(shù)據(jù)元素。

緒論

存儲(chǔ)結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要優(yōu)點(diǎn)是便于修改，在進(jìn)行插入、刪除運(yùn)算時(shí)僅需修改相應(yīng)數(shù)據(jù)元素的指針值，而不必移動(dòng)數(shù)據(jù)元素。與順序存儲(chǔ)結(jié)構(gòu)相比，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要缺點(diǎn)是存儲(chǔ)空間的利用率較低，因?yàn)槌擞糜跀?shù)據(jù)元素的存儲(chǔ)空間外，還需要額外的存儲(chǔ)空間來(lái)存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系。此外，由于邏輯上相鄰的數(shù)據(jù)元素在存儲(chǔ)空間中不一定相鄰，所以不能對(duì)數(shù)據(jù)元素進(jìn)行隨機(jī)存取。

緒論

存儲(chǔ)結(jié)構(gòu)

線性結(jié)構(gòu)采用索引存儲(chǔ)方法后就可以對(duì)結(jié)點(diǎn)進(jìn)行隨機(jī)訪問(wèn)。在進(jìn)行插入、刪除運(yùn)算時(shí)，只需改動(dòng)存儲(chǔ)在索引表中數(shù)據(jù)元素的存儲(chǔ)地址，而不必移動(dòng)數(shù)據(jù)元素，所以仍保持較高的數(shù)據(jù)修改和運(yùn)算效率。索引存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)是增加了索引表，這也降低了存儲(chǔ)空間的利用率。哈希（或散列）存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是查找速度快，只要給出待查數(shù)據(jù)元素的關(guān)鍵字，就可以立即計(jì)算出該數(shù)據(jù)元素的存儲(chǔ)地址。與前面三種存儲(chǔ)方法不同的是，哈希存儲(chǔ)結(jié)構(gòu)只存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)而不存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系。哈希存儲(chǔ)結(jié)構(gòu)一般只適合于對(duì)數(shù)據(jù)進(jìn)行快速查找和插入的場(chǎng)合。

緒論

存儲(chǔ)結(jié)構(gòu)

表1.2在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的示意如圖所示：1.3

算法與算法分析

算法的定義和描述

算法分析和復(fù)雜度計(jì)算

緒論

算法的定義和描述

算法是建立在數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上對(duì)特定問(wèn)題求解步驟的一種描述，是若干條指令組成的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法必須滿足以下性質(zhì)。（1）有窮性：一個(gè)算法必須在有窮步之后結(jié)束，即必須在有限時(shí)間內(nèi)完成。（2）確定性：算法的每一步必須有確切的含義而沒(méi)有二義性。對(duì)于相同的輸入，算法執(zhí)行的路徑是唯一的。（3）可行性：算法所描述的操作都可以通過(guò)可實(shí)現(xiàn)的基本運(yùn)算在有限次執(zhí)行后得以完成。（4）輸入：一個(gè)算法可以有零個(gè)或多個(gè)輸入。（5）輸出：一個(gè)算法具有一個(gè)或多個(gè)輸出，且輸出與輸入之間存在某種特定的關(guān)系。

緒論

算法的定義和描述

算法的含義與程序十分相似但又有區(qū)別。一個(gè)程序不一定滿足有窮性，如操作系統(tǒng)程序只要不停機(jī)執(zhí)行就永不停止，因此，操作系統(tǒng)不是一個(gè)算法。此外，程序中的語(yǔ)句最終都要轉(zhuǎn)化（編譯）成計(jì)算機(jī)可執(zhí)行的指令；而算法中的指令則無(wú)此限制，即一個(gè)算法可采用自然語(yǔ)言如英語(yǔ)、漢語(yǔ)描述，也可以采用圖形方式如流程圖、拓?fù)鋱D描述。算法給出了對(duì)一個(gè)問(wèn)題的求解，而程序僅是算法在計(jì)算機(jī)上的實(shí)現(xiàn)。一個(gè)算法若用程序設(shè)計(jì)語(yǔ)言來(lái)描述，則此時(shí)算法也就是一個(gè)程序。對(duì)某個(gè)特定問(wèn)題的求解究竟采用何種數(shù)據(jù)結(jié)構(gòu)及選擇什么算法，需要看問(wèn)題的具體要求和現(xiàn)實(shí)環(huán)境的各種條件；數(shù)據(jù)結(jié)構(gòu)的選擇是否恰當(dāng)將直接影響到算法的效率，只有把數(shù)據(jù)結(jié)構(gòu)與算法有機(jī)地結(jié)合起來(lái)才能設(shè)計(jì)出高質(zhì)量的程序來(lái)。

緒論

算法的定義和描述

【例1.2】對(duì)兩個(gè)正整數(shù)m和n，給出求它們最大公因子的算法。算法流程如圖所示。

緒論

算法的定義和描述

解:算法設(shè)計(jì)如下：（1）求余數(shù)：以n除m，余數(shù)為r且0≤r＜n。（2）判斷余數(shù)r是否等于零：如果r為零，則輸出n的當(dāng)前值（即為最大公因子），算法結(jié)束；否則執(zhí)行（3）。（3）將n值傳給m，將r值傳給n，轉(zhuǎn)（1）。上述算法給出了三個(gè)計(jì)算步驟，而且每一步驟意義明確并切實(shí)可行。雖然出現(xiàn)了循環(huán)，但m和n都是已給定的有限整數(shù)，并且每次m除以n后得到的余數(shù)r即使不為零也總有r＜min(m,n)，這就保證循環(huán)執(zhí)行有限次后必然終止，即滿足算法的所有特征，所以是一個(gè)正確的算法。1.3

算法與算法分析

算法的定義和描述

算法分析和復(fù)雜度計(jì)算

緒論

算法分析與復(fù)雜度計(jì)算

算法設(shè)計(jì)主要是考慮可解算法的設(shè)計(jì)，而算法分析則是研究和比較各種算法的性能與優(yōu)劣。算法的時(shí)間復(fù)雜度和空間復(fù)雜度是算法分析的兩個(gè)主要方面，其目的主要是考察算法的時(shí)間和空間效率，以求改進(jìn)算法或?qū)Σ煌乃惴ㄟM(jìn)行比較。（1）時(shí)間復(fù)雜度：一個(gè)程序的時(shí)間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需要的時(shí)間。（2）空間復(fù)雜度：一個(gè)程序的空間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需的存儲(chǔ)量。在復(fù)雜度計(jì)算中，實(shí)際上是把求解問(wèn)題的關(guān)鍵操作，如加法、減法和比較運(yùn)算指定為基本操作，然后把算法執(zhí)行基本操作的次數(shù)作為算法的時(shí)間復(fù)雜度，而把算法執(zhí)行期間占用存儲(chǔ)單元的數(shù)量作為算法的空間復(fù)雜度。

緒論

算法分析與復(fù)雜度計(jì)算

在此涉及頻度的概念，即語(yǔ)句（指令）的頻度是指它在算法中被重復(fù)執(zhí)行的次數(shù)。一個(gè)算法的時(shí)間耗費(fèi)就是該算法中所有語(yǔ)句（指令）的頻度之和（記作T(n)），它是該算法所求解問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n)。當(dāng)問(wèn)題規(guī)模n趨向無(wú)窮大時(shí)，T(n)的數(shù)量級(jí)稱為時(shí)間復(fù)雜度，記作：

T(n)＝O(f(n))

上述式子中“O”的文字含義是T(n)的數(shù)量級(jí)，其嚴(yán)格的數(shù)學(xué)定義是：若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則存在正常數(shù)C和n0，使得當(dāng)n≥n0時(shí)都滿足

0≤T(n)≤C·f(n)

例如，一個(gè)程序的實(shí)際執(zhí)行時(shí)間為T(n)=2.7n3+8.3n2+5.6，則T(n)=O(n3)。也即，當(dāng)n趨于無(wú)窮大時(shí)，n3前的2.7可以忽略，即該程序的時(shí)間復(fù)雜度的數(shù)量級(jí)是n3。算法的時(shí)間復(fù)雜度采用這種數(shù)量級(jí)的形式表示后，將給分析算法的時(shí)間復(fù)雜度帶來(lái)很大的方便，即對(duì)一個(gè)算法，只需分析影響該算法時(shí)間復(fù)雜度的主要部分即可，而無(wú)需對(duì)該算法的每一個(gè)語(yǔ)句都進(jìn)行詳細(xì)的分析。

緒論

算法分析與復(fù)雜度計(jì)算

若一個(gè)算法中的兩個(gè)部分的時(shí)間復(fù)雜度分別為T1(n)=O(f(n))和T2(n)=O(g(n))，則（1）在“O”下的求和準(zhǔn)則為T1(n)+T2(n)＝O(max(f(n),g(n)))。（2）在“O”下的乘法準(zhǔn)則為T1(n)×T2(n)＝O(f(n)×g(n))。當(dāng)算法轉(zhuǎn)換為程序后，每條語(yǔ)句執(zhí)行一次所需的時(shí)間取決于機(jī)器的指令性能、速度以及編譯所生成的代碼質(zhì)量，這是難以確定的。因此，我們假設(shè)每條語(yǔ)句執(zhí)行一次所需的時(shí)間均是單位時(shí)間，則程序計(jì)算的時(shí)間復(fù)雜度法則如下。

（1）執(zhí)行一條讀寫語(yǔ)句或賦值語(yǔ)句所用的時(shí)間為O(1)。

（2）依次執(zhí)行一系列語(yǔ)句所用的時(shí)間采用求和準(zhǔn)則。（3）條件語(yǔ)句if的耗時(shí)主要是當(dāng)條件為真時(shí)執(zhí)行語(yǔ)句體所用的時(shí)間，而檢測(cè)條件是否為真還需耗費(fèi)O(1)。（4）對(duì)while、do…while和for這樣的循環(huán)語(yǔ)句，其運(yùn)行時(shí)間為每次執(zhí)行循環(huán)體及檢測(cè)是否繼續(xù)循環(huán)的時(shí)間，故常用乘法準(zhǔn)則。

緒論

算法分析與復(fù)雜度計(jì)算

【例1.3】試求下面程序段的時(shí)間復(fù)雜度。for(i=0;i<n;i++)for(j=0;j<n;j++){C[i][j]=0;for(k=0;k<n;k++)C[i][j]=C[i][j]+A[i][k]*B[k][j];}解：給程序中的語(yǔ)句進(jìn)行編號(hào)，并在其右側(cè)列出該語(yǔ)句的頻度：(1) for(i=0;i<n;i++) n+1(2) for(j=0;j<n;j++) n(n+1) {(3) C[i][j]=0 n2(4) for(k=0;k<n;k++) n2(n+1)(5) C[i][j]=C[i][j]+A[i][k]*B[k][j]; n3 }

緒論

算法分析與復(fù)雜度計(jì)算

語(yǔ)句（1）的i值由0遞增到n，并且測(cè)試到i等于n時(shí)（即條件“i<n”為假）才會(huì)終止，故它的頻度是n+1，但它的循環(huán)體卻只能執(zhí)行n次。語(yǔ)句（2）作為語(yǔ)句（1）循環(huán)體中的一個(gè)語(yǔ)句應(yīng)該執(zhí)行n次，而語(yǔ)句（2）自身又要執(zhí)行n+1次，所以語(yǔ)句（2）的頻度是n(n+1)。同理，可得語(yǔ)句（3）、（4）和（5）的頻度分別是n2、n2(n+1)和n3。也即，該程序段所有語(yǔ)句的頻度之和為

T(n)=2n3+3n2+2n+1

最后得到：T(n)=O(n3)。實(shí)際上，由算法的三重for循環(huán)且每重循環(huán)進(jìn)行n次以及“O”下的乘法準(zhǔn)則可直接得到：T(n)=O(n3)。此外要說(shuō)明的是，時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列的順序如下O(1)＜O(log2n)＜O(n)＜O(nlog2n)＜O(n2)＜O(n3)＜O(2n)22:10:57第2章線性表

第二章

線性表

線性表是最簡(jiǎn)單、最基本、最常用的一種線性結(jié)構(gòu)。它在很多領(lǐng)域，尤其是在程序設(shè)計(jì)語(yǔ)言和程序設(shè)計(jì)過(guò)程中被大量使用。本章介紹線性表的基本概念及其邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，并針對(duì)不同存儲(chǔ)結(jié)構(gòu)給出實(shí)現(xiàn)線性表的建立以及在線性表中插入、刪除和查找的算法

。本章內(nèi)容提要:線性表及其邏輯結(jié)構(gòu)

線性表的順序存儲(chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)

第二章

線性表

2.1

線性表及其邏輯結(jié)構(gòu)

線性表的定義

線性表的基本操作

線性表一個(gè)線性表是n個(gè)元素的有限序列，其特點(diǎn)是在數(shù)據(jù)元素的非空集合中：（1）存在唯一一個(gè)稱為“第一個(gè)”的元素。（2）存在唯一一個(gè)稱為“最后一個(gè)”的元素。（3）除第一個(gè)元素之外，序列中的每一個(gè)元素只有一個(gè)直接前驅(qū)。（4）除最后一個(gè)元素之外，序列中的每一個(gè)元素只有一個(gè)直接后繼。

線性表的定義

線性表

線性表的定義為：具有相同數(shù)據(jù)類型的n（n≥0）個(gè)數(shù)據(jù)元素的有限序列，通常記為（a1,a2,…,ai-1,ai,ai+1,…,an），其中，n為表長(zhǎng)，n=0時(shí)稱為空表。線性表中相鄰元素之間存在著順序關(guān)系：ai-1稱為ai的直接前驅(qū)，ai+1稱為ai的直接后繼；對(duì)于ai，當(dāng)i=2，…，n時(shí)，有且僅有一個(gè)直接前驅(qū)ai-1；當(dāng)i=1，2，…，n-1時(shí)，有且僅有一個(gè)直接后繼ai+1；

a1是表中的第一個(gè)元素，它沒(méi)有前驅(qū)；

an是表中的最后一個(gè)元素，它沒(méi)有后繼。對(duì)非空線性表，數(shù)據(jù)元素ai在表中的位置僅取決于元素ai本身的序號(hào)i。

線性表的定義

線性表

線性表的特征如下：（1）均勻性：線性表中每個(gè)數(shù)據(jù)元素的長(zhǎng)度、大小和類型都相同。（2）有序性：線性表中各數(shù)據(jù)元素是有序的，且各數(shù)據(jù)元素之間的次序是不能改變的。

線性表的定義

2.1

線性表及其邏輯結(jié)構(gòu)

線性表的定義

線性表的基本操作

線性表數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是定義在邏輯結(jié)構(gòu)層面上，而運(yùn)算的具體實(shí)現(xiàn)則建立在存儲(chǔ)結(jié)構(gòu)上。因此，線性表基本運(yùn)算是作為邏輯結(jié)構(gòu)的一部分，并且每一個(gè)操作的具體實(shí)現(xiàn)只有在確定了線性表的存儲(chǔ)結(jié)構(gòu)之后才能完成。對(duì)線性表實(shí)施的基本操作有如下幾種。

線性表的基本操作

置空L=Init_List()生成一個(gè)空的線性表L求線性表的長(zhǎng)度Length_List(L)求得線性表中數(shù)據(jù)元素的個(gè)數(shù)取表中第i個(gè)元素Get_List(L,i)返回表L中的第i個(gè)元素ai的值或地址按給定值x查找Locate_List(L,x)返回首次出現(xiàn)在L中其值為x的數(shù)據(jù)元素的序號(hào)或地址；否則返回0值插入Insert_List(L,i,x)表L的第i個(gè)位置上插入值為x的元素，這樣使序號(hào)為i、i+1、…、n的數(shù)據(jù)元素變?yōu)樾蛱?hào)為i+1、i+2、…、n+1的數(shù)據(jù)元素；插入后新表長(zhǎng)=原表長(zhǎng)+1刪除Delete_List(L,i)在線性表L中刪除序號(hào)為i的元素，刪除后使序號(hào)為i+1、i+2、…、n的數(shù)據(jù)元素變?yōu)樾蛱?hào)為i、i+1、…、n-1的數(shù)據(jù)元素；刪除后新表長(zhǎng)=原表長(zhǎng)-12.2線性表的順序存儲(chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)

線性表的順序存儲(chǔ)

順序表基本運(yùn)算的實(shí)現(xiàn)

線性表線性表的順序存儲(chǔ)是用一組地址連續(xù)的存儲(chǔ)單元按順序依次存放線性表中的每一個(gè)元素（數(shù)據(jù)元素），這種存儲(chǔ)方式存儲(chǔ)的線性表稱為順序表。在這種順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上也相鄰；也即無(wú)需增加額外存儲(chǔ)空間來(lái)表示線性表中元素之間的邏輯關(guān)系。由于順序表中每個(gè)元素具有相同的類型，即其長(zhǎng)度相同，則順序表中第i個(gè)元素ai的存儲(chǔ)地址為

Loc(ai)=Loc(a1)+(i-1)×L（1≤i≤n）其中，Loc(a1)為順序表的起始地址（即第一個(gè)元素的地址）；L為每個(gè)元素所占存儲(chǔ)空間的大小。因此，只要知道順序表的起始地址和每個(gè)元素所占存儲(chǔ)空間的大小，就可以求出任意一個(gè)元素的存儲(chǔ)地址，即順序表中的任意一個(gè)元素都可以隨機(jī)存?。S機(jī)存取的特點(diǎn)是存取每一個(gè)元素所花費(fèi)的時(shí)間相同）。

線性表的順序存儲(chǔ)——順序表

線性表

一維數(shù)組在內(nèi)存中占用的存儲(chǔ)空間就是一組連續(xù)的存儲(chǔ)區(qū)域，并且每個(gè)數(shù)組元素的類型相同，故用一維數(shù)組來(lái)存儲(chǔ)順序表。為了避免元素的序號(hào)及其下標(biāo)的不一致性，我們約定順序表中的元素存放于一維數(shù)組時(shí)是從下標(biāo)為1的位置開始的。此外，考慮到順序表的運(yùn)算有插入、刪除等操作，即表長(zhǎng)是可變的，因此，數(shù)組的容量需要設(shè)計(jì)得足夠大。我們data[MAXSIZE]來(lái)存儲(chǔ)順序表，而MAXSIZE是根據(jù)實(shí)際問(wèn)題所定義的一個(gè)足夠大的整數(shù)。此時(shí)順序表中的數(shù)據(jù)由data[1]開始依次存放。由于當(dāng)前順序表中的實(shí)際元素個(gè)數(shù)可能還未達(dá)到MAXSIZE-1值，因此需要用一個(gè)len變量來(lái)記錄當(dāng)前順序表中最后一個(gè)元素在數(shù)組中的位置（即下標(biāo)）。這里的len起著一個(gè)指針的作用，它始終指向順序表中的最后一個(gè)元素且表空時(shí)len=0。

線性表的順序存儲(chǔ)——順序表

線性表

從結(jié)構(gòu)上考慮，我們將data和len組合在一個(gè)結(jié)構(gòu)體里來(lái)作為順序表的類型：typedefstruct{datatypedata[MAXSIZE]; //存儲(chǔ)順序表中的元素

intlen; //順序表的表長(zhǎng)}SeqList; //順序表類型其中，datatype為順序表中元素的類型，在具體實(shí)現(xiàn)中可為int、float、char類型或其他結(jié)構(gòu)類型；順序表中的元素可存放在data數(shù)組中下標(biāo)為1～MAXSIZE-1的任何一個(gè)位置；第i個(gè)元素的實(shí)際存放位置就是i；len為順序表的表長(zhǎng)。有了順序表類型，則可以定義如下順序表和指向順序表的指針變量：

SeqListList,*L；其中，List是一個(gè)結(jié)構(gòu)體變量，它內(nèi)部含有一個(gè)可存儲(chǔ)順序表的data數(shù)組；

線性表的順序存儲(chǔ)——順序表

線性表L是指向List這類結(jié)構(gòu)體變量的指針變量，如“L=&List;”；或者動(dòng)態(tài)生成一個(gè)順序表存儲(chǔ)空間并由L指向該空間，如“L=(SeqList*)malloc(sizeof(SeqList));”。在這種定義下，List.data[i]或L->data[i]均表示順序表中第i個(gè)元素的值，而List.len或L->len均表示順序表的表長(zhǎng)，兩種表示如圖所示。

線性表的順序存儲(chǔ)——順序表

2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)

線性表的順序存儲(chǔ)

順序表基本運(yùn)算的實(shí)現(xiàn)

線性表1.順序表的初始化順序表的初始化就是構(gòu)造一個(gè)空表。將L設(shè)為指針變量，然后動(dòng)態(tài)分配順序表的存儲(chǔ)空間，并設(shè)表長(zhǎng)len=0。算法如下：SeqList*Init_SeqList(){SeqList*L;L=(SeqList*)malloc(sizeof(SeqList));L->len=0;returnL;}

順序表算法實(shí)現(xiàn)

線性表2.建立順序表依次輸入順序表的長(zhǎng)度n和n個(gè)順序表元素即可建立順序表。算法如下：voidCreatList(SeqList**L){inti,n;printf("InputlengthofList:");scanf("%d",&n);printf("InputelementsofList:\n");for(i=1;i<=n;i++)scanf("%d",&(*L)->data[i]);(*L)->len=n;}

順序表算法實(shí)現(xiàn)

線性表3.插入運(yùn)算：在表的第i個(gè)位置插入一個(gè)值為x的新元素，使得原表長(zhǎng)為n的表變?yōu)楸黹L(zhǎng)為n+1的表。插入x的過(guò)程如下：（1）按an到ai的順序依次將an～ai后移一個(gè)元素位置，為插入的x讓出存儲(chǔ)位置。（2）將x放入空出的第i個(gè)位置。（3）修改表長(zhǎng)len的值（len同時(shí)是指向最后一個(gè)元素的指針），使其指向新的表尾元素。插入時(shí)可能出現(xiàn)下列非法情況：（1）當(dāng)L->len=MAXSIZE-1，順序表已放滿元素。（2）當(dāng)i＜1或i≥MAXSIZE時(shí)，i已超出數(shù)組范圍。（3）當(dāng)L->len+1＜i＜MAXSIZE時(shí)，i雖沒(méi)有超出數(shù)組范圍，但i指示的位置使得順序表元素不再連續(xù)存放。（2）、（3）可以用i＜1或i＞L->len+1表示。

順序表算法實(shí)現(xiàn)

線性表插入算法如下：voidInsert_SeqList(SeqList*L,inti,datatypex){intj;if(L->len==MAXSIZE-1) //表滿

printf("TheListisfull!\n");elseif(i<1||i>L->len+1) //插入位置非法

printf("Thepositionisinvalid!\n");else{for(j=L->len;j>=i;j--) //將an～ai順序后移一個(gè)元素位置

L->data[j+1]=L->data[j];L->data[i]=x; //插入x到第i個(gè)位置

L->len++; //表長(zhǎng)增1}}}

順序表算法實(shí)現(xiàn)

線性表4.刪除運(yùn)算：將順序表中第i個(gè)元素從表中除去，刪除后使原表長(zhǎng)為n的順序表成為表長(zhǎng)為n-1的順序表。刪除ai的過(guò)程如下：（1）按ai+1到an的順序依次將ai+1～an前移一個(gè)元素位置，移動(dòng)的同時(shí)即完成了對(duì)ai的刪除。（2）修改len值，使其仍指向表的最后一個(gè)元素。刪除時(shí)可能會(huì)出現(xiàn)下列非法情況：（1）當(dāng)L->len=0時(shí)，順序表為空而無(wú)法刪除。（2）當(dāng)i＜1或i＞L->Len時(shí)，i位置上沒(méi)有元素，即刪除位置非法。

順序表算法實(shí)現(xiàn)

線性表刪除算法如下：voidDelete_SeqList(SeqList*L,datatypei){intj;if(L->len==0) //表為空

printf("TheListisempt!\n");elseif(i<1||i>L->len) //刪除位置非法

printf("Thepositionisinvalid!\n");else{for(j=i+1;j<=L->len;j++)//將ai+1～an順序前移一個(gè)位置實(shí)現(xiàn)對(duì)ai的刪除

L->data[j-1]=L->data[j];L->len--; //表長(zhǎng)減1}}

順序表算法實(shí)現(xiàn)

線性表5.查找運(yùn)算：在順序表中查找與給定值x相等的元素。完成該運(yùn)算最簡(jiǎn)單的方法是：從第一個(gè)元素a1起依次和x比較，直至找到一個(gè)與x相等的元素時(shí)則返回該元素的存儲(chǔ)位置（即下標(biāo)）；如果查遍整個(gè)表都沒(méi)找到與x相等的元素則返回0值。算法如下：intLocation_SeqList(SeqList*L,datatypex){inti=1; //從第一個(gè)元素開始查找

while(i<L->len&&L->data[i]!=x)//順序表未查完且當(dāng)前元素不是要找的元素

i++;if(L->data[i]==x)returni; //找到則返回其位置值

elsereturn0; //未找到則返回0值}

順序表算法實(shí)現(xiàn)

線性表查找算法的主要運(yùn)算是比較。顯然，比較的次數(shù)與x在表中的位置有關(guān)，當(dāng)ai=x時(shí)，對(duì)算法需要比較i次，在等概率的情況下，查找成功的平均比較次數(shù)為

因此，查找算法的時(shí)間復(fù)雜度為O(n)。

順序表算法實(shí)現(xiàn)

2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)

順序表表示的線性表特點(diǎn)是用物理位置上的鄰接關(guān)系來(lái)表示元素之間的邏輯關(guān)系，使我們可以隨機(jī)存取表中的任意一個(gè)元素，但也產(chǎn)生了在插入和刪除操作中移動(dòng)大量元素的問(wèn)題。鏈?zhǔn)酱鎯?chǔ)可用連續(xù)或不連續(xù)的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的元素，元素之間的邏輯關(guān)系無(wú)法用物理位置上的鄰接關(guān)系來(lái)表示，因此，需要用“指針”來(lái)指示元素之間的邏輯關(guān)系，即通過(guò)“指針”鏈接起元素之間的鄰接關(guān)系，而“指針”要占用額外存儲(chǔ)空間。鏈?zhǔn)酱鎯?chǔ)方式失去了順序表可以隨機(jī)存取元素的功能,但卻換來(lái)了存儲(chǔ)空間操作的方便性：進(jìn)行插入和刪除操作時(shí)無(wú)需移動(dòng)大量的元素。本節(jié)將從四個(gè)方面介紹線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)。2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)

單鏈表

單鏈表運(yùn)算實(shí)現(xiàn)

循環(huán)鏈表

單鏈表應(yīng)用示例

線性表

單鏈表

在每個(gè)元素中除了含有數(shù)據(jù)信息外，還要有一個(gè)指針用來(lái)指向它的直接后繼元素，即通過(guò)指針建立起元素之間的線性關(guān)系，我們稱這種元素為結(jié)點(diǎn)。結(jié)點(diǎn)中存放數(shù)據(jù)信息的部分稱為數(shù)據(jù)域，存放指向后繼結(jié)點(diǎn)指針的部分稱為指針域線性表中的n個(gè)元素通過(guò)各自結(jié)點(diǎn)的指針域“鏈”在一起又被稱為鏈表。每個(gè)結(jié)點(diǎn)中只有一個(gè)指向后繼結(jié)點(diǎn)的指針，故稱其為單鏈表。鏈表是由一個(gè)個(gè)結(jié)點(diǎn)構(gòu)成的，單鏈表結(jié)點(diǎn)的定義如下：typedefstructnode{datatypedata; //data為結(jié)點(diǎn)的數(shù)據(jù)信息

structnode*next;//next為指向后繼結(jié)點(diǎn)的指針}LNode; //單鏈表結(jié)點(diǎn)類型結(jié)點(diǎn)結(jié)構(gòu)如圖

線性表

單鏈表

線性表（a1,a2,a3,a4,a5,a6）對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意如下圖所示。將第一個(gè)結(jié)點(diǎn)的地址200放入到一個(gè)指針變量如H中，最后一個(gè)結(jié)點(diǎn)由于沒(méi)有后繼，其指針域必須置空（NULL）以表明鏈表到此結(jié)束。通過(guò)指針H就可以由第一個(gè)結(jié)點(diǎn)的地址開始“順藤摸瓜”地找到每一個(gè)結(jié)點(diǎn)。

線性表

單鏈表

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)具有以下特點(diǎn)：（1）邏輯關(guān)系相鄰的元素在物理位置上可以不相鄰。（2）表中的元素只能順序訪問(wèn)而不能隨機(jī)訪問(wèn)。（3）表的大小可以動(dòng)態(tài)變化。（4）插入、刪除等操作只需修改指針（地址）而無(wú)需移動(dòng)元素。單鏈表關(guān)心的是結(jié)點(diǎn)之間的邏輯關(guān)系，而對(duì)每個(gè)結(jié)點(diǎn)的實(shí)際存儲(chǔ)地址并不感興趣，可以形象地畫為下圖所示的形式。通常用“頭指針”來(lái)標(biāo)識(shí)一個(gè)單鏈表，如單鏈表L、單鏈表H等均是指單鏈表中的第一個(gè)結(jié)點(diǎn)的地址存放在指針變量L或H中；當(dāng)頭指針為“NULL”時(shí)則表示單鏈表為空。

線性表

單鏈表

在線性表的鏈?zhǔn)酱鎯?chǔ)中，為了便于插入和刪除算法的實(shí)現(xiàn)且使單鏈表的操作在各種情況下統(tǒng)一，在單鏈表的第一個(gè)結(jié)點(diǎn)之前添加了一個(gè)頭結(jié)點(diǎn)，該頭結(jié)點(diǎn)不存儲(chǔ)任何數(shù)據(jù)信息，只是用其指針域中的指針指向單鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，即通過(guò)頭指針指向的頭結(jié)點(diǎn)，可以訪問(wèn)到單鏈表中的所有數(shù)據(jù)結(jié)點(diǎn)。

添加頭結(jié)點(diǎn)后，無(wú)論單鏈表中的結(jié)點(diǎn)如何變化，比如插入新結(jié)點(diǎn)、刪除單鏈表中任意一個(gè)數(shù)據(jù)結(jié)點(diǎn)，頭結(jié)點(diǎn)將始終不變，這使得單鏈表的運(yùn)算變得更加簡(jiǎn)單。2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)

單鏈表

單鏈表運(yùn)算實(shí)現(xiàn)

循環(huán)鏈表

單鏈表應(yīng)用示例

線性表

單鏈表運(yùn)算實(shí)現(xiàn)

1.建立單鏈表1）在鏈表頭部插入結(jié)點(diǎn)的方式建立單鏈表單鏈表的建立是從空表開始的，每讀入一個(gè)數(shù)據(jù)則申請(qǐng)一個(gè)結(jié)點(diǎn)，然后插在頭結(jié)點(diǎn)之后，存儲(chǔ)線性表（‘A’,‘B’,‘C’,‘D’）的單鏈表建立過(guò)程如下圖所示。因?yàn)槭窃趩捂湵眍^部插入，故讀入數(shù)據(jù)的順序與線性表中元素的順序正好相反。

線性表

單鏈表運(yùn)算實(shí)現(xiàn)

算法實(shí)現(xiàn)如下：voidCreateLinkList(LNode**head){//將主調(diào)函數(shù)中指向待生成單鏈表的指針地址（如&p）傳給**headcharx;LNode*p;*head=(LNode*)malloc(sizeof(LNode));//在主調(diào)函數(shù)空間生成鏈表頭結(jié)點(diǎn)

(*head)->next=NULL; //*head為鏈表頭指針

printf("Inputanycharstring:\n");scanf("%c",&x);//結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閏har型，讀入結(jié)點(diǎn)數(shù)據(jù)

while(x!='\n') //生成鏈表的其他結(jié)點(diǎn)

{p=(LNode*)malloc(sizeof(LNode));//申請(qǐng)一個(gè)結(jié)點(diǎn)空間

p->data=x;p->next=(*head)->next;//將頭結(jié)點(diǎn)的next值賦給新結(jié)點(diǎn)*p的next(*head)->next=p;//頭結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)*p實(shí)現(xiàn)在表頭插入

scanf("%c",&x); //繼續(xù)生成下一個(gè)新結(jié)點(diǎn)

}

線性表

單鏈表運(yùn)算實(shí)現(xiàn)

2）在鏈表的尾部插入結(jié)點(diǎn)的方式建立單鏈表在頭部插入結(jié)點(diǎn)的方式生成單鏈表較為簡(jiǎn)單，但生成結(jié)點(diǎn)的順序與線性表中的元素順序正好相反。若希望兩者的次序一致，則可采用尾插法來(lái)生成單鏈表。由于每次都是將新結(jié)點(diǎn)插入鏈表的尾部，所以必須再增加一個(gè)指針q來(lái)始終指向單鏈表的尾結(jié)點(diǎn)，以方便新結(jié)點(diǎn)的插入。在鏈尾插入結(jié)點(diǎn)生成單鏈表的過(guò)程示意如下圖所示。

線性表

單鏈表運(yùn)算實(shí)現(xiàn)

算法如下：LNode*CreateLinkList(){LNode*head,*p,*q;charx;head=(LNode*)malloc(sizeof(LNode)); //生成頭結(jié)點(diǎn)

head->next=NULL;p=head;q=p; //指針q始終指向鏈尾結(jié)點(diǎn)

printf("Inputanycharstring:\n");scanf("%c",&x);while(x!='\n') //生成鏈表的其他結(jié)點(diǎn)

{p=(LNode*)malloc(sizeof(LNode));p->data=x;p->next=NULL;q->next=p; //在鏈尾插入

q=p;scanf("%c",&x);}returnhead; //返回單鏈表表頭指針}

線性表

單鏈表運(yùn)算實(shí)現(xiàn)

2.求表長(zhǎng)算法如下：intLength_LinkList(LNode*head){LNode*p=head; //p指向單鏈表頭結(jié)點(diǎn)

inti=0; //i為結(jié)點(diǎn)計(jì)數(shù)器

while(p->next!=NULL){p=p->next;i++;}returni; //返回表長(zhǎng)值i}求表長(zhǎng)算法的時(shí)間復(fù)雜度為O(n)

線性表

單鏈表運(yùn)算實(shí)現(xiàn)

3.查找

1）按序號(hào)查找從鏈表的第一個(gè)結(jié)點(diǎn)開始查找，若當(dāng)前結(jié)點(diǎn)是第i個(gè)結(jié)點(diǎn)，則返回指向該結(jié)點(diǎn)的指針值，否則繼續(xù)向后查找；如果整個(gè)表都無(wú)序號(hào)為i的結(jié)點(diǎn)（i大于鏈表中結(jié)的個(gè)數(shù)），則返回空指針值。算法如下：LNode*Get_LinkList(LNode*head,inti){ //在單鏈表head中查找第i個(gè)結(jié)點(diǎn)

LNode*p=head; //由第一個(gè)結(jié)點(diǎn)開始查找

intj=0;while(p!=NULL&&j<i) //當(dāng)未查到鏈尾且j小于i時(shí)繼續(xù)查找

{p=p->next;j++;}returnp;//找到則返回指向i結(jié)點(diǎn)的指針值，找不到則p返回空值}

線性表

單鏈表運(yùn)算實(shí)現(xiàn)

2）按值查找從鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)開始查找，若當(dāng)前結(jié)點(diǎn)值等于x則返回指向該結(jié)點(diǎn)的指針值，否則繼續(xù)向后查找；如果整個(gè)表都找不到值等于x的結(jié)點(diǎn)則返回空值。算法如下：LNode*Locate_LinkList(LNode*head,charx){ //在單鏈表中查找結(jié)點(diǎn)值為x的結(jié)點(diǎn)

LNode*p=head->next; //由第一個(gè)數(shù)據(jù)結(jié)點(diǎn)開始查找

while(p!=NULL&&p->data!=x) //當(dāng)未查到鏈尾且當(dāng)前結(jié)點(diǎn)不等于x時(shí)繼續(xù)查找

p=p->next;returnp;//找到則返回指向值為x的結(jié)點(diǎn)的指針值，找不到則p返回空值}查找算法的時(shí)間復(fù)雜度均為O(n)。

線性表

單鏈表運(yùn)算實(shí)現(xiàn)

4.插入鏈表中的各結(jié)點(diǎn)是通過(guò)指針鏈接起來(lái)的，因而可以通過(guò)改變鏈表結(jié)點(diǎn)中指針的指向來(lái)實(shí)現(xiàn)鏈表結(jié)點(diǎn)的插入與刪除。數(shù)組進(jìn)行插入或刪除操作時(shí)需要移動(dòng)大量的數(shù)組元素，但是鏈表的插入或刪除操作由于僅需修改有關(guān)指針的指向而變得非常容易。在鏈表結(jié)點(diǎn)*p之后插入鏈表結(jié)點(diǎn)*q的示意如圖所示。插入操作如下：

①q->next=p->next;②p->next=q;

線性表

單鏈表運(yùn)算實(shí)現(xiàn)

在涉及改變指針值的操作中一定要注意指針值的改變次序，否則容易出錯(cuò)。假如上面插入操作的順序改為

①p->next=q;②q->next=p->next;

此時(shí)，①將使鏈表結(jié)點(diǎn)*p的指針p->next指向鏈表結(jié)點(diǎn)*q，②將*p的指針p->next值（指向*q）賦給了結(jié)點(diǎn)*q的指針q->next，這使得結(jié)點(diǎn)*q的指針q->next指向結(jié)點(diǎn)*q自身；這種結(jié)果將導(dǎo)致鏈表由此斷為兩截，而后面的一截鏈表就“丟失”了。因此，在插入鏈表結(jié)點(diǎn)*q時(shí)，應(yīng)將鏈表結(jié)點(diǎn)*p的指針p->next值（指向后繼結(jié)點(diǎn)）先賦給結(jié)點(diǎn)*q的指針

q->next（即語(yǔ)句“q->next=p->next;”），以防止鏈表的斷開，然后再使結(jié)點(diǎn)*p的指針p->next改為指向結(jié)點(diǎn)*q（即語(yǔ)句“p->next=q;”）。

線性表

單鏈表運(yùn)算實(shí)現(xiàn)

算法如下：voidInsert_LinkList(LNode*head,inti,charx){//在單鏈表head的第i個(gè)位置上插入值為x的元素

LNode*p,*q;p=Get_LinkList(head,i-1); //查找第i-1個(gè)結(jié)點(diǎn)*/if(p==NULL)printf("Error!\n"); //第i-1個(gè)位置不存在而無(wú)法插入

else{q=(LNode*)malloc(sizeof(LNode)); //申請(qǐng)結(jié)點(diǎn)空間

q->data=x;q->next=p->next; //完成插入操作①p->next=q; //完成插入操作②}}該算法的時(shí)間花費(fèi)在尋找第i-1個(gè)結(jié)點(diǎn)上，故算法時(shí)間復(fù)雜度為O(n)。

線性表

單鏈表的運(yùn)算實(shí)現(xiàn)

5.刪除要?jiǎng)h除一個(gè)鏈表結(jié)點(diǎn)必須知道它的前驅(qū)鏈表結(jié)點(diǎn)，只有使指針變量p指向這個(gè)前驅(qū)鏈表結(jié)點(diǎn)時(shí)，才可以通過(guò)下面的語(yǔ)句實(shí)現(xiàn)所要?jiǎng)h除的操作：p->next=p->next->next;即通過(guò)改變鏈表結(jié)點(diǎn)*p中指針p->nxet的指向，使它由指向待刪結(jié)點(diǎn)改為指向待刪結(jié)點(diǎn)的后繼結(jié)點(diǎn)，由此達(dá)到從鏈表中刪去待刪結(jié)點(diǎn)的目的，如圖所示，其中①為p->next=p->next->next。多數(shù)情況下，在刪除待刪結(jié)點(diǎn)前都要先找到這個(gè)待刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，這就需要借助一個(gè)指針變量（如p）來(lái)定位于這個(gè)前驅(qū)結(jié)點(diǎn)，然后才能進(jìn)行刪除操作，如圖所示。

線性表

單鏈表的運(yùn)算實(shí)現(xiàn)算法如下：voidDel_LinkList(LNode*head,inti){//刪除單鏈表head上的第i個(gè)數(shù)據(jù)結(jié)點(diǎn)

LNode*p,*q;p=Get_LinkList(head,i-1); //查找第i-1個(gè)結(jié)點(diǎn)

if(p==NULL)printf("第i-1個(gè)結(jié)點(diǎn)不存在!\n");//待刪結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)不存在，無(wú)待刪結(jié)點(diǎn)

elseif(p->next==NULL)printf("第i個(gè)結(jié)點(diǎn)不存在!\n"); //待刪結(jié)點(diǎn)不存在

else{q=p->next; //q指向第i個(gè)結(jié)點(diǎn)

p->next=q->next; //從鏈表中刪除第i個(gè)結(jié)點(diǎn)

free(q); //系統(tǒng)回收第i個(gè)結(jié)點(diǎn)的存儲(chǔ)空間

}}刪除算法的時(shí)間復(fù)雜度為O(n)。2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)

單鏈表

單鏈表運(yùn)算實(shí)現(xiàn)

循環(huán)鏈表

單鏈表應(yīng)用示例

線性表

循環(huán)鏈表

循環(huán)鏈表，將單鏈表中最后一個(gè)結(jié)點(diǎn)的指針值由空改為指向單鏈表的頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。這樣，從鏈表中的任一結(jié)點(diǎn)位置出發(fā)都可以找到鏈表的其他結(jié)點(diǎn)。在循環(huán)鏈表上的操作基本上與單鏈表相同，只是將原來(lái)判斷指針是否為NULL改為判斷是否為頭指針，再無(wú)其他變化。帶頭結(jié)點(diǎn)的循環(huán)鏈表示意圖為：

線性表

循環(huán)鏈表

在帶頭結(jié)點(diǎn)的循環(huán)鏈表中查找值等于x的結(jié)點(diǎn)，其實(shí)現(xiàn)算法如下：LNode*Locate_CycLink(LNode*head,datatypex){LNode*p=head->next; //由第一個(gè)數(shù)據(jù)結(jié)點(diǎn)開始查while(p!=head&&p->data!=x)//未查完循環(huán)鏈表且當(dāng)前結(jié)點(diǎn)不等于x時(shí)繼續(xù)查找

p=p->next;if(p!=head)returnp; //找到值等于x的結(jié)點(diǎn)*p，返回其指針值pelsereturnNULL;//當(dāng)p又查到頭結(jié)點(diǎn)時(shí)則無(wú)等于x值的結(jié)點(diǎn)，故返回NULL值}

由于鏈表的操作通常是在表頭或表尾進(jìn)行，故也可改變循環(huán)鏈表的標(biāo)識(shí)方法，即不用頭指針而用一個(gè)指向尾結(jié)點(diǎn)的指針R來(lái)標(biāo)識(shí)循環(huán)鏈表。這種標(biāo)識(shí)的好處是可以直接找到鏈尾結(jié)點(diǎn)，而找到頭結(jié)點(diǎn)也非常容易，R->next即為指向頭結(jié)點(diǎn)的指針。2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)

單鏈表

單鏈表運(yùn)算實(shí)現(xiàn)

循環(huán)鏈表

單鏈表應(yīng)用示例

線性表

單鏈表應(yīng)用示例例1.已知單鏈表H如圖所示，寫一個(gè)算法將其逆置。解：由于頭插法生成的單鏈表其結(jié)點(diǎn)序列正好與輸入數(shù)據(jù)的順序相反，因此，應(yīng)依次取出題設(shè)鏈表中的每一個(gè)數(shù)據(jù)結(jié)點(diǎn)，然后用頭插法再插入新鏈表中即可實(shí)現(xiàn)單鏈表的逆置。在算法中，使指針p始終指向由剩余結(jié)點(diǎn)構(gòu)成的鏈表中的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，而指針q則從這剩余結(jié)點(diǎn)鏈表中取出第一個(gè)數(shù)據(jù)結(jié)點(diǎn)插入頭結(jié)點(diǎn)*H之后；當(dāng)然，還應(yīng)使指針p繼續(xù)指向剩余結(jié)點(diǎn)鏈表中的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，即移到剛?cè)〕龅慕Y(jié)點(diǎn)之后的下一個(gè)數(shù)據(jù)結(jié)點(diǎn)位置。算法實(shí)現(xiàn)如下：voidConvert(LNode*H){LNode*p,*q;p=H->next; //p指向剩余結(jié)點(diǎn)鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)

H->next=NULL; //新鏈表H初始為空

線性表

單鏈表應(yīng)用示例while(p!=NULL){q=p; //從剩余結(jié)點(diǎn)鏈表中取出第一個(gè)結(jié)點(diǎn)

p=p->next; //p繼續(xù)指向剩余結(jié)點(diǎn)鏈表新的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)

q->next=H->next; //將取出的結(jié)點(diǎn)*q插入新鏈表H的鏈?zhǔn)?/p>

H->next=q;}}該算法只對(duì)鏈表順序掃描一遍即實(shí)現(xiàn)鏈表的逆置，故其時(shí)間復(fù)雜度為O(n)。

線性表

單鏈表應(yīng)用示例例2.對(duì)兩個(gè)元素遞增有序的單鏈表A和B，編寫算法將A、B合并成一個(gè)按元素遞減有序（允許有相同值）的單鏈表C，要求算法使用A、B中的原有結(jié)點(diǎn)，不允許增加新結(jié)點(diǎn)。解：由例1可知，將遞增有序改為遞減有序只能采用頭插法，如果仍保持遞增有序則應(yīng)采用尾插法，因此本題采用頭插法實(shí)現(xiàn)。算法如下：

voidMerge(LNode*A,LNode*B,LNode**C){ //將增序鏈表A、B合并成降序鏈表*CLNode*p,*q,*s;p=A->next; //p始終指向鏈表A的第一個(gè)未比較的數(shù)據(jù)結(jié)點(diǎn)

q=B->next; //q始終指向鏈表B的第一個(gè)未比較的數(shù)據(jù)結(jié)點(diǎn)

*C=A; //生成鏈表的*C的頭結(jié)點(diǎn)

(*C)->next=NULL;free(B); //回收鏈表B的頭結(jié)點(diǎn)空間

while(p!=NULL&&q!=NULL){//將A、B兩鏈表中當(dāng)前比較結(jié)點(diǎn)中值小者賦給*s

線性表

單鏈表應(yīng)用示例

if(p->data<q->data){s=p;p=p->next;}else{s=q；q=q->next;}s->next=(*C)->next;//用頭插法將結(jié)點(diǎn)*s插到鏈表*C的頭結(jié)點(diǎn)之后

(*C)->next=s;}if(p==NULL) //如果指向鏈表A的指針*p為空，則使*p指向鏈表Bp=q;while(p!=NULL){//將*p所指鏈表中的剩余結(jié)點(diǎn)依次摘下插入鏈表*C的鏈?zhǔn)?/p>

s=p；p=p->next;s->next=(*C)->next;(*C)->next=s;}對(duì)m個(gè)結(jié)點(diǎn)的單鏈表A和n個(gè)結(jié)點(diǎn)的單鏈表B，該算法的時(shí)間復(fù)雜度為O(m+n)。

線性表

單鏈表應(yīng)用示例例3.約瑟夫（Josephus）問(wèn)題：設(shè)有n個(gè)人圍成一圈并順序編號(hào)為1～n。由編號(hào)為k的人進(jìn)行1到m的報(bào)數(shù)，數(shù)到m的人出圈；接著再?gòu)乃南乱粋€(gè)人重新開始1到m的報(bào)數(shù)，直到所有的人都出圈為止，請(qǐng)輸出出圈人的出圈次序。解：為了便于循環(huán)查找的統(tǒng)一性，我們采用不帶頭結(jié)點(diǎn)的循環(huán)鏈表，即每一個(gè)人對(duì)應(yīng)鏈表中的一個(gè)結(jié)點(diǎn)，某人出圈相當(dāng)于從鏈表中刪去此人所對(duì)應(yīng)的結(jié)點(diǎn)。整個(gè)算法可分為以下兩個(gè)部分：（1）建立一個(gè)具有n個(gè)結(jié)點(diǎn)且無(wú)頭結(jié)點(diǎn)的循環(huán)鏈表。（2）不斷從表中刪除出圈人結(jié)點(diǎn)，直到鏈表中只剩下一個(gè)結(jié)點(diǎn)時(shí)為止。算法如下：voidJosephus(intn,intm,intk){LNode*p,*q;inti;p=(LNode*)malloc(sizeof(LNode));q=p;

線性表

單鏈表應(yīng)用示例for(i=1;i<n;i++)

//從編號(hào)k開始建立一個(gè)單鏈表

{q->data=k;k=k%n+1;q->next=(LNode*)malloc(sizeof(LNode));q=q->next;}q->data=k;q->next=p; //鏈接成循環(huán)單鏈表，此時(shí)p指向編號(hào)為k的結(jié)點(diǎn)

while(p->next!=p) //當(dāng)循環(huán)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)不為1時(shí)

{for(i=1;i<m;i++){q=p;p=p->next;}//p指向報(bào)數(shù)為m的結(jié)點(diǎn)，q指向報(bào)數(shù)為m-1的結(jié)點(diǎn)

q->next=p->next; //刪除報(bào)數(shù)為m的結(jié)點(diǎn)

printf("%4d",p->data); //輸出出圈人的編號(hào)

free(p); //釋放被刪結(jié)點(diǎn)的空間

p=q->next; //p指向新的開始報(bào)數(shù)結(jié)點(diǎn)

}printf("%4d",p->data); //輸出最后出圈人的編號(hào)}22:10:57第3章棧和隊(duì)列22:10:57

第3章棧和隊(duì)列棧和隊(duì)列都是操作受限的線性表?xiàng)＃合冗M(jìn)后出隊(duì)列：先進(jìn)先出22:10:57本章主要內(nèi)容:棧的定義及基本運(yùn)算棧的存儲(chǔ)結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)隊(duì)列的定義及基本運(yùn)算隊(duì)列的存儲(chǔ)結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)

第3章棧和隊(duì)列22:10:573.1

棧的定義及基本運(yùn)算

棧的定義

棧的基本操作22:10:57

棧的定義棧是限定僅在一端進(jìn)行操作的線性表?xiàng)ｍ敚╰op）：允許進(jìn)行插入和刪除元素操作的一端棧底（bottom）：固定不變的另一端空棧：不含元素的棧滿棧：存儲(chǔ)空間被用完的棧先進(jìn)后出22:10:573.1

棧的定義及基本運(yùn)算

棧的定義

棧的基本操作22:10:57

棧的基本操作棧初始化Init_Stack(s)：生成一個(gè)空棧s判?？誆mpty_Stack(s)：若棧s為空則返回1，否則返回0入棧Push_Stack(s,x)：在棧s的頂部插入一個(gè)新元素x，使x成為新的棧頂元素，棧變化出棧Pop_Stack(s,x)：在棧s非空的情況下，操作結(jié)果是將棧s的頂部元素從棧中刪除，并由x返回棧頂元素值，即棧中少了一個(gè)元素，棧變化讀棧頂元素Top_Stack(s,x)：在棧s非空的情況下，操作結(jié)果是將棧s的頂部元素讀到x中，棧不變化22:10:57本章主要內(nèi)容:棧的定義及基本運(yùn)算棧的存儲(chǔ)結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)隊(duì)列的定義及基本運(yùn)算隊(duì)列的存儲(chǔ)結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)

第3章棧和隊(duì)列22:10:573.2棧的存儲(chǔ)結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)

順序棧

兩個(gè)順序棧共享連續(xù)空間

鏈棧22:10:57

順序棧順序棧：棧的順序存儲(chǔ)結(jié)構(gòu)利用一組地址連續(xù)的存儲(chǔ)單元來(lái)依次存放由棧底到棧頂?shù)乃性?，附加一個(gè)top指針來(lái)指示棧頂元素在順序棧中的位置typedefstruct{datatypedata[MAXSIZE];//棧中元素存儲(chǔ)空間

inttop; //棧頂指針}SeqStack;順序棧的類型定義22:10:57

順序棧順序棧操作示意圖22:10:57

順序棧順序棧基本操作：初始化棧voidInit_SeqStack(SeqStack**s){*s=(SeqStack*)malloc(sizeof(SeqStack));//在主調(diào)函數(shù)中申請(qǐng)?？臻g

(*s)->top=-1;//置?？諛?biāo)志}22:10:57

順序棧順序?；静僮鳎号袛鄺Ｊ欠駷榭読ntEmpty_SeqStack(SeqStack*s){if(s->top==-1) //棧為空時(shí)返回1值

return1;elsereturn0; //棧不空時(shí)返回0值}22:10:57

順序棧順序?；静僮鳎喝霔oidPush_SeqStack(SeqStack*s,datatypex){if(s->top==MAXSIZE-1)printf("Stackisfull!\n"); //棧已滿

else{s->top++; //先使棧頂指針top增1s->data[s->top]=x;//再將元素x壓入棧*s中

}}22:10:57

順序棧順序?；静僮鳎撼鰲oidPop_SeqStack(SeqStack*s,datatype*x){//將棧*s中的棧頂元素出棧并通過(guò)參數(shù)x返回給主調(diào)函數(shù)

if(s->top==-1)printf("Stackisempty!\n"); //棧為空

else{*x=s->data[s->top];//棧頂元素出棧

s->top--; //棧頂指針top減1}}22:10:57

順序棧順序?；静僮鳎喝ｍ斣豽oidTop_SeqStack(SeqStack*s,datatype*x){if(s->top==-1)printf("Stackisempty!\n"); //棧為空

else*x=s->data[s->top];//取棧頂元素值賦給*x}22:10:573.2棧的存儲(chǔ)結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)

順序棧

兩個(gè)順序棧共享連續(xù)空間

鏈棧22:10:57兩個(gè)順序棧共享連續(xù)空間利用棧底位置相對(duì)不變這一特點(diǎn)，兩個(gè)順序?？梢怨蚕硪粋€(gè)一維數(shù)據(jù)空間來(lái)互補(bǔ)余缺。實(shí)現(xiàn)方法是將兩個(gè)棧的棧底分設(shè)在一維數(shù)據(jù)空間的兩端，讓其各自的棧頂由兩端向中間延伸22:10:57兩個(gè)順序棧共享連續(xù)空間多個(gè)棧共享一維數(shù)據(jù)空間的問(wèn)題就比較復(fù)雜，因?yàn)橐粋€(gè)存儲(chǔ)空間只有兩端是固定的，需要：設(shè)置棧頂指針和棧底指針。這種情況下，當(dāng)某個(gè)棧發(fā)生上溢時(shí)，如果整個(gè)一維數(shù)據(jù)空間未被占滿，則必須移動(dòng)某些（或某個(gè)）棧來(lái)騰出空間解決所發(fā)生的上溢22:10:573.2棧的存儲(chǔ)結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)

順序棧

兩個(gè)順序棧共享連續(xù)空間

鏈棧22:10:57鏈棧鏈棧是指