第 3 章特殊线性表 栈、队列和串是3种特殊的线性表,其中,栈和队列都是操作特殊的线 性表,串是一种数据对象和操作都特殊的线性表。本章将分别讨论这3种 特殊线性表的顺序存储结构、链式存储结构及基本操作的实现。 3.栈 1 3.1.1 栈的定义和基本操作 1. 栈的定义 栈(stack)是一种特殊的线性表,它只允许在一端进行插入和删除操 作,允许插入和删除的一端称栈顶,另一端称为栈底。处于栈顶位置的元 素称为栈顶元素。栈中含有元素的个数称为栈长,含有0个数据元素的栈 称为空栈。通过栈的定义可以看出,栈的特点是后进先出(LIFO)或先进 后出(FILO), 因此,栈又称后进先出的线性表。 下面通过例子说明栈结构的特点。假设有一个很窄的死胡同,胡同里 能容纳若干辆汽车,胡同的宽度一次只允许一辆车进出。现有五辆车,编 号分别为A、B、C、D、E。按编号的顺序依次进入死胡同,如图3. 1所示。 此时若编号为D的车要退出胡 同,则必须等编号为E的车退 若编号为A的车图3.死胡同示意图 出后才可以; 1 要退出胡同,则必须等编号为 E、D、C、B的车都依次退出后才可以。这个死胡同就可以比作一个栈,编 号为A的车的位置称为栈底,编号为E的车的位置称为栈顶,车进出胡同 可以看作栈的插入和删除操作,插入和删除操作都在栈顶进行。 习惯上,把栈的插入操作称为入栈(或进栈、压栈), 把栈的删除操作称 为出栈(或退栈、弹栈)。 2. 栈的基本操作 栈的基本操作主要有以下7种。 数据结构( C 语言版)( 第4版) (1)初始化操作InitStack(S), 用于初始化一个空栈S。 (2)求栈长操作GetLen(S), 用于返回栈S的元素个数,即栈长。 (3)取栈顶元素操作GetTop(S,e), 通过e带回栈S的栈顶元素的值。 (4)入栈操作Push(S,x), 用于将值为x元素压入栈S,使x成为新的栈顶元素。 (5)出栈操作Pop(S,e), 用于将非空栈的栈顶元素删除,同时通过e带回栈顶元素的 值,新的栈顶元素为栈S中原栈顶元素的前一个元素。 (6)判栈空操作EmptyStack(S), 用于判断栈S是否为空,若栈S为空,则返回1,否 则返回0。 (7)输出栈操作List(S), 用于依次输出栈S中的所有元素的值。 栈是一个线性表,它也有顺序存储和链式存储这两种存储结构,分别称为顺序栈和 链栈。 3.1.2 顺序栈表示及实现 1. 顺序栈 栈的顺序存储结构称为顺序栈,它利用一组地址连续的存储单元依次存放从栈底到 栈顶的数据元素,同时利用一个变量记录当前栈顶的位置(下标或指针), 称为栈顶指针, 栈顶指针并不一定是指针变量,也可以是下标变量。为了用C语言方便描述,在此约定: 用下标变量记录栈顶的位置,栈顶指针始终指向栈顶元素的下一个单元;在初始化栈时, 栈顶指针值为0,表示空栈;在栈中插入新的元素后,栈顶指针增1;在栈中删除栈顶元素 后,栈顶指针减1。 变量t图3. 假设用一维数组S[5]表示一个顺序栈, op为栈顶指针,2所示为这个顺序 栈的几种状态。 图3.顺序栈S的几种状态 2 图3.表示顺序栈为空栈,这也是初始化操作的结果,此时栈顶指针t0。 2(b) 2(a) op= 2(a) op= 图3.表示在图3.的状态下元素A入栈后的状态,此时栈顶指针t1。 图3.c) 2(的状态下元素B、C、D、此时栈顶指 2(表示在图3.b) E依次入栈后的状态, 针top=5,表示栈满。 top= 图 3。 3.2(d) 2(的状态下元素E、D依次出栈后的状态,此时栈顶指针 表示在图3.c) 第3 章　特殊线性表　 51 图3.2(e)表示在图3.2(d)的状态下元素C、B、A 依次出栈后的状态,此时栈顶指针 top=0,表示栈空。 由上面的例子可知,在用数组表示栈时,无论数组定义得多么大,栈在使用过程中都 有可能会出现栈满的情况。当栈满时,C语言中定义的数组是无法扩充空间的,因此在 C语言中使用动态分配的一维数组,即在初始化时先用函数malloc()为栈分配一个初始 容量,在操作过程中,若栈的空间不足,则用函数realloc()重新申请一个足够大的空间。 顺序栈的类型定义如下: #define INITSIZE 100 /*存储空间的初始分配量*/ typedef int ElemType; /*数据元素类型*/ typedef struct { ElemType *base; /*存放元素的动态数组起始地址*/ int top; /*栈顶指针*/ int stacksize; /*当前栈空间的大小*/ }SeqStack; 其中,INITSIZE是为栈分配的存储空间的初始量;base是栈空间的起始地址,也称栈底 指针,它始终指向栈底的位置;top是栈顶指针,指向栈顶元素的下一个单元,其初值为0, 作为栈空的标记;stacksize是当前栈可以使用的最大容量。top==stacksize时表示栈 满,此时若有元素入栈,则需要增加存储空间,否则将产生(上)溢出错误;top==0时表 示栈空,此时若进行出栈操作,则将产生(下)溢出错误。 2.顺序栈基本操的实现 (1)初始化操作 创建一个空栈S。 算法思路:分配存储空间,将栈顶指针初始化为0,栈空间的大小为初始分配量。 void InitStack(SeqStack*S) { S->base=(ElemType *)malloc(INITSIZE*sizeof(ElemType));/*申请存储空间*/ S->top=0; /*栈顶指针初始值为0*/ S->stacksize=INITSIZE; /*栈容量为初始值*/ } (2)求栈长操作 返回栈S的元素个数,即栈的长度。 算法思路:栈S的长度为S->top。 int GetLen(SeqStack *S) { return (S->top); } (3)取栈顶元素操作 取出栈S的栈顶元素的值。 算法思路:若栈不为空,则将栈顶元素值送到指定的内存单元,S->top的值不变。 52 数据结构(C 语言版)(第4 版) int GetTop(SeqStack *S,ElemType *e) { if(S->top==0) return 0; /*栈空,返回0*/ *e=S->base[S->top-1]; /*栈顶元素值存入指针e 所指向的内存单元*/ return 1; /*取栈顶元素成功,返回1*/ } (4)压栈操作 将值为x的数据元素插入栈S,使之成为新的栈顶元素。 算法思路:若栈满,则增加栈容量。先将x存入S->top所指的内存单元,然后将 栈顶指针S->top增1。 int Push(SeqStack *S,ElemType x) { if(S->top>=S->stacksize) /*若栈满,则增加一个存储单元*/ { S->base=(ElemType *)realloc(S->base,(S->stacksize+1)*sizeof(ElemType)); if(!S->base) return 0; /*空间分配不成功,返回0*/ S->stacksize++; } S->base[S->top++]=x; /*插入元素后,栈顶指针后移*/ return 1; } (5)弹栈操作 取出栈S的栈顶元素值,同时栈顶指针减1。 算法思路:若栈不为空,则先将栈顶指针S->top减1,然后将S->top单元的元 素值存入指定的内存单元。 int Pop(SeqStack *S,ElemType *e) { if(S->top==0) return 0; /*栈空,返回0*/ *e=S->base[--S->top]; /*先将栈顶指针减1,再取顶元素值*/ return 1; /*弹栈成功,返回1*/ } (6)判栈空操作 判断栈S是否为空。 算法思路:栈S为空的条件是S->top的值为0。 int EmptyStack(SeqStack *S) { if(S->top==0) return 1; /*栈为空则返回1,否则返回0*/ else return 0; } (7)输出栈操作 输出栈S自栈顶到栈底的元素值。 算法思路:依次输出下标从S->top-1到0的元素值。 void List(SeqStack *S) 第3 章　特殊线性表　 53 { int i; for(i=S->top-1;i>=0;i--) printf("%4d ",S->base[i]); printf("\n"); } 由于栈结构具有后进先出的固有特性,因此栈成为程序设计中的有用工具。栈在计 算机语言处理和将递归算法改为非递归算法等方面起着非常重要的作用。 【例3.1】 编写算法,将十进制正整数m 转换成n(2≤n≤9)进制数。 算法思路:利用“辗转相除法”,即不断地用n除以m,直到m=0为止,将各次除得 的余数倒排。在此,将十进制数m 除以n所得的各位余数入栈,然后依次出栈并输出 即可。 void Conversion(int m,int n) { SeqStack S; InitStack(&S); while(m!=0) { Push(&S,m%n); m=m/n;} /*余数入栈,商作为下一个被除数*/ List(&S); /*输出*/ } 【例3.2】 编写算法,用非递归方法计算n!。 算法思路:设置一个栈,将n~1依次入栈,然后依次出栈并乘到初值为1的变量f上 即可。 long Fac(int n) { long f=1; ElemType x; SeqStack S; InitStack(&S); /*初始化空栈*/ while(n>0) { Push(&S,n);n--;} /*n~1 依次入栈*/ while(!EmptyStack(&S)) { Pop(&S,&x);f*=x;} /*1~n 依次出栈并乘到初值为1 的变量f 上*/ return f; } 【例3.3】 利用一个栈实现下列函数的非递归计算。 Pn(x)= 1 n=0 2x n=1 2xPn-1(x)-2(n-1)Pn-2(x) n>1 ì . í .. .. 算法思路:设置一个栈,用于保存n和对应的Pn(x),栈中相邻元素的Pn(x)有上述 关系。然后一边出栈一边计算Pn(x),直到栈空时,计算的Pn(x)即为所求。 typedef struct { int no; /*n 值*/ double val; /*P 值*/ 54 数据结构(C 语言版)(第4 版) }ElemType; /*栈中的数据元素为结构体类型*/ double P(int n,double x) { double fv1,fv2; int i; SeqStack S; if(n==0) return 1; if(n==1) return 2*x; InitStack(&S); fv1=1;fv2=2*x; for(i=n;i>=2;i--) S.base[S.top++].no=i; while(!EmptyStack(&S)) /*若栈不为空,则计算各个P 值*/ { S.top--; S.base[S.top].val=2*x*fv2-2*(S.base[S.top].no-1)*fv1; fv1=fv2; fv2=S.base[S.top].val; } return fv2; /*返回最终结果*/ } 【例3.4】 设计一个算法,判断一个表达式中括号“(”与“)”、“[”与“]”、“{”与“}”是否 匹配。若匹配,则返回1,否则返回0。 算法思路:设置一个栈S,用i(初值为0)扫描表达式exps,当遇到“(”“[”“{”时,将 其入栈;若遇到“}”“]”“)”时,判断栈顶元素是否为相匹配的括号,若不匹配,则表明表达 式有误;若表达式扫描完成后栈空,则表明表达式括号匹配。 typedef char ElemType; /*数据元素类型为字符型*/ int Match(ElemType *exps) { int i=0,nomatch=0; SeqStack S; ElemType x; InitStack(&S); /*初始化空栈*/ while(!nomatch&&exps[i]!='\0') { switch(exps[i]) { case '(': /*当前字符为"("时,将其入栈*/ case '[': /*当前字符为"["时,将其入栈*/ case '{':Push(&S,exps[i]);break; /*当前字符为"{"时,将其入栈*/ case ')':GetTop(&S,&x); if(x=='(') Pop(&S,&x); else nomatch=1; break; /*判断栈顶元素是否为相匹配的括号"("*/ case ']':GetTop(&S,&x); if(x=='[') Pop(&S,&x); else nomatch=1; break; /*判断栈顶元素是否为相匹配的括号"["*/ 第3 章　特殊线性表　 55 case '}':GetTop(&S,&x); if(x=='{') Pop(&S,&x); else nomatch=1; /*判断栈顶元素是否为相匹配的括号"{"*/ } i++; } if(EmptyStack(&S)&&!nomatch) return 1; /*栈空且符号匹配,返回1*/ else return 0; /*否则返回0*/ } * 3.1.3 链栈表示及实现 1.链栈 栈的链式存储结构称为链栈。链栈实际上是一个仅在表头进行操作的单链表,这种 单链表的第一个结点称为栈顶结点,最后一个结点称为栈底结点,头指针指向栈顶结点 (不带头结点)或头结点(带头结点)。图3.3是一个带头结点的链栈的示意图。本节讨论 的链栈均指带头结点的链栈。 图3.3 链栈示意图 链栈的结点类型定义如下: typedef int ElemType; /*数据元素类型*/ typedef struct node { ElemType data; /*数据域*/ struct node *next; /*指针域*/ }LinkStack; 这实质上就是单链表的结点类型定义。 2.链栈基本操作的实现 下面介绍链栈基本操作的实现。 (1)初始化操作 创建一个带头结点的空栈S。 算法思路:创建头结点并将头结点指针域置为空。 LinkStack *InitStack(void) { LinkStack *S; S=(LinkStack *)malloc(sizeof(LinkStack)); S->next=NULL; 56 数据结构(C 语言版)(第4 版) return S; } (2)取栈顶元素操作 取出栈S的栈顶元素值。 算法思路:若栈不为空,则将栈顶结点的值送到指定的内存单元,栈顶结点不变。 int GetTop(LinkStack *S,ElemType *e) { if(S->next==NULL) return 0; /*若栈空,返回0*/ *e=S->next->data; /*否则,取栈顶元素值*/ return 1; } (3)求栈长操作 返回栈S的元素个数,即栈的长度。 其设计思路与单链表的求表长操作相同。 int GetLen(LinkStack *S) { LinkStack *p; int i; p=S->next; i=0; while(p!=NULL) { i++; p=p->next;} return i; } (4)入栈操作 将值为x的数据元素插入栈S,使x成为新的栈顶元素。 算法思路:先创建一个新结点,其数据域的值为x,然后将该结点插入头结点之后作 为栈顶结点。 int Push(LinkStack *S,ElemType x) { LinkStack *p; p=(LinkStack *)malloc(sizeof(LinkStack)); /*申请存储空间*/ if(!p) return 0; /*若空间申请失败,则返回0*/ p->data=x; p->next=S->next; /*插入头结点之后*/ S->next=p; return 1; } (5)出栈操作 删除栈S的栈顶元素。 算法思路:若栈不为空,则先将栈顶结点的值送到指定的内存单元,然后删除栈顶 结点。 int Pop(LinkStack *S,ElemType *e) 第3 章　特殊线性表　 57 { LinkStack *p; if(S->next==NULL) return 0; /*栈空,删除失败,返回0*/ p=S->next; *e=p->data; /*栈顶结点值送到指针e 所指向的单元*/ S->next=p->next; free(p); return 1; /*出栈成功,返回1*/ } (6)判栈空操作 判断栈S是否为空。 算法思路:栈空的条件是头结点的指针域为空。 int EmptyStack(LinkStack *S) { if(S->next==NULL) return 1; /*栈空则返回1,否则返回0*/ else return 0; } (7)输出栈 输出栈S自栈顶到栈底的元素值。 其设计思路与单链表的输出操作相同。 void List(LinkStack *S) { LinkStack *p; p=S->next; while(p!=NULL) { printf("%4d ",p->data); p=p->next; } printf("\n"); } 【例3.5】 编写算法,利用栈将带头结点的单链表逆置。 方法一:把单链表S1看成一个链栈,将从S1出栈的元素依次入栈S2,直到S1为空 为止。此时S2就是S1的逆置。 void TurnLink1(LinkStack *S1,LinkStack *S2) { ElemType x; while(S1->next!=NULL) { Pop(S1,&x); Push(S2,x); } } 方法二:将链表中的元素利用顺序栈交换顺序。 void TurnLink2(slink *head) 58 数据结构(C 语言版)(第4 版) { SeqStack S; slink *p; InitStack(&S); /*初始化空栈*/ p=head->next; while(p) {Push(&S,p->data);p=p->next;} /*链表中的元素依次入栈*/ p=head->next; while(!EmptyStack(&S)) {Pop(&S,&p->data);p=p->next;} /*栈中的元素依次出栈到链表中的对应结点上*/ } 当然,该算法也可以使用链栈实现。 【例3.6】 设计一个算法,判断一个字符串是否对称。若是,则返回1,否则返回0。 算法思路:先将长度为len的字符串的前半部分(str[0]~str[len/2-1])入栈,然后 用后半部分(str[(len+1)/2]~str[len-1])的字符依次与出栈的元素相比较;不相等时 返回0;若比较完毕且栈为空,则字符串对称。 typedef char ElemType; /*这里的ElemType 类型设定为char*/ int Symmetric(ElemType *str) { ElemType x,same=1; int len,i; LinkStack *S; S=InitStack(); /*初始化空栈*/ for(len=0;str[len]!='\0';len++); /*计算字符串长度*/ for(i=0;ibase=(ElemType *)malloc(MAXSIZE*sizeof(ElemType)); /*分配内存*/ Q->front=Q->rear=0; /*队头指针和队尾指针初始值都为0*/ } (2)求队列长操作 计算循环队列中数据元素的个数。 算法思路:根据循环队列的特点,有以下几种情况: 队列长度= 0 (front==rear) rear-front (rear>front) rear+MAXSIZE-front (rearrear-Q->front+MAXSIZE)%MAXSIZE); } (3)取队头元素操作 取出循环队列Q 的队头元素值。 算法思路:先判断队列是否为空,若不为空,则将队头元素值送到指定的内存单元。 int GetFront(CirQueue *Q,ElemType *e) { if(Q->front==Q->rear) return 0; /*队空,返回0*/ *e=Q->base[Q->front]; /*取队头元素*/ return 1; } (4)入队列操作 在循环队列Q 的队尾插入值为x的元素。 算法思路:先判断队列是否为满,若不为满,则先在队尾指针处存放x,然后将队尾 指针后移一个位置。 int EnQueue(CirQueue *Q,ElemType x) { if((Q->rear+1)%MAXSIZE==Q->front) return 0; /*队满,返回0*/ Q->base[Q->rear]=x; /*入队列*/ Q->rear=(Q->rear+1)%MAXSIZE; /*修改队尾指针*/ return 1; } 第3 章　特殊线性表　 63 (5)出队列操作 将循环队列Q 的队头元素删除。 算法思路:先判断队列是否为空,若不为空,则先将队头元素值送到指定的内存单 元,然后将队头指针后移一个位置。 int OutQueue(CirQueue *Q,ElemType *e) { if(Q->front==Q->rear) return 0; /*队空,返回0*/ *e=Q->base[Q->front]; /*取队头元素值*/ Q->front=(Q->front+1)%MAXSIZE; /*修改队头指针*/ return 1; } (6)判队空操作 判断循环队列Q 是否为空。 算法思路:循环队列Q 为空的条件是Q->front==Q->rear。 int EmptyQueue(CirQueue *Q) { if(Q->front==Q->rear) return 1; else return 0; } (7)输出操作 输出循环队列Q 从队头到队尾的所有元素值。 算法思路:依次输出下标自front至rear-1的元素值,修改循环变量i的方法是i= (i+1)%MAXSIZE。 void List(CirQueue *Q) { int i; i=Q->front; while(i!=Q->rear) { printf("%4d ",Q->base[i]); i=(i+1)%MAXSIZE; } } 【例3.7】 编写程序,从键盘输入一个整数序列a1,a2,…,an。若ai>0,则ai 入队列; 若ai<0,则队头元素出队列;当ai=0时算法结束。要求利用循环队列完成,并在异常情 况下(如队空)打印错误信息。 算法思路:先建立一个空的循环队列Q,然后通过循环接收用户输入的整数。若输 入的值大于0,则将该数入队列;若小于0,则出队列一个元素并输出;若等于0,则退出 循环。 void Fun(void) { CirQueue Q;ElemType x; InitQueue(&Q); 64 数据结构(C 语言版)(第4 版) printf("输入数据(0:结束):"); scanf("%d",&x); while(x!=0) /*当输入0 时退出循环,同时算法结束*/ { if(x>0) { if(!EnQueue(&Q,x)) { printf("队列满!\n");break;} } else if(!OutQueue(&Q,&x)) { printf("队列空!\n");break;} scanf("%d",&x); } } 3.2.3 链队列表示及实现 1.链队列 队列的链式存储结构称为链队列。链队列实际上是一个带头指针和尾指针的单链 表,这种单链表的第一个结点称为队头结点,最后一个结点称为队尾结点,尾指针始终指 向队尾结点。在带头结点的链队列中,头指针指向头结点;在不带头结点的链队列中,头 指针指向队头结点。图3.7是一个带头结点的链队列的示意图。 图3.7 带头结点的链队列示意图 链队列的类型定义如下: typedef int ElemType; /*数据元素类型*/ typedef struct node { ElemType data; /*数据域*/ struct node *next; /*指针域*/ }qlink; /*结点类型定义*/ typedef struct { qlink *front; /*队头指针*/ qlink *rear; /*队尾指针*/ }LinkQueue; /*链队列类型定义*/ 2.链队列基本操作的实现 下面介绍带头结点的链队列的基本操作的实现。 (1)初始化操作 建立空的链队列Q。 第3 章　特殊线性表　 65 算法思路:创建头结点,队头指针和队尾指针都指向它,并将其指针域置为空 (NULL)。 void InitQueue(LinkQueue *Q) { Q->front=Q->rear=(qlink *)malloc(sizeof(qlink)); /*创建头结点*/ Q->front->next=NULL; /*头结点指针域置为空*/ } (2)求队列长度操作 计算链队列Q 中数据元素的个数。 其设计思路与单链表的求表长操作相同。 int GetLen(LinkQueue *Q) { int i;qlink *p; p=Q->front->next;i=0; while(p!=NULL) { i++;p=p->next;} return i; } (3)判队空操作 判断链队列Q 是否为空。 算法思路:链队列Q 为空的条件是Q->front==Q->rear或Q->front-> next==NULL。 int EmptyQueue(LinkQueue *Q) { if(Q->front==Q->rear) return 1; /*队空的条件为front==rear*/ else return 0; } (4)取队头元素操作 取出链队列Q 的队头元素值。 算法思路:若链队列不为空,则将队头结点数据域值送到指定的内存单元。 int GetFront(LinkQueue *Q,ElemType *e) { if(Q->front==Q->rear) return 0; /*队空,返回0*/ *e=Q->front->next->data; return 1; } (5)入队列操作 在队列Q 中插入一个值为x的结点,使之成为新的队尾结点。 算法思路:先创建新结点,数据域值为x,指针域值为空(NULL),然后将新结点插入 尾结点之后,最后修改队尾指针,使其指向新插入的结点。 void EnQueue(LinkQueue *Q,ElemType x) 66 数据结构(C 语言版)(第4 版) { qlink *p; p=(qlink *)malloc(sizeof(qlink)); /*创建新结点*/ p->data=x; p->next=NULL; Q->rear->next=p; /*插入链队列的尾部*/ Q->rear=p; } (6)出队操作 删除链队列中的队头结点。 算法思路:若链队列不为空,则先将队头结点数据域值送到指定的内存单元,然后删 除队头结点。若删除结点为队尾结点,则需要修改队尾指针。 int OutQueue(LinkQueue *Q,ElemType *e) { qlink *p; if(Q->front==Q->rear) return 0; /*队空,返回0*/ p=Q->front->next; *e=p->data; Q->front->next=p->next; if(Q->rear==p) /*当队中只有一个元素时,出队后应重新修改队尾 指针rear*/ Q->rear=Q->front; free(p); return 1; } (7)输出队列操作 输出链队列从队头结点至队尾结点的数据域值。 其设计思路与单链表的输出操作相同。 void List(LinkQueue *Q) { qlink *p; p=Q->front->next; while(p!=NULL) { printf("%4d",p->data); p=p->next; } } 3.3 串 3.3.1 串的定义和基本操作 1.串的定义 串(string)又称字符串,是一种特殊的线性表,其特殊性体现在表中的每个数据元素 第3 章　特殊线性表　 67 都是一个字符,即串是由0个或多个字符组成的有限序列。一般记为 S="a1a2a3…an" (n≥0) 其中,S是串名,用双引号括起来的字符序列是串值,双引号本身不是串的内容,是串的定 界符。ai(1≤i≤n)代表一个字符,可以是字母、数字或其他字符。串中的字符个数n称为 串长,含有0个字符的串称为空串。 串中任意连续的字符所组成的子序列称为该串的子串,包含子串的串称为主串。字 符在串中的位序称为该字符在串中的位置。子串在主串中的位置是以子串的第一个字符 在主串中的位置表示的。若两个串的长度相等,并且各个对应位置上的字符都相同,则称 这两个串相等。假设S1、S2、S3为如下三个串: S1="data",S2="structure",S3="data structure" 则它们的长度分别为4、9、14,并且S1、S2是S3的子串,S1在S3中的位置是1,S2在S3 中的位置是6。 2.串的基本操作 串的基本操作主要有以下12种。 (1)初始化操作InitString(s),用于初始化一个空串s。 (2)串赋值操作StrAssign(s1,s2),用于将串常量s2赋给串变量s1。 (3)串复制操作Assign(s1,s2),用于将串变量s2的值赋给串变量s1。 (4)求串长操作Length(s),用于返回串s的长度。 (5)判串等操作Equal(s,t),用于判断串s和t的值是否相等,若相等则返回1,否则 返回0。 (6)串连接操作Concat(s,s1,s2),用于将串s2连接到串s1的后面,结果存到串 s中。 (7)取子串操作SubStr(s,i,j,t),用于将串s的从第i个字符开始的j个连续字符存 到t中。在此,1≤i≤Length(s),0≤j≤Length(s)-i+1。 (8)插入操作Insert(s,i,t),用于将串t插入串s的第i个字符之前。在此,1≤i≤ Length(s)+1。 (9)删除操作Delete(s,i,j),用于在串s中删除从第i个字符开始的长度为j的子串。 在此,1≤i≤Length(s),1≤j≤Length(s)-i+1。 (10)串查找操作Index(s,t,pos),用于从串s的第pos个字符开始查找串t首次出 现的位置。在此,1≤pos≤Length(s)。该操作也称为串的模式匹配,将在3.3.4节具体 介绍。 (11)替换操作Replace(s,i,j,t),用于将串s的从第i个字符开始的连续j个字符替 换成串t。在此,1≤i≤Length(s),1≤j≤Length(s)-i+1。 (12)输出操作List(s),用于输出串s的值。 串也是线性表,也有顺序存储和链式存储这两种存储结构,分别称为顺序串和链串。 68 数据结构(C 语言版)(第4 版) 3.3.2 顺序串表示及实现 1.顺序串 串的顺序存储结构称为顺序串,即串中的字符被依次存放在一组连续的存储单元中。 一般来说,一个字符占用1字节的存储空间,因此一个存储单元可以存储多个字符。例 如,一个32位的内存单元可以存储4个字符。串的顺序存储有两种格式:一种是每个存 储单元只存放一个字符,称为非紧缩格式;另一种是每个存储单元存放多个字符,称为紧 缩格式。假设一个存储单元占4字节,存放的起始地址为i,则串"DATASTRUCTURE" 的非紧缩格式存储和紧缩格式存储如图3.8和图3.9所示。 图3.8 非紧缩格式示例图3.9 紧缩格式示例 串的顺序存储还有两种方式:串的定长表示和串的顺序表表示。所谓串的定长表示 就是指预先定义一个固定的字符数组空间,例如: #define MAXSIZE 256 char string[MAXSIZE]; 其中,0号单元用于存放串长,因此这种表示法能存放的字符个数至多为255个,并且空 间不能扩充,目前基本不采用此法。由于串长无法预测,因此采用动态分配的一维数组存 储串值,即串的顺序表表示。下面仅介绍顺序表表示方法,读者可以自行用定长表示法完 成串的一些基本操作。顺序串的类型定义如下: #define INITSIZE 100 /*为串分配的存储空间的初始量*/ typedef struct { char *ch; /*串存放的起始地址*/ int length; /*串长*/ int strsize; /*当前为串分配的存储空间容量*/ }SeqStr; 其中,INITSIZE是为串分配的存储空间的初始量;ch是串存放的起始地址,串中的第i 个字符存储在ch[i-1]中;length是串长,最后一个字符的下标为length-1;strsize是当 前分配的存储空间容量,如果在操作过程中存储空间不足,则可以用函数realloc()进行 再分配,为顺序串增加存储空间。 2.顺序串基本操作的实现 (1)初始化操作 创建一个空串s。