数据结构习题集答案c版清华大学严蔚敏.docx
- 文档编号:5429867
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:12
- 大小:19.73KB
数据结构习题集答案c版清华大学严蔚敏.docx
《数据结构习题集答案c版清华大学严蔚敏.docx》由会员分享,可在线阅读,更多相关《数据结构习题集答案c版清华大学严蔚敏.docx(12页珍藏版)》请在冰点文库上搜索。
数据结构习题集答案c版清华大学严蔚敏
voidprint_descending(intx,inty,intz)果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m).
typedefstruct{
char*sport;
enum{male,female}gender;
charschoolname;otalscore+=;
if==0)score[0].malescore+=;
elsescore[0].femalescore+=;
break;
case'B':
+=;
if==0)+=;
else+=;
break;
………………
}
i++;
}
for(i=0;i<5;i++)
{
printf("School%d:
\n",i);
printf("Totalscoreofmale:
%d\n",;
printf("Totalscoreoffemale:
%d\n",;
printf("Totalscoreofall:
%d\n\n",;
}
}
voidpolyvalue()
{
floatad;
float*p=a;
printf("Inputnumberofterms:
");
scanf("%d",&n);
printf("Inputthe%dcoefficientsfroma0toa%d:
\n",n,n);
for(i=0;i<=n;i++)scanf("%f",p++);
printf("Inputvalueofx:
");
scanf("%f",&x);
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[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++;pc++;}}=x;[pc].j=[pa].j;[pc].e=[pa].epa++;pc++;}while[pb]==x)=x;[pc].j=[pb].j;[pc].e=[pb].e;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].epa++;pc++;}}=x;[pc].j=[pa].j;[pc].e=[pa].epa++;pc++;}while[pb]==x)=x;[pc].j=[pb].j;[pc].e=[pb].e;pb++;pc++;}}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;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->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++;
voidPrintGList_CTree(CTreeT,inti)ata=getchar();firstarc)
else
{
for(q=
q->nextarc=p;
}
p->adjvex=j;p->nextarc=NULL;
}dj)
{
[j].adj=1;
++;
}
returnOK;
}dj=0;
;
returnOK;
}StatusDelete_Arc(MGraph&G,charv,charw)dj)
{
[j].adj=0;
;
}
returnOK;
}余算法请自行写出.
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;
else
{
for(p=[j].firstedge;p&&p->jlink->ivex!
=i;p=p->jlink);
if(!
p)returnERROR;ata=getchar();irstedge)[j].firstedge=p;
else
{
q=
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->adjvex;
for(q=[y].firstarc;q;q=q->nextarc)
{
z=q->adjvex;
if(z!
=x&&!
is_adj(G,x,z))return0;
}irstarc;p;p=p->nextarc)
if(p->adjvex==n)return1;
return0;
}于是强连通图,所以从第一个结点出发一定能够访问到所有结点.
见书后解答.
StatusTopoNo(ALGraphG)
intvisited[MAXSIZE];
intexist_path_len(ALGraphG,inti,intj,intk).
Find_All_Path(G,u,v,0);.
}irstarc;p;p=p->nextarc)
{
w=p->adjvex;
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是同一条回路,不予存储.这个算法太复杂,很难保证细节的准确性,大家理解思路便可.希望有人给出更加简捷的算法.
intvisited[MAXSIZE];
intfinished[MAXSIZE];
intcount;irstout;p;p=p->tlink)
{
w=p->headvex;
if(!
visited[w])DFS1(G,w);
}irstin;p;p=p->hlink)
{
w=p->tailvex;
if(!
visited[w])DFS2(G,w);
}
voidForest_Prim(ALGraphG,intk,CSTree&T)irstarc;p;p=p->nextarc)
if(p->adjvex==k)closedge[j].lowcost=p->cost;
}owcost=0;
for(i=1;i<;i++)
{
k=minimum(closedge);
if(closedge[k].lowcost { Addto_Forest(T,closedge[k].adjvex,k);owcost=0; for(p=[k].firstarc;p;p=p->nextarc) if(p->cost closedge[p->adjvex]={k,p->cost}; }. T=(CSTNode*)malloc(sizeof(CSTNode));. } typedefstruct{ intvex;cno)return1; elsereturn0; }cno);这个结构上实现了初始化,判断元素是否等价(两个结点是否属于同一个连通分量),合并等价类(连通分量)的操作. StatusTopoSeq(ALGraphG,intnew[])irstarc;p;p=p->nextarc) { w=p->adjvex; if(! visited[w])DFS(G,w); } }PL==0)k=Get_MPL(G,j); if(k>max)max=k;irstarc;p;p=p->nextarc) D[p->adjvex]=*p->info;irstarc;p;p=p->nextarc) { w=p->adjvex; if(! final[w]&&(min+(*p->info) typedefstruct{ char*start; intsize; }fmblock;. InitStack(S);InitStack(T);. } voidFree_BS(freelist&avail,char*addr,intn)tadr=q; [j].length=s;ey=key; for(i=1; 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 elselow=mid; }axkey)returnERROR;axkey&&key>[mid-1].maxkey) found=1; elseif(key>[mid].maxkey) low=mid+1; elsehigh=mid-1; } i=[mid].firstloc; typedefstruct{ LNode*h;微积分可得,在等概率情况下,平均查找长度约为n/3. typedefstruct{ DLNode*pre; intdata; DLNode*next; }DLNode; typedefstruct{ DLNode*sp; intlength; }DSList; intlast=0,flag=1; intIs_BSTree(BitreeT)果试图在删除x结点的同时修改线索,则问题反而复杂化了. voidBSTree_Merge(BiTree&T,BiTree&S)合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱. voidBSTree_Split(BiTree&T,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).精心搜集整理,只为你的需要
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 习题集 答案 清华大学 严蔚敏