您好,欢迎访问三七文档
当前位置:首页 > 财经/贸易 > 资产评估/会计 > 《数据结构》第三四章习题C语言版
3.6证明:ijk,表明pi最先出栈,pj次之,pk最后出栈。分情况:1.若pipj,在pj出栈时,若pk还在栈中,则pkpj,可能的关系pipkpj或pkpipj;pk不在栈中,则pipjpk;2.若pipj,pk还在栈中,则pkpj,即pkpjpipk不在栈中,则pjpipk由此,输出序列中不可能出现当ijk时,pipkpj3.9Voiddigui(intj){if(j1){printf(j);digui(j-1);}}3.11简述队列和栈两种数据类型的相同点和差异点•相同点:都是操作受限的线性表•差异:1.队列只能在头部删除、尾部插入而栈只能在称为栈顶的一端插入、删除。2.队列是先进先出表,栈是后进先出表。3.15typedefintElemType;typedefstruct{inttop[2];ElemTypev[m0];}DuStack;Inistack(DuStack&tws){tws.top[0]=0;tws.top[1]=m0-1;v=(ElemType*)malloc(m0*sizeof(ElemType));}voidpush(DuStack*tws,inti,ElemTypex){if(tws-top[0]+1=tws-top[1]){printf(“overflow”);return;}switch(i){case0:tws-v[tws-top[0]]=x;tws-top[0]++;break;case1:tws-v[tws-top[1]]=x;tws-top[1]--;break;}}ElemTypepop(Dustack*tws,inti){switch(i){case0:if(tws-top[0]==0){printf(“underflow”);return;}tws-top[0]--;x=tws-v[tws-top[0]];break;case1:if(tws-top[1]==m0-1){printf(“underflow”);return;}tws-top[1]++;x=tws-v[tws-top[1]];break;}return(x);}3.17StatusMatching(){//设读入的字符序列以@结尾,本算法判该字符串是否以&为中心对称InitStack(s1);InitStack(s2);scanf(&ch);while(ch!='@')//读入以@为结尾的字符序列{Push(s1,ch);scanf(&ch);//@不是栈中字符序列的一部分}x=GetTop(s1);//取s1栈顶元素,注意GetTop与pop区别WHILE(x!='&')//将字符串'&'后的一串放入栈S2{push(s2,x);Pop(s1,x)//'&'弹出栈S1,但不进入S2}eq=true;//判s1,s2中对应字符相等否while(!StackEmpty(s1)&&!StackEmpty(s2)&&eq){pop(s1,x1);pop(s2,x2);if(x1!=x2)//有不配字符eq=false;}IF(StackEmpty(s1)&&StackEmpty(s2)&&eq)returnTRUE;//匹配elsereturnFALSE;//不匹配}3.29typedefstruct{elemtypeelems[m];intrear,front//取值在0到m-1之间inttag;//0为空,1为非空}cyclicqueue//设头、尾指针和标志域的循环队列StatusInitQueue(cyclicqueue&cq);//初始化{cq.tag:=0;cq.rear=cq.front=0;returnOK;}StatusEnQueue(cyclicqueue&cq,elemtypex){//cq是由头尾指针和标志域的循环队列,本算法是入队操作,若队列不满,//则将x插入到队尾If((cq.tag=1)&&(cq.front=cq.rear))return(false);//队满else{cq.rear=(cq.rear+1)%m;cq.elems(cq.rear)=x;if(cq.tag=0)cq.tag=1;//由空变不空标记}}StatusDelQueue(cyclicqueue&cq,elemtype&x){//cq是由头尾指针和标志域的循环队列,本算法是出队操作,若队列非空//则将队头元素出队If(cq.tag=0)return(FALSE)//队空不能删除else{cq.front=(cq.front+1)%m;IF(cq.front=cq.rear)cq.tag=0//经删除后队列变成空队}}讨论:当m较小时,设标记可用足m个单元,但每次操作要判tag,多用了时间,若m较大,不在乎一个单元,应使用牺牲一个单元办法,使操作加快(不再判断tag).}3.30definemaxlenm;{队列长度}typedefstruct{elemtypeelems[m];intrear,length//rear取值在0到m-1之间,length取值在0到m之间}cyclicqueue//设头、尾指针和标志域的循环队列StatusInit_queue(cyclicqueue&q){//初始化q.rear=0;q.length=0;returnOK;}Statusadd_queue(cyclicqueue&q,elemtypex){//q是由尾指针和长度标志的循环队列,本算法是入队操作,若队列不满,//将x插入到队尾If(q.length=m)returnFALSE;//队列满else{q.rear=(q.rear+1)%m;q.elem[q.rear]=x;q.length++;returnOK;//入队成功}}de_queue(cyclicqueue&q,elemtypex){//q是由尾指针和长度标志的循环队列,本算法是出队操作,若队列不空,//将将队头元素出列,并赋给x,队长度减1if(q.length=0)returnFALSE;//队空else{front=(q.rear-q.length+1+m)%m;x=q.elem[front];q.length--;}};3.31Voidjudge(){QueueQ;StackS;while((c=getchar())!=‘@’){EnQueue(Q,c);push(S,c);}Mark=TRUE;while(!QueueEmpty(Q)&&mark){DeQueue(Q,c);pop(S,d);if(c!=d)mark=FALSE;}if(mark)printf(‘itisapalindrome’);elseprintf(“itisn’tapalindrome”);}4.5K=substring(S,3,1);//’Y’P=substring(s,6,1);//’+’Replace(s,k,p);’(X+Z)+*’Concat(s,k);’(X+Z)+*Y’Replace(s,substring(s,6,1),’’)//’(X+Z)*Y’即所要求的结果4.16intstrcompare(HStringS,HStringT){inti,minlen;if(S.lengthT.length)minlen=S.length;elseminlen=T.length;i=0;while(iminlen){ifS.ch[i]T.ch[i])return(-1);elseif(S.ch[i]T.ch[i])return(1);elsei++;}If(S.length==T.length)return(0);elseif(S.lengthT.length)return(-1);elsereturn(1);}5.19TypedefelemtypeArray2[m][n];saddlepoint(Array2a){//a是m行n列的二维数组,本算法求所有马鞍点//b是一维数组,存放一行中可能的马鞍点的列值,k记相等值个数//c是一维数组,存放某列可能马鞍点的行值,kk记相等值个数Elemtypeb[n];Elemtypec[m];for(i=1;i=m;i++){min=a[i,1];//最小值初始化b[1]=1;k=1;for(j=2;jn;j++)//找每一行中的最小值if(a[i,j]min){b[1]=j;min=a[i,j];k=1;}//重新确定最小值elseif(a[i,j]==min){b[k+1]=j;k=k+1;}//有相等的最小值for(jj=1;jj=k;jj++)//第i行有k个相等的最小值{j=b[jj];max=a[1,j];kk=1;c[1]=I;//a[i,j]是否是马鞍点for(ii=2;ii=m;ii++)//找第j列的最大值if(a[ii,j]max){c[1]=ii;max=a[ii,j];kk=1;}//重新确定最大值elseif(a[ii,j]==max){c[kk+1]=ii;kk++;}//有相等的最大值if(max==min)//有可能是马鞍点for(ii=1;ii=kk;ii++)kk个相等的最大值哪个是马鞍点if(c[ii]==i)printf(‘马鞍点’,i,j,a[i,j]);]//endoffor(jj=1;jj=k;jj++)}//endoffor(i=1;i=m;i++)}//endofsaddlepoint()解法2:若矩阵中元素值互不相同,则第i行只一个最小值,记下列号j;然后在第j列查最大值,记下其行号ii,若i=ii,则a[i,j]是马鞍点.改进:在第j列求最大值时,可用WHILE循环,一但某值大于最小值min时,即可退出循环,该点不是马鞍点.程序段如下:FOR(jj=1;jj=k;jj++)//第I行有k个相等的最小值{j=b[jj];ii=1;flag=true;kk=0;c[1]=i;//a[ii,j]是否是马鞍点while((ii=m)&&flag)//找第j列的最大值if(a[ii,j]min)flag=falseelseif(a[ii,j]==min){c[kk+1]=ii;kk=kk+1}//有相等的最大值IF(kk!=0)//有可能有马鞍点for(ii=1;ii=kk;ii++)//kk个相等的最大值哪个是马鞍点if(c[ii]==i)printf(‘马鞍点’,i,j,a[i,j]);]{endofFOR(jj=1;jj=k;jj++)解法3:先将矩阵每行的最小值存入row一维数组,将每列的最大值存入col一维数组,再进行两层循环,若a[i,j]=row[i]=col[j],则a[i,j]为马鞍点.for(i=1;i=m;i++)for(j=1;j=n;j++)if(a[i,j]==row[i]&&a[i,j]==col[j])printf(‘马鞍点’,i,j,a[i,j]);//时间复杂度O(3*(m*n)),当马鞍点很多时适宜
本文标题:《数据结构》第三四章习题C语言版
链接地址:https://www.777doc.com/doc-2838843 .html