sub->len=s->length-pos;//设置子串的串长
else sub->length=len; //设置子串的串长
sub->ch=(char *)malloc(len*sizeof(char));//为sub->ch申请结点空间
for(i=0;ilength;i++)//将s串中pos位置开始的共sub->length个字符复制到sub串中
sub->ch[i]=s->ch[pos+i];
}
3、若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;｝
习题精选
一、.单项选择题
1.串是一种特殊的线性表，其特殊性体现在（）。
A．可以顺序存储B．数据元素是一个字符
C．可以链式存储D．数据元素可以是多个字符若
2．串下面关于串的的叙述中，（）是不正确的？
A．串是字符的有限序列B．空串是由空格构成的串
C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存
3.串的长度是指（）。
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
4.设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是：
Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF
二、算法设计
1.编写算法，实现下面函数的功能。函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数）
[题目分析]本题是字符串的插入问题，要求在字符串s的pos位置，插入字符串t。首先应查找字符串s的pos位置，将第pos个字符到字符串s尾的子串向后移动字符串t的长度，然后将字符串t复制到字符串s的第pos位置后。
对插入位置pos要验证其合法性，小于1或大于串s的长度均为非法，因题目假设给字符串s的空间足够大，故对插入不必判溢出。
void insert(char *s,char *t,int pos)
//将字符串t插入字符串s的第pos个位置。
{int i=1,x=0; char *p=s,*q=t; //p，q分别为字符串s和t的工作指针
if(pos<1) {printf(“pos参数位置非法\n”);exit(0);}
while(*p!=’\0’&&i//若pos小于串s长度，则查到pos位置时，i=pos。
if(*p == '/0') {printf("%d位置大于字符串s的长度",pos);exit(0);}
else //查找字符串的尾
while(*p!= '/0') {p++; i++;} //查到尾时，i为字符‘\0’的下标，p也指向‘\0’。 while(*q!= '\0') {q++; x++; } //查找字符串t的长度x，循环结束时q指向'\0'。 for(j=i;j>=pos ;j--){*(p+x)=*p; p--;}//串s的pos后的子串右移，空出串t的位置。 q--; //指针q回退到串t的最后一个字符
for(j=1;j<=x;j++) *p--=*q--; //将t串插入到s的pos位置上
[算法讨论] 串s的结束标记('\0')也后移了，而串t的结尾标记不应插入到s中。
2.写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。
[题目分析]实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现字符串逆序存储，即第一个输入的字符最后存储，最后输入的字符先存储，使用递归可容易做到。 void InvertStore(char A[])
//字符串逆序存储的递归算法。
{ char ch;
static int i = 0;//需要使用静态变量
scanf ("%c",&ch);
if (ch!= '.') //规定'.'是字符串输入结束标志
{InvertStore(A);
A[i++] = ch;//字符串逆序存储
}
A[i] = '\0'; //字符串结尾标记
}//结束算法InvertStore。
