沖刺必會(huì)代碼100題

PAGEPAGE4沖刺必會(huì)代碼100題順序表1、已知線性表（a1,a2,…,an）按順序結(jié)構(gòu)存儲(chǔ)且每個(gè)元素為不相等的整數(shù)。設(shè)計(jì)把所有奇數(shù)移動(dòng)到所有偶數(shù)前邊的算法（要求時(shí)間最少，輔助空間最少）。LL.data[i]L.data[j]ij為止。對(duì)應(yīng)的算法如下：voidmove(SqList&L)voidmove(SqList&L){inti=0,j=L.length-1,k;ElemTypetemp;while(i<=j){ while(L.data[i]%2==1) while(L.data[j]%2==0) if(i<j) L.data[i]=L.data[j]; L.data[j]=temp;}}//L.data[i]L.data[j]temp=L.data[i];}{//j指向一個(gè)偶數(shù)j--;//i指向一個(gè)偶數(shù)i++;本算法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。2LO(1)。LL.datai,L.data[L.length-i-1]進(jìn)行交換。對(duì)應(yīng)的算法如下:voidreverse(SqList&L){inti;ElemTypex;for(i=0;i<L.length/2;i++){ x=L.data[i]; L.data[i]L.data[L.length-i-1]; //L.data[i]L.data[L.length-i-1]交換 L.data[L.length-i-1]=x;}}3、將兩個(gè)有序表合并為一個(gè)新的有序順序表，并由函數(shù)返回結(jié)果順序表?！舅惴ㄋ枷搿渴紫?，按照順序不斷取下兩個(gè)順序表表頭較小的結(jié)點(diǎn)存入新的順序表中。然后，看看哪個(gè)表還有剩余，將剩下的部分加到新的順序表后面。boolMerge(SqListA,SqListB,SqList&C){ if(A.length+B.lengthC.length) //表長超過returnreturninti=0,j=0, while(i<A.length&&j<B.length) { //循環(huán)，兩兩比較，小者存入結(jié)果表 if(A.data[i]<=B.data[j]) C.data[k++]=A.data[i++]; else C.data[k++]=B.data[j++]; } while(i<A.length) C.data[k++]=A.data[i++]; while(j<B.length) C.data[k++]=B.data[j++]; C.length=k; returntrue;}4、從順序表中刪除具有最小值的元素（假設(shè)唯一）并由函數(shù)返回被刪除元素的值?？粘龅奈恢糜勺詈笠粋€(gè)元素填補(bǔ)?！舅惴ㄋ枷搿克阉卣麄€(gè)順序表，查找最小值元素并記在其位置，搜索結(jié)束后用最后一個(gè)元素填補(bǔ)空出的原最小值元素的位置。boolDelete_Min(SqList&L,ElemType&value){//L中最小值元素結(jié)點(diǎn)，并通過引用型參數(shù)value返回其值if(L.length==0)returnfalse;//表空，終止操作value=L.data[0];intpos=0;//假設(shè)0號(hào)元素的值最小for(inti=1;i<L.length;i++)//循環(huán)遍歷，尋找具有最小值的元素{if(L.data[i]value)//讓value記憶當(dāng)前具有最小值的元素{value=L.data[i];pos=i;}}L.data[pos]=L.data[L.length-1];//空出的位置由最后一個(gè)元素填補(bǔ)L.length--;returntrue;}5nL采用順序存儲(chǔ)結(jié)構(gòu),O(n)O(1)的算法,x的數(shù)據(jù)元素?！舅惴ㄋ枷搿縦Lx的元素個(gè)數(shù),Lk,xk位,L的長度。對(duì)應(yīng)的算法如下:voiddel_x(SqList&L,ElemTypex){intk,iintk,i0; //kLx0 while(i<L.length) { if(L.data[i]==x)k++; //kk++; //k else L.data[i-k]L.data[i]; //xk個(gè)位置 i++; }L.lengthL.lengthL.length-k; //k}i0L.data[i]L.data[k]中，k1;L.data[i]x，則跳過繼續(xù)判斷下一個(gè)元素。最后順序表k。對(duì)應(yīng)算法如下。voiddel_x(SqList&L,ElemTypex)voiddel_x(SqList&L,ElemTypex){inti;k=0;//kLx0for(i=0;i<L.length;i++)if(L.data[i]!=x){ L.data[k]=L.data[i]; k++;}L.lengthk; //k}6Lxy(x≤y)O(1)?！舅惴ㄋ枷搿拷夥ㄒ唬罕绢}是上訴題目的變形?？梢圆捎蒙显V解法一的方法，只是將L.data[i]==x{inti,k=0;for(i=0;j<L.length;i++)if(!(L.data[i]>=x&&L.data[i]<=y)){{inti,k=0;for(i=0;j<L.length;i++)if(!(L.data[i]>=x&&L.data[i]<=y)){ L.data[k]=L.data[i]; k++;}L.lengthk; //k}解法二：voiddel_xy(SqList&L,voiddel_xy(SqList&L,x,{inti=0,k=0;while(i<L.length){ if(L.data[i]>=x&&L.data[i]<=L.data[i-k]=L.data[]}else//k記錄被刪除記錄的個(gè)數(shù)k++;PAGEPAGE497、【2010年統(tǒng)考】設(shè)將n(n>1)個(gè)整數(shù)存放在一維數(shù)組R中。試著設(shè)計(jì)一個(gè)在時(shí)間復(fù)雜度和空間復(fù)雜度都盡可能高效的算法，將R中保存的序列循環(huán)左移p（0<p<n）R（x0,x1,…,xn-1）（xp,xp+1,…,xn-1,x0,x1,…,xp-1）。要求：給出算法的基本設(shè)計(jì)思想；CC++語言描述，關(guān)鍵之處給出注釋說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度?！舅惴ㄋ枷搿肯葘個(gè)數(shù)據(jù)x0,x1,…,xn-2,xn-1原地逆置，得到xn-1,xn-2,…,x,x0,然后再將n-p個(gè)數(shù)據(jù)和后p個(gè)數(shù)據(jù)分別原地逆置，得到最終結(jié)果：xp,xp+1,…,xn-1,x0,x1,…,xp-1voidReverse(intR[],intleft,intright){ 將數(shù)組原地逆置i=left,j=while(i<j){ inttmp=r[i];r[i]=r[j];;r[j]=tmpi++; //ij--; //j}}voidLeftShift(intR[],intn,intp){ //nRp個(gè)位置if(p>0&&{Reverse(r,0,n-1); //將數(shù)組全部逆置 Reverse(r,0,n-p-1); //n-p個(gè)數(shù)據(jù)逆置 Reverse(r,n-p,n-1); //p個(gè)數(shù)據(jù)逆置}}}鏈表1來兩個(gè)鏈表的存儲(chǔ)空間，不另外占用其他的存儲(chǔ)空間。表中不允許有重復(fù)的數(shù)據(jù)。voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc){ //LaLbLc//La//LaLc的頭結(jié)點(diǎn)Lc=pc=La;//pbLb的工作指針，初始化為首元結(jié)點(diǎn)pb=Lb->next;//paLa的工作指針，初始化為首元結(jié)點(diǎn)pa=La->next; while(pa&&pb)if(pa->data<if(pa->data< { //Lbpbpc的后面，pb指針后移pc->next=pc->next=pc=pc=}//if pa=pa->next;}//if elseif(pa->data>pb->data){{pc->next= //Lbpbpc的后面，pbpc->next=pc=pc= pb=pb->next;}//elseifelse{pc= pc->next=pc= pa=pa->next;q=q=pa->next;pb=pb=}}}} pc->nextpa?pa:pb; //Lc表的最好free(Lb); //free(Lb); //Lb的頭結(jié)點(diǎn)}2、將兩個(gè)非遞減的有序表合并為一個(gè)非遞增的有序表。要求結(jié)果鏈表仍然使用原來兩個(gè)鏈表的存儲(chǔ)空間，不占用另外的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)。LcLc最后。算法思想是:LaLbLc(Lc的La的表頭結(jié)點(diǎn))指向。papbLaLbLaLbLc表的表頭結(jié)點(diǎn)之后，LaLb表中的元素。當(dāng)一個(gè)表到達(dá)表尾結(jié)點(diǎn)為空時(shí),Lc表的表頭結(jié)Lb的頭結(jié)點(diǎn)。voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc){ //LaLbLcLc->next=Lc->next=//LaLc的頭結(jié)點(diǎn)Lc=pc=La；//pbLb的工作指針，初始化為首元結(jié)點(diǎn)pb=Lb->next;//paLa的工作指針，初始化為首元結(jié)點(diǎn)pa=La->next;{{//Laqpb,pb指針后移if(!pa){//q指向待摘取的元素while(pa||pb)q=pb;q=pb; pb=pb->next;}elseif(!pb) //Lbqpa,pa指針后移{q=pa;} pa=pa->next;} elseif(pa->datapb->data) //Laqpa，{pa指針后移{q=pa;q=pa;//Lb//Lbqpb，pb指針后else}移{{q=pb;pb=pb->next;}Lc->next=q;Lc->next=q;}free(Lb)}q->next=Lc->next;3ABABA鏈表中。【算法思想】A與B的交集是指同時(shí)出現(xiàn)在兩個(gè)集合中的元素，因此，此題的關(guān)鍵點(diǎn)在于:依次摘取兩個(gè)表中相等的元素重新進(jìn)行鏈接,刪除其他不等的元素。算法思想是:LaLbLc(Lc的La的表頭結(jié)點(diǎn))指向。papbLaLbLaLbLaLb表中的元素;如果其中一個(gè)表中的元素較小，刪除此表中較小的元素，此表的工LaLb有一個(gè)到達(dá)表尾結(jié)點(diǎn)為空時(shí)，依次刪除另一個(gè)非Lb的頭結(jié)點(diǎn)。voidIntersection(LinkList&La,LinkList&Lb,LinkList&Lc)//pb//pbLb的工作指針，初始化為首元結(jié)點(diǎn)pb=Lb->next;//paLa的工作指針，初始化為首元結(jié)點(diǎn)pa=La->next;{{//相等，交集并入結(jié)果表中if(pa->data==pb->data){while(pa&&//LaLc的頭結(jié)點(diǎn)Lc=pc=La; pc->next=pa;pc=pc=u=pb; pa=pa->next;u=pb; pb=pb->next;free(u);free(u);}} elseif(pa->datapb->data) //La中的元素{{ u=pa;pa=pa->next;free(u);}else //La{u=pb;pb=free(u);}}while(pa) //LbLa中的所有元素{u=pa;pa=pa->next;free(u);}while(pb) //LaLb中的所有元素{u=pb;pb=pb->next;free(u);}pc->next=NULL;free(Lb)}4ABAB（AB的集合），并且以同樣的形式存儲(chǔ)，同時(shí)返回該集合的元素個(gè)數(shù)?！舅惴ㄋ枷搿緼BAAB的數(shù)據(jù)域相等的結(jié)點(diǎn)。由于要?jiǎng)h除結(jié)點(diǎn)，此題的關(guān)鍵點(diǎn)在于:在遍歷鏈表時(shí)，需要保存待刪除結(jié)點(diǎn)的前驅(qū)。算法思想是:假設(shè)待求的鏈表為La和Lb，pa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的首元結(jié)點(diǎn)。pre為La中pa所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針，初始化為La。從首元結(jié)點(diǎn)開始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均未到達(dá)表尾結(jié)點(diǎn)時(shí)，如果La表中的元素小于Lb表中的元素，La表中的元素即為待求差集中的元素，差集元素個(gè)數(shù)增1，pre置為La表的工作指針pa,pa后移;如果Lb表中的元素小于La表中的元素,pb后移;如果La表中的元素等于Lb表中的元素，則在La表刪除該元素值對(duì)應(yīng)的結(jié)點(diǎn)。voidDifference(LinkList&La,LinkList&Lb,int&n)//pb//pbLb的工作指針，初始化為首元結(jié)點(diǎn)pa=Lb->next;//paLapa=La->next;{{//A鏈表當(dāng)前的結(jié)點(diǎn)指針后移if(pa->data<pb->data){while(pa&&//preLapa所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針pre=La;n++;n++;pre=pa;pre=pa;{//La{//LaLaLb中元素值相同的結(jié)點(diǎn)else//A鏈表當(dāng)前的結(jié)點(diǎn)指針后移pb=pb->next;elseif(pb->data>} pre->next=pa->next;u=pa;u=pa;free(u); pa=pa->next;free(u);}}}}}5、試編寫在帶頭結(jié)點(diǎn)的單鏈表L中刪除一個(gè)最小值結(jié)點(diǎn)的高效率算法（假設(shè)最小值結(jié)點(diǎn)是唯一的）。算法思想：p從頭至尾掃描單鏈表，pre指向*pminp保存值最小的結(jié)點(diǎn)指針（p）,minpre指向*minp結(jié)點(diǎn)的前驅(qū)（pre）。一p->dataminp->datap、preminprep掃描完畢，minp指向最小值結(jié)點(diǎn)，minpre指向最小minp所指結(jié)點(diǎn)刪除即可。LinkListDelete_Min(LinkList&L){ //L是帶頭結(jié)點(diǎn)的單鏈表，本算法是刪除其最小值結(jié)點(diǎn) LNode*pre=L,*ppre->next; //p為工作指針，pre指向其前驅(qū){{if(p->data<minp->data){minp=p;minpre=pre;}pre=p;p=p->next;//繼續(xù)掃描下一節(jié)點(diǎn)}free(minp);returnL;}//刪除最小值結(jié)點(diǎn)minpre->next=minp->next;while(p!=NULL)LNode*minpre=pre,*minpp; 6Lxx的結(jié)點(diǎn)不唯一，試編寫算法實(shí)現(xiàn)上述操作。算法思想：解法一p指向*ppxppre、p同步后移一個(gè)結(jié)點(diǎn)。刪除某結(jié)點(diǎn)相關(guān)題型的代碼模板if條件即可。例如，我們要求刪除結(jié)點(diǎn)值介于minkmaxk之間的所有結(jié)點(diǎn)，則只需要將if語句修改為if(p->datamink&&p->data<maxk)。voidDelete_x(LinkList&L,ElemTypex){ //LLx的結(jié)點(diǎn)while(p!= LNode*p=L->next,*preL,*q;//pprewhile(p!={{p=p->next;//q指向該結(jié)點(diǎn)q=p;{//p=p->next;//q指向該結(jié)點(diǎn)q=p;{//否則，prep同步后移else}//釋放*q結(jié)點(diǎn)的空間free(q);//刪除*q結(jié)點(diǎn)pre->next=p;{{pre=p;p=}//else}//else}//while}解法二：采用尾插法建立單鏈表。用p指針掃描L的所有結(jié)點(diǎn)，當(dāng)其值不為x時(shí)將其鏈接到L之后，否則將其釋放。voidDelet_x(Linklist&L,ElemTypex){ //LLx的結(jié)點(diǎn) LNode*p=L->next,*rL*q; //r指向尾節(jié)點(diǎn)，其初值為頭結(jié)點(diǎn)while(p!={if(p->data!=x)//*p結(jié)點(diǎn)值不為x時(shí)將其鏈接到L的尾部{}//繼續(xù)掃描p=p->next;}//繼續(xù)掃描p=p->next;r=p; else{{q=p;q=p; p=p->next;}}//whiler->nextNULL; //NULL}7、試編寫算法將帶頭結(jié)點(diǎn)的單鏈表就地逆置，所謂“就地”O(jiān)(1)。插法建立單鏈表所示。LinkListReverse(LinkListL){ //LL逆置////LnextNULLL->next=NULL;//從第一個(gè)元素結(jié)點(diǎn)開始p=L->next;//p為工作指針，rp的后繼，以防斷鏈LNode*p,*r;//p的后繼r=p->next;{////p的后繼r=p->next;{//依次將元素結(jié)點(diǎn)摘下while(p!=NULL)L->next=p=} returnL;}8AAAB表中含有原表中序號(hào)為偶數(shù)的元素，且保持其相對(duì)順序不變。LinkListDisCreat(LinkList&A){ //AAB中ii0; //iA中結(jié)點(diǎn)的序號(hào) BLinkList)malloc(sizeof(LNode));//B表表頭B->nextB->nextNULL; //B表初始化 LNode*ra=A,*rbB; //rarbAB表的尾節(jié)點(diǎn)p=p=A->next; A->nextNULL; //A表置空{(diào){//處理序號(hào)為偶數(shù)的鏈表結(jié)點(diǎn)if(i%2==0)//序號(hào)+1i++;{while(p!=rb->next=p; //在表尾插入新結(jié)rb=p; //rb指向新尾結(jié)點(diǎn)}else{ra->next=p; //處理原序號(hào)為奇數(shù)的結(jié)ra=p; //在A表尾插入新的結(jié)點(diǎn)}pp->next; //p恢復(fù)為指向新的待處理結(jié)點(diǎn)}ra->next=NULL;rb->next=return}9C={hcA1a…a}B{b…，b2，b1}。算法思想：本題的思路和上題基本一樣，不設(shè)置序號(hào)變量。二者的差別僅在于對(duì)B表的建立不采用尾插法，而是采用頭插法。LinkListDisCreat(LinkList&A){ LinkListBLinkList)malloc(sizeof(LNde));//B表表頭while(p!=while(p!=//raA的尾節(jié)點(diǎn)LNode*ra=A;//p為工作指針LNode*p=A->next,*q;//B表的初始化B->next=NULL;{{ ra->next=p;rap; //將*pA的表尾////頭插后，*pq記憶*p的后繼p->next=B->next;q=p=returnB;//AreturnB;//Anext域置空ra->next=NULL;}p=q;//*pB的前端B->next=p;10、設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表B和C，其中B表的結(jié)點(diǎn)為A表中小于零的結(jié)點(diǎn)，而C表中的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)（鏈表A中的元素為非零整數(shù)，要求B、C表利用A表的結(jié)點(diǎn)）。【算法思想】BAC申請(qǐng)一個(gè)頭結(jié)點(diǎn)，初始化為空AApp的后p->data<0p指向的結(jié)點(diǎn)適用前插法插入到Bpa->data>0pCp指向新的待插入的結(jié)點(diǎn)voidDecompose(LinkList&A,LinkList&B,LinkList&C){ //ABCB=B->next=C->next= C=C->next=p=p=A->next; while(p!=NULL){rp->next; //p的后繼if(p->data0) //0B中，前插法{B->next=p; p->next=B->next=p;}}{ else{ p->next=C->next;C->next=p;}p=r;//p指向新的待處理結(jié)點(diǎn)}}n該結(jié)點(diǎn)的數(shù)據(jù)域?！舅惴ㄋ枷搿看祟}的關(guān)鍵在于：在遍歷的時(shí)候利用指針pmax記錄值最大的結(jié)點(diǎn)的位置。算法思想：初值時(shí)候指針pmax指向首元結(jié)點(diǎn)，然后在遍歷過程中，用pmax依次和后面的結(jié)點(diǎn)進(jìn)行比較，發(fā)現(xiàn)大者則用pmax指向該結(jié)點(diǎn)。這樣將鏈表從頭到尾遍歷一遍時(shí)，pmax所指向的結(jié)點(diǎn)中的數(shù)據(jù)即為最大值。ElemTypeMax(LinkListL){//p指向第二個(gè)結(jié)點(diǎn)p=L->next->next;//p指向第二個(gè)結(jié)點(diǎn)p=L->next->next;//pmax指向首元結(jié)點(diǎn)pmax=L->next;returnif(L->next==NULL)}}//p指向下一個(gè)結(jié)點(diǎn)，繼續(xù)遍歷p=p->max;//pmax指向數(shù)值大的結(jié)點(diǎn)pmax=p;if(p->data>pmax->data){//遍歷鏈表，如果下一個(gè)結(jié)點(diǎn)存在while(p!=NULL) returnpmax->data;}12minkmaxk是給定的兩個(gè)參數(shù)，其值可以和表中的元素相同，也可以不同）的所有元素voidDelete_Min_Max(LinkList&L,intmink,intmaxk){ //Lminkmaxk的所有元素p=p= while(p&&p->datamink) //mink的結(jié)點(diǎn){pre=p;} p=p->next;} while(p&&p->datamaxk) //maxk的結(jié)點(diǎn)p=q=pre->next;pre->nextp; //修改待刪除結(jié)點(diǎn)的指針while(qp) //依次釋放待刪除結(jié)點(diǎn)的空間{ s=q->next;q=}}13、在一個(gè)遞增有序的線性表中，有數(shù)值相同的元素存在。若存儲(chǔ)方式為單鏈表，設(shè)計(jì)算法去掉數(shù)值相同的元素，使表中不再具有重復(fù)的元素?！舅惴ㄋ枷搿孔⒁獾筋}目是有序表，說明所有相同值域的結(jié)點(diǎn)都是相鄰的。用p掃描遞增單鏈表L，若*p結(jié)點(diǎn)的值域等于其后繼結(jié)點(diǎn)的值域，則刪除后者，否則p移向下一個(gè)結(jié)點(diǎn)。voidDeleteSame(LinkList&L){ //L是遞增有序的單鏈表，本算法刪除表中數(shù)值相同的元素if(p== LNode*pL->next,*q; //pif(p==returnreturn;//q指向*p的后繼結(jié)點(diǎn)//q指向*p的后繼結(jié)點(diǎn)q=p->next;{ if(p->dataq->data) //找到重復(fù)值的結(jié)點(diǎn){{ p->nextq->next; //q結(jié)點(diǎn)}}elseelse} p=p->next;}}14,3類字符的數(shù)據(jù)元素(如:字母字符﹑字符和其他字符),試編寫算法構(gòu)造3個(gè)以循環(huán)鏈表表示的線性表,同一類的字符,且利用原表中的節(jié)點(diǎn)空間作為這三個(gè)表的節(jié)點(diǎn)空間,空間。3個(gè)頭節(jié)點(diǎn),pL,將不同類型的數(shù)據(jù)元素采用頭插法插入到相應(yīng)的循環(huán)單鏈表中。對(duì)應(yīng)的算法如下:voidSplit(LinkList*L,LinkList*&A,LinkList*&B,LinkList*&C)LinkList*p=L->next,*LinkList*p=L->next,*q; A=(LinkList*)malloc(sizeof(LinkList));A->next=A->next=B->next=B->next= C=(LinkList*)malloc(sizeof(LinkList));C->next=C->next=C;{ while(p!=NULL){ if(p->data>='A'&&p->data<='Z'||p->data>='a'&&p->data<='z'){q=p;p=p->next; q->next=A->next;A->nextA->nextp; //A}elseif(p->data>='O'&&p->data<='9'){{q=p;p=p->next;q->nextA->next;A->nextp; //B}{q=p;p=p->next;q->next=C->next;C->nextp; //C}}}else15、已知帶頭節(jié)點(diǎn)的循環(huán)單鏈表L中至少有兩個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)的兩個(gè)字段為data和next,其中data值是否小于其后續(xù)兩個(gè)節(jié)點(diǎn)的值之和。若滿足,true;false。【算法思想】用p掃描整個(gè)循環(huán)單鏈表L,一旦找到這樣的節(jié)點(diǎn)*p,它使得條件p->data<p->next->data+p->next->next->data不成立,則中止循環(huán),返回0﹔否則繼續(xù)掃描。當(dāng)while循環(huán)正常結(jié)束時(shí)返回1。對(duì)應(yīng)的算法如下:booljudge(LinkList*L){boolb= LinkList*p=boolb= while(p->next->next!=L&&b){{ if(p->data>p->next->data+p->next->next->data)b=p=} returnb;}雙指針策略思想（重點(diǎn)）：一快，一慢一早，一晚一左，一右【2009年統(tǒng)考】16、已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為：linklinkdatalistk個(gè)位置上的結(jié)點(diǎn)k為正整數(shù))data域的值，并返回10。要求：描述算法的基本設(shè)計(jì)思想；描述算法的詳細(xì)實(shí)現(xiàn)步驟；根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語言描述算法（C、C++言實(shí)現(xiàn)），關(guān)鍵之處請(qǐng)給出簡要注釋?！舅惴ㄋ枷搿縫pkqpk+1qkpqpNULLk個(gè)結(jié)點(diǎn)?！舅惴ú襟E】①設(shè)定計(jì)數(shù)器i=0，用指針p和q指向首元結(jié)點(diǎn)②從首元結(jié)點(diǎn)開始依順著鏈表linkp驟⑤。③若i小于k，則i+1；否則，q指向下一個(gè)結(jié)點(diǎn)。④p指向下一個(gè)結(jié)點(diǎn)，轉(zhuǎn)步驟②。i==data0.算法如下：typedefstructLNodeintint structLNode*next;}LNode,*LinkList;intSearch_k(LinkListlist,intk){////k個(gè)位置上的結(jié)點(diǎn)inti=0;p=q=list->link;while(p!=NULL){if(i<k)i++;elseq=q->link;p=p->link;}if(i==k){cout<<q->data;return1;}else//初始化計(jì)數(shù)器//p，q均指向首元結(jié)點(diǎn)//p為空//計(jì)數(shù)器+1//q移到下一個(gè)結(jié)點(diǎn)//p移動(dòng)到下一個(gè)結(jié)點(diǎn)//data域的值}//k，查找失敗return0;17、給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。如果有環(huán)，返回1，否則返回0。給出算法的基本思想CC++下圖給出了一個(gè)有環(huán)的鏈表。typedefstructListNode{intdata;structListNode*next;}【算法思想】21一定會(huì)在環(huán)中相遇。1、判斷極端條件，如果鏈表為空，或者鏈表只有一個(gè)結(jié)點(diǎn)，一定不會(huì)帶環(huán)，直接返回NULL。2、創(chuàng)建快慢指針，都初始化指向頭結(jié)點(diǎn)。因?yàn)榭熘羔樏看味家竭M(jìn)2個(gè)單位，所以在判斷其自身有效性的同時(shí)還要判斷其next指針的有效性，在循環(huán)條件中將兩語句邏輯與并列起來。初始化慢指針slow=head，每次向后走一步；初始化快指針fastfastslow必定會(huì)相遇。inthasCycle(ListNode*head){ //判斷鏈表是否有環(huán)return0; if(head==NULL||head->next==return0; ListNode*fast=head->next;ListNode*slow=while(slow!={ if(fast==NULL||fast->nextNULL) //鏈表無環(huán)return0;slow=slow->next;} fast=fast->next->next;} return1;}棧和隊(duì)列回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個(gè)算法判斷給定字符序列是否是回文。（將一般字符入棧。）【算法思想】將字符串前一半入棧，然后，棧中元素和字符串后一半比較。即將第一個(gè)出棧元素和后一半串中第一個(gè)字符比較，若相等，則再出棧一個(gè)元素與后一個(gè)字符比較，依次類推，直至?？?，在這種情況下可判斷該字符序列是回文。如果出棧元素與串中的字符進(jìn)行比較時(shí)出現(xiàn)不等的情況，則可判斷該字符序列不是回文。【算法思想】intisPalindrome(char*t)intisPalindrome(char*t){InitStack(S);len=strlen(t);//求字符串長度for(inti=0;i<len/2;i++)//將一半字符入串Push(S,t[i]);if(len%2!=0)i++;while(!EmptyStack(S)){inttmp=Pop(S);if(tmp!=t[i])return0;elsei++}return1;//長度為奇數(shù)，跳過中間字段//每彈出一個(gè)字符與相應(yīng)字符比較//不相等返回0//比較完畢均相等返回1}假設(shè)以數(shù)組Q]agag==0tag1（DeQueue）算法。【算法思想】tagtagQtag==0，front==rear==04隊(duì)空條件：Q.front==Q.rear&&Q.tag==0隊(duì)滿條件：Q.front==Q.rear&&Q.tag==1進(jìn)隊(duì)操作：Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;Q.tag=1。出隊(duì)操作：x=Q.data[Q.front]；Q.front=(Q.front+1)%MaxSize;Q.tag=0;//設(shè)tag法的循環(huán)隊(duì)列入隊(duì)算法intEnQueue(SqQueue&Q,ElemTypex){ if(Q.front==Q.rear&&Q.tag1) //兩個(gè)條件都滿足時(shí)則隊(duì)滿return0;Q.data[Q.rear]==Q.tag= Q.rear=Q.tag= return1; }//設(shè)tag法的循環(huán)隊(duì)列出隊(duì)算法intDeQueue(SqQueue&Q,ElemType&x){ if(Q.front==Q.rear&&Q.tag==0)return0;x=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize;Q.tag=return1;}（）【算法思想】exp，遇到左括號(hào)時(shí)進(jìn)棧；遇到右括號(hào)時(shí)，若棧頂為左括號(hào)，則出棧，否則返回假。當(dāng)表達(dá)式掃描完畢且棧為空時(shí)返回真；否則返回假。算法如下：boolMatch(charexp[],intn)inti=0;charinti=0;chare; boolmatch=true;while(i<n&&while(i<n&&//初始化棧InitStack(st);LinkStNode*st;////當(dāng)前字符為左括號(hào)，將其進(jìn)棧if(exp[i]=='('){Push(st,exp[i]);Push(st,exp[i]);elseif(exp[i //當(dāng)前字符為右括號(hào){if(GetTop(st,e)==true){if(e!='(')match=false;elsePop(st,e);}//e//棧頂元素不為（時(shí)//表示不匹配//棧頂元素為）時(shí)//將棧頂元素出棧}i++//繼續(xù)處理其他字符}if(!StackEmpty(st)) false;DestroyStakck(st);returnmatch;}//無法取棧頂元素時(shí)表示不匹配elsematch=false;4、【課后變式習(xí)題】假設(shè)表達(dá)式中允許包含3種括號(hào)：圓括號(hào)、方括號(hào)和大括號(hào)。編寫一個(gè)算法判斷表達(dá)式中的括號(hào)是否正確匹配。樹和二叉樹先序遍歷過程：若二叉樹為空，什么都不做，否則①訪問根結(jié)點(diǎn)②先序遍歷左子樹③先序遍歷右子樹遞歸算法：voidPreOrder(BiTreeT){ if(T!=NULL){visit(T); //訪問根結(jié)點(diǎn)PreOrder(T->lchild); 遞歸遍歷左子樹PreOrder(T->rchild); //}}非遞歸算法：voidPreOrder(BiTreeT){InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){printf(p->data);push(S,p);p=p->lchild;}else{pop(S,p);p=}}}二叉樹的中序非遞歸遍歷中序遍歷過程：若二叉樹為空，則什么也不做；否則：①中序遍歷左子樹②訪問根結(jié)點(diǎn)③中旬遍歷右子樹遞歸算法：voidInOrder(BiTreeT){{ if(T!=NULL){ InOrder(T->lchild);visit(T);visit(T);} InOrder(T->rchild);}}非遞歸算法：voidInOrder(BiTreeT){InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){push(S,p);p=p->lchild;}else{pop(S,p);printf(p->data);p=}}}二叉樹的后序非遞歸遍歷后序遍歷過程：若二叉樹為空，什么也不做，否則，①后序遍歷左子樹②后序遍歷右子樹③后序遍歷根結(jié)點(diǎn)遞歸算法：voidPostOrder(BiTreeT){ if(T!=NULL){visit(T);}}voidPostOrder(BiTreeT){p=T;while(p||!StackEmpty(S)){if(p){push(S,p);p=p->lchild;}else{pop(S,p);if(p->rchild&&(p->rchild).tag==0){push(S,p);p=}else{printf(p->data);p.tag=1;p=}}}}注意：在二叉樹的存儲(chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)增加一個(gè)是否訪問的tag域，初始值均為0二叉樹的層序遍歷算法層次遍歷的算法過程可以概括為：?先將二叉樹根結(jié)點(diǎn)入隊(duì)，?然后出隊(duì)，訪問該出隊(duì)結(jié)點(diǎn)，?若它有左子樹，則將左子樹根結(jié)點(diǎn)入隊(duì)，?若它有右子樹，則將右子樹根結(jié)點(diǎn)入隊(duì)，?然后出隊(duì)，訪問出隊(duì)結(jié)點(diǎn)?如此反復(fù)，直到隊(duì)列為空。voidLevelOrder(BiTree){BiTreep;BiTreep;//初始化輔助隊(duì)列InitQueue(Q);EnQueue(Q,T);EnQueue(Q,T);//將根結(jié)點(diǎn)入隊(duì){//隊(duì)列循環(huán)不為空while(!IsEmpty(Q))if(p->lchild!=NULL)//pif(p->lchild!=NULL)//p所指向結(jié)點(diǎn)visit(p);//隊(duì)頭元素出隊(duì)DeQueue(Q,p);if(p->rchild!=if(p->rchild!= EnQueue(Q,p->rchild//右子樹不為空，右子樹入隊(duì)}}}注：對(duì)于二叉樹的層序遍歷的算法，大家應(yīng)該重點(diǎn)背下，當(dāng)成一個(gè)模板，應(yīng)用到下面各種題目中。關(guān)于二叉樹隊(duì)列的一個(gè)問題，EnQueue(p->lchild)Q[++rearp->lchild都EnQueue()Q[++rear]二叉樹的遞歸算法設(shè)計(jì)策略遞歸體的一般格式如下:f(ds)=g(op(ds),c)其中，f()為遞歸函數(shù)，ds為遞歸數(shù)據(jù)，op為基本遞歸運(yùn)算符，g為非遞歸函數(shù)，c為常量。對(duì)于二叉樹，一般遞歸模型如下:f(b)=c b=NULL時(shí)f(b)=g(f(b->lchild),f(b->rchild),c1) 其他情況對(duì)應(yīng)的遞歸算法如下：DataTypefun(BTNode*b){ if(b==NULL) return(c); else returng(fun(b->lchild),fun(b->rchild),c1)}DataType;試編寫二叉樹的自下而上、從右到左的層次遍歷算法。【算法思想】棧頂開始依次訪問。voidInvertLevel(BiTreebt){if(bt!= StackS;Queueif(bt!= { //初始化棧和隊(duì)列{{//從上而下層次遍歷while(IsEmpty(Q)==false)DeQueue(Q,p);DeQueue(Q,p);Push(S,p);if(p->lchild)//出隊(duì)，入棧EnQueue(Q,p->lchild);//左子樹不為空，左子樹入隊(duì)if(p->rchild)if(p->rchild)EnQueue(Q,p->rchild);//右子樹不為空，右子樹入隊(duì)}//whiile{Pop(S,p);visit(p->data); //自下而上、從右到左的層次遍歷}}//if}while(IsEmpty(s)==false)例題：設(shè)二叉樹采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)，試著編寫非遞歸算法二叉樹的最大高度（二叉樹的最大寬度是指二叉樹所有層中結(jié)點(diǎn)個(gè)數(shù)的最大值）。【算法思想】levellastlast數(shù)+1，并且計(jì)算下一層的最右結(jié)點(diǎn)，直到遍歷完成。level的值即為二叉樹的高度intBidepth(BiTreeT){ //求二叉樹的最大寬度BiTreep;BiTreep;//假設(shè)隊(duì)列的容量足夠大BiTreeQ[MaxSize];{return0;if(T==//level//level記錄當(dāng)前結(jié)點(diǎn)所在的層次，intlast=0,level=0;//初始化隊(duì)列intfront=-1,rear=-1;//last指向當(dāng)前層的最右結(jié)點(diǎn)Q[++rearT; //將根結(jié)點(diǎn)入隊(duì)while(front<{if(p->lchild) p=Q[++front];if(p->lchild) Q[++rearp->lchild; //左孩子入隊(duì) Q[++rearp->rchild; //右孩子入隊(duì)if(front==level){level++; //層數(shù)加+1lastrear; //last,指向下一層}//if}//while}//else}（的最大值）【算法思想】歷完畢之后，若局部寬度大于當(dāng)前的最大寬度，則修改最大寬度。intwidth(BiTreeT){ //求二叉樹高度if(T==return0; //{ BiTreeQ[MaxSize]; //Q是隊(duì)列，假設(shè)容量足夠大 front=rear1; //初始化隊(duì)列BiTreeBiTreep;//根結(jié)點(diǎn)入隊(duì)Q[rear]=T;//最大寬度intmaxw=0;//局部寬度inttmp=0;//同層最右結(jié)點(diǎn)在隊(duì)列中的位置intlast=1;{ while(front<=last){ p=Q[front++];if(p->lchild!=NULL) Q[++rearp->lchild; //左子樹入隊(duì)if(p->rchild!=if(p->rchild!= Q[++rearp->rchild; //右子樹入隊(duì)if(front>last){last=rear;//last指向下層最右元素if(tmp>maxw)//更新當(dāng)前最大寬度tmp=0;tmp=0;}//if}//whilereturnmaxw;}}maxw=tmp;假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，計(jì)算一棵給定二叉樹的所有節(jié)點(diǎn)數(shù)。解:計(jì)算一棵二叉樹的所有節(jié)點(diǎn)個(gè)數(shù)的遞歸模型f(b)如下。intNodes(BTNode*b){intnum1,num2;return0; ifreturn0; else { num1=Nodes(b->1child);return(numl+num2+1) num2=Nodes(b->rchild)return(numl+num2+1)