数据结构-算法与数据结构复习

1、2021/8/141算法与数据结构复习2021/8/142n 习题习题3.33.3：如果对循环队列采用设置运算标志的方式来区分队列的满和空的状态，试给出对应的各运算实现。在队列的类定义里加入一个标志位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 习题习题4.24.2：如果采用带尾指针的单循环链表作为队列的存储结构，设计算法以实现队列的各运算。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

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习题习题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

6、.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|)2021/8/147习题习题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,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+;时间性能时间性能：O(|A|+|B|)O(|A|+|B|)2021/8/148习题习题5-45-4：假设顺序表L中的元素按从小到大的次序排列，设计算法以删除表中的重复的元素，并要求时间尽可能少。对顺序表(1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9) 模拟执行本算法，统计移动元素的次数。

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链表练习链表练习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=

9、B.get_head();q=La; p=La-next; s=Lb;while(p!=NULL) if(p-data%2=0) /偶数结点 u=p; p=p-next; q-next=p; /结点从A表删除s-next=u; s=s-next; /插入B表 else p=p-next; q=q-next; /否则p,q后移2021/8/1410链表练习链表练习2 2：递增有序链表集合求交、并、差子集，考虑时间复杂度。（1）C=AB p pa-datadata : 将A中当前元素插入C表中, pa=pa-next pa-data=pb-data : 将A或B中的当前元素插入C表中, pa=pa

10、-next, pb=pb-next pa-datapb-data：将B中当前元素插入C表中,pb=pb-next 如果pa!=NULL, 将A中剩余结点接到C表中， 如果pb!=NULL，将B中剩余结点接到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当前元素不在B中，将A中当前元素插入C表中， pa=pa-next pa-datadata： A当前元素可能在B中，pb=pb-next pa-da

12、ta=pb-data: B当前元素在A中， pa=pa-next,pb=pb-next如果pa!=NULL, 将A中剩余结点接到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