i++; stack[i].id=n; stack[i].x=stack[i-1].x; stack[i].y=stack[i-1].z; stack[i].z=stack[i-1].y; } printf(\ printf(\ printf(\ printf(\ printf(\ i--; do { if( i>=1 ) { printf(\ printf(\ printf(\ printf(\ printf(\ } stack[i].id = stack[i].id-1; n=stack[i].id; if( n>=1 ) { s=stack[i].x; stack[i].x = stack[i].y; stack[i].y=s; } if( n==1 ) { printf(\ printf(\ printf(\ printf(\stack[i].z); i--; } }while( (n<=1)&&(i>0) ) }while( i>0 )
} getch(); }
习题四 一、选择项
l．空串与空格串（ B ）。
A．相同 B．不相同 C．可能相同 D．无法确定
2．设有两个申S1与S2，求串S2在S1中首次出现位置的运算称作（ C ）。 A．连接 B．求子串 C．模式匹配 D．判子串
3．串与普通的线性表相比较，它的特殊性体现在（ C ）。 A．顺序的存储结构 B．链接的存储结构 C．数据元素是一个字符 D．数据元素可以任意 4．设有串S=‘Computer’，则其子串的数目是（ A ）。
A．36 B．37 C．8 D．9 二、境空题
1．串是由零个或多个字符组成的有限序列。通常记作：s＝“c1，c2，?，cn”(n=>0)，其中，S称为串名；串中的Ci（1<=i<=n）可以是字母、数字 字格或其他字符。用双引号括起来的部分是串值．即串S的内容。
2．串中字符的个数称为串的长度。
3．不含有任何字符的串称为空串，它的长度为零。
4．由一个或多个空格构成的串称为空格串，它的长度为空格的个数。
5．串中任意多个连续字符组成的子序列称为该串的子串；包含子串的串称为主串。 6．字符在序列中的序号称为该字符在串中的位置。
7．两个字符串相等是指两个字符串的，也就是说这两个字符串不仅值相等，而且对应位置上长度相等的字符也相等。
8．两个串的比较实际上是ASCII码的比较。两个串从第一个位置上的字符开始进行比较，当第一次出现ASCII码大的串为大，若比较过程中出现一个字符串结束的情况，则另一个串为、较大者。
9．串的顺序存储结构就是把串所包含的字符序列，依次存人连续的存储单元中去。 10．有些计算机系统中为了充分利用存储空间，允许一个存储单元可以存放多个字 符，串的这种存储方式是一种紧缩式存储方式。
11．串的非紧缩存储方式是以存储单元为存储单位，一个存储单元中只存放一个字符。在这种情况下，即使一个存储单元能存放多个字符，这时候也只存放一个字符。
12．串在非紧缩方式下，串长度的存储是隐式的，串所占用的存储单元的个数即串的长度。
13．一些计算机是以字节为存取单位，恰好一个字符占用一个字节，自然形成了每个存储单元存放一个字符的分配方式，这种方式就是一种单字节存储方式。这种方式一般不需要存放串长的存储单元，而需要以程序中各变量值所不包含的字符为结束符。
14．串的链式存储结构是将存储区域分成一系列大小相同的结点，每个结点有两个城：数据域和指针域。其中数据域用于存放数据，指针域用于存放下一个结点的指针。 15．子串定位StrIndex (s，t)，也称为模式匹配，是返回串t在s主串中的位置。 三、判断回
1．子串是主串中字符构成的有限序列。（错误：子串是主串中连续字符构成的有限序列。 ）
2．KMP算法的最大特点是指示主串的指针不需要回溯。（正确 ）
3．串中的元素只能是字符。（正确：注意字符可以是字母、数字或计算机能表达的其他符号。 ）
4．串中的元素只可能是字母。（错误：可以是数字或其他字符 ） 5．串是一种特殊的线性表。（正确 ） 6．串中可以包含有空白字符。（ 正确 ） 7．串的长度不能为零。（错误：串可以是空串、长度可以为零 ） 8．两个串相等必有串长度相同。（ 正确 ） 9．两个串相等则各位置上字符必须对应相等。（ 正确 ） 四、综合题
l．编写算法实现将窜S1中的第 i个字符到第 j个字符之间的字符(不包括第 i个字符和第j个字符)之间的字符用串S2替换。假设串的存储结构为： ＃define MAXSIZE 81 struct string{
int len；
char ch［MAXSIZE］； ｝stringtype；
void replace (stringtype s1[], int i, int j, stringtype s2[]) { stringtype s[100]; int h,k; if ( i<=h && i 2．设计一个算法，测试一个串S是否回文（所谓回文是指从左面读起和从右面读起内容一样）。 int invert(stringtype *s) { /*判断是否回文*/ int i, j; j=length(s)%2; for ( i=0; i 3．写一个递归算法来实现字符的逆序存储，要求不另设存储空间。 SubStr(s, void reverse ( stringtype *s ) { char c; int i; i=1; printf(\ do { scanf(\ Reverse(s); s.ch[i]=c; i++; }while(c!='#'&&i 4．一个仅由字母组成的字符串s，长度为n，其结构为单链表，每个结点的数据城只存放一个字母。设计一个算法，去掉字符串中所有值为X的字母。 void sjt4( linklist *s, char x ) { linklist *p,*q,*r; int w; p=s; w=1; while ( p!=NULL ) { if ( w==1 ) /*处理第一个结点*/