第3講堆棧、隊(duì)列和字符串

1、Stack 、Queue & String棧和隊(duì)列是限定插入和刪除只能插入和刪除只能在表的“端點(diǎn)端點(diǎn)”進(jìn)行的線(xiàn)性表。 線(xiàn)性表線(xiàn)性表 棧棧 隊(duì)列隊(duì)列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in棧和隊(duì)列是兩種常用的數(shù)據(jù)類(lèi)型棧和隊(duì)列是兩種常用的數(shù)據(jù)類(lèi)型Section 1Stack退棧進(jìn)棧a0an-1an-2topbottom棧的抽象數(shù)據(jù)類(lèi)型定義棧的抽象數(shù)據(jù)類(lèi)型定義 ADT Stack 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象： D ai | ai ElemSet, i=

2、1,2,.,n, n0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系： R1 | ai-1, aiD, i=2,.,n 約定an 端為棧頂，a1 端為棧底。 基本操作：基本操作： ADT StackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &x)Push(&S, x)Pop(&S, &x) InitStack(&S) 操作結(jié)果：構(gòu)造一個(gè)空棧 S。 DestroyStack(&S) 初始條件：棧 S 已存在。 操作結(jié)果：棧 S 被銷(xiāo)毀。StackEmpty(S)初始條件：棧 S 已存在。 操作結(jié)果：若棧 S

3、 為空棧， 則返回 TRUE， 否則 FALE。StackLength(S)初始條件：棧 S 已存在。操作結(jié)果：返回 S 的元素 個(gè)數(shù)，即棧的 長(zhǎng)度。 GetTop(S, &x)初始條件：棧 S 已存在且非空。 操作結(jié)果：用 x 返回 S 的棧頂 元素。a1a2an ClearStack(&S)初始條件：棧 S 已存在。 操作結(jié)果：將 S 清為空棧。Push(&S, x) 初始條件：棧 S 已存在。 操作結(jié)果：插入元素 x 為新 的棧頂元素。a1a2anx Pop(&S, &x) 初始條件：棧 S 已存在且非 空。 操作結(jié)果：刪除 S 的棧頂元 素，并用 x 返回 其值。a1a2anan-1

4、/- 棧的順序存儲(chǔ)表?xiàng)５捻樞虼鎯?chǔ)表示示 - #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; 類(lèi)似于線(xiàn)性表的順序映象實(shí)現(xiàn)，類(lèi)似于線(xiàn)性表的順序映象實(shí)現(xiàn)，指向表尾的指針可以作為棧頂指針指向表尾的指針可以作為棧頂指針。 Status InitStack (SqStack &S)/ 構(gòu)造一個(gè)空棧S S.base=new ElemTypeSTACK_INIT_SIZE; if (!S.base) ex

5、it (OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; Status Push (SqStack &S, SElemType e) if (S.top - S.base = S.stacksize) /棧滿(mǎn)，追加存儲(chǔ)空間 S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (ElemType); if (!S.base) exit (OVERFLOW); /存儲(chǔ)分配失敗 S.top = S.base

6、 + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK;Status Pop (SqStack &S, SElemType &e) / 若棧不空，則刪除S的棧頂元素， / 用e返回其值，并返回OK； / 否則返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK;template class Stack private: int top; Type *elements; int maxSize;public: Stack ( int s

7、= 10 ); Stack ( ) delete elements; int Push ( Type x ); int Pop ( Type &x ); int GetTop ( Type &x ); void MakeEmpty ( ) top = -1; int IsEmpty ( ) const return top = -1; int IsFull ( ) const return top = maxSize-1; template Stack :Stack ( int s ) top= -1; maxSize = s; elements = new TypemaxSize; top空

8、棧toptoptoptoptopa 進(jìn)棧b 進(jìn)棧aababcdee 進(jìn)棧abcdef 進(jìn)棧溢出abdee 退棧ctopc 退棧b 退棧abaa 退?？湛諚opabdd 退棧ctopabctoptoptemplate int Stack:Push( Type x ) if (IsFull( ) return 0; elements+top = x; return 1;template int stack:Pop( Type & x ) if (IsEmpty( ) return 0; x=elementstop-; return 1; template int stack:GetTop( Ty

9、pe & x ) if (IsEmpty( ) return 0; x=elementstop; return 1;第一個(gè)例子：反轉(zhuǎn)表第一個(gè)例子：反轉(zhuǎn)表#include sq_stack.h void main()/* Pre: The user supplies an integer n and n decimal numbers. Post:The numbers are printed in reverse order. Uses:The STL class stack and its methods*/ int n; double item; stack numbers; / decl

10、ares a stack of numbers cout Type in an integer n followed n numbers. endl The numbers will be printed in reverse order. n; for (int i = 0; i item; numbers.push(item); cout endl endl; while (!numbers.empty() cout numbers.top() ; numbers.pop(); cout endl;toptemplate class Stack;template class StackNo

11、de friend class Stack; private: Type data; StackNode *link; public: StackNode ( Type d,StackNode*l = NULL )data=d;link=l; template class Stack private: StackNode *top; public: Stack ( ) top=NULL Stack ( ); void Push ( Type x ); int Pop ( Type & x ); int GetTop ( Type & x ); void MakeEmpty();/實(shí)現(xiàn)與Stac

12、k()同 int IsEmpty () return top = NULL; template Stack:Stack ( ) StackNode *p; while ( top != NULL ) p = top; top = top-link; delete p; template void Stack:Push ( Type x ) top = new StackNode ( x, top );template int Stack:Pop ( Type & x ) if ( IsEmpty ( ) ) return 0; StackNode *p = top; top = top-lin

13、k; x = p-data; delete p; return 1;template int Stack:GetTop ( Type & x ) if ( IsEmpty ( ) ) return 0; x = top-data; return 1; u中綴中綴(infix)表示表示 如如 A+B；u前綴前綴(prefix)表示表示 ，如如 +AB；u后綴后綴(postfix)表示表示 ，如如 AB+；操作符 ch = ( *, /, % +, - - )isp (棧棧內(nèi)內(nèi)) 0 1 7 5 3 8icp (棧棧外外) 0 8 6 4 2 1將字符放回輸入流將字符放回輸入流(cin.putba

14、ck)，讀操作數(shù)讀操作數(shù)newoperand2022-6-13443 32 2 棧的應(yīng)用舉例棧的應(yīng)用舉例 例例 1 數(shù)制轉(zhuǎn)換問(wèn)題數(shù)制轉(zhuǎn)換問(wèn)題 輾轉(zhuǎn)相除法如圖所示： 算法描述：算法描述： # define Length 10# define Length 10 void conversion ( int N void conversion ( int N，int r )int r ) int S Length , top ; int S Length , top ; / 定義一個(gè)順序棧 int x ;int x ; top = -1 ; top = -1 ; / 初始化棧 while ( N )

15、while ( N ) S+ top = N % r ; S+ top = N % r ; / 余數(shù)入棧 N=N / r ; N=N / r ; / 商作為被除數(shù)繼續(xù) while (top!= -1) while (top!= -1) / 出棧輸出 x = stop- ; x = stop- ; printf ( printf (“%d%d”, x ) ;, x ) ; 算算 法法 描描 述述# define Length 10 void conversion ( int N，int r ) int S Length , top ; / 定義一個(gè)順序棧定義一個(gè)順序棧 int x ; top =

16、 -1 ; / 初始化初始化 while ( N ) S+ top = N % r ; / 余數(shù)入棧余數(shù)入棧 N=N / r ; / 商作為被除數(shù)繼續(xù)商作為被除數(shù)繼續(xù) while (top!= -1) / 出棧輸出出棧輸出 x = stop- ; printf (“%d”, x ) ; 例例 2 檢查一個(gè)表達(dá)式中的括號(hào)是否配對(duì)檢查一個(gè)表達(dá)式中的括號(hào)是否配對(duì)# define STRLEN 255Bool cheak ( ) char S STRLEN ; / 初始化字符棧 int top = -1 ; char ch = # while ( ch ! = n ) / 重復(fù)從鍵盤(pán)讀字符，直到讀到回

17、車(chē)換行符 scanf ( “%c” , &ch ) ; switch ( ch ) / 根據(jù)讀入字符的不同情況分別處理 case ( : S+ top = ch ; break ; 例例 2 續(xù)續(xù)case : / ch是是( 或或 時(shí)，入棧時(shí)，入棧 S+ top = ch ; break ; case ): / 處理處理 ch=) 時(shí)的情況時(shí)的情況 if (Stop = = ( ) top - - ; else if ( Stop = = ) return ERROR ; break ; case : / 處理處理 ch= 時(shí)的情況時(shí)的情況 if (Stop = = ) top - - ; e

18、lse if ( Stop = = ( ) return ERROR ; break ; if ( top 0 ) return TRUE ; / 棧空時(shí)返回真，否則返回假棧空時(shí)返回真，否則返回假 else return ERROR ; / 算法結(jié)束算法結(jié)束例例3 表達(dá)式求值算法表達(dá)式求值算法OperandType ExpressionEvaluate ( ) / OperandType ExpressionEvaluate ( ) / 從鍵盤(pán)輸入中綴表達(dá)從鍵盤(pán)輸入中綴表達(dá)式，計(jì)算其值式，計(jì)算其值InitStack (OPTR) ; Push(OPTR , InitStack (OPTR) ;

19、 Push(OPTR , # #) ; / ) ; / 初始化運(yùn)算符棧初始化運(yùn)算符棧InitStack ( OPND ) ; / InitStack ( OPND ) ; / 初始化操作數(shù)初始化操作數(shù)ch = getchar ( ) ;ch = getchar ( ) ;while(ch !=while(ch !=# # & GetTop(OPTR)!= & GetTop(OPTR)!=# #) / ) / 逐個(gè)讀字符逐個(gè)讀字符chch且不等于且不等于# # if ( ! in ( ch , OP ) ) if ( ! in ( ch , OP ) ) Push ( OPND , ch ) ;

20、 / Push ( OPND , ch ) ; / 不是運(yùn)算符入操作數(shù)棧不是運(yùn)算符入操作數(shù)棧 else switch ( ) / else switch ( ) / 是運(yùn)算符時(shí)分別做不同處理是運(yùn)算符時(shí)分別做不同處理 case case : / ch 的優(yōu)先級(jí)低于棧頂運(yùn)算符的優(yōu)先級(jí) Pop ( OPTR , theta ) ; Pop ( OPND , x ) ; Pop ( OPND , y ) ; / 彈出兩個(gè)操作數(shù)Push(OPND , Operate(x,theta,y); / 計(jì)算、入操作數(shù)棧 ch = getchar ( ) ; / 讀下一個(gè)字符ch Pop ( OPND , x )

21、 ; return x ; / 返回結(jié)果 / 算法結(jié)束2022-6-1350例例4、后綴表達(dá)式求值。、后綴表達(dá)式求值。OperandType exprEvaluatel (char A ) / 本函數(shù)返回由后綴表達(dá)式A表示的表達(dá)式運(yùn)算結(jié)果 InitStack (S) ; ch = *A+ ; while ( ch != # ) if (!In(ch , OP ) Push (S , ch ) ; / 讀入的字符是操作數(shù)時(shí)入棧 else / / 是運(yùn)算符，取出兩個(gè)操作數(shù) Pop (S , x ) ; Pop (S , y) ; switch ( ch ) / 對(duì)兩個(gè)操作數(shù)進(jìn)行相應(yīng)計(jì)算 case

22、+ ： c = a+b ; break ; case - ： c = a-b ; break ; case *： c= a*b ; break ; case / ： c=a/b ; break ; case %： c=a%b ; break ; Push ( S, c ) ; / 計(jì)算結(jié)果入棧 ch=*A+ ; / 讀下一個(gè)字符 Pop ( S , c ) ; return c ; / 返回結(jié)果 / 算法結(jié)束2022-6-1351例例5、 利用棧實(shí)現(xiàn)遞歸函數(shù)計(jì)算利用棧實(shí)現(xiàn)遞歸函數(shù)計(jì)算n! 設(shè)設(shè)f (n) = n! , 求求f (n) 可以遞歸地定義為：可以遞歸地定義為：f (n)= 1 f (

23、n)= 1 n=0 n=0 時(shí)時(shí) / / 遞歸終止條件遞歸終止條件f f（n n）=n=n* *f (n-1) n0 f (n-1) n0 時(shí)時(shí) / / 遞歸步驟遞歸步驟 遞歸函數(shù)：遞歸函數(shù)：int fact (int n) if ( n = = 0 ) return 1 ; else return ( n* fact (n - 1) ) ; 2022-6-1352例例: 利用迭代實(shí)現(xiàn)遞歸函數(shù)計(jì)算利用迭代實(shí)現(xiàn)遞歸函數(shù)計(jì)算n! Int fact(int n,stack&s) While(n1) s.puch(n-) Int result=1; Int val; While(s.pop(val)

24、result=result*val; Return 2022-6-1353例例 6 漢諾塔問(wèn)題算法void hanoi( int n,char x, char y, char z ) void hanoi( int n,char x, char y, char z ) / / 將將x x柱上柱上n n個(gè)盤(pán)子借助個(gè)盤(pán)子借助y y柱移到柱移到z z柱上柱上 if( n = = 1) move (x,1,z );if( n = = 1) move (x,1,z ); / /將將x x柱上編號(hào)為柱上編號(hào)為1 1的盤(pán)子移動(dòng)到的盤(pán)子移動(dòng)到z z柱上柱上 else hanio( n-1, x, z, y )

25、;else hanio( n-1, x, z, y ); / / 將將x x柱上的柱上的n-1n-1個(gè)盤(pán)子移動(dòng)到個(gè)盤(pán)子移動(dòng)到y(tǒng) y柱上柱上 move (x , n , z ) ; move (x , n , z ) ; / / 將將x x柱上編號(hào)為柱上編號(hào)為n n的盤(pán)子移動(dòng)到的盤(pán)子移動(dòng)到z z上上 hanio(n-1, y, x, z) ;hanio(n-1, y, x, z) ; / / 將將y y柱上的柱上的n-1n-1個(gè)盤(pán)子移動(dòng)到個(gè)盤(pán)子移動(dòng)到z z柱上柱上 Section 2Queuea0 a1 a2 an-1frontrear ADT Queue 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： Dai | ai

26、ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | ai-1, ai D, i=2,.,n 約定其中a1 端為隊(duì)列頭隊(duì)列頭， an 端為隊(duì)列尾隊(duì)列尾基本操作：基本操作：隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義 ADT Queue隊(duì)列的基本操作：隊(duì)列的基本操作：InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &x)ClearQueue(&Q)DeQueue(&Q, &x)EnQueue(&Q, x)InitQueue(&Q) 操作結(jié)果：操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。DestroyQu

27、eue(&Q)初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：隊(duì)列Q被銷(xiāo)毀， 不再存在。 QueueEmpty(Q)初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：若Q為空隊(duì)列，則 返回TRUE，否則 返回FALSE。 QueueLength(Q) 初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：返回Q的元素個(gè) 數(shù)，即隊(duì)列的長(zhǎng) 度。 GetHead(Q, &x) 初始條件：初始條件：Q為非空隊(duì)列。 操作結(jié)果：操作結(jié)果：用x返回Q的隊(duì)頭 元素。a1a2an ClearQueue(&Q)初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：將Q清為空隊(duì)列。 EnQueue

28、(&Q, x) 初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：插入元素x為Q的 新的隊(duì)尾元素。a1a2anx DeQueue(&Q, &x) 初始條件：初始條件：Q為非空隊(duì)列。 操作結(jié)果：操作結(jié)果：刪除Q的隊(duì)頭元 素，并用x返回 其值。a1a2an front rear空隊(duì)列front rearA進(jìn)隊(duì)Afront rearB進(jìn)隊(duì)A Bfront rearC, D進(jìn)隊(duì)A B C Dfront rearA退隊(duì)B C Dfront rearB退隊(duì)C Dfront rearE,F,G進(jìn)進(jìn)隊(duì)C D E F GC D E F Gfront rearH進(jìn)進(jìn)隊(duì),溢出n n 01234567front

29、01234567front01234567frontrearAABCrearrear空隊(duì)列空隊(duì)列A進(jìn)進(jìn)隊(duì)隊(duì)B, C進(jìn)進(jìn)隊(duì)隊(duì)0123456701234567A退退隊(duì)隊(duì)B退退隊(duì)隊(duì)01234567D,E,F,G,H,I進(jìn)進(jìn)隊(duì)隊(duì)frontBCrearAfrontBCrearfrontCrearDEFG HI#define MAXQSIZE 100 /最大隊(duì)列長(zhǎng)度 typedef struct QElemType *base; / 動(dòng)態(tài)分配存儲(chǔ)空間 int front; / 頭指針，若隊(duì)列不空， / 指向隊(duì)列頭元素 int rear; / 尾指針，若隊(duì)列不空，指向 / 隊(duì)列尾元素 的下一個(gè)位置 SqQu

30、eue;循環(huán)隊(duì)列循環(huán)隊(duì)列順序映象 Status InitQueue (SqQueue &Q) / 構(gòu)造一個(gè)空隊(duì)列Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType); if (!Q.base) exit (OVERFLOW); / 存儲(chǔ)分配失敗 Q.front = Q.rear = 0; return OK; Status EnQueue (SqQueue &Q, ElemType e) / 插入元素e為Q的新的隊(duì)尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /隊(duì)列滿(mǎn)

31、 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; Status DeQueue (SqQueue &Q, ElemType &e) / 若隊(duì)列不空，則刪除Q的隊(duì)頭元素， / 用e返回其值，并返回OK; 否則返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;front rear空隊(duì)列front rearA進(jìn)隊(duì)Afront rearB進(jìn)隊(duì)A Bfront rear

32、C, D進(jìn)隊(duì)A B C Dfront rearA退隊(duì)B C Dfront rearB退隊(duì)C Dfront rearE,F,G進(jìn)進(jìn)隊(duì)C D E F GC D E F Gfront rearH進(jìn)進(jìn)隊(duì),溢出n n 01234567front01234567front01234567frontrearAABCrearrear空隊(duì)列空隊(duì)列A進(jìn)進(jìn)隊(duì)隊(duì)B, C進(jìn)進(jìn)隊(duì)隊(duì)0123456701234567A退退隊(duì)隊(duì)B退退隊(duì)隊(duì)01234567D,E,F,G,H進(jìn)進(jìn)隊(duì)隊(duì)frontBCrearAfrontBCrearfrontCrearDEF GHtemplate class Queue private: int re

33、ar, front; Type *elements; int maxSize;public: Queue ( int sz= 10 ); Queue ( ) delete elements; int EnQueue ( Type x ); int DeQueue ( Type &x ); int GetFront ( Type &x ); void MakeEmpty ( ) front = rear; int IsEmpty ( ) const return front = rear; int IsFull ( ) const return (rear+1) % maxSize = fron

34、t; int Length ( ) const return (rear-front+maxSize) % maxSize;template Queue:Queue( int sz ) front=0; rear=0; maxSize=sz; elements = new TypemaxSize;template int Queue:EnQueue( Type x ) if ( IsFull ( ) ) return 0; rear = (rear+1) % MaxSize; elementsrear = x; return 1;template int Queue:DeQueue( Type

35、 & x ) if ( IsEmpty ( ) ) return 0; front = ( front+1) % MaxSize; x = elementsfront; return 1;template int Queue:GetFront( Type & x ) if ( IsEmpty ( ) ) return 0; x = elements( front+1) % MaxSize; Return 1;(C+語(yǔ)言版)frontreartemplate class Queue;template class QueueNode friend class Queue;private: Type

36、 data; QueueNode *link;public: QueueNode(Type d, QueueNode *l = NULL ) data=d;link=l; template class Queue private: QueueNode *front, *rear; public: Queue( ) rear=NULL;front=NULL; Queue ( ); void EnQueue ( Type x ); int DeQueue ( Type & x ); int GetFront ( Type & x ); void MakeEmpty(); /實(shí)現(xiàn)與Queue()同

37、int IsEmpty ( ) const return front = NULL; ; template Queue : Queue ( ) QueueNode *p; while ( front != NULL ) p = front; front = front-link; delete p; template void Queue : EnQueue ( Type x ) if ( front = NULL ) front=rear=newQueueNode(x); else rear-link=newQueueNode(x); rear=rear-link; template int

38、 Queue:DeQueue(Type & x) if ( IsEmpty ( ) ) return 0; QueueNode *p=front; front=front-link; x=p-data; delete p; return 1;template int Queue:GetFront(Type & x) if ( IsEmpty( ) ) return 0; x=front-data; return 1; 顯示楊輝三角形的算法顯示楊輝三角形的算法Void yanghuiTriangle(int n)/結(jié)果顯示三角形的第結(jié)果顯示三角形的第1行行第第n行行 linkQueue q; i

39、nt s, t; q.InQueue(1); q.InQueue(1); /存儲(chǔ)第存儲(chǔ)第1行的兩個(gè)元素的值行的兩個(gè)元素的值 cout1“t” 1; /顯示第顯示第1行行 for (int i=2; i=n; i+) /依次顯示三角形的第依次顯示三角形的第2行到第行到第n行行 coutendl; q.InQueue(1); /第第i行的第行的第1個(gè)元素值為個(gè)元素值為1 cout1“t” /顯示第顯示第i行的第行的第1個(gè)元素個(gè)元素 q.OutQueue(s); /取第取第i-1行的第行的第1個(gè)元素個(gè)元素 顯示楊輝三角形的算法（續(xù)）顯示楊輝三角形的算法（續(xù)） for (int j=2; j=i; j

40、+) q.OutQueue(t); /取第取第i-1行的第行的第j個(gè)元素個(gè)元素 q.InQueue(s+t); /s+t為第為第i行第行第j個(gè)元素的值個(gè)元素的值 couts+t“t”; /顯示第顯示第i行第行第j個(gè)元素的值個(gè)元素的值 s=t: q.InQueue(1); /第第i行第行第i+1個(gè)元素的值個(gè)元素的值 為為1 cout1; /顯示第顯示第i行第行第i+1個(gè)元素的值個(gè)元素的值 cout=0)n(n=0)個(gè)字符的有限序列個(gè)字符的有限序列S=S=a1,a2,a1,a2,an,an 串名串名: s: s 串值串值: ai(1=i=n): ai(1=i=n) 串長(zhǎng)串長(zhǎng): n: n術(shù)術(shù) 語(yǔ)語(yǔ)空

41、空 串串n=0n=0的串的串子子 串串串中若干相鄰字符組成的子序列串中若干相鄰字符組成的子序列主主 串串包含子串的串包含子串的串空格串空格串僅含有空格字符的串僅含有空格字符的串(n(n不為不為0)0)串相等串相等設(shè)設(shè) s1=s1=a11,a11,an1,an1 s2= s2=a12,a12,an2,an2 若若 n1=n2n1=n2且且ai1=ai2ai1=ai2（1=i=n1)1=i=n1) 則則 s1=s2s1=s2 串的抽象數(shù)據(jù)類(lèi)型串的抽象數(shù)據(jù)類(lèi)型ADT String 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象：D ai |aiCharacterSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：R1 | a

42、i-1, ai D, i=2,.,n 基本操作基本操作: StrAssign (&T, chars) StrCopy (&T, S) DestroyString(&S) StrEmpty (S) StrCompare (S, T) StrLength(S) Concat (&T, S1, S2)SubString (&Sub, S, pos, len) Index (S, T, pos) Replace (&S, T, V)StrInsert (&S, pos, T) StrDelete (&S, pos, len) ClearString (&S) ADT String StrAssign

43、(&T, chars) 初始條件：初始條件：chars 是字符串常量是字符串常量 操作結(jié)果：操作結(jié)果：把把 chars 賦為賦為 T 的值的值 StrCopy (&T, S) 初始條件：初始條件：串串 S 存在存在 操作結(jié)果：操作結(jié)果：由串由串 S 復(fù)制得串復(fù)制得串 T DestroyString (&S) 初始條件：初始條件：串串 S 存在存在 操作結(jié)果：操作結(jié)果：串串 S 被銷(xiāo)毀被銷(xiāo)毀 StrEmpty(S)始條件：始條件：串串S存在存在操作結(jié)果：操作結(jié)果：若若 S 為空串，則返回為空串，則返回 TRUE，否則返回，否則返回 FALSE 表示空串，空串的長(zhǎng)度為零表示空串，空串的長(zhǎng)度為零 S

44、trCompare(S,T)初 始 條 件 ：初 始 條 件 ： 串串 S 和和 T 存 在存 在操作結(jié)果：操作結(jié)果：若若S T，則返回值，則返回值 0 若若S T，則返回值，則返回值 0 若若S T，則返回值，則返回值 0例如：例如：StrCompare( data , state ) 0 S t r L e n g t h ( S ) 初 始 條 件 ：初 始 條 件 ： 串串 S 存 在存 在 操作結(jié)果：操作結(jié)果：返回返回 S 的元素個(gè)數(shù)，的元素個(gè)數(shù)， 稱(chēng)為串的長(zhǎng)度稱(chēng)為串的長(zhǎng)度 Concat(&T,S1,S2) 初 始 條 件 ：初 始 條 件 ： 串串 S 1 和和 S 2 存 在存

45、在 操作結(jié)果：操作結(jié)果：用用 T 返回由返回由 S1 和和 S2 聯(lián)接而成的新串聯(lián)接而成的新串例如：例如： Concate( T, man , kind ) 求得求得 T = mankind SubString (&Sub, S, pos, len)初始條件：初始條件： 串串 S 存在，存在，1posStrLength(S) 且且0lenStrLength(S)-pos+1操作結(jié)果：操作結(jié)果： 用用 Sub 返回串返回串 S 的第的第 pos 個(gè)字符個(gè)字符 起長(zhǎng)度為起長(zhǎng)度為 len 的子串的子串例如：例如： SubString( sub, commander , 4, 3) 求得求得 sub

46、= man SubString( sub, commander , 1, 9)求得求得 sub = commander SubString( sub, commander , 9, 1)求得求得 sub = r 子串為子串為“串串” ” 中的一個(gè)字符子序列中的一個(gè)字符子序列SubString(sub, commander , 4, 7) sub = ? SubString(sub, beijing , 7, 2) = ? sub = ?SubString( student , 5, 0) = 起始位置和子串長(zhǎng)度之間存在約束關(guān)系起始位置和子串長(zhǎng)度之間存在約束關(guān)系長(zhǎng)度為長(zhǎng)度為 0 的子串為的子串為

47、“合法合法”串串 I n d e x ( S , T, p o s )初始初始條件：條件：串串S和和T存在，存在，T是非空串，是非空串， 1posStrLength(S)操作結(jié)果：操作結(jié)果： 若主串若主串 S 中存在和串中存在和串 T 值值 相同的子串相同的子串, 則返回它在則返回它在主主 串串 S 中 第中 第 p o s 個(gè)個(gè) 字符之后第一次出現(xiàn)的位字符之后第一次出現(xiàn)的位 置；否則函數(shù)值為置；否則函數(shù)值為0 假設(shè)假設(shè) S = abcaabcaaabc , T = bca Index(S, T, 1) = 2Index(S, T, 3) = 6Index(S, T, 8) = 0 “子串在主

48、串中的位置子串在主串中的位置”意指子串意指子串中的第一個(gè)字符在主串中的位序中的第一個(gè)字符在主串中的位序Replace(&S,T,V) 初始條件：初始條件：串串S, T和和 V 均已存在，均已存在， 且且 T 是非空串是非空串操作結(jié)果：操作結(jié)果：用用V替換主串替換主串S中出現(xiàn)中出現(xiàn) 的所有與（模式串）的所有與（模式串）T 相等的不重疊的子串相等的不重疊的子串假設(shè)假設(shè) S = abcaabcaaabca ，T = bca 若若 V = x ， 則經(jīng)置換后得到則經(jīng)置換后得到 S = axaxaax 若若 V = bc ， 則經(jīng)置換后得到則經(jīng)置換后得到 S = abcabcaabc StrInsert

49、 (&S, pos, T)初始條件：初始條件：串串S和和T存在，存在， 1posStrLength(S)1操作結(jié)果：操作結(jié)果：在串在串S的第的第pos個(gè)字符之個(gè)字符之前前 插入串插入串T例如：例如：S = chater ，T = rac ， 則執(zhí)行則執(zhí)行 StrInsert(S, 4, T)之后得到之后得到 S = character StrDelete (&S, pos, len)初始條件：初始條件：串串S存在存在 1posStrLength(S)-len+1操作結(jié)果：操作結(jié)果：從串從串S中刪除第中刪除第pos個(gè)字符個(gè)字符 起長(zhǎng)度為起長(zhǎng)度為len的子串的子串 ClearString(&S)

50、初 始 條 件 ：初 始 條 件 ： 串串 S 存 在存 在 操 作 結(jié) 果 ：操 作 結(jié) 果 ： 將將 S 清 為 空 串清 為 空 串 對(duì)于串的基本操作集可以有不同的定義方法，在使用高級(jí)程序設(shè)計(jì)語(yǔ)言中的串類(lèi)型時(shí)，應(yīng)以該語(yǔ)言的參考手冊(cè)為準(zhǔn)以該語(yǔ)言的參考手冊(cè)為準(zhǔn)。 gets(str) 輸入一個(gè)串； puts(str) 輸出一個(gè)串； strcat(str1, str2) 串聯(lián)接函數(shù)； strcpy(str1, str2, k) 串復(fù)制函數(shù)； strcmp(str1, str2) 串比較函數(shù)； strlen(str) 求串長(zhǎng)函數(shù)；例如：C語(yǔ)言函數(shù)庫(kù)中提供下列串處理函數(shù)：在上述抽象數(shù)據(jù)類(lèi)型定義的在上

51、述抽象數(shù)據(jù)類(lèi)型定義的1313種操作中種操作中 串賦值串賦值StrAssignStrAssign、 等六種操作等六種操作串復(fù)制串復(fù)制StrcopyStrcopy、 構(gòu)成串類(lèi)型構(gòu)成串類(lèi)型串比較串比較StrCompareStrCompare、 的最小操作的最小操作求串長(zhǎng)求串長(zhǎng)StrLengthStrLength、 子集子集串聯(lián)接串聯(lián)接ConcatConcat求子串求子串SubStringSubString 例如，可利用例如，可利用串比較串比較、求串長(zhǎng)和求子串、求串長(zhǎng)和求子串等操作實(shí)現(xiàn)定位函數(shù)等操作實(shí)現(xiàn)定位函數(shù)Index(S,T,pos)。 StrCompare(SubString(S, i, Str

52、Length(T),T ) ? 0 S 串 T 串 T 串iposn-m+1算法的基本思想為：算法的基本思想為：int Index (String S, String T, int pos) / T為非空串。若主串S中第pos個(gè)字符之后存在與 T相等的子串，則返回第一個(gè) 這樣的子串在S中的位置，否則返回0 if (pos 0) n = StrLength(S); m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return

53、i ; / while / if return 0; / S中不存在與T相等的子串 / Index 串的邏輯結(jié)構(gòu)和線(xiàn)性表極為相似，區(qū)別區(qū)別僅在于串的數(shù)據(jù)對(duì)象約束為字符集。 串的基本操作和線(xiàn)性表有很大差別。串的基本操作和線(xiàn)性表有很大差別。 在線(xiàn)性表的基本操作中，大多以大多以“單個(gè)單個(gè)元素元素”作為操作對(duì)象作為操作對(duì)象； 在串的基本操作中，通常以通常以“串的整體串的整體”作為操作對(duì)象作為操作對(duì)象。 在程序設(shè)計(jì)語(yǔ)言中，串只是作為輸入或輸出的常量出現(xiàn)，則只需存儲(chǔ)此串的串值，即字符序列即可。但在多數(shù)非數(shù)值處理的程序中，串也以變量的形式出現(xiàn)。串的表示和實(shí)現(xiàn)串的表示和實(shí)現(xiàn)一、串的定長(zhǎng)順序存儲(chǔ)表示一、串的定長(zhǎng)

54、順序存儲(chǔ)表示二、串的堆分配存儲(chǔ)表示二、串的堆分配存儲(chǔ)表示三、串的塊鏈存儲(chǔ)表示三、串的塊鏈存儲(chǔ)表示 #define MAXSTRLEN 255 / 用戶(hù)可在255以?xún)?nèi)定義最大串長(zhǎng) typedef unsigned char Sstring MAXSTRLEN + 1; / 0號(hào)單元存放串的長(zhǎng)度一、串的定長(zhǎng)順序存儲(chǔ)表示一、串的定長(zhǎng)順序存儲(chǔ)表示 按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時(shí)，其基本操作為 “字符序列字符序列的復(fù)制的復(fù)制”。 串串的實(shí)際長(zhǎng)度可在這個(gè)予定義長(zhǎng)度的范圍內(nèi)隨意設(shè)定，超過(guò)予定義長(zhǎng)度的串值則被舍去，稱(chēng)之為“截?cái)嘟財(cái)唷?。特點(diǎn)特點(diǎn): typedef struct char *ch; / 若是

55、非空串，則按串長(zhǎng)分配存儲(chǔ)區(qū)， / 否則ch為NULL int length; / 串長(zhǎng)度 HString;二、串的堆分配存儲(chǔ)表示二、串的堆分配存儲(chǔ)表示 通常，C語(yǔ)言中提供的串類(lèi)型就是以這種存儲(chǔ)方式實(shí)現(xiàn)的。系統(tǒng)利用函數(shù)malloc( )和free( )進(jìn)行串值空間的動(dòng)態(tài)管理，為每一個(gè)新產(chǎn)生的串分配一個(gè)存儲(chǔ)區(qū)，稱(chēng)串值共享的存儲(chǔ)空間為“堆堆”。 C語(yǔ)言中的串以一個(gè)空字符為結(jié)束符， 串長(zhǎng)是一個(gè)隱含值。 這類(lèi)串操作實(shí)現(xiàn)的算法為： 先為新生成的串分配一個(gè)存儲(chǔ)空間，然后 進(jìn)行串值的復(fù)制。三、串的塊鏈存儲(chǔ)表示三、串的塊鏈存儲(chǔ)表示也可用鏈表來(lái)存儲(chǔ)串值，由于串的數(shù)據(jù)元素是一個(gè)字符，它只有 8 位二進(jìn)制數(shù)，因此用鏈

56、表存儲(chǔ)時(shí)，通常一個(gè)結(jié)點(diǎn)中存放的不是一個(gè)字符，而是一個(gè)子串。存儲(chǔ)密度存儲(chǔ)密度 = 數(shù)據(jù)元素所占存儲(chǔ)位實(shí)際分配的存儲(chǔ)位 #define CHUNKSIZE 80 / 可由用戶(hù)定義的塊大小 typedef struct Chunk / 結(jié)點(diǎn)結(jié)構(gòu) char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的鏈表結(jié)構(gòu) Chunk *head, *tail; / 串的頭和尾指針 int curlen; / 串的當(dāng)前長(zhǎng)度 LString; 這是串的一種重要操作，很多 軟件，若有“編輯編輯”菜單項(xiàng)的話(huà)， 則其中必有“查找查找”子菜單項(xiàng)。串的模式

57、匹配算法串的模式匹配算法初始條件：串S和T存在，T是非空串， 1posStrLength(S)。操作結(jié)果：若主串S中存在和串T值相 同的子串返回它在主串S中 第pos個(gè)字符之后第一次出 現(xiàn)的位置；否則函數(shù) 值為0。 首先，回憶一下串匹配(查找)的定義:INDEX (S, T, pos) 下面討論以定長(zhǎng)順序結(jié)構(gòu)表示串時(shí)的幾種算法。一、簡(jiǎn)單算法一、簡(jiǎn)單算法二、首尾匹配算法首尾匹配算法三、三、KMP(KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法算法int Index(SString S, SString T, int pos) / 返回子串返回子串T在主串在主串S

58、中第中第pos個(gè)字符之后的位置。若不存在，個(gè)字符之后的位置。若不存在， / 則函數(shù)值為則函數(shù)值為0。其中，。其中，T非空，非空，1posStrLength(S)。 i = pos; j = 1; while (i = S0 & j T0) return i-T0; else return 0; / Index一、簡(jiǎn)單算法一、簡(jiǎn)單算法 先比較模式串的第一個(gè)字符， 再比較模式串的最后一個(gè)字符， 最后比較模式串中從第二個(gè)到 第n-1個(gè)字符。二、首尾匹配算法首尾匹配算法 int Index_FL(SString S, SString T, int pos) sLength = S0; tLength

59、= T0; i = pos; patStartChar = T1; patEndChar = TtLength; while (i = sLength tLength + 1) if (Si != patStartChar) +i; /重新查找匹配起始點(diǎn) else if (Si+tLength-1 != patEndChar) +i; / 模式串的“尾字符”不匹配 else return 0; / 檢查中間字符的匹配情況檢查中間字符的匹配情況 k = 1; j = 2; while ( j tLength & Si+k = Tj) +k; +j; if ( j = tLength ) retu

60、rn i; else +i; / 重新開(kāi)始下一次的匹配檢測(cè)KMP算法的時(shí)間復(fù)雜度可以達(dá)到O(m+n) 當(dāng) Si Tj 時(shí)，ababcabcacbab 已經(jīng)得到的結(jié)果： abcac Si-j+1.i-1 = T1.j-1 即：S3.6=T1.4 三、三、KMP(KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法算法i=7j=5算法討論設(shè)主串為s1s2sn,模式串為t1t2tn.當(dāng)匹配過(guò)程中產(chǎn)生失配時(shí)，（即sitj時(shí)）主串中第i字符應(yīng)與模式中哪個(gè)字符再比較？設(shè)應(yīng)與模式中第k(kj)個(gè)字符繼續(xù)進(jìn)行比較,則模式中前K個(gè)字符應(yīng)滿(mǎn)足下列關(guān)系： Si-k+1.i-1 = T1.