22:10:57第1章緒論

第一章

緒論

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

邏輯結構與存儲結構算法與算法分析

第一章

緒論

1.1

數據結構的概念

數據結構的概念

數據結構

數據與數據元素

緒論

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

數據結構的概念

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

（2）設計階段：設計出解決數學模型的算法。

（3）編程階段：用適當的編程語言編寫出可執行的程序。

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

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

數據結構的概念

方面層次數據表示數據處理抽象邏輯結構基本運算實現存儲結構算法評價不同數據結構的比較與算法分析

緒論數據結構的核心內容是分解與抽象。通過對問題的抽象，舍棄數據元素（含義見后）的具體內容，就得到邏輯結構；類似地，通過分解將處理要求劃分成各種功能，再通過抽象舍棄實現的細節，就得到基本運算的定義。上述兩個方面的結合使人們將問題轉換為數據結構，這是一個從具體（即具體問題）到抽象（即數據結構）的過程。通過增加對實現細節的考慮，進一步得到存儲結構和實現算法，從而完成設計任務，這是一個從抽象（即數據結構）到具體（即具體實現）的過程。熟練掌握這兩個過程是數據結構課程在專業技能培養方面的基本目標。在系統地學習數據結構知識之前，先對一些基本概念和術語予以說明。

數據結構的概念

1.1

數據結構的概念

數據結構的概念

數據結構

數據與數據元素

緒論

數據是人們利用文字符號、數學符號以及其他規定的符號對現實世界的事物及其活動所做的抽象描述。簡言之，數據是信息的載體，是對客觀事物的符號化表示。從計算機的角度看，數據是計算機程序對所描述客觀事物進行加工處理的一種表示，凡是能夠被計算機識別、存取和加工處理的符號、字符、圖形、圖像、聲音、視頻信號等都可以稱為數據。我們日常涉及的數據主要分為兩類：一類是數值數據，包括整數、實數和復數等，它們主要用于工程和科學計算以及商業事務處理；另一類是非數值數據，主要包括字符和字符串以及文字、圖形、語音等，它們多用于控制、管理和數據處理等領域。

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

數據與數據元素

緒論

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

數據與數據元素

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

緒論表1.1構成了全部學生信息的數據。表中的每一行即為記錄一個學生信息的數據元素，而該行中的每一項則為一個數據項。數據、數據元素和數據項實際上反映了數據組織的三個層次，數據可以由若干個數據元素構成，而數據元素則又可以由若干數據項構成。

數據與數據元素

1.1

數據結構的概念

數據結構的概念

數據結構

數據與數據元素

緒論數據結構是指數據以及數據之間的相互關系，即數據的組織形式。它可以看作是相互之間存在著某種特定關系的數據元素集合。因此，可以把數據結構看成是帶結構的數據元素集合。數據結構包含以下三個方面的內容。（1）數據元素之間的邏輯關系，即數據的邏輯結構。（2）數據元素及其關系在計算機存儲器中的存儲方式，即數據的存儲結構（物理結構）。（3）施加在數據上的操作，即數據的運算。

數據結構

緒論

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

數據結構1.2

邏輯結構與存儲結構

邏輯結構

存儲結構

緒論數據的邏輯結構是對數據元素之間邏輯關系的描述。根據數據元素之間關系的不同特性，可以劃分為以下四種基本邏輯結構。（1）集合結構：數據元素之間除了“屬于同一集合”的聯系之外，沒有其他關系。（2）線性結構：數據元素之間存在著“一對一”的關系。（3）樹形結構：數據元素之間存在著“一對多”的關系。（4）圖結構（或稱網狀結構）：數據元素之間存在著“多對多”的關系。

邏輯結構

緒論

由于集合結構的簡單性和松散性，所以通常只討論其他三種邏輯結構。數據的邏輯結構可以分為線性結構和非線性結構兩類。若數據元素之間的邏輯關系可以用一個線性序列簡單地表示出來，則稱為線性結構，否則稱為非線性結構。樹形結構和圖結構就屬于非線性結構。現實生活中的樓層編號就屬于線性結構，而省、市、地區的劃分則屬于樹形結構，城市交通圖則屬于圖結構。

邏輯結構

緒論關于邏輯結構需要注意以下幾點:（1）邏輯結構與數據元素本身的形式和內容無關。例如，給表1.1中的每個學生增加一個數據項“學號”，就得到另一個數據，但由于所有的數據元素仍是“一個接一個排列”，故新數據的邏輯結構與原來數據的邏輯結構相同，仍是一個線性結構。（2）邏輯結構與數據元素的相對位置無關。例如，將表1.1中的學生按年齡由大到小的順序重新排列就得到另一個表格，但這個新表格中的所有數據元素“一個接一個排列”的性質并沒有改變，其邏輯結構與原表格相同，還是線性結構。（3）邏輯結構與所含數據元素的個數無關。例如，在表1.1中增加或刪除若干學生信息（數據元素），所得到的表格仍為線性結構。

邏輯結構1.2

邏輯結構與存儲結構

邏輯結構

存儲結構

緒論

數據的存儲結構是數據結構在計算機中的實現方法，包括數據結構中數據元素的表示以及數據元素之間關系的表示。數據元素及數據元素之間的關系在計算機中可以有以下四種基本存儲結構。（1）順序存儲結構：借助于數據元素在存儲器中的相對位置來表示數據元素之間的邏輯關系。通常順序存儲結構是利用程序語言中的數組來描述。（2）鏈式存儲結構：在數據元素上附加指針域，并借助指針來指示數據元素之間的邏輯關系。通常是利用程序語言中的指針類型來描述。（3）索引存儲結構：在存儲所有數據元素信息的同時建立附加索引表。索引表中表項的一般形式是：（關鍵字，地址）；關鍵字是數據元素中某個數據項的值，它唯一標識該數據元素；地址則是指向該數據元素的指針。由關鍵字可以立即通過地址找到該數據元素。（4）哈希（或散列）存儲結構：此方法的基本思想是根據數據元素的關鍵字通過哈希（或散列）函數直接計算出該數據元素的存儲地址。

存儲結構

緒論

存儲結構

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

緒論

存儲結構

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

緒論

存儲結構

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

緒論

存儲結構

表1.2在順序存儲結構和鏈式存儲結構下的示意如圖所示：1.3

算法與算法分析

算法的定義和描述

算法分析和復雜度計算

緒論

算法的定義和描述

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

緒論

算法的定義和描述

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

緒論

算法的定義和描述

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

緒論

算法的定義和描述

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

算法與算法分析

算法的定義和描述

算法分析和復雜度計算

緒論

算法分析與復雜度計算

算法設計主要是考慮可解算法的設計，而算法分析則是研究和比較各種算法的性能與優劣。算法的時間復雜度和空間復雜度是算法分析的兩個主要方面，其目的主要是考察算法的時間和空間效率，以求改進算法或對不同的算法進行比較。（1）時間復雜度：一個程序的時間復雜度是指程序運行從開始到結束所需要的時間。（2）空間復雜度：一個程序的空間復雜度是指程序運行從開始到結束所需的存儲量。在復雜度計算中，實際上是把求解問題的關鍵操作，如加法、減法和比較運算指定為基本操作，然后把算法執行基本操作的次數作為算法的時間復雜度，而把算法執行期間占用存儲單元的數量作為算法的空間復雜度。

緒論

算法分析與復雜度計算

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

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

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

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

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

緒論

算法分析與復雜度計算

若一個算法中的兩個部分的時間復雜度分別為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))。當算法轉換為程序后，每條語句執行一次所需的時間取決于機器的指令性能、速度以及編譯所生成的代碼質量，這是難以確定的。因此，我們假設每條語句執行一次所需的時間均是單位時間，則程序計算的時間復雜度法則如下。

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

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

緒論

算法分析與復雜度計算

【例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];}解：給程序中的語句進行編號，并在其右側列出該語句的頻度：(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，但它的循環體卻只能執行n次。語句（2）作為語句（1）循環體中的一個語句應該執行n次，而語句（2）自身又要執行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循環且每重循環進行n次以及“O”下的乘法準則可直接得到：T(n)=O(n3)。此外要說明的是，時間復雜度按數量級遞增排列的順序如下O(1)＜O(log2n)＜O(n)＜O(nlog2n)＜O(n2)＜O(n3)＜O(2n)22:10:57第2章線性表

第二章

線性表

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

。本章內容提要:線性表及其邏輯結構

線性表的順序存儲結構及運算實現

線性表的鏈式存儲結構及運算實現

第二章

線性表

2.1

線性表及其邏輯結構

線性表的定義

線性表的基本操作

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

線性表的定義

線性表

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

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

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

線性表的定義

線性表

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

線性表的定義

2.1

線性表及其邏輯結構

線性表的定義

線性表的基本操作

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

線性表的基本操作

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

線性表的順序存儲

順序表基本運算的實現

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

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

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

線性表

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

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

線性表

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

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

SeqListList,*L；其中，List是一個結構體變量，它內部含有一個可存儲順序表的data數組；

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

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

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

2.2線性表的順序存儲結構及運算實現

線性表的順序存儲

順序表基本運算的實現

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

順序表算法實現

線性表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;}

順序表算法實現

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

順序表算法實現

線性表插入算法如下：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}}}

順序表算法實現

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

順序表算法實現

線性表刪除算法如下：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順序前移一個位置實現對ai的刪除

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

順序表算法實現

線性表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值}

順序表算法實現

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

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

順序表算法實現

2.3線性表的鏈式存儲結構及運算實現

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

單鏈表

單鏈表運算實現

循環鏈表

單鏈表應用示例

線性表

單鏈表

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

structnode*next;//next為指向后繼結點的指針}LNode; //單鏈表結點類型結點結構如圖

線性表

單鏈表

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

線性表

單鏈表

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

線性表

單鏈表

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

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

單鏈表

單鏈表運算實現

循環鏈表

單鏈表應用示例

線性表

單鏈表運算實現

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

線性表

單鏈表運算實現

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

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

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

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

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

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

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

}

線性表

單鏈表運算實現

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

線性表

單鏈表運算實現

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

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

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

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

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

線性表

單鏈表運算實現

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

inti=0; //i為結點計數器

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

線性表

單鏈表運算實現

3.查找

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

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

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

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

線性表

單鏈表運算實現

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

LNode*p=head->next; //由第一個數據結點開始查找

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

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

線性表

單鏈表運算實現

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

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

線性表

單鏈表運算實現

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

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

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

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

線性表

單鏈表運算實現

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

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

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

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

線性表

單鏈表的運算實現

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

線性表

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

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

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

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

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

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

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

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

單鏈表

單鏈表運算實現

循環鏈表

單鏈表應用示例

線性表

循環鏈表

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

線性表

循環鏈表

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

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

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

單鏈表

單鏈表運算實現

循環鏈表

單鏈表應用示例

線性表

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

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

線性表

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

p=p->next; //p繼續指向剩余結點鏈表新的第一個數據結點

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

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

線性表

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

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

q=B->next; //q始終指向鏈表B的第一個未比較的數據結點

*C=A; //生成鏈表的*C的頭結點

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

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

線性表

單鏈表應用示例

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

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

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

線性表

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

線性表

單鏈表應用示例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; //鏈接成循環單鏈表，此時p指向編號為k的結點

while(p->next!=p) //當循環單鏈表中的結點個數不為1時

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

q->next=p->next; //刪除報數為m的結點

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

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

p=q->next; //p指向新的開始報數結點

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

第3章棧和隊列棧和隊列都是操作受限的線性表棧：先進后出隊列：先進先出22:10:57本章主要內容:棧的定義及基本運算棧的存儲結構和運算實現隊列的定義及基本運算隊列的存儲結構和運算實現

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

棧的定義及基本運算

棧的定義

棧的基本操作22:10:57

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

棧的定義及基本運算

棧的定義

棧的基本操作22:10:57

棧的基本操作棧初始化Init_Stack(s)：生成一個空棧s判棧空Empty_Stack(s)：若棧s為空則返回1，否則返回0入棧Push_Stack(s,x)：在棧s的頂部插入一個新元素x，使x成為新的棧頂元素，棧變化出棧Pop_Stack(s,x)：在棧s非空的情況下，操作結果是將棧s的頂部元素從棧中刪除，并由x返回棧頂元素值，即棧中少了一個元素，棧變化讀棧頂元素Top_Stack(s,x)：在棧s非空的情況下，操作結果是將棧s的頂部元素讀到x中，棧不變化22:10:57本章主要內容:棧的定義及基本運算棧的存儲結構和運算實現隊列的定義及基本運算隊列的存儲結構和運算實現

第3章棧和隊列22:10:573.2棧的存儲結構和運算實現

順序棧

兩個順序棧共享連續空間

鏈棧22:10:57

順序棧順序棧：棧的順序存儲結構利用一組地址連續的存儲單元來依次存放由棧底到棧頂的所有元素，附加一個top指針來指示棧頂元素在順序棧中的位置typedefstruct{datatypedata[MAXSIZE];//棧中元素存儲空間

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

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

順序棧順序棧基本操作：初始化棧voidInit_SeqStack(SeqStack**s){*s=(SeqStack*)malloc(sizeof(SeqStack));//在主調函數中申請棧空間

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

順序棧順序棧基本操作：判斷棧是否為空intEmpty_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

順序棧順序棧基本操作：出棧voidPop_SeqStack(SeqStack*s,datatype*x){//將棧*s中的棧頂元素出棧并通過參數x返回給主調函數

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棧的存儲結構和運算實現

順序棧

兩個順序棧共享連續空間

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

順序棧

兩個順序棧共享連續空間

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