第4章 串、数组和广义表
1．选择题
BBDCA ABBC
2．填空题
（1）两个串的长度相等且对应位置的字符相同
（2）零个字符的串，0
（3）由一个或多个空格字符组成的串，包含的空格个数
（4）展开广义表所包含括号的最大层数
（5）LOC (A[0][0]) + (n*i + j) k
（6）332
（7）1208
（8）42
3．问答题
（1）一个串可以包含若干个子串，子串是指串中任意个连续字符组成的子序列，串的最大子串是它本身，最小子串是空串。因串s中无重复字符且共有8个字符，故含一个字符的子串有8个，含2个字符的子串有7个，含3个字符的子串有6个，含4个字符的子串有5个，含5个字符的子串有4个，含6个字符的子串有3个，含7个字符的子串有2个，另有一个空串和它本身。
子串总数=8+7+6+5+4+3+2+1=37
（2）串S的长度为n，其中的字符各不相同，所以S中含1个字符的子串有n个，含2个字符的子串有n-1个，……，含n-2个字符的子串有3个，含n-1个字符的子串有2个，所求子串个数是n(n-1)/2-1。
（3）
|
下标j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
串T |
a |
b |
c |
a |
a |
c |
a |
b |
a |
c |
a |
|
Next[j] |
-1 |
0 |
0 |
-1 |
1 |
1 |
-1 |
0 |
2 |
1 |
-1 |
（4）按行优先的存储次序：
A[0][0][0][0]，A[0][0][0][1]，A[0][0][1][0]，A[0][0][1][1]，
A[0][1][0][0]，A[0][1][0][1]，A[0][1][1][0]，A[0][1][1][1]，
A[1][0][0][0]，A[1][0][0][1]，A[1][0][1][0]，A[1][0][1][1]，
A[1][1][0][0]，A[1][1][0][1]，A[1][1][1][0]，A[1][1][1][1]
按列优先的存储次序：
A[0][0][0][0]，A[1][0][0][0]，A[0][1][0][0]，A[1][1][0][0]，
A[0][0][1][0]，A[1][0][1][0]，A[0][1][1][0]，A[1][1][1][0]，
A[0][0][0][1]，A[1][0][0][1]，A[0][1][0][1]，A[1][1][0][1]，
A[0][0][1][1]，A[1][0][1][1]，A[0][1][1][1]，A[1][1][1][1]。
（5）该广义表的一种存储图如图A-2所示。
图A-2 广义表存储结构
（6）各小题答案如下：
①该广义表的存储结构如图A-3所示。
A-3 广义表存储结构
②该广义表的表头为a，表尾为((b,(a,b)),((a,b),(a,b)))。
③该广义表的深度为3。
（7）广义表A的一种存储结构如图A-4所示。A的长度为5，深度为4。
求出e的方式是：head[tail[head[head[head[tail[tail[tail[tail[[A]]]]]]]]]]
图A-4 广义表存储结构
4．上机操作题
（1）先比较s和t公共长度部分的相应字符，若前者字符大于后者字符，则返回1；若前者字符小于后者字符，则返回-1；相等时继续比较；当所有公共长度部分的相应字符均相同时，再比较两者的长度，当两者的长度相等时返回0，前者长度大于后者长度，则返回1；若前者长度小于后者长度，则返回-1，算法如下。
int strcmp(SqString *s, SqString *t)
{
int i, minlen;
if(s->len<t->len)
minlen=s->len; /*计算minlen为较短长度*/
else
minlen=t->len;
i=0;
while(i<=minlen)
{
if(s->data[i]<t->data[i])
return(-1); /*s<t*/
else if(s->data[i]>t->data[i])
return(1); /*s>t*/
else
i++;
}
if(s->len==t->len)
return(0); /*s=t*/
else if(s->len<t->len)
return(-1); /*s<t*/
else
return(1); /*s>t*/
}
（2）算法如下：
int pelindrom(Sstring s)
{
int i=0,j=s.len-1;
while(j-i>=1)
if(s.data[i]==s.data[j])
{
i++;j--;
}
else retum 0;
return 1;
}
（3）算法如下：
Sstring sreplace(Sstring s,int i,int j,Sstring t)
{
int k;
Sstring p;p.len=0;
if(i<1||i>s.len||(i+j-1)>s.len||j<0)
{printf("i error"); return p;}
for(k=0;k<i-1;k++)
p.data[k]=s.data[k];
for(k=o;k<t.len;k++)
p.data[i+k-1]=t.data[k];
for(k=i+j-1;k<s.len;k++)
p.data[k-j+t.len]=s.data[k];
p.len=s.len-j+t.len;
return p;
}
（4）算法如下：
int countsub(Sstring s,Sstring t)
{
int j,k,i=0,c=0,m=t.len,n=s.len;
while(i<=n-m)
{
j=0;k=i;
while(j<m&&s.data[k]==t.data[j])
{k++;j++;}
if(j==m)
{
c++;i+=m;
}
else i++;
}
return C;
}
（5）算法如下：
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
k=n(i-1)-i(i-1)/2+j
B[k]=A[i][j]
}
if(i>j)
p=0;
else
{
k=n(i-1)-i(i-1)/2+j
p=B[k]
}
（6）采用一般递归方法对应的求解算法如下：
char MaxAtom1(GLNode *g)
{
char m=0,m1; /*m赋初值0，表示最小原子值*/
while(g!=NULL) /*对每个元素进行循环*/
{
if(g->tag==1) /*为子表的情况*/
{
m1=MaxAtom1(g->val.sublist); /*对子表递归调用*/
if (m1>m) m=m1;
}
else if(g->val.data>m) /*为原子时，进行原子比较*/
m=g->val.data;
g=g->link;
}
return(m);
}
采用head()和tail()对应的求解算法如下：
char MaxAtom2(GLNode *g)
{
char m=0,m1,m2; /*m赋初值0，表示最小原子值*/
if(g==NULL) /*g为NULL时*/
return(m);
else if(g->tag==0) /*g为原子时*/
return(g->val.data);
else if(g->tag==1 && g->val.sublist==NULL) /*g为空表时*/
return(m);
else /*g为非空子表时*/
{
m1=MaxAtom2(head(g)); /*在表头中递归查找*/
m2=MaxAtom2(tail(g)); /*在表尾中递归查找*/
m=(m1>m2)?m1:m2;
return(m);
}
}
（7）本题的递归模型如下：
NULL 当g=NULL时
f(g)= g 当g为原子或空表时
f(head(g))作为f(tail(g))的最后一个元素 当g为非空子表时
对应的递归算法如下：
GLNode *Reverse(GLNode *g)
{
GLNode *h,*t,*h1,*t1,*p;
if(g==NULL) /*为NULL时,返回NULL*/
return NULL;
else if(g->tag==1 && g->val.sublist!=NULL) /*为非空子表*/
{
h=head(g);
h1=Reverse(h); /*求表头的逆置得到h1*/
t=tail(g);
t1=Reverse(t); /*求表尾的逆置得到t1*/
if(t1->val.sublist==NULL) /*逆置后的表尾为空表时，将h1外加()后返回*/
{
t1->val.sublist=h1;
return(t1);
}
else /*逆置后的表尾为不空表时，将h1作为t1的最后一个元素，返回t1*/
{
p=t1->val.sublist;
while(p->link!=NULL) p=p->link;
p->link=h1;
return(t1);
}
}
else /*为原子或空表时，返回g*/
return(g);
}