数据结构习题集答案c版清华大学严蔚敏Word格式文档下载.docx
《数据结构习题集答案c版清华大学严蔚敏Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数据结构习题集答案c版清华大学严蔚敏Word格式文档下载.docx（12页珍藏版）》请在冰点文库上搜索。
n）;
Inputthe%dcoefficientsfroma0toa%d:
n,n）;
=n;
i++）scanf（"
%f"
p++）;
Inputvalueofx:
x）;
p=a;
xp=1;
sum=0;
StatusInsert（LinkList&
L,inti,intb）
voidmerge1（LinkList&
A,LinkList&
B,LinkList&
C）
voidSqList_Intersect（SqListA,SqListB,SqList&
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->
=L）
next=p->
p=p->
}同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.
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->
p&
q;
next,q=q->
next）{p->
ch=q->
ch;
pre=p;
}while（q）{p=（LStrNode*）malloc（sizeof（LStrNode））;
p->
pre->
next=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[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]）{[pc].i=x;
[pc].j=[pb].j;
[pc].e=[pb].e;
pb++;
pc++;
}else{[pc].i=x;
[pc].j=[pa].j;
[pc].e=[pa].epa++;
}}=x;
}while[pb]==x）=x;
}}pb].j）{[pc].i=x;
}}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;
PBTNode*lchild;
PBTNode*rchild;
PBTNode*parent;
}PBTNode,PBitree;
.scanf（"
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;
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;
astchild））tr->
firstchild=;
astchild->
nextsib=;
astchild=;
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->
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;
next）Print_CSTree（p->
child,i+1）;
.Print_CTree,0）;
.}算法另一个改进之处在于加入了广义表格式是否合法的判断.
voidPrintGlist_CSTree（CSTreeT）ata=c;
i=pos++;
voidPrintGList_CTree（CTreeT,inti）ata=getchar（）;
firstarc）
else
for（q=
q->
nextarc=p;
adjvex=j;
nextarc=NULL;
}dj）
[j].adj=1;
++;
returnOK;
}dj=0;
;
}StatusDelete_Arc（MGraph&
G,charv,charw）dj）
[j].adj=0;
}余算法请自行写出.
StatusInsert_Arc（ALGraph&
G,charv,charw）余算法请自行写出.
StatusDelete_Vex（OLGraph&
G,charv）余算法请自行写出.
StatusDelete_Arc（AMLGraph&
G,charv,charw）irstedge->
ivex==i）
[j].firstedge=[j].firstedge->
jlink;
for（p=[j].firstedge;
jlink->
ivex!
=i;
jlink）;
if（!
p）returnERROR;
ata=getchar（）;
irstedge）[j].firstedge=p;
q=
while（q）
r=q;
if（q->
jvex==j）q=q->
elseq=q->
ilnk;
if（r->
jvex==j）r->
jlink=p;
elser->
ilink=p;
intPass_ALGraph（ALGraphG）irstarc;
nextarc）
y=p->
adjvex;
for（q=[y].firstarc;
q=q->
z=q->
if（z!
=x&
!
is_adj（G,x,z））return0;
}irstarc;
if（p->
adjvex==n）return1;
return0;
}于是强连通图,所以从第一个结点出发一定能够访问到所有结点.
见书后解答.
StatusTopoNo（ALGraphG）
intvisited[MAXSIZE];
intexist_path_len（ALGraphG,inti,intj,intk）.
Find_All_Path（G,u,v,0）;
.
w=p->
if（!
visited[w]）DFS（G,w,k+1）;
else此一旦遍历中发现当前结点visited为真,即表示发现了一条回路
}结点序列（例如,142857）存入thiscycle中;
由于这种算法中,一条回路会被发现好几次,所以必须先判断该回路是否已经在cycles中被记录过,如果没有才能存入cycles的一个行向量中.把cycles的每一个行向量取出来与之比较.由于一条回路可能有多种存储顺序,比如142857等同于285714和571428,所以还要调整行向量的次序,并存入temp数组,例如,thiscycle为142857第一个结点为1,cycles的当前向量为857142,则找到后者中的1,把1后部分提到1前部分前面,最终在temp中得到142857,与thiscycle比较,发现相同,因此142857和857142是同一条回路,不予存储.这个算法太复杂,很难保证细节的准确性,大家理解思路便可.希望有人给出更加简捷的算法.
intfinished[MAXSIZE];
intcount;
irstout;
tlink）
headvex;
visited[w]）DFS1（G,w）;
}irstin;
hlink）
tailvex;
visited[w]）DFS2（G,w）;
voidForest_Prim（ALGraphG,intk,CSTree&
T）irstarc;
adjvex==k）closedge[j].lowcost=p->
cost;
}owcost=0;
for（i=1;
k=minimum（closedge）;
if（closedge[k].lowcost<
Max_int）
Addto_Forest（T,closedge[k].adjvex,k）;
owcost=0;
for（p=[k].firstarc;
cost<
closedge[p->
adjvex].lowcost）
adjvex]={k,p->
cost};
}.
T=（CSTNode*）malloc（sizeof（CSTNode））;
typedefstruct{
intvex;
cno）return1;
elsereturn0;
}cno）;
这个结构上实现了初始化,判断元素是否等价（两个结点是否属于同一个连通分量）,合并等价类（连通分量）的操作.
StatusTopoSeq（ALGraphG,intnew[]）irstarc;
visited[w]）DFS（G,w）;
}PL==0）k=Get_MPL（G,j）;
if（k>
max）max=k;
irstarc;
D[p->
adjvex]=*p->
info;
final[w]&
（min+（*p->
info）<
D[w]））于在原算法中,每次循环都是对尾相同的边进行处理,所以可以用遍历邻接表中的一条链来代替.
char*start;
intsize;
}fmblock;
InitStack（S）;
InitStack（T）;
voidFree_BS（freelist&
avail,char*addr,intn）tadr=q;
[j].length=s;
ey=key;
if（i>
||returnERROR;
returni;
intSearch_Bin_Recursive（SSTableST,intkey,intlow,inthigh）ey==key）returnmid;
elseif[mid].key>
key）
returnSearch_Bin_Recursive（ST,key,low,mid-1）;
elsereturnSearch_Bin_Recursive（ST,key,mid+1,high）;
}ey）return;
low=1;
high=;
while（low<
=high）
mid=（low+high）/2;
if（key>
=r[mid].key&
key<
r[mid+1].key）ey）high=mid;
elselow=mid;
}axkey）returnERROR;
axkey&
key>
[mid-1].maxkey）
found=1;
elseif（key>
[mid].maxkey）
low=mid+1;
elsehigh=mid-1;
i=[mid].firstloc;
LNode*h;
微积分可得,在等概率情况下,平均查找长度约为n/3.
DLNode*pre;
intdata;
DLNode*next;
}DLNode;
DLNode*sp;
intlength;
}DSList;
intlast=0,flag=1;
intIs_BSTree（BitreeT）果试图在删除x结点的同时修改线索,则问题反而复杂化了.
voidBSTree_Merge（BiTree&
T,BiTree&
S）合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.
voidBSTree_Split（BiTree&
A,BiTree&
B,intx）种情况,树中没有待插入关键字的同义词,此时只要新建一个叶子结点并连到分支结点上即可.另一种情况,有同义词,此时要把同义词的叶子结点与树断开,在断开的部位新建一个下一层的分支结点,再把同义词和新关键字的叶子结点连到新分支结点的下一层.
StatusTrieTree_Delete_Key（TrieTree&
T,StringTypekey）ey;
j=（j+1）%hashsize[sizeindex]）ey）==i）printf（"
%s\n"
[j]）;
}{
if（m<
1）returnERROR;
T=malloc（m*sizeof（WORD））;
算法不考虑排序问题.
}ey&
EQ[h].key,key））
h=（h+1）%20000;
if（EQ[h].key,key））k=h;
elsek=NULL;
}矩阵的元素是随机分布时,查找的时间复杂度为O
（1）.精心搜集整理，只为你的需要
升级会员 