第 3章 棧和隊(duì)列 棧和隊(duì)列是兩種應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu) ，它們都 來(lái)自線性表數(shù)據(jù)結(jié)構(gòu)， 都是 “ 操作受限 ” 的線性表 。 棧在計(jì)算機(jī)的實(shí)現(xiàn)有多種方式： 硬堆棧 ：利用 CPU中的某些寄存器組或類似的硬 件或使用內(nèi)存的特殊區(qū)域來(lái)實(shí)現(xiàn)。這類堆棧容量有限， 但速度很快； 軟堆棧 ：這類堆棧主要在內(nèi)存中實(shí)現(xiàn)。堆棧容量 可以達(dá)到很大。在實(shí)現(xiàn)方式上，又有 動(dòng)態(tài)方式 和 靜態(tài) 方式 兩種。 本章將討論棧和隊(duì)列的基本概念 、 存儲(chǔ)結(jié)構(gòu) 、 基本 操作以及這些操作的具體實(shí)現(xiàn) 。 3.1 棧 3.1.1 棧的基本概念 1 棧的概念 棧 (Stack)： 是限制在表的一端進(jìn)行插入和刪除操 作的線性表。又稱為后進(jìn)先出 LIFO (Last In First Out) 或先進(jìn)后出 FILO (First In Last Out)線性 表。 棧頂 (Top)： 允許進(jìn)行插入、刪除操作的一端，又 稱為表尾。用棧頂指針 (top)來(lái)指示棧頂元素 。 棧底 (Bottom)： 是固定端，又稱為表頭。 空棧 ： 當(dāng)表中沒(méi)有元素時(shí)稱為空棧。 設(shè)棧 S=(a1， a2， a n)，則 a1稱 為棧底元素， an為棧頂元素，如圖 3- 1所示。 棧中元素按 a1， a2， a n的次序 進(jìn)棧，退棧的第一個(gè)元素應(yīng)為棧頂元 素。即棧的修改是按后進(jìn)先出的原則 進(jìn)行的。 圖 3-1 順序 棧示意圖 a1 a2 ai an bottom top 進(jìn)棧（ push） 出棧 (pop) 2 棧的抽象數(shù)據(jù)類型定義 ADT Stack 數(shù)據(jù)對(duì)象： D = ai|ai ElemSet, i=1,2,n ， n0 數(shù)據(jù)關(guān)系： R =|ai-1， ai D, i=2,3,n 基本操作：初始化、進(jìn)棧、出棧、取棧頂元素等 ADT Stack 棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧，和線性表相類似， 用 一維數(shù)組 來(lái) 存儲(chǔ)棧 。根據(jù)數(shù)組是否可以根據(jù)需要增大， 又可分為 靜態(tài)順序棧 和 動(dòng)態(tài)順序棧 。 靜態(tài)順序棧 實(shí)現(xiàn)簡(jiǎn)單，但不能根據(jù)需要增大棧的 存儲(chǔ)空間； 動(dòng)態(tài)順序棧 可以根據(jù)需要增大棧的存儲(chǔ)空間，但 實(shí)現(xiàn)稍為復(fù)雜。 3.1.2 棧的順序存儲(chǔ)表示 采用 動(dòng)態(tài) 一維數(shù)組 來(lái) 存儲(chǔ)棧 。所謂動(dòng)態(tài)，指的是棧 的大小可以根據(jù)需要增加。 用 bottom表示棧底指針，棧底固定不變的；棧頂 則隨著進(jìn)棧和退棧操作而變化。用 top(稱為棧頂指針 ) 指示當(dāng)前棧頂位置。 用 top=bottom作為?？盏臉?biāo)記 ，每次 top指向棧頂 數(shù)組中的下一個(gè)存儲(chǔ)位置 。 結(jié)點(diǎn)進(jìn)棧 ： 首先將數(shù)據(jù)元素保存到棧頂 (top所指 的當(dāng)前位置 )，然后執(zhí)行 top加 1，使 top指向棧頂?shù)南?一個(gè)存儲(chǔ)位置 ; 3.1.2.1 棧的動(dòng)態(tài)順序存儲(chǔ)表示 結(jié)點(diǎn)出棧 ： 首先執(zhí)行 top減 1，使 top指向棧頂元 素的存儲(chǔ)位置，然后將棧頂元素取出 。 圖 3-2是一個(gè)動(dòng)態(tài)棧的變化示意圖 。 圖 3-2 (動(dòng)態(tài) )堆棧變化示意圖 空棧 bottom top 元素 a進(jìn)棧 bottom top a 元素 b， c進(jìn)棧 bottom top a b c 元素 c退棧 bottom top a b bottom top a b d e f 元素 d， e， f進(jìn)棧 基本操作的實(shí)現(xiàn) 1 棧的類型定義 #define STACK_SIZE 100 /* 棧初始向量大小 */ #define STACKINCREMENT 10 /* 存儲(chǔ)空間分配增量 */ #typedef int ElemType ; typedef struct sqstack ElemType *bottom; /* 棧不存在時(shí)值為 NULL */ ElemType *top; /* 棧頂指針 */ int stacksize ; /* 當(dāng)前已分配空間，以元素為單位 */ SqStack ; 2 棧的初始化 Status Init_Stack(void) SqStack S ; S.bottom=(ElemType *)malloc(STACK_SIZE *sizeof(ElemType); if (! S.bottom) return ERROR; S.top=S.bottom ; /* ?？諘r(shí)棧頂和棧底指針相同 */ S. stacksize=STACK_SIZE; return OK ; 3 壓棧 (元素進(jìn)棧 ) Status push(SqStack S , ElemType e) if (S.top-S.bottom=S. stacksize-1) S.bottom=(ElemType *)realloc(S. STACKINCREMENT+STACK_SIZE) *sizeof(ElemType); /* 棧滿，追加存儲(chǔ)空間 */ if (! S.bottom) return ERROR; S.top=S.bottom+S. stacksize ; S. stacksize+=STACKINCREMENT ; *S.top=e; S.top+ ; /* 棧頂指針加 1， e成為新的棧頂 */ return OK; 4 彈棧 (元素 出棧 ) Status pop( SqStack S, ElemType *e ) /*彈出棧頂元素 */ if ( S.top= S.bottom ) return ERROR ; /* 棧空，返回失敗標(biāo)志 */ S.top- ; e=*S. top ; return OK ; 采用 靜態(tài) 一維數(shù)組 來(lái) 存儲(chǔ)棧 。 棧底固定不變的，而棧頂則隨著進(jìn)棧和退棧操作變 化的， 棧底固定不變的；棧頂則隨著進(jìn)棧和退棧操作而 變化，用一個(gè)整型變量 top(稱為棧頂指針 )來(lái)指示當(dāng) 前棧頂位置。 用 top=0表示?？盏某跏紶顟B(tài) ，每次 top指向棧頂 在數(shù)組中的存儲(chǔ)位置 。 結(jié)點(diǎn)進(jìn)棧 ： 首先執(zhí)行 top加 1，使 top指向新的棧 頂位置 ， 然后將數(shù)據(jù)元素保存到棧頂 (top所指的當(dāng)前 位置 )。 3.1.2.2 棧的靜態(tài)順序存儲(chǔ)表示 結(jié)點(diǎn)出棧 ： 首先 把 top指向的棧頂元素取出 ， 然 后執(zhí)行 top減 1，使 top指向新的棧頂位置 。 若棧的數(shù)組有 Maxsize個(gè)元素 ，則 top=Maxsize-1時(shí) 棧滿 。圖 3-3是一個(gè)大小為 5的棧的變化示意圖 。 圖 3-3 靜態(tài) 堆棧變化示意圖 空棧 bottom top Top=1 1個(gè)元素進(jìn)棧 bottom top a Top=3 3個(gè)元素進(jìn)棧 bottom top a b c Top=4 棧滿 bottom top a b e d Top=2 元素 c進(jìn)棧 bottom top a b 基本操作的實(shí)現(xiàn) 1 棧的類型定義 # define MAX_STACK_SIZE 100 /* 棧向量大小 */ # typedef int ElemType ; typedef struct sqstack ElemType stack_arrayMAX_STACK_SIZE ; int top; SqStack ; 2 棧的初始化 SqStack Init_Stack(void) SqStack S ; S.bottom=S.top=0 ; return(S) ; 3 壓棧 (元素進(jìn)棧 ) Status push(SqStack S , ElemType e) /* 使數(shù)據(jù)元素 e進(jìn)棧成為新的棧頂 */ if (S.top=MAX_STACK_SIZE-1) return ERROR; /* 棧滿，返回錯(cuò)誤標(biāo)志 */ S.top+ ; /* 棧頂指針加 1 */ S.stack_arrayS.top=e ; /* e成為新的棧頂 */ return OK; /* 壓棧成功 */ 4 彈棧 (元素 出棧 ) Status pop( SqStack S, ElemType *e ) /*彈出棧頂元素 */ if ( S.top=0 ) return ERROR ; /* 棧空，返回錯(cuò)誤標(biāo)志 */ *e=S.stack_arrayS.top ; S.top- ; return OK ; 當(dāng)棧滿時(shí)做進(jìn)棧運(yùn)算必定產(chǎn)生空間溢出，簡(jiǎn)稱 “ 上 溢 ” 。上溢是一種出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免。 當(dāng)?？諘r(shí)做退棧運(yùn)算也將產(chǎn)生溢出，簡(jiǎn)稱 “ 下溢 ” 。 下溢則可能是正?，F(xiàn)象，因?yàn)闂Ｔ谑褂脮r(shí)，其初態(tài)或終 態(tài)都是空棧，所以下溢常用來(lái)作為控制轉(zhuǎn)移的條件。 1 棧的鏈?zhǔn)奖硎?棧的 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 稱為鏈棧，是運(yùn)算受限的單鏈表。 其插入和刪除操作只能在表頭位置上進(jìn)行。因此，鏈棧 沒(méi)有必要像單鏈表那樣附加頭結(jié)點(diǎn)，棧頂指針 top就是 鏈表的頭指針。圖 3-4是棧的鏈?zhǔn)酱鎯?chǔ)表示形式 。 3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)表示 空棧 top 非空棧 top a4 a3 a1 a2 圖 3-4 鏈 棧存儲(chǔ)形式 鏈棧的 結(jié)點(diǎn)類型說(shuō)明如下： typedef struct Stack_Node ElemType data ; struct Stack_Node *next ; Stack_Node ; 2 鏈棧基本操作的實(shí)現(xiàn) (1) 棧的初始化 Stack_Node *Init_Link_Stack(void) Stack_Node *top ; top=(Stack_Node *)malloc(sizeof(Stack_Node ) ; top-next=NULL ; return(top) ; (2) 壓棧 (元素進(jìn)棧 ) Status push(Stack_Node *top , ElemType e) Stack_Node *p ; p=(Stack_Node *)malloc(sizeof(Stack_Node) ; if (!p) return ERROR; /* 申請(qǐng)新結(jié)點(diǎn)失敗，返回錯(cuò)誤標(biāo)志 */ p-data=e ; p-next=top-next ; top-next=p ; /* 鉤鏈 */ return OK; (3) 彈棧 (元素 出棧 ) Status pop(Stack_Node *top , ElemType *e) /* 將棧頂元素 出 棧 */ Stack_Node *p ; ElemType e ; if (top-next=NULL ) return ERROR ; /* 棧空，返回錯(cuò)誤標(biāo)志 */ p=top-next ; e=p-data ; /* 取棧頂元素 */ top-next=p-next ; /* 修改棧頂指針 */ free(p) ; return OK ; 3.2 棧的應(yīng)用 由于棧具有的 “ 后進(jìn)先出 ” 的固有特性，因此，棧 成為程序設(shè)計(jì)中常用的工具和數(shù)據(jù)結(jié)構(gòu)。以下是幾個(gè)棧 應(yīng)用的例子。 3.2.1 數(shù)制轉(zhuǎn)換 十進(jìn)制整數(shù) N向其它進(jìn)制數(shù) d(二 、 八 、 十六 )的轉(zhuǎn)換 是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題。 轉(zhuǎn)換法則 ： 該轉(zhuǎn)換法則對(duì)應(yīng)于一個(gè)簡(jiǎn)單算法原理 : n=(n div d)*d+n mod d 其中： div為整除運(yùn)算 ,mod為求余運(yùn)算 例如 (1348)10= (2504)8， 其運(yùn)算過(guò)程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 采用靜態(tài)順序棧方式實(shí)現(xiàn) void conversion(int n , int d) /*將 十進(jìn)制整數(shù) N轉(zhuǎn)換為 d(2或 8)進(jìn)制數(shù) */ SqStack S ; int k, *e ; S=Init_Stack(); while (n0) k=n%d ; push(S , k) ; n=n/d ; /* 求出所有的余 數(shù)， 進(jìn)棧 */ while (S.top!=0) /* 棧不空時(shí)出棧，輸出 */ pop(S, e) ; printf(%1d , *e) ; 3.2.2 括號(hào)匹配問(wèn)題 在文字處理軟件或編譯程序設(shè)計(jì)時(shí)，常常需要檢查 一個(gè)字符串或一個(gè)表達(dá)式中的括號(hào)是否相匹配 ? 匹配思想 ： 從左至右掃描一個(gè)字符串 (或表達(dá)式 )，則 每個(gè)右括號(hào)將與最近遇到的那個(gè)左括號(hào)相匹配 。則可以 在從左至右掃描過(guò)程中把所遇到的左括號(hào)存放到堆棧中。 每當(dāng)遇到一個(gè)右括號(hào)時(shí)，就將它與棧頂?shù)淖罄ㄌ?hào) (如果 存在 )相匹配，同時(shí)從棧頂刪除該左括號(hào)。 算法思想 ： 設(shè)置一個(gè)棧，當(dāng)讀到左括號(hào)時(shí)，左括號(hào)進(jìn) 棧。當(dāng)讀到右括號(hào)時(shí)，則從棧中彈出一個(gè)元素，與讀到 的左括號(hào)進(jìn)行匹配，若匹配成功，繼續(xù)讀入；否則匹配 失敗，返回 FLASE。 算法描述 #define TRUE 0 #define FLASE -1 SqStack S ; S=Init_Stack() ; /*堆棧初始化 */ int Match_Brackets( ) char ch , x ; scanf(%c , while (asc(ch)!=13) if (ch=()|(ch=) push(S , ch) ; else if (ch=) x=pop(S) ; if (x!=) printf(括號(hào)不匹配” ) ; return FLASE ; else if (ch=) x=pop(S) ; if (x!=() printf(括號(hào)不匹配” ) ; return FLASE ; if (S.top!=0) printf(括號(hào)數(shù)量不匹配！” ) ; return FLASE ; else return TRUE ; 3.2.2 棧與遞歸調(diào)用的實(shí)現(xiàn) 棧的另一個(gè)重要應(yīng)用是在程序設(shè)計(jì)語(yǔ)言中實(shí)現(xiàn)遞歸 調(diào)用。 遞歸調(diào)用 ： 一個(gè)函數(shù) (或過(guò)程 )直接或間接地調(diào)用 自己本身，簡(jiǎn)稱 遞歸 (Recursive)。 遞歸 是程序設(shè)計(jì)中的一個(gè)強(qiáng)有力的工具。因?yàn)檫f歸 函數(shù)結(jié)構(gòu)清晰，程序易讀，正確性很容易得到證明。 為了使遞歸調(diào)用不至于無(wú)終止地進(jìn)行下去，實(shí)際上 有效的遞歸調(diào)用函數(shù) (或過(guò)程 )應(yīng)包括兩部分： 遞推規(guī)則 (方法 )， 終止條件 。 例如：求 n! Fact(n)= 1 當(dāng) n=0時(shí) 終止條件 n*fact(n-1) 當(dāng) n0時(shí) 遞推規(guī)則 為保證遞歸調(diào)用正確執(zhí)行，系統(tǒng)設(shè)立一個(gè) “ 遞歸工 作棧 ” ，作為整個(gè)遞歸調(diào)用過(guò)程期間使用的數(shù)據(jù)存儲(chǔ)區(qū)。 每一層遞歸包含的信息如： 參數(shù) 、 局部變量 、 上一 層的返回地址構(gòu)成 一個(gè)“ 工作記錄 ” 。每進(jìn)入一層遞 歸，就產(chǎn)生一個(gè)新的工作記錄壓入棧頂；每退出一層遞 歸，就從棧頂彈出一個(gè)工作記錄。 從被調(diào)函數(shù)返回調(diào)用函數(shù)的一般步驟： (1) 若棧為空，則執(zhí)行正常返回。 從棧頂彈出一個(gè)工作記錄。 將“工作記錄”中的參數(shù)值、局部變量值賦給相 應(yīng)的變量；讀取返回地址。 將函數(shù)值賦給相應(yīng)的變量。 (5) 轉(zhuǎn)移到返回地址。 1 隊(duì)列的基本概念 隊(duì)列 (Queue)：也是運(yùn)算受限的線性表。是一種 先 進(jìn)先出 (First In First Out ，簡(jiǎn)稱 FIFO)的線性表。只允 許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。 隊(duì)首 (front) ：允許進(jìn)行刪除的一端稱為隊(duì)首。 隊(duì)尾 (rear) ：允許進(jìn)行插入的一端稱為隊(duì)尾。 例如：排隊(duì)購(gòu)物。操作系統(tǒng)中的作業(yè)排隊(duì)。先進(jìn)入 隊(duì)列的成員總是先離開(kāi)隊(duì)列。 3.3 隊(duì) 列 3.3.1 隊(duì)列及其基本概念 隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列。在空隊(duì)列中依次 加入元素 a1, a2, , a n之后， a1是隊(duì)首元素， an是隊(duì)尾元 素。顯然退出隊(duì)列的次序也只能是 a1, a2, , a n ，即隊(duì) 列的修改是依 先進(jìn)先出 的原則進(jìn)行的，如圖 3-5所示。 a1 , a2 , , a n 出隊(duì) 入隊(duì) 隊(duì)尾 隊(duì)首 圖 3-5 隊(duì)列示意圖 2 隊(duì)列的抽象數(shù)據(jù)類型定義 ADT Queue 數(shù)據(jù)對(duì)象： D = ai|ai ElemSet, i=1, 2, , n, n = 0 數(shù)據(jù)關(guān)系： R = | ai-1, ai D, i=2,3,n 約定 a1端為隊(duì)首， an端為隊(duì)尾。 基本操作： Create()：創(chuàng)建一個(gè)空隊(duì)列 ； EmptyQue()：若隊(duì)列為空 ， 則返回 true ， 否則返 回 flase ； InsertQue(x) ：向隊(duì)尾插入元素 x； DeleteQue(x) ：刪除隊(duì)首元素 x； ADT Queue 3.3.2 隊(duì)列的順序表示和實(shí)現(xiàn) 利用 一組連續(xù)的存儲(chǔ)單元 (一維數(shù)組 ) 依次存放從隊(duì) 首到隊(duì)尾的各個(gè)元素，稱為 順序隊(duì)列 。 對(duì)于隊(duì)列，和順序棧相類似，也有動(dòng)態(tài)和靜態(tài)之分。 本部分介紹的是 靜態(tài)順序隊(duì)列 ，其類型定義如下： #define MAX_QUEUE_SIZE 100 typedef struct queue ElemType Queue_arrayMAX_QUEUE_SIZE ; int front ; int rear ; SqQueue; 3.3.2.1 隊(duì)列的順序 存儲(chǔ)結(jié)構(gòu) 設(shè)立一個(gè) 隊(duì)首指針 front ，一個(gè) 隊(duì)尾指針 rear ，分 別指向隊(duì)首和隊(duì)尾元素 。 初始化 ： front=rear=0。 入隊(duì) ： 將新元素插入 rear所指的位置，然后 rear加 1。 出隊(duì) ： 刪去 front所指的元素，然后加 1并返回被刪 元素。 隊(duì)列為空 ： front=rear。 隊(duì)滿 ： rear=MAX_QUEUE_SIZE-1或 front=rear。 在非空隊(duì)列里，隊(duì)首指針始終指向隊(duì)頭元素，而隊(duì) 尾指針始終指向隊(duì)尾元素的下一位置。 順序隊(duì)列中存在 “ 假溢出 ” 現(xiàn)象。因?yàn)樵谌腙?duì)和出 隊(duì)操作中，頭、尾指針只增加不減小，致使被刪除元素 的空間永遠(yuǎn)無(wú)法重新利用。因此，盡管隊(duì)列中實(shí)際元素 個(gè)數(shù)可能遠(yuǎn)遠(yuǎn)小于數(shù)組大小，但可能由于尾指針?biāo)瘸?向量空間的上界而不能做入隊(duì)操作。該現(xiàn)象稱為 假溢出 。 如圖 3-6所示是數(shù)組大小為 5的順序隊(duì)列中隊(duì)首 、 隊(duì)尾指 針和隊(duì)列中元素的變化情況。 (a) 空隊(duì)列 Q.front Q.rear (b) 入隊(duì) 3個(gè)元素 a3 a2 a1 Q.front Q.rear (c) 出隊(duì) 3個(gè)元素 Q.front Q.rear (d) 入隊(duì) 2個(gè)元素 a5 a4 Q.front Q.rear 圖 3-6 隊(duì)列示意圖 3.3.2.2 循環(huán)隊(duì)列 為充分利用向量空間，克服上述“ 假溢出 ”現(xiàn)象的 方法是：將為隊(duì)列分配的 向量空間看成為一個(gè)首尾相接 的圓環(huán) ，并稱這種隊(duì)列為 循環(huán)隊(duì)列 (Circular Queue)。 在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，隊(duì)首、隊(duì)尾 指針仍要加 1，朝前移動(dòng)。只不過(guò)當(dāng)隊(duì)首、隊(duì)尾指針指 向向量上界 (MAX_QUEUE_SIZE-1)時(shí)，其加 1操作的 結(jié)果是指向向量的下界 0。 這種循環(huán)意義下的加 1操作可以描述為： if (i+1=MAX_QUEUE_SIZE) i=0; else i+ ; 其中： i代表隊(duì)首指針 (front)或隊(duì)尾指針 (rear) 用模運(yùn)算可簡(jiǎn)化為： i=(i+1)%MAX_QUEUE_SIZE ; 顯然，為循環(huán)隊(duì)列所分配的空間可以被充分利用， 除非向量空間真的被隊(duì)列元素全部占用，否則不會(huì)上溢 。因此，真正實(shí)用的順序隊(duì)列是循環(huán)隊(duì)列。 例：設(shè) 有循環(huán)隊(duì)列 QU0， 5，其初始狀態(tài)是 front=rear=0，各種操作后隊(duì)列的頭、尾指針的狀態(tài)變 化情況如下圖 3-7所示。 1 2 3 4 5 0 (a) 空隊(duì)列 front rear 1 2 3 4 5 0 (b) d, e, b, g入 隊(duì) front d e b g rear 1 2 3 4 5 0 (c) d, e出隊(duì) b g front rear 入隊(duì)時(shí)尾指針向前追趕頭指針，出隊(duì)時(shí)頭指針向前 追趕尾指針，故隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等。因此， 無(wú)法通過(guò) front=rear來(lái)判斷隊(duì)列 “ 空 ” 還是 “ 滿 ” 。解 決此問(wèn)題的方法是：約定入隊(duì)前，測(cè)試尾指針在循環(huán)意 義下加 1后是否等于頭指針，若相等則認(rèn)為隊(duì)滿 。即 ： rear所指的單元始終為空。 1 2 3 4 5 0 (d) i, j, k入 隊(duì) b g front i j k rear 1 2 3 4 5 0 (e) b, g出隊(duì) i j k rear front 1 2 3 4 5 0 (f) r, p, s, t入隊(duì) i j k front r p rear 圖 3-7 循環(huán)隊(duì)列操作及指針變化情況 循環(huán)隊(duì)列為空 ： front=rear 。 循環(huán)隊(duì)列滿 ： (rear+1)%MAX_QUEUE_SIZE =front。 循環(huán)隊(duì)列的基本操作 1 循環(huán)隊(duì)列的初始化 SqQueue Init_CirQueue(void) SqQueue Q ; Q.front=Q.rear=0; return(Q) ; 2 入隊(duì)操作 Status Insert_CirQueue(SqQueue Q , ElemType e) /* 將數(shù)據(jù)元素 e插入到循環(huán)隊(duì)列 Q的隊(duì)尾 */ if (Q.rear+1)%MAX_QUEUE_SIZE= Q.front) return ERROR; /* 隊(duì)滿，返回錯(cuò)誤標(biāo)志 */ Q.Queue_arrayQ.rear=e ; /* 元素 e入隊(duì) */ Q.rear=(Q.rear+1)% MAX_QUEUE_SIZE ; /* 隊(duì)尾指針向前移動(dòng) */ return OK; /* 入隊(duì)成功 */ 3 出隊(duì)操作 Status Delete_CirQueue(SqQueue Q, ElemType *x ) /* 將循環(huán)隊(duì)列 Q的隊(duì)首元素出隊(duì) */ if (Q.front+1= Q.rear) return ERROR ; /* 隊(duì)空，返回錯(cuò)誤標(biāo)志 */ *x=Q.Queue_arrayQ.front ; /* 取隊(duì)首元素 */ Q.front=(Q.front+1)% MAX_QUEUE_SIZE ; /* 隊(duì)首指針向前移動(dòng) */ return OK ; 1 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列，它是限制僅 在表頭進(jìn)行刪除操作和表尾進(jìn)行插入操作的單鏈表。 需要兩類不同的結(jié)點(diǎn) ： 數(shù)據(jù)元素 結(jié)點(diǎn) ， 隊(duì)列的 隊(duì)首 指針和隊(duì)尾指針 的結(jié)點(diǎn) ，如圖 3-8所示。 3.3.3 隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 數(shù)據(jù)元素結(jié)點(diǎn)類型定義： typedef struct Qnode ElemType data ; struct Qnode *next ; QNode ; 數(shù)據(jù)元素結(jié)點(diǎn) data 指針結(jié)點(diǎn) front rear 圖 3-8 鏈隊(duì)列結(jié)點(diǎn)示意圖 指針結(jié)點(diǎn)類型定義： typedef struct link_queue QNode *front , *rear ; Link_Queue ; 2 鏈隊(duì)運(yùn)算及指針變化 鏈隊(duì)的操作實(shí)際上是單鏈表的操作，只不過(guò)是刪 除在表頭進(jìn)行，插入在表尾進(jìn)行。插入、刪除時(shí)分別修 改不同的指針。鏈隊(duì)運(yùn)算及指針變化如圖 3-9所示。 圖 3-9 隊(duì)列操作及指針變化 (a) 空隊(duì)列 front rear (b) x入隊(duì) x front rear (c) y再入隊(duì) y front rear x (d) x出隊(duì) y x front rear 3 鏈隊(duì)列的基本操作 鏈隊(duì)列的初始化 LinkQueue *Init_LinkQueue(void) LinkQueue *Q ; QNode *p ; p=(QNode *)malloc(sizeof(QNode) ; /* 開(kāi)辟頭結(jié)點(diǎn) */ p-next=NULL ; Q=(LinkQueue *)malloc(sizeof(LinkQueue) ; /* 開(kāi)辟鏈隊(duì)的指針結(jié)點(diǎn) */ Q.front=Q.rear=p ; return(Q) ; 鏈隊(duì)列的 入隊(duì)操作 在已知隊(duì)列的隊(duì)尾插入一個(gè)元素 e ，即 修改隊(duì)尾 指 針 (Q.rear)。 Status Insert_CirQueue(LinkQueue *Q , ElemType e) /* 將數(shù)據(jù)元素 e插入到鏈隊(duì)列 Q的隊(duì)尾 */ p=(QNode *)malloc(sizeof(QNode) ; if (!p) return ERROR; /* 申請(qǐng)新結(jié)點(diǎn)失敗，返回錯(cuò)誤標(biāo)志 */ p-data=e ; p-next=NULL ; /* 形成新結(jié)點(diǎn) */ Q.rear-next=p ; Q.rear=p ; /* 新結(jié)點(diǎn)插入到隊(duì)尾 */ return OK; 鏈隊(duì)列的出隊(duì)操作 Status Delete_LinkQueue(LinkQueue *Q, ElemType *x) QNode *p ; if (Q.front=Q.rear) return ERROR ; /* 隊(duì)空 */ p=Q.front-next ; /* 取隊(duì)首結(jié)點(diǎn) */ *x=p-data ; Q.front-next=p-next ; /* 修改隊(duì)首指針 */ if (p=Q.rear) Q.rear=Q.front ; /* 當(dāng)隊(duì)列只有一個(gè)結(jié)點(diǎn)時(shí)應(yīng)防止丟失隊(duì)尾指針 */ free(p) ; return OK ; 鏈隊(duì)列的撤消 void Destroy_LinkQueue(LinkQueue *Q ) /* 將鏈隊(duì)列 Q的隊(duì)首元素出隊(duì) */ while (Q.front!=NULL) Q.rear=Q.front-next; /* 令尾指針指向隊(duì)列的第一個(gè)結(jié)點(diǎn) */ free(Q.front); /* 每次釋放一個(gè)結(jié)點(diǎn) */ /* 第一次是頭結(jié)點(diǎn)，以后是元素結(jié)點(diǎn) */ Q.ront=Q.rear; 習(xí) 題 三 1 設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)?a, b, c。問(wèn)經(jīng)過(guò)棧 操作后可以得到哪些輸出序列？ 2 循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么 ?如何判斷它的空和滿 ? 3 設(shè)有一個(gè)靜態(tài)順序隊(duì)列，向量大小為 MAX，判斷 隊(duì)列為空的條件是什么？隊(duì)列滿的條件是什么？ 4 設(shè)有一個(gè)靜態(tài)循環(huán)隊(duì)列，向量大小為 MAX，判斷 隊(duì)列為空的條件是什么？隊(duì)列滿的條件是什么？ 5 利用棧的基本操作， 寫一個(gè)返回棧 S中結(jié)點(diǎn)個(gè)數(shù)的 算法 int StackSize(SeqStack S) ，并說(shuō)明 S為何不作為指 針參數(shù) 的算法 ? 6 一個(gè)雙向棧 S是在同一向量空間內(nèi)實(shí)現(xiàn)的兩個(gè)棧 ， 它們的棧底分別設(shè)在向量空間的兩端。試為此雙向棧設(shè) 計(jì)初始化 InitStack(S) ，入棧 Push(S,i,x)，出棧 Pop(S,i,x) 算法 ，其中 i為 0或 1 ，用以表示棧號(hào)。 7 設(shè) Q0,6是一個(gè)靜態(tài)順序隊(duì)列 ，初始狀態(tài)為 front=rear=0，請(qǐng)畫(huà)出做完下列操作后隊(duì)列的頭尾指針 的狀態(tài)變化情況，若不能入對(duì)，請(qǐng)指出其元素，并說(shuō)明 理由。 a, b, c, d入隊(duì) a, b, c出隊(duì) i , j , k , l , m入隊(duì) d, i出隊(duì) n, o, p, q, r入隊(duì) 8 假設(shè) Q0,5是一個(gè)循環(huán)隊(duì)列 ，初始狀態(tài)為 front=rear=0，請(qǐng)畫(huà)出做完下列操作后隊(duì)列的頭尾指針 的狀態(tài)變化情況，若不能入對(duì)，請(qǐng)指出其元素，并說(shuō)明 理由。 d, e, b, g, h入隊(duì) d, e出隊(duì) i , j , k , l , m入隊(duì) b出隊(duì) n, o, p, q, r入隊(duì) 第 4章 串 在非數(shù)值處理、事務(wù)處理等問(wèn)題常涉及到一系列 的字符操作。計(jì)算機(jī)的硬件結(jié)構(gòu)主要是反映數(shù)值計(jì)算的 要求，因此，字符串的處理比具體數(shù)值處理復(fù)雜。本章 討論串的存儲(chǔ)結(jié)構(gòu)及幾種基本的處理。 4.1 串類型的定義 4.1.1 串的基本概念 串 (字符串 )：是零個(gè)或多個(gè)字符組成的有限序列。 記作： S=a1a2a3 ，其中 S是串名， ai(1 i n)是單 個(gè)， 可以是字母、數(shù)字或其它字符。 串值 ：雙引號(hào)括起來(lái)的字符序列是串值。 串長(zhǎng) ：串中所包含的字符個(gè)數(shù)稱為該串的長(zhǎng)度。 空串 (空的字符串 )：長(zhǎng)度為零的串稱為空串，它不 包含任何字符。 空格串 (空白串 )：構(gòu)成串的所有字符都是空格的串 稱為空白串。 注意 ：空串和空白串的不同，例如 “ ” 和 “” 分別表 示長(zhǎng)度為 1的空白串和長(zhǎng)度為 0的空串。 子串 (substring)：串中任意個(gè)連續(xù)字符組成的子序 列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。 子串的序號(hào) ：將子串在主串中首次出現(xiàn)時(shí)的該子串 的首字符對(duì)應(yīng)在主串中的序號(hào)，稱為子串在主串中的序 號(hào)（或位置）。 例如， 設(shè)有串 A和 B分別是： A=這是字符串”， B=是” 則 B是 A的子串， A為主串。 B在 A中出現(xiàn)了兩次，其中 首次出現(xiàn)所對(duì)應(yīng)的主串位置是 3。因此，稱 B在 A中的序 號(hào)為 3 。 特別地，空串是任意串的子串，任意串是其自身的 子串。 串相等 ：如果兩個(gè)串的串值相等 (相同 )，稱這兩個(gè) 串相等。換言之，只有當(dāng)兩個(gè)串的長(zhǎng)度相等，且各個(gè)對(duì) 應(yīng)位置的字符都相同時(shí)才相等。 通常在程序中使用的串可分為兩種：串變量和串常 量。 串常量和整常數(shù)、實(shí)常數(shù)一樣，在程序中只能被引 用但不能不能改變其值，即只能讀不能寫。通常串常量 是由直接量來(lái)表示的，例如語(yǔ)句錯(cuò)誤 (溢出 ” )中 “ 溢 出 ” 是直接量。 串變量和其它類型的變量一樣，其值是可以改變。 4.1.2 串的抽象數(shù)據(jù)類型定義 ADT String 數(shù)據(jù)對(duì)象： D = ai|ai CharacterSet, i=1,2,n, n 0 數(shù)據(jù)關(guān)系： R = | ai-1, ai D, i=2,3,n 基本操作： StrAssign(t , chars) 初始條件： chars是一個(gè)字符串常量。 操作結(jié)果：生成一個(gè)值為 chars的串 t 。 StrConcat(s, t) 初始條件：串 s, t 已存在。 操作結(jié)果：將串 t聯(lián)結(jié)到串 s后形成新串存放到 s中。 StrLength(t) 初始條件：字符串 t已存在。 操作結(jié)果：返回串 t中的元素個(gè)數(shù)，稱為串長(zhǎng)。 SubString (s, pos, len, sub) 初始條件：串 s, 已存在 , 1 pos StrLength(s)且 0 len StrLength(s) pos+1。 操作結(jié)果：用 sub返回串 s的第 pos個(gè)字符起長(zhǎng)度為 len 的子串。 ADT String 4.2 串的存儲(chǔ)表示和實(shí)現(xiàn) 串是一種特殊的線性表，其存儲(chǔ)表示和線性表類似， 但又不完全相同。串的存儲(chǔ)方式取決于將要對(duì)串所進(jìn)行 的操作。串在計(jì)算機(jī)中有 3種表示方式： 定長(zhǎng)順序存儲(chǔ)表示 ：將串定義成字符數(shù)組，利用 串名可以直接訪問(wèn)串值。用這種表示方式，串的存 儲(chǔ)空間在編譯時(shí)確定，其大小不能改變。 堆分配存儲(chǔ)方式 ：仍然用一組地址連續(xù)的存儲(chǔ)單 元來(lái)依次存儲(chǔ)串中的字符序列，但串的存儲(chǔ)空間是 在程序運(yùn)行時(shí)根據(jù)串的實(shí)際長(zhǎng)度動(dòng)態(tài)分配的。 塊鏈存儲(chǔ)方式 ：是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。 4.2.1 串的定長(zhǎng)順序存儲(chǔ)表示 這種存儲(chǔ)結(jié)構(gòu)又稱為串的順序存儲(chǔ)結(jié)構(gòu)。是用一 組連續(xù)的存儲(chǔ)單元來(lái)存放串中的字符序列。所謂定長(zhǎng)順 序存儲(chǔ)結(jié)構(gòu)，是直接使用定長(zhǎng)的字符數(shù)組來(lái)定義，數(shù)組 的上界預(yù)先確定。 定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)定義為： #define MAX_STRLEN 256 typedef struct char strMAX_STRLEN ; int length; StringType ; 1 串的聯(lián)結(jié)操作 Status StrConcat ( StringType s, StringType t) /* 將串 t聯(lián)結(jié)到串 s之后，結(jié)果仍然保存在 s中 */ int i, j ; if (s.length+t.length)MAX_STRLEN) Return ERROR ; /* 聯(lián)結(jié)后長(zhǎng)度超出范圍 */ for (i=0 ; it.length ; i+) s.strs.length+i=t.stri ; /* 串 t聯(lián)結(jié)到串 s之后 */ s.length=s.length+t.length ; /* 修改聯(lián)結(jié)后的串長(zhǎng)度 */ return OK ; 2 求子串操作 Status SubString (StringType s, int pos, int len, StringType *sub) int k, j ; if (poss.length|len(s.length-pos+1) return ERROR ; /* 參數(shù)非法 */ sub-length=len-pos+1 ; /* 求得子串長(zhǎng)度 */ for (j=0, k=pos ; kstrj=s.stri ; /* 逐個(gè)字符復(fù)制求得子串 */ return OK ; 4.2.2 串的堆分配存儲(chǔ)表示 實(shí)現(xiàn)方法：系統(tǒng)提供一個(gè)空間足夠大且地址連續(xù)的 存儲(chǔ)空間 (稱為 “ 堆 ” )供串使用。可使用 C語(yǔ)言的動(dòng)態(tài) 存儲(chǔ)分配函數(shù) malloc()和 free()來(lái) 管理。 特點(diǎn)是：仍然以一組地址連續(xù)的存儲(chǔ)空間來(lái)存儲(chǔ)字 符串值，但其所需的存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài) 分配，故是動(dòng)態(tài)的，變長(zhǎng)的。 串的堆式存儲(chǔ)結(jié)構(gòu)的類型定義 typedef struct char *ch; /* 若非空，按長(zhǎng)度分配，否則為 NULL */ int length; /* 串的長(zhǎng)度 */ HString ; 1 串的聯(lián)結(jié)操作 Status Hstring *StrConcat(HString *T, HString *s1, HString *s2) /* 用 T返回由 s1和 s2聯(lián)結(jié)而成的串 */ int k, j , t_len ; if (T.ch) free(T); /* 釋放舊空間 */ t_len=s1-length+s2-length ; if (p=(char *)malloc(sizeof(char)*t_len)=NULL) printf(系統(tǒng)空間不夠，申請(qǐng)空間失敗 ！ n) ; return ERROR ; for (j=0 ; jlength; j+) T-chj=s1-chj ; /* 將串 s復(fù)制到串 T中 */ for (k=s1-length, j=0 ; jlength; k+, j+) T-chj=s1-chj ; /* 將串 s2復(fù)制到串 T中 */ free(s1-ch) ; free(s2-ch) ; return OK ; 4.2.3 串的鏈?zhǔn)酱鎯?chǔ)表示 串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和線性表的串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類 似，采用單鏈表來(lái)存儲(chǔ)串， 結(jié)點(diǎn)的構(gòu)成是： data域：存放字符， data域可存放的字符個(gè)數(shù)稱為 結(jié)點(diǎn)的大??； next域：存放指向下一結(jié)點(diǎn)的指針。 若每個(gè)結(jié)點(diǎn)僅存放一個(gè)字符，則結(jié)點(diǎn)的指針域就非 常多，造成系統(tǒng)空間浪費(fèi)，為節(jié)省存儲(chǔ)空間，考慮串結(jié) 構(gòu)的特殊性，使每個(gè)結(jié)點(diǎn)存放若干個(gè)字符，這種結(jié)構(gòu)稱 為塊鏈結(jié)構(gòu)。如 圖 4-1是塊大小為 3的串的塊鏈?zhǔn)酱鎯?chǔ)結(jié) 構(gòu)示意圖。 串的塊鏈?zhǔn)酱鎯?chǔ)的類型定義包括： 塊結(jié)點(diǎn)的類型定義 #define BLOCK_SIZE 4 typedef struct Blstrtype char dataBLOCK_SIZE ; struct Blstrtype *next; BNODE ; a b c e p c g head 圖 4-1 串的塊鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖 (2) 塊鏈串的類型定義 typedef struct BNODE head; /* 頭指針 */ int Strlen ; /* 當(dāng)前長(zhǎng)度 */ Blstring ; 在這種存儲(chǔ)結(jié)構(gòu)下，結(jié)點(diǎn)的分配總是完整的結(jié)點(diǎn)為 單位，因此，為使一個(gè)串能存放在整數(shù)個(gè)結(jié)點(diǎn)中，在串 的末尾填上不屬于串值的特殊字符，以表示串的終結(jié)。 當(dāng)一個(gè)塊 (結(jié)點(diǎn) )內(nèi)存放多個(gè)字符時(shí)，往往會(huì)使操作 過(guò)程變得較為復(fù)雜，如在串中插入或刪除字符操作時(shí)通 常需要在塊間移動(dòng)字符。 4.3 串的模式匹配算法 模式匹配 (模范匹配 )： 子串在主串中的定位稱為模 式匹配或串匹配 (字符串匹配 ) 。模式匹配成功是指在 主串 S中能夠找到模式串 T，否則，稱模式串 T在主串 S 中不存在。 模式匹配的應(yīng)用在非常廣泛。例如，在文本編輯 程序中，我們經(jīng)常要查找某一特定單詞在文本中出現(xiàn)的 位置。顯然，解此問(wèn)題的有效算法能極大地提高文本編 輯程序的響應(yīng)性能。 模式匹配是一個(gè)較為復(fù)雜的串操作過(guò)程。迄今為止， 人們對(duì)串的模式匹配提出了許多思想和效率各不相同的 計(jì)算機(jī)算法。介紹兩種主要的模式匹配算法。 4.3.1 Brute-Force模式匹配算法 設(shè) S為目標(biāo)串， T為模式串，且不妨設(shè)： S=s0s1s2s n-1 ， T=t0t1t2 t m-1 串的匹配實(shí)際上是對(duì)合法的位置 0 i n-m依次將 目標(biāo)串中的子串 sii+m -1和模式串 t0m -1進(jìn)行比較： 若 sii+m -1=t0m -1：則稱從位置 i開(kāi)始的匹 配成功，亦稱模式 t在目標(biāo) s中出現(xiàn)； 若 sii+m -1t0m -1：從 i開(kāi)始的匹配失敗。 位置 i稱為位移，當(dāng) sii+m -1=t0m -1時(shí)， i稱為 有效位移；當(dāng) sii+m -1 t0m -1時(shí)， i稱為無(wú)效 位移。 這樣，串匹配 問(wèn)題可簡(jiǎn)化為找出某給定模式 T在給 定目標(biāo)串 S中首次出現(xiàn) 的有效位移。 算法實(shí)現(xiàn) int IndexString(StringType s , StringType t , int pos ) /* 采用順序存儲(chǔ)方式存儲(chǔ)主串 s和模式 t， */ /* 若模式 t在主串 s中從第 pos位置開(kāi)始有匹配的子串， */ /* 返回位置，否則返回 -1 */ char *p , *q ; int k , j ; k=pos-1 ； j=0 ; p=s.str+pos-1 ; q=t.str ; /* 初始匹配位置設(shè)置 */ /* 順序存放時(shí)第 pos位置的下標(biāo)值為 pos-1 */ while (ks.length) q+ ; k+ ; j+ ; else k=k-j+1 ; j=0 ; q=t.str ; p=s.str+k ; /* 重新設(shè)置匹配位置 */ if (j=t.length) return(k-t.length) ; / * 匹配，返回位置 */ else return(-1) ; /* 不匹配，返回 -1 */ 該算法簡(jiǎn)單，易于理解。在一些場(chǎng)合的應(yīng)用里，如 文字處理中的文本編輯，其效率較高。 該算法的時(shí)間復(fù)雜度為 O(n*m) ，其中 n 、 m分別 是主串和模式串的長(zhǎng)度。通常情況下，實(shí)際運(yùn)行過(guò)程中， 該算法的執(zhí)行時(shí)間近似于 O(n+m) 。 理解該算法的關(guān)鍵點(diǎn) 當(dāng)?shù)谝淮?sktj時(shí)：主串要退回到 k-j+1的位置，而模 式串也要退回到第一個(gè)字符（即 j=0的位置）。 比較出現(xiàn) sktj時(shí)：則應(yīng)該有 sk-1=tj-1， ， sk-j+1=t1， sk-j=t0 。 4.3.2 模式匹配的一種改進(jìn)算法 該改進(jìn)算法是由 D.E.Knuth ， J.H.Morris和 V.R.Pratt提出來(lái)的，簡(jiǎn)稱為 KMP算法。其 改進(jìn)在于： 每當(dāng)一趟匹配過(guò)程出現(xiàn)字符不相等時(shí)，主串指示器 不用回溯，而是利用已經(jīng)得到的“部分匹配”結(jié)果，將 模式串的指示器向右“ 滑動(dòng) ”盡可能遠(yuǎn)的一段距離后， 繼續(xù)進(jìn)行比較。 例： 設(shè)有串 s=abacabab ， t=abab 。則第一次匹配 過(guò)程如圖 4-2所示。 圖 4-2 模式匹配示例 s=“a b cbb” i=3 | | 匹配失敗 t=“a b b” j=3 在 i=3和 j=3時(shí)，匹配失敗。但重新開(kāi)始第二次匹配 時(shí)，不必從 i=1 ， j=0開(kāi)始。因?yàn)?s1=t1， t0t1，必有 s1t0， 又因?yàn)?t0=t2， s2=t2，所以必有 s2=t0。由此可知，第二次 匹配可以直接從 i=3 、 j=1開(kāi)始。 總之，在主串 s與模式串 t的匹配過(guò)程中，一旦出現(xiàn) sitj ，主串 s的指針不必回溯，而是直接與模式串的 tk(0 kj進(jìn)行比較，而 k的取值與主串 s無(wú)關(guān)，只與模式 串 t本身的構(gòu)成有關(guān)，即從模式串 t可求得 k值。 ) 不失一般性，設(shè) 主串 s=s1s2 sn ， 模式串 t=t1 t2 t m 。 當(dāng) sitj(1 i n-m， 1 jm， mn)時(shí)，主串 s的指針 i 不必回溯，而模式串 t的指針 j回溯到第 k(kk滿足 4-1式。 t1t2t k-1= si-(k-1) si-(k-2) s i-2 si-1 (4-1) 而已經(jīng)得到的 “部分匹配”的結(jié)果為： tj-(k-1) tj-k t j-1=si-(k-1) si-(k-2) s i-2 si-1 (4-2) 由式 (4-1)和式 (4-2)得： t1t2t k-1=tj-(k-1) tj-k t j-1 (4-3) 該推導(dǎo)過(guò)程可用圖 4-3形象描述。實(shí)際上，式 (4-3) 描述了模式串中存在相互重疊的子串的情況。 圖 4-3 KMP算法示例 主串 s i 模式串 t k j 0 當(dāng) j=1時(shí) Maxk|1kj t1t2t k-1=tj-(k-1) tj-k t j-1 該集合不空時(shí) 1 其它情況 nextj= 定義 nextj函數(shù)為 在求得了 nextj值之后， KMP算法的思想是： 設(shè)目標(biāo)串 (主串 )為 s，模式串為 t ，并設(shè) i指針和 j指針 分別指示目標(biāo)串和模式串中正待比較的字符，設(shè) i和 j的 初值均為 1。若有 si=tj，則 i和 j分別加 1。否則， i不變， j 退回到 j=nextj的位置，再比較 si和 tj，若相等，則 i和 j 分別加 1。否則， i不變， j再次退回到 j=nextj的位置， 依此類推。直到下列兩種可能： (1) j退回到某個(gè)下一個(gè) j值時(shí)字符比較相等，則指 針各自加 1繼續(xù)進(jìn)行匹配。 (2)退回到 j=0，將 i和 j分別加 1，即從主串的下一個(gè)字 符 si+1模式串的 t1重新開(kāi)始匹配。 KMP算法如下 #define Max_Strlen 1024 int nextMax_Strlen; int KMP_index (StringType s , StringType t) /* 用 KMP算法進(jìn)行模式匹配，匹配返回位置，否則返回 -1 */ /*用靜態(tài)存儲(chǔ)方式保存字符串， s和 t分別表示主串和模式串 */ int k=0 , j=0 ; /*初始匹配位置設(shè)置 */ while (ks.length) else return(-1) ; 很顯然， KMP_index函數(shù)是在已知下一個(gè)函數(shù)值的 基礎(chǔ)上執(zhí)行的，以下討論如何求 next函數(shù)值 ? 由式 (4-3)知，求模式串的 nextj值與主串 s無(wú)關(guān)，只 與模式串 t本身的構(gòu)成有關(guān)，則可把求 next函數(shù)值的問(wèn)題 看成是一個(gè)模式匹配問(wèn)題。由 next函數(shù)定義可知： 當(dāng) j=1時(shí)： next1=0。 設(shè) nextj=k，即在模式串中存在： t1t2t k-1=tj-(k-1)tj- k t j-1 ，其中下標(biāo) k滿足 1kk 滿足上式，即： nextj+1=nextj+1=k+1 (2) 若有 tktj ：則表明在模式串中有： t1 t2t k-1 tktj- (k-1) tj-k tj-1 tj ，當(dāng) tktj時(shí)應(yīng) 將模式向右滑動(dòng) 至以模 式中的第 nextk個(gè)字符和主串中的第 j個(gè)字符相比較。 若 nextk= k，且 tj = tk，則說(shuō)明在主串中第 j+1字符 之前存在一個(gè)長(zhǎng)度為 k(即 nextk)的最長(zhǎng)子串，與模 式串中從第一個(gè)字符起長(zhǎng)度為 k的子串相等。即 nextj+1=k+1 同理，若 tjtk，應(yīng) 將模式繼續(xù)向右滑動(dòng) 至將模式中 的第 nextk個(gè)字符和 tj對(duì)齊， ，依此類推，直到 tj和 模式串中的某個(gè)字符匹配成功或者不存在任何 k(1 kj)滿足等式： t1 t2t k-1 tk=tj-(k-1) tj-k tj-1 tj 則： nextj+1=1 根據(jù)上述分析， 求 next函數(shù)值的算法如下： void next(StringType t , int next) /* 求模式 t的 next串 t函數(shù)值并保存在 next數(shù)組中 */ int k=1 , j=0 ; next1=0; while (k1)個(gè)具有相同數(shù)據(jù)類型的數(shù)據(jù)元素 a1， a2， ， an組成的有序序列 ，且該 序列必須存儲(chǔ)在一塊 地址連續(xù)的存儲(chǔ)單元中 。 數(shù)組中的數(shù)據(jù)元素 具有相同數(shù)據(jù)類型 。 數(shù)組是一種隨機(jī)存取結(jié)構(gòu)，給定一組下標(biāo)，就可 以訪問(wèn)與其對(duì)應(yīng)的數(shù)據(jù)元素。 數(shù)組中的數(shù)據(jù)元素個(gè)數(shù)是固定的。 5.1.1 數(shù)組的 抽象數(shù)據(jù)類型定義 1 抽象數(shù)據(jù)類型定義 ADT Array 數(shù)據(jù)對(duì)象： ji= 0,1, ,bi-1 , 1,2, ,n ; D = aj1j2 jn | n0稱為數(shù)組的維數(shù) ， bi是數(shù)組第 i維的 長(zhǎng)度 ， ji是數(shù)組元素 第 i維的下標(biāo) ， aj1j2 jn ElemSet 數(shù)據(jù)關(guān)系： R = R1, R2, , Rn Ri=|0 jk bk-1 ， 1 k n且 ki， 0 ji bi-2， aj1j2 ji+1 jn D 基本操作： ADT Array 由上述定義知 ， n維數(shù)組中有 b1b2 bn個(gè)數(shù)據(jù) 元素 ， 每個(gè)數(shù)據(jù)元素都受到 n維關(guān)系的約束 。 2 直觀的 n維數(shù)組 以二維數(shù)組為例討論。將 二維數(shù)組看成是一個(gè)定長(zhǎng) 的線性表 ， 其 每個(gè)元素又是一個(gè)定長(zhǎng)的線性表 。 設(shè)二維數(shù)組 A=(aij)mn，則 A=(1， 2， ， p) (p=m或 n) 其中每個(gè)數(shù)據(jù)元素 j是一個(gè)列向量 (線性表 ) ： j =(a1j ， a2j ， ， amj) 1 j n 或 是一個(gè)行向量 ： i =(ai1 ， ai2 ， ， ain) 1 i m 如圖 5-1所示。 a11 a12 a1n a21 a22 a2n am1 am2 amn A= A= a11 a12 a1n a21 a22 a2n am1 am2 amn a11 a21 am1 a12 a22 am2 a1n a2n amn A= 圖 5-1 二維數(shù)組圖 例形式 (a) 矩陣 表示形式 (b) 列向量的一維數(shù)組形式 (c) 行向量的一維數(shù)組形式 5.2 數(shù)組的 順序表示和實(shí)現(xiàn) 數(shù)組一般不做插入和刪除操作，也就是說(shuō)，數(shù)組 一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就不再發(fā) 生變化。因此，一般都是 采用順序存儲(chǔ)的方法來(lái)表示數(shù) 組 。 問(wèn)題 ： 計(jì)算機(jī)的 內(nèi)存結(jié)構(gòu)是一維 (線性 )地址結(jié)構(gòu) ， 對(duì)于多維數(shù)組，將其存放 (映射 )到內(nèi)存一維結(jié)構(gòu)時(shí)，有 個(gè) 次序約定問(wèn)題 。即必須按某種次序?qū)?shù)組元素排成一 列序列，然后將這個(gè)線性序列存放到內(nèi)存中。 二維數(shù)組是最簡(jiǎn)單的多維數(shù)組，以此為例說(shuō)明多維 數(shù)組存放 (映射 )到內(nèi)存一維結(jié)構(gòu)時(shí)的 次序約定問(wèn)題 。 通常有兩種順序存儲(chǔ)方式 行優(yōu)先順序 (Row Major Order) ： 將數(shù)組元素 按行排列，第 i+1個(gè)行向量緊接在第 i個(gè)行向量后面。對(duì) 二維數(shù)組，按行優(yōu)先順序存儲(chǔ)的線性序列為： a11,a12,a 1n, a21,a22,a 2n , a m1,am2,a mn PASCAL、 C是按行優(yōu)先順序存儲(chǔ)的，如圖 5-2(b) 示。 列優(yōu)先順序 (Column Major Order) ： 將數(shù)組 元素按列向量排列，第 j+1個(gè)列向量緊接在第 j個(gè)列向量 之后，對(duì)二維數(shù)組，按列優(yōu)先順序存儲(chǔ)的線性序列為： a11,a21,a m1, a12,a22,a m2, , a n1,an2,a nm FORTRAN是按列優(yōu)先順序存儲(chǔ)的，如圖 5-2(c)。 圖 5-2 二維數(shù)組及其順序存儲(chǔ)圖 例形式 a11 a12 a1n a21 a22 a2n am1 am2 amn A= (a) 二維數(shù)組的表示形式 (b) 行優(yōu)先順序存儲(chǔ) (c) 列 優(yōu)先順序存儲(chǔ) a11 a12 a1n 第 1 行 a21 a22 a2n 第 2 行 am1 am2 Amn 第 m 行 a11 a21 am1 第 1 列 a12 a22 am2 第 2 列 a1m a2m amn 第 n 列 設(shè)有二維數(shù)組 A=(aij)mn，若每個(gè)元素占用的存儲(chǔ)單 元數(shù)為 l(個(gè) )， LOCa11表示元素 a11的首地址 ，即 數(shù)組 的 首地址 。 1 以 “ 行優(yōu)先順序 ” 存儲(chǔ) 第 1行中的 每個(gè)元素對(duì)應(yīng)的 (首 )地址是： LOCa1j=LOCa11+(j-1)l j=1,2, ,n (2) 第 2行中的 每個(gè)元素對(duì)應(yīng)的 (首 )地址是： LOCa2j=LOCa11+nl +(j-1)l j=1,2, ,n 第 m行中的 每個(gè)元素對(duì)應(yīng)的 (首 )地址是： LOCamj=LOCa11+(