📄 xtjd4.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>New Page 1</TITLE>
<META content="text/html; charset=gb2312" http-equiv=Content-Type>
<META content="Microsoft FrontPage 4.0" name=GENERATOR>
<META content=FrontPage.Editor.Document name=ProgId></HEAD>
<BODY>
<P align=left><B><SPAN
style="COLOR: blue; FONT-FAMILY: 宋体; FONT-SIZE: 24pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">数据结构辅导站</SPAN><SPAN
lang=EN-US
style="COLOR: blue; FONT-FAMILY: Times New Roman; FONT-SIZE: 24pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-spacerun: yes; mso-fareast-font-family: 宋体">
</SPAN></B><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:12.0pt;font-family:宋体;
mso-bidi-font-family:"Times New Roman";mso-font-kerning:1.0pt;mso-ansi-language:
EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA"><a href="index.htm">返回主页</a></span></P>
<HR>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">4.3</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">《数据结构题集》P.190 </font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">4.25</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">typedef struct {</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2"> char *ch;</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2"> int length;</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">}HString;</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2"> </font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">Status Replace(HString &s, HString t, HString v){</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
//用串v替换串s中所有的子串t</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
if (t.length==0) return ERROR;</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
i=0; j=0;</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
while (i<=s.length-1) {</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
while (i<=s.length-1 && j<=t.length-1) {</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
if (s.ch[i]==t.ch[j]){++i; ++j;}</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
else {i=i-j+2; j=0;}</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
}//while</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
if (j<=t.length-1) return OK;</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
pos=i-t.length;</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
if (!(s.ch=(char *)realloc(s.ch, (s.length-t.length+v.length)*sizeof(char))))</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
exit(OVERFLOW);</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
for (k=s.length-1; k>=i; --k)</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
s.ch[k-t.length+v.length]=s.ch[k];</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
s.ch[pos..pos+v.length-1]=v[0..v.length-1];</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
s.length=s.length-t.length+v.length;</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
i=pos+v.length; j=0;</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
}//while</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">
return OK;</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2">}//Replace</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"><font size="2"><font color="#FF0000">注意</font>：在这里不能用串的其它基本操作来实现Replace</font></p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"> </p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"> </p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"> </p>
<font color="#0000FF">(以下内容来自http://bbs.kaoyan.com)</font>
<p>第四章 串
<p>4.10
<p>void String_Reverse(Stringtype s,Stringtype &r)//求s的逆串r<br>
{<br>
StrAssign(r,''); //初始化r为空串<br>
for(i=Strlen(s);i;i--)<br>
{<br>
StrAssign(c,SubString(s,i,1));<br>
StrAssign(r,Concat(r,c)); //把s的字符从后往前添加到r中<br>
}<br>
}//String_Reverse
<p>4.11
<p>void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r<br>
{<br>
StrAssign(r,'');<br>
for(i=1;i<=Strlen(s);i++)<br>
{<br>
StrAssign(c,SubString(s,i,1));<br>
for(j=1;j<i&&StrCompare(c,SubString(s,j,1));j++);
//判断s的当前字符c是否第一次出现<br>
if(i==j)<br>
{<br>
for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++);
//判断当前字符是否包含在t中<br>
if(k>Strlen(t)) StrAssign(r,Concat(r,c));<br>
}<br>
}//for<br>
}//String_Subtract
<p>4.12
<p>int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数<br>
{<br>
for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围<br>
if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串<br>
{ //分别把T的前面和后面部分保存为head和tail<br>
StrAssign(head,SubString(S,1,i-1));<br>
StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));<br>
StrAssign(S,Concat(head,V));<br>
StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串<br>
i+=Strlen(V); //当前指针跳到插入串以后<br>
n++;<br>
}//if<br>
return n;<br>
}//Replace<br>
分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place',
T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?
<p>4.13
<p>int Delete_SubString(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数<br>
{<br>
for(n=0,i=1;i<=Strlen(s)-Strlen(t)+1;i++)<br>
if(!StrCompare(SubString(s,i,Strlen(t)),t))<br>
{<br>
StrAssign(head,SubString(S,1,i-1));<br>
StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1));<br>
StrAssign(S,Concat(head,tail)); //把head,tail连接为新串<br>
n++;<br>
}//if<br>
return n,<br>
}//Delete_SubString
<p>4.14
<p>Status NiBoLan_to_BoLan(Stringtype str,Stringtype &new)//把前缀表达式str转换为后缀式new<br>
{<br>
Initstack(s); //s的元素为Stringtype类型<br>
for(i=1;i<=Strlen(str);i++)<br>
{<br>
r=SubString(str,i,1);<br>
if(r为字母) push(s,r);<br>
else<br>
{<br>
if(StackEmpty(s)) return ERROR;<br>
pop(s,a);<br>
if(StackEmpty(s)) return ERROR;<br>
pop(s,b);<br>
StrAssign(t,Concat(r,b));<br>
StrAssign(c,Concat(t,a)); //把算符r,子前缀表达式a,b连接为新子前缀表达式c<br>
push(s,c);<br>
}<br>
}//for<br>
pop(s,new);<br>
if(!StackEmpty(s)) return ERROR;<br>
return OK;<br>
}//NiBoLan_to_BoLan<br>
分析:基本思想见书后注释3.23.请读者用此程序取代作者早些时候对3.23题给出的程序.
<p>4.15
<p>void StrAssign(Stringtype &T,char chars&#;)//用字符数组chars给串T赋值,Stringtype的定义见课本<br>
{<br>
for(i=0,T[ 0 ]=0;chars[i];T[ 0 ]++,i++) T[i+1]=chars[i];<br>
}//StrAssign
<p>4.16
<p>char StrCompare(Stringtype s,Stringtype t)//串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数<br>
{<br>
for(i=1;i<=s[ 0 ]&&i<=t[ 0 ]&&s[i]==t[i];i++);<br>
if(i>s[ 0 ]&&i>t[ 0 ]) return 0;<br>
else if(i>s[ 0 ]) return -t[i];<br>
else if(i>t[ 0 ]) return s[i];<br>
else return s[i]-t[i];<br>
}//StrCompare
<p>4.17
<p>int String_Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数<br>
{<br>
for(n=0,i=1;i<=S[ 0 ]-T[ 0 ]+1;i++)<br>
{<br>
for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++);<br>
if(k>T[ 0 ]) //找到了与T匹配的子串:分三种情况处理<br>
{<br>
if(T[ 0 ]==V[ 0 ])<br>
for(l=1;l<=T[ 0 ];l++) //新子串长度与原子串相同时:直接替换<br>
S[i+l-1]=V[l];<br>
else if(T[ 0 ]<V[ 0 ]) //新子串长度大于原子串时:先将后部右移<br>
{<br>
for(l=S[ 0 ];l>=i+T[ 0 ];l--)<br>
S[l+V[ 0 ]-T[ 0 ]]=S[l];<br>
for(l=1;l<=V[ 0 ];l++)<br>
S[i+l-1]=V[l];<br>
}<br>
else //新子串长度小于原子串时:先将后部左移<br>
{<br>
for(l=i+V[ 0 ];l<=S[ 0 ]+V[ 0
]-T[ 0 ];l++)<br>
S[l]=S[l-V[ 0 ]+T[ 0
]];<br>
for(l=1;l<=V[ 0 ];l++)<br>
S[i+l-1]=V[l];<br>
}<br>
S[ 0 ]=S[ 0 ]-T[ 0 ]+V[ 0 ];<br>
i+=V[ 0 ];n++;<br>
}//if<br>
}//for<br>
return n;<br>
}//String_Replace
<p>4.18
<p>typedef struct {<br>
char ch;<br>
int num;<br>
} mytype;<br>
void StrAnalyze(Stringtype S)//统计串S中字符的种类和个数<br>
{<br>
mytype T[MAXSIZE]; //用结构数组T存储统计结果<br>
for(i=1;i<=S[ 0 ];i++)<br>
{<br>
c=S[i];j=0;<br>
while(T[j].ch&&T[j].ch!=c) j++; //查找当前字符c是否已记录过<br>
if(T[j].ch) T[j].num++;<br>
else T[j]={c,1};<br>
}//for<br>
for(j=0;T[j].ch;j++)<br>
printf("%c: %d\n",T[j].ch,T[j].num);<br>
}//StrAnalyze
<p>4.19
<p>void Subtract_String(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r<br>
{<br>
r[ 0 ]=0;<br>
for(i=1;i<=s[ 0 ];i++)<br>
{<br>
c=s[i];<br>
for(j=1;j<i&&s[j]!=c;j++); //判断s的当前字符c是否第一次出现<br>
if(i==j)<br>
{<br>
for(k=1;k<=t[ 0 ]&&t[k]!=c;k++);
//判断当前字符是否包含在t中<br>
if(k>t[ 0 ]) r[++r[ 0 ]]=c;<br>
}<br>
}//for<br>
}//Subtract_String
<p>4.20<br>
int SubString_Delete(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数<br>
{<br>
for(n=0,i=1;i<=s[ 0 ]-t[ 0 ]+1;i++)<br>
{<br>
for(j=1;j<=t[ 0 ]&&s[i+j-1]==t[i];j++);<br>
if(j>m) //找到了与t匹配的子串<br>
{<br>
for(k=i;k<=s[ 0 ]-t[ 0 ];k++) s[k]=s[k+t[
0 ]]; //左移删除<br>
s[ 0 ]-=t[ 0 ];n++;<br>
}<br>
}//for<br>
return n;<br>
}//Delete_SubString
<p>4.21
<p>typedef struct{<br>
char
ch;<br>
LStrNode
*next;<br>
}
LStrNode,*LString; //链串结构
<p>void StringAssign(LString &s,LString t)//把串t赋值给串s<br>
{<br>
s=malloc(sizeof(LStrNode));<br>
for(q=s,p=t->next;p;p=p->next)<br>
{<br>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -