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(x<y) ia++; else if(x>y) ib++; else { C.insert(ic,x); ia++;ib++; ic++;} } 时间性能：O(|A|+|B|) }
算法与数据结构复习
习题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; }
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(x<y) ia++; else if(x>y) ib++; else { A.delete_element(ia); ib++;} } 时间性能：O(|A|+|B|) }
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->data<pb->data) { u=pa; s->next=u; s=u; pa=pa->next;} else if(pa->data>pb->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;} }
习题2：假设递增有序顺序表A、B分别表示一个集合，设计 算法求解C=A∩B，并分析其时间性能。
• data[ia]<data[ib]: A当前元素不在B中，ia++ • data[ia]>data[ib]: A当前元素可能在B中，ib++ • data[ia]=data[ib]: 将该元素插入C表中 ia++,ib++,ic++
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; }
链表练习2：递增有序链表集合求交、并、差子集，考虑时间复 杂度。
（1）C=AB • pa->data<pb->data : 将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表中。
习题5.5：递增有序顺序表A、B分别表示一个集合，设计算法 求解A=A-B，并分析其时间性能。
• data[ia]<data[ib]: A当前元素不在B中，ia++ • data[ia]>data[ib]: A当前元素可能在B中，ib++ • data[ia]=data[ib]: 删除A当前元or_code queue::append(const elementtype x) { if ( full() ) return overflow; rear = ( rear + 1 ) % maxlen ; data[rear] = x; count ++; tag=1; return success; } error_code queue::serve() { if ( empty() ) return underflow; front = ( front + 1 ) % maxlen; count --; tag=0; return success; }
习题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(i<L.length()) { L.get_element(i,x); for(j=L.length();j>i;j--) { L.get_element(j, y); if(x==y) L.delete_element(j); } i++; } }
链表练习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后移 } }
习题4.2：如果采用带尾指针的单循环链表作为队列 的存储结构，设计算法以实现队列的各运算。 rear
队头元素 q1 q2 ... 队尾元素 qn
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; }
（2）C=A-B • pa->data<pb->data: A当前元素不在B中，将A中当前元素插入C表中，
pa=pa->next • pa->data<pb->data： 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->data<pb->data) {u=pa; s->next=u; s=u; pa=pa->next;} else if(pa->data>pb->data) pb=pb->next; else { pa=pa->next; pb=pb->next;} } if(pa!=NULL) {s->next=pa;} }