严蔚敏数据结构C语言版习题集答案.docx
《严蔚敏数据结构C语言版习题集答案.docx》由会员分享,可在线阅读,更多相关《严蔚敏数据结构C语言版习题集答案.docx(28页珍藏版)》请在冰点文库上搜索。
严蔚敏数据结构C语言版习题集答案
严蔚敏《数据结构(C语言版)习题集》答案
第一章绪论
voidprint_descending(intx,inty,intz)....+f[m-k]
=f[m-1]+f[m-2]+......+f[m-k]+f[m-k-1]-f[m-k-1]
=2*f[m-1]-f[m-k-1]
所以上述算法的时间复杂度仅为O(m).如果采用递归设计,将达到O(k^m).即使采用暂存中间结果的方法,也将达到O(m^2).
typedefstruct{
char*sport;
enum{male,female}gender;
charschoolname;port!
=NULL)
{
switch(result[i].schoolname)
{
case'A':
score[0].totalscore+=result[i].score;
if(result[i].gender==0)score[0].malescore+=result[i].score;
elsescore[0].femalescore+=result[i].score;
break;
case'B':
score[0].totalscore+=result[i].score;
if(result[i].gender==0)score[0].malescore+=result[i].score;
elsescore[0].femalescore+=result[i].score;
break;
…… …… ……
}
i++;
}
for(i=0;i<5;i++)
{
printf("School%d:
\n",i);
printf("Totalscoreofmale:
%d\n",score[i].malescore);
printf("Totalscoreoffemale:
%d\n",score[i].femalescore);
printf("Totalscoreofall:
%d\n\n",score[i].totalscore);
}
}
voidpolyvalue()
{
floattemp;
float*p=a;
printf("Inputnumberofterms:
");
scanf("%d",&n);
printf("Inputvalueofx:
");
scanf("%f",&x);
printf("Inputthe%dcoefficientsfroma0toa%d:
\n",n+1,n);
p=a;xp=1;sum=0;
StatusInsert(LinkList&L,inti,intb)
voidmerge1(LinkList&A,LinkList&B,LinkList&C)
voidSqList_Intersect(SqListA,SqListB,SqList&C)
voidLinkList_Intersect_Delete(LinkList&A,LinkListB,LinkListC)iList为带头结点的单循环链表类型.
{
s=L->next;
A=(CiList*)malloc(sizeof(CiLNode));p=A;
B=(CiList*)malloc(sizeof(CiLNode));q=B;
C=(CiList*)malloc(sizeof(CiLNode));r=C;.4,2的顺序重排双向循环链表L中的所有结点
{
p=;
while(p->next!
=L&&p->next->next!
=L)
{
p->next=p->next->next;
p=p->next;
}同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.
DuLNode*Locate_DuList(DuLinkedList&L,intx) intx;
inty;
}coordinate;
voidRepaint_Color(intg[m][n],inti,intj,intcolor)归形式的算法该怎么写呢?
voidNiBoLan(char*str,char*new)题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进行连接操作:
c=link(a,b).
Statusg(intm,intn,int&s)
voidInitCiQueue(CiQueue&Q)
StatusEnCyQueue(CyQueue&Q,intx)省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:
设S='place',T='ace',V='face',则省掉i+=Strlen(V);运行时会出现什么结果?
intDelete_SubString(Stringtype&s,Stringtypet)读者用此程序取代作者早些时候对题给出的程序.
voidStrAssign(Stringtype&T,charchars)h&&T[j].ch!
=c)j++;h)T[j].num++;
elseT[j]={c,1};
}h;j++)
printf("%c:
%d\n",T[j].ch,T[j].num);
}前一个程序的区别在于,串s业已存在.
{
for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next)
{
p->ch=q->ch;pre=p;
}
while(q)
{
p=(LStrNode*)malloc(sizeof(LStrNode));
p->ch=q->ch;
pre->next=p;pre=p;
}
p->next=NULL;
}算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明"重复子串"是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2).
voidGet_LPubSub(StringtypeS,StringtypeT) for(k=0,j=jmin;j<=jmax;j++)
{
if(A[j]==B[j-i])k++;
elsek=0;
if(k>maxlen)
{
lps1=j-k+1;lps2=j-i-k+1;maxlen=k;
}
}一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o(strlrn(s)*strlen(t))。
第五章数组和广义表
voidRSh(intA[n],intk)....直到最终回到A[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个"循环链"上面.举例如下:
n=15,k=6,则p=3.
第一条链:
A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0].
第二条链:
A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].
第三条链:
A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].
恰好使所有元素都右移一次.
虽然未经数学证明,但作者相信上述规律应该是正确的.
voidGet_Saddle(intA[m][n])里采用了一个递归函数来找到所有满足和为i的m个自然数作为各变元的指数.只要先取第一个数为j,然后再找到所有满足和为i-j的m-1个自然数就行了.要注意j的取值范围必须使剩余m-1个自然数能够找到,所以不能小于i-(m-1)*maxn,也不能大于i.只要找到了一组符合条件的数,就可以在存储多项式系数的数组中确定对应的项的系数的位置,并且在系数不为0时输出对应的项.
voidTSMatrix_Add(TSMatrixA,TSMatrixB,TSMatrix&C) while[pb].i while[pa].i==x&&[pb].i==x)==[pb].j)
{
ce=[pa].e+[pb].e;
if(ce)=x;
[pc].j=[pa].j;
[pc].e=ce;
pa++;pb++;pc++;
}
}>[pb].j)
{
[pc].i=x;
[pc].j=[pb].j;
[pc].e=[pb].e;
pb++;pc++;
}
else
{
[pc].i=x;
[pc].j=[pa].j;
[pc].e=[pa].e
pa++;pc++;
}
}=x;
[pc].j=[pa].j;
[pc].e=[pa].e
pa++;pc++;
}
while[pb]==x)=x;
[pc].j=[pb].j;
[pc].e=[pb].e;
pb++;pc++;
}
} while[pb].i while[pa].i==x&&[pb].i==x)==[pb].j)
{
ne=[pa].e+[pb].e;
if(ne)=x;
[pc].j=[pa].j;
[pc].e=ne;
pa++;pb++;pc++;
}
}>[pb].j)
{
[pc].i=x;
[pc].j=[pb].j;
[pc].e=[pb].e;
pb++;pc++;
}
else
{
[pc].i=x;
[pc].j=[pa].j;
[pc].e=[pa].e
pa++;pc++;
}
}=x;
[pc].j=[pa].j;
[pc].e=[pa].e
pa++;pc++;
}
while[pb]==x)=x;
[pc].j=[pb].j;
[pc].e=[pb].e;
pb++;pc++;
}
}!
=j;s++);==j)eq
returnOK;
}
returnERROR;
}
voidMPList_PianDao(MPList&L)
voidGList_PrintList(GListA)是层序遍历的基本思想.
第六章树和二叉树
intIs_Descendant_C(intu,intv)
intBitree_Sim(BitreeB1,BitreeB2)次根据栈顶元素的mark域值决定做何种动作.
typedefstruct{
intdata;
EBTNode*lchild;
EBTNode*rchild;
EBTNode*parent;
enum{0,1,2}mark;
}EBTNode,EBitree;
typedefstruct{
intdata;
PBTNode*lchild;
PBTNode*rchild;
PBTNode*parent;
}PBTNode,PBitree;.
scanf("%d",&k);
c=0;.
}
voidLayerOrder(BitreeT)相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.
StatusCreateBitree_Triplet(Bitree&T)意:
为了能用一个统一的公式计算子孙数目,所以当T为空指针时,要返回-1而不是0.
BTNode*PreOrder_Next(BTNode*p)不是哪儿理解错了?
BitreePostOrder_Next(Bitreep)irstchild)return1;
for(sd=1,p=[T].firstchild;p;p=p->next)
if((d=SubDepth(p->child))>sd)sd=d;
returnsd+1;
}arent)dep++;.
Build_Sub(1,n,1,n);.
}
分析:
本算法利用了这样一个性质,即一棵子树在前序和中序序列中所占的位置总是连续的.因此,就可以用起始下标和终止下标来确定一棵子树.Pre_Start,Pre_End,In_Start和In_End分别指示子树在前序子序列里的起始下标,终止下标,和在中序子序列里的起始和终止下标.
typedefstruct{
CSNode*ptr;
CSNode*lastchild;
}NodeMsg;tr=(CSNode*)malloc(sizeof(CSNode));
Tree[i].ptr->data=[i].data;arent>=0)arent;astchild))tr->firstchild=Tree[i].ptr;astchild->nextsib=Tree[i].ptr;astchild=Tree[i].ptr;tr=(CSNode*)malloc(sizeof(CSNode));
Tree[0].data=c;
Tree[0].ptr->data=c;
while((p=getchar())!
='^'&&(c=getchar())!
='^')
{
Tree[n].ptr=(CSNode*)malloc(sizeof(CSNode));
Tree[n].data=c;
Tree[n].ptr->data=c;
for(k=0;Tree[k].data!
=p;k++);ata!
=p)returnERROR;tr;
if(!
r->firstchild)
r->firstchild=Tree[n].ptr;
elseTree[k].lastchild->nextsib=Tree[n].ptr;
Tree[k].lastchild=Tree[n].ptr;
StatusCreateBiTree_GList(BiTree&T)ata);irstchild;p;p=p->next)
Print_CSTree(p->child,i+1);.
Print_CTree,0);.
}算法另一个改进之处在于加入了广义表格式是否合法的判断.
voidPrintGlist_CSTree(CSTreeT)ata=c;
i=pos++;irstchild=p;
p->child=pos;irtchild=NULL;
voidPrintGList_CTree(CTreeT,inti)ata);
if[i].firstchild)ata=getchar();i].firstarc)[i].firstarc=p;
else
{
for(q=[i].firstarc;q->nextarc;q=q->nextarc);
q->nextarc=p;
}
p->adjvex=j;p->nextarc=NULL;
}dj)
{
[i][j].adj=1;
++;
}
returnOK;
}dj=0;
;
returnOK;
}
StatusDelete_Arc(MGraph&G,charv,charw)dj)
{
[i][j].adj=0;
;
}
returnOK;
}余算法请自行写出.
StatusInsert_Arc(ALGraph&G,charv,charw)irstarc)[i].firstarc=p;
else
{
for(q=[i].firstarc;q->q->nextarc;q=q->nextarc)
if(q->adjvex==j)returnERROR;余算法请自行写出.
StatusDelete_Vex(OLGraph&G,charv)irstin->tailvex==m)irstin;
[i].firstin=q->hlink;
free(q);;
}
elseirstin;p&&p->hlink->tailvex!
=m;p=p->hlink);
if(p)
{
q=p->hlink;
p->hlink=q->hlink;
free(q);;
}
}irstout->headvex==m)irstout;
[i].firstout=q->tlink;
free(q);;
}
elseirstout;p&&p->tlink->headvex!
=m;p=p->tlink);
if(p)
{
q=p->tlink;
p->tlink=q->tlink;
free(q);;
}
}irstin;p;p=p->hlink)
p->headvex--;
for(p=[i].firstout;p;p=p->tlink)
p->tailvex--;余算法请自行写出.
StatusDelete_Arc(AMLGraph&G,charv,charw)irstedge->jvex==j)
[i].firstedge=[i].firstedge->ilink;
else
{
for(p=[i].firstedge;p&&p->ilink->jvex!
=j;p=p->ilink);
if(!
p)returnERROR;irstedge->ivex==i)
[j].firstedge=[j].firstedge->jlink;
else
{
for(p=[j].firstedge;p&&p->jlink->ivex!
=i;p=p->jlink);
if(!
p)returnERROR;ata=getchar();irstedge)[i].firstedge=p;
else
{
q=[i].firstedge;
while(q)
{
r=q;
if(q->ivex==i)q=q->ilink;
elseq=q->jlink;
}
if(r->ivex==i)r->ilink=p;irstedge)[j].firstedge=p;
else
{
q=[i].firstedge;
while(q)
{
r=q;
if(q->jvex==j)q=q->jlink;
elseq=q->ilnk;
}
if(r->jvex==j)r->jlink=p;
elser->ilink=p;
}
intPass_ALGraph(ALGraphG)irstarc;p;p=p->nextarc)
{
y=p-