數(shù)據(jù)結(jié)構(gòu)（自考） 課件 第3、4章 棧和隊(duì)列、數(shù)組廣義表和串

全國(guó)高等教育自學(xué)考試指定教材

計(jì)算機(jī)及應(yīng)用專(zhuān)業(yè)（專(zhuān)科段）數(shù)據(jù)結(jié)構(gòu)第三章棧和隊(duì)列學(xué)習(xí)目標(biāo)掌握棧和隊(duì)列的邏輯定義、特點(diǎn)及基本操作，了解它們的邏輯表示方法及使用場(chǎng)掌握棧的兩種存儲(chǔ)方式及各自的特點(diǎn)，掌握兩種方式下基本操作的實(shí)現(xiàn)及復(fù)雜度分析掌握隊(duì)列的兩種存儲(chǔ)方式及各自的特點(diǎn)，掌握兩種方式下基本操作的實(shí)現(xiàn)，重點(diǎn)掌握循環(huán)隊(duì)列的實(shí)現(xiàn)及復(fù)雜度分析了解線性表與棧及隊(duì)列的關(guān)系靈活運(yùn)用棧和隊(duì)列的基本操作，設(shè)計(jì)算法解決與此相關(guān)的實(shí)際問(wèn)題本章主要內(nèi)容棧12棧和隊(duì)列的應(yīng)用3隊(duì)列棧和隊(duì)列是線性表的兩個(gè)經(jīng)典特例，它們都是操作受限的線性表，即操作的位置需要滿(mǎn)足各自的條件因?yàn)檫@些條件的特殊性，使得實(shí)現(xiàn)各自的操作時(shí)過(guò)程簡(jiǎn)捷，效率更高第一節(jié)

棧棧是一種特殊的線性表，它的特殊性體現(xiàn)在操作的位置上。在含n個(gè)元素的線性表中進(jìn)行插入或刪除時(shí)，操作位置可以有n+1個(gè)或n個(gè)當(dāng)將操作位置限定在線性表的同一端時(shí)，得到的數(shù)據(jù)結(jié)構(gòu)就是棧它是一種受限的線性表?xiàng)５亩x及其基本操作定義3.1棧（stack）是限定僅在一端進(jìn)行插入和刪除的線性表能進(jìn)行插入和刪除的這一端稱(chēng)為棧頂，線性表的另一端稱(chēng)為棧底在棧頂插入一個(gè)元素稱(chēng)為入棧（push）、進(jìn)棧或壓棧，從棧頂刪除一個(gè)元素稱(chēng)為出棧（pop）或退棧棧的表示將棧S表示為：S=(a0,a1,…,an-1)

通常指定an-1一端為棧頂，a0一端是棧底棧中元素個(gè)數(shù)n稱(chēng)為棧的長(zhǎng)度，當(dāng)n=0時(shí)，稱(chēng)為空棧棧具有后進(jìn)先出（LIFO，LastInFirstOut）的特性只要棧不空，就允許出棧只要棧不滿(mǎn)，就允許入棧當(dāng)沒(méi)有其他的特殊限制時(shí)，對(duì)于同一個(gè)入棧序列，可能會(huì)得到很多個(gè)合理正確的出棧序列示例例3.1設(shè)有5個(gè)元素1,2,3,4,5依次入棧，以push(x)表示x入棧，pop(x)表示x出棧，試寫(xiě)出得到出棧序列2,1,4,3,5的操作過(guò)程操作過(guò)程為push(1),push(2),pop(2),pop(1),push(3),

push(4),pop(4),pop(3),push(5),pop(5)棧的基本操作示例例3.2依次讀入數(shù)據(jù)元素序列a,b,c,d,e,f,g并入棧。下列選項(xiàng)中，不可能是出棧序列的是A．d,e,c,f,b,g,aB．c,d,b,e,f,a,gC．e,f,d,g,c,b,aD．f,e,g,d,a,c,b答案為D示例例3.3元素a,b,c,d,e依次進(jìn)入初始為空的棧中，在所有可能的出棧序列中，以元素d開(kāi)頭的序列個(gè)數(shù)是A．3 B．4 C．5 D．6

答案為B棧的存儲(chǔ)及其實(shí)現(xiàn)棧有兩種主要的存儲(chǔ)方式，分別是順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)順序存儲(chǔ)方式使用數(shù)組保存棧元素，得到的是順序棧鏈?zhǔn)酱鎯?chǔ)方式使用單鏈表保存棧元素，得到的是鏈?zhǔn)綏ｍ樞驐＜捌鋵?shí)現(xiàn)在順序棧中，棧中的元素保存在一維數(shù)組中，將棧底定義在數(shù)組下標(biāo)為0的位置同時(shí)使用一個(gè)變量標(biāo)記棧頂?shù)奈恢?，即棧頂位置棧頂位置也稱(chēng)為棧頂指針順序棧的定義typedefintELEMType; //以int類(lèi)型為例typedefstruct{ ELEMTypeelement[maxSize]; //maxSize是數(shù)組最大容量 //已定義的常量 inttop; //棧頂位置}SeqStack;棧頂位置top的兩種定義方式本書(shū)采用(a)的方式相應(yīng)操作的實(shí)現(xiàn)入棧入棧時(shí)，新元素放在element[top]處，然后top加1第1個(gè)元素入棧時(shí)放在數(shù)組下標(biāo)為0的位置因?yàn)閿?shù)組空間有限，最大容量是maxSize，所以入棧時(shí)需要判定棧不能是滿(mǎn)的出棧出棧時(shí)，需要先將top值減1，然后將element[top]處的值通過(guò)參數(shù)x返回出棧時(shí)需要判定棧不是空的效率top的值既是保存下一個(gè)入棧元素的位置，也是棧中所含元素個(gè)數(shù)的計(jì)數(shù)器因?yàn)闂５娜霔２僮骷俺鰲２僮鞫荚跅ｍ斶M(jìn)行，所以入棧及出棧時(shí)都不需要移動(dòng)棧中已有的元素，故時(shí)間復(fù)雜度都是O(1)判定棧空及棧滿(mǎn)等操作的時(shí)間復(fù)雜度也是O(1)對(duì)頂棧數(shù)組的兩個(gè)端點(diǎn)分別作為兩個(gè)棧的棧底左側(cè)棧占用數(shù)組0到k的單元，棧頂在k+1位置右側(cè)棧占用數(shù)組m-1到h的單元，棧頂在h-1位置此時(shí)必須滿(mǎn)足k<h，才能保證兩個(gè)棧不會(huì)重疊棧S1入棧時(shí)，棧頂值增大，出棧時(shí)棧頂值減小棧S2剛好相反，入棧時(shí)棧頂值減小，出棧時(shí)棧頂值增大鏈?zhǔn)綏Ｋ^的鏈?zhǔn)綏?，可以看作是一個(gè)僅在表頭位置進(jìn)行操作的單鏈表將頭指針?biāo)傅倪@一端作為棧頂，表尾一端作為棧底入棧操作及出棧操作都可以通過(guò)頭指針完成。所以，在鏈?zhǔn)綏Ｖ?，可以只定義頭指針，尾指針及頭結(jié)點(diǎn)都可以不定義鏈?zhǔn)綏５亩xtypedefintELEMType;typedefstructnode{

ELEMTypedata; structnode*next;}LinkedStackNode;typedefLinkedStackNode*LinkedStack; //鏈?zhǔn)綏３跏蓟瘲３跏紩r(shí)是個(gè)空棧，所以指向棧頂?shù)闹羔樫x值NULL出棧僅當(dāng)棧不為空時(shí)才能執(zhí)行出棧操作，所以pop函數(shù)中要先判斷棧不為空出棧后，將棧頂元素的值通過(guò)x返回給調(diào)用者元素所占用的空間要釋放掉清空棧及判?？杖霔Ｈ霔r(shí)，需要?jiǎng)?chuàng)建一個(gè)新結(jié)點(diǎn)，并將新結(jié)點(diǎn)插入在棧頂位置順序棧與鏈?zhǔn)綏５谋容^實(shí)現(xiàn)順序棧和鏈?zhǔn)綏５乃胁僮鞫贾恍枰?shù)時(shí)間，因此棧的兩種實(shí)現(xiàn)方式的優(yōu)劣僅體現(xiàn)在它們的存儲(chǔ)效率上順序棧需要預(yù)先申請(qǐng)一個(gè)固定長(zhǎng)度的一維數(shù)組，并自始至終全部占用，當(dāng)棧中元素個(gè)數(shù)相對(duì)較少時(shí)，空間浪費(fèi)較大鏈?zhǔn)綏５拈L(zhǎng)度雖然可變，但是每個(gè)元素都需要一個(gè)指針域，這又產(chǎn)生了結(jié)構(gòu)性空間開(kāi)銷(xiāo)棧與函數(shù)調(diào)用棧是保存調(diào)用信息的最佳結(jié)構(gòu)系統(tǒng)內(nèi)部會(huì)開(kāi)辟一個(gè)函數(shù)調(diào)用棧用來(lái)保存函數(shù)在調(diào)用過(guò)程中所需要的一些信息第二節(jié)

隊(duì)列隊(duì)列也是一種特殊的線性表，其特殊性也體現(xiàn)在操作的位置上它具有優(yōu)先的特性，即先來(lái)的先得到服務(wù)這種先來(lái)先服務(wù)的特性稱(chēng)為先進(jìn)先出（FirstInFirstOut），簡(jiǎn)稱(chēng)FIFO隊(duì)列的定義及其基本操作定義3.2隊(duì)列（queue）是只能在表的一端插入、在另一端刪除的線性表能進(jìn)行插入的一端稱(chēng)為隊(duì)列尾，簡(jiǎn)稱(chēng)隊(duì)尾；能進(jìn)行刪除的一端稱(chēng)為隊(duì)列頭，簡(jiǎn)稱(chēng)隊(duì)頭在隊(duì)尾插入元素稱(chēng)為入隊(duì)（enqueue），從隊(duì)頭刪除元素稱(chēng)為出隊(duì)（dequeue）仍然可以沿用線性表的方法來(lái)表示隊(duì)列，隊(duì)列Q可以表示為 Q=(a0,a1,…,an-1)a0稱(chēng)為隊(duì)頭元素，an-1稱(chēng)為隊(duì)尾元素，元素個(gè)數(shù)n稱(chēng)為隊(duì)列長(zhǎng)度當(dāng)給定隊(duì)列的入隊(duì)序列后，僅能得到一個(gè)出隊(duì)序列，而且是與入隊(duì)序列完全相同的序列。這是由隊(duì)列先進(jìn)先出的特性決定的隊(duì)列的定義typedefintELEMType;typedefstruct{ ELEMTypeelement[maxSize]; intfront,rear;}Queue;隊(duì)列的操作定義隊(duì)列的存儲(chǔ)及實(shí)現(xiàn)與線性表及棧一樣，隊(duì)列也有兩種實(shí)現(xiàn)方式，分別得到順序隊(duì)列和鏈?zhǔn)疥?duì)列順序隊(duì)列使用一個(gè)一維數(shù)組A（下標(biāo)從0到n-1）來(lái)保存隊(duì)列，假定隊(duì)列中含有m（m≤n）個(gè)元素選擇A[0]作為隊(duì)頭，那么A[m-1]就是隊(duì)尾當(dāng)出隊(duì)時(shí)，隊(duì)頭A[0]從數(shù)組中刪除，此時(shí)要依次將后面的m-1個(gè)元素均前移一個(gè)位置這種情況下出隊(duì)操作的時(shí)間開(kāi)銷(xiāo)是O(m)存儲(chǔ)結(jié)構(gòu)現(xiàn)在交換隊(duì)頭和隊(duì)尾的位置，選擇A[m-1]是隊(duì)頭，那么A[0]是隊(duì)尾入隊(duì)時(shí)，隊(duì)列中原有的m個(gè)元素均需后移一個(gè)位置，騰出A[0]的位置放置新元素此時(shí)入隊(duì)操作的時(shí)間開(kāi)銷(xiāo)將為O(m)存儲(chǔ)結(jié)構(gòu)可以使用變量front指示隊(duì)頭位置，使用變量rear指示隊(duì)尾位置稱(chēng)front為隊(duì)頭指針，rear為隊(duì)尾指針表示的是數(shù)組下標(biāo)通常，front指示的是隊(duì)頭元素所在的位置，rear指示的是隊(duì)尾元素后面的空位置按照慣例，還是將第一個(gè)入隊(duì)的元素保存在數(shù)組下標(biāo)0的位置入隊(duì)的新元素放置到所有元素的后面經(jīng)過(guò)若干次入隊(duì)、出隊(duì)操作后，含m個(gè)元素的隊(duì)列的示意圖如下所示，其中陰影部分表示隊(duì)列中的元素實(shí)際占用的數(shù)組單元

a0…am-1

↑front

↑rear

當(dāng)再進(jìn)行若干次入隊(duì)操作后，rear會(huì)到達(dá)數(shù)組的末尾，即最后一個(gè)下標(biāo)位置。之后再進(jìn)行入隊(duì)操作時(shí)，導(dǎo)致數(shù)組下標(biāo)越界。但數(shù)組的前半段可能會(huì)因出隊(duì)操作而有空閑的單元

x…y

↑front

↑rear可以重復(fù)利用數(shù)組中前面的空閑單元保存后續(xù)入隊(duì)的元素…v

……u…

↑rear

↑front

示例設(shè)隊(duì)列保存在最大容量為7的數(shù)組A中，從空隊(duì)列開(kāi)始，依次執(zhí)行下列各步操作，分別畫(huà)出得到的隊(duì)列示意圖依次將5,12,9,37入隊(duì)列將5,12依次出隊(duì)列，并依次將25,8入隊(duì)列將16入隊(duì)列，再將9出隊(duì)列，再將7,4入隊(duì)列循環(huán)隊(duì)列順序隊(duì)列都實(shí)現(xiàn)為循環(huán)隊(duì)列在循環(huán)隊(duì)列中，入隊(duì)操作會(huì)涉及到隊(duì)尾rear值的變化，rear=(rear+1)%n，出隊(duì)操作會(huì)涉及到隊(duì)頭front值的變化，front=(front+1)%n，其中n是數(shù)組的大小可以把這個(gè)數(shù)組想象成一個(gè)首尾相接的圓環(huán)，A[n-1]的后面是A[0]“循環(huán)”一詞的含義正是如此空與滿(mǎn)數(shù)組滿(mǎn)時(shí)，rear==front條件rear==front也代表空隊(duì)列解決方法：讓數(shù)組中始終剩余至少一個(gè)空位置。當(dāng)數(shù)組中僅有一個(gè)空位置時(shí)，就認(rèn)為已經(jīng)達(dá)到隊(duì)列的最大長(zhǎng)度了，隊(duì)列已滿(mǎn)初始時(shí)，front=0且rear=0循環(huán)隊(duì)列的定義typedefintELEMType;typedefstruct{

ELEMTypeelement[maxSize]; intfront,rear;}SeqQueue;循環(huán)隊(duì)列初始化構(gòu)造一個(gè)空隊(duì)列，隊(duì)頭和隊(duì)尾指針均賦初值0清空隊(duì)列隊(duì)列置空也得到一個(gè)空隊(duì)列，可以將隊(duì)頭和隊(duì)尾指針均賦值0，和初始化隊(duì)列的結(jié)果一樣也可以讓隊(duì)頭和隊(duì)尾指針的值相等，表示是一個(gè)空隊(duì)列判空與判滿(mǎn)隊(duì)列為空的條件是rear==front隊(duì)列為滿(mǎn)的條件是(rear+1)%n==front求隊(duì)列長(zhǎng)度入隊(duì)與出隊(duì)鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列采用帶頭指針及尾指針的單鏈表作為隊(duì)列的存儲(chǔ)結(jié)構(gòu)單鏈表的頭指針可以當(dāng)作隊(duì)頭指針front，尾指針可以當(dāng)作隊(duì)尾指針rear鏈?zhǔn)疥?duì)列的定義typedefintELEMType;typedefstructnode{ ELEMTypedata; structnode*next;}LinkedQueueNode;typedefstruct{ LinkedQueueNode*front,*rear; //隊(duì)頭、隊(duì)尾指針}LinkedQueue;初始化、清空隊(duì)列判空循環(huán)隊(duì)列中，當(dāng)隊(duì)頭指針和隊(duì)尾指針相等時(shí)，隊(duì)列為空空鏈?zhǔn)疥?duì)列中，隊(duì)頭指針和隊(duì)尾指針都為NULL在內(nèi)存足夠大的情況下，鏈?zhǔn)疥?duì)列通常不會(huì)滿(mǎn)入隊(duì)列出隊(duì)第三節(jié)

棧和隊(duì)列的應(yīng)用——括號(hào)的匹配檢查程序中有很多符號(hào)是成對(duì)出現(xiàn)的，并且它們的出現(xiàn)次序必須正確，可以嵌套但不能交錯(cuò)“左”符號(hào)稱(chēng)為“開(kāi)”符號(hào)，“右”符號(hào)稱(chēng)為“閉”符號(hào)如果表達(dá)式中符號(hào)匹配正確，則表達(dá)式稱(chēng)為平衡的表達(dá)式可以用棧來(lái)實(shí)現(xiàn)檢驗(yàn)符號(hào)平衡性的算法檢驗(yàn)括號(hào)匹配算法的思想從左至右掃描給定的符號(hào)串，忽略所有非括號(hào)的符號(hào)當(dāng)遇到開(kāi)括號(hào)時(shí)，保存它當(dāng)遇到一個(gè)閉括號(hào)時(shí)，看看它是否對(duì)應(yīng)于最近遇到的開(kāi)括號(hào)如果是，則丟掉開(kāi)括號(hào)，并繼續(xù)掃描符號(hào)串如果能掃描完整個(gè)符號(hào)串，且沒(méi)有遇到不匹配的情況，則給定的符號(hào)串代表的表達(dá)式是平衡的可以使用棧來(lái)保存遇到的開(kāi)括號(hào)表達(dá)式不平衡的情況剛掃描到的閉括號(hào)與棧頂開(kāi)括號(hào)不匹配，說(shuō)明括號(hào)有交錯(cuò)已掃描到表達(dá)式尾，但棧不空，說(shuō)明開(kāi)括號(hào)數(shù)多于閉括號(hào)數(shù)掃描到閉括號(hào)時(shí)發(fā)現(xiàn)棧為空，說(shuō)明缺少與此閉括號(hào)對(duì)應(yīng)的開(kāi)括號(hào)檢驗(yàn)括號(hào)平衡性算法的實(shí)現(xiàn)檢驗(yàn)括號(hào)平衡性算法示例檢查表達(dá)式[a+(d+e)]時(shí)棧的變化過(guò)程檢查表達(dá)式{[(])}時(shí)棧的變化過(guò)程表達(dá)式的計(jì)算表達(dá)式的表示形式及計(jì)算次序中綴表達(dá)式： <操作數(shù)><運(yùn)算符><操作數(shù)> c*(a+b)前綴表達(dá)式 <運(yùn)算符><操作數(shù)><操作數(shù)>后綴表達(dá)式 <操作數(shù)><操作數(shù)><運(yùn)算符>將中綴表達(dá)式轉(zhuǎn)變?yōu)楹缶Y表達(dá)式——手算給中綴表達(dá)式中的每個(gè)運(yùn)算符加括號(hào)，這樣的表達(dá)式稱(chēng)為帶完全括號(hào)的中綴表達(dá)式接下來(lái)，將每個(gè)運(yùn)算符右移，緊貼在對(duì)應(yīng)的閉括號(hào)的前面最后，去掉括號(hào)得到后綴表達(dá)式將中綴表達(dá)式轉(zhuǎn)變?yōu)楹缶Y表達(dá)式——算法自左至右掃描中綴表達(dá)式，當(dāng)遇到操作數(shù)時(shí)，直接輸出它。當(dāng)遇到運(yùn)算符時(shí)，不能像操作數(shù)那樣直接輸出，而是保存在棧中。當(dāng)滿(mǎn)足一定的條件時(shí)才輸出棧頂?shù)倪\(yùn)算符當(dāng)讀到表達(dá)式中的一個(gè)運(yùn)算符時(shí)，將它與棧內(nèi)運(yùn)算符進(jìn)行比較。分以下情況考慮若棧內(nèi)運(yùn)算符的優(yōu)先級(jí)高于棧外運(yùn)算符的優(yōu)先級(jí)，則輸出棧內(nèi)運(yùn)算符，繼續(xù)比較棧外運(yùn)算符與棧內(nèi)運(yùn)算符若棧外運(yùn)算符的優(yōu)先級(jí)高于棧內(nèi)運(yùn)算符的優(yōu)先級(jí)，則棧外運(yùn)算符入棧，繼續(xù)讀入表達(dá)式的下一個(gè)符號(hào)若已經(jīng)讀到表達(dá)式末尾，則依次出棧棧中的全部運(yùn)算符部分運(yùn)算符優(yōu)先級(jí)表運(yùn)算符+,-*,/,%()#棧內(nèi)優(yōu)先級(jí)351-0棧外優(yōu)先級(jí)2481-示例將中綴表達(dá)式1+2*3轉(zhuǎn)換為后綴表達(dá)式算法——獲取算符優(yōu)先級(jí)轉(zhuǎn)換算法將中綴表達(dá)式轉(zhuǎn)變?yōu)楹缶Y形式的算法后綴表達(dá)式計(jì)算從左至右掃描后綴表達(dá)式當(dāng)遇到操作數(shù)時(shí)，操作數(shù)進(jìn)棧當(dāng)遇到運(yùn)算符時(shí)，從棧中彈出兩個(gè)操作數(shù)，并進(jìn)行運(yùn)算符所代表的運(yùn)算，結(jié)果仍放到棧中因?yàn)闂５暮筮M(jìn)先出的特性，故從棧中先彈出的操作數(shù)是運(yùn)算符的右操作數(shù)，后彈出的是左操作數(shù)示例計(jì)算后綴表達(dá)式123*+值的過(guò)程計(jì)算表達(dá)式算法計(jì)算后綴表達(dá)式算法打印楊輝三角形楊輝三角形的前8行相鄰兩行的對(duì)應(yīng)關(guān)系打印算法打印楊輝三角形算法ThankYou!全國(guó)高等教育自學(xué)考試指定教材

計(jì)算機(jī)及應(yīng)用專(zhuān)業(yè)（專(zhuān)科段）數(shù)據(jù)結(jié)構(gòu)第四章數(shù)組、廣義表和串學(xué)習(xí)目標(biāo)掌握數(shù)組、廣義表和串的基本概念掌握數(shù)組按行主序及按列主序的存儲(chǔ)方式及二維數(shù)組地址計(jì)算方法掌握特殊矩陣的存儲(chǔ)方式及相應(yīng)的地址計(jì)算方法理解廣義表的概念，掌握廣義表的表示及基本運(yùn)算了解模式匹配概念，掌握串的模式匹配算法本章主要內(nèi)容數(shù)組及廣義表12串第一節(jié)

數(shù)組及廣義表數(shù)組是程序設(shè)計(jì)語(yǔ)言中的重要語(yǔ)法成分，很多語(yǔ)言都定義了數(shù)組類(lèi)型以C語(yǔ)言為例，它定義了一維數(shù)組，數(shù)組元素還可以是數(shù)組，由此得到數(shù)組的數(shù)組，即多維數(shù)組一般地將n（n≥2）維數(shù)組看作是n-1維數(shù)組的數(shù)組從數(shù)據(jù)結(jié)構(gòu)的角度來(lái)理解，一維數(shù)組可以作為線性表的存儲(chǔ)結(jié)構(gòu)，數(shù)組中保存的各元素可以組成一個(gè)線性表多維數(shù)組在系統(tǒng)內(nèi)部都對(duì)應(yīng)一個(gè)隱含的一維數(shù)組，所以多維數(shù)組也是一種線性表例如二維數(shù)組就是以一維數(shù)組為元素的線性表數(shù)組的每個(gè)元素都是形如(index,value)的二元對(duì)，index是數(shù)組下標(biāo)，也稱(chēng)為索引，value是對(duì)應(yīng)于該下標(biāo)的數(shù)值任何兩個(gè)元素的index值都不相同數(shù)組的基本操作Create(); //創(chuàng)建一個(gè)空的數(shù)組Store(index,value);//添加數(shù)據(jù)(index,value)//同時(shí)刪除有相同index值的數(shù)據(jù)對(duì)（若存在）Retrieve(index);//返回下標(biāo)為index的value值示例用數(shù)組表示一個(gè)星期每天的最高溫度hightem={(星期日,30),(星期一,28),(星期二,29),(星期三,32),(星期四,28),(星期五,30),(星期六,31)}數(shù)組上的操作Store(星期一,29);Retrieve(星期五);也可以約定使用0到6來(lái)分別表示星期日到星期六，此時(shí)，數(shù)組hightem可表示為hightem={(0,30),(1,28),(2,29),(3,32),(4,28),(5,30),(6,31)}數(shù)組的順序存儲(chǔ)方式數(shù)組的順序存儲(chǔ)有兩種形式。以二維數(shù)組為例，它的元素可以按行排列，也可以按列排列所謂按行排列，就是先排數(shù)組的第一行，緊隨其后排第二行，依此類(lèi)推所謂按列排列，就是先排數(shù)組的第一列，緊隨其后排第二列，依此類(lèi)推最終都是將數(shù)組中的全部元素排列成一個(gè)序列C語(yǔ)言中多維數(shù)組下標(biāo)的形式：[i1][i2][i3]…[ik]ij（1≤j≤k）為非負(fù)整數(shù)聲明值為整型類(lèi)型的k維數(shù)組DkArrayintDkArray[u1][u2][u3]…[uk];每一維的下標(biāo)取值范圍是：0≤ij<uj（1≤j≤k）數(shù)組最多可容納n=u1

u2

u3

…

uk個(gè)整數(shù)所需要的內(nèi)存空間sizeof(DkArray)=n

sizeof(int)個(gè)字節(jié)若開(kāi)始地址為start，則占用的空間將延伸至start+sizeof(DkArray)-1。intD2Array[3][6];對(duì)應(yīng)一個(gè)3行6列的矩陣通常int占4個(gè)字節(jié)數(shù)組D2Array中含有18個(gè)元素共占用18

4=76個(gè)字節(jié)編號(hào)對(duì)上述的下標(biāo)表格按行自上而下、同一行中自左至右進(jìn)行連續(xù)編號(hào)，從0開(kāi)始按行優(yōu)先把二維數(shù)組中的下標(biāo)映射到0到n-1之間的某個(gè)整數(shù)的方式稱(chēng)為行主序，也稱(chēng)為行主映射按列優(yōu)先，對(duì)下標(biāo)表格從第一列開(kāi)始，從上到下進(jìn)行連續(xù)編號(hào)，直到最后一列映射函數(shù)行主序所對(duì)應(yīng)的映射函數(shù)為 map(i1,i2)=i1

u2+i2

其中u2是數(shù)組的列數(shù)列主序所對(duì)應(yīng)的映射函數(shù)為 map(i1,i2)=i2

u1+i1

其中u1是數(shù)組的行數(shù)示例例4.2二維數(shù)組A[10][5]采用行主序方式存儲(chǔ)，每個(gè)數(shù)據(jù)元素占4個(gè)存儲(chǔ)單元，若A[0][4]的存儲(chǔ)地址是1000，則A[8][4]的存儲(chǔ)地址是多少？解：給定的數(shù)組A是10行5列，需要從A[0][4]的存儲(chǔ)地址反推出數(shù)組A的首地址，然后再計(jì)算A[8][4]的存儲(chǔ)地址行主序所對(duì)應(yīng)的映射函數(shù)為map(i1,i2)=i1

u2+i2本題中：u2=5，map(0,4)=4每個(gè)元素占4個(gè)存儲(chǔ)單元 A[0][0]的存儲(chǔ)地址=1000-4

4=984根據(jù)計(jì)算公式，A[8][4]的映射編號(hào)是 map(8,4)=8

5+4=44存儲(chǔ)地址為984+44

4=1160換一種計(jì)算方法A[0][4]和A[8][4]之間的元素個(gè)數(shù)是 8

5=40A[0][4]與A[8][4]之間的偏移量 =40

4A[8][4]的存儲(chǔ)地址 =A[0][4]的存儲(chǔ)地址+ A[0][4]與A[8][4]之間的偏移量 =1000+160=1160示例三維數(shù)組D3Array[3][2][4]按行主序下標(biāo)排列的形式對(duì)于三維數(shù)組ThrDimenArray[u1][u2][u3]，其行主序的映射函數(shù)應(yīng)為 map(i1,i2,i3)=i1

u2

u3+i2

u3+i3排列規(guī)律所有第一維值為i1的元素都排在第一維值大于i1的元素之前。第一維值相同的元素?cái)?shù)目為u2

u3。因此第一維值小于i1的元素?cái)?shù)目為i1

u2

u3，第一維值等于i1且第二維值小于i2的元素?cái)?shù)目為i2

u3，第一維值等于i1第二維值等于i2且第三維值小于i3的元素?cái)?shù)目為i3矩陣的壓縮存儲(chǔ)對(duì)稱(chēng)矩陣和三角矩陣從節(jié)省存儲(chǔ)空間的角度考慮，對(duì)稱(chēng)矩陣和上（下）三角矩陣，都可以只保存矩陣中約一半的元素，從而可以節(jié)省差不多一半的存儲(chǔ)空間這樣的存儲(chǔ)形式稱(chēng)為壓縮存儲(chǔ)壓縮存儲(chǔ)對(duì)于對(duì)稱(chēng)矩陣，因?yàn)閷?duì)角線以上及以下的元素對(duì)稱(chēng)相等，所以只需要保存其中的一半及對(duì)角線上的元素即可對(duì)于上三角矩陣或下三角矩陣，僅保存上三角部分或下三角部分的元素，另外一半的零元素不再保存若矩陣有n行n列，則這三種形式下需要保存的元素個(gè)數(shù)為n

(n+1)/2三角部分

稀疏矩陣稀疏矩陣該矩陣只有10個(gè)非零元素，每個(gè)非零元素用一個(gè)三元組表示三元組表三元組表應(yīng)是一個(gè)有序序列，通常按行主序次序排列，即先按行的大小排列，同一行的三元組再按列的大小排列對(duì)應(yīng)前例的三元組表i0012234455j1200521405v891-3121624615-7稀疏矩陣的存儲(chǔ)結(jié)構(gòu)typedefstruct{ inti,j; //存儲(chǔ)非零元素的下標(biāo)

ELEMTypev; //存儲(chǔ)非零元素的值}triTerm;typedefstruct{ introws,cols; //矩陣的行數(shù)、列數(shù) intterms; //非零元素個(gè)數(shù)

triTermtri[maxSize]; //三元組表}SparseMatrix;輸入三元組生成三元組表的程序矩陣轉(zhuǎn)置矩陣轉(zhuǎn)置即是行、列互換，i行的元素放置到i列，這也意味著，j列的元素放置在j行。如果矩陣是n

m的，則轉(zhuǎn)置后得到的矩陣是m

n的很容易想到，將三元組表中的每個(gè)三元組項(xiàng)的i與j互換，即可得到轉(zhuǎn)置后矩陣的三元組表但是這樣轉(zhuǎn)換后得到的三元組表不再按行主序排列，不便于后續(xù)操作的實(shí)現(xiàn)所以要實(shí)現(xiàn)的矩陣轉(zhuǎn)置程序，必須得到一個(gè)按行主序排列的三元組表思路可以像readSparseMatrix函數(shù)那樣處理，讀入原矩陣的一個(gè)三元組，插入到目標(biāo)矩陣的三元組表中可以使用一個(gè)臨時(shí)計(jì)數(shù)數(shù)組，記錄原矩陣的每個(gè)三元組在目標(biāo)矩陣的三元組表中的插入位置，以輔助完成轉(zhuǎn)置操作，由此避免了三元組的移動(dòng)，高效率地實(shí)現(xiàn)轉(zhuǎn)置操作不失一般性，設(shè)原矩陣A的行數(shù)是rows，列數(shù)是cols。則轉(zhuǎn)置后矩陣B的行數(shù)是cols，列數(shù)是rows。三元組的個(gè)數(shù)沒(méi)有改變A中處于0列的元素，將是B中處于0行的元素。所以B的三元組表中的最前面的元素，是A中列值為0的元素。接下來(lái)是A中列值為1的元素，依此類(lèi)推，最后是A中列值為cols-1的元素。使用臨時(shí)數(shù)組ColSize來(lái)保存統(tǒng)計(jì)結(jié)果前例中的矩陣，臨時(shí)數(shù)組ColSize內(nèi)容在B的三元組表中，為各行元素預(yù)留位置01234532201201234567890行元素1行元素2行元素4行元素5行元素對(duì)于A的三元組(0,1,8)和(4,1,24)，轉(zhuǎn)置后分別為(1,0,8)和(1,4,24)，它們應(yīng)該保存在上述第二部分，即位置3和位置4中故由ColSize數(shù)組中的元素值，從前向后依次相加，得到RowNext的值012345603577810轉(zhuǎn)置算法數(shù)組的應(yīng)用走迷宮是實(shí)驗(yàn)心理學(xué)中的一個(gè)經(jīng)典問(wèn)題不失一般性，使用一個(gè)m行n列的矩陣maze表示迷宮，讓機(jī)器人R尋找從maze[0][0]（左上角，入口）到maze[m-1][n-1]（右下角，迷宮的唯一出口）間的可行路徑任一時(shí)刻，R在迷宮中的位置用行、列號(hào)[i][j]來(lái)表示，這時(shí)它有4個(gè)方向可以進(jìn)行試探，即從圖上看是上、下、左、右設(shè)下一位置是[g][h]，顯然[g][h]的值與走的方向有關(guān)若從[i][j]向右走一步，則g=i;h=j+1若向上走一步，則g=i-1;h=j當(dāng)R走到迷宮邊緣時(shí)，可以試探的方向不足4個(gè)，需要進(jìn)行邊界的判斷為了避免過(guò)多的邊界條件判斷，可以把原來(lái)表示迷宮的矩陣maze擴(kuò)大一圈，變成m+2行n+2列，并且令表示邊緣的這些矩陣元素全為1編寫(xiě)計(jì)算機(jī)程序求解迷宮問(wèn)題，一般采用一步一探查并加回溯的方法。稱(chēng)R所在的位置為當(dāng)前位置，當(dāng)R走到一個(gè)位置時(shí)，除了進(jìn)入當(dāng)前位置的方向外，可以在其他3個(gè)方向進(jìn)行探查，選擇可行并尚未走過(guò)的方向走一步，所處的新位置變?yōu)楫?dāng)前位置，并再次探查下一個(gè)可行位置；當(dāng)3個(gè)方向都走不通時(shí)，只能沿來(lái)路退到前一個(gè)位置再選擇其他方向，這一步驟稱(chēng)為回溯?；厮莺蟮奈恢糜肿?yōu)楫?dāng)前位置在探查的過(guò)程中，因?yàn)橛谢厮?，所以可能?huì)走到原來(lái)已走過(guò)的位置，為避免重復(fù)并找出確定的可行路徑，需要一個(gè)棧記錄已走過(guò)的每一步的位置及方向，另外還需要設(shè)置一個(gè)與原來(lái)迷宮矩陣同樣大小的標(biāo)志矩陣mark，以對(duì)走過(guò)的位置進(jìn)行標(biāo)記mark矩陣的初值全為0，當(dāng)R走到maze[i][j]位置時(shí)，則置mark[i][j]為1R走迷宮的步驟令R處在迷宮入口，此為當(dāng)前位置在當(dāng)前位置上，依右、下、左、上的順序探查前進(jìn)方向向可以進(jìn)入的方向前進(jìn)，即目標(biāo)位置的maze和mark值全為0。前進(jìn)一步后，目標(biāo)位置為當(dāng)前位置，將mark矩陣的當(dāng)前位置標(biāo)記為1，并且將前一位置的位置值及進(jìn)入當(dāng)前位置的方向入棧重復(fù)步驟②和③若找不到前進(jìn)通路，則從原路后退一步（退棧），改變探測(cè)方向，再重復(fù)步驟②、③，以尋找另一條新的通路重復(fù)步驟②~⑤，直到走出迷宮或宣布迷宮無(wú)通路為止走步時(shí)相鄰兩個(gè)位置之間行、列值的關(guān)系若向右走，則行值不變，列值加1若向下走，則行值加1，列值不變?nèi)粝蜃笞?，則行值不變，列值減1若向上走，則行值減1，列值不變將這4組值定義在move矩陣中列號(hào)0、1、2、3分別對(duì)應(yīng)著方向右,下,左,上行號(hào)0和1分別對(duì)應(yīng)著位置坐標(biāo)i和j走迷宮算法走迷宮算法廣義表廣義表是線性表的推廣，也稱(chēng)為列表是由n(n≥0)個(gè)表元素組成的有限序列 LS=(a0,a1,…,an-1)LS是廣義表的名稱(chēng)n是表的長(zhǎng)度當(dāng)n=0時(shí)稱(chēng)為空表ai(0≤i≤n-1)的類(lèi)型可以不完全一致，既可以是單個(gè)元素（稱(chēng)為原子），也可以是廣義表（稱(chēng)為子表）原子不可再分第一個(gè)元素a0稱(chēng)為L(zhǎng)S的表頭（Head），其余元素組成的表(a1,a2,…,an-1)稱(chēng)為L(zhǎng)S的表尾（Tail）廣義表中括號(hào)的最大嵌套層數(shù)定義為表的深度空表的深度為1，原子的深度為0其他情況，可以遞歸求解廣義表的深度=max{各子表的深度}+1示例A=()A是空表，長(zhǎng)度為0，深度為1B=(())B的長(zhǎng)度為1，深度為2C=(6,2)C的長(zhǎng)度為2，深度為1，兩個(gè)元素都是原子D=('a',(5,3,'x’))D的長(zhǎng)度為2，深度為2，含一個(gè)原子及一個(gè)子表示例E=(C,D,A)E的長(zhǎng)度為3，深度為3，含3個(gè)子表F=(C)F的長(zhǎng)度為1，深度為2，含1個(gè)子表G=(4,G)G的長(zhǎng)度為2，深度為∞，遞歸表各表的表頭和表尾示例Head(B)=()，Tail(B)=()Head(C)=6，Tail(C)=(2)Head(D)='a'，Tail(D)=((5,3,'x'))Head(E)=C，Tail(E)=(D,A)Head(F)=C，Tail(F)=()Head(G)=4，Tail(G)=(G)空表沒(méi)有定義表頭和表尾，所以不能求表A的表頭和表尾表E的表頭是表C第二節(jié)

串串（String）也稱(chēng)為字符串，是由零個(gè)或多個(gè)字符組成的有限序列記為：s="a0a1…an-1"，(n≥0)，其中，s是串名，使用雙引號(hào)括起來(lái)的字符序列是串的值串中的每個(gè)符號(hào)ai(0≤i≤n-1)可以是字母、數(shù)字或其他字符，其在串中的次序定義為該符號(hào)的位置位置從0開(kāi)始串中字符個(gè)數(shù)n稱(chēng)為串的長(zhǎng)度n=0時(shí)稱(chēng)為空串串s中任意個(gè)連續(xù)字符組成的子序列稱(chēng)為串s的子串，相應(yīng)地s稱(chēng)為主串子串在主串中首次出現(xiàn)時(shí)子串首字符對(duì)應(yīng)于主串的符號(hào)位置，定義為子串在主串中的位置設(shè)有串s1="Thisisastring"，s2="is"s1為主串，s2是s1的子串s2在s1中的位置為2空串是任意串的子串任意串是其自身的子串串的模式匹配在主串中尋找子串（第一個(gè)字符）在主串中的位置，稱(chēng)為串的模式匹配子串又稱(chēng)為模式，主串稱(chēng)為目標(biāo)樸素的模式匹配算法（B-F算法）設(shè)主串T="aaaaab"，模式串P="aab"，采用B-F算法的匹配過(guò)程在每趟匹配中，主串與模式串的字符之間的比較次數(shù)有3次，共4趟，所以共進(jìn)行了12次比較主串a(chǎn)aaaab

模式串a(chǎn)ab

第1趟

aab

第2趟

aab

第3趟

aab第4趟樸素的模式匹配算法簡(jiǎn)單，但時(shí)間效率不高設(shè)主串長(zhǎng)度為n，模式串長(zhǎng)度為m。如果每次都是比較到模式串最后一個(gè)字符時(shí)才出現(xiàn)失配，且主串的最后m個(gè)字符與模式串匹配成功，這就出現(xiàn)了最壞情況此時(shí)，每一趟都進(jìn)行了m次比較，共比較了n-m+1趟，故總比較次數(shù)將達(dá)到(n-m+1)

m算法的最壞情況時(shí)間復(fù)雜度為O(n

m)改進(jìn)的模式匹配算法（KMP算法）設(shè)主串T="b0b1b2…bm-1…bn-1"，模式串P="p0p1p2…pm-1"，進(jìn)行第一趟匹配時(shí)，T與P的對(duì)應(yīng)字符進(jìn)行比較主串Tb0b1b2…bm-1…bn-1模式串Pp0p1p2…pm-1匹配過(guò)程中，若某一趟比較時(shí)出現(xiàn)失配，模式串P需要整體右移，那么P右移的位數(shù)應(yīng)該是多少呢模式串P的首字符p0對(duì)應(yīng)于主串的字符bs，且前j(j≥0)對(duì)字符都匹配成功，第j+1對(duì)字符匹配不成功則有bsbs+1bs+2…bs+j-1=p0p1p2…pj-1如果下一趟比較時(shí)模式串P與主串T匹配，也就是P與主串中從bs+1開(kāi)始的子串匹配，則必須滿(mǎn)足p0p1p2…pj-1…pm-1=bs+1bs+2bs+3…bs+j…bs+m若知道p0p1…pj-2

p1p2…pj-1，則立刻可以斷定p0p1…pj-2

bs+1bs+2…bs+j-1，即下一趟必不匹配同樣地，若p0p1…pj-3

p2p3…pj-1，則再下一趟也不匹配，因?yàn)閜0p1…pj-3

bs+2bs+3…bs+j-1如果找到一個(gè)k值，滿(mǎn)足p0p1…pk+1

pj-k-2pj-k-1…pj-1但p0p1…pk=pj-k-1pj-k…pj-1則有p0p1…pk=bs+j-k-1bs+j-k…bs+j-1那么，下一趟可以直接用pk+1與bs+j進(jìn)行比較如何確定k值呢對(duì)于不同的失配位置j，k的取值是不同的，它僅依賴(lài)于模式串P本身前j個(gè)字符的構(gòu)成，而與主串無(wú)關(guān)設(shè)模式串P=p0p1…pm-2pm-1，定義特征向量next