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

1、A,1,算法与数据结构复习,A,2,习题3.3：如果对循环队列采用设置运算标志的方式 来区分队列的满和空的状态，试给出对应的各运算实现。,在队列的类定义里加入一个标志位tag。 queue:queue( ) count = 0; front = rear = 0; tag=0; bool queue:empty( ) const if ( front=rear ,A,3,error_code queue:append(const elementtype x) if ( full() ) return overflow; rear = ( rear + 1 ) % maxlen ; datare

2、ar = x; count +; tag=1; return success; error_code queue:serve() if ( empty() ) return underflow; front = ( front + 1 ) % maxlen; count -; tag=0; return success; ,A,4,习题4.2：如果采用带尾指针的单循环链表作为队列的存储结构，设计算法以实现队列的各运算。,队头元素,队尾元素,rear,queue:queue( ) rear = new node; rear - next = rear; count = 0; bool stack

3、:empty( ) const return rear-next=rear; error_code queue:get_front(elementtype ,A,5,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* fro

4、nt = rear - next; node * u=front-next; front- next = u - next; delete u; count -; if ( front - next = NULL ) rear = front; return success; ,A,6,习题5.5：递增有序顺序表A、B分别表示一个集合，设计算法 求解A=A-B，并分析其时间性能。 dataiadataib: A当前元素可能在B中，ib+ dataia=dataib: 删除A当前元素， ib+；,void subtraction(list ,时间性能：O(|A|+|B|),A,7,习题2：假设递

5、增有序顺序表A、B分别表示一个集合，设计 算法求解C=AB，并分析其时间性能。 dataiadataib: A当前元素可能在B中，ib+ dataia=dataib: 将该元素插入C表中 ia+,ib+,ic+,void intersection(list A, list B, list ,时间性能：O(|A|+|B|),A,8,习题5-4：假设顺序表L中的元素按从小到大的次序排列，设计 算法以删除表中的重复的元素，并要求时间尽可能少。对顺序 表(1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9) 模拟执行本算法，统计移动元素的次数。,void DeleteRepeat(

6、list ,A,9,链表练习1： A表分成奇、偶两个子表A、B（A表做删除，B表 做插入）,void split(list /否则p,q后移 ,A,10,链表练习2：递增有序链表集合求交、并、差子集，考虑时间复 杂度。,（1）C=AB 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表中。,A,11,void merge_list(list ,A,12,（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,13,习题6.6（2）：将递归程序转换为等价的非递归程序 vo