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

22:10:57第1章緒論

第一章

緒論

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

緒論

用計算機解決實際問題的軟件開發(fā)一般分為下面幾個步驟：

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

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

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

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

（4）測試階段：測試、修改直到得到問題的解答。

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

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

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

緒論數(shù)據(jù)結(jié)構(gòu)的核心內(nèi)容是分解與抽象。通過對問題的抽象，舍棄數(shù)據(jù)元素（含義見后）的具體內(nèi)容，就得到邏輯結(jié)構(gòu)；類似地，通過分解將處理要求劃分成各種功能，再通過抽象舍棄實現(xiàn)的細節(jié)，就得到基本運算的定義。上述兩個方面的結(jié)合使人們將問題轉(zhuǎn)換為數(shù)據(jù)結(jié)構(gòu)，這是一個從具體（即具體問題）到抽象（即數(shù)據(jù)結(jié)構(gòu)）的過程。通過增加對實現(xiàn)細節(jié)的考慮，進一步得到存儲結(jié)構(gòu)和實現(xiàn)算法，從而完成設(shè)計任務(wù)，這是一個從抽象（即數(shù)據(jù)結(jié)構(gòu)）到具體（即具體實現(xiàn)）的過程。熟練掌握這兩個過程是數(shù)據(jù)結(jié)構(gòu)課程在專業(yè)技能培養(yǎng)方面的基本目標。在系統(tǒng)地學習數(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ù)學符號以及其他規(guī)定的符號對現(xiàn)實世界的事物及其活動所做的抽象描述。簡言之，數(shù)據(jù)是信息的載體，是對客觀事物的符號化表示。從計算機的角度看，數(shù)據(jù)是計算機程序?qū)λ枋隹陀^事物進行加工處理的一種表示，凡是能夠被計算機識別、存取和加工處理的符號、字符、圖形、圖像、聲音、視頻信號等都可以稱為數(shù)據(jù)。我們?nèi)粘Ｉ婕暗臄?shù)據(jù)主要分為兩類：一類是數(shù)值數(shù)據(jù)，包括整數(shù)、實數(shù)和復數(shù)等，它們主要用于工程和科學計算以及商業(yè)事務(wù)處理；另一類是非數(shù)值數(shù)據(jù)，主要包括字符和字符串以及文字、圖形、語音等，它們多用于控制、管理和數(shù)據(jù)處理等領(lǐng)域。

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

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

緒論

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

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

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

緒論表1.1構(gòu)成了全部學生信息的數(shù)據(jù)。表中的每一行即為記錄一個學生信息的數(shù)據(jù)元素，而該行中的每一項則為一個數(shù)據(jù)項。數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項實際上反映了數(shù)據(jù)組織的三個層次，數(shù)據(jù)可以由若干個數(shù)據(jù)元素構(gòu)成，而數(shù)據(jù)元素則又可以由若干數(shù)據(jù)項構(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)包含以下三個方面的內(nèi)容。（1）數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。（2）數(shù)據(jù)元素及其關(guān)系在計算機存儲器中的存儲方式，即數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）。（3）施加在數(shù)據(jù)上的操作，即數(shù)據(jù)的運算。

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

緒論

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

數(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ù)元素之間存在著“多對多”的關(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)實生活中的樓層編號就屬于線性結(jié)構(gòu)，而省、市、地區(qū)的劃分則屬于樹形結(jié)構(gòu)，城市交通圖則屬于圖結(jié)構(gòu)。

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

緒論關(guān)于邏輯結(jié)構(gòu)需要注意以下幾點:（1）邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式和內(nèi)容無關(guān)。例如，給表1.1中的每個學生增加一個數(shù)據(jù)項“學號”，就得到另一個數(shù)據(jù)，但由于所有的數(shù)據(jù)元素仍是“一個接一個排列”，故新數(shù)據(jù)的邏輯結(jié)構(gòu)與原來數(shù)據(jù)的邏輯結(jié)構(gòu)相同，仍是一個線性結(jié)構(gòu)。（2）邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對位置無關(guān)。例如，將表1.1中的學生按年齡由大到小的順序重新排列就得到另一個表格，但這個新表格中的所有數(shù)據(jù)元素“一個接一個排列”的性質(zhì)并沒有改變，其邏輯結(jié)構(gòu)與原表格相同，還是線性結(jié)構(gòu)。（3）邏輯結(jié)構(gòu)與所含數(shù)據(jù)元素的個數(shù)無關(guān)。例如，在表1.1中增加或刪除若干學生信息（數(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)在計算機中的實現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素的表示以及數(shù)據(jù)元素之間關(guān)系的表示。數(shù)據(jù)元素及數(shù)據(jù)元素之間的關(guān)系在計算機中可以有以下四種基本存儲結(jié)構(gòu)。（1）順序存儲結(jié)構(gòu)：借助于數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。通常順序存儲結(jié)構(gòu)是利用程序語言中的數(shù)組來描述。（2）鏈式存儲結(jié)構(gòu)：在數(shù)據(jù)元素上附加指針域，并借助指針來指示數(shù)據(jù)元素之間的邏輯關(guān)系。通常是利用程序語言中的指針類型來描述。（3）索引存儲結(jié)構(gòu)：在存儲所有數(shù)據(jù)元素信息的同時建立附加索引表。索引表中表項的一般形式是：（關(guān)鍵字，地址）；關(guān)鍵字是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，它唯一標識該數(shù)據(jù)元素；地址則是指向該數(shù)據(jù)元素的指針。由關(guān)鍵字可以立即通過地址找到該數(shù)據(jù)元素。（4）哈希（或散列）存儲結(jié)構(gòu)：此方法的基本思想是根據(jù)數(shù)據(jù)元素的關(guān)鍵字通過哈希（或散列）函數(shù)直接計算出該數(shù)據(jù)元素的存儲地址。

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

緒論

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

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

緒論

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

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

緒論

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

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

緒論

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

表1.2在順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)下的示意如圖所示：1.3

算法與算法分析

算法的定義和描述

算法分析和復雜度計算

緒論

算法的定義和描述

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

緒論

算法的定義和描述

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

緒論

算法的定義和描述

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

緒論

算法的定義和描述

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

算法與算法分析

算法的定義和描述

算法分析和復雜度計算

緒論

算法分析與復雜度計算

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

緒論

算法分析與復雜度計算

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

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

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

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

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

緒論

算法分析與復雜度計算

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

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

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

緒論

算法分析與復雜度計算

【例1.3】試求下面程序段的時間復雜度。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];}解：給程序中的語句進行編號，并在其右側(cè)列出該語句的頻度：(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 }

緒論

算法分析與復雜度計算

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

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

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

第二章

線性表

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

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

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

線性表的鏈式存儲結(jié)構(gòu)及運算實現(xiàn)

第二章

線性表

2.1

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

線性表的定義

線性表的基本操作

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

線性表的定義

線性表

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

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

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

線性表的定義

線性表

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

線性表的定義

2.1

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

線性表的定義

線性表的基本操作

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

線性表的基本操作

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

線性表的順序存儲

順序表基本運算的實現(xiàn)

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

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

線性表的順序存儲——順序表

線性表

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

線性表的順序存儲——順序表

線性表

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

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

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

線性表的順序存儲——順序表

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

線性表的順序存儲——順序表

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

線性表的順序存儲

順序表基本運算的實現(xiàn)

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

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

線性表2.建立順序表依次輸入順序表的長度n和n個順序表元素即可建立順序表。算法如下：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;}

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

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

順序表算法實現(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順序后移一個元素位置

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

L->len++; //表長增1}}}

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

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

順序表算法實現(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順序前移一個位置實現(xiàn)對ai的刪除

L->data[j-1]=L->data[j];L->len--; //表長減1}}

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

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

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

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

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

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

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

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

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

2.3線性表的鏈式存儲結(jié)構(gòu)及運算實現(xiàn)

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

單鏈表

單鏈表運算實現(xiàn)

循環(huán)鏈表

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

線性表

單鏈表

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

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

線性表

單鏈表

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

線性表

單鏈表

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

線性表

單鏈表

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

添加頭結(jié)點后，無論單鏈表中的結(jié)點如何變化，比如插入新結(jié)點、刪除單鏈表中任意一個數(shù)據(jù)結(jié)點，頭結(jié)點將始終不變，這使得單鏈表的運算變得更加簡單。2.3線性表的鏈式存儲結(jié)構(gòu)及運算實現(xiàn)

單鏈表

單鏈表運算實現(xiàn)

循環(huán)鏈表

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

線性表

單鏈表運算實現(xiàn)

1.建立單鏈表1）在鏈表頭部插入結(jié)點的方式建立單鏈表單鏈表的建立是從空表開始的，每讀入一個數(shù)據(jù)則申請一個結(jié)點，然后插在頭結(jié)點之后，存儲線性表（‘A’,‘B’,‘C’,‘D’）的單鏈表建立過程如下圖所示。因為是在單鏈表頭部插入，故讀入數(shù)據(jù)的順序與線性表中元素的順序正好相反。

線性表

單鏈表運算實現(xiàn)

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

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

printf("Inputanycharstring:\n");scanf("%c",&x);//結(jié)點的數(shù)據(jù)域為char型，讀入結(jié)點數(shù)據(jù)

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

{p=(LNode*)malloc(sizeof(LNode));//申請一個結(jié)點空間

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

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

}

線性表

單鏈表運算實現(xiàn)

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

線性表

單鏈表運算實現(xiàn)

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

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

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

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

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

線性表

單鏈表運算實現(xiàn)

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

inti=0; //i為結(jié)點計數(shù)器

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

線性表

單鏈表運算實現(xiàn)

3.查找

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

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

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

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

線性表

單鏈表運算實現(xiàn)

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

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

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

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

線性表

單鏈表運算實現(xiàn)

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

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

線性表

單鏈表運算實現(xiàn)

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

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

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

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

線性表

單鏈表運算實現(xiàn)

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

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

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

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

線性表

單鏈表的運算實現(xiàn)

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

線性表

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

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

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

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

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

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

free(q); //系統(tǒng)回收第i個結(jié)點的存儲空間

}}刪除算法的時間復雜度為O(n)。2.3線性表的鏈式存儲結(jié)構(gòu)及運算實現(xiàn)

單鏈表

單鏈表運算實現(xiàn)

循環(huán)鏈表

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

線性表

循環(huán)鏈表

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

線性表

循環(huán)鏈表

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

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

由于鏈表的操作通常是在表頭或表尾進行，故也可改變循環(huán)鏈表的標識方法，即不用頭指針而用一個指向尾結(jié)點的指針R來標識循環(huán)鏈表。這種標識的好處是可以直接找到鏈尾結(jié)點，而找到頭結(jié)點也非常容易，R->next即為指向頭結(jié)點的指針。2.3線性表的鏈式存儲結(jié)構(gòu)及運算實現(xiàn)

單鏈表

單鏈表運算實現(xiàn)

循環(huán)鏈表

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

線性表

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

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

線性表

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

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

q->next=H->next; //將取出的結(jié)點*q插入新鏈表H的鏈首

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

線性表

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

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

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

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

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

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

線性表

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

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

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

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

線性表

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

線性表

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

//從編號k開始建立一個單鏈表

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

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

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

q->next=p->next; //刪除報數(shù)為m的結(jié)點

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

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

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

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

第3章棧和隊列棧和隊列都是操作受限的線性表棧：先進后出隊列：先進先出22:10:57本章主要內(nèi)容:棧的定義及基本運算棧的存儲結(jié)構(gòu)和運算實現(xiàn)隊列的定義及基本運算隊列的存儲結(jié)構(gòu)和運算實現(xiàn)

第3章棧和隊列22:10:573.1

棧的定義及基本運算

棧的定義

棧的基本操作22:10:57

棧的定義棧是限定僅在一端進行操作的線性表棧頂（top）：允許進行插入和刪除元素操作的一端棧底（bottom）：固定不變的另一端空棧：不含元素的棧滿棧：存儲空間被用完的棧先進后出22:10:573.1

棧的定義及基本運算

棧的定義

棧的基本操作22:10:57

棧的基本操作棧初始化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é)果是將棧s的頂部元素讀到x中，棧不變化22:10:57本章主要內(nèi)容:棧的定義及基本運算棧的存儲結(jié)構(gòu)和運算實現(xiàn)隊列的定義及基本運算隊列的存儲結(jié)構(gòu)和運算實現(xiàn)

第3章棧和隊列22:10:573.2棧的存儲結(jié)構(gòu)和運算實現(xiàn)

順序棧

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

鏈棧22:10:57

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

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

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

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

(*s)->top=-1;//置棧空標志}22:10:57

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

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

順序棧順序棧基本操作：入棧voidPush_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中的棧頂元素出棧并通過參數(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

順序棧順序棧基本操作：取棧頂元素voidTop_SeqStack(SeqStack*s,datatype*x){if(s->top==-1)printf("Stackisempty!\n"); //棧為空

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

順序棧

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

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

順序棧

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

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