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

《数据结构-算法与数据结构复习.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与数据结构复习习题3.3：如果对循环队列采用设置运算标志的方式来区分队列的满和空的状态，试给出对应的各运算实现。在队列的类定义里加入一个标志位tag。queue::queue(){count=0;front=rear=0;tag=0;}boolqueue::empty()const{if(front==rear&&tag==0)returntrue;elsereturnfalse;}boolqueue::full()const{if(front==rear&&tag==1)returntrue;elsereturnfalse;}error_codequeue::append(

2、constelementtypex){if(full())returnoverflow;rear=(rear+1)%maxlen;data[rear]=x;count++;tag=1;returnsuccess;}error_codequeue::serve(){if(empty())returnunderflow;front=(front+1)%maxlen;count--;tag=0;returnsuccess;}习题4.2：如果采用带尾指针的单循环链表作为队列的存储结构，设计算法以实现队列的各运算。q1q2qn...队头元素队尾元素rearqueue::queue(){re

3、ar=newnode;rear->next=rear;count=0;}boolstack::empty()const{returnrear->next==rear;}error_codequeue::get_front(elementtype&x)const{if(empty())returnunderflow;x=rear->next->next->data;returnsuccess;}error_codequeue::append(constelementtypex){node*s=newnode;s->data=x;s->next=rear->next;rear->ne

4、xt=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：递增有序顺序表A、B分别表示一个集合，设计算法求解A=A-B，并分析其时间性能。data[ia]

5、[ia]>data[ib]:A当前元素可能在B中，ib++data[ia]=data[ib]:删除A当前元素，ib++；voidsubtraction(list&A,listB){intia,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(

6、A

7、+

8、B

9、)习题2：假设递增有序顺序表A、B分别表示一个集合，设计

10、算法求解C=A∩B，并分析其时间性能。data[ia]data[ib]:A当前元素可能在B中，ib++data[ia]=data[ib]:将该元素插入C表中ia++,ib++,ic++voidintersection(listA,listB,list&C){intia,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+

11、+;else{C.insert(ic,x);ia++;ib++;ic++;}}}时间性能：O(

12、A

13、+

14、B

15、)习题5-4：假设顺序表L中的元素按从小到大的次序排列，设计算法以删除表中的重复的元素，并要求时间尽可能少。对顺序表(1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9)模拟执行本算法，统计移动元素的次数。voidDeleteRepeat(list&L){inti,j,x,y;if(L.length()==0

16、

17、L.length()==1){cout<<