數(shù)據(jù)結(jié)構(gòu)-算法與數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)

1、2021/8/141算法與數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)2021/8/142n 習(xí)題習(xí)題3.33.3：如果對(duì)循環(huán)隊(duì)列采用設(shè)置運(yùn)算標(biāo)志的方式來(lái)區(qū)分隊(duì)列的滿(mǎn)和空的狀態(tài)，試給出對(duì)應(yīng)的各運(yùn)算實(shí)現(xiàn)。在隊(duì)列的類(lèi)定義里加入一個(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 tru

2、e; else return false; 2021/8/143 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 su

3、ccess;2021/8/144n 習(xí)題習(xí)題4.24.2：如果采用帶尾指針的單循環(huán)鏈表作為隊(duì)列的存儲(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

4、-next - data; return success; 2021/8/145error_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

5、- next = u - next; delete u; count -; if ( front - next = NULL ) rear = front; return success;2021/8/146習(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

6、.length()A.get_element(ia,x); B.get_element(ib,y);if(xy) ib+;else A.delete_element(ia); ib+;時(shí)間性能時(shí)間性能：O(|A|+|B|)O(|A|+|B|)2021/8/147習(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,i

7、b,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+;時(shí)間性能時(shí)間性能：O(|A|+|B|)O(|A|+|B|)2021/8/148習(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ù)。

8、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+;2021/8/149鏈表練習(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=

9、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表 else p=p-next; q=q-next; /否則p,q后移2021/8/1410鏈表練習(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

10、-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表中。2021/8/1411void 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-d

11、atadata) 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;2021/8/1412（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-da

12、ta=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()-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!=NUL