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

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

2、研究這些數(shù)據(jù)自身的特性以及它們之間的相互關(guān)系。本章內(nèi)容提要:數(shù)據(jù)結(jié)構(gòu)的概念 邏輯結(jié)構(gòu)與存儲結(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í)際問題的軟件開發(fā)一般分為下面幾個步驟： 數(shù)據(jù)結(jié)構(gòu)的概念 （1）分析階段：分析實(shí)際問題，從中抽象出一個數(shù)學(xué)模型。 （2）設(shè)計(jì)階段：設(shè)計(jì)出解決數(shù)學(xué)模型的算法。 （3）編程階段：用適當(dāng)?shù)木幊陶Z言編寫出可執(zhí)行的程序。 （4）測試階段：測試、修改直到得到問題的解答。 緒論數(shù)據(jù)結(jié)構(gòu)課程集中討論軟件開發(fā)過程中的設(shè)計(jì)階段，同時(shí)涉及分析階段和編程階段的若干基本問題。此外，為了構(gòu)造出好的數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)，

3、還需考慮數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)的評價(jià)與選擇。因此，數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容包括了下表所示的數(shù)據(jù)表示方面和數(shù)據(jù)處理方面的3個層次。 數(shù)據(jù)結(jié)構(gòu)的概念 方 面層 次數(shù)據(jù)表示數(shù)據(jù)處理抽象邏輯結(jié)構(gòu)基本運(yùn)算實(shí)現(xiàn)存儲結(jié)構(gòu)算法評價(jià)不同數(shù)據(jù)結(jié)構(gòu)的比較與算法分析 緒論數(shù)據(jù)結(jié)構(gòu)的核心內(nèi)容是分解與抽象。通過對問題的抽象，舍棄數(shù)據(jù)元素（含義見后）的具體內(nèi)容，就得到邏輯結(jié)構(gòu)；類似地，通過分解將處理要求劃分成各種功能，再通過抽象舍棄實(shí)現(xiàn)的細(xì)節(jié)，就得到基本運(yùn)算的定義。上述兩個方面的結(jié)合使人們將問題轉(zhuǎn)換為數(shù)據(jù)結(jié)構(gòu)，這是一個從具體（即具體問題）到抽象（即數(shù)據(jù)結(jié)構(gòu)）的過程。通過增加對實(shí)現(xiàn)細(xì)節(jié)的考慮，進(jìn)一步得到存儲結(jié)構(gòu)和實(shí)現(xiàn)算法，從而完成設(shè)計(jì)任

4、務(wù)，這是一個從抽象（即數(shù)據(jù)結(jié)構(gòu)）到具體（即具體實(shí)現(xiàn)）的過程。熟練掌握這兩個過程是數(shù)據(jù)結(jié)構(gòu)課程在專業(yè)技能培養(yǎng)方面的基本目標(biāo)。在系統(tǒng)地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識之前，先對一些基本概念和術(shù)語予以說明。 數(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ù)是人們利用文字符號、數(shù)學(xué)符號以及其他規(guī)定的符號對現(xiàn)實(shí)世界的事物及其活動所做的抽象描述。簡言之，數(shù)據(jù)是信息的載體，是對客觀事物的符號化表示。從計(jì)算機(jī)的角度看，數(shù)據(jù)是計(jì)算機(jī)程序?qū)λ枋隹陀^事物進(jìn)行加工處理的一種表示，凡是能夠被計(jì)算機(jī)識別、存取和加工處理的符號、字符、圖形、圖像、聲音、視頻信號等都可以稱為數(shù)據(jù)。 我們?nèi)粘Ｉ婕暗?/p>

5、數(shù)據(jù)主要分為兩類：一類是數(shù)值數(shù)據(jù)，包括整數(shù)、實(shí)數(shù)和復(fù)數(shù)等，它們主要用于工程和科學(xué)計(jì)算以及商業(yè)事務(wù)處理；另一類是非數(shù)值數(shù)據(jù)，主要包括字符和字符串以及文字、圖形、語音等，它們多用于控制、管理和數(shù)據(jù)處理等領(lǐng)域。 數(shù)據(jù)元素是數(shù)據(jù)集合中的一個“個體”，是數(shù)據(jù)的基本單位。在計(jì)算機(jī)中，數(shù)據(jù)元素通常被作為一個整體來進(jìn)行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)和記錄等。一個數(shù)據(jù)元素可以由一個或多個數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的數(shù)據(jù)最小單位，有時(shí)也稱為字段或域。 數(shù)據(jù)與數(shù)據(jù)元素 緒論 【例1.1】 一個學(xué)生信息（數(shù)據(jù)）表如表1.2所示，請指出表中的數(shù)據(jù)、數(shù)據(jù)元素及數(shù)據(jù)項(xiàng)，并由此得出三者之間的關(guān)

6、系。表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ù)。表中的每一行即為記錄一個學(xué)生信息的數(shù)據(jù)元素，而該行中的每一項(xiàng)則為一個數(shù)據(jù)項(xiàng)。數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)實(shí)際上反映了數(shù)據(jù)組織的三個層次，數(shù)據(jù)可以由若干個數(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é)

7、構(gòu)看成是帶結(jié)構(gòu)的數(shù)據(jù)元素集合。數(shù)據(jù)結(jié)構(gòu)包含以下三個方面的內(nèi)容。（1）數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。（2）數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲器中的存儲方式，即數(shù)據(jù)的存儲結(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)系）來描述數(shù)據(jù)的，它與數(shù)據(jù)如何存儲無關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看成是從具體問題抽象出來的數(shù)學(xué)模型。 數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲器中的映像表示，即在能夠反映數(shù)據(jù)邏輯關(guān)系的前提下數(shù)據(jù)在存儲器中的存儲方式。 數(shù)據(jù)的運(yùn)算是在數(shù)據(jù)上所施加的一系列操作，稱為抽象運(yùn)算。它只考慮這些操作

8、的功能，而暫不考慮如何完成，只有在確定了存儲結(jié)構(gòu)后，才會具體實(shí)現(xiàn)這些操作。也就是說，抽象運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而實(shí)現(xiàn)則是建立在存儲結(jié)構(gòu)上的。最常用的運(yùn)算有檢索、插入、刪除、更新、排序等。 數(shù)據(jù)結(jié)構(gòu)1.2 邏輯結(jié)構(gòu)與存儲結(jié)構(gòu) 邏輯結(jié)構(gòu) 存儲結(jié)構(gòu) 緒論數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間邏輯關(guān)系的描述。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，可以劃分為以下四種基本邏輯結(jié)構(gòu)。（1）集合結(jié)構(gòu)：數(shù)據(jù)元素之間除了“屬于同一集合”的聯(lián)系之外，沒有其他關(guān)系。（2）線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“一對一”的關(guān)系。（3）樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“一對多”的關(guān)系。（4）圖結(jié)構(gòu)（或稱網(wǎng)狀結(jié)構(gòu)）：數(shù)據(jù)元素之間存在著“多對多”的

9、關(guān)系。 邏輯結(jié)構(gòu) 緒論 由于集合結(jié)構(gòu)的簡單性和松散性，所以通常只討論其他三種邏輯結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。若數(shù)據(jù)元素之間的邏輯關(guān)系可以用一個線性序列簡單地表示出來，則稱為線性結(jié)構(gòu)，否則稱為非線性結(jié)構(gòu)。 樹形結(jié)構(gòu)和圖結(jié)構(gòu)就屬于非線性結(jié)構(gòu)。現(xiàn)實(shí)生活中的樓層編號就屬于線性結(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)容無關(guān)。例如，給表1.1中的每個學(xué)生增加一個數(shù)據(jù)項(xiàng)“學(xué)號”，就得到另一個數(shù)據(jù)，但由于所有的數(shù)據(jù)元素仍是“一個接一個排列”，故新數(shù)據(jù)的邏輯結(jié)構(gòu)與原來數(shù)據(jù)的

10、邏輯結(jié)構(gòu)相同，仍是一個線性結(jié)構(gòu)。（2）邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對位置無關(guān)。例如，將表1.1中的學(xué)生按年齡由大到小的順序重新排列就得到另一個表格，但這個新表格中的所有數(shù)據(jù)元素“一個接一個排列”的性質(zhì)并沒有改變，其邏輯結(jié)構(gòu)與原表格相同，還是線性結(jié)構(gòu)。（3）邏輯結(jié)構(gòu)與所含數(shù)據(jù)元素的個數(shù)無關(guān)。例如，在表1.1中增加或刪除若干學(xué)生信息（數(shù)據(jù)元素），所得到的表格仍為線性結(jié)構(gòu)。 邏輯結(jié)構(gòu)1.2 邏輯結(jié)構(gòu)與存儲結(jié)構(gòu) 邏輯結(jié)構(gòu) 存儲結(jié)構(gòu) 緒論 數(shù)據(jù)的存儲結(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ī)中可以有以下四種基本存儲結(jié)構(gòu)。 （

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

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

13、元素。 與順序存儲結(jié)構(gòu)相比，鏈?zhǔn)酱鎯Y(jié)構(gòu)的主要缺點(diǎn)是存儲空間的利用率較低，因?yàn)槌擞糜跀?shù)據(jù)元素的存儲空間外，還需要額外的存儲空間來存儲數(shù)據(jù)元素之間的邏輯關(guān)系。此外，由于邏輯上相鄰的數(shù)據(jù)元素在存儲空間中不一定相鄰，所以不能對數(shù)據(jù)元素進(jìn)行隨機(jī)存取。 緒論 存儲結(jié)構(gòu) 線性結(jié)構(gòu)采用索引存儲方法后就可以對結(jié)點(diǎn)進(jìn)行隨機(jī)訪問。在進(jìn)行插入、刪除運(yùn)算時(shí)，只需改動存儲在索引表中數(shù)據(jù)元素的存儲地址，而不必移動數(shù)據(jù)元素，所以仍保持較高的數(shù)據(jù)修改和運(yùn)算效率。索引存儲結(jié)構(gòu)的缺點(diǎn)是增加了索引表，這也降低了存儲空間的利用率。 哈希（或散列）存儲結(jié)構(gòu)的優(yōu)點(diǎn)是查找速度快，只要給出待查數(shù)據(jù)元素的關(guān)鍵字，就可以立即計(jì)算出該數(shù)據(jù)元素的

14、存儲地址。與前面三種存儲方法不同的是，哈希存儲結(jié)構(gòu)只存儲數(shù)據(jù)元素的數(shù)據(jù)而不存儲數(shù)據(jù)元素之間的邏輯關(guān)系。哈希存儲結(jié)構(gòu)一般只適合于對數(shù)據(jù)進(jìn)行快速查找和插入的場合。 緒論 存儲結(jié)構(gòu) 表1.2在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)下的示意如圖所示：1.3 算法與算法分析 算法的定義和描述 算法分析和復(fù)雜度計(jì)算 緒論 算法的定義和描述 算法是建立在數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上對特定問題求解步驟的一種描述，是若干條指令組成的有限序列，其中每一條指令表示一個或多個操作。算法必須滿足以下性質(zhì)。 （1）有窮性：一個算法必須在有窮步之后結(jié)束，即必須在有限時(shí)間內(nèi)完成。 （2）確定性：算法的每一步必須有確切的含義而沒有二義性。對于相同的輸入

15、，算法執(zhí)行的路徑是唯一的。 （3）可行性：算法所描述的操作都可以通過可實(shí)現(xiàn)的基本運(yùn)算在有限次執(zhí)行后得以完成。 （4）輸入：一個算法可以有零個或多個輸入。 （5）輸出：一個算法具有一個或多個輸出，且輸出與輸入之間存在某種特定的關(guān)系。 緒論 算法的定義和描述 算法的含義與程序十分相似但又有區(qū)別。一個程序不一定滿足有窮性，如操作系統(tǒng)程序只要不停機(jī)執(zhí)行就永不停止，因此，操作系統(tǒng)不是一個算法。此外，程序中的語句最終都要轉(zhuǎn)化（編譯）成計(jì)算機(jī)可執(zhí)行的指令；而算法中的指令則無此限制，即一個算法可采用自然語言如英語、漢語描述，也可以采用圖形方式如流程圖、拓?fù)鋱D描述。算法給出了對一個問題的求解，而程序僅是算法在計(jì)

16、算機(jī)上的實(shí)現(xiàn)。一個算法若用程序設(shè)計(jì)語言來描述，則此時(shí)算法也就是一個程序。 對某個特定問題的求解究竟采用何種數(shù)據(jù)結(jié)構(gòu)及選擇什么算法，需要看問題的具體要求和現(xiàn)實(shí)環(huán)境的各種條件；數(shù)據(jù)結(jié)構(gòu)的選擇是否恰當(dāng)將直接影響到算法的效率，只有把數(shù)據(jù)結(jié)構(gòu)與算法有機(jī)地結(jié)合起來才能設(shè)計(jì)出高質(zhì)量的程序來。 緒論 算法的定義和描述 【例1.2】 對兩個正整數(shù)m和n，給出求它們最大公因子的算法。算法流程如圖所示。 緒論 算法的定義和描述 解: 算法設(shè)計(jì)如下： （1）求余數(shù)：以n除m，余數(shù)為r且0rn。 （2）判斷余數(shù)r是否等于零：如果r為零，則輸出n的當(dāng)前值（即為最大公因子），算法結(jié)束；否則執(zhí)行（3）。 （3）將n值傳給m，

17、將r值傳給n，轉(zhuǎn)（1）。 上述算法給出了三個計(jì)算步驟，而且每一步驟意義明確并切實(shí)可行。雖然出現(xiàn)了循環(huán)，但m和n都是已給定的有限整數(shù)，并且每次m除以n后得到的余數(shù)r即使不為零也總有rmin(m, n)，這就保證循環(huán)執(zhí)行有限次后必然終止，即滿足算法的所有特征，所以是一個正確的算法。1.3 算法與算法分析 算法的定義和描述 算法分析和復(fù)雜度計(jì)算 緒論 算法分析與復(fù)雜度計(jì)算 算法設(shè)計(jì)主要是考慮可解算法的設(shè)計(jì)，而算法分析則是研究和比較各種算法的性能與優(yōu)劣。算法的時(shí)間復(fù)雜度和空間復(fù)雜度是算法分析的兩個主要方面，其目的主要是考察算法的時(shí)間和空間效率，以求改進(jìn)算法或?qū)Σ煌乃惴ㄟM(jìn)行比較。 （1）時(shí)間復(fù)雜度：一

18、個程序的時(shí)間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需要的時(shí)間。 （2）空間復(fù)雜度：一個程序的空間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需的存儲量。 在復(fù)雜度計(jì)算中，實(shí)際上是把求解問題的關(guān)鍵操作，如加法、減法和比較運(yùn)算指定為基本操作，然后把算法執(zhí)行基本操作的次數(shù)作為算法的時(shí)間復(fù)雜度，而把算法執(zhí)行期間占用存儲單元的數(shù)量作為算法的空間復(fù)雜度。 緒論 算法分析與復(fù)雜度計(jì)算 在此涉及頻度的概念，即語句（指令）的頻度是指它在算法中被重復(fù)執(zhí)行的次數(shù)。一個算法的時(shí)間耗費(fèi)就是該算法中所有語句（指令）的頻度之和（記作T(n)），它是該算法所求解問題規(guī)模n的某個函數(shù)f(n)。當(dāng)問題規(guī)模n趨向無窮大時(shí)，T(n)的數(shù)量級稱為時(shí)間復(fù)

19、雜度，記作：T(n)O(f(n) 上述式子中“O”的文字含義是T(n)的數(shù)量級，其嚴(yán)格的數(shù)學(xué)定義是：若T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則存在正常數(shù)C和n0，使得當(dāng)nn0時(shí)都滿足0T(n)Cf(n) 例如，一個程序的實(shí)際執(zhí)行時(shí)間為T(n)=2.7n3+8.3n2+5.6，則T(n)=O(n3)。也即，當(dāng)n趨于無窮大時(shí)，n3前的2.7可以忽略，即該程序的時(shí)間復(fù)雜度的數(shù)量級是n3。 算法的時(shí)間復(fù)雜度采用這種數(shù)量級的形式表示后，將給分析算法的時(shí)間復(fù)雜度帶來很大的方便，即對一個算法，只需分析影響該算法時(shí)間復(fù)雜度的主要部分即可，而無需對該算法的每一個語句都進(jìn)行詳細(xì)的分析。 緒論 算法分析

20、與復(fù)雜度計(jì)算 若一個算法中的兩個部分的時(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)換為程序后，每條語句執(zhí)行一次所需的時(shí)間取決于機(jī)器的指令性能、速度以及編譯所生成的代碼質(zhì)量，這是難以確定的。因此，我們假設(shè)每條語句執(zhí)行一次所需的時(shí)間均是單位時(shí)間，則程序計(jì)算的時(shí)間復(fù)雜度法則如下。 （1）執(zhí)行一條讀寫語句或賦值語句所用的時(shí)間為O(1)。 （2）依次執(zhí)行一系列語句所用的時(shí)間采用求和準(zhǔn)則。 （3）條件語句if的耗時(shí)

21、主要是當(dāng)條件為真時(shí)執(zhí)行語句體所用的時(shí)間，而檢測條件是否為真還需耗費(fèi)O(1)。 （4）對while、dowhile和for這樣的循環(huán)語句，其運(yùn)行時(shí)間為每次執(zhí)行循環(huán)體及檢測是否繼續(xù)循環(huán)的時(shí)間，故常用乘法準(zhǔn)則。 緒論 算法分析與復(fù)雜度計(jì)算 【例1.3】 試求下面程序段的時(shí)間復(fù)雜度。for(i=0;in;i+) for(j=0;jn;j+) Cij=0; for(k=0;kn;k+) Cij=Cij+Aik*Bkj; 解： 給程序中的語句進(jìn)行編號，并在其右側(cè)列出該語句的頻度：(1) for(i=0;in;i+) n+1(2) for(j=0;jn;j+) n(n+1) (3) Cij=0 n2(4)

22、for(k=0;kn;k+) n2(n+1)(5) Cij=Cij+Aik*Bkj; n3 緒論 算法分析與復(fù)雜度計(jì)算 語句（1）的i值由0遞增到n，并且測試到i等于n時(shí)（即條件“idatai均表示順序表中第i個元素的值，而List.len或L-len均表示順序表的表長，兩種表示如圖所示。 線性表的順序存儲順序表 2.2 線性表的順序存儲結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn) 線性表的順序存儲 順序表基本運(yùn)算的實(shí)現(xiàn) 線性表1. 順序表的初始化順序表的初始化就是構(gòu)造一個空表。將L設(shè)為指針變量，然后動態(tài)分配順序表的存儲空間，并設(shè)表長len=0。算法如下：SeqList *Init_SeqList() SeqList *L

23、; L=(SeqList*)malloc(sizeof(SeqList); L-len=0; return L; 順序表算法實(shí)現(xiàn) 線性表2. 建立順序表依次輸入順序表的長度n和n個順序表元素即可建立順序表。算法如下：void CreatList(SeqList *L) int i, n; printf(Input length of List: ); scanf(%d, &n); printf(Input elements of List: n); for(i=1;idatai); (*L)-len=n; 順序表算法實(shí)現(xiàn) 線性表3.插入運(yùn)算：在表的第i個位置插入一個值為x的新元素，使得原表長為

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

25、eqList(SeqList *L, int i, datatype x) int j; if(L-len=MAXSIZE-1) /表滿 printf(The List is full!n); else if(iL-len+1) /插入位置非法 printf(The position is invalid !n); else for(j=L-len;j=i;j-) /將anai順序后移一個元素位置 L-dataj+1=L-dataj; L-datai=x; /插入x到第i個位置 L-len+; /表長增1 順序表算法實(shí)現(xiàn) 線性表4.刪除運(yùn)算：將順序表中第i個元素從表中除去，刪除后使原表長為n的

26、順序表成為表長為n-1的順序表。刪除ai的過程如下：（1）按ai+1到an的順序依次將ai+1an前移一個元素位置，移動的同時(shí)即完成了對ai的刪除。（2）修改len值，使其仍指向表的最后一個元素。刪除時(shí)可能會出現(xiàn)下列非法情況：（1）當(dāng)L-len=0時(shí)，順序表為空而無法刪除。（2）當(dāng)i1或iL-Len時(shí)，i位置上沒有元素，即刪除位置非法。 順序表算法實(shí)現(xiàn) 線性表刪除算法如下：void Delete_SeqList(SeqList *L, datatype i) int j; if(L-len=0) /表為空 printf(The List is empt !n); else if(iL-len)

27、 /刪除位置非法 printf(The position is invalid !n); else for(j=i+1;jlen;j+) /將ai+1an順序前移一個位置實(shí)現(xiàn)對ai的刪除 L-dataj-1=L-dataj; L-len-; /表長減1 順序表算法實(shí)現(xiàn) 線性表5. 查找運(yùn)算：在順序表中查找與給定值x相等的元素。完成該運(yùn)算最簡單的方法是：從第一個元素a1起依次和x比較，直至找到一個與x相等的元素時(shí)則返回該元素的存儲位置（即下標(biāo)）；如果查遍整個表都沒找到與x相等的元素則返回0值。算法如下：int Location_SeqList(SeqList *L, datatype x) in

28、t i=1; /從第一個元素開始查找 while(ilen&L-datai!=x) /順序表未查完且當(dāng)前元素不是要找的元素 i+; if(L-datai=x) return i; /找到則返回其位置值 else return 0; /未找到則返回0值 順序表算法實(shí)現(xiàn) 線性表查找算法的主要運(yùn)算是比較。顯然，比較的次數(shù)與x在表中的位置有關(guān)，當(dāng)ai=x時(shí)，對算法需要比較i次，在等概率的情況下，查找成功的平均比較次數(shù)為因此，查找算法的時(shí)間復(fù)雜度為O(n)。 順序表算法實(shí)現(xiàn) 2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及運(yùn)算實(shí)現(xiàn) 順序表表示的線性表特點(diǎn)是用物理位置上的鄰接關(guān)系來表示元素之間的邏輯關(guān)系，使我們可以隨機(jī)存取

29、表中的任意一個元素，但也產(chǎn)生了在插入和刪除操作中移動大量元素的問題。 鏈?zhǔn)酱鎯捎眠B續(xù)或不連續(xù)的存儲單元來存儲線性表中的元素，元素之間的邏輯關(guān)系無法用物理位置上的鄰接關(guān)系來表示，因此，需要用“指針”來指示元素之間的邏輯關(guān)系，即通過“指針”鏈接起元素之間的鄰接關(guān)系，而“指針”要占用額外存儲空間。鏈?zhǔn)酱鎯Ψ绞绞チ隧樞虮砜梢噪S機(jī)存取元素的功能,但卻換來了存儲空間操作的方便性：進(jìn)行插入和刪除操作時(shí)無需移動大量的元素。 本節(jié)將從四個方面介紹線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)。2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及運(yùn)算實(shí)現(xiàn) 單鏈表 單鏈表運(yùn)算實(shí)現(xiàn) 循環(huán)鏈表 單鏈表應(yīng)用示例 線性表 單鏈表 在每個元素中除了含有數(shù)據(jù)信

30、息外，還要有一個指針用來指向它的直接后繼元素，即通過指針建立起元素之間的線性關(guān)系，我們稱這種元素為結(jié)點(diǎn)。結(jié)點(diǎn)中存放數(shù)據(jù)信息的部分稱為數(shù)據(jù)域，存放指向后繼結(jié)點(diǎn)指針的部分稱為指針域線性表中的n個元素通過各自結(jié)點(diǎn)的指針域“鏈”在一起又被稱為鏈表。每個結(jié)點(diǎn)中只有一個指向后繼結(jié)點(diǎn)的指針，故稱其為單鏈表。鏈表是由一個個結(jié)點(diǎn)構(gòu)成的，單鏈表結(jié)點(diǎn)的定義如下：typedef struct nodedatatype data; /data為結(jié)點(diǎn)的數(shù)據(jù)信息 struct node *next; /next為指向后繼結(jié)點(diǎn)的指針LNode; /單鏈表結(jié)點(diǎn)類型結(jié)點(diǎn)結(jié)構(gòu)如圖 線性表 單鏈表 線性表（a1, a2, a3, a

31、4, a5, a6）對應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)示意如下圖所示。將第一個結(jié)點(diǎn)的地址200放入到一個指針變量如H中，最后一個結(jié)點(diǎn)由于沒有后繼，其指針域必須置空（NULL）以表明鏈表到此結(jié)束。通過指針H就可以由第一個結(jié)點(diǎn)的地址開始“順藤摸瓜”地找到每一個結(jié)點(diǎn) 。 線性表 單鏈表 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)具有以下特點(diǎn)：（1）邏輯關(guān)系相鄰的元素在物理位置上可以不 相鄰。（2）表中的元素只能順序訪問而不能隨機(jī)訪問。（3）表的大小可以動態(tài)變化。（4）插入、刪除等操作只需修改指針（地址）而無需移動元素。 單鏈表關(guān)心的是結(jié)點(diǎn)之間的邏輯關(guān)系，而對每個結(jié)點(diǎn)的實(shí)際存儲地址并不感興趣，可以形象地畫為下圖所示的形式。 通常用“頭指針

32、”來標(biāo)識一個單鏈表，如單鏈表L、單鏈表H等均是指單鏈表中的第一個結(jié)點(diǎn)的地址存放在指針變量L或H中；當(dāng)頭指針為“NULL”時(shí)則表示單鏈表為空。 線性表 單鏈表 在線性表的鏈?zhǔn)酱鎯χ?，為了便于插入和刪除算法的實(shí)現(xiàn)且使單鏈表的操作在各種情況下統(tǒng)一，在單鏈表的第一個結(jié)點(diǎn)之前添加了一個頭結(jié)點(diǎn)，該頭結(jié)點(diǎn)不存儲任何數(shù)據(jù)信息，只是用其指針域中的指針指向單鏈表的第一個數(shù)據(jù)結(jié)點(diǎn)，即通過頭指針指向的頭結(jié)點(diǎn)，可以訪問到單鏈表中的所有數(shù)據(jù)結(jié)點(diǎn)。 添加頭結(jié)點(diǎn)后，無論單鏈表中的結(jié)點(diǎn)如何變化，比如插入新結(jié)點(diǎn)、刪除單鏈表中任意一個數(shù)據(jù)結(jié)點(diǎn)，頭結(jié)點(diǎn)將始終不變，這使得單鏈表的運(yùn)算變得更加簡單。2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)

33、 單鏈表 單鏈表運(yùn)算實(shí)現(xiàn) 循環(huán)鏈表 單鏈表應(yīng)用示例 線性表 單鏈表運(yùn)算實(shí)現(xiàn) 1.建立單鏈表1）在鏈表頭部插入結(jié)點(diǎn)的方式建立單鏈表 單鏈表的建立是從空表開始的，每讀入一個數(shù)據(jù)則申請一個結(jié)點(diǎn)，然后插在頭結(jié)點(diǎn)之后，存儲線性表（A, B, C, D）的單鏈表建立過程如下圖所示。因?yàn)槭窃趩捂湵眍^部插入，故讀入數(shù)據(jù)的順序與線性表中元素的順序正好相反。 線性表 單鏈表運(yùn)算實(shí)現(xiàn) 算法實(shí)現(xiàn)如下：void CreateLinkList(LNode *head) /將主調(diào)函數(shù)中指向待生成單鏈表的指針地址（如&p）傳給*head char x; LNode *p; *head=(LNode *)malloc(size

34、of(LNode); /在主調(diào)函數(shù)空間生成鏈表頭結(jié)點(diǎn) (*head)-next=NULL; /*head為鏈表頭指針 printf(Input any char string: 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); /申請一個結(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

35、, &x); /繼續(xù)生成下一個新結(jié)點(diǎn) 線性表 單鏈表運(yùn)算實(shí)現(xiàn) 2）在鏈表的尾部插入結(jié)點(diǎn)的方式建立單鏈表 在頭部插入結(jié)點(diǎn)的方式生成單鏈表較為簡單，但生成結(jié)點(diǎn)的順序與線性表中的元素順序正好相反。若希望兩者的次序一致，則可采用尾插法來生成單鏈表。由于每次都是將新結(jié)點(diǎn)插入鏈表的尾部，所以必須再增加一個指針q來始終指向單鏈表的尾結(jié)點(diǎn)，以方便新結(jié)點(diǎn)的插入。在鏈尾插入結(jié)點(diǎn)生成單鏈表的過程示意如下圖所示。 線性表 單鏈表運(yùn)算實(shí)現(xiàn) 算法如下：LNode *CreateLinkList() LNode *head, *p, *q; char x; head=(LNode*)malloc(sizeof(LNode)

36、; /生成頭結(jié)點(diǎn) head-next=NULL; p=head; q=p; /指針q始終指向鏈尾結(jié)點(diǎn) printf(Input any char string: 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); return head; /返回單鏈表表頭指針 線性表 單鏈表運(yùn)算實(shí)現(xiàn) 2. 求表長算法如下：int Length_LinkList(LNode *head) LNode

37、 *p=head; /p指向單鏈表頭結(jié)點(diǎn) int i=0; /i為結(jié)點(diǎn)計(jì)數(shù)器 while(p-next!=NULL) p=p-next; i+; return i; /返回表長值i求表長算法的時(shí)間復(fù)雜度為O(n) 線性表 單鏈表運(yùn)算實(shí)現(xiàn) 3. 查找 1）按序號查找 從鏈表的第一個結(jié)點(diǎn)開始查找，若當(dāng)前結(jié)點(diǎn)是第i個結(jié)點(diǎn)，則返回指向該結(jié)點(diǎn)的指針值，否則繼續(xù)向后查找；如果整個表都無序號為i的結(jié)點(diǎn)（i大于鏈表中結(jié)的個數(shù)），則返回空指針值。 算法如下：LNode *Get_LinkList(LNode *head, int i) /在單鏈表head中查找第i個結(jié)點(diǎn) LNode *p=head; /由第一個

38、結(jié)點(diǎn)開始查找 int j=0; while(p!=NULL&jnext; j+; return p; /找到則返回指向i結(jié)點(diǎn)的指針值，找不到則p返回空值 線性表 單鏈表運(yùn)算實(shí)現(xiàn) 2）按值查找 從鏈表的第一個數(shù)據(jù)結(jié)點(diǎn)開始查找，若當(dāng)前結(jié)點(diǎn)值等于x則返回指向該結(jié)點(diǎn)的指針值，否則繼續(xù)向后查找；如果整個表都找不到值等于x的結(jié)點(diǎn)則返回空值。算法如下：LNode *Locate_LinkList(LNode *head, char x) /在單鏈表中查找結(jié)點(diǎn)值為x的結(jié)點(diǎn) LNode *p=head-next; /由第一個數(shù)據(jù)結(jié)點(diǎn)開始查找 while(p!=NULL&p-data!=x) /當(dāng)未查到鏈尾且當(dāng)前

39、結(jié)點(diǎn)不等于x時(shí)繼續(xù)查找 p=p-next; return p; /找到則返回指向值為x的結(jié)點(diǎn)的指針值，找不到則p返回空值查找算法的時(shí)間復(fù)雜度均為O(n)。 線性表 單鏈表運(yùn)算實(shí)現(xiàn) 4. 插入 鏈表中的各結(jié)點(diǎn)是通過指針鏈接起來的，因而可以通過改變鏈表結(jié)點(diǎn)中指針的指向來實(shí)現(xiàn)鏈表結(jié)點(diǎn)的插入與刪除。數(shù)組進(jìn)行插入或刪除操作時(shí)需要移動大量的數(shù)組元素，但是鏈表的插入或刪除操作由于僅需修改有關(guān)指針的指向而變得非常容易。 在鏈表結(jié)點(diǎn)*p之后插入鏈表結(jié)點(diǎn)*q的示意如圖所示。插入操作如下： q-next=p-next; p-next=q; 線性表 單鏈表運(yùn)算實(shí)現(xiàn) 在涉及改變指針值的操作中一定要注意指針值的改變次序，

40、否則容易出錯。假如上面插入操作的順序改為 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（即語句“q-next=p-next;”），以防止鏈表的斷開，然后再使結(jié)點(diǎn)*p的指針p-next改為指向結(jié)點(diǎn)*q（即語句“p-next=q;”）。 線性

41、表 單鏈表運(yùn)算實(shí)現(xiàn) 算法如下：void Insert_LinkList(LNode *head, int i, char x) /在單鏈表head的第i個位置上插入值為x的元素 LNode *p, *q; p=Get_LinkList(head, i-1);/查找第i-1個結(jié)點(diǎn)*/ if(p=NULL) printf(Error ! n); /第i-1個位置不存在而無法插入 else q=(LNode *)malloc(sizeof(LNode);/申請結(jié)點(diǎn)空間 q-data=x; q-next=p-next; /完成插入操作 p-next=q; /完成插入操作 該算法的時(shí)間花費(fèi)在尋找第i-1

42、個結(jié)點(diǎn)上，故算法時(shí)間復(fù)雜度為O(n)。 線性表 單鏈表的運(yùn)算實(shí)現(xiàn) 5. 刪除 要刪除一個鏈表結(jié)點(diǎn)必須知道它的前驅(qū)鏈表結(jié)點(diǎn)，只有使指針變量p 指向這個前驅(qū)鏈表結(jié)點(diǎn)時(shí)，才可以通過下面的語句實(shí)現(xiàn)所要刪除的操作：p-next= p-next-next;即通過改變鏈表結(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)前都要先找到這個待刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，這就需要借助一個指針變量（如p）來定位于這個前驅(qū)結(jié)點(diǎn)，然后才能進(jìn)行刪除操作，如圖所示。 線性表 單鏈表的運(yùn)算

43、實(shí)現(xiàn)算法如下：void Del_LinkList(LNode *head , int i) /刪除單鏈表head上的第i個數(shù)據(jù)結(jié)點(diǎn) LNode *p, *q; p=Get_LinkList(head, i-1); /查找第i-1個結(jié)點(diǎn) if(p=NULL) printf(第i-1個結(jié)點(diǎn)不存在!n ); /待刪結(jié)點(diǎn)的前一個結(jié)點(diǎn)不存在，無待刪結(jié)點(diǎn) else if(p-next=NULL) printf(第i個結(jié)點(diǎn)不存在!n);/待刪結(jié)點(diǎn)不存在 else q=p-next;/q指向第i個結(jié)點(diǎn) p-next=q-next;/從鏈表中刪除第i個結(jié)點(diǎn) free(q);/系統(tǒng)回收第i個結(jié)點(diǎn)的存儲空間 刪除算

44、法的時(shí)間復(fù)雜度為O(n)。2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及運(yùn)算實(shí)現(xiàn) 單鏈表 單鏈表運(yùn)算實(shí)現(xiàn) 循環(huán)鏈表 單鏈表應(yīng)用示例 線性表 循環(huán)鏈表 循環(huán)鏈表，將單鏈表中最后一個結(jié)點(diǎn)的指針值由空改為指向單鏈表的頭結(jié)點(diǎn)，整個鏈表形成一個環(huán)。這樣，從鏈表中的任一結(jié)點(diǎn)位置出發(fā)都可以找到鏈表的其他結(jié)點(diǎn)。在循環(huán)鏈表上的操作基本上與單鏈表相同，只是將原來判斷指針是否為NULL改為判斷是否為頭指針，再無其他變化。帶頭結(jié)點(diǎn)的循環(huán)鏈表示意圖為： 線性表 循環(huán)鏈表 在帶頭結(jié)點(diǎn)的循環(huán)鏈表中查找值等于x的結(jié)點(diǎn)，其實(shí)現(xiàn)算法如下：LNode *Locate_CycLink(LNode *head, datatype x)LNode *p

45、=head-next; /由第一個數(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) return p; /找到值等于x的結(jié)點(diǎn)*p，返回其指針值p else return NULL; /當(dāng)p又查到頭結(jié)點(diǎn)時(shí)則無等于x值的結(jié)點(diǎn)，故返回NULL值 由于鏈表的操作通常是在表頭或表尾進(jìn)行，故也可改變循環(huán)鏈表的標(biāo)識方法，即不用頭指針而用一個指向尾結(jié)點(diǎn)的指針R來標(biāo)識循環(huán)鏈表。這種標(biāo)識的好處是可以直接找到鏈尾結(jié)點(diǎn)，而找到頭結(jié)點(diǎn)也非常容易，R-next即為指向頭結(jié)點(diǎn)的指針。2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)

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

47、H-next; /p指向剩余結(jié)點(diǎn)鏈表的第一個數(shù)據(jù)結(jié)點(diǎn) H-next=NULL; /新鏈表H初始為空 線性表 單鏈表應(yīng)用示例 while(p!=NULL) q=p; /從剩余結(jié)點(diǎn)鏈表中取出第一個結(jié)點(diǎn) p=p-next; /p繼續(xù)指向剩余結(jié)點(diǎn)鏈表新的第一個數(shù)據(jù)結(jié)點(diǎn) q-next=H-next; /將取出的結(jié)點(diǎn)*q插入新鏈表H的鏈?zhǔn)?H-next=q; 該算法只對鏈表順序掃描一遍即實(shí)現(xiàn)鏈表的逆置，故其時(shí)間復(fù)雜度為O(n)。 線性表 單鏈表應(yīng)用示例例2. 對兩個元素遞增有序的單鏈表A和B，編寫算法將A、B合并成一個按元素遞減有序（允許有相同值）的單鏈表C，要求算法使用A、B中的原有結(jié)點(diǎn)，不允許增加新結(jié)

48、點(diǎn)。解：由例1可知，將遞增有序改為遞減有序只能采用頭插法，如果仍保持遞增有序則應(yīng)采用尾插法，因此本題采用頭插法實(shí)現(xiàn)。算法如下： void Merge(LNode *A, LNode *B, LNode *C) /將增序鏈表A、B合并成降序鏈表*C LNode *p, *q, *s; p=A-next; /p始終指向鏈表A的第一個未比較的數(shù)據(jù)結(jié)點(diǎn) q=B-next; /q始終指向鏈表B的第一個未比較的數(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é)

49、點(diǎn)中值小者賦給*s 線性表 單鏈表應(yīng)用示例 if(p-datadata) 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指向鏈表B p=q; while(p!=NULL) /將*p所指鏈表中的剩余結(jié)點(diǎn)依次摘下插入鏈表*C的鏈?zhǔn)?s=p；p=p-next; s-next=(*C)-next; (*C)-next=s; 對m個結(jié)點(diǎn)的單鏈表A和n個結(jié)點(diǎn)的單鏈表B，該算法的時(shí)間復(fù)雜度為O(m+n)。 線性表 單鏈

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

51、 *q; int i; p=(LNode*)malloc(sizeof(LNode); q=p; 線性表 單鏈表應(yīng)用示例for(i=1;idata=k; k=k%n+1; q-next=(LNode*)malloc(sizeof(LNode); q=q-next; q-data=k; q-next=p; /鏈接成循環(huán)單鏈表，此時(shí)p指向編號為k的結(jié)點(diǎn) while(p-next!=p) /當(dāng)循環(huán)單鏈表中的結(jié)點(diǎn)個數(shù)不為1時(shí) for(i=1;inext; /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); /輸

52、出出圈人的編號 free(p); /釋放被刪結(jié)點(diǎn)的空間 p=q-next; /p指向新的開始報(bào)數(shù)結(jié)點(diǎn) printf(%4d, p-data); /輸出最后出圈人的編號03:05:54第3章棧和隊(duì)列03:05:54 第3章 棧和隊(duì)列 棧和隊(duì)列都是操作受限的線性表?xiàng)＃合冗M(jìn)后出隊(duì)列：先進(jìn)先出03:05:54本章主要內(nèi)容:棧的定義及基本運(yùn)算棧的存儲結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)隊(duì)列的定義及基本運(yùn)算隊(duì)列的存儲結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)第3章 棧和隊(duì)列03:05:543.1 棧的定義及基本運(yùn)算 棧的定義 棧的基本操作03:05:54 棧的定義棧是限定僅在一端進(jìn)行操作的線性表?xiàng)ｍ敚╰op）：允許進(jìn)行插入和刪除元素操作的一端棧底（bot

53、tom）：固定不變的另一端空棧：不含元素的棧滿棧：存儲空間被用完的棧先進(jìn)后出03:05:543.1 棧的定義及基本運(yùn)算 棧的定義 棧的基本操作03:05:54 棧的基本操作棧初始化Init_Stack(s)：生成一個空棧s判?？誆mpty_Stack(s)：若棧s為空則返回1，否則返回0入棧Push_Stack(s, x)：在棧s的頂部插入一個新元素x，使x成為新的棧頂元素，棧變化出棧Pop_Stack(s, x)：在棧s非空的情況下，操作結(jié)果是將棧s的頂部元素從棧中刪除，并由x返回棧頂元素值，即棧中少了一個元素，棧變化讀棧頂元素Top_Stack(s, x)：在棧s非空的情況下，操作結(jié)果是將

54、棧s的頂部元素讀到x中，棧不變化03:05:54本章主要內(nèi)容:棧的定義及基本運(yùn)算棧的存儲結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)隊(duì)列的定義及基本運(yùn)算隊(duì)列的存儲結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)第3章 棧和隊(duì)列03:05:543.2 棧的存儲結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn) 順序棧 兩個順序棧共享連續(xù)空間 鏈棧03:05:54 順序棧順序棧：棧的順序存儲結(jié)構(gòu)利用一組地址連續(xù)的存儲單元來依次存放由棧底到棧頂?shù)乃性?，附加一個top指針來指示棧頂元素在順序棧中的位置typedef struct datatype dataMAXSIZE; /棧中元素存儲空間 int top; /棧頂指針SeqStack;順序棧的類型定義03:05:54 順序棧順序棧操作示意圖0

55、3:05:54 順序棧順序棧基本操作：初始化棧void Init_SeqStack(SeqStack *s) *s=(SeqStack*)malloc(sizeof(SeqStack); /在主調(diào)函數(shù)中申請?？臻g (*s)-top=-1; /置棧空標(biāo)志03:05:54 順序棧順序?；静僮鳎号袛鄺Ｊ欠駷榭読nt Empty_SeqStack(SeqStack *s) if(s-top=-1) /棧為空時(shí)返回1值 return 1; else return 0; /棧不空時(shí)返回0值03:05:54 順序棧順序?；静僮鳎喝霔oid Push_SeqStack(SeqStack *s, data

56、type x) if(s-top=MAXSIZE-1) printf(Stack is full!n);/棧已滿 else s-top+; /先使棧頂指針top增1 s-datas-top=x; /再將元素x壓入棧*s中 03:05:54 順序棧順序?；静僮鳎撼鰲oid Pop_SeqStack(SeqStack *s, datatype *x) /將棧*s中的棧頂元素出棧并通過參數(shù)x返回給主調(diào)函數(shù) if(s-top=-1) printf(Stack is empty!n);/棧為空 else *x=s-datas-top; /棧頂元素出棧 s-top-; /棧頂指針top減1 03:05

57、:54 順序棧順序?；静僮鳎喝ｍ斣豽oid Top_SeqStack(SeqStack *s, datatype *x) if(s-top=-1) printf(Stack is empty!n);/棧為空 else *x=s-datas-top; /取棧頂元素值賦給*x03:05:543.2 棧的存儲結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn) 順序棧 兩個順序棧共享連續(xù)空間 鏈棧03:05:54兩個順序棧共享連續(xù)空間利用棧底位置相對不變這一特點(diǎn)，兩個順序?？梢怨蚕硪粋€一維數(shù)據(jù)空間來互補(bǔ)余缺。實(shí)現(xiàn)方法是將兩個棧的棧底分設(shè)在一維數(shù)據(jù)空間的兩端，讓其各自的棧頂由兩端向中間延伸03:05:54兩個順序棧共享連續(xù)空間多個棧

58、共享一維數(shù)據(jù)空間的問題就比較復(fù)雜，因?yàn)橐粋€存儲空間只有兩端是固定的，需要：設(shè)置棧頂指針和棧底指針。這種情況下，當(dāng)某個棧發(fā)生上溢時(shí)，如果整個一維數(shù)據(jù)空間未被占滿，則必須移動某些（或某個）棧來騰出空間解決所發(fā)生的上溢03:05:543.2 棧的存儲結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn) 順序棧 兩個順序棧共享連續(xù)空間 鏈棧03:05:54鏈棧鏈棧是指以鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的棧鏈棧是動態(tài)分配元素存儲空間的，所以操作時(shí)無需考慮順序棧容易出現(xiàn)的上溢問題，這樣，多個棧的共享問題也就迎刃而解了typedef struct node datatype data; struct node *next;StackNode;鏈棧的定義：03:

59、05:54鏈棧鏈棧的基本操作：初始化鏈棧void Init_LinkStack(StackNode *s) *s=NULL; /置棧頂指針*s為空03:05:54鏈棧鏈棧的基本操作：判斷鏈棧是否為空int Empty_LinkStack(StackNode *s) if(s=NULL) return 1; /棧為空時(shí)返回1值 else return 0; /棧不空時(shí)返回0值03:05:54鏈棧鏈棧的基本操作：入棧void Push_LinkStack(StackNode *top, datatype x) StackNode *p; p=(StackNode *)malloc(sizeof(S

60、tackNode); /申請一個結(jié)點(diǎn)空間 p-data=x; /讀入結(jié)點(diǎn)數(shù)據(jù) p-next=*top; /該結(jié)點(diǎn)作為棧頂元素鏈入鏈棧 *top=p; /棧頂指針指向這個新棧頂元素03:05:54鏈棧鏈棧的基本操作：出棧void Pop_LinkStack(StackNode *top, datatype *x) StackNode *p; if(*top=NULL) /棧頂指針為空時(shí) printf(Stack is empty!n); else /棧頂指針為空時(shí) *x=(*top)-data; /棧頂元素的數(shù)據(jù)賦給*x p=*top; /指針p指向棧頂元素 *top=(*top)-next;