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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,算法与数据结构复习,1,习题,3.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,习题,4.2,：如果采用带尾指针的单循环链表作为队列的存储结构，设计算法以实现队列的各运算。,q,1,q,2,q,n,.,队头元素,队尾元素,rear,queue: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-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.5,：递增有序顺序表,A,、,B,分别表示一个集合，设计算法,求解,A=A-B,，并分析其时间性能。,dataia,dataib,: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,：假设递增有序顺序表,A,、,B,分别表示一个集合，设计,算法求解,C=A,B,，并分析其时间性能。,dataia,dataib,: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-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,：,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,：递增有序链表集合求交、并、差子集，考虑时间复,杂度。,（,1,）,C=A,B,p,a-datadata:,将,A,中当前元素插入,C,表中,pa=,pa,-next,pa-data=,pb,-data,:,将,A,或,B,中的当前元素插入,C,表中,pa=,pa,-next,pb,=,pb,-next,pa-data,pb,-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=pa;s-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.6,（,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,