// LString.h 串的块链存储表示
#define CHUNKSIZE 4 // 可由用户定义的块大小
typedef struct Chunk {
char ch[CHUNKSIZE]; //块的数据域 struct Chunk *next; //块的指针域 }Chunk;
typedef struct {
Chunk *head, // 串的头指针 *tail; // 串的尾指针 int curlen; // 串的当前长度 }LString;
char blank = '#'; // 全局变量,用于填补空余
// 初始化(产生空串)字符串T。 void InitString(LString *T) {
(*T).curlen=0; (*T).head=NULL; (*T).tail=NULL; }
// 生成一个其值等于chars的串T(要求chars中不包含填补空余的字符) // 成功返回1，否则返回0
int StrAssign(LString *T,char *chars) {
int i,j,k,l;
Chunk *p,*q;
i=strlen(chars); // i为串的长度
if(!i||strchr(chars,blank)) // 串长为0或chars中包含填补空余的字符 return 0; (*T).curlen=i;
j=i/CHUNKSIZE; // j为块链的结点数，块的个数
if(i%CHUNKSIZE) //不足一个块的，当成一个块即块数加1 j++;
for(k=0;kp=(Chunk*)malloc(sizeof(Chunk)); if(!p)return 0;
if(k==0) // 第一个链块 (*T).head=q=p; else {
q->next=p; q=p; }
for(l=0;lch+l)=*chars++; if(!*chars) // 最后一个链块 {(*T).tail=q; q->next=NULL;
for(;l// 用填补空余的字符（blank=‘#’）填满链表 *(q->ch+l)=blank; } }return 1; }
// 由串S复制得串T(连填补空余的字符一块拷贝) int StrCopy(LString *T,LString S) {
Chunk *h=S.head,*p,*q;
(*T).curlen=S.curlen; if(h) {
p=(*T).head=(Chunk*)malloc(sizeof(Chunk));
*p=*h; // 复制1个结点 h=h->next;
while(h) //没到队尾，继续复制块 {
q=p;
p=(Chunk*)malloc(sizeof(Chunk)); q->next=p; *p=*h; h=h->next; }
p->next=NULL; (*T).tail=p; return 1; } else
return 0; }
// 若S为空串,则返回1,否则返回0 int StrEmpty(LString S) {
if(S.curlen) // 非空 return 0; else
return 1; }
// 若S>T,则返回值>0;若S=T,则返回值=0;若Sint i=0; // i为当前待比较字符在S,T串中的位置Chunk *ps=S.head,*pt=T.head; // ps,pt分别指向S和T的待比较块 int js=0,jt=0; // js,jt分别指示S和T的待比较字符在块中的位序
while(ii++; // 分别找S和T的第i个字符while(*(ps->ch+js)==blank) // 跳过填补空余的字符 {
js++;
if(js==CHUNKSIZE) {
ps=ps->next; js=0;
}
}; // *(ps->ch+js)为S的第i个有效字符
while(*(pt->ch+jt)==blank) // 跳过填补空余的字符 {
jt++;
if(jt==CHUNKSIZE) {
pt=pt->next; jt=0; }
}; // *(pt->ch+jt)为T的第i个有效字符 if(*(ps->ch+js)!=*(pt->ch+jt))
return *(ps->ch+js)-*(pt->ch+jt); else // 继续比较下一个字符 {
js++;
if(js==CHUNKSIZE) {
ps=ps->next; js=0; } jt++;
if(jt==CHUNKSIZE) {
pt=pt->next; jt=0; } } }
return S.curlen-T.curlen; }
// 返回S的元素个数,称为串的长度 int StrLength(LString S) {
return S.curlen; }
// 将S清为空串
int ClearString(LString *S) {
Chunk *p,*q;
//释放空间，并置空 p=(*S).head;
while(p) {
q=p->next; free(p); p=q; }
(*S).head=NULL; (*S).tail=NULL; (*S).curlen=0; return 1; }
// 用T返回由S1和S2联接而成的新串
int Concat(LString *T,LString S1,LString S2) {
LString a1,a2; InitString(&a1); InitString(&a2); StrCopy(&a1,S1); StrCopy(&a2,S2);
(*T).curlen=S1.curlen+S2.curlen; (*T).head=a1.head; a1.tail->next=a2.head; (*T).tail=a2.tail; return 1; }
// 用Sub返回串S的第pos个字符起长度为len的子串。 int SubString(LString *Sub, LString S,int pos,int len) {
Chunk *p,*q; int i,k,n,
flag=1; //用来标志复制是否完成，1完成，0未完成
if(pos<1||pos>S.curlen||len<0||len>S.curlen-pos+1) return 0; n=len/CHUNKSIZE; if(len%CHUNKSIZE) n++; // n为块的个数
p=(Chunk*)malloc(sizeof(Chunk)); (*Sub).head=p; // 生成空的Sub串 for(i=1;iq=(Chunk*)malloc(sizeof(Chunk));p->next=q; p=q; }
p->next=NULL; (*Sub).tail=p; (*Sub).curlen=len;
for(i=len%CHUNKSIZE; i*(p->ch+i)=blank; // 填充Sub尾部的多余空间 q=(*Sub).head; // q指向Sub串即将复制的块i=0; // i指示即将复制的字符在块中的位置 p=S.head; // p指向S串的当前块
n=0; // n指示当前字符在串中的序号 while(flag) {
for(k=0; kch+k)!=blank) {n++;
if(n>=pos&&n<=pos+len-1) // 复制 {
if(i==CHUNKSIZE) { // 到下一块 q=q->next; i=0; }
*(q->ch+i)=*(p->ch+k); i++;
if(n==pos+len-1) // 复制结束 {
flag=0; break; } } }
p=p->next; }
return 1; }
// T为非空串。若主串S中第pos个字符之后存在与T相等的子串, // 则返回第一个这样的子串在S中的位置,否则返回0 int Index(LString S,LString T,int pos) {
int i,n,m;
LString sub;
if(pos>=1 && pos<=StrLength(S)) // pos满足条件 {
n=StrLength(S); // 主串长度 m=StrLength(T); // T串长度 i=pos; while(i<=n-m+1) {
SubString(&sub,S,i,m); // sub为从S的第i个字符起,长度为m的子串 if(StrCompare(sub,T)!=0) // sub不等于T ++i; else
return i; } }
return 0; }
// 压缩串(清除块中不必要的填补空余的字符)。 void Zip(LString *S) {
int j,n=0;
Chunk *h=(*S).head; char *q;
q=(char*)malloc(((*S).curlen+1)*sizeof(char));
while(h) // 将LString类型的字符串转换为char[]类型的字符串 {
for(j=0; jch+j)!=blank) {*(q+n)=*(h->ch+j); n++; }
h=h->next; //h指向下一个块 }
*(q+n)=0; // 串结束符 ClearString(S); // 清空S StrAssign(S,q); // 重新生成S }
// 在串S的第pos个字符之前插入串T
int StrInsert(LString *S,int pos,LString T)
{
int i,j,k; Chunk *p,*q; LString t;
if(pos<1||pos>StrLength(*S)+1) // pos超出范围 return 0;
StrCopy(&t,T); // 复制T为t
Zip(S); // 去掉S中多余的填补空余的字符
i=(pos-1)/CHUNKSIZE; // 到达插入点要移动的块数
j=(pos-1)%CHUNKSIZE; // 到达插入点在最后一块上要移动的字符数 p=(*S).head;
if(pos==1) // 插在S串前 {
t.tail->next=(*S).head; (*S).head=t.head; }
else if(j==0) // 插在块之间 {
for(k=1;kp=p->next; // p指向插入点的左块 q=p->next; // q指向插入点的右块 p->next=t.head; // 插入t t.tail->next=q;if(q==NULL) // 插在S串后
(*S).tail=t.tail; // 改变尾指针 }
else // 插在一块内的两个字符之间 {
for(k=1;k<=i;k++)
p=p->next; // p指向插入点所在块
q=(Chunk*)malloc(sizeof(Chunk)); // 生成新块 for(i=0;i*(q->ch+i)=blank; // 块q的前j个字符为填补空余的字符 for(i=j;i*(q->ch+i)=*(p->ch+i); // 复制插入点后的字符到q *(p->ch+i)=blank; // p的该字符为填补空余的字符 }q->next=p->next; p->next=t.head; t.tail->next=q; }
(*S).curlen+=t.curlen;
Zip(S); //进行压缩 return 1; }
// 从串S中删除第pos个字符起长度为len的子串 int StrDelete(LString *S,int pos,int len) {
int i=1; // 当前字符是S串的第i个字符(1～S.curlen) Chunk *p=(*S).head; // p指向S的当前块
int j=0; // 当前字符在当前块中的位序(0～CHUNKSIZE-1)
if(pos<1||pos>(*S).curlen-len+1||len<0) // pos,len的值超出范围 return 0;
while(iwhile(*(p->ch+j)==blank) // 跳过填补空余的字符 {j++;
if(j==CHUNKSIZE) // 应转向下一块 {
p=p->next; j=0; } }
i++; // 当前字符是S的第i个字符 j++;
if(j==CHUNKSIZE) // 应转向下一块 {
p=p->next; j=0; }
}; // i=pos,*(p->ch+j)为S的第pos个有效字符
while(iwhile(*(p->ch+j)==blank) // 跳过填补空余的字符 {j++;
if(j==CHUNKSIZE) // 应转向下一块 {
p=p->next; j=0; } }
*(p->ch+j)=blank; // 把字符改成填补空余的字符来＂删除＂第i个字符 i++; // 到下一个字符
j++;
if(j==CHUNKSIZE) // 应转向下一块 {
p=p->next; j=0; } };
(*S).curlen-=len; // 串的当前长度 return 1; }
// 用V替换主串S中出现的所有与T相等的不重叠的子串 int Replace(LString *S,LString T,LString V) {
int i=1; // 从串S的第一个字符起查找串T if(StrEmpty(T)) // T是空串 return 0; do {
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 }
}while(i); return 1; }
// 输出字符串T。
void StrPrint(LString T) {
int i=0,j; Chunk *h; h=T.head;
while(ifor(j=0;jif(*(h->ch+j)!=blank) // 不是填补空余的字符 {printf(\"%c\ i++; }
h=h->next; }
printf(\"\\n\"); }
void DestroyString() {
// 块链类型的字符串无法销毁 }
int main() {
char *s1=\"ABCDEFGHI\ int k;
int pos,len;
LString t1,t2,t3,t4;
InitString(&t1); InitString(&t2);
printf(\"初始化串t1后，串t1空否？%d(1:空 0:否) 串长=%d\\n\ StrEmpty(t1),StrLength(t1)); k=StrAssign(&t1,s3); if(k==1) {
printf(\"串t1为: \"); StrPrint(t1); } else
printf(\"出错\\n\"); // 不能生成空串 k=StrAssign(&t1,s4); if(k==1) {
printf(\"串t1为: \"); StrPrint(t1); } else
printf(\"出错\\n\"); // 不能生成含有变量blank所代表的字符的串 k=StrAssign(&t1,s1); if(k==1) {
printf(\"串t1为: \"); StrPrint(t1);
} else
printf(\"出错\\n\");
printf(\"串t1空否？%d(1:空 0:否) 串长=%d\\n\ StrEmpty(t1),StrLength(t1)); StrAssign(&t2,s2); printf(\"串t2为: \"); StrPrint(t2);
StrCopy(&t3,t1);
printf(\"由串t1拷贝得到串t3,串t3为: \"); StrPrint(t3); InitString(&t4); StrAssign(&t4,s5); printf(\"串t4为: \"); StrPrint(t4);
Replace(&t3,t4,t2);
printf(\"用t2取代串t3中的t4串后，串t3为: \"); StrPrint(t3); ClearString(&t1);
printf(\"清空串t1后，串t1空否？%d(1:空 0:否) 串长=%d\\n\ StrEmpty(t1),StrLength(t1)); Concat(&t1,t2,t3);
printf(\"串t1(=t2+t3)为: \"); StrPrint(t1); Zip(&t1);
printf(\"去除不必要的占位符后，串t1为: \"); StrPrint(t1);
pos=Index(t1,t3,1); printf(\"pos=%d\\n\
printf(\"在串t1的第pos个字符之前插入串t2，请输入pos: \"); scanf(\"%d\
k=StrInsert(&t1,pos,t2); if(k) {
printf(\"插入串t2后，串t1为: \"); StrPrint(t1); } else
printf(\"插入失败！\\n\");
printf(\"求从t1的第pos个字符起,长度为len的子串t2,请输入pos,len: \"); scanf(\"%d,%d\SubString(&t2,t1,pos,len); printf(\"串t2为: \"); StrPrint(t2);