一、串的定义

1、串的定义

串是有零个或或多个字符组成的有限序列，又称为字符串。

一般记为：（n为正整数），str中串名，(1<=i<=n),由字母、数字和其他字符组成，n为串的长度。

2、串的一些概念

（1）空串：长度为零的串，称为空串，不含任意字符。

（2）子串：串中任意个连续的字符组成的子序列称为该串的子串，其中空串是任意串的子串。

注：串、子串和空串等概念与集合的概念有着很多相似之处。

二、串的存储结构

串的存储结构主要分为顺序存储结构和链式存储结构两大类。

三、顺序串

1、顺序串定义

用一组地址连续的存储单元存储串值的字符序列。

2、顺序串的基本运算

（1）代码部分

#include <stdio.h>
#include<string.h>
#include <malloc.h>#define MaxSize 200
//串声明
typedef struct
{char data[MaxSize];int length;
}SqString;//串赋值
void Assign(SqString &s,char str[])
{int i=0;while(str[i]!='\0')          //遍历str的所有字符,数组以空字符'\0'标识串结束{s.data[i]=str[i];i++;}s.length=i;
}//销毁串
void DestroyStr(SqString s)
{
}
//串复制
void StrCopy(SqString &s,SqString t)
{int i;for(i=0;i<t.length;i++)s.data[i]=t.data[i];s.length=t.length;
}//串长度int StrLength(SqString s)
{return (s.length);
}
//判断串相等运算算法int StrEqual(SqString s,SqString t)
{int i=0;if(s.length !=t.length)          //串长不同时返回0return (0);else{for(i=0;i<s.length;i++)if(s.data[i]!=t.data[i])return 0;return 1;}
}//串连接运算算法SqString Concat(SqString s,SqString t)
{SqString r;int i,j;for(i=0;i<s.length;i++)r.data[i]=s.data[i];             //将s复制到rfor(j=0;j<t.length;j++)r.data[s.length+j]=t.data[j];   //将t复制到rr.length=i+j;return r;                           //返回r
}//子串运算SqString SubStr(SqString s,int i,int j)
{SqString t;int k;if(i<1 || i>s.length || j<1 || i+j>s.length+1)t.length=0;else{for(k=i-1;k<i+j;k++)t.data[k-i+1]=s.data[k];t.length=j;}return t;
}//查找子串位置运算算法int Index(SqString s,SqString t)
{int i=0,j=0;                             //i和j分别扫描主串s和子串twhile(i<s.length && j<t.length)          //两个串都没有扫描完{if(s.data[i]==t.data[j])             //对应字符相同时，继续比较下一对字符{i++;                             //继续后面两个字符的比较j++;}else                                 //否则，主串指针回溯重新开始下一次匹配{i=i-j+1;                         //i回退到原i的下一个位置j=0;                             //j从t的第一个字符开始}}if(j>=t.length)return i-t.length+1;elsereturn 0;
}//子串插入int InsStr (SqString &s,int i,SqString t)
{int j;if(i<1 || i>s.length+1)                     //位置参数错误返回0return 0;else{for(j=s.length-1;j=i-1;j--)            //将s.data[i-1..s.length-1]s.data[j+t.length]=s.data[j];      //后移t.length个位置for(j=0;j<t.length;j++)                //插入子串ts.data[i+j-1]=t.data[j];s.length=s.length+t.length;            //修改s串长度return 1;                              //成功插入返回1}
}//子串删除int DelStr(SqString &s,int i,int j)
{int k;if(i<1 || i>s.length || j<1 || i+j>s.length+1)return 0;else{for(k=i+j-1;k<s.length;k++)s.data[k-j]=s.data[k];s.length=s.length-j;return 1;}
}//子串替换
SqString RepStrAll(SqString s,SqString s1,SqString s2)
{int i;i=Index(s,s1);while(i>0){DelStr(s,i,s1.length);                   //从s中删除子串s1InsStr(s,i,s2);                           //在s中插入子串s2         i=Index(s,s1);}return s;
}
//输出串void DispStr(SqString s)
{int i;for(i=0;i<s.length;i++)printf("%c",s.data[i]);printf("\n");
}void main()
{SqString s1,s2,s3,s4,s5,s6,s7;Assign(s1,"abcd");printf("s1:");DispStr(s1);printf("s1 的长度: %d\n",StrLength(s1));printf("s1=>s2\n");StrCopy(s2,s1);printf("s2 :");DispStr(s2);printf("s1和s2 %s\n",(StrEqual(s1,s2)==1 ? "相同" : "不相同"));Assign(s3,"12345678");printf("s3 :");DispStr(s3);printf("s1和s3连接=>s4\n");s4=Concat(s1,s3);printf("s4:");DispStr(s4);printf("s3[2..5]=>s5\n");s5=SubStr(s3,2,4);printf("s5:");DispStr(s5);Assign(s6,"567");printf("s6:");DispStr(s6);printf("s6在s3中位置:%d\n",Index(s3,s6));printf("从s3中删除s3[3..6]字符\n");DelStr(s3,3,4);printf("s3:");DispStr(s3);printf("从s4中将s6替换成s1=>s7\n");s7=RepStrAll(s4,s6,s1);printf("s7:");DispStr(s7);DestroyStr(s1);DestroyStr(s2);DestroyStr(s3);DestroyStr(s4);DestroyStr(s5);DestroyStr(s6);DestroyStr(s7);
}