严蔚敏版数据结构C语言版参考答案第五章(2)

p->next=NULL; }//StringCopy

char StringCompare(LString s,LString t)//串的比较,s>t时返回正数,s=t时返回0,s

for(p=s->next,q=t->next;p&&q&&p->ch==q->ch;p=p->next,q=q->next); if(!p&&!q) return 0;

else if(!p) return -(q->ch); else if(!q) return p->ch; else return p->ch-q->ch; }//StringCompare

int StringLen(LString s)//求串s的长度(元素个数) {

for(i=0,p=s->next;p;p=p->next,i++); return i;

}//StringLen

LString * Concat(LString s,LString t)//连接串s和串t形成新串,并返回指针 {

p=malloc(sizeof(LStrNode)); for(q=p,r=s->next;r;r=r->next) {

q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; }//for //复制串s

for(r=t->next;r;r=r->next) {

q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; }//for //复制串t q->next=NULL; return p; }//Concat

LString * Sub_String(LString s,int start,int len)//返回一个串,其值等于串s从start位置起长为len的子串 {

p=malloc(sizeof(LStrNode));q=p;

for(r=s;start;start--,r=r->next); //找到start所对应的结点指针r for(i=1;i<=len;i++,r=r->next) {

q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; } //复制串t

q->next=NULL; return p;

}//Sub_String 4.22

void LString_Concat(LString &t,LString &s,char c)//用块链存储结构,把串s插入到串t的字符c之后 {

p=t.head;

while(p&&!(i=Find_Char(p,c))) p=p->next; //查找字符c if(!p) //没找到 {

t.tail->next=s.head;

t.tail=s.tail; //把s连接在t的后面 } else {

q=p->next;

r=(Chunk*)malloc(sizeof(Chunk)); //将包含字符c的节点p分裂为两个 for(j=0;jch[j]='#'; //原结点p包含c及其以前的部分 for(j=i;j

r->ch[j]=p->ch[j];

p->ch[j]='#'; //p的后半部分和r的前半部分的字符改为无效字符'#' }

p->next=s.head; s.tail->next=r;

r->next=q; //把串s插入到结点p和r之间 }//else

t.curlen+=s.curlen; //修改串长 s.curlen=0;

}//LString_Concat

int Find_Char(Chunk *p,char c)//在某个块中查找字符c,如找到则返回位置是第几个字符,如没找到则返回0 {

for(i=0;ich[i]!=c;i++); if(i==CHUNKSIZE) return 0; else return i+1; }//Find_Char 4.23

int LString_Palindrome(LString L)//判断以块链结构存储的串L是否为回文序列,是则返回1,否则返回0

{

InitStack(S);

p=S.head;i=0;k=1; //i指示元素在块中的下标,k指示元素在整个序列中的序号(从1开始)

for(k=1;k<=S.curlen;k++) {

if(k<=S.curlen/2) Push(S,p->ch[i]); //将前半段的字符入串 else if(k>(S.curlen+1)/2) {

Pop(S,c); //将后半段的字符与栈中的元素相匹配 if(p->ch[i]!=c) return 0; //失配 }

if(++i==CHUNKSIZE) //转到下一个元素,当为块中最后一个元素时,转到下一块 {

p=p->next; i=0; } }//for

return 1; //成功匹配 }//LString_Palindrome 4.24

void HString_Concat(HString s1,HString s2,HString &t)//将堆结构表示的串s1和s2连接为新串t {

if(t.ch) free(t.ch);

t.ch=malloc((s1.length+s2.length)*sizeof(char)); for(i=1;i<=s1.length;i++) t.ch[i-1]=s1.ch[i-1]; for(j=1;j<=s2.length;j++,i++) t.ch[i-1]=s2.ch[j-1]; t.length=s1.length+s2.length; }//HString_Concat 4.25

int HString_Replace(HString &S,HString T,HString V)//堆结构串上的置换操作,返回置换次数 {

for(n=0,i=0;i<=S.length-T.length;i++) {

for(j=i,k=0;k

if(k==T.length) //找到了与T匹配的子串:分三种情况处理 {

if(T.length==V.length)

for(l=1;l<=T.length;l++) //新子串长度与原子串相同时:直接替换 S.ch[i+l-1]=V.ch[l-1];

else if(T.length …… 此处隐藏：361字，全部文档内容请下载后查看。喜欢就下载吧 ……