数据结构之串的定义及实现

串的基本定义及实现

串类型的定义定长顺序存储形式堆分配存储形式 1.1、串类型的定义 串（string）是零个或多个字符组成的有限序列 , S=‘a1a2…an’（n>=0） 其中，s是串名，用单引号括起来的是串的值；ai是字母、数字或其他字符；传中字符的数目n称为串的长度。另个字符的串称为空串，它的长度为0。 串中一个连续的字符组成的子序列称为该串的子串。包含子串的串称为主串。通常称字符在序列中的序号为在串中位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。 1.2几种对比 1.栈和队列是操作受限的线性表，串是取值受限的线性表，约束为字符集。 2.空格串：由一个或多个空格组成的串，空串：零个字符的串称为空串 3.串的逻辑结构和线性表很相似区别仅在于串的数据对象为字符集。然而，串的基本操作和线性表有很大差别。线性表通常操作对象为单个字符，而串的操作对象为一个子串。 2定长顺序存储形式 2.1顺序储存表示 #define MAXSIZE 300 typdef char str[MAXSIZE+1];

2.2赋值

void StrAssign（str s,char ch[]）{ int a,i; if((a=strlen(ch)>MAXSIZE)//判断是否ch的长度大于最大值 exit(-1); for(i=1;i<a;i++){//进行值拷贝 s[i]=ch[i]; s[0]=ch[0];//第一个字符存长度 }

2.3拷贝

void strcopy(str s,str ss){ if(ss[0]>s[0]){ printf("内存不足"); exit(-1); } for(int i=0;i<=ss[0];i++)//一个字符一个字符拷贝 s[i]=ss[i]; s[0]+=ss[0]; }

2.4判断是否为空

int strempty(str s){//为空返回1，否则返回0 if(s[0]==0) return 1; else return 0; }

2.5比较大小

int strcompare(str s,str t){ for(int i=0;i<s[0]&&i<t[0];i++){ if(s[i]!=t[i]) return s[i]-t[i];//返回不相等时的字符的大小 } return s[0]-t[0];//某个串结束，前面都相等，返回串长的大小 }

2.6求长度

int strlength(str s){ return s[0]; }

2.7连接两个串

int strcat(str s,str t){//全部连接 if(s[0]+t[0]<=MAXSIZE){ for(int i=1;i<=t[0];i++) s[s[0]+i]=t[i]; s[0]+=t[0]; } else{//连接部分 if(s[0]==MAXSIZE) return 0; for(int i=1;i<=MAXSIZE-s[0]-1;i++) s[s[0]+i)=t[i]; s[0]+=t[0]; } }

2.8找到主串中在第pos个字符之后的len个字符

void substring(str s,str n,int pos,int len){ if(pos<1||pos>s[0]||pos>s[0]-len-1||len<0) exit(-1); for(int i=1;i<len;i++) n[i]=s[i+pos-1]; n[0]=len; }

2.9主串中找到与串在POS位置之后相等的子串

int index(str s,str t,int pos){ if(pos<0||pos>s[0]) return 0; int i=pos; int j=1; while(i<=s[0]&&j<=t[0]){ if(s[i]==t[j]){//如果相等，则进行下一个字符对比 ++i; ++j; } else{//如果不相等，主串的跳到不相等之前那个位置，重新开始对比 i=i-j+2; j=1; } } if(j>t[0]) return i-t[0]; }

2.10在主串位置 pos之后插入一个串

void strinsert(str s,str t,int pos){ if(pos<0||pos>s[0]+1) exit(-1); if(s[0]+t[0]<=MAXSIZE){//全部插入 for(int i=s[0];i>=pos;i--){//移动之后再插入 s[i+t[0]]=s[i]; } for(i=pos;i<pos+t[0];i++){ s[i]=t[pos-i+1]; } s[0]+=t[0]; else{//部分插入 for(i=MAXSIZE;i>=pos+t[0];i--){ s[i]=s[i-t[0]]; } for(i=pos;i<pos+t[0]||i<=MAXSIZE;i++) s[i]=t[i-pos+1]; s[0]=MAXSIZE; } }

2.11删除一个子串

void strdelete(str s,int pos,int len){//删除一个串 if(pos<1||pos>=MAXSIZE||len<0||pos>s[0]-len+1){ exit(-1); } for(int i=pos+len;i<=s[0];i++){ s[i-len]=s[i]; } s[0]-=len; }

2.12用一个串替换掉主串中出现的某个串

void replace(str s,str t,str v){//用v替换掉s与t相等的串 int i=1; int k; if(strempty(t)) exit(-1); while(i){ i=index(s,t,i); if(i){ strdelete(s,i,strlength(t)); k=strinsert(s,i,v); if(!k) exit(-1); i+=strlength(v); } } }

2.13打印出串的内容

void print(str s){ int i; for(i=1;i<s[0];i++){ printf("%c",s[i]); } printf("\n"); }

emmmmm，这次就先更到这，后面的内容放到下一篇里面吧。