沖刺必會代碼100題

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