4.1 简述下列每对术语的区别：
　　空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。

答：
　●空串是指不包含任何字符的串，它的长度为零。
　　空白串是指包含一个或多个空格的串，空格也是字符。

　●串常量是指在程序中只可引用但不可改变其值的串。
　　串变量是可以在运行中改变其值的。

　●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。

　●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。
　　动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。

　●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。

　●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。

4.2 假设有如下的串说明：

　　char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p;

　(1)在执行如下的每个语句后p的值是什么?
　　p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6');
　(2)在执行下列语句后，s3的值是什么?
　　strcpy(s3,s1); strcat(s3,","); strcat(s3,s2);
　(3)调用函数strcmp(s1,s2)的返回值是什么?
　(4)调用函数strcmp(&s1[5],"ton")的返回值是什么?
　(5)调用函数stlen(strcat(s1,s2))的返回值是什么?

解：
　(1) stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位置，否则返回NULL。
　因此:
　　执行p=stchr(s1,'t');后p的值是指向第一个字符t的位置, 也就是p==&s1[1]。
　　执行p=strchr(s2,'9');后p的值是指向s2串中第一个9所在的位置,也就是p==&s2[9]。
` 　执行p=strchr(s2,'6');之后，p的返回值是NULL。

　(2)strcpy函数功能是串拷贝，strcat函数的功能是串联接。所以:
　　在执行strcpy(s3,s1); 后，s3的值是"Stocktom,CA"
　　在执行strcat(s3,","); 后，s3的值变成"Stocktom,Ca,"
　　在执行完strcat(s3,s2);后，s3的值就成了"Stocktom,Ca,March 5,1999"

　(3)函数strcmp(串1，串2)的功能是串比较，按串的大小进行比较，返回大于0，等于0或小于0的值以表示串1比串2 大，串1等于串2 ，串1小于串2。因此在调用函数strcmp(s1,s2)后，返回值是大于0的数(字符比较是以ascii码值相比的)

　(4)首先，我们要知道&s1[5]是一个地址，当放在函数strcmp中时，它就表示指向以它为首地址的一个字符串，所以在strcmp( &s1[5],"ton")中，前一个字符串值是"tom,CA",用它和"ton"比较，应该是后者更大，所以返回值是小于0的数。

　(5)strlen是求串长的函数，我们先将s1,s2联接起来，值是"Stocktom,CAMarch 5,1999",数一数有几个字符?是不是23个(空格也是一个)? 所以返回值是23。

4.3 设T[0..n-1]="adaabaabcaabaa",P[0..m-1]="aab".当用模式串匹配目标串T时，请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。

解：
　　所有的有效位移i的值为：2，5，9。
　　算法NaveStrMatch(T,P)的返回值是第一个有效位移，因此是2。

4.4 利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。

解：
　　算法如下：
　void StrInsert(char *S, char *T, int i)
　　{//将串T插入到串S的第i个位置上
　　　char *Temp;
　　　if(i<=strlen(S))
　　　　{
　　　　　Temp=(char *)malloc(sizeof(char[Maxsize]));// 设置一个临时串 
　　　　　strcpy(Temp,&S[i]);//将第i位起以后的字符拷贝到临时串中
　　　　　strcpy(&S[i], T);//将串T拷贝到串S的第i个位置处，覆盖后面的字符
　　　　　strcat(S,Temp);//把临时串中的字符联接到串S后面
　　　　　free( Temp );
　　　　}
　　}

4.5 利用C的库函数strlen 和strcpy(或strncpy)写一算法void StrDelete(char *S,int i, int m)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中从位置i开始直至末尾的字符均删去。

解：
　　算法如下：
　void StrDelete(char *S, int i ,int m)
　　{ //串删除
　　　char Temp[Maxsize];//定义一个临时串
　　　if(i+m<strlen(S)) 
　　　　{
　　　　　strcpy (Temp, &S[i+m]);//把删除的字符以后的字符保存到临时串中
　　　　　strcpy( &S[i],Temp);//用临时串中的字符覆盖位置i之后的字符
　　　　}
　　　else if(i+m>=strlen(S)&& i<strlen(S))
　　　　{
　　　　　strcpy(&S[i],"\0");//把位置i的元素置为'\0'，表示串结束
　　　　}
　　}

4.6 以HString为存储表示，写一个求子串的算法。

解：
　　HString 是指以动态分配顺序串为存储表示，其定义为：
　　　typedef struct {
　　　　char *ch;
　　　　int length;
　　　}HString;

　　void *substr( HString *sub,HString *s,int pos,int len)
　　　{//用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串
　　　　//pos的合法位置为0<=pos<=s->length-1
　　　　int i; 
　　　　if (pos<0||pos>s->length-1||len<=0)
　　　　　Error("parameter error!");//参数不合法，子串为空串
　　　　if (s->length<pos+len)//s串中没有足够的元素
　　　　　sub->len=s->length-pos;//设置子串的串长
　　　　else sub->length=len; //设置子串的串长 
　　　　sub->ch=(char *)malloc(len*sizeof(char));//为sub->ch申请结点空间
　　　　for(i=0;i<sub->length;i++)//将s串中pos位置开始的共sub->length个字符复制到sub串中
　　　　　sub->ch[i]=s->ch[pos+i];
　　　}

4.7 一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：

　　a b c d e f g h i j k l m n o p q r s t u v w x y z 

　　n g z q t c o b m u h e l k p d a w x f y i v r s j 

　　则字符串"encrypt"被加密为"tkzwsdf".试写一算法将输入的文本串进行加密后输出；另写一算法，将输入的已加密的文本串进行解密后输出。

解：
　　加密算法可以用两个串中字符的一一对应关系来实现，当输入一个字符时，由算法在串Original中查找其位置，然后用串Cipher中相应位置的字符去替换原来的字符就可以了。解密算法则恰恰相返。
　　设字母映射表的存储结构如下：
　#define MaxStrSize 26
　typedef struct{
　　　char Original[MaxStrSize]; //可容纳26个字符，并依次存储在Original[0..n]中
　　　char Cipher[MaxStrSize]; //可容纳26个字符，并依次对应Original表中的密码
　　　int length;
　　}SeqString; 

　void Encrypt( SeqString codetable)
　　{//加密算法。
　　　char ch;
　　　int i;
　　　while((ch=getchar())!='\0')
　　　　{ i=0;
　　　　　while (i<codetable.length&&ch!=codetable.Original[i])
　　　　　　　i++;
　　　　　if (i>=codetable.length)
　　　　　　　Error("data error!");
　　　　　else 
　　　　　　　printf("%c",codetable.Cipher[i]);
　　　　}
　　　printf("\n");
　　}

　void Decipher(SeqString Original , SeqString Cipher, char* T)
　　{//解密算法。
　　　char ch;
　　　while((ch=getchar())!='\0')
　　　　{ i=0;
　　　　　while (i<codetable.length&&ch!=codetable.Cipher[i])
　　　　　　　i++;
　　　　　if (i>=codetable.length)
　　　　　　　Error("data error!");
　　　　　else 
　　　　　　　printf("%c",codetable.Original[i]);
　　　　}
　　　printf("\n");
　　}

4.8 写一算法void StrReplace(char *T, char *P, char *S),将T中首次出现的子串P替换为串S。注意：S和P的长度不一定相等。可以使用已有的串操作。

解：
　　由于S和P的长度不一定相等，所以在替换时可能要移动字符元素。我们可以用到前面设计的一系列算法。算法如下：
　void StrReplace (char *T, char *P, char *S)
　　{//串替换
　　　int i , m;
　　　m=strlen (P);//取得子串长度
　　　i=StrMatch(T,P);//取得串匹配位置
　　　StrDelete( T,i,m);//删除匹配处子串
　　　StrInsert( T, S,i);//将S串插入到匹配位置处
　　}

4.9 将NaveStrMatch改写为输出目标串中所有与模式串匹配的有效位移。
解：
　　把相应的返回语句改为打印输出就可找到所有匹配位置。改写后如下：
　void NaveStrMatch (SeqString T, SeqString P)
　　{
　　　int i,j,k;
　　　int m=P.lenth;//模式串长度
　　　int n=T.length;//目标串长度
　　　for (i=0; i<n-m; i++) // 确定合法位移
　　　　{
　　　　　j=0; k=i;
　　　　　while(j<m&&T.ch[k]==P.ch[j])
　　　　　　{
　　　　　　　k++;j++;
　　　　　　}
　　　　　if(j==m) printf("\n%d",i);
　　　　}//endfor
　　　printf("Search End.");
　　}

*4.10 利用4.9的结果写一算法void StrReplaceAll(char *T, char *P, char *S),将T中出现的所有与P相等的不重叠子串替换为S，这里S和P的长度不一定相等。

解：
　　这个算法是具有实用性的，但是做起来比较难，简单的算法应是这样的，利用4.9的算法在串T中找到一个P的匹配成功，马上进行串替换，然后从替换后的下一个位置进行匹配，直到查找完所有的有效位移或者所有合法位移考查完毕也没有匹配成功。
　　算法如下：
　void StrReplaceAll(char *T, char *P, char *S)
　　{//全部替换
　　　int i, j, k ;
　　　i=0;
　　　while(i<strlen(T)-strlen(P)) //合法位移
　　　　{
　　　　　j=0; k=i;
　　　　　while(T[k]==P[j]) //进行匹配
　　　　　　{k++;j++;}
　　　　　if(j==m){ //匹配成功
　　　　　　　StrDelete( T,i,m);//删除匹配处子串
　　　　　　　StrInsert( T, S,i);//将S串插入到匹配位置处
　　　　　　　i+=strlen(S); //将查找位置移到替换后的下一个字符处，避免重复替换
　　　　　　}//endif
　　　　　else i++;
　　　　}//endwhile
　　}//end

4.11 若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。

解:
　　查找过程是这样的，取S中的一个字符(结点)，然后和T中所有的字符一一比较，直到比完仍没有相同的字符时，查找过程结束，否则再取S中下一个字符，重新进行上述过程。算法如下：
　　链串的结构类型定义:
　typedef struct node{
　　　char data;
　　　struct node *next;
　　}LinkStrNode; //结点类型
　typedef LinkStrNode *LinkString; //LinkString为链串类型
　LinkString S; //S是链串的头指针

　char SearchNoin( LinkString S, LinkString T)
　　{//查找不在T中出现的字符
　　　LinkStrNode *p,*q;
　　　p=S;
　　　q=T;
　　　while (p)
　　　　{ //取S中结点字符
　　　　　　while(q&&p->data!=q->data)//进行字符比较
　　　　　　　　q=q->next;
　　　　　　if(q==NULL)　return p->data;//找到并返回字符值
　　　　　　q=T; //指针恢复串T的开始结点
　　　　　　p=p->next;
　　　　}
　　　printf("there's no such character.");
　　　return NULL;
　　}