字符串：是由零个或多个字符串组成的有限序列，又名字符串。一般记为 s=“a1a2a3a4。。。an”； 子串和主串 子串：串中任意个数的子序列称为改串的子串
计算机中的常用字符的标准为ASCII，由7位二进制数表示一个字符，总共可以表示128个字符。后来出现一些特殊字符，于是ASCII拓展为由8位二进制数表示。
在C语言中比较字符串的大小： 1.相等：串的长度及串中各个位置对应的字符都相等。 2.s< t s=“a1a2a3a4。。。an”； t=“b1b2b3b4。。。bm”； - n< m,且si = ti 如s=“hap”，t=“happy” - 存在某个K小于等于min（m，n），使ai=bi，ak < bk 如s=“happes” t=“happy” 字符e的ASCII为101 y的ASCII为121
在C语言中字符串的长度中包含一个‘\0’ 串的顺序存储结构 要为串变量分配一个固定长度的存储区，但如两串的连接，字符串的替换，都有可能使串序列超过了数组的长度。
串的链式存储结构 由于串结构的特殊性，如果一个节点时对应一个字符会存在很大的空间浪费。因此一个节点可以存放多个字符，当一个节点未被占满时，可以用“#”或其他非字符串补全。但性能不如顺序存储。
#include "string.h" #include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 40 /* 存储空间初始分配量 */ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */ typedef char String[MAXSIZE+1]; /* 0号单元存放串的长度 */ using namespace std; Status StrAssign(String T, char* chars){ int i; if(strlen(chars)>MAXSIZE) //strlen(s)//不包含‘\0’,所以是大于MAXSIZE return ERROR; T[0] = strlen(chars); for(i=1;i<=T[0];i++){ T[i]=*(chars+i-1); //char代表首符号的地址 } return OK; } /* 返回串的元素个数 */ int StrLength(String S) { return S[0]; } /* 若S为空串,则返回TRUE,否则返回FALSE */ Status StrEmpty(String S) { if(S[0]==0) return TRUE; else return FALSE; } Status StrCopy(String T, String S){ if(MAXSIZE<S[0]){ //第一位为字符串的长度 return ERROR; } T[0] = S[0]; int i; for(i=1;i<=T[0];i++){ T[i] = S[i]; } return OK; } void PrintStr(String S){ if(S[0]){ int i=1; for(;i<=S[0];i++){ printf("%c",S[i]); } } printf("\n"); } Status ClearString(String S){ if(S[0]==0) return ERROR; S[0]=0; return OK; } /* 初始条件: 串S和T存在 */ /* 操作结果: 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0 */ int StrCompare(String T , String S){ int i = 1; while(i<=T[0]&&i<=S[0]){ if(T[i]!=S[i]) return S[i]-T[i]; i++; } return S[0]-T[0]; //在abcde 和 abcdef的情况下 是相等的 } /* 用T返回S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE */ Status Concat(String T , String S1, String S2){ int i=1; if(S1[0]+S2[0]<=MAXSIZE){ if(S1[0]){ for(i=1;i<=S1[0];i++) T[i] = S1[i]; } if(S2[0]){ for(i=1;i<=S2[0];i++) T[i+S1[0]] = S2[i]; } T[0] = S1[0]+S2[0]; return OK; }else{//截断S2 if(S1[0]&&S1[0]<MAXSIZE){ for(i=1;i<=S1[0];i++) T[i] = S1[i]; } for(i=1;i<=MAXSIZE-S1[0];i++){ T[i+S1[0]] = S2[i]; } T[0]=MAXSIZE; return FALSE; } } /* 用Sub返回串S的第pos个字符起长度为len的子串。 */ Status SubString(String Sub, String S ,int pos , int len ){ if(S[0]!=0&&len>=0&&len<=(S[0]-pos+1)&&pos>=1&&pos<=S[0]){ //包含开始的位置 int i; for(i=1;i<=len;i++){ Sub[i] = S[pos+i-1]; } Sub[0] = len; } return ERROR; } /* T为非空串。若主串S中第pos个字符之后存在与T相等的子串， */ /* 则返回第一个这样的子串在S中的位置，否则返回0 */ int Index(String S , String T ,int pos){ if(pos<1) return -1; int n = S[0]; int m = T[0]; String sub; int i ; i=pos; while(i<=n-m+1){ //子字符串需要移动和原字符比较的次数 SubString(sub,S,i,m); if(StrCompare(sub,T)!=0){ ++i; }else{ return i; } } return 0; } int Index1(String S,String T,int position){ if(position<1&&position>S[0]) return -1; int i = position; int j = 1; while(i<=S[0]&&j<=T[0]){ if(S[i] == T[j]){ i++; j++; }else{ i=i-j+2;//i总比j大i-1，原来位置的i+2得到它的下一个位置 j=1; } } if(j > T[0]){//说明整个T字符串已经匹配上了 return i-T[0]; }else{ return 0; } } /* 初始条件: 串S和T存在,1≤pos≤StrLength(S)+1 */ /* 操作结果: 在串S的第pos个字符之前插入串T。完全插入返回TRUE,部分插入返回FALSE */ Status StrInsert(String S, int pos , String T){ int i; if(pos<1||pos>S[0]+1) return ERROR; if(S[0]+T[0]<=MAXSIZE){ for(i=S[0];i>=pos;i--) //移动 S[i+T[0]]=S[i]; for(i=1;i<=T[0];i++){ //插入 S[i+pos-1]=T[i]; } S[0]=S[0]+T[0]; return TRUE; }else{ for(i=MAXSIZE;i>=pos;i--){//将从pos位置开始，T[0]长度的子串，移动到最后一个位置 S[i]=S[i-T[0]]; if(i == MAXSIZE-T[0]) //加这个的目的是为了恰好复制需要改变的长度 //MAXSIZE-T[0]为需要复制字符的个数 break; } for(i=pos;i<pos+T[0];i++) //再向空出的元素赋值 S[i]=T[i-pos+1]; S[0]=MAXSIZE; return FALSE; } } Status StrDelete(String S , int pos ,int len){ if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1) return ERROR; int i; for(i=pos+len;i<=S[0];i++){ //例 1 2 3 4 5 6 7 8 9 0 pos=2 len=3 需要删除的元素为234 //需要从第2个位置开始复制的是5 6 7 8 9 0 赋值的次数为S[0]-pos+len S[i-len] = S[i]; } S[0]=S[0]-len; return OK; } /* 初始条件: 串S,T和V存在,T是非空串（此函数与串的存储结构无关） */ /* 操作结果: 用V替换主串S中出现的所有与T相等的不重叠的子串 */ Status Replace(String S,String T,String V){ int Tlength = T[0]; int i; String sub; for(i=1;i<=S[0]-Tlength+1;i++){ SubString(sub,S,i,Tlength); if(StrCompare(sub,T)!=0) continue; else{ StrDelete(S,i,Tlength); StrInsert(S,i,V); } } } /* 初始条件: 串S,T和V存在,T是非空串（此函数与串的存储结构无关） */ /* 操作结果: 用V替换主串S中出现的所有与T相等的不重叠的子串 */ Status Replace1(String S,String T,String V) { int i=1; /* 从串S的第一个字符起查找串T */ if(StrEmpty(T)) /* T是空串 */ return ERROR; while(i){ i=Index(S,T,i); /* 结果i为从上一个i之后找到的子串T的位置 */ if(i) /* 串S中存在串T */ { StrDelete(S,i,StrLength(T)); /* 删除该串T */ StrInsert(S,i,V); /* 在原串T的位置插入串V */ i+=StrLength(V); /* 在插入的串V后面继续查找串T */ } } return OK; } int main() { String s1,s2,s3,T,sub; StrAssign(s1,"abcdefghijklmnopqrstuvwxyz"); printf("串长为%d 串空否？%d(1:是 0:否)\n",StrLength(s1),StrEmpty(s1)); StrCopy(s2,s1); printf("复制后的字符串为:"); PrintStr(s2); StrAssign(s3,"abcde"); printf("\ns1与s3比较的结果是："); printf("%d\n",StrCompare(s1,s3)); printf("把s1和s2连接后赋值给T后的结果是:"); Concat(T,s1,s2); printf("串长为%d 串空否？%d(1:是 0:否)\n",StrLength(T),StrEmpty(T)); PrintStr(T); printf("\n拷贝在T中从3起到长度为8的子串:\n"); SubString(sub,T,3,8); PrintStr(sub); printf("\n在S中找到与T字符串相等的字符串的位置为\n"); int position = Index(T,sub,1); printf("%d\n",position); String a,b; StrAssign(a,"123456789abcdefghijklmnopqrstuvwxz12345"); printf("串长为%d 串空否？%d(1:是 0:否)\n",StrLength(a),StrEmpty(a)); PrintStr(a); StrAssign(b,"0000000000"); printf("\n"); printf("在第7个位置前插入字符串\n"); StrInsert(a,7,b); PrintStr(a); printf("在第七个位置上删除长度为10的子字符串的结果为\n"); //StrDelete(a,7,10); PrintStr(a); printf("将r1中与r2相等的子串替换为r3\n"); String r1,r2,r3; StrAssign(r1,"aabbccddeeaabbccddeeaabb"); StrAssign(r2,"aa"); StrAssign(r3,"00000"); printf("r1= ");PrintStr(r1); printf("r2= ");PrintStr(r2); printf("r3= ");PrintStr(r3); Replace1(r1,r2,r3); PrintStr(r1); return 0; }