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

算法与数据结构复习,习题3.3：如果对循环队列采用设置运算标志的方式来区分队列的满和空的状态，试给出对应的各运算实现。,在队列的类定义里加入一个标志位tag。queue:queue()count=0;front=rear=0;tag=0;boolqueue:empty()constif(front=rear,error_codequeue:append(constelementtypex)if(full()returnoverflow;rear=(rear+1)%maxlen;datarear=x;count+;tag=1;returnsuccess;error_codequeue:serve()if(empty()returnunderflow;front=(front+1)%maxlen;count-;tag=0;returnsuccess;,习题4.2：如果采用带尾指针的单循环链表作为队列的存储结构，设计算法以实现队列的各运算。,队头元素,队尾元素,rear,queue:queue()rear=newnode;rear-next=rear;count=0;boolstack:empty()constreturnrear-next=rear;error_codequeue:get_front(elementtype,error_codequeue:append(constelementtypex)node*s=newnode;s-data=x;s-next=rear-next;rear-next=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，并分析其时间性能。dataiadataib:A当前元素可能在B中，ib+dataia=dataib:删除A当前元素，ib+；,voidsubtraction(list,时间性能：O(|A|+|B|),习题2：假设递增有序顺序表A、B分别表示一个集合，设计算法求解C=AB，并分析其时间性能。dataiadataib:A当前元素可能在B中，ib+dataia=dataib:将该元素插入C表中ia+,ib+,ic+,voidintersection(listA,listB,list,时间性能：O(|A|+|B|),习题5-4：假设顺序表L中的元素按从小到大的次序排列，设计算法以删除表中的重复的元素，并要求时间尽可能少。对顺序表(1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9)模拟执行本算法，统计移动元素的次数。,voidDeleteRepeat(list,链表练习1：A表分成奇、偶两个子表A、B（A表做删除，B表做插入）,voidsplit(list/否则p,q后移,链表练习2：递增有序链表集合求交、并、差子集，考虑时间复杂度。,（1）C=ABpa-datadata:将A中当前元素插入C表中,pa=pa-nextpa-data=pb-data:将A或B中的当前元素插入C表中,pa=pa-next,pb=pb-nextpa-datapb-data：将B中当前元素插入C表中,pb=pb-next如果pa!=NULL,将A中剩余结点接到C表中，如果pb!=NULL，将B中剩余结点接到C表中。,voidmerge_list(list,（2）C=A-Bpa-datadata:A当前元素不在B中，将A中当前元素插入C表中，pa=pa-nextpa-datadata：A当前元素可能在B中，pb=pb-nextpa-data=pb-data:B当前元素在A中，pa=pa-next,pb=pb-next如果pa!=NULL,将A中剩余结点接到C表中。,voidsubtraction(list,习题6.6（2）：将递归程序转换为等价的非递归程序void