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

《数据结构算法与数据结构复习.ppt》由会员分享，可在线阅读，更多相关《数据结构算法与数据结构复习.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法与数据结构复习n 习题习题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 true;else return false;error_code queue:append(const

2、 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：如果采用带尾指针的单循环链表作为队列的存储结构，设计算法以实现队列的各运算。q1q2qn.队头元素队尾元素rearqueue:queue()rear=new node;r

3、ear-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 su

4、ccess;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

5、&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 intersecti

6、on(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)模拟执行本

7、算法，统计移动元素的次数。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

8、=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后移链表练习链表练习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 如

9、果pa!=NULL,将A中剩余结点接到C表中，如果pb!=NULL，将B中剩余结点接到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=

10、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中剩余结点接到C表中。void subtraction(list&A,list B,list&C)node*pa,*pb,*pc;node*

11、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）：将递归程序转换为等价的非递归程序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;