算法與數(shù)據(jù)結構復習,1,習題3.3：如果對循環(huán)隊列采用設置運算標志的方式來區(qū)分隊列的滿和空的狀態(tài)，試給出對應的各運算實現(xiàn)。,在隊列的類定義里加入一個標志位tag。queue:queue()count=0;front=rear=0;tag=0;boolqueue:empty()constif(front=rear,2,error_codequeue:append(constelementtypex)if(full()returnoverflow;rear=(rear+1)%maxlen;datarear=x;count+;tag=1;returnsuccess;error_codequeue:serve()if(empty()returnunderflow;front=(front+1)%maxlen;count-;tag=0;returnsuccess;,3,習題4.2：如果采用帶尾指針的單循環(huán)鏈表作為隊列的存儲結構，設計算法以實現(xiàn)隊列的各運算。,隊頭元素,隊尾元素,rear,queue:queue()rear=newnode;rear-next=rear;count=0;boolstack:empty()constreturnrear-next=rear;error_codequeue:get_front(elementtype,4,error_codequeue:append(constelementtypex)node*s=newnode;s-data=x;s-next=rear-next;rear-next=s;rear=s;count+;returnsuccess;error_codequeue:serve()if(empty()returnunderflow;node*front=rear-next;node*u=front-next;front-next=u-next;deleteu;count-;if(front-next=NULL)rear=front;returnsuccess;,5,習題5.5：遞增有序順序表A、B分別表示一個集合，設計算法求解A=A-B，并分析其時間性能。dataiadataib:A當前元素可能在B中，ib+dataia=dataib:刪除A當前元素，ib+；,voidsubtraction(list,時間性能：O(|A|+|B|),6,習題2：假設遞增有序順序表A、B分別表示一個集合，設計算法求解C=AB，并分析其時間性能。dataiadataib:A當前元素可能在B中，ib+dataia=dataib:將該元素插入C表中ia+,ib+,ic+,voidintersection(listA,listB,list,時間性能：O(|A|+|B|),7,習題5-4：假設順序表L中的元素按從小到大的次序排列，設計算法以刪除表中的重復的元素，并要求時間盡可能少。對順序表(1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9)模擬執(zhí)行本算法，統(tǒng)計移動元素的次數(shù)。,voidDeleteRepeat(list,8,鏈表練習1：A表分成奇、偶兩個子表A、B（A表做刪除，B表做插入）,voidsplit(list/否則p,q后移,9,鏈表練習2：遞增有序鏈表集合求交、并、差子集，考慮時間復雜度。,（1）C=ABpa-datadata:將A中當前元素插入C表中,pa=pa-nextpa-data=pb-data:將A或B中的當前元素插入C表中,pa=pa-next,pb=pb-nextpa-datapb-data：將B中當前元素插入C表中,pb=pb-next如果pa!=NULL,將A中剩余結點接到C表中，如果pb!=NULL，將B中剩余結點接到C表中。,10,voidmerge_list(list,11,（2）C=A-Bpa-datadata:A當前元素不在B中，將A中當前元素插入C表中，pa=pa-nextpa-datadata：A當前元素可能在B中，pb=pb-nextpa-data=pb-data:B當前元素在A中，pa=pa-next,pb=pb-next如果pa!=NULL,將A中剩余結點接到C表中。,voidsubtraction(list,12,習題6.6（2）：將遞歸程序轉換為等價的非遞歸程序voidP