数据结构C语言版串的块链存储表示和实现.docx

数据结构C语言版串的块链存储表示和实现.docx

《数据结构C语言版串的块链存储表示和实现.docx》由会员分享，可在线阅读，更多相关《数据结构C语言版串的块链存储表示和实现.docx（21页珍藏版）》请在冰点文库上搜索。

数据结构C语言版串的块链存储表示和实现

/*

数据结构C语言版串的块链存储表示和实现

P78

编译环境：

Dev-C++4.9.9.2

日期：

2011年2月12日

*/

#include

#include

#include

#include

//LString.h串的块链存储表示

#defineCHUNKSIZE4//可由用户定义的块大小

typedefstructChunk

{

charch[CHUNKSIZE];//块的数据域

structChunk*next;//块的指针域

}Chunk;

typedefstruct

{

Chunk*head,//串的头指针

*tail;//串的尾指针

intcurlen;//串的当前长度

}LString;

charblank='#';//全局变量,用于填补空余

//初始化（产生空串）字符串T。

voidInitString（LString*T）

{

（*T）.curlen=0;

（*T）.head=NULL;

（*T）.tail=NULL;

}

//生成一个其值等于chars的串T（要求chars中不包含填补空余的字符）

//成功返回1，否则返回0

intStrAssign（LString*T,char*chars）

{

inti,j,k,l;

Chunk*p,*q;

i=strlen（chars）;//i为串的长度

if（!

i||strchr（chars,blank））//串长为0或chars中包含填补空余的字符

return0;

（*T）.curlen=i;

j=i/CHUNKSIZE;//j为块链的结点数，块的个数

if（i%CHUNKSIZE）//不足一个块的，当成一个块即块数加1

j++;

for（k=0;k

{

p=（Chunk*）malloc（sizeof（Chunk））;

if（!

p）

return0;

if（k==0）//第一个链块

（*T）.head=q=p;

else

{

q->next=p;

q=p;

}

for（l=0;l

*（q->ch+l）=*chars++;

if（!

*chars）//最后一个链块

{

（*T）.tail=q;

q->next=NULL;

for（;l

//用填补空余的字符（blank=‘#’）填满链表

*（q->ch+l）=blank;

}

}

return1;

}

//由串S复制得串T（连填补空余的字符一块拷贝）

intStrCopy（LString*T,LStringS）

{

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;

return1;

}

else

return0;

}

//若S为空串,则返回1,否则返回0

intStrEmpty（LStringS）

{

if（S.curlen）//非空

return0;

else

return1;

}

//若S>T,则返回值>0;若S=T,则返回值=0;若S

intStrCompare（LStringS,LStringT）

{

inti=0;//i为当前待比较字符在S,T串中的位置

Chunk*ps=S.head,*pt=T.head;//ps,pt分别指向S和T的待比较块

intjs=0,jt=0;//js,jt分别指示S和T的待比较字符在块中的位序

while（i

{

i++;//分别找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;

}

}

}

returnS.curlen-T.curlen;

}

//返回S的元素个数,称为串的长度

intStrLength（LStringS）

{

returnS.curlen;

}

//将S清为空串

intClearString（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;

return1;

}

//用T返回由S1和S2联接而成的新串

intConcat（LString*T,LStringS1,LStringS2）

{

LStringa1,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;

return1;

}

//用Sub返回串S的第pos个字符起长度为len的子串。

intSubString（LString*Sub,LStringS,intpos,intlen）

{

Chunk*p,*q;

inti,k,n,

flag=1;//用来标志复制是否完成，1完成，0未完成

if（pos<1||pos>S.curlen||len<0||len>S.curlen-pos+1）

return0;

n=len/CHUNKSIZE;

if（len%CHUNKSIZE）

n++;//n为块的个数

p=（Chunk*）malloc（sizeof（Chunk））;

（*Sub）.head=p;//生成空的Sub串

for（i=1;i

{

q=（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;k

if（*（p->ch+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;

}

return1;

}

//T为非空串。

若主串S中第pos个字符之后存在与T相等的子串,

//则返回第一个这样的子串在S中的位置,否则返回0

intIndex（LStringS,LStringT,intpos）

{

inti,n,m;

LStringsub;

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

returni;

}

}

return0;

}

//压缩串（清除块中不必要的填补空余的字符）。

voidZip（LString*S）

{

intj,n=0;

Chunk*h=（*S）.head;

char*q;

q=（char*）malloc（（（*S）.curlen+1）*sizeof（char））;

while（h）//将LString类型的字符串转换为char[]类型的字符串

{

for（j=0;j

if（*（h->ch+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

intStrInsert（LString*S,intpos,LStringT）

{

inti,j,k;

Chunk*p,*q;

LStringt;

if（pos<1||pos>StrLength（*S）+1）//pos超出围

return0;

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;

}

elseif（j==0）//插在块之间

{

for（k=1;k

p=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）;//进行压缩

return1;

}

//从串S中删除第pos个字符起长度为len的子串

intStrDelete（LString*S,intpos,intlen）

{

inti=1;//当前字符是S串的第i个字符（1～S.curlen）

Chunk*p=（*S）.head;//p指向S的当前块

intj=0;//当前字符在当前块中的位序（0～CHUNKSIZE-1）

if（pos<1||pos>（*S）.curlen-len+1||len<0）//pos,len的值超出围

return0;

while（i

{

while（*（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（i

{

while（*（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;//串的当前长度

return1;

}

//用V替换主串S中出现的所有与T相等的不重叠的子串

intReplace（LString*S,LStringT,LStringV）

{

inti=1;//从串S的第一个字符起查找串T

if（StrEmpty（T））//T是空串

return0;

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）;

return1;

}

//输出字符串T。

voidStrPrint（LStringT）

{

inti=0,j;

Chunk*h;

h=T.head;

while（i

{

for（j=0;j

if（*（h->ch+j）!

=blank）//不是填补空余的字符

{

printf（"%c",*（h->ch+j））;

i++;

}

h=h->next;

}

printf（"\n"）;

}

voidDestroyString（）

{

//块链类型的字符串无法销毁

}

intmain（）

{

char*s1="ABCDEFGHI",*s2="12345",*s3="",*s4="asd#tr",*s5="ABCD";

intk;

intpos,len;

LStringt1,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",pos）;

printf（"在串t1的第pos个字符之前插入串t2，请输入pos:

"）;

scanf（"%d",&pos）;

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",&pos,&len）;

SubString（&t2,t1,pos,len）;

printf（"串t2为:

"）;

StrPrint（t2）;

printf（"StrCompare（t1,t2）=%d\n",StrCompare（t1,t2））;

printf（"删除串t1中的子字符串：

从第pos个字符起删除len个字符。

"

"请输入pos,len：

"）;

scanf（"%d,%d",&pos,&len）;

k=StrDelete（&t1,pos,len）;

if（k）

{

printf（"从第%d位置起删除%d个元素后串t1为:

",pos,len）;

StrPrint（t1）;

}

system（"pause"）;

return0;

}

/*

输出效果：

初始化串t1后，串t1空否？

1（1:

空0:

否）串长=0

出错

出错

串t1为:

ABCDEFGHI

串t1空否？

0（1:

空0:

否）串长=9

串t2为:

12345

由串t1拷贝得到串t3,串t3为:

ABCDEFGHI

串t4为:

ABCD

用t2取代串t3中的t4串后，串t3为:

12345EFGHI

清空串t1后，串t1空否？

1（1:

空0:

否）串长=0

串t1（=t2+t3）为:

1234512345EFGHI

去除不必要的占位符后，串t1为:

1234512345EFGHI

pos=6

在串t1的第pos个字符之前插入串t2，请输入pos:

3

插入串t2后，串t1为:

2345EFGHI

求从t1的第pos个字符起,长度为len的子串t2,请输入pos,len:

2,2

串t2为:

21

StrCompare