【算法源代码】
int index(char s[ ], char t[ ],int m,int n) {int i=0,j=0;
while (i<=m-n && j<=n-1)
if (s[i]==t[j]){i++;j++;} /*对应字符相等，指针后移*/
else {i=i-j+1;j=0;} /*对应字符不相等，i回溯，j仍为0*/ if(i<=m-n && j==n)
{printf(\在s串中位置是%d\ return(i-n+1); }/*匹配成功*/
else return(0); /*匹配失败*/ }
2．函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos。请用c语言实现该函数。假设分配给字符串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,j; char *p=s,*q=t; /*p，q分别为字符串s和t的工作指针*/ if(pos<1)
{printf(\参数位置非法\\n\while(*p!='\\0'&&i {printf(\位置大于字符串s的长度\ 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位置上*/ } 3．设计一个算法，统计在输入字符串中各个不同字符出现的频度。（字符串中的合法字符为'A'-'Z'这26个字母和'0'-'9'这10个数字）。 【算法分析】 由于字母共26个，加上数字符号10个共36个，所以设一长36的整型数组，前10个分量存放数字字符出现的次数，余下存放字母出现的次数。从字符串中读出数字字符时，字符的ASCII代码值减去数字字符'0'的ASCII代码值，得出其数值(0..9)，字母的ASCII代码值减去字符'A'的ASCII代码值加上10，存入其数组的对应下标分量中。遇其它符号不作处理，直至输入字符串结束。 【算法源代码】 void Count() 21 /*统计输入字符串中数字字符和字母字符的个数*/ {int i,num[36]; char ch; for(i=0;i<36;i++)num[i]=0;/* 初始化*/ while((ch=getchar())!='#') /*‘#’表示输入字符串结束*/ if(('0'<=ch)&&(ch<='9')) {i=ch-'0';num[i]++;} /* 数字字符*/ else if(('A'<= ch)&&(ch <='Z')) {i=ch-'A'+10;num[i]++;}/* 字母字符*/ for(i=0;i<10;i++) /* 输出数字字符的个数*/ printf(\数字％d的个数＝％d\\n\for(i=10;i<36;i++)/* 求出字母字符的个数*/ printf(\字母字符％c的个数＝％d\\n\}/* 算法结束*/ 4．若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。 【算法分析】 查找过程是这样的，取S中的一个字符(结点)，然后和T中所有的字符一一比较，直到比完仍没有相同的字符时，查找过程结束，否则再取S中下一个字符，重新进行上述过程。 【算法源代码】 char SearchNo( LinkString S, LinkString T) /*查找不在T中出现的字符*/ { LinkString p,q; p=S; q=T; while (p) {/*取S中结点字符*/ while(q&&p->data!=q->data)/*进行字符比较*/ q->next; if(q==NULL)return p->data;/*找到并返回字符值*/ q=T; /*指针恢复串T的开始结点*/ p=p->next; } printf(\ return NULL; } 5．如果一个字符串的一个子串（其长度大于1）的各个字符均相同，则称之为等值子串。试设计一个算法，输入字符串s，以“！”作为结束标志。如果串s中不存在等值子串，则输出信息“无等值子串”，否则求出（输出）一个长度最大的等值子串。 【算法分析】 用字符数组s接受用户输入的字符串。设head指向当前发现的最长等值子串的串头，max记录此子串的长度。对s进行扫描，若发现新的等值子串，用count变量统计其长度，若他的长度大于原有的max，则对head和max进行更新。重复上述过程直到s末尾。 【算法源代码】 #define MAXSIZE 100 {int i,j,k,head,max,count; char s[MAXSIZE]; printf(\输入字符串：\ k=0; scanf(\ while(s[k]!='!') 22 scanf(\ i=0,j=1,head=0,max=1; for(;s[i]!='!'&&s[j]!='!';i=j,j++) {count=1; while(s[i]==s[j]) {j++; count++; } if(count>max) {head=i; max=count; } } if(max>1) {printf(\最大等值子串：\for(k=head;k<(head+max);k++) printf(\} else printf(\无等值子串\printf(\} 6．采用顺序存储结构存储的串，编写一个程序，将两个字符串进行比较，若s>t时返回1，s=t时返回0，s 从两个字符串的第一个字符开始逐个进行比较（按字符的ASCII码大小比较），直到出现不同的字符或遇到'\\0'为止。如果全部字符都相同，就认为两个字符串相等，返回0。若出现了不相同的字符，则以第一个不相同的字符的比较结果为准。若前者字符大于后者字符，则返回1，否则返回-1。 【算法源代码】 int comp(SString *s1,SString *s2) { int i=0,minlen; minlen=s1->len>s2->len?s1->len:s2->len; /*minlen存放s1与s2中的较短的字符串的长度*/ while(i<=minlen) { if(s1->data[i]==s2->data[i]) /*如果s1与s2的当前字符相等，则比较下一个*/ i++; else if(s1->data[i] else return 1; /*s1的当前值大于s2的当前值，返回1*/ } if(s1->len==s2->len) return 0; /*s1与s2所有字符均相等，且长度相等，则返回0*/ } 7．输入一个由若干单词组成的文本行，每个单词之间用若干个空格隔开，统计其中的单词数。 【算法分析】 单词的数目可以有空格出现的次数来决定（连续的多个空格作为出现一次空格；不包含一行开头的空格）。如果当前字符为非空格，而他前面的字符是空格，则表示新的单词出现，此时让num（单词数）累加1。如果当前字符为非空格，而他前面的字符也是非空格，则表示此字符仍然是原单词的继续，num不应累加。前面一个单词是否为空格，可以设置一个变量 23 word，若word=0，则表示前一个字符时空格，如果word=1，表示前一个字符为非空格。 【算法源代码】 int count(s) char s[80]; {char c; int i,num=0,word=0; for(i=0;s[i]!='\\0';i++) {if(s[i]==' ') word=0; else if(word==0) {word=1; num++; } } return num; } 8．一个仅由字母组成的字符串s，长度为n，其结构为单链表，每个结点的data字段只存放一个字母。试设计一个函数，去掉字符串中所有的X字母，并将串中的一个最小字母排列到串尾。 【算法分析】 从链表的表头开始查找每一个结点，如果该结点的数据值为X，则删除该结点。同时在查找的过程中，顺便比较该结点与前驱结点的大小，如果该结点的值闭其前驱结点的值大，则顺便交换，直到整个链表结束。 【算法源代码】 search(LinkList s,char x) /*在带头结点的单链表s中查找数据值为x的结点*/ { LinkList p,q,r; char temp; p=s->next; q=s;/*p表示当前操作的结点，q表示p的前驱结点*/ while(p!=NULL) {if(p->data==x) {r=p; q-next=p->next; p=p->next; free(r); } /*找到释放结点*/ else {q=p; p=p->next; } if(q!=s&&p->data>q->data) /*将结点值最小的结点移到表尾*/ { temp=p->data; p->data=q->data; q->data=temp; } } } 9．设计一个算法，将字符串s的全部字符复制到字符串t中，不能利用strcpy函数。 【算法分析】 要实现两个字符串的复制，实质为两个字符数组之间的复制，在复制时，一个字符一个字符的复制，直到遇到'\\0'，'\\0'一同复制过去，'\\0'之后的字符不复制。 【算法源代码】 copy(char s[],char t[]) 24