《《數據結構嚴蔚敏》PPT課件.ppt》由會員分享，可在線閱讀，更多相關《《數據結構嚴蔚敏》PPT課件.ppt（708頁珍藏版）》請在裝配圖網上搜索。

1、第 3章 棧和隊列 棧和隊列是兩種應用非常廣泛的數據結構 ，它們都 來自線性表數據結構， 都是 “ 操作受限 ” 的線性表 。 棧在計算機的實現有多種方式： 硬堆棧 ：利用 CPU中的某些寄存器組或類似的硬 件或使用內存的特殊區(qū)域來實現。這類堆棧容量有限， 但速度很快； 軟堆棧 ：這類堆棧主要在內存中實現。堆棧容量 可以達到很大。在實現方式上，又有 動態(tài)方式 和 靜態(tài) 方式 兩種。 本章將討論棧和隊列的基本概念 、 存儲結構 、 基本 操作以及這些操作的具體實現 。 3.1 棧 3.1.1 棧的基本概念 1 棧的概念 棧 (Stack)： 是限制在表的一端進行插入和刪除操 作的線性表。又稱為后

2、進先出 LIFO (Last In First Out) 或先進后出 FILO (First In Last Out)線性 表。 棧頂 (Top)： 允許進行插入、刪除操作的一端，又 稱為表尾。用棧頂指針 (top)來指示棧頂元素 。 棧底 (Bottom)： 是固定端，又稱為表頭。 空棧 ： 當表中沒有元素時稱為空棧。 設棧 S=(a1， a2， a n)，則 a1稱 為棧底元素， an為棧頂元素，如圖 3- 1所示。 棧中元素按 a1， a2， a n的次序 進棧，退棧的第一個元素應為棧頂元 素。即棧的修改是按后進先出的原則 進行的。 圖 3-1 順序 棧示意圖 a1 a2 ai an b

3、ottom top 進棧（ push） 出棧 (pop) 2 棧的抽象數據類型定義 ADT Stack 數據對象： D = ai|ai ElemSet, i=1,2,n ， n0 數據關系： R =|ai-1， ai D, i=2,3,n 基本操作：初始化、進棧、出棧、取棧頂元素等 ADT Stack 棧的順序存儲結構簡稱為順序棧，和線性表相類似， 用 一維數組 來 存儲棧 。根據數組是否可以根據需要增大， 又可分為 靜態(tài)順序棧 和 動態(tài)順序棧 。 靜態(tài)順序棧 實現簡單，但不能根據需要增大棧的 存儲空間； 動態(tài)順序棧 可以根據需要增大棧的存儲空間，但 實現稍為復雜。 3.1.2 棧的順序存儲表

4、示 采用 動態(tài) 一維數組 來 存儲棧 。所謂動態(tài)，指的是棧 的大小可以根據需要增加。 用 bottom表示棧底指針，棧底固定不變的；棧頂 則隨著進棧和退棧操作而變化。用 top(稱為棧頂指針 ) 指示當前棧頂位置。 用 top=bottom作為?？盏臉擞?，每次 top指向棧頂 數組中的下一個存儲位置 。 結點進棧 ： 首先將數據元素保存到棧頂 (top所指 的當前位置 )，然后執(zhí)行 top加 1，使 top指向棧頂的下 一個存儲位置 ; 3.1.2.1 棧的動態(tài)順序存儲表示 結點出棧 ： 首先執(zhí)行 top減 1，使 top指向棧頂元 素的存儲位置，然后將棧頂元素取出 。 圖 3-2是一個動態(tài)

5、棧的變化示意圖 。 圖 3-2 (動態(tài) )堆棧變化示意圖 空棧 bottom top 元素 a進棧 bottom top a 元素 b， c進棧 bottom top a b c 元素 c退棧 bottom top a b bottom top a b d e f 元素 d， e， f進棧 基本操作的實現 1 棧的類型定義 #define STACK_SIZE 100 /* 棧初始向量大小 */ #define STACKINCREMENT 10 /* 存儲空間分配增量 */ #typedef int ElemType ; typedef struct sqstack ElemType *bo

6、ttom; /* 棧不存在時值為 NULL */ ElemType *top; /* 棧頂指針 */ int stacksize ; /* 當前已分配空間，以元素為單位 */ 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棧頂和棧底指針相同 */ S. stacksize=STACK_SIZE; return OK

7、 ; 3 壓棧 (元素進棧 ) Status push(SqStack S , ElemType e) if (S.top-S.bottom=S. stacksize-1) S.bottom=(ElemType *)realloc(S. STACKINCREMENT+STACK_SIZE) *sizeof(ElemType); /* 棧滿，追加存儲空間 */ if (! S.bottom) return ERROR; S.top=S.bottom+S. stacksize ; S. stacksize+=STACKINCREMENT ; *S.top=e; S.top+ ; /* 棧頂指針加

8、1， e成為新的棧頂 */ return OK; 4 彈棧 (元素 出棧 ) Status pop( SqStack S, ElemType *e ) /*彈出棧頂元素 */ if ( S.top= S.bottom ) return ERROR ; /* ?？?，返回失敗標志 */ S.top- ; e=*S. top ; return OK ; 采用 靜態(tài) 一維數組 來 存儲棧 。 棧底固定不變的，而棧頂則隨著進棧和退棧操作變 化的， 棧底固定不變的；棧頂則隨著進棧和退棧操作而 變化，用一個整型變量 top(稱為棧頂指針 )來指示當 前棧頂位置。 用 top=0表示?？盏某跏紶顟B(tài) ，每次 t

9、op指向棧頂 在數組中的存儲位置 。 結點進棧 ： 首先執(zhí)行 top加 1，使 top指向新的棧 頂位置 ， 然后將數據元素保存到棧頂 (top所指的當前 位置 )。 3.1.2.2 棧的靜態(tài)順序存儲表示 結點出棧 ： 首先 把 top指向的棧頂元素取出 ， 然 后執(zhí)行 top減 1，使 top指向新的棧頂位置 。 若棧的數組有 Maxsize個元素 ，則 top=Maxsize-1時 棧滿 。圖 3-3是一個大小為 5的棧的變化示意圖 。 圖 3-3 靜態(tài) 堆棧變化示意圖 空棧 bottom top Top=1 1個元素進棧 bottom top a Top=3 3個元素進棧 bottom

10、top a b c Top=4 棧滿 bottom top a b e d Top=2 元素 c進棧 bottom top a b 基本操作的實現 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)

11、 ; 3 壓棧 (元素進棧 ) Status push(SqStack S , ElemType e) /* 使數據元素 e進棧成為新的棧頂 */ if (S.top=MAX_STACK_SIZE-1) return ERROR; /* 棧滿，返回錯誤標志 */ S.top+ ; /* 棧頂指針加 1 */ S.stack_arrayS.top=e ; /* e成為新的棧頂 */ return OK; /* 壓棧成功 */ 4 彈棧 (元素 出棧 ) Status pop( SqStack S, ElemType *e ) /*彈出棧頂元素 */ if ( S.top=0 ) return E

12、RROR ; /* ?？?，返回錯誤標志 */ *e=S.stack_arrayS.top ; S.top- ; return OK ; 當棧滿時做進棧運算必定產生空間溢出，簡稱 “ 上 溢 ” 。上溢是一種出錯狀態(tài)，應設法避免。 當?？諘r做退棧運算也將產生溢出，簡稱 “ 下溢 ” 。 下溢則可能是正?，F象，因為棧在使用時，其初態(tài)或終 態(tài)都是空棧，所以下溢常用來作為控制轉移的條件。 1 棧的鏈式表示 棧的 鏈式存儲結構 稱為鏈棧，是運算受限的單鏈表。 其插入和刪除操作只能在表頭位置上進行。因此，鏈棧 沒有必要像單鏈表那樣附加頭結點，棧頂指針 top就是 鏈表的頭指針。圖 3-4是棧的鏈式存儲表示

13、形式 。 3.1.3 棧的鏈式存儲表示 空棧 top 非空棧 top a4 a3 a1 a2 圖 3-4 鏈 棧存儲形式 鏈棧的 結點類型說明如下： typedef struct Stack_Node ElemType data ; struct Stack_Node *next ; Stack_Node ; 2 鏈?；静僮鞯膶崿F (1) 棧的初始化 Stack_Node *Init_Link_Stack(void) Stack_Node *top ; top=(Stack_Node *)malloc(sizeof(Stack_Node ) ; top-next=NULL ; return(

14、top) ; (2) 壓棧 (元素進棧 ) Status push(Stack_Node *top , ElemType e) Stack_Node *p ; p=(Stack_Node *)malloc(sizeof(Stack_Node) ; if (!p) return ERROR; /* 申請新結點失敗，返回錯誤標志 */ p-data=e ; p-next=top-next ; top-next=p ; /* 鉤鏈 */ return OK; (3) 彈棧 (元素 出棧 ) Status pop(Stack_Node *top , ElemType *e) /* 將棧頂元素 出 棧

15、*/ Stack_Node *p ; ElemType e ; if (top-next=NULL ) return ERROR ; /* ?？?，返回錯誤標志 */ p=top-next ; e=p-data ; /* 取棧頂元素 */ top-next=p-next ; /* 修改棧頂指針 */ free(p) ; return OK ; 3.2 棧的應用 由于棧具有的 “ 后進先出 ” 的固有特性，因此，棧 成為程序設計中常用的工具和數據結構。以下是幾個棧 應用的例子。 3.2.1 數制轉換 十進制整數 N向其它進制數 d(二 、 八 、 十六 )的轉換 是計算機實現計算的基本問題。 轉換

16、法則 ： 該轉換法則對應于一個簡單算法原理 : n=(n div d)*d+n mod d 其中： div為整除運算 ,mod為求余運算 例如 (1348)10= (2504)8， 其運算過程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 采用靜態(tài)順序棧方式實現 void conversion(int n , int d) /*將 十進制整數 N轉換為 d(2或 8)進制數 */ SqStack S ; int k, *e ; S=Init_Stack(); while (n0) k=n%d ; push(S , k) ; n=n/

17、d ; /* 求出所有的余 數， 進棧 */ while (S.top!=0) /* 棧不空時出棧，輸出 */ pop(S, e) ; printf(%1d , *e) ; 3.2.2 括號匹配問題 在文字處理軟件或編譯程序設計時，常常需要檢查 一個字符串或一個表達式中的括號是否相匹配 ? 匹配思想 ： 從左至右掃描一個字符串 (或表達式 )，則 每個右括號將與最近遇到的那個左括號相匹配 。則可以 在從左至右掃描過程中把所遇到的左括號存放到堆棧中。 每當遇到一個右括號時，就將它與棧頂的左括號 (如果 存在 )相匹配，同時從棧頂刪除該左括號。 算法思想 ： 設置一個棧，當讀到左括號時，左括號進

18、棧。當讀到右括號時，則從棧中彈出一個元素，與讀到 的左括號進行匹配，若匹配成功，繼續(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(括號不匹配” ) ; return FLA

19、SE ; else if (ch=) x=pop(S) ; if (x!=() printf(括號不匹配” ) ; return FLASE ; if (S.top!=0) printf(括號數量不匹配！” ) ; return FLASE ; else return TRUE ; 3.2.2 棧與遞歸調用的實現 棧的另一個重要應用是在程序設計語言中實現遞歸 調用。 遞歸調用 ： 一個函數 (或過程 )直接或間接地調用 自己本身，簡稱 遞歸 (Recursive)。 遞歸 是程序設計中的一個強有力的工具。因為遞歸 函數結構清晰，程序易讀，正確性很容易得到證明。 為了使遞歸調用不至于無終止地進行

20、下去，實際上 有效的遞歸調用函數 (或過程 )應包括兩部分： 遞推規(guī)則 (方法 )， 終止條件 。 例如：求 n! Fact(n)= 1 當 n=0時 終止條件 n*fact(n-1) 當 n0時 遞推規(guī)則 為保證遞歸調用正確執(zhí)行，系統(tǒng)設立一個 “ 遞歸工 作棧 ” ，作為整個遞歸調用過程期間使用的數據存儲區(qū)。 每一層遞歸包含的信息如： 參數 、 局部變量 、 上一 層的返回地址構成 一個“ 工作記錄 ” 。每進入一層遞 歸，就產生一個新的工作記錄壓入棧頂；每退出一層遞 歸，就從棧頂彈出一個工作記錄。 從被調函數返回調用函數的一般步驟： (1) 若棧為空，則執(zhí)行正常返回。 從棧頂彈出一個工作記

21、錄。 將“工作記錄”中的參數值、局部變量值賦給相 應的變量；讀取返回地址。 將函數值賦給相應的變量。 (5) 轉移到返回地址。 1 隊列的基本概念 隊列 (Queue)：也是運算受限的線性表。是一種 先 進先出 (First In First Out ，簡稱 FIFO)的線性表。只允 許在表的一端進行插入，而在另一端進行刪除。 隊首 (front) ：允許進行刪除的一端稱為隊首。 隊尾 (rear) ：允許進行插入的一端稱為隊尾。 例如：排隊購物。操作系統(tǒng)中的作業(yè)排隊。先進入 隊列的成員總是先離開隊列。 3.3 隊 列 3.3.1 隊列及其基本概念 隊列中沒有元素時稱為空隊列。在空隊列中依次

22、加入元素 a1, a2, , a n之后， a1是隊首元素， an是隊尾元 素。顯然退出隊列的次序也只能是 a1, a2, , a n ，即隊 列的修改是依 先進先出 的原則進行的，如圖 3-5所示。 a1 , a2 , , a n 出隊 入隊 隊尾 隊首 圖 3-5 隊列示意圖 2 隊列的抽象數據類型定義 ADT Queue 數據對象： D = ai|ai ElemSet, i=1, 2, , n, n = 0 數據關系： R = | ai-1, ai D, i=2,3,n 約定 a1端為隊首， an端為隊尾。 基本操作： Create()：創(chuàng)建一個空隊列 ； EmptyQue()：若隊列為

23、空 ， 則返回 true ， 否則返 回 flase ； InsertQue(x) ：向隊尾插入元素 x； DeleteQue(x) ：刪除隊首元素 x； ADT Queue 3.3.2 隊列的順序表示和實現 利用 一組連續(xù)的存儲單元 (一維數組 ) 依次存放從隊 首到隊尾的各個元素，稱為 順序隊列 。 對于隊列，和順序棧相類似，也有動態(tài)和靜態(tài)之分。 本部分介紹的是 靜態(tài)順序隊列 ，其類型定義如下： #define MAX_QUEUE_SIZE 100 typedef struct queue ElemType Queue_arrayMAX_QUEUE_SIZE ; int front ; i

24、nt rear ; SqQueue; 3.3.2.1 隊列的順序 存儲結構 設立一個 隊首指針 front ，一個 隊尾指針 rear ，分 別指向隊首和隊尾元素 。 初始化 ： front=rear=0。 入隊 ： 將新元素插入 rear所指的位置，然后 rear加 1。 出隊 ： 刪去 front所指的元素，然后加 1并返回被刪 元素。 隊列為空 ： front=rear。 隊滿 ： rear=MAX_QUEUE_SIZE-1或 front=rear。 在非空隊列里，隊首指針始終指向隊頭元素，而隊 尾指針始終指向隊尾元素的下一位置。 順序隊列中存在 “ 假溢出 ” 現象。因為在入隊和出 隊

25、操作中，頭、尾指針只增加不減小，致使被刪除元素 的空間永遠無法重新利用。因此，盡管隊列中實際元素 個數可能遠遠小于數組大小，但可能由于尾指針巳超出 向量空間的上界而不能做入隊操作。該現象稱為 假溢出 。 如圖 3-6所示是數組大小為 5的順序隊列中隊首 、 隊尾指 針和隊列中元素的變化情況。 (a) 空隊列 Q.front Q.rear (b) 入隊 3個元素 a3 a2 a1 Q.front Q.rear (c) 出隊 3個元素 Q.front Q.rear (d) 入隊 2個元素 a5 a4 Q.front Q.rear 圖 3-6 隊列示意圖 3.3.2.2 循環(huán)隊列 為充分利用向量空間

26、，克服上述“ 假溢出 ”現象的 方法是：將為隊列分配的 向量空間看成為一個首尾相接 的圓環(huán) ，并稱這種隊列為 循環(huán)隊列 (Circular Queue)。 在循環(huán)隊列中進行出隊、入隊操作時，隊首、隊尾 指針仍要加 1，朝前移動。只不過當隊首、隊尾指針指 向向量上界 (MAX_QUEUE_SIZE-1)時，其加 1操作的 結果是指向向量的下界 0。 這種循環(huán)意義下的加 1操作可以描述為： if (i+1=MAX_QUEUE_SIZE) i=0; else i+ ; 其中： i代表隊首指針 (front)或隊尾指針 (rear) 用模運算可簡化為： i=(i+1)%MAX_QUEUE_SIZE ;

27、 顯然，為循環(huán)隊列所分配的空間可以被充分利用， 除非向量空間真的被隊列元素全部占用，否則不會上溢 。因此，真正實用的順序隊列是循環(huán)隊列。 例：設 有循環(huán)隊列 QU0， 5，其初始狀態(tài)是 front=rear=0，各種操作后隊列的頭、尾指針的狀態(tài)變 化情況如下圖 3-7所示。 1 2 3 4 5 0 (a) 空隊列 front rear 1 2 3 4 5 0 (b) d, e, b, g入 隊 front d e b g rear 1 2 3 4 5 0 (c) d, e出隊 b g front rear 入隊時尾指針向前追趕頭指針，出隊時頭指針向前 追趕尾指針，故隊空和隊滿時頭尾指針均相等。

28、因此， 無法通過 front=rear來判斷隊列 “ 空 ” 還是 “ 滿 ” 。解 決此問題的方法是：約定入隊前，測試尾指針在循環(huán)意 義下加 1后是否等于頭指針，若相等則認為隊滿 。即 ： rear所指的單元始終為空。 1 2 3 4 5 0 (d) i, j, k入 隊 b g front i j k rear 1 2 3 4 5 0 (e) b, g出隊 i j k rear front 1 2 3 4 5 0 (f) r, p, s, t入隊 i j k front r p rear 圖 3-7 循環(huán)隊列操作及指針變化情況 循環(huán)隊列為空 ： front=rear 。 循環(huán)隊列滿 ： (

29、rear+1)%MAX_QUEUE_SIZE =front。 循環(huán)隊列的基本操作 1 循環(huán)隊列的初始化 SqQueue Init_CirQueue(void) SqQueue Q ; Q.front=Q.rear=0; return(Q) ; 2 入隊操作 Status Insert_CirQueue(SqQueue Q , ElemType e) /* 將數據元素 e插入到循環(huán)隊列 Q的隊尾 */ if (Q.rear+1)%MAX_QUEUE_SIZE= Q.front) return ERROR; /* 隊滿，返回錯誤標志 */ Q.Queue_arrayQ.rear=e ; /* 元素

30、 e入隊 */ Q.rear=(Q.rear+1)% MAX_QUEUE_SIZE ; /* 隊尾指針向前移動 */ return OK; /* 入隊成功 */ 3 出隊操作 Status Delete_CirQueue(SqQueue Q, ElemType *x ) /* 將循環(huán)隊列 Q的隊首元素出隊 */ if (Q.front+1= Q.rear) return ERROR ; /* 隊空，返回錯誤標志 */ *x=Q.Queue_arrayQ.front ; /* 取隊首元素 */ Q.front=(Q.front+1)% MAX_QUEUE_SIZE ; /* 隊首指針向前移動 *

31、/ return OK ; 1 隊列的鏈式存儲表示 隊列的鏈式存儲結構簡稱為鏈隊列，它是限制僅 在表頭進行刪除操作和表尾進行插入操作的單鏈表。 需要兩類不同的結點 ： 數據元素 結點 ， 隊列的 隊首 指針和隊尾指針 的結點 ，如圖 3-8所示。 3.3.3 隊列的鏈式表示和實現 數據元素結點類型定義： typedef struct Qnode ElemType data ; struct Qnode *next ; QNode ; 數據元素結點 data 指針結點 front rear 圖 3-8 鏈隊列結點示意圖 指針結點類型定義： typedef struct link_queue QN

32、ode *front , *rear ; Link_Queue ; 2 鏈隊運算及指針變化 鏈隊的操作實際上是單鏈表的操作，只不過是刪 除在表頭進行，插入在表尾進行。插入、刪除時分別修 改不同的指針。鏈隊運算及指針變化如圖 3-9所示。 圖 3-9 隊列操作及指針變化 (a) 空隊列 front rear (b) x入隊 x front rear (c) y再入隊 y front rear x (d) x出隊 y x front rear 3 鏈隊列的基本操作 鏈隊列的初始化 LinkQueue *Init_LinkQueue(void) LinkQueue *Q ; QNode *p ; p

33、=(QNode *)malloc(sizeof(QNode) ; /* 開辟頭結點 */ p-next=NULL ; Q=(LinkQueue *)malloc(sizeof(LinkQueue) ; /* 開辟鏈隊的指針結點 */ Q.front=Q.rear=p ; return(Q) ; 鏈隊列的 入隊操作 在已知隊列的隊尾插入一個元素 e ，即 修改隊尾 指 針 (Q.rear)。 Status Insert_CirQueue(LinkQueue *Q , ElemType e) /* 將數據元素 e插入到鏈隊列 Q的隊尾 */ p=(QNode *)malloc(sizeof(QNo

34、de) ; if (!p) return ERROR; /* 申請新結點失敗，返回錯誤標志 */ p-data=e ; p-next=NULL ; /* 形成新結點 */ Q.rear-next=p ; Q.rear=p ; /* 新結點插入到隊尾 */ return OK; 鏈隊列的出隊操作 Status Delete_LinkQueue(LinkQueue *Q, ElemType *x) QNode *p ; if (Q.front=Q.rear) return ERROR ; /* 隊空 */ p=Q.front-next ; /* 取隊首結點 */ *x=p-data ; Q.fro

35、nt-next=p-next ; /* 修改隊首指針 */ if (p=Q.rear) Q.rear=Q.front ; /* 當隊列只有一個結點時應防止丟失隊尾指針 */ free(p) ; return OK ; 鏈隊列的撤消 void Destroy_LinkQueue(LinkQueue *Q ) /* 將鏈隊列 Q的隊首元素出隊 */ while (Q.front!=NULL) Q.rear=Q.front-next; /* 令尾指針指向隊列的第一個結點 */ free(Q.front); /* 每次釋放一個結點 */ /* 第一次是頭結點，以后是元素結點 */ Q.ront=Q.r

36、ear; 習 題 三 1 設有一個棧，元素進棧的次序為 a, b, c。問經過棧 操作后可以得到哪些輸出序列？ 2 循環(huán)隊列的優(yōu)點是什么 ?如何判斷它的空和滿 ? 3 設有一個靜態(tài)順序隊列，向量大小為 MAX，判斷 隊列為空的條件是什么？隊列滿的條件是什么？ 4 設有一個靜態(tài)循環(huán)隊列，向量大小為 MAX，判斷 隊列為空的條件是什么？隊列滿的條件是什么？ 5 利用棧的基本操作， 寫一個返回棧 S中結點個數的 算法 int StackSize(SeqStack S) ，并說明 S為何不作為指 針參數 的算法 ? 6 一個雙向棧 S是在同一向量空間內實現的兩個棧 ， 它們的棧底分別設在向量空間的兩端

37、。試為此雙向棧設 計初始化 InitStack(S) ，入棧 Push(S,i,x)，出棧 Pop(S,i,x) 算法 ，其中 i為 0或 1 ，用以表示棧號。 7 設 Q0,6是一個靜態(tài)順序隊列 ，初始狀態(tài)為 front=rear=0，請畫出做完下列操作后隊列的頭尾指針 的狀態(tài)變化情況，若不能入對，請指出其元素，并說明 理由。 a, b, c, d入隊 a, b, c出隊 i , j , k , l , m入隊 d, i出隊 n, o, p, q, r入隊 8 假設 Q0,5是一個循環(huán)隊列 ，初始狀態(tài)為 front=rear=0，請畫出做完下列操作后隊列的頭尾指針 的狀態(tài)變化情況，若不能入對

38、，請指出其元素，并說明 理由。 d, e, b, g, h入隊 d, e出隊 i , j , k , l , m入隊 b出隊 n, o, p, q, r入隊 第 4章 串 在非數值處理、事務處理等問題常涉及到一系列 的字符操作。計算機的硬件結構主要是反映數值計算的 要求，因此，字符串的處理比具體數值處理復雜。本章 討論串的存儲結構及幾種基本的處理。 4.1 串類型的定義 4.1.1 串的基本概念 串 (字符串 )：是零個或多個字符組成的有限序列。 記作： S=a1a2a3 ，其中 S是串名， ai(1 i n)是單 個， 可以是字母、數字或其它字符。 串值 ：雙引號括起來的字符序列是串值。 串

39、長 ：串中所包含的字符個數稱為該串的長度。 空串 (空的字符串 )：長度為零的串稱為空串，它不 包含任何字符。 空格串 (空白串 )：構成串的所有字符都是空格的串 稱為空白串。 注意 ：空串和空白串的不同，例如 “ ” 和 “” 分別表 示長度為 1的空白串和長度為 0的空串。 子串 (substring)：串中任意個連續(xù)字符組成的子序 列稱為該串的子串，包含子串的串相應地稱為主串。 子串的序號 ：將子串在主串中首次出現時的該子串 的首字符對應在主串中的序號，稱為子串在主串中的序 號（或位置）。 例如， 設有串 A和 B分別是： A=這是字符串”， B=是” 則 B是 A的子串， A為主串。

40、B在 A中出現了兩次，其中 首次出現所對應的主串位置是 3。因此，稱 B在 A中的序 號為 3 。 特別地，空串是任意串的子串，任意串是其自身的 子串。 串相等 ：如果兩個串的串值相等 (相同 )，稱這兩個 串相等。換言之，只有當兩個串的長度相等，且各個對 應位置的字符都相同時才相等。 通常在程序中使用的串可分為兩種：串變量和串常 量。 串常量和整常數、實常數一樣，在程序中只能被引 用但不能不能改變其值，即只能讀不能寫。通常串常量 是由直接量來表示的，例如語句錯誤 (溢出 ” )中 “ 溢 出 ” 是直接量。 串變量和其它類型的變量一樣，其值是可以改變。 4.1.2 串的抽象數據類型定義 AD

41、T String 數據對象： D = ai|ai CharacterSet, i=1,2,n, n 0 數據關系： R = | ai-1, ai D, i=2,3,n 基本操作： StrAssign(t , chars) 初始條件： chars是一個字符串常量。 操作結果：生成一個值為 chars的串 t 。 StrConcat(s, t) 初始條件：串 s, t 已存在。 操作結果：將串 t聯結到串 s后形成新串存放到 s中。 StrLength(t) 初始條件：字符串 t已存在。 操作結果：返回串 t中的元素個數，稱為串長。 SubString (s, pos, len, sub) 初始條

42、件：串 s, 已存在 , 1 pos StrLength(s)且 0 len StrLength(s) pos+1。 操作結果：用 sub返回串 s的第 pos個字符起長度為 len 的子串。 ADT String 4.2 串的存儲表示和實現 串是一種特殊的線性表，其存儲表示和線性表類似， 但又不完全相同。串的存儲方式取決于將要對串所進行 的操作。串在計算機中有 3種表示方式： 定長順序存儲表示 ：將串定義成字符數組，利用 串名可以直接訪問串值。用這種表示方式，串的存 儲空間在編譯時確定，其大小不能改變。 堆分配存儲方式 ：仍然用一組地址連續(xù)的存儲單 元來依次存儲串中的字符序列，但串的存儲空間

43、是 在程序運行時根據串的實際長度動態(tài)分配的。 塊鏈存儲方式 ：是一種鏈式存儲結構表示。 4.2.1 串的定長順序存儲表示 這種存儲結構又稱為串的順序存儲結構。是用一 組連續(xù)的存儲單元來存放串中的字符序列。所謂定長順 序存儲結構，是直接使用定長的字符數組來定義，數組 的上界預先確定。 定長順序存儲結構定義為： #define MAX_STRLEN 256 typedef struct char strMAX_STRLEN ; int length; StringType ; 1 串的聯結操作 Status StrConcat ( StringType s, StringType t) /* 將串

44、 t聯結到串 s之后，結果仍然保存在 s中 */ int i, j ; if (s.length+t.length)MAX_STRLEN) Return ERROR ; /* 聯結后長度超出范圍 */ for (i=0 ; it.length ; i+) s.strs.length+i=t.stri ; /* 串 t聯結到串 s之后 */ s.length=s.length+t.length ; /* 修改聯結后的串長度 */ return OK ; 2 求子串操作 Status SubString (StringType s, int pos, int len, StringType *su

45、b) int k, j ; if (poss.length|len(s.length-pos+1) return ERROR ; /* 參數非法 */ sub-length=len-pos+1 ; /* 求得子串長度 */ for (j=0, k=pos ; kstrj=s.stri ; /* 逐個字符復制求得子串 */ return OK ; 4.2.2 串的堆分配存儲表示 實現方法：系統(tǒng)提供一個空間足夠大且地址連續(xù)的 存儲空間 (稱為 “ 堆 ” )供串使用。可使用 C語言的動態(tài) 存儲分配函數 malloc()和 free()來 管理。 特點是：仍然以一組地址連續(xù)的存儲空間來存儲字 符串值

46、，但其所需的存儲空間是在程序執(zhí)行過程中動態(tài) 分配，故是動態(tài)的，變長的。 串的堆式存儲結構的類型定義 typedef struct char *ch; /* 若非空，按長度分配，否則為 NULL */ int length; /* 串的長度 */ HString ; 1 串的聯結操作 Status Hstring *StrConcat(HString *T, HString *s1, HString *s2) /* 用 T返回由 s1和 s2聯結而成的串 */ int k, j , t_len ; if (T.ch) free(T); /* 釋放舊空間 */ t_len=s1-length+s2

47、-length ; if (p=(char *)malloc(sizeof(char)*t_len)=NULL) printf(系統(tǒng)空間不夠，申請空間失敗 ！ n) ; return ERROR ; for (j=0 ; jlength; j+) T-chj=s1-chj ; /* 將串 s復制到串 T中 */ for (k=s1-length, j=0 ; jlength; k+, j+) T-chj=s1-chj ; /* 將串 s2復制到串 T中 */ free(s1-ch) ; free(s2-ch) ; return OK ; 4.2.3 串的鏈式存儲表示 串的鏈式存儲結構和線性表的

48、串的鏈式存儲結構類 似，采用單鏈表來存儲串， 結點的構成是： data域：存放字符， data域可存放的字符個數稱為 結點的大??； next域：存放指向下一結點的指針。 若每個結點僅存放一個字符，則結點的指針域就非 常多，造成系統(tǒng)空間浪費，為節(jié)省存儲空間，考慮串結 構的特殊性，使每個結點存放若干個字符，這種結構稱 為塊鏈結構。如 圖 4-1是塊大小為 3的串的塊鏈式存儲結 構示意圖。 串的塊鏈式存儲的類型定義包括： 塊結點的類型定義 #define BLOCK_SIZE 4 typedef struct Blstrtype char dataBLOCK_SIZE ; struct Blstrt

49、ype *next; BNODE ; a b c e p c g head 圖 4-1 串的塊鏈式存儲結構示意圖 (2) 塊鏈串的類型定義 typedef struct BNODE head; /* 頭指針 */ int Strlen ; /* 當前長度 */ Blstring ; 在這種存儲結構下，結點的分配總是完整的結點為 單位，因此，為使一個串能存放在整數個結點中，在串 的末尾填上不屬于串值的特殊字符，以表示串的終結。 當一個塊 (結點 )內存放多個字符時，往往會使操作 過程變得較為復雜，如在串中插入或刪除字符操作時通 常需要在塊間移動字符。 4.3 串的模式匹配算法 模式匹配 (模范匹

50、配 )： 子串在主串中的定位稱為模 式匹配或串匹配 (字符串匹配 ) 。模式匹配成功是指在 主串 S中能夠找到模式串 T，否則，稱模式串 T在主串 S 中不存在。 模式匹配的應用在非常廣泛。例如，在文本編輯 程序中，我們經常要查找某一特定單詞在文本中出現的 位置。顯然，解此問題的有效算法能極大地提高文本編 輯程序的響應性能。 模式匹配是一個較為復雜的串操作過程。迄今為止， 人們對串的模式匹配提出了許多思想和效率各不相同的 計算機算法。介紹兩種主要的模式匹配算法。 4.3.1 Brute-Force模式匹配算法 設 S為目標串， T為模式串，且不妨設： S=s0s1s2s n-1 ， T=t0t

51、1t2 t m-1 串的匹配實際上是對合法的位置 0 i n-m依次將 目標串中的子串 sii+m -1和模式串 t0m -1進行比較： 若 sii+m -1=t0m -1：則稱從位置 i開始的匹 配成功，亦稱模式 t在目標 s中出現； 若 sii+m -1t0m -1：從 i開始的匹配失敗。 位置 i稱為位移，當 sii+m -1=t0m -1時， i稱為 有效位移；當 sii+m -1 t0m -1時， i稱為無效 位移。 這樣，串匹配 問題可簡化為找出某給定模式 T在給 定目標串 S中首次出現 的有效位移。 算法實現 int IndexString(StringType s , Stri

52、ngType t , int pos ) /* 采用順序存儲方式存儲主串 s和模式 t， */ /* 若模式 t在主串 s中從第 pos位置開始有匹配的子串， */ /* 返回位置，否則返回 -1 */ char *p , *q ; int k , j ; k=pos-1 ； j=0 ; p=s.str+pos-1 ; q=t.str ; /* 初始匹配位置設置 */ /* 順序存放時第 pos位置的下標值為 pos-1 */ while (ks.length) q+ ; k+ ; j+ ; else k=k-j+1 ; j=0 ; q=t.str ; p=s.str+k ; /* 重新設置匹

53、配位置 */ if (j=t.length) return(k-t.length) ; / * 匹配，返回位置 */ else return(-1) ; /* 不匹配，返回 -1 */ 該算法簡單，易于理解。在一些場合的應用里，如 文字處理中的文本編輯，其效率較高。 該算法的時間復雜度為 O(n*m) ，其中 n 、 m分別 是主串和模式串的長度。通常情況下，實際運行過程中， 該算法的執(zhí)行時間近似于 O(n+m) 。 理解該算法的關鍵點 當第一次 sktj時：主串要退回到 k-j+1的位置，而模 式串也要退回到第一個字符（即 j=0的位置）。 比較出現 sktj時：則應該有 sk-1=tj-1

54、， ， sk-j+1=t1， sk-j=t0 。 4.3.2 模式匹配的一種改進算法 該改進算法是由 D.E.Knuth ， J.H.Morris和 V.R.Pratt提出來的，簡稱為 KMP算法。其 改進在于： 每當一趟匹配過程出現字符不相等時，主串指示器 不用回溯，而是利用已經得到的“部分匹配”結果，將 模式串的指示器向右“ 滑動 ”盡可能遠的一段距離后， 繼續(xù)進行比較。 例： 設有串 s=abacabab ， t=abab 。則第一次匹配 過程如圖 4-2所示。 圖 4-2 模式匹配示例 s=“a b cbb” i=3 | | 匹配失敗 t=“a b b” j=3 在 i=3和 j=3時

55、，匹配失敗。但重新開始第二次匹配 時，不必從 i=1 ， j=0開始。因為 s1=t1， t0t1，必有 s1t0， 又因為 t0=t2， s2=t2，所以必有 s2=t0。由此可知，第二次 匹配可以直接從 i=3 、 j=1開始。 總之，在主串 s與模式串 t的匹配過程中，一旦出現 sitj ，主串 s的指針不必回溯，而是直接與模式串的 tk(0 kj進行比較，而 k的取值與主串 s無關，只與模式 串 t本身的構成有關，即從模式串 t可求得 k值。 ) 不失一般性，設 主串 s=s1s2 sn ， 模式串 t=t1 t2 t m 。 當 sitj(1 i n-m， 1 jm， mn)時，主串

56、 s的指針 i 不必回溯，而模式串 t的指針 j回溯到第 k(kk滿足 4-1式。 t1t2t k-1= si-(k-1) si-(k-2) s i-2 si-1 (4-1) 而已經得到的 “部分匹配”的結果為： 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) 該推導過程可用圖 4-3形象描述。實際上，式 (4-3) 描述了模式串中存在相互重疊的子串的情況。 圖 4-3 KMP算法示例 主串 s i 模式串 t k j 0

57、當 j=1時 Maxk|1kj t1t2t k-1=tj-(k-1) tj-k t j-1 該集合不空時 1 其它情況 nextj= 定義 nextj函數為 在求得了 nextj值之后， KMP算法的思想是： 設目標串 (主串 )為 s，模式串為 t ，并設 i指針和 j指針 分別指示目標串和模式串中正待比較的字符，設 i和 j的 初值均為 1。若有 si=tj，則 i和 j分別加 1。否則， i不變， j 退回到 j=nextj的位置，再比較 si和 tj，若相等，則 i和 j 分別加 1。否則， i不變， j再次退回到 j=nextj的位置， 依此類推。直到下列兩種可能： (1) j退回到

58、某個下一個 j值時字符比較相等，則指 針各自加 1繼續(xù)進行匹配。 (2)退回到 j=0，將 i和 j分別加 1，即從主串的下一個字 符 si+1模式串的 t1重新開始匹配。 KMP算法如下 #define Max_Strlen 1024 int nextMax_Strlen; int KMP_index (StringType s , StringType t) /* 用 KMP算法進行模式匹配，匹配返回位置，否則返回 -1 */ /*用靜態(tài)存儲方式保存字符串， s和 t分別表示主串和模式串 */ int k=0 , j=0 ; /*初始匹配位置設置 */ while (ks.length)

59、else return(-1) ; 很顯然， KMP_index函數是在已知下一個函數值的 基礎上執(zhí)行的，以下討論如何求 next函數值 ? 由式 (4-3)知，求模式串的 nextj值與主串 s無關，只 與模式串 t本身的構成有關，則可把求 next函數值的問題 看成是一個模式匹配問題。由 next函數定義可知： 當 j=1時： next1=0。 設 nextj=k，即在模式串中存在： t1t2t k-1=tj-(k-1)tj- k t j-1 ，其中下標 k滿足 1kk 滿足上式，即： nextj+1=nextj+1=k+1 (2) 若有 tktj ：則表明在模式串中有： t1 t2t k

60、-1 tktj- (k-1) tj-k tj-1 tj ，當 tktj時應 將模式向右滑動 至以模 式中的第 nextk個字符和主串中的第 j個字符相比較。 若 nextk= k，且 tj = tk，則說明在主串中第 j+1字符 之前存在一個長度為 k(即 nextk)的最長子串，與模 式串中從第一個字符起長度為 k的子串相等。即 nextj+1=k+1 同理，若 tjtk，應 將模式繼續(xù)向右滑動 至將模式中 的第 nextk個字符和 tj對齊， ，依此類推，直到 tj和 模式串中的某個字符匹配成功或者不存在任何 k(1 kj)滿足等式： t1 t2t k-1 tk=tj-(k-1) tj-k

61、 tj-1 tj 則： nextj+1=1 根據上述分析， 求 next函數值的算法如下： void next(StringType t , int next) /* 求模式 t的 next串 t函數值并保存在 next數組中 */ int k=1 , j=0 ; next1=0; while (k1)個具有相同數據類型的數據元素 a1， a2， ， an組成的有序序列 ，且該 序列必須存儲在一塊 地址連續(xù)的存儲單元中 。 數組中的數據元素 具有相同數據類型 。 數組是一種隨機存取結構，給定一組下標，就可 以訪問與其對應的數據元素。 數組中的數據元素個數是固定的。 5.1.1 數組的 抽象數據

62、類型定義 1 抽象數據類型定義 ADT Array 數據對象： ji= 0,1, ,bi-1 , 1,2, ,n ; D = aj1j2 jn | n0稱為數組的維數 ， bi是數組第 i維的 長度 ， ji是數組元素 第 i維的下標 ， aj1j2 jn ElemSet 數據關系： 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維數組中有 b1b2 bn個數據 元素 ， 每個數據元素都受到 n維關系的約束 。 2 直觀的 n維數組 以二維數組為例

63、討論。將 二維數組看成是一個定長 的線性表 ， 其 每個元素又是一個定長的線性表 。 設二維數組 A=(aij)mn，則 A=(1， 2， ， p) (p=m或 n) 其中每個數據元素 j是一個列向量 (線性表 ) ： j =(a1j ， a2j ， ， amj) 1 j n 或 是一個行向量 ： 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 a

64、mn A= 圖 5-1 二維數組圖 例形式 (a) 矩陣 表示形式 (b) 列向量的一維數組形式 (c) 行向量的一維數組形式 5.2 數組的 順序表示和實現 數組一般不做插入和刪除操作，也就是說，數組 一旦建立，結構中的元素個數和元素間的關系就不再發(fā) 生變化。因此，一般都是 采用順序存儲的方法來表示數 組 。 問題 ： 計算機的 內存結構是一維 (線性 )地址結構 ， 對于多維數組，將其存放 (映射 )到內存一維結構時，有 個 次序約定問題 。即必須按某種次序將數組元素排成一 列序列，然后將這個線性序列存放到內存中。 二維數組是最簡單的多維數組，以此為例說明多維 數組存放 (映射 )到內存一

65、維結構時的 次序約定問題 。 通常有兩種順序存儲方式 行優(yōu)先順序 (Row Major Order) ： 將數組元素 按行排列，第 i+1個行向量緊接在第 i個行向量后面。對 二維數組，按行優(yōu)先順序存儲的線性序列為： a11,a12,a 1n, a21,a22,a 2n , a m1,am2,a mn PASCAL、 C是按行優(yōu)先順序存儲的，如圖 5-2(b) 示。 列優(yōu)先順序 (Column Major Order) ： 將數組 元素按列向量排列，第 j+1個列向量緊接在第 j個列向量 之后，對二維數組，按列優(yōu)先順序存儲的線性序列為： a11,a21,a m1, a12,a22,a m2,

66、, a n1,an2,a nm FORTRAN是按列優(yōu)先順序存儲的，如圖 5-2(c)。 圖 5-2 二維數組及其順序存儲圖 例形式 a11 a12 a1n a21 a22 a2n am1 am2 amn A= (a) 二維數組的表示形式 (b) 行優(yōu)先順序存儲 (c) 列 優(yōu)先順序存儲 a11 a12 a1n 第 1 行 a21 a22 a2n 第 2 行 am1 am2 Amn 第 m 行 a11 a21 am1 第 1 列 a12 a22 am2 第 2 列 a1m a2m amn 第 n 列 設有二維數組 A=(aij)mn，若每個元素占用的存儲單 元數為 l(個 )， LOCa11表示元素 a11的首地址 ，即 數組 的 首地址 。 1 以 “ 行優(yōu)先順序 ” 存儲 第 1行中的 每個元素對應的 (首 )地址是： LOCa1j=LOCa11+(j-1)l j=1,2, ,n (2) 第 2行中的 每個元素對應的 (首 )地址是： LOCa2j=LOCa11+nl +(j-1)l j=1,2, ,n 第 m行中的 每個元素對應的 (首 )地址是： LOCamj=LOCa11+(