第3讲堆栈、队列和字符串

Stack、Queue&String栈和队列是限定插入和删除只能在表的“端点”进行的线性表。

线性表栈队列Insert(L,

i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n栈和队列是两种常用的数据类型Section1

Stack

只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶

(top)，另一端称为栈底(bottom)特点后进先出(LIFO)栈(Stack)退栈进栈a0an-1an-2topbottom栈的抽象数据类型定义ADTStack

{

数据对象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

约定an

端为栈顶，a1端为栈底。基本操作：

}ADTStackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&x)Push(&S,x)Pop(&S,&x)

InitStack(&S)

操作结果：构造一个空栈

S。

DestroyStack(&S)

初始条件：栈S已存在。

操作结果：栈S被销毁。

StackEmpty(S)

初始条件：栈S已存在。

操作结果：若栈S为空栈，

则返回TRUE，

否则FALE。

StackLength(S)

初始条件：栈S已存在。

操作结果：返回S的元素

个数，即栈的

长度。

GetTop(S,&x)

初始条件：栈S已存在且非空。

操作结果：用x返回S的栈顶

元素。a1a2an……

ClearStack(&S)

初始条件：栈S已存在。

操作结果：将S清为空栈。

Push(&S,x)

初始条件：栈S已存在。

操作结果：插入元素x为新

的栈顶元素。

a1a2anx……Pop(&S,&x)

初始条件：栈S已存在且非

空。

操作结果：删除S的栈顶元

素，并用x返回

其值。a1a2anan-1

……

栈的数组表示

—顺序栈

//-----栈的顺序存储表示

-----

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;

类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。

StatusInitStack(SqStack&S){//构造一个空栈SS.base=newElemType[STACK_INIT_SIZE];if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}

StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){//栈满，追加存储空间

S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*

sizeof(ElemType));

if(!S.base)exit(OVERFLOW);//存储分配失败

S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;}StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，

//用e返回其值，并返回OK；

//否则返回ERROR

if

(S.top

==

S.base)

returnERROR;

e=*--S.top;

returnOK;}template<classType>classStack{private:int

top;

Type*elements;

intmaxSize;public:Stack(ints

=10);~Stack(){delete[]elements;

}

intPush(Typex);

intPop(Type

&x);intGetTop(Type

&x);

voidMakeEmpty(){top=-1;

}

intIsEmpty()const{returntop==-1;

}

intIsFull()const{returntop==maxSize-1;

} }template<classType>Stack<Type>::Stack(ints){top=-1;maxSize=s;elements=newType[maxSize]; }

top空栈toptoptoptoptopa进栈b进栈aababcdee进栈abcdef进栈溢出abdee退栈ctopc退栈b退栈abaa退栈空栈topabdd退栈ctopabctoptoptemplate<classType>intStack<Type>::Push(Typex){

if(IsFull())

return0;elements[++top]=x;return1;}template<classType>intstack<Type>::Pop(Type&x){if(IsEmpty())return0;x=elements[top--];return1;}

template<classType>intstack<Type>::GetTop(Type&x){if(IsEmpty())

return0;x=elements[top];return1;}第一个例子：反转表#include"sq_stack.h"voidmain()/*Pre:Theusersuppliesanintegernandndecimalnumbers.Post:Thenumbersareprintedinreverseorder.Uses:TheSTLclassstackanditsmethods*/{intn;doubleitem;stack<double>numbers;//declaresastackofnumberscout<<"Typeinanintegernfollowednnumbers."<<endl<<"Thenumberswillbeprintedinreverseorder."<<endl;cin>>n;for(inti=0;i<n;i++){

cin>>item;numbers.push(item);}cout<<endl<<endl;while(!numbers.empty()){cout<<numbers.top()<<"";numbers.pop();}cout<<endl;}栈的链接表示—链式栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头top链式栈(LinkedStack)类的定义template<classType>classStack;template<classType>classStackNode{friendclassStack<Type>;private:

Typedata;StackNode<Type>*link;public:StackNode(Typed,StackNode<Type>

*l=NULL){ data=d;link=l;

}};template<classType>classStack{private:StackNode<Type>*top;public:Stack(){top=NULL}~Stack();

voidPush(Typex);

intPop(Type&x);

intGetTop(Type&x);

voidMakeEmpty();//实现与~Stack()同

intIsEmpty(){returntop==NULL;

}}template<classType>Stack<Type>::~Stack(){StackNode<Type>*p;

while(top!=NULL)

{p=top;top=top->link;

deletep;

}}template<classType>voidStack<Type>::Push(Typex){top=newStackNode<Type>(x,top);}template<classType>intStack<Type>::Pop(Type&x){if(IsEmpty())return

0; StackNode<Type>*p=top;top=top->link;x=p->data;

deletep;

return1;}

template<classType>intStack<Type>::GetTop(Type&x){if(IsEmpty())return0;x=top->data;return1;}

表达式求值一个表达式由操作数(亦称运算对象)、操作符

(亦称运算符)和分界符组成。算术表达式有三种表示：中缀(infix)表示

<操作数><操作符><操作数>，如A+B；前缀(prefix)表示

<操作符><操作数><操作数>，如+AB；后缀(postfix)表示

<操作数><操作数><操作符>，如AB+；表达式的中缀表示

表达式中相邻两个操作符的计算次序为：优先级高的先计算；优先级相同的自左向右计算；当使用括号时从最内层括号开始计算。C++中操作符的优先级

优先级

操作符

1 单目+、-、！

2 *、/、% 3 +、-

4 <、<=、>、>=5==、!= 6 && 7 || 一般表达式的操作符有4种类型：算术操作符如双目操作符（+、-、*、/和%）以及单目操作符（+、-）。关系操作符包括<、<=、==、!=、>=、>。这些操作符主要用于比较。逻辑操作符如与(&&)、或(||)、非(!)。括号‘(’和‘)’它们的作用是改变运算顺序。

中缀表达式中各个算术操作符的优先级isp叫做栈内(instackpriority)优先数icp叫做栈外(incomingpriority)优先数。操作符优先数相等的情况只出现在括号配对或栈底的‘=’号与输入流最后的‘=’号配对时。上面讨论的+、-为双目运算符，如为单目运算符，编程实现时，可在前面加上0而转化为双目运算符。如在+、-的前一个字符(跳过空格,当前一个字符不是运算符时用‘0’表示)为‘=’或‘(’，则为单目运算符。中缀算术表达式求值中缀算术表达式求值使用两个栈，操作符栈OPTR(operator)，操作数栈OPND(operand)，对中缀表达式求值的一般规则：(1)建立并初始化OPTR栈和OPND栈，然后在OPTR栈中压入一个‘=’。(2)从输入流获取一字符ch,并跳过空格及回车。(3)取出OPTR的栈顶OPTR_top。(4)当OPTR_top!=‘=’或ch!=‘=’时,循环执行以下工作,否则结束算法。此时在OPND栈的栈顶得到运算结果。

while(OPTR_top!=‘=’

||ch!=‘=’){

①若ch不是操作符，则将字符放回输入流(cin.putback)，读操作数newoperand并进OPND栈，并读入下一字符(跳过空格及回车)送入ch；②若ch是操作符，比较icp(ch)的优先级和isp(OPTR_top)的优先级：

若isp(OPTR_top)<icp(ch)，则ch进OPTR栈，从中缀表达式取下一字符(跳过空格及回车)送入ch；

若isp(OPTR_top)>icp(ch)，则从OPND栈退出a2和a1，从OPTR栈退出θ,形成运算指令(a1)θ(a2)，结果进OPND栈；

若isp(OPTR_top)==icp(ch)且ch==

“)”，则从OPTR栈退出栈顶的“(”，对消括号，然后从中缀表达式取下一字符送入ch。

③取出OPTR的栈顶OPTR_top。}2023/2/5443．2栈的应用举例

例1数制转换问题

辗转相除法如图所示：

算法描述：

#defineLength10voidconversion(intN，intr){intS[Length],top;//定义一个顺序栈

intx;top=-1;//初始化栈

while(N){S[++top]=N%r;//余数入栈

N=N/r;

//商作为被除数继续

}while(top!=-1)

//出栈输出

{x=s[top--];printf(“%d”,x);}}算法描述#defineLength10voidconversion(intN，intr){

intS[Length],top;//定义一个顺序栈

intx;top=-1;//初始化

while(N)

{

S[++top]=N%r;

//余数入栈

N=N/r;//商作为被除数继续

}

while(top!=-1)//出栈输出

{

x=s[top--];

printf(“%d”,x);}}例2检查一个表达式中的括号是否配对#defineSTRLEN255Boolcheak()

{charS[STRLEN];//初始化字符栈

inttop=-1;

charch=’#’

while(ch!=’\n’)//重复从键盘读字符，直到读到回车换行符

{scanf(“%c”,&ch);

switch(ch)//根据读入字符的不同情况分别处理

{case’(’:

{S[++top=ch;break;}

例2续case’[’://ch是’(’或’[’时，入栈

{S[++top=ch;break;}case’)’://处理ch=’)’时的情况

{if(S[top]==’(’)top--;

elseif(S[top]==’[’)returnERROR;break;

}case’]’://处理ch=’]’时的情况

{if(S[top]==’[’)top--;

elseif(S[top]==’(’)returnERROR;break;

}}if(top<0)returnTRUE;//栈空时返回真，否则返回假

elsereturnERROR;}//算法结束例3表达式求值算法

OperandTypeExpressionEvaluate()//从键盘输入中缀表达式，计算其值InitStack(OPTR);Push(OPTR,‘#’);//初始化运算符栈InitStack(OPND);//初始化操作数ch=getchar();while(ch!=‘#‘&&GetTop(OPTR)!=‘#‘)//逐个读字符ch且不等于#

{if(!in(ch,OP))

Push(OPND,ch);//不是运算符入操作数栈

else{switch()//是运算符时分别做不同处理

{case‘<‘: //ch的优先级高于栈顶运算符的优先级

{Push(OPTR,ch);break;}例3续case‘=’://ch的优先级等于栈顶运算符的优先级

{Pop(OPTR,c);breck;}case‘>’://ch的优先级低于栈顶运算符的优先级

{Pop(OPTR,theta);

Pop(OPND,x);Pop(OPND,y);//弹出两个操作数Push(OPND,Operate(x,theta,y);//计算、入操作数栈

}ch=getchar();//读下一个字符ch

}

Pop(OPND,x);returnx;//返回结果

}//算法结束2023/2/550例4、后缀表达式求值。

OperandTypeexprEvaluatel(charA[])

//本函数返回由后缀表达式A表示的表达式运算结果{InitStack(S);ch=*A++;while(ch!=’#’){if(!In(ch,OP)Push(S,ch);//读入的字符是操作数时入栈

else//是运算符，取出两个操作数

{Pop(S,x);Pop(S,y);switch(ch)//对两个操作数进行相应计算

{case’+’

：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);//计算结果入栈

}ch=*A++;

//读下一个字符

}Pop(S,c);returnc;

//

返回结果

}

//算法结束2023/2/551例5、利用栈实现递归函数计算n!

设f(n)=n!,求f(n)可以递归地定义为：

f(n)=1

n=0时//递归终止条件

f（n）=n*f(n-1)n>0时//递归步骤递归函数：

intfact(intn) {if(n==0)return1; elsereturn(n*fact(n-1)); }2023/2/552例:利用迭代实现递归函数计算n!

Intfact(intn,stack<int>&s){While(n>1)s.puch(n--)Intresult=1;Intval;While(s.pop(val))result=result*val;Return}2023/2/553例6

汉诺塔问题算法

voidhanoi(intn,charx,chary,charz)//将x柱上n个盘子借助y柱移到z柱上

{if(n==1)move(x,1,z);//将x柱上编号为1的盘子移动到z柱上

else{hanio(n-1,x,z,y);//将x柱上的n-1个盘子移动到y柱上

move(x,n,z);//将x柱上编号为n的盘子移动到z上

hanio(n-1,y,x,z);//将y柱上的n-1个盘子移动到z柱上

}}Section2

Queue队列(

Queue)定义队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,FirstInFirstOut)a0

a1

a2

an-1frontrearADTQueue{

数据对象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

约定其中a1

端为队列头，an

端为队列尾基本操作：队列的抽象数据类型定义}

ADTQueue队列的基本操作：InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&x)ClearQueue(&Q)DeQueue(&Q,&x)EnQueue(&Q,x)InitQueue(&Q)

操作结果：构造一个空队列Q。

DestroyQueue(&Q)

初始条件：队列Q已存在。

操作结果：队列Q被销毁，

不再存在。

QueueEmpty(Q)

初始条件：队列Q已存在。

操作结果：若Q为空队列，则

返回TRUE，否则

返回FALSE。

QueueLength(Q)

初始条件：队列Q已存在。

操作结果：返回Q的元素个

数，即队列的长

度。

GetHead(Q,&x)

初始条件：Q为非空队列。

操作结果：用x返回Q的队头

元素。a1a2an……

ClearQueue(&Q)

初始条件：队列Q已存在。

操作结果：将Q清为空队列。

EnQueue(&Q,x)

初始条件：队列Q已存在。

操作结果：插入元素x为Q的

新的队尾元素。a1a2anx……

DeQueue(&Q,&x)

初始条件：Q为非空队列。

操作结果：删除Q的队头元

素，并用x返回

其值。a1a2an……

循环队列

(CircularQueue)队列的进队和出队(C语言版)

frontrear空队列frontrearA进队AfrontrearB进队ABfrontrearC,D进队ABCDfrontrearA退队BCDfrontrearB退队CDfrontrearE,F,G进队CDEFGCDEFGfrontrearH进队,溢出队列的进队和出队原则

进队时将新元素按

rear指示位置加入再将队尾指针先进一rear=rear+1。

出队时将下标为

front的元素取出,再将队头指针先进一front=front+1。

队满时再进队将溢出出错；队空时再出队将队空处理。解决办法之一：将队列元素存放数组首尾相接，形成循环(环形)队列。

01234567front01234567front01234567frontrearAABCrearrear空队列A进队B,C进队0123456701234567A退队B退队01234567D,E,F,G,H,I进队frontBCrearAfrontBCrearfrontCrearDEFGHI队列存放数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;队列初始化：front=rear=0;队空条件：front

==

rear;队满条件：(rear+1)%maxSize==front

循环队列(CircularQueue)#defineMAXQSIZE100//最大队列长度

typedefstruct{

QElemType*base;//动态分配存储空间

intfront;//头指针，若队列不空，

//指向队列头元素

intrear;//尾指针，若队列不空，指向

//队列尾元素的下一个位置

}SqQueue;循环队列——顺序映象

StatusInitQueue(SqQueue&Q){//构造一个空队列QQ.base=(ElemType*)malloc

(MAXQSIZE*sizeof(ElemType));

if(!Q.base)exit(OVERFLOW);//存储分配失败

Q.front=Q.rear=0;

returnOK;

}StatusEnQueue(SqQueue&Q,ElemTypee){//插入元素e为Q的新的队尾元素

if((Q.rear+1)%MAXQSIZE==Q.front)

returnERROR;//队列满

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;

returnOK;}

StatusDeQueue(SqQueue&Q,ElemType&e){

//若队列不空，则删除Q的队头元素，

//用e返回其值，并返回OK;否则返回ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;

returnOK;}队列的进队和出队(C++语言版)

frontrear空队列frontrearA进队AfrontrearB进队ABfrontrearC,D进队ABCDfrontrearA退队BCDfrontrearB退队CDfrontrearE,F,G进队CDEFGCDEFGfrontrearH进队,溢出队列的进队和出队原则

进队时队尾指针先进一rear=rear+1，

再将新元素按

rear指示位置加入。

出队时队头指针先进一front=front+1，再将下标为

front的元素取出。

队满时再进队将溢出出错；队空时再出队将队空处理。解决办法之一：将队列元素存放数组首尾相接，形成循环(环形)队列。

队列存放数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;队列初始化：front=rear=0;队空条件：front

==

rear;队满条件：(rear+1)%maxSize==front

循环队列(CircularQueue)01234567front01234567front01234567frontrearAABCrearrear空队列A进队B,C进队0123456701234567A退队B退队01234567D,E,F,G,H进队frontBCrearAfrontBCrearfrontCrearDEFGHtemplate<classType>classQueue{ private:

intrear,front;

Type*elements;

intmaxSize;public:Queue(intsz=10);~Queue(){delete[]elements;

}

intEnQueue(Typex);

intDeQueue(Type&x);

intGetFront(Type&x);

voidMakeEmpty(){

front=rear;

}

intIsEmpty()const

{returnfront==rear;}

intIsFull()const{return(rear+1)%maxSize==front;}

intLength()const{return(rear-front+maxSize)%maxSize;}}template<classType>Queue<Type>::Queue(intsz){front=0;rear=0;maxSize=sz;elements=newType[maxSize]; }template<classType>intQueue<Type>::EnQueue(Typex){if(IsFull())return0;

rear=(rear+1)%MaxSize; elements[rear]=x;return1; }template<classType>intQueue<Type>::DeQueue(Type&x){if(IsEmpty())return

0; front=(front+1)%MaxSize;

x=elements[front];

return1;}template<classType>intQueue<Type>::GetFront(Type&x){if(IsEmpty())return0; x=elements[(front+1)%MaxSize];Return1;}队列的链接表示—链式队列

(C++语言版)

队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为front==NULLfrontreartemplate<classType>classQueue;template<classType>classQueueNode{ friendclassQueue<Type>;private:

Typedata; QueueNode<Type>*link;public:QueueNode(Typed,QueueNode<Type>*l=NULL){data=d;link=l;}};

template<classType>classQueue{private:

QueueNode<Type>*front,*rear;public:Queue(){rear=NULL;front=NULL;}

~Queue();

voidEnQueue(Typex);intDeQueue(Type&x);

intGetFront(Type&x);

voidMakeEmpty();//实现与~Queue()同

intIsEmpty()const

{returnfront==NULL;

}

};

template<classType>Queue<Type>::~Queue(){QueueNode<Type>*p;

while(front!=NULL){p=front;front=front->link;

deletep;}}template<classType>voidQueue<Type>::EnQueue(Typex){if(front==NULL)front=rear=newQueueNode<Type>(x);

else{rear->link=newQueueNode<Type>(x);

rear=rear->link;

}}template<classType>intQueue<Type>::DeQueue(Type

&x){

if(IsEmpty())return0;QueueNode<Type>*p=front; front=front->link;x=p->data;

deletep;

return1; }template<classType>intQueue<Type>::GetFront(Type

&x){if(IsEmpty())return0; x=front->data;return1;}

显示杨辉三角形的算法VoidyanghuiTriangle(intn){//结果显示三角形的第1行—第n行linkQueue<int>q;ints,t;q.InQueue(1);q.InQueue(1);

//存储第1行的两个元素的值

cout<<1<<“\t”<<1;

//显示第1行for(inti=2;i<=n;

i++){//依次显示三角形的第2行到第n行

cout<<endl;

q.InQueue(1);

//第i行的第1个元素值为1cout<<1<<“\t”

//显示第i行的第1个元素

q.OutQueue(s);

//取第i-1行的第1个元素

显示杨辉三角形的算法（续）for(intj=2;j<=i;j++){

q.OutQueue(t);

//取第i-1行的第j个元素q.InQueue(s+t);

//s+t为第i行第j个元素的值

cout<<s+t<<“\t”;

//显示第i行第j个元素的值

s=t:}q.InQueue(1);//第i行第i+1个元素的值为1

cout<<1;

//显示第i行第i+1个元素的值}

cout<<endl;

}

Section3

String串的定义n(n>=0)个字符的有限序列S=‘a1,a2,……,an’

串名:s

串值:ai(1<=i<=n)

串长:n术语空串n=0的串子串串中若干相邻字符组成的子序列主串包含子串的串空格串仅含有空格字符的串(n不为0)串相等设s1=‘a11,…,an1’s2=‘a12,…,an2’

若n1=n2且ai1=ai2（1<=i<=n1)

则s1=s2

串的抽象数据类型ADTString{

数据对象：D＝{ai|ai∈CharacterSet,i=1,2,...,n,n≥0}数据关系：R1＝{<ai-1,ai>|ai-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)}ADTString

StrAssign(&T,chars)

初始条件：chars是字符串常量

操作结果：把chars赋为T的值

StrCopy(&T,S)

初始条件：串S存在

操作结果：由串S复制得串T

DestroyString(&S)

初始条件：串S存在

操作结果：串S被销毁

StrEmpty(S)

始条件：串S存在

操作结果：若S为空串，则返回

TRUE，否则返回

FALSE

表示空串，空串的长度为零

StrCompare(S,T)

初始条件：串S和T存在

操作结果：若ST，则返回值

0

若ST，则返回值

0

若ST，则返回值

0例如：StrCompare(data,state)<0StrCompare(cat,case)>0

StrLength(S)

初始条件：串S存在

操作结果：返回S的元素个数，

称为串的长度

Concat(&T,S1,S2)

初始条件：串S1和S2存在

操作结果：用T返回由S1和S2

联接而成的新串例如：

Concate(T,man,kind)

求得T=mankind

SubString(&Sub,S,pos,len)初始条件：

串S存在，1≤pos≤StrLength(S)

且0≤len≤StrLength(S)-pos+1操作结果：

用Sub返回串S的第pos个字符起长度为len的子串例如：

SubString(sub,commander,4,3)

求得sub=manSubString(sub,commander,1,9)求得sub=commanderSubString(sub,commander,9,1)求得sub=r子串为“串”中的一个字符子序列SubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置和子串长度之间存在约束关系长度为0的子串为“合法”串

Index(S,T,pos)

初始条件：串S和T存在，T是非空串，

1≤pos≤StrLength(S)

操作结果：若主串S中存在和串T值

相同的子串,则返回它在主

串S中第pos个

字符之后第一次出现的位

置；否则函数值为0

假设S=abcaabcaaabc,T=bca

Index(S,T,1)=2Index(S,T,3)=6Index(S,T,8)=0

“子串在主串中的位置”意指子串中的第一个字符在主串中的位序Replace(&S,T,V)

初始条件：串S,T和V均已存在，

且T是非空串

操作结果：用V替换主串S中出现

的所有与（模式串）T

相等的不重叠的子串假设S=abcaabcaaabca，T=bca若V=

x，则经置换后得到

S=axaxaax若V=bc，则经置换后得到

S=abcabcaabc

StrInsert(&S,pos,T)

初始条件：串S和T存在，

1≤pos≤StrLength(S)＋1

操作结果：在串S的第pos个字符之前插入串T例如：S=chater，T=rac，则执行StrInsert(S,4,T)之后得到

S=character

StrDelete(&S,pos,len)

初始条件：串S存在

1≤pos≤StrLength(S)-len+1

操作结果：从串S中删除第pos个字符

起长度为len的子串

ClearString(&S)

初始条件：串S存在

操作结果：将S清为空串

对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。

gets(str)输入一个串；

puts(str)

输出一个串；

strcat(str1,str2)串联接函数；

strcpy(str1,str2,k)串复制函数；

strcmp(str1,str2)串比较函数；

strlen(str)求串长函数；例如：C语言函数库中提供下列串处理函数：在上述抽象数据类型定义的13种操作中串赋值StrAssign、等六种操作串复制Strcopy、构成串类型串比较StrCompare、的最小操作求串长StrLength、子集串联接Concat求子串SubString

例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。

StrCompare(SubString(S,i,StrLength(T)),T)?

0

S串T串

T串iposn-m+1算法的基本思想为：intIndex(StringS,StringT,intpos){

//T为非空串。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在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

returni;

}//while

}//if

return0;//S中不存在与T相等的子串}//Index

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。

串的基本操作和线性表有很大差别。

在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。

在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。串的表示和实现一、串的定长顺序存储表示二、串的堆分配存储表示三、串的块链存储表示

#defineMAXSTRLEN255//用户可在255以内定义最大串长

typedef

unsignedcharSstring[MAXSTRLEN+1];//0号单元存放串的长度一、串的定长顺序存储表示

按这种串的表示方法实现的串的运算时，其基本操作为

“字符序列的复制”。

串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断”。特点:

typedefstruct{char*ch;

//若是非空串，则按串长分配存储区，

//否则ch为NULL

intlength;//串长度

}HString;二、串的堆分配存储表示

通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。

C语言中的串以一个空字符为结束符，串长是一个隐含值。

这类串操作实现的算法为：先为新生成的串分配一个存储空间，然后进行串值的复制。三、串的块链存储表示也可用链表来存储串值，由于串的数据元素是一个字符，它只有8位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。存储密度

=数据元素所占存储位实际分配的存储位

#defineCHUNKSIZE80

//可由用户定义的块大小

typedefstructChunk{

//

结点结构

charch[CUNKSIZE];

structChunk*next;

}Chunk;

typedefstruct{//串的链表结构

Chunk*head,*tail;//串的头和尾指针

intcurlen;//串的当前长度

}LString;

这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。串的模式匹配算法初始条件：串S和T存在，T是非空串，

1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串返回它在主串S中第pos个字符之后第一次出

现的位置；否则函数值为0。首先，回忆一下串匹配(查找)的定义:INDEX(S,T,pos)

下面讨论以定长顺序结构表示串时的几种算法。一、简单算法二、首尾匹配算法三、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法intIndex(SStringS,SStringT,intpos){

//返回子串T在主串S中第pos个字符之后的位置。若不存在，

//则函数值为0。其中，T非空，1≤pos≤StrLength(S)。

i=pos;j=1;

while(i<=S[0]&&j<=T[0]){

if(S[i]==T[j]){++i;++j;}//继续比较后继字符

else

{i=i-j+2;j=1;}

//指针后退重新开始匹配

}

if(j>T[0])returni-T[0];

elsereturn0;}//Index一、