int EmptyStack( DuStack *S, int i ) /*判栈空(栈号 i) */

{return (i == 0 && S->top[0] == -1|| i == 1 && S->top[1] == STACKSIZE) ; }

int FullStack( DuStack *S)

/*判栈满,满时肯定两头相遇*/ {return (S->top[0] == S-top1-1); }

void Push(DuStack *S, int i, ElemType x) /*进栈(栈号i) */ {if (FullStack( S ))

Error(\上溢、退出运行*/ if ( i == 0) S->Data[ ++ S->top0]= x; /*栈0入栈*/ if ( i == 1) S->Data[ -- S->top[1] ]= x; /* 栈1入栈*/ }

ElemType Pop(DuStack *S, int i) /*出栈(栈号i) */

{if (EmptyStack ( S,i) )

Error(\下溢退出*/ if( i==0 )

return ( S->Data[ S->top0--] );/*返回栈顶元素，指针值减1*/ if( i==1 )

return ( S->Data[ S->top[1] ++] ); /*该栈是以另一端为底的，所以指针加1*/ }

8．回文是指正读反读均相同的字符序列，如\和\均是回文，但\不是回文。设计一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 【算法源代码】

void sympthy(LinkList head, stack *s)/*判断长为n的字符串是否中心对称*/ { int i=1;

LinkList p=head->next;

while(i<=n/2) /* 前一半字符进栈*/ { push(s,p->data); p=p->next; }

if(n%2!==0) p=p->next;/* 奇数个结点时跳过中心结点*/ while(p&&p->data==pop(s)) p=p->next; if (p==NULL) printf(\链表中心对称\ else printf(\链表不是中心对称\} /* 算法结束*/

9．用标志位方式设计出在循环队列中进行插入和删除运算的算法。 【算法分析】

可引入标志位flag，且规定当flag=0时表示队列空，当flag=1时表示队列非空。同时设front，rear和MAXSIZE分别为队头指针，队尾指针和队列的长度。其中，队头指针指向队头元素所在的实际存储单元的前一个位置，队尾指针指向队尾元素所在的位置。从而可得队满的条件是：(rear==front)&&(flag==1) 【算法源代码】

int flag; /*设置全局变量flag作为标志位*/ enqueue(SqQueue*sq,ElemType x) {

/*将x插入循环队列sq中，sq具有队头和队尾指针*/ if((flag==1)&&(sq->rear==sq->front)) /*判断队满*/ printf(\ else

{sq->rear=(sq->rear+1)%MAXSIZE; sq->data[sq->rear]=x; } if(flag==0) flag=1;

17

}

ElemType dequeue(SqQueue*sq) /*删除队列sq的队头元素，并返回该元素*/ {ElemType x;

if(flag==0) printf(\ /*判断队空*/

else{sq->front=(sq->front+1)%MAXSIZE; x=sq->data[sq->front]; } if(sq->front==sq->rear) flag=0; return x; }

第4章 串

4.1 选择题

1．下面关于串的的叙述中，哪一个是不正确的？（ ） A）串是字符的有限序列 B）空串是由空格构成的串

C）模式匹配是串的一种重要运算

D）串既可以采用顺序存储，也可以采用链式存储 【答案】B

【解析】空串是不含任何字符的串，即空串的长度是零。空格串是由空格组成的串，其长度等于空格的个数。

2．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ） A）求子串 B）联接 C）匹配 D）求串长

【答案】C

3．若串s=\，其子串个数是（ ）

A）8 B）37 C）36 D）9 【答案】C

【解析】s的长度为8，长度为8的子串有1个，长度为7的子串有2个，长度为6的子串有3个，长度为5的子串有4个，?，长度为1的子串有8个，共有(1+8)*8/2=36个。

4．串的长度是指（ ）

A）串中所含不同字母的个数 B）串中所含字符的个数

C）串中所含不同字符的个数 D）串中所含非空格字符的个数 【答案】B

5．若串S1=\，S2=\，S3=\，S4=\，则执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2, '8'),length(S2)))其结果为（ ）

A）ABC###G0123 B）ABCD###2345 C）ABC###G2345 D）ABC###G1234 【答案】D 【解析】函数concat(x,y)返回x和y的连接串，substr(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，length(s)返回串s的长度。replase(s,t,v)用v替换s中出现的所有与t相等的子串,index(s,t,i)当s中存在与t值相同的子串时，返回它在s中的第i个字符之后第一次出现的位置。 substr(S1,length(S2),length(S3))=substr(S1,4,3)= \

replase(S1,substr(S1,length(S2),length(S3)),S3)=replase(S1, \substr(S4,index(S2, '8'),length(S2))=substr(S4,2,4)= \

18

concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2, '8'),length(S2)))=concat(\

4.2 填空题

1．空格串是指_____________，其长度等于_____________。 【答案】（1）由空格字符（ASCII值32）所组成的字符串 （2）空格个数

2．组成串的数据元素只能是_____________。 【答案】字符

【解析】串是一种特殊的线性表，其特殊性在于串中的元素只能是字符型数据。 3．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_____________。

【答案】O(m+n)

【解析】朴素的模式匹配（Brute－Force）时间复杂度是Ｏ（m*n），KMP算法有一定改进，时间复杂度达到Ｏ（m＋n）。

4．两个字符串相等的充分必要条件是_____________。

【答案】两串的长度相等且两串中对应位置上的字符也相等。

5．一个字符串中_____________称为该串的子串 。 【答案】任意个连续的字符组成的子序列

4.3 判断题

1．KMP算法的特点是在模式匹配时指示主串的指针不会变小（ ） 【答案】√

【解析】KMP算法的改进在于：每当一趟匹配过程中出现字符比较不相等时，不需回溯主串指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。

2．串是一种数据对象和操作都特殊的线性表（ ） 【答案】√

【解析】串是一种特殊的线性表，其特殊性在于串中的元素只能是字符型数据。字符型数据的操作符合字符型数据的操作规范，具有它的特殊性。

3．如果一个串中的所有字符均在另一串中出现，那么说明前者是后者的子串（ ） 【答案】× 【解析】一个字符串中任意个连续的字符组成的子序列称为该串的子串，注意其中字符的连续性。

4.4 应用题

1．描述以下概念的区别：空格串与空串。

【答案】空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。

2．设S1，S2为串，请给出使S1/*S2=S2/*S1成立的所有可能的条件（/*为连接符）。 【答案】

（1）s1和s2均为空串； （2）两串之一为空串；

（3）两串串值相等（即两串长度相等且对应位置上的字符相同）。

（4）两串中一个串长是另一个串长（包括串长为1仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。

19

3．已知：s ＝\＋*\，t ＝\＋z)*y\。试利用联结、求子串和置换等基本运算，将 s 转化为 t 。

【答案】本题有多种解法，下面是其中的一种： （1） s1=substr（s,3,1） /*取出子串：\（2） s2=substr（s,6,1） /*取出子串：\

（3） s3=substr（s,1,5） /*取出子串：\ （4） s4=substr（s,7,1） /*取出子串：\

（5） s5=replace（s3,3,1,s2）/*形成部分串：\

（6） s=s5/*s4/*s1 /*形成串t即\【解析】题中所给操作的含义如下： /*：连接函数，将两个串连接成一个串 substr（s,i,j）：取子串函数，从串s的第i个字符开始，取连续j个字符形成子串 replace（s1,i,j,s2）：置换函数，用s2串替换s1串中从第i个字符开始的连续j个字符

4.4 应用题

1．描述以下概念的区别：空格串与空串。

【答案】空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。

2．设S1，S2为串，请给出使S1/*S2=S2/*S1成立的所有可能的条件（/*为连接符）。 【答案】

（1）s1和s2均为空串； （2）两串之一为空串；

（3）两串串值相等（即两串长度相等且对应位置上的字符相同）。

（4）两串中一个串长是另一个串长（包括串长为1仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。 3．已知：s ＝\＋*\，t ＝\＋z)*y\。试利用联结、求子串和置换等基本运算，将 s 转化为 t 。

【答案】本题有多种解法，下面是其中的一种： （1） s1=substr（s,3,1） /*取出子串：\（2） s2=substr（s,6,1） /*取出子串：\

（3） s3=substr（s,1,5） /*取出子串：\ （4） s4=substr（s,7,1） /*取出子串：\

（5） s5=replace（s3,3,1,s2）/*形成部分串：\

（6） s=s5/*s4/*s1 /*形成串t即\【解析】题中所给操作的含义如下： /*：连接函数，将两个串连接成一个串 substr（s,i,j）：取子串函数，从串s的第i个字符开始，取连续j个字符形成子串 replace（s1,i,j,s2）：置换函数，用s2串替换s1串中从第i个字符开始的连续j个字符

4.5 算法设计题

1．设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出0。 【算法分析】

判断字符串t是否是字符串s的子串，称为串的模式匹配，其基本思想是对串s和t各设一个指针i和j，i的值域是0..m-n，j的值域是0..n-1。初始值i和j均为0。模式匹配从s0和t0开始，若s0==t0，则i和j指针增加1，若在某个位置si!=tj，则主串指针i回溯到i=i-j+1，j仍从0开始，进行下一轮的比较，直到匹配成功（j>n-1），返回子串在主串的位置（i-j）。否则，当i>m-n则为匹配失败。

20