算法與數(shù)據(jù)結(jié)構(gòu)復習n 習題習題3.33.3：如果對循環(huán)隊列采用設置運算標志的方式來區(qū)分隊列的滿和空的狀態(tài)，試給出對應的各運算實現(xiàn)。在隊列的類定義里加入一個標志位tag。queue:queue( ) count = 0; front = rear = 0; tag=0; bool queue:empty( ) const if ( front=rear&tag=0) return true; else return false;bool queue:full( )const if ( front=rear&tag=1) return true; else return false; error_code queue:append(const elementtype x) if ( full() ) return overflow; rear = ( rear + 1 ) % maxlen ; datarear = x; count +; tag=1; return success;error_code queue:serve() if ( empty() ) return underflow; front = ( front + 1 ) % maxlen; count -; tag=0; return success;n 習題習題4.24.2：如果采用帶尾指針的單循環(huán)鏈表作為隊列的存儲結(jié)構(gòu)，設計算法以實現(xiàn)隊列的各運算。q1q2qn .隊頭元素隊尾元素rearqueue:queue( ) rear = new node; rear - next = rear; count = 0; bool stack:empty( ) const return rear-next=rear; error_code queue:get_front(elementtype &x) const if ( empty() ) return underflow; x = rear - next-next - data; return success; error_code queue:append(const elementtype x ) node* s = new node; s - data = x; s-next=rear-next; rear - next = s; rear = s; count +; return success;error_code queue:serve() if ( empty() ) return underflow; node* front = rear - next; node * u=front-next; front- next = u - next; delete u; count -; if ( front - next = NULL ) rear = front; return success;習題習題5.55.5：遞增有序順序表A、B分別表示一個集合，設計算法求解A=A-B，并分析其時間性能。 dataiadataib: A當前元素可能在B中，ib+ dataia=dataib: 刪除A當前元素， ib+；void subtraction(list &A, list B)int ia,ib,x,y;ia=ib=1;while(ia=A.length()&ib=B.length()A.get_element(ia,x); B.get_element(ib,y);if(xy) ib+;else A.delete_element(ia); ib+;時間性能時間性能：O(|A|+|B|)O(|A|+|B|)習題習題2 2：假設遞增有序順序表A、B分別表示一個集合，設計算法求解C=AB，并分析其時間性能。 dataiadataib: A當前元素可能在B中，ib+ dataia=dataib: 將該元素插入C表中 ia+,ib+,ic+void intersection(list A, list B, list &C)int ia,ib,ic,x,y;ia=ib=ic=1;while(ia=A.length()&ib=B.length()A.get_element(ia,x); B.get_element(ib,y);if(xy) ib+;else C.insert(ic,x); ia+;ib+; ic+;時間性能時間性能：O(|A|+|B|)O(|A|+|B|)習題習題5-45-4：假設順序表L中的元素按從小到大的次序排列，設計算法以刪除表中的重復的元素，并要求時間盡可能少。對順序表(1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9) 模擬執(zhí)行本算法，統(tǒng)計移動元素的次數(shù)。void DeleteRepeat(list &L) int i,j,x,y;if(L.length()=0|L.length()=1)cout不需刪除; return;i=1;while(ii;j-) L.get_element(j, y); if(x=y) L.delete_element(j); i+;鏈表練習鏈表練習1 1： A表分成奇、偶兩個子表A、B（A表做刪除，B表做插入）void split(list& A, list& B)node *La, *Lb; node *p, *q, *u, *s;La=A.get_head(); Lb=B.get_head();q=La; p=La-next; s=Lb;while(p!=NULL) if(p-data%2=0) /偶數(shù)結(jié)點 u=p; p=p-next; q-next=p; /結(jié)點從A表刪除s-next=u; s=s-next; /插入B表 else p=p-next; q=q-next; /否則p,q后移鏈表練習鏈表練習2 2：遞增有序鏈表集合求交、并、差子集，考慮時間復雜度。（1）C=AB p pa-datadata : 將A中當前元素插入C表中, pa=pa-next pa-data=pb-data : 將A或B中的當前元素插入C表中, pa=pa-next, pb=pb-next pa-datapb-data：將B中當前元素插入C表中,pb=pb-next 如果pa!=NULL, 將A中剩余結(jié)點接到C表中， 如果pb!=NULL，將B中剩余結(jié)點接到C表中。void merge_list(list &A,list &B, list &C)node *pa,*pb,*pc; node *u,*s;pa=A.get_head()-next; pb=B.get_head()-next; pc=C.get_head();s=pc;while(pa!=NULL&pb!=NULL)if(pa-datadata) u=pa; s-next=u; s=u; pa=pa-next;else if(pa-datapb-data) u=pb; s-next=u; s=u; pb=pb-next;else u=pa; s-next=u; s=u; pa=pa-next; pb=pb-next;if(pa!=NULL) s-next=pa;if(pb!=NULL) s-next=pb;（2）C=A-B pa-datadata: A當前元素不在B中，將A中當前元素插入C表中， pa=pa-next pa-datadata： A當前元素可能在B中，pb=pb-next pa-data=pb-data: B當前元素在A中， pa=pa-next,pb=pb-next如果pa!=NULL, 將A中剩余結(jié)點接到C表中。void subtraction(list &A, list B, list &C)node *pa,*pb,*pc; node *u,*s;pa=A.get_head()-next; pb=B.get_head()-next; pc=C.get_head();s=pc;while(pa!=NULL&pb!=NULL)if(pa-datadata) u=pa; s-next=u; s=u; pa=pa-next;else if(pa-datapb-data) pb=pb-next;else pa=pa-next; pb=pb-next;if(pa!=NULL) s-next=pa;習題習題6.66.6（2 2）：將遞歸程序轉(zhuǎn)換為等價的非遞歸程序void P(int N) stack S; while(N0|!S.empty() while(N0) S.push(N); N=N-1; if(!S.empty() S.pop(N); coutN; N=N-1;