数据结构算法与数据结构复习市公开课一等奖省赛课微课金奖课件.pptx

算法与数据结构复习第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;第2页 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 success;第3页n 习题习题4.24.2：假如采取带尾指针单循环链表作为队列存放结构，设计算法以实现队列各运算。q1q2qn.队头元素队尾元素rearqueue:queue()rear=new noderear-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;第4页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 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)rear=front;return success;第5页习题习题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.length()A.get_element(ia,x);B.get_element(ib,y);if(xy)ib+;else A.delete_element(ia);ib+;时间性能时间性能：O(|A|+|B|)第6页习题习题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,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|)第7页习题习题5-45-4：假设次序表L中元素按从小到大次序排列，设计算法以删除表中重复元素，并要求时间尽可能少。对次序表(1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9)模拟执行本算法，统计移动元素次数。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+;第8页链表练习链表练习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=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后移第9页链表练习链表练习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 假如pa!=NULL,将A中剩下结点接到C表中，假如pb!=NULL，将B中剩下结点接到C表中。第10页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=pas-next=u;s=u;pa=pa-next;pb=pb-next;if(pa!=NULL)s-next=pa;if(pb!=NULL)s-next=pb;第11页（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*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;第12页习题习题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;第13页