《數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)》由會(huì)員分享,可在線閱讀,更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)(13頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、算法與數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)n 習(xí)題習(xí)題3.33.3:如果對(duì)循環(huán)隊(duì)列采用設(shè)置運(yùn)算標(biāo)志的方式來(lái)區(qū)分隊(duì)列的滿和空的狀態(tài),試給出對(duì)應(yīng)的各運(yùn)算實(shí)現(xiàn)。在隊(duì)列的類定義里加入一個(gè)標(biāo)志位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_
2、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 習(xí)題習(xí)題4.24.2:如果采用帶尾指針的單循環(huán)鏈表作為隊(duì)列的存
3、儲(chǔ)結(jié)構(gòu),設(shè)計(jì)算法以實(shí)現(xiàn)隊(duì)列的各運(yùn)算。q1q2qn .隊(duì)頭元素隊(duì)尾元素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
4、(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
5、) rear = front; return success;習(xí)題習(xí)題5.55.5:遞增有序順序表A、B分別表示一個(gè)集合,設(shè)計(jì)算法求解A=A-B,并分析其時(shí)間性能。 dataiadataib: A當(dāng)前元素可能在B中,ib+ dataia=dataib: 刪除A當(dāng)前元素, 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_elemen
6、t(ia); ib+;時(shí)間性能時(shí)間性能:O(|A|+|B|)O(|A|+|B|)習(xí)題習(xí)題2 2:假設(shè)遞增有序順序表A、B分別表示一個(gè)集合,設(shè)計(jì)算法求解C=AB,并分析其時(shí)間性能。 dataiadataib: A當(dāng)前元素可能在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);i
7、f(xy) ib+;else C.insert(ic,x); ia+;ib+; ic+;時(shí)間性能時(shí)間性能:O(|A|+|B|)O(|A|+|B|)習(xí)題習(xí)題5-45-4:假設(shè)順序表L中的元素按從小到大的次序排列,設(shè)計(jì)算法以刪除表中的重復(fù)的元素,并要求時(shí)間盡可能少。對(duì)順序表(1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9) 模擬執(zhí)行本算法,統(tǒng)計(jì)移動(dò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_e
8、lement(j, y); if(x=y) L.delete_element(j); i+;鏈表練習(xí)鏈表練習(xí)1 1: A表分成奇、偶兩個(gè)子表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é)點(diǎn) u=p; p=p-next; q-next=p; /結(jié)點(diǎn)從A表刪除s-next=u; s=s-next; /插入B表 e
9、lse p=p-next; q=q-next; /否則p,q后移鏈表練習(xí)鏈表練習(xí)2 2:遞增有序鏈表集合求交、并、差子集,考慮時(shí)間復(fù)雜度。(1)C=AB p pa-datadata : 將A中當(dāng)前元素插入C表中, pa=pa-next pa-data=pb-data : 將A或B中的當(dāng)前元素插入C表中, pa=pa-next, pb=pb-next pa-datapb-data:將B中當(dāng)前元素插入C表中,pb=pb-next 如果pa!=NULL, 將A中剩余結(jié)點(diǎn)接到C表中, 如果pb!=NULL,將B中剩余結(jié)點(diǎn)接到C表中。void merge_list(list &A,list &B, li
10、st &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;
11、if(pb!=NULL) s-next=pb;(2)C=A-B pa-datadata: A當(dāng)前元素不在B中,將A中當(dāng)前元素插入C表中, pa=pa-next pa-datadata: A當(dāng)前元素可能在B中,pb=pb-next pa-data=pb-data: B當(dāng)前元素在A中, pa=pa-next,pb=pb-next如果pa!=NULL, 將A中剩余結(jié)點(diǎn)接到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()-nex
12、t; 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;習(xí)題習(xí)題6.66.6(2 2):將遞歸程序轉(zhuǎn)換為等價(jià)的非遞歸程序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;