严蔚敏数据结构C语言版习题集答案.docx
《严蔚敏数据结构C语言版习题集答案.docx》由会员分享，可在线阅读，更多相关《严蔚敏数据结构C语言版习题集答案.docx（29页珍藏版）》请在冰点文库上搜索。
严蔚敏数据结构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（"Inputvalueof
x:
"）;
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（int
A[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）;;
}
else
irstout;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->next
升级会员 