【Test-6-4】假设二叉树中每个结点值为单个字符, 采用二叉链存储结构存储。下面算法的功能是:求二叉
void strinit(HString s); //置s为空串
int strlen(HString s); //求串s的长度
void strcpy(HString to,HString from); //将串from复制到串to
void streat(HString to,HString from); //将串from联接到串to的末尾
int strcmp(HString s1,HString s2);
//比较串s1和s2的大小,当s1<s2,s1=s2或s1>s2时,
//返回值小于0,等于0或大于0
HString substr(HString s,int i,int m);
//返回串S中从第i(0≤i≤strlen(s)-m)个字符起长度为m的子串阅读下列算法f32,并回答问题:
(1)设串S="abcdabcd",T="bcd",V="bcda",写出执行f32(S,T,V)之后的S;
(2)简述算法f32的功能。
void f 32(HString S,HString T,HString V){
int m,n,pos,i;
HString news;
strinit(news);
n=strlen(S);
m=strlen(T);
pos=i=0;
while(i<=n-m){
if(strcmp(substr(S,i,m),T)!=0)i++;
else{
strcat(news,substr(S,pos,i-pos));
strcat(news,V);
pos=i=i+m;
}
}
strcat(news,substr(S,pos,n—pos));
strcpy(S,news);
}
【程序5说明】
设M叉树采用列表法表示,即每棵子树对应一个列表,列表的结构为:子树根结点的值部分(设为一个字符)和用“()”括起来的各子树的列表(如有子树的话),各子列表间用“,”分隔。例如下面的三叉树可用列表a(b(c,d),e,f(g,h,i))表示。
本程序输入列表,生成一棵M叉树,并由M叉树输出列表。假定输入无错误。
【程序5】
include<Stdio.h>
include<Stdlib.h>
define M 3
typedef struct node{char val;
struct node,subTree[M];
}NODE;
char buf[255],*Str=buf;
NODE * d=NULL
NODE*makeTree()/*由列表生成M叉树*/
{int k;NODE*s;
s=(1);
s->val= *Str++;
for(k=0;k<M;k++)s->subTree[k]=NULL;
if(* str='('){
k=0;
do{str++;
s->sub Tree[k]=(2);
if(*Str==')'){Str++;break;}
k=k+1;
}while((3));
}
return s;
}
void walkTree(NODE*t)/*由M又树输出列表*/
{int i;
if(t!=NULL){
(4)
if(t->subTree[0]==NULL)return;
putchar('(');
for(i=0;i<M;i++){
(5);
if(i!=M-1&&t->subTree[i+1]!=NULL)
putchar(',');
}
putchar(')');
}
}
void main()
{printf("Enter exp:");
scanf("%s",str);
d=makeTree();
walkTree(d);putchar('\n");
}
阅读下列程序说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。
【程序5说明】
设M叉树采用列表法表示,即每棵子树对应一个列表,列表的结构为:子树根结点的值部分(设为一个字符)和用"()"括起来的各子树的列表(如有子树的话),各子列表间用","分隔。例如下面的三叉树可用列表a(b(c,d),e,f(g,h,i))表示。
本程序输入列表,生成一棵M叉树,并由M叉树输出列表。假定输入无错误。
【程序5】
#include
#include
B.h>
#define M 3
typedef struct node{char val;
struct node*subTree[M];
}NODE;
char buf[255],*str=buf;
NODE*d=NULL
NODE*makeTree()/*由列表生成M叉树*/
{int k;NODE*s;
s= (1) ;
s->val=*str++;
for(k=0;ksubTree[k]=NULL;
if(*str=′(′){
k=0;
do{str++;
s->subTree[k]= (2) ;
if(*str==′)′){str++;break;}
k=k+1;
}while((3) );
}
return s;
}
void walkTree(NODE*t)/*由M叉树输出列表*/
{int i;
if(t!=NULL){
(4)
if(t->subTree[0]==NULL)return;
putchar(′(′);
for(i=0;i
(5) ;
if(i!=M-1&&t->subTree[i+1]!= NULL)
putchar(′,′);
}
putchar(′)′);
}
}
void main()
{printf("Enter exp:");
scanf("%s",str);
d=makeTree();
walkTree(d);putchar(′\n′);
}
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!