《數(shù)據(jù)結(jié)構(gòu)》全套教學(xué)課件

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

全套可編輯PPT課件數(shù)據(jù)結(jié)構(gòu)與算法項目一全套可編輯PPT課件01數(shù)據(jù)結(jié)構(gòu)概述算法與算法分析02CONTENTS全套可編輯PPT課件PART1.1數(shù)據(jù)結(jié)構(gòu)概述全套可編輯PPT課件1.1.1數(shù)據(jù)結(jié)構(gòu)的概念1.數(shù)據(jù)2.數(shù)據(jù)元素3.數(shù)據(jù)項數(shù)據(jù)(Data)是信息的載體，是能夠輸入計算機(jī)中并能被計算機(jī)識別、存儲和加工處理的符號集合。在計算機(jī)科學(xué)中，數(shù)據(jù)的含義很廣泛，既包括整數(shù)和實數(shù)等數(shù)值類型，也包括聲音、文字和圖像等非數(shù)值類型。數(shù)據(jù)元素(DataElement)是數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行處理。數(shù)據(jù)元素也稱為結(jié)點或記錄。一個數(shù)據(jù)元素可以由一個或多個數(shù)據(jù)項組成。通常，能獨立、完整地描述問題中的一切實體都是數(shù)據(jù)元素。數(shù)據(jù)項(DataItem)是數(shù)據(jù)的最小單位，是對數(shù)據(jù)元素屬性的描述，也稱為域或字段。例如，在圖書管理系統(tǒng)中，可以把一本圖書的有關(guān)信息視為一個數(shù)據(jù)元素，其由書名、作者、書號、出版時間和出版社等數(shù)據(jù)項組成。全套可編輯PPT課件1.1.1數(shù)據(jù)結(jié)構(gòu)的概念4.數(shù)據(jù)對象5.數(shù)據(jù)類型6.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)對象(DataObject)是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。例如，整數(shù)數(shù)據(jù)對象是集合N={0，±1，±2，…};圖書數(shù)據(jù)對象是集合A={“數(shù)據(jù)結(jié)構(gòu)”，“數(shù)據(jù)庫”，“軟件工程”}。數(shù)據(jù)類型(DataType)是一組性質(zhì)相同的值的集合和定義在該集合上的一組操作的總稱。每個數(shù)據(jù)項均屬于某一確定的數(shù)據(jù)類型。按“值”的特性不同，數(shù)據(jù)類型可以分為原子類型和結(jié)構(gòu)類型兩類。數(shù)據(jù)結(jié)構(gòu)(DataStructure)是相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包含三方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩種。1.線性結(jié)構(gòu)線性結(jié)構(gòu)有且僅有一個開始結(jié)點和一個終端結(jié)點，且所有結(jié)點都最多只有一個直接前驅(qū)和一個直接后繼。2.非線性結(jié)構(gòu)非線性結(jié)構(gòu)中，一個結(jié)點可能有多個直接前驅(qū)或多個直接后繼。3.常見的基本邏輯結(jié)構(gòu)集合結(jié)構(gòu)：數(shù)據(jù)元素的有限集合。數(shù)據(jù)元素之間只有“屬于同一個集合”的關(guān)系。1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)線性結(jié)構(gòu)：數(shù)據(jù)元素的有序集合。數(shù)據(jù)元素之間存在一對一的關(guān)系。樹形結(jié)構(gòu)：樹形層次數(shù)據(jù)結(jié)構(gòu)，樹中的數(shù)據(jù)元素之間存在一對多的關(guān)系。圖形結(jié)構(gòu)：圖中的數(shù)據(jù)元素之間是多對多的關(guān)系。上述基本邏輯結(jié)構(gòu)如圖1-1所示。1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)關(guān)于數(shù)據(jù)的存儲結(jié)構(gòu)主要有以下4種。1.順序存儲結(jié)構(gòu)把邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元中，結(jié)點之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)通常借助于程序語言的數(shù)組來描述。2.鏈?zhǔn)酱鎯Y(jié)構(gòu)該結(jié)構(gòu)不要求邏輯上相鄰的結(jié)點在物理位置上也相鄰，結(jié)點間的邏輯關(guān)系由附加的指針結(jié)點來表示，由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。1.1.3數(shù)據(jù)的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)通常借助于程序語言的指針來描述，如圖1-2所示。1.1.3數(shù)據(jù)的存儲結(jié)構(gòu)T

extT

ext3.索引存儲結(jié)構(gòu)在建立結(jié)點信息的同時，還要建立附加的索引表來標(biāo)識結(jié)點的地址。索引表中的每一項稱為索引項，索引項由結(jié)點的關(guān)鍵字和該結(jié)點的存儲地址組成，關(guān)鍵字是能唯一標(biāo)識一個結(jié)點的數(shù)據(jù)項。4.散列存儲結(jié)構(gòu)這種結(jié)構(gòu)的基本思想是，根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址。上述4種存儲結(jié)構(gòu)既可以單獨使用，也可以組合使用，具體使用可根據(jù)實際問題具體分析。PART1.2算法與算法分析4.確定性算法中的每條指令都必須有確切的含義，不能有二義性。在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對于相同的輸入，只能得到相同的輸出。5.可行性一個算法必須是可行的，即算法中描述的操作，可通過已經(jīng)實現(xiàn)的基本運(yùn)算執(zhí)行有限次來實現(xiàn)。2.輸出一個算法有一個或多個輸出，這些輸出是與輸入有著一定關(guān)系的量。3.有窮性一個算法總是(對任何合法的輸入值)在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時間內(nèi)完成。1.2.1算法及其特性1.輸入一個算法有零個或多個輸入，這些輸入取自某個特定對象的集合。1.2.2算法分析1.算法設(shè)計的要求(1)正確性正確性的含義是算法對于一切合法的輸入數(shù)據(jù)都能夠得出滿足規(guī)格說明要求的結(jié)果。事實上，要驗證算法的正確性是極為困難的，因為通常情況下合法的輸入數(shù)據(jù)量太大，用窮舉法逐一驗證是不現(xiàn)實的。所謂的算法正確性，就是指算法達(dá)到了測試要求。(2)可讀性可讀性是指開發(fā)人員對算法閱讀理解的難易程度，可讀性高的算法便于開發(fā)人員之間的交流，有利于算法的調(diào)試與修改。1.2.2算法分析1.算法設(shè)計的要求(3)健壯性對于非法的輸入數(shù)據(jù)，算法能給出相應(yīng)的響應(yīng)，而不是產(chǎn)生不可預(yù)料的后果。(4)高效率與低存儲量需求效率指的是算法的執(zhí)行時間，對于解決同一問題的多個算法，執(zhí)行時間短的算法效率高。存儲量需求是指算法執(zhí)行過程中所需的最大存儲空間。效率與存儲量需求都與問題的規(guī)模有關(guān)，如求100個人的平均薪資與求1000個人的平均薪資顯然不同。對于同樣問題規(guī)模的多個算法，滿足高效率和低存儲量需求的算法好。2.影響算法運(yùn)行時間的因素影響算法運(yùn)行時間的主要因素有計算機(jī)硬件、實現(xiàn)算法的語言、編譯生成的目標(biāo)代碼的質(zhì)量和問題的規(guī)模。換言之，主要因素即計算機(jī)硬件系統(tǒng)、軟件系統(tǒng)和問題的規(guī)模。在各種因素都不能確定的情況下，很難比較出算法的執(zhí)行時間，按照執(zhí)行算法的絕對時間來衡量算法的效率是不合適的。為此，可以將與計算機(jī)軟硬件相關(guān)的因素確定下來，這樣，一個特定算法的運(yùn)行時間就只依賴于問題的規(guī)模，即算法的運(yùn)行時間是問題規(guī)模n的函數(shù)T(n)。1.2.2算法分析3.算法的時間效率分析執(zhí)行一個算法所耗費的時間，應(yīng)該是該算法中每條語句執(zhí)行時間之和，而每條語句的執(zhí)行時間是該語句執(zhí)行次數(shù)(也稱為頻度)與該語句執(zhí)行一次所需時間的乘積。但當(dāng)算法轉(zhuǎn)換為程序之后，每條語句執(zhí)行一次所需的時間取決于機(jī)器的指令性能、速度及編譯所產(chǎn)生的代碼質(zhì)量，這是很難確定的。假設(shè)每條語句執(zhí)行所需的時間均是單位時間，這樣，一個算法的時間耗費就是該算法中所有語句執(zhí)行頻度之和。于是，就可以獨立于機(jī)器的軟件、硬件系統(tǒng)來分析算法的時間耗費。計算算法的時間耗費T(n)需要計算算法中每條語句的執(zhí)行頻度之和。1.2.2算法分析

1.2.2算法分析常用算法時間復(fù)雜度的比較如表1-1所示。5.影響算法時間復(fù)雜度的因素算法的時間復(fù)雜度不僅依賴于問題的規(guī)模，還與輸入實例的初始狀態(tài)有關(guān)。例如，在數(shù)組A[0…n-1]中查找給定值K的算法如下：此算法中語句③的執(zhí)行頻度最高，它不僅與問題規(guī)模n有關(guān)，還與輸入實例中數(shù)組A中各元素的取值及K的取值有關(guān)。若A中沒有與K相等的元素，則語句③的執(zhí)行頻度f(n)=n。若A的最后一個元素等于K，則語句③的執(zhí)行頻度f(n)是常數(shù)0。6.最壞時間復(fù)雜度和平均時間復(fù)雜度最壞情況下的時間復(fù)雜度稱為最壞時間復(fù)雜度。最壞情況下的時間復(fù)雜度是算法在任何輸入實例上運(yùn)行時間的上界。平均時間復(fù)雜度是指所有可能的輸入實例均以等概率出現(xiàn)的情況下，算法的期望運(yùn)行時間。7.算法的空間復(fù)雜度空間復(fù)雜度是對算法在運(yùn)行過程中臨時占用存儲空間的大小，記作S(n)=O(f(n))。其中，n為問題規(guī)模?！纠?-1】求以下5個算法的時間復(fù)雜度。i=i

?2是基本語句，設(shè)執(zhí)行次數(shù)為T(n)，則要滿足：2T(n)-1≤n，即T(n)≤log2

n+1。則時間復(fù)雜度為O(log2

n)。x=x+1是基本語句，執(zhí)行次數(shù)為1，其語句頻度與問題規(guī)模n無關(guān)，則時間復(fù)雜度為O(1)。x=x+1是基本語句，執(zhí)行次數(shù)為n，其語句頻度與問題規(guī)模呈線性關(guān)系，并隨著問題規(guī)模n的增大而增大，則時間復(fù)雜度為O(n)。x=x+1是基本語句，執(zhí)行次數(shù)為n2，則時間復(fù)雜度為O(n2)。x=x+1是基本語句，執(zhí)行次數(shù)為n3，則時間復(fù)雜度為O(n3)。謝謝觀看！數(shù)據(jù)結(jié)構(gòu)

線性表項目二01線性表的定義及基本操作線性表的順序存儲結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)020304CONTENTS順序表與鏈表的比較案例實現(xiàn)——通信錄管理0405PART2.1線性表的定義及基本操作2.1.1線性表的定義線性表(LinearList)是由n個性質(zhì)相同的數(shù)據(jù)元素構(gòu)成的有限序列。其中，表中數(shù)據(jù)元素的個數(shù)n定義為線性表的長度，當(dāng)n=0時，稱為空表，此時表中沒有任何數(shù)據(jù)元素。以n>0時的線性表L=(a1

，a2

，…，ai，…，an

)為例，其中ai(1≤i≤n)稱為表中的第i個數(shù)據(jù)元素，下標(biāo)i表示該元素在線性表中的位置。任意一對相鄰的數(shù)據(jù)元素ai-1和ai(2≤i≤n)均存在線性關(guān)系(ai-1，ai)，且ai-1稱為ai的直接前驅(qū)，ai

稱為ai-1的直接后繼。線性表的邏輯結(jié)構(gòu)如圖2-1所示。(1)存在唯一的數(shù)據(jù)元素a1

，或稱首結(jié)點，它沒有直接前驅(qū)，只有一個直接后繼。(2)存在唯一的數(shù)據(jù)元素an，或稱尾結(jié)點，它沒有直接后繼，只有一個直接前驅(qū)。(3)除第一個結(jié)點(首結(jié)點)外，集合中的每個數(shù)據(jù)元素均只有一個直接前驅(qū)。(4)除最后一個結(jié)點(尾結(jié)點)外，集合中的每個數(shù)據(jù)元素均只有一個直接后繼。2.1.2線性表的基本操作(1)InitList(&L)。初始化線性表L。(2)ListEmpty(L)。判斷線性表L是否為空表，如果L為空表，則返回true(1)；否則返回false(0)。(3)ListLength(L)。求線性表L的長度。(4)LocateNode(L，x)。查找線性表L中值為x的結(jié)點的位置。(5)GetNode(L，i)。取線性表L中的第i個結(jié)點，要求1≤i≤ListLength(L)。(6)InsertList(&L，x，i)。在線性表L中的第i個結(jié)點之前插入值為x的新結(jié)點。(7)DeleteList(&L，i)。刪除線性表L中的第i個結(jié)點。在實際運(yùn)用中，線性表往往還有其他操作，如將兩個或兩個以上的線性表合并成一個線性表；把一個線性表拆分成兩個或兩個以上的線性表，并完成多種條件的合并、拆分、復(fù)制和排序等運(yùn)算。這一過程通常可以借助上述基本操作的組合來實現(xiàn)。PART2.2線性表的順序存儲結(jié)構(gòu)2.2.1順序表的定義順序表(SequentialList)是線性表的順序存儲表示的簡稱，指的是用一組地址連續(xù)的存儲單元依次存儲線性表中的元素，即以存儲位置的相鄰表示相繼的兩個元素之間的前驅(qū)和后繼關(guān)系(邏輯關(guān)系)，并以表中第一個元素的存儲位置作為順序表的起始地址，稱為順序表的基地址。順序表存儲結(jié)構(gòu)如圖2-2所示。若每個數(shù)據(jù)元素需占用c個存儲單元，并將第一個存儲單元所占的地址作為該數(shù)據(jù)元素的存儲位置，設(shè)表的最大長度為MaxSize，順序表邏輯結(jié)構(gòu)如圖2-3所示，則表中任一元素ai的存儲地址為：順序表為相鄰的元素ai

和ai+1賦予相鄰的存儲位置LOC(ai)和LOC(ai+1)，即在線性表中邏輯關(guān)系相鄰的數(shù)據(jù)元素在內(nèi)存中的物理位置也是相鄰的。對于這種存儲方式，只要確定表頭結(jié)點的首地址，線性表中任一數(shù)據(jù)元素都可以隨機(jī)存取，所以順序表是一種隨機(jī)存取的存儲結(jié)構(gòu)。2.2.2順序表的基本操作在C語言中，可以使用結(jié)構(gòu)體類型來定義順序表類型，順序表的類型定義為：注意：①該方法是在前述方法的基礎(chǔ)上，使用結(jié)構(gòu)體將結(jié)點和表長封裝在一起。②SeqList是新定義的結(jié)構(gòu)體類型標(biāo)識符，用來定義順序表，可使用語句“SeqListL；”定義一個順序表L，這樣表長可表示為L.length，順序表中的各個結(jié)點可依次表示為L.data[0]、L.data[1]、...、L.data[L.length-1]。③也可使用語句“SeqList?L；”定義一個指向順序表的指針L，為敘述方便就把L稱為順序表，這樣，順序表的表長和結(jié)點都可用L表示為L->length和L->data[0]、L->data[1]、…、L->data[L->length-1]。下面將使用結(jié)構(gòu)體來描述順序表，并通過此方法來定義順序表。但要注意，這樣定義的順序表L在使用前必須要確定L的指向。有了順序表的描述方法之后，就可以實現(xiàn)對順序表的操作。該算法的問題規(guī)模是表的長度n，基本語句是for循環(huán)中執(zhí)行元素賦值的語句，因此時間復(fù)雜度為O(n)。1.建表操作輸入給定的數(shù)組元素作為線性表的數(shù)據(jù)元素，將其輸入順序表中，并將輸入的元素個數(shù)作為順序表的長度來建立順序表。具體算法如右：2.插入操作將值為t的新結(jié)點插入到當(dāng)前表L中第i個結(jié)點的位置上，如果插入成功，則返回1；否則返回0。可將順序表、新結(jié)點的值t和插入位置i作為參數(shù)。算法步驟：①判斷插入位置是否正確，如果不正確，則給出提示，返回0；否則轉(zhuǎn)向②。②判斷當(dāng)前表是否已滿，如果已滿，則給出提示，返回0；否則轉(zhuǎn)向③。③從最后一個結(jié)點開始依次后移，直到第i個結(jié)點，轉(zhuǎn)向④。④將t插到第i個結(jié)點位置上，并將表長加1，返回1。在C語言中，數(shù)組中元素的下標(biāo)是從0開始的，順序表插入過程如圖2-4所示。具體算法如下：顯然程序中結(jié)點后移的語句執(zhí)行的頻度最高，而對不同的位置該語句執(zhí)行的頻度也不相同，因此需要求該語句的平均執(zhí)行頻度。設(shè)順序表的表長為n，即L->length=n，當(dāng)i的值為1、2、…、n+1時，該語句的執(zhí)行頻度分別為n、n-1、…、1、0，所以平均頻度為[n(n+1)/2]/(n+1)=n/2，因此，該算法的時間復(fù)雜度為T(n)=O(n)。3.刪除操作刪除當(dāng)前表L中第i個結(jié)點，如果刪除成功，則返回1；否則返回0。可將順序表和待刪結(jié)點的位置i作為參數(shù)。算法步驟：①判斷刪除位置是否正確，如果不正確，則給出提示，返回0；否則轉(zhuǎn)向②。②判斷當(dāng)前表是否為空，如果為空，則給出提示，返回0；否則轉(zhuǎn)向③。③從第i+1個結(jié)點開始依次前移，直到最后一個結(jié)點，轉(zhuǎn)向④。④將表長減1，返回1。順序表刪除過程如圖2-5所示。具體算法如下：與插入操作的算法分析相同，在順序表上實現(xiàn)刪除操作，等概率情況下，平均要移動表中大約一半的數(shù)據(jù)元素，最終可得該算法的時間復(fù)雜度為T(n)=(n-1)/2=O(n)。4.查找操作查找操作分為按值查找和按位查找。(1)按值查找在順序表中實現(xiàn)按值查找操作，需要與順序表中的數(shù)據(jù)元素按照順序依次加以比較，若查找成功，則返回對應(yīng)元素的序號；否則返回0。注意：此處序號非元素下標(biāo)。具體算法如下：該算法的問題規(guī)模是表長n，基本語句為while循環(huán)中元素比較的語句。如果順序表的最后一個元素為要找的t，則需要從第一個元素開始，比較n個元素，這是最壞的情況，時間復(fù)雜度為O(n)；如果順序表的第一個元素就是t，則算法只要比較一次即可，這是最好的情況，時間復(fù)雜度為O(1)。等概率情況下，平均要比較n/2個元素，該算法的平均時間復(fù)雜度為O(n)。該算法按順序表從前向后進(jìn)行查找，也可以修改算法實現(xiàn)從后向前查找。當(dāng)實際項目中數(shù)據(jù)量比較大，經(jīng)常使用的數(shù)據(jù)在表的后半部分時，則適合采取從后向前查找的算法。(2)按位查找根據(jù)順序表的隨機(jī)查找的特性，按位查找只需返回相應(yīng)位置的數(shù)據(jù)元素即可。具體算法如下：顯然，按位查找算法的時間復(fù)雜度為O(1)。PART2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.1鏈表的定義1.結(jié)點(Node)的組成線性表中的數(shù)據(jù)元素及元素之間的邏輯關(guān)系可由結(jié)點來表示。結(jié)點由兩部分組成：一部分用來存儲數(shù)據(jù)元素信息的數(shù)據(jù)域；另一部分用來存儲元素直接后繼存儲位置的指針域。結(jié)點結(jié)構(gòu)如圖2-6所示。2.單鏈表(LingleLinkedList)用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示的線性表稱為鏈表，即用一組任意(可以連續(xù)也可以不連續(xù))的存儲單元來存放線性表的結(jié)點。把每個結(jié)點中只包含一個指針域的鏈表稱為單鏈表。3.開始結(jié)點、尾結(jié)點、頭結(jié)點和頭指針在鏈表中存儲第一個數(shù)據(jù)元素(a1)的結(jié)點稱為開始結(jié)點；存儲最后一個數(shù)據(jù)元素(an)的結(jié)點稱為尾結(jié)點，由于尾結(jié)點沒有直接后繼，所以尾結(jié)點指針域的值為NULL，NULL在表示鏈表的示意圖中經(jīng)常用“∧”來代替；在開始結(jié)點之前附加的一個結(jié)點稱為頭結(jié)點；指向鏈表中第一個結(jié)點(頭結(jié)點或開始結(jié)點)的指針稱為頭指針。4.單鏈表示意圖不帶頭結(jié)點的單鏈表如圖2-7(a)所示，帶頭結(jié)點的單鏈表如圖2-7(b)所示。在C語言中，單鏈表的類型定義為：注意：①LinkList和ListNode?是不同名字的同一個指針類型，各有特定的用途以示區(qū)別。②LinkList用來定義指向單鏈表的頭指針。③ListNode?用來定義指向某一結(jié)點的指針，如有定義“ListNode?p；”并使p指向某結(jié)點，則p指向結(jié)點的數(shù)據(jù)域可表示為p->data，p指向結(jié)點的指針域可表示為p->next。2.3.2單鏈表的基本操作1.建表操作鏈表的建立有頭插法建立鏈表和尾插法建立鏈表兩種方式。(1)頭插法建立鏈表頭插法建立鏈表是將新生成的結(jié)點插入現(xiàn)有鏈表的首結(jié)點之前。不帶頭結(jié)點和帶頭結(jié)點的單鏈表頭插法算法如下：以帶頭結(jié)點的單鏈表頭插法建立鏈表為例，具體操作過程如圖2-8所示。(2)尾插法建立鏈表尾插法建立鏈表是將新生成的結(jié)點插入現(xiàn)有鏈表的尾結(jié)點之后。不帶頭結(jié)點的單鏈表和帶頭結(jié)點的單鏈表的尾插法具體算法如下：以帶頭結(jié)點的單鏈表尾插法建立鏈表為例，具體操作過程如圖2-9所示。以上四種建表算法中，問題規(guī)模都取決于表長n，基本語句為while循環(huán)中新結(jié)點插入的語句。因此，算法的平均時間復(fù)雜度均為O(n)。2.插入操作將值為x的新結(jié)點插入到當(dāng)前鏈表第i個結(jié)點的位置上，如果插入成功，則返回1；否則返回0?？蓪㈡湵眍^指針、插入結(jié)點的值和插入位置i作為參數(shù)。算法思路：從開始結(jié)點出發(fā)，按順序查找到第i-1個結(jié)點，將待插入結(jié)點插入到第i-1個結(jié)點的后面。單鏈表的插入如圖2-10所示。具體算法如下：

該算法的問題規(guī)模是表長n，基本語句為while循環(huán)中用于尋找第i-1個結(jié)點的語句，因此算法的平均時間復(fù)雜度為O(n)。3.刪除操作刪除當(dāng)前單鏈表的第i個結(jié)點，如果刪除成功，則返回1；否則返回0。可將鏈表頭指針和刪除位置i作為參數(shù)。算法思路：從開始結(jié)點出發(fā)，按順序查找到第i-1個結(jié)點，將第i個結(jié)點刪除。例如，如果要刪除單鏈表中的數(shù)據(jù)元素ai，則需要找到指向待刪除元素的指針p及指向其直接前驅(qū)結(jié)點的指針r，再將r的next指針指向p的后繼結(jié)點，最后釋放結(jié)點p。單鏈表的刪除如圖2-11所示。具體算法如下：

該算法的問題規(guī)模是表長n，基本語句為while循環(huán)中用于查找值等于x的結(jié)點的語句。算法的平均時間復(fù)雜度為O(n)。4.查找操作單鏈表上的查找操作同樣包括按值查找和按位查找兩種，但與順序表查找不同的是，單鏈表的查找并不能實現(xiàn)隨機(jī)查找，因此只能從表頭開始查找，屬于順序查找。(1)按值查找返回當(dāng)前鏈表中值等于給定值結(jié)點的地址，可將鏈表頭指針和給定值作為參數(shù)。算法思路：從開始結(jié)點出發(fā)，按順序掃描鏈表的結(jié)點，比較當(dāng)前結(jié)點數(shù)據(jù)域的值與給定值是否相等，若相等，則移動指針指向的結(jié)點就是要找的結(jié)點。算法步驟：①定義一個移動指針p指向開始結(jié)點，轉(zhuǎn)向②。②判斷p指向的結(jié)點是否存在，并且當(dāng)前結(jié)點數(shù)據(jù)域的值與給定值是否不相等，若是，則轉(zhuǎn)向③；否則返回p。③使p指向下一個結(jié)點，轉(zhuǎn)向②。具體算法如下：(2)按位查找返回當(dāng)前鏈表中第i個結(jié)點的地址，可將鏈表頭指針和查找位置i作為參數(shù)。算法思路：從開始結(jié)點出發(fā)，按順序掃描鏈表的結(jié)點，并將計數(shù)器加1，當(dāng)計數(shù)器的值為i時，移動指針指向的結(jié)點就是第i個結(jié)點。算法步驟：①定義一個移動指針p指向開始結(jié)點，設(shè)置一個計數(shù)器j并置初值為1，轉(zhuǎn)向②。②判斷p指向的結(jié)點是否存在，并且j是否小于i，若是，則轉(zhuǎn)向③；否則轉(zhuǎn)向④。③使p指向下一個結(jié)點，并將計數(shù)器加1，轉(zhuǎn)向②。④如果j==i，則返回p；否則返回NULL。具體算法如下：上述兩種查找均需從表頭結(jié)點依次向后比較，因此該算法問題規(guī)模均為表長n，時間復(fù)雜度均為O(n)。2.3.3循環(huán)鏈表概述將單鏈表中最后一個結(jié)點的指針指向鏈表中的第一個結(jié)點，使整個鏈表構(gòu)成一個環(huán)形，這種鏈表稱為單循環(huán)鏈表，簡稱循環(huán)鏈表(CircularLinkedList)。從循環(huán)鏈表中的任意一個結(jié)點出發(fā)都可以找到表中的其他結(jié)點。為了統(tǒng)一處理空表與非空表，通常循環(huán)鏈表也附設(shè)一個頭結(jié)點，如圖2-12所示。有時，在循環(huán)鏈表中只設(shè)指向尾結(jié)點的尾指針rear而不設(shè)頭指針，這樣便于對鏈表的頭結(jié)點和尾結(jié)點進(jìn)行操作。循環(huán)鏈表的操作過程與單鏈表類似，差別在于當(dāng)需要從頭到尾遍歷整個鏈表時，判斷是否達(dá)到表尾的條件不同。在單鏈表中找表尾結(jié)點要判斷某結(jié)點鏈域值是否為“空”；在循環(huán)鏈表中找表尾結(jié)點則要判斷某結(jié)點的鏈域值是否等于頭指針。在循環(huán)鏈表中，從表中任一結(jié)點p出發(fā)，均可以找到其前驅(qū)結(jié)點。具體算法如下：顯然，該算法的時間復(fù)雜度為O(n)。2.3.4雙向鏈表概述在單鏈表中，從一個已知結(jié)點出發(fā)，只能訪問到該結(jié)點及其后繼結(jié)點，無法找到該結(jié)點之前的其他結(jié)點。而在循環(huán)鏈表中，雖然從任一結(jié)點出發(fā)都可訪問到表中的所有結(jié)點，但訪問該結(jié)點的直接前驅(qū)結(jié)點的時間復(fù)雜度為O(n)；另外，在單鏈表中，若已知某結(jié)點p的存儲位置，則將一新結(jié)點s插入p之后比插入p之前更方便，因為使用前插法必須知曉p直接前驅(qū)結(jié)點的位置。同理，刪除p的直接后繼結(jié)點比刪除p本身更方便。1.雙向鏈表(DoublyLinkedList)在單鏈表的每個結(jié)點里再增加一個指向其直接前驅(qū)結(jié)點的指針域prior，這樣形成的鏈表中有兩條方向不同的鏈，因此稱為雙向鏈表。在雙向鏈表中增加一個頭結(jié)點，得到帶頭結(jié)點的雙向鏈表。帶頭結(jié)點的雙向鏈表能使某些操作變得方便。將雙向鏈表頭結(jié)點和尾結(jié)點連接起來構(gòu)成的循環(huán)鏈表，稱為雙向循環(huán)鏈表。雙向(循環(huán))鏈表示意圖如圖2-13所示。在C語言中，雙向鏈表的類型定義為：2.插入操作(前插)在帶頭結(jié)點的雙向鏈表中，將值為x的新結(jié)點s插入結(jié)點p之前，設(shè)p!=NULL。可將指向結(jié)點的指針p和插入結(jié)點的值x作為參數(shù)。在結(jié)點p之前插入結(jié)點s，需要完成以下4個操作，雙向鏈表前插操作如圖2-14所示。注意：操作③必須在操作①和操作②之后進(jìn)行，只要能夠保證這一點，4個操作的順序可以任意，都能實現(xiàn)前插操作。具體算法如下：3.刪除操作在帶頭結(jié)點的雙向鏈表中，刪除當(dāng)前結(jié)點p，設(shè)p!=NULL。可將指向結(jié)點的指針p作為參數(shù)。關(guān)于此處的結(jié)點p，有以下兩種情況需要考慮。(1)p不是尾結(jié)點，即p->next!=NULL此時需要完成以下兩個操作，雙向鏈表刪除當(dāng)前結(jié)點操作如圖2-15所示。(2)p是尾結(jié)點，即p->next==NULL此時只需完成操作p->prior->next=NULL或p->prior->next=p->next即可。注意：無論上述哪種情況，完成后均需做一個釋放結(jié)點p的存儲空間的操作，即free(p)。PART2.4順序表與鏈表的比較1.基于時間的考慮順序表可實現(xiàn)元素的隨機(jī)存取，對表中任意結(jié)點都可以在O(1)時間內(nèi)直接存取；而鏈表中的結(jié)點則需要從頭指針起，按順序掃描結(jié)點才能存取。因此，若線性表的操作主要是進(jìn)行查找操作，很少進(jìn)行插入和刪除操作，則應(yīng)采用順序表作為存儲結(jié)構(gòu)。對于頻繁進(jìn)行插入和刪除操作的線性表,應(yīng)采用鏈表作為存儲結(jié)構(gòu)。2.基于空間的考慮順序表的存儲空間是靜態(tài)分配的，在程序執(zhí)行之前，必須明確規(guī)定它的存儲規(guī)模，即對MaxSize要有合適的設(shè)定。因此，當(dāng)線性表的長度變化較大而難以估計其存儲規(guī)模時，不宜采用順序表。鏈表無須事先估計存儲規(guī)模，但鏈表的存儲密度較低。存儲密度是指結(jié)點數(shù)據(jù)本身所占的存儲單元數(shù)和整個結(jié)點所占的存儲單元數(shù)之比。顯然，存儲密度越大，存儲空間的利用率就越高。3.基于語言的考慮各種高級語言都提供數(shù)組，但不一定提供指針，由于鏈表是基于指針的，所以鏈表的使用有時會受到高級語言的限制。PART2.5案例實現(xiàn)——通信錄管理2.5.1案例分析現(xiàn)有一份通信錄如表2-1所示，在該表中，單個數(shù)據(jù)元素是聯(lián)系人所對應(yīng)的一行信息，包括姓名、性別、手機(jī)號碼、住宅電話和電子郵箱五個數(shù)據(jù)項，通信錄中的記錄按順序排列。其中，“性別”字段用0和1表示，0表示女性，1表示男性。記錄之間是一對一的關(guān)系，除第一條記錄和最后一條記錄外，每條記錄都只有一個直接前驅(qū)和一個直接后繼。因此，系統(tǒng)中的數(shù)據(jù)元素是線性結(jié)構(gòu)，可以采用順序表和鏈表兩種方式實現(xiàn)。表2-1通信錄2.5.2案例1——基于順序表的通信錄管理在基于順序表的通信錄管理實現(xiàn)過程中，設(shè)計了如下操作：(1)輸入數(shù)組中存放的數(shù)據(jù)以建立順序表，并輸出檢驗。本步驟使用了順序表的建立算法。(2)輸入新記錄的插入位置和各項值，從而實現(xiàn)新記錄的插入，并輸出檢驗。本步驟使用了順序表的指定位置插入算法。(3)刪除查找到的記錄。輸入要查找的記錄的“姓名”，若找到，則刪除該記錄的信息；否則輸出“刪除位置非法”。本步驟使用了順序表的查找算法和刪除算法。程序運(yùn)行結(jié)果如圖2-16所示。2.5.3案例2——基于鏈表的通信錄管理在基于鏈表的通信錄管理實現(xiàn)過程中，出于對系統(tǒng)靈活性和可操作性的考慮，要求系統(tǒng)運(yùn)行采用菜單式呈現(xiàn)。針對案例的具體要求，設(shè)計以下操作：(1)設(shè)計菜單顯示效果，可供用戶通過選擇菜單項執(zhí)行不同的功能。(2)用單鏈表存儲數(shù)據(jù)。因為在通信錄的使用過程中，新添加的記錄使用頻率相對較高，所以本步驟采用了不帶頭結(jié)點的單鏈表頭插法建立鏈表。(3)輸入新記錄的各項值，在原有鏈表的首結(jié)點之前插入新結(jié)點。本步驟采用單鏈表的頭插法建立鏈表。(4)輸入要查找記錄的姓名，若找到，則輸出該記錄的信息；否則輸出“該記錄不存在”。本步驟采用單鏈表的查找算法。(5)輸入要刪除記錄的姓名，若找到，則刪除該記錄；否則提示“沒有查到要刪除的通訊者”。本步驟采用單鏈表的刪除算法。程序運(yùn)行后，按照提示進(jìn)行選擇，如選擇“1”，然后輸入“張婉0166000000016000001zhang_x0002_wan@163.com”和“鄭涂1166000000026000002zhengtu@126.com”兩條記錄，如圖2-17(a)所示。之后選擇“2”插入新結(jié)點“李麗”的相關(guān)信息，選擇“5”輸出鏈表后如圖2-17(b)所示。謝謝觀看！數(shù)據(jù)結(jié)構(gòu)

棧和隊列項目三01棧隊列案例實現(xiàn)——漢諾塔問題和鍵盤緩沖區(qū)0203CONTENTSPART3.1棧3.1.1棧的定義及基本操作1.棧的定義棧(Stack)是只允許在一端完成插入和刪除操作的線性表，向棧中插入元素稱為進(jìn)(入)棧，從棧中刪除元素稱為退(出)棧。通常允許插入、刪除的這一端稱為棧頂(StackTop)，由于元素的入棧和出棧，棧頂?shù)奈恢媒?jīng)常是變動的，因此需要用一個整型量top指示棧頂?shù)奈恢茫ǔ７Qtop為棧頂指針，另一端稱為棧底。當(dāng)表中沒有元素時稱為空棧，即top=-1。棧為后進(jìn)先出(LastInFirstOut，LIFO)的線性表，簡稱為LIFO表。由于棧的修改是按后進(jìn)先出的原則進(jìn)行的，因此每次刪除的總是當(dāng)前棧中“最新”的元素，即最后插入的元素，而最先插入的元素則被放在棧的底部，直到最后才能被刪除。如圖3-1所示就是棧的基本結(jié)構(gòu)。(4)入棧Push(S，x)。若S非滿棧，則將元素x插入棧頂。(6)取棧頂元素GetTop(S，x)。若S非空棧，則將棧頂元素存放到x中，棧的狀態(tài)不變。(1)置棧空InitStack(S)。構(gòu)造一個空棧S。(3)判棧滿StackFull(S)。若S為滿棧，則返回1；否則返回0。(5)出棧Pop(S，x)。若S非空棧，則將棧頂元素存放到x中并返回，變更棧的狀態(tài)。(2)判棧空StackEmpty(S)。若S為空棧，則返回1；否則返回0。2.棧的基本操作棧可以理解為操作受限的線性表，因此我們可以結(jié)合線性表的存儲結(jié)構(gòu)來理解棧的存儲結(jié)構(gòu)，所以棧的存儲結(jié)構(gòu)同樣也包括順序存儲和鏈?zhǔn)酱鎯煞N。1.順序棧的定義棧的順序存儲結(jié)構(gòu)即為順序棧(SequenceStack)。順序?？梢赃M(jìn)行如下定義：3.1.2順序棧設(shè)S是SeqStack類型的指針變量，則棧頂指針可表示為S->top，棧頂元素可表示為S->stack[S->top]。注意：①條件S->top==StackSize-1表示棧滿，條件S->top==-1表示?？铡＂诋?dāng)有元素x入棧時，需要先將S->top加1，然后再將元素入棧，即依次完成下列操作：S->top++，S->stack[S->top]=x，可將其合并為一個操作：S->stack[++S->top]=x。③當(dāng)棧頂元素做出棧操作時，需要先將棧頂元素出棧，即x=S->stack[S->top]，再將棧頂指針減1，即S->top--，可將其合并為一個操作：x=S->stack[S->top--]。棧頂指針與棧中元素的關(guān)系如圖3-2所示。④當(dāng)棧滿時，做入棧操作所產(chǎn)生的空間溢出現(xiàn)象稱為上溢；當(dāng)棧空時，做出棧操作所產(chǎn)生的溢出現(xiàn)象稱為下溢，其中，上溢屬于出錯狀態(tài)，應(yīng)設(shè)法避免。2.順序棧的基本操作(1)棧的初始化(2)判?？?3)入棧操作(4)出棧操作(5)取棧頂元素3.1.3鏈棧1.鏈棧的定義棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧(LinkedStack)，其插入和刪除操作只允許在表頭位置上進(jìn)行，鏈表的頭指針就是棧頂指針。鏈?？梢赃M(jìn)行如下定義：2.鏈棧的基本操作(1)棧的初始化(2)判棧空(3)入棧操作(4)出棧操作(5)取棧頂元素注意：由于鏈棧中的結(jié)點是動態(tài)分配的，因此可以不考慮上溢，故無須定義StackFull操作。3.1.4順序棧和鏈棧的比較1.時間性能因為棧的所有操作都在棧頂進(jìn)行，所以順序棧和鏈?；静僮鞯乃惴ǘ贾恍枰?shù)階的時間。2.空間性能順序棧初始化時需要設(shè)定一個固定的長度，當(dāng)數(shù)據(jù)元素過多時可能出現(xiàn)上溢現(xiàn)象，數(shù)據(jù)元素較少時又存在空間浪費現(xiàn)象。鏈棧只有在內(nèi)存空間不足時才會出現(xiàn)棧滿的問題，但因為每個元素結(jié)點都需要指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。因此，棧的使用過程中如果元素個數(shù)變化較大，則宜選用鏈棧；反之則選用順序棧。3.1.5棧的應(yīng)用棧的一個重要應(yīng)用就是在程序設(shè)計中實現(xiàn)遞歸。遞歸，即子程序(或函數(shù))直接或間接調(diào)用自身的算法，可以理解為，遞歸函數(shù)的調(diào)用是函數(shù)在執(zhí)行過程中進(jìn)行多次自我嵌套調(diào)用，而棧恰恰是嵌套調(diào)用機(jī)制的實現(xiàn)基礎(chǔ)。遞歸通常用于解決結(jié)構(gòu)自相似的問題。例如，臺階問題、漢諾塔問題及圖的遍歷等。它本質(zhì)上是將一個大問題轉(zhuǎn)換為一個或多個小問題，再將小問題繼續(xù)分解為更小的問題，直到小問題可以解決為止。因此，遞歸有兩個組成部分：一是遞歸終止條件；二是遞歸模式。遞歸調(diào)用的執(zhí)行步驟為：①記錄調(diào)用過程結(jié)束時的返回地址及前一次調(diào)用過程中的數(shù)據(jù)信息。②無條件轉(zhuǎn)移到被調(diào)用過程的入口地址開始執(zhí)行程序。③傳遞返回的數(shù)據(jù)信息。④取出返回地址，且無條件地轉(zhuǎn)移到該地址，即返回到調(diào)用過程中去執(zhí)行程序。【例3-1】遞歸———階乘問題的操作。要求：用遞歸調(diào)用編寫計算階乘n!的函數(shù)f(n)。設(shè)計思路：上述函數(shù)中，n=0是終止遞歸的條件，以3的階乘為例，遞歸中棧的變化過程如圖3-3所示。(1)開始時，棧為空，如圖3-3(a)所示。(2)在棧中保存3乘2!，如圖3-3(b)所示。(3)調(diào)用2!，在棧中保存2乘1!，如圖3-3(c)所示。(4)調(diào)用1!，在棧中保存1乘0!，如圖3-3(d)所示。(5)調(diào)用0!。因為n=0達(dá)到了遞歸終止的條件，0!值為1，所以返回1。1乘1退棧，此時得到1!的值為1，如圖3-3(e)所示。(6)2乘1退棧，此時得到2!的值為2，如圖3-3(f)所示。(7)3乘2退棧，此時得到3!的值為6。這時棧已空，算法結(jié)束。最后結(jié)果為6，如圖3-3(g)所示。由此分析可知，遞歸算法因為需要反復(fù)入棧、出棧，時間和空間開銷比較大，因此執(zhí)行效率比較低。具體算法如下：程序運(yùn)行結(jié)果如圖3-4所示。PART3.2隊

列3.2.1隊列的定義及基本操作與棧類似，隊列也是一種操作受限的線性表，但與棧的限制不同。1.隊列的定義隊列(Queue)是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的操作受限的線性表。向隊列中插入元素稱為入隊，從隊列中刪除元素稱為出隊。允許刪除的一端稱為隊頭(Front)，允許插入的一端稱為隊尾(Rear)，當(dāng)隊列中沒有元素時稱為空隊列。隊列是先進(jìn)先出(FirstInFirstOut，F(xiàn)IFO)的線性表，簡稱為FIFO表。隊列的修改是依照先進(jìn)先出的原則進(jìn)行的，新來的成員總是加入隊尾(即不允許插隊)，每次離開的成員總是隊頭上的成員(不允許中途離隊)，即當(dāng)前“最老”的成員離隊。例如，設(shè)隊列Q=(a1，a2

，a3

，…，an

)，其中a1

就是隊首元素，an

就是隊尾元素，若入隊時按照自a1

至an

的順序進(jìn)入，則出隊時也按照同樣的順序退出，隊列的先進(jìn)先出如圖3-5所示。2.隊列的基本操作(1)置隊空：InitQueue(&Q)。構(gòu)造一個空隊列Q。(2)判隊空：QueueEmpty(Q)。若隊列Q為空，則返回1；否則返回0。(3)判隊滿：QueueFull(Q)。若隊列Q為滿，則返回1；否則返回0。(4)入隊：EnQueue(&Q，x)。若隊列Q非滿，則將元素x插入Q的隊尾。(5)出隊：DelQueue(&Q，&x)。若隊列Q非空，則將Q的隊頭元素賦值給x中并返回，改變隊列的狀態(tài)。(6)取隊頭元素：GetHead(Q，&x)。若隊列Q非空，則將Q的隊頭元素賦值給x中并返回，不改變隊列的狀態(tài)。3.2.2順序隊列1.順序隊列的定義隊列的順序存儲結(jié)構(gòu)稱為順序隊列(SequentialQueue)。順序隊列與順序表類似，采用一個一維數(shù)組存放數(shù)據(jù)元素。由于隊列的隊首和隊尾位置要隨著出隊、入隊操作不斷變化，所以應(yīng)設(shè)置兩個指針front和rear分別用來指向當(dāng)前隊首和隊尾。順序隊列的類型定義如下：隊首指針front和隊尾指針rear的初值在隊列初始化時置為-1。非空隊列中，隊首指針始終指向當(dāng)前隊首元素的前一個位置，隊尾指針指向當(dāng)前的隊尾元素。當(dāng)新元素入隊時，rear指針先加1，再賦值；當(dāng)隊首元素出隊時，front指針也先加1，再取走元素。2.順序隊列的基本操作設(shè)有一個順序隊列為q=(a，b，c，d，e)，對應(yīng)的存儲結(jié)構(gòu)如圖3-6(a)所示，此時front==-1，rear==4。若元素f、g和h相繼入隊，如圖3-6(b)所示，則此時front==-1，rear==7，rear==QueueMaxSize-1，隊列已滿。元素a和b出隊，如圖3-6(c)所示，此時front==1，rear==7。若所有元素都出隊，如圖3-6(d)所示，則此時front==rear==7，隊列變?yōu)榭贞犃?。從圖3-6可以看出，在順序隊列中，當(dāng)rear==QueueMaxSize-1時，隊列滿；當(dāng)front==rear時，隊列空。在如圖3-6(d)所示的情況下，隊列實際已經(jīng)為空，但如果此時存在元素要入隊，由于rear指針已達(dá)到數(shù)組下界，則將會造成“溢出”。順序隊列中，這種不是由于存儲空間不夠，而是由于經(jīng)過多次插入和刪除操作引起的溢出，稱為“假溢出”。當(dāng)出現(xiàn)假溢出時，如果把所有的元素向低位移動，使空位從低位區(qū)移向高位區(qū)，則會浪費時間。因此，可以把隊列向量空間的元素位置0至QueueMaxSize-1看成一個首尾相接的環(huán)形，當(dāng)入隊的隊尾指針等于最大容量，即rear==QueueMaxSize時，rear=0。3.2.3循環(huán)隊列1.循環(huán)隊列的定義3.2.2節(jié)中提到了避免“假溢出”現(xiàn)象的方法，而循環(huán)隊列可以理解為向量空間的元素位置首尾相接的順序隊列，在循環(huán)隊列中，可以通過數(shù)學(xué)運(yùn)算中的取余運(yùn)算實現(xiàn)隊列的首尾相連。由圖3-7可以看出，循環(huán)隊列隊空和隊滿的條件都是front==rear，這就使兩者難以區(qū)分，為了解決這一問題，可采用以下三種方式。(1)設(shè)置標(biāo)志位tag。將tag初始化為0，當(dāng)入隊操作成功時，設(shè)置tag=1；當(dāng)出隊操作成功時，設(shè)置tag=0，則隊滿的條件為front==rear&&tag==1，隊空的條件為front==rear&&tag==0。(2)設(shè)置一個計數(shù)器num。將num初始化為0，當(dāng)入隊操作成功時，num加1；當(dāng)出隊操作成功時，num減1，則隊滿的條件為num==QueueMaxSize，隊空的條件為num==0。(3)犧牲一個存儲空間。在非空循環(huán)隊列中，隊首指針始終指向當(dāng)前隊首元素的前一個位置，隊尾指針指向當(dāng)前的隊尾元素。隊列為空時，隊首指針和隊尾指針相等，即front==rear；隊滿時，隊尾指針加1后等于隊首指針，即front==(rear+1)%QueueMaxSize。循環(huán)隊列隊滿如圖3-8所示。該方式用來區(qū)別循環(huán)隊列的隊空和隊滿狀態(tài)。2.循環(huán)隊列的基本操作(1)隊列的初始化(2)隊列判空(3)入隊操作(4)出隊操作

(5)取隊首元素3.2.4鏈隊列1.鏈隊列的定義隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊列(LinkedQueue)。鏈隊列是只允許在表頭插入和表尾刪除的單鏈表，因此需要設(shè)置指向隊頭的指針front和指向隊尾的指針rear。為了使空鏈隊列與非空鏈隊列的處理一致，鏈隊列也要加上頭結(jié)點，帶頭結(jié)點的鏈隊列如圖3-9所示。當(dāng)鏈隊列為空時，front==rear，其頭指針和尾指針均指向頭結(jié)點。2.鏈隊列的基本操作鏈隊列的類型定義如下：(1)隊列的初始化(2)隊列判空(3)入隊操作(4)出隊操作

(5)取隊首元素3.2.5循環(huán)隊列和鏈隊列的比較關(guān)于循環(huán)隊列和鏈隊列之間的差別，可以從其時間性能和空間性能兩個角度進(jìn)行分析。1.時間性能受限于隊列的操作，插入操作只能在隊尾進(jìn)行，刪除操作只能在隊頭進(jìn)行，因此循環(huán)隊列和鏈隊列基本操作的算法時間復(fù)雜度都為O(1)。2.空間性能循環(huán)隊列雖然可以避免普通順序隊列的“假溢出”現(xiàn)象，但作為順序存儲結(jié)構(gòu)依然存在事先確定隊列空間的問題。所以，循環(huán)隊列存在存儲元素個數(shù)的限制和空間浪費的問題。鏈隊列在內(nèi)存擁有空閑空間時沒有隊列滿的問題，但因結(jié)構(gòu)問題，存儲密度小于1，故產(chǎn)生了結(jié)構(gòu)性開銷。因此，當(dāng)隊列使用過程中元素個數(shù)變化較大時，更適合選用鏈隊列；反之，則應(yīng)選用循環(huán)隊列。3.2.6隊列的應(yīng)用下面以一個例題來介紹循環(huán)隊列的操作?！纠?-2】循環(huán)隊列的操作。要求：對于循環(huán)隊列，將自然數(shù)按順序入隊、出隊。具體的操作是：當(dāng)隊列未滿時，入隊、出隊，輸出出隊元素的值；當(dāng)隊滿時，執(zhí)行連續(xù)出隊操作，輸出出隊元素的值(應(yīng)與隊列未滿時輸出的標(biāo)識不同)，直至隊列為空。當(dāng)隊列采用順序存儲結(jié)構(gòu)時，涉及的操作有隊列的初始化、判斷隊列是否為空、入隊、判斷隊列是否為滿、出隊。設(shè)計思路：(1)若將MaxSize定義為20，則預(yù)期的輸出結(jié)果是：1?2?3?4?5?6?7?8?9?10?11?12?13?14?15?16?17?18?19#20#21#22#23#24#25#26#27#28#29#30#31#32#33#34#35#36#37#。(2)當(dāng)隊列未滿時，出隊元素的值后跟一個星號(?)，具體是從1到18(隊列中元素的值從19到37，共19個元素)；隊列滿后，執(zhí)行連續(xù)出隊操作，出隊元素的值后跟一個井號(#)，具體是從19到37。(3)初始化隊列，當(dāng)隊列未滿時，自然數(shù)按順序入隊、出隊，并輸出出隊元素的值，后跟一個星號；當(dāng)隊列滿時，連續(xù)出隊，并輸出出隊元素的值，后跟井號，直到隊列為空。具體算法如下：程序運(yùn)行結(jié)果如圖3-10所示。PART3.3案例實現(xiàn)——漢諾塔問題和鍵盤緩沖區(qū)3.3.1案例1———漢諾塔問題漢諾塔圓盤之間的移動過程很復(fù)雜、煩瑣，但規(guī)律性卻很強(qiáng)。分析圓盤的移動順序。若n=1，則將圓盤從a桿直接移動到c桿。若n=2，則將a桿上的n-1(等于1)個圓盤移到b桿上，再將a桿上的一個圓盤移到c桿上，最后將b桿上的n-1(等于1)個圓盤移到c桿上。若n=3，則：(1)將a桿上的n-1(等于2，令其為n′)個圓盤移到b桿上(借助于c桿)，即①將a桿上的n′-1(等于1)個圓盤移到c桿上。②將a桿上的一個圓盤移到b桿上。③將c桿上的n′-1(等于1)個圓盤移到b桿上。(2)將a桿上的一個圓盤移到c桿上。(3)將b桿上的n-1(等于2，令其為n′)個圓盤移到c桿上(借助a桿)，即①將b桿上的n′-1(等于1)個圓盤移到a桿上。②將b桿上的一個圓盤移到c桿上。③將a桿上的n′-1(等于1)個圓盤移到c桿上。至此，完成了三個圓盤的移動過程。分析該移動過程可知，可以使用遞歸調(diào)用來解決這個移動過程。當(dāng)n≥2時，移動的過程可分解為三個步驟：①以c桿為臨時桿，從a桿將1至n-1號盤移至b桿。②將a桿中剩下的第n號盤移至c桿。③以a桿為臨時桿，從b桿將1至n-1號盤移至c桿?？梢钥吹剑襟E②只需移動一次即可完成；步驟①與③的操作則完全相同，唯一區(qū)別在于各桿的作用有所不同。這樣，原問題被轉(zhuǎn)換為相同性質(zhì)的、規(guī)模較小的新問題，即Hanoi(n，a，b，c)可轉(zhuǎn)化為Hanoi(n-1，a，c，b)與Hanoi(n-1，b，a，c)。其中，Hanoi中的參數(shù)分別表示為需移動的盤數(shù)、起始桿、臨時桿與終止桿。采用遞歸算法實現(xiàn)，漢諾塔問題流程如圖3-11所示。程序運(yùn)行結(jié)果如圖3-12所示。3.3.2案例2———鍵盤緩沖區(qū)為了充分利用緩沖區(qū)的空間，往往將緩沖區(qū)設(shè)計成循環(huán)隊列的結(jié)構(gòu)，并為其設(shè)置一個隊首指針和一個隊尾指針。每輸入一個字符到緩沖區(qū)中，就將尾指針后移，進(jìn)入緩沖區(qū)的循環(huán)隊列中；每輸出一個字符，就將隊頭指針前移，將其從緩沖區(qū)隊列中刪除。程序運(yùn)行后顯示“序號HelloWorld!”，此時可以通過鍵盤輸入字符，但屏幕不顯示。例如，輸入“havefun，”，由鍵盤輸入“，”時，屏幕顯示剛才鍵盤輸入的字符；按Enter鍵時，繼續(xù)顯示“序號HelloWorld!”；在字符后輸入“；”時，系統(tǒng)退出。程序運(yùn)行結(jié)果如圖3-13所示。謝謝觀看！數(shù)據(jù)結(jié)構(gòu)

串和數(shù)組項目四01串?dāng)?shù)組案例實現(xiàn)——單詞檢索計數(shù)和稀疏矩陣的運(yùn)算0203CONTENTSPART4.1串串的邏輯結(jié)構(gòu)與線性表十分相似，區(qū)別在于串的數(shù)據(jù)對象約束為字符集。1.串的定義串(String)是字符串的簡稱。它是一種在數(shù)據(jù)元素的組成上具有一定約束條件的線性表，即要求組成線性表的所有數(shù)據(jù)元素都是字符。所以也可以這樣定義串：串是由零個或多個字符組成的有限序列。串一般記作s="a1a2…an"(n≥0)其中，s是串的名稱，用雙引號("")括起來的字符序列是串的值；雙引號本身不是串的值，它們是串的標(biāo)記，以便將串與標(biāo)識符(如變量名)加以區(qū)別，稱為定界符；ai(1≤i≤n)可以是字母、數(shù)字或其他字符；串中字符的數(shù)目n被稱作串的長度(或串長)。當(dāng)n=0時，串中沒有任何字符，串的長度為0，稱為空串，用?表示。4.1.1串的邏輯結(jié)構(gòu)而空格串是由一個或者多個空格組成的串，串的長度為所含空格的個數(shù)。例如：s1

=""s2

="

"s1

中沒有字符，是一個空串；s2

中有兩個空格字符，故其長度等于2，是一個空格串。串中任意連續(xù)的字符組成的子序列稱為該串的子串。包含子串的串相應(yīng)地又稱為該子串的主串。通常稱字符在串中的序號為該字符在串中的位置。當(dāng)一個字符在串中多次出現(xiàn)時，以該字符第一次在串中出現(xiàn)的位置為該字符在串中的位置。子串在主串中的位置則以子串在主串中第一次出現(xiàn)的第一個字符的位置來表示。當(dāng)且僅當(dāng)兩個串的長度相等且各個對應(yīng)位置上的字符都相同時，兩個串相等。2.串的基本操作(1)StrAssign(&s1，s2)。將串s1賦值為s2。(2)StrLength(s)。返回串的長度。(3)StrConcat(s1，s2，&s)或StrConcat(&sl，s2)。用s返回由串s2和串s1連接而成的新串。(4)SubStr(s，pos，len)。返回串s中從第pos個字符開始長度為len的子串。(5)StrCompare(sl，s2)。比較串s1和串s2的大小。若s1>s2，則返回正整數(shù)；若s1=s2，則返回0；若s1<s2，則返回負(fù)整數(shù)。(6)StrIndex(s，t，pos)。返回串t在串s的第pos個字符之后首次出現(xiàn)的位置，若t不是s的子串，則返回0。(7)StrInsert(&s，pos，t)。在串s的第pos個字符之前插入串t。(8)StrDelete(&s，pos，len)。刪除串s中第pos個字符開始長度為len的子串。(9)StrReplace(&s，t，r)。用串r替換串s中出現(xiàn)的所有與串t相等的不重疊子串。(10)StrEqual(s，t)。判斷串s與串t是否相等。以上是串的幾個基本操作，其中前五個操作是最為基本的，不能用其他的操作來實現(xiàn)，因此通常將這五個基本操作稱為最小操作子集。而其他的操作均可在最小操作子集上實現(xiàn)。4.1.2串的存儲結(jié)構(gòu)由于串是一種特殊的線性表，其存儲結(jié)構(gòu)與線性表的存儲結(jié)構(gòu)類似。但由于串是由若干單個字符組成，所以存儲時有一些特殊技巧。串的存儲方式取決于對串所進(jìn)行的操作，串在計算機(jī)中有三種表示方法。(1)定長順序存儲結(jié)構(gòu)。這種表示方法是將串定義成字符數(shù)組，是最簡單的處理方法。此時，數(shù)組名即為串名，從而可以根據(jù)串名直接訪問串值。使用這種方法時，串的大小不能更改。(2)堆分配存儲結(jié)構(gòu)。這種表示方法的特點是用一組地址連續(xù)的存儲單元依次存儲串中的字符序列，但串的存儲空間是在程序運(yùn)行時根據(jù)串的實際長度動態(tài)分配的。(3)串的鏈?zhǔn)酱鎯Y(jié)構(gòu)。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，每個結(jié)點設(shè)定一個字符域char，存放字符；設(shè)定一個指針域next，存放所指向的下一個結(jié)點的地址。1.串的定長順序存儲結(jié)構(gòu)串的定長順序存儲結(jié)構(gòu)是采用與其邏輯結(jié)構(gòu)相對應(yīng)的存儲結(jié)構(gòu)，將串中的各個字符按順序依次存放在一組地址連續(xù)的存儲單元里，邏輯上相鄰的字符在內(nèi)存中也相鄰。這是一種靜態(tài)存儲結(jié)構(gòu)，串值的存儲分配是在編譯時完成的。因此，需要預(yù)先定義串的存儲空間大小。在串的定長順序存儲結(jié)構(gòu)中，串的類型定義如下：以下給出串的定長順序存儲結(jié)構(gòu)中，串的判斷相等、連接和求子串等基本操作的實現(xiàn)。(1)判斷相等(2)連接操作(3)求子串串的定長順序存儲結(jié)構(gòu)適用于求串長和求子串等操作。但這種存儲結(jié)構(gòu)存在以下兩個缺點：一是需要預(yù)先定義一個串允許的最大長度，若定義空間過大，則會造成浪費；二是由于限定了串的最大長度，因而會限制串的部分操作，如連接和置換操作等。2.串的堆分配存儲結(jié)構(gòu)堆分配存儲結(jié)構(gòu)的實現(xiàn)方法是，提供一個足夠大的連續(xù)存儲空間作為串的可利用空間，用來存儲各串的串值。每當(dāng)建立一個新串時，系統(tǒng)就從這個可利用空間中劃分出一個大小與新串長度相等的空間給新串，若分配成功，則返回一個指向起始地址的指針。為操作方便，將每個串的長度信息也作為存儲結(jié)構(gòu)的一部分?？墒褂肅語言中動態(tài)分配函數(shù)庫中的malloc(

)函數(shù)和free(

)函數(shù)來管理可利用空間。串的堆分配存儲結(jié)構(gòu)可進(jìn)行如下定義，串的堆分配存儲結(jié)構(gòu)示例如圖4-1所示。以下是基于該存儲結(jié)構(gòu)實現(xiàn)的一些算法。(1)串的賦值(2)串的連接堆分配存儲結(jié)構(gòu)的串既有順序存儲結(jié)構(gòu)的特點(簡單、便捷)，又因為在實際操作中對串長沒有任何限制，足夠靈活，所以經(jīng)常被用于串處理的過程中。3.串的鏈?zhǔn)酱鎯Y(jié)構(gòu)采用鏈表的方式存儲串值，稱為串的鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡稱鏈串。在鏈表方式中，每個結(jié)點設(shè)定一個字符域char，用來存放字符；設(shè)定一個指針域next，用來存放所指向的下一個結(jié)點的地址。通常將每個結(jié)點所存儲的字符個數(shù)稱為結(jié)點的大小。如果每個結(jié)點的字符域只存放一個字符，雖然串的運(yùn)算容易進(jìn)行，運(yùn)算速度快，但每個字符都要設(shè)置一個指針域，則會導(dǎo)致存儲空間利用率降低。為了提高存儲空間的利用率，設(shè)置結(jié)點的字符域存放多個字符時，稱為大結(jié)點結(jié)構(gòu)。這種鏈表方式雖然起到了提高存儲空間利用率的作用，但運(yùn)算速度比單字符結(jié)點的鏈表方式要慢。如圖4-2和圖4-3所示為串“TEACHERSTUDENT”的結(jié)點大小分別為1和4的鏈?zhǔn)酱鎯Y(jié)構(gòu)。

在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，串的類型定義如下：串值的鏈?zhǔn)酱鎯Y(jié)構(gòu)對串的某些操作(如連接操作等)有一定不便之處，總體上不如另外兩種存儲結(jié)構(gòu)靈活，其占用存儲量大且操作復(fù)雜。4.1.3串的模式匹配串的模式匹配又稱子串的定位操作，是在主串s中定位子串t的操作。首先，判斷主串s中是否存在子串t，如果存在，則模式匹配成功，并輸出子串t在主串s中首次出現(xiàn)的位置；如果不存在，則模式匹配失敗。串定位操作StrIndex(s，t，pos)的功能就是模式匹配。在串匹配中，一般將主串稱為目標(biāo)串，子串稱為模式串。串的模式匹配應(yīng)用非常廣泛。例如，在文本編輯程序中，經(jīng)常要查找某一特定單詞在文本中出現(xiàn)的位置。顯然，解決此問題的有效算法能極大提高文本編輯程序的響應(yīng)性能。樸素模式匹配算法的基本思想是：從目標(biāo)串s="s0s1s2..sn-1"的第i個字符起與模式串t="t0t1t2…tm-1"進(jìn)行比較。即從j=0起比較s[i+j]與t[j]，若相等，則在主串s中存在以i為起始位置匹配成功的可能性，繼續(xù)向后比較，直至與串t中最后一個字符相等為止；否則改從串s中第i個字符的下一個字符起重新開始下一輪的“匹配”，即將串t向右移動一位(i增1，j退回至0)，重新開始新一輪的匹配，直至串t中的每個字符依次和串s中的一個連續(xù)的字符序列相等，則稱模式匹配成功，此時串t的第1個字符在串s中的位置就是t在s中的位置；否則模式匹配失敗。(1)假設(shè)s="edcedcedbedde"，t="edcedb"，則模式匹配過程如下：第1趟匹配，從串s的第1個字符“e”與串t的第1個字符“e”開始比較(假設(shè)下標(biāo)從0開始)，判斷s[0]和t[0]是否相等，由于兩個字符相等，于是繼續(xù)逐個比較后續(xù)字符s[1]和t[1]是否相等……當(dāng)比較到第6個字符時，s[5]和t[5]對應(yīng)的字符不相等，第1趟匹配過程結(jié)束，第1趟匹配如圖4-4所示。第2趟匹配，將串t向右移動一位，從串s的第2個字符“d”開始，重新與串t的第1個字符進(jìn)行比較，第1次比較時，s和t的對應(yīng)字符不相等，第2趟匹配過程結(jié)束，第2趟匹配如圖4-5所示。第3趟匹配，將串t向右移動一位，從串s的第3個字符“c”開始，重新與串t的第1個字符進(jìn)行比較，第1次比較時，s和t的對應(yīng)字符不相等，第3趟匹配過程結(jié)束，第3趟匹配如圖4-6所示。第4趟匹配，繼續(xù)將串t向右移動一位，從串s的第4個字符“e”開始，重新與串t的第1個字符進(jìn)行比較，在串s中找到一個連續(xù)的字符序列與串t相等，模式匹配成功，第4趟匹配如圖4-7所示。(2)假設(shè)s="abcabcaabca"，t="abbb"，則模式匹配過程如下：第1趟匹配，從串s的第1個字符“a”與串t的第1個字符“a”開始比較，由于兩個字符相等，于是繼續(xù)逐個比較后續(xù)字符，當(dāng)比較到第3個字符時，s和t的對應(yīng)字符不相等，第1趟匹配過程結(jié)束。第2趟匹配，將串t向右移動一位，從串s的第2個字符“b”開始，重新與串t的第1個字符進(jìn)行比較，第1次比較時，s和t的對應(yīng)字符不相等，第2趟匹配過程結(jié)束。按照上述兩趟比較的方法，在接下來的比較過程中均沒有匹配成功，即在s中沒有找到與t相等的連續(xù)字符序列。最后一趟匹配，從串s的第8個字符“a”開始，重新與串t的第1個字符進(jìn)行比較，在串s中仍沒有找到一個與串t相等的連續(xù)字符序列，模式匹配失敗。樸素模式匹配算法具體如下：一般情況下，上述算法的實際執(zhí)行效率與字符t.str[0]在串s中是否頻繁出現(xiàn)有密切關(guān)系。例如，s是一般的英文文稿，t="hello"，假設(shè)s中有5%的字母是“h”，則在上述算法執(zhí)行過程中，對于95%的情況可以只進(jìn)行一次對應(yīng)位的比較就將t向右移一位，時間復(fù)雜度下降為O(s.curlen)，這時算法接近最好情況。然而，在有些情況下，該算法效率卻很低。例如，當(dāng)s="aaaaaaaaaaaaaaaaaaaaaaaab"，t="aaaaab"時，由于模式串t的前六個字符均為“a”，而目標(biāo)串s的前32個字符均為“a”，每次匹配都在模式串的最后一個位置上發(fā)生字符不相等，整個過程需要匹配的次數(shù)為(s.curlen-t.curlen)次，總比較次數(shù)為t.curlen×(s.curlen-t.curlen)。由于通常有t.curlen<<s.curlen，因此最壞情況的時間復(fù)雜度為O(s.curlen×t.curlen)。PART4.2數(shù)

組4.2.1數(shù)組的定義數(shù)組是由n(n>0)個相同類型的元素a1

，a2

，…，an

構(gòu)成的有限序列，且該有限序列存儲在一塊地址連續(xù)的內(nèi)存單元中。由此可見，數(shù)組的定義就是順序存儲結(jié)構(gòu)的線性表。數(shù)組具有如下性質(zhì)：(1)定義數(shù)組就是指明數(shù)組中包含元素的個數(shù)，即指明數(shù)組的長度。換句話說，數(shù)組具有固定長度。(2)數(shù)組中的元素具有相同的數(shù)據(jù)類型。(3)數(shù)組中的每個元素都和唯一的一組下標(biāo)值相關(guān)聯(lián)，即可以通過一組下標(biāo)值唯一確定數(shù)組中的一個元素。(4)數(shù)組是一種隨機(jī)存儲結(jié)構(gòu)，即可隨機(jī)存取數(shù)組中的任意元素，時間復(fù)雜度為O(1)。1.一維數(shù)組長度為n的一維數(shù)組可用元素序列a0，a1，a2

，…，an-2，an-1來描述。數(shù)組在內(nèi)存中占據(jù)連續(xù)的內(nèi)存空間，假設(shè)a0

在內(nèi)存中的地址是LOC(a0

)，且每個元素占用c個單元，那么任意元素ai

的地址為：LOC(ai)=LOC(a0

)+i×c(0≤i≤n-1)2.二維數(shù)組長度為m×n的二維數(shù)組可用以下元素序列來描述：數(shù)組Am×n可以看成是由m個(行)元素a0′，a1′，a2′，…，am-2′，am-1′構(gòu)成的一維數(shù)組：或者是由n個(列)元素a0″，a1″，a2″，…，an-2″，an-1″構(gòu)成的一維數(shù)組：二維數(shù)組在內(nèi)存中有兩種存放順序：按行存儲和按列存儲。所謂按行存儲，就是指先存放第0行元素，接著是第1行元素，依此類推；按列存儲是指先存放第0列元素，接著是第1列元素，直至最后一列。這兩種存放順序在高級程序設(shè)計語言中都適用。假設(shè)a0，0在內(nèi)存中的地址是LOC(a0，0)，且每個元素占用c個單元，那么任意元素ai，j的地址按行存儲時為：LOC(ai，j)=LOC(a0，0)+(i×n+j)×c(0≤i≤m-1，0≤j≤n-1)按列存儲時為：LOC(ai

，j)=LOC(a0，0)+(j×m+i)×c

(0≤i≤m-1，0≤j≤n-1)

從理論上講，數(shù)組可以使用兩種存儲結(jié)構(gòu)，即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。然而，由于數(shù)組結(jié)構(gòu)沒有插入和刪除元素的操作，所以使用順序存儲結(jié)構(gòu)較為適宜。數(shù)組一般不使用鏈?zhǔn)酱鎯Y(jié)構(gòu)。組成數(shù)組結(jié)構(gòu)的元素可以是多維的，但存儲數(shù)據(jù)元素的內(nèi)存單元地址是一維的。因此，在存儲數(shù)組結(jié)構(gòu)之前，需要解決將多維關(guān)系映射到一維關(guān)系的問題。對于一維數(shù)組，按下標(biāo)順序分配即可。對多維數(shù)組分配時，要把其元素映象存儲在一維存儲器中。一般有兩種存儲方式：一種是以行為主序(先行后列)的順序存放，即一行分配完了接著分配下一行；另一種是以列為主序(先列后行)的順序存放，即一列一列地分配。以行為主序的分配規(guī)律是：先排最右的下標(biāo)，從右向左排，最后排最左的下標(biāo)。以列為主序分配的規(guī)律恰好相反：先排最左的下標(biāo)，從左向右排，最后排最右的下標(biāo)。4.2.2數(shù)組的存儲結(jié)構(gòu)與尋址以二維數(shù)組為例，設(shè)有m×n的二維數(shù)組Am×n，兩種順序下的分配結(jié)果如圖4-8所示。對于任意元素，可以按元素的下標(biāo)求其地址。以“以行為主序”的分配為例，設(shè)數(shù)組的基址為LOC(a0，0)，每個數(shù)組元素占據(jù)c個地址單元，由于數(shù)組元素ai，j的前面有i行，每一行的元素個數(shù)為n，因此在第i行中它的前面還有j個數(shù)組元素。在C語言中，數(shù)組中每一維的下界定義為0，那么ai，j的物理地址可用以下公式計算：同理，對于三維數(shù)組Am×n×p，即m×n×p數(shù)組，其數(shù)組元素ai，j，k物理地址的計算公式為：多科學(xué)與工程領(lǐng)域中常用的數(shù)據(jù)結(jié)構(gòu)，利用矩陣的元素進(jìn)行各種運(yùn)算是我們感興趣的問題。在使用高級語言編制程序時，矩陣通常用二維數(shù)組來表示。有些情況下，會有一些特殊矩陣，如三角矩陣、對稱矩陣、對角矩陣和稀疏矩陣等，此類矩陣階數(shù)很高但相同值或零元素很多。為了節(jié)約存儲空間，可以對這類矩陣進(jìn)行壓縮存儲。壓縮存儲是指為多個值相同的元素只分配一個存儲空間。下面介紹幾種特殊矩陣的壓縮存儲。1.特殊矩陣的壓縮存儲(1)對稱矩陣對稱矩陣是指在一個n階方陣中，有ai，j=aj，i，其中0≤i<n，0≤j<n。對稱矩陣關(guān)于主對角線對稱，為了節(jié)省空間，只需存儲上三角或下三角部分即可。例如，只存儲下三角的值，對角線上方的值通過對稱關(guān)系映射過去即可。這樣，原來需要n2個存儲單元，現(xiàn)在只需要n(n+1)/2個存儲單元，節(jié)省了大約一半的存儲空間。4.2.3矩陣的存儲壓縮

(2)三角矩陣三角矩陣是指n階矩陣中的下三角(或上三角)的元素都是0或常數(shù)的矩陣，可以分為上三角矩陣和下三角矩陣。以下兩個矩陣中，c為某個常數(shù)，矩陣A1

為下三角矩陣，主對角線以上均為同一個常數(shù)；矩陣A2

為上三角矩陣，主對角線以下均為同一個常數(shù)。注意：三角矩陣的特點與對稱矩陣相似。下三角矩陣除了存儲下三角中的元素，還要存儲對角線上方的常數(shù)。因為該常數(shù)值相等，所以只存一個