数据结构 算法与数据结构复习教学内容.ppt

《数据结构 算法与数据结构复习教学内容.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构算法与数据结构复习error_codequeue::append(constelementtypex){if(full())returnoverflow;rear=(rear+1)%maxlen;data[rear]=x;count++;tag=1;returnsuccess;}error_codequeue::serve(){if(empty())returnunderflow;front=(front+1)%maxlen;count--;tag=0;returnsuccess;}习题4.2：如果采用带尾指针的单循环链表作为

2、队列的存储结构，设计算法以实现队列的各运算。q1q2qn...队头元素队尾元素rearqueue::queue(){rear=newnode;rear->next=rear;count=0;}boolstack::empty()const{returnrear->next==rear;}error_codequeue::get_front(elementtype&x)const{if(empty())returnunderflow;x=rear->next->next->data;returnsuccess;}error_codequ

3、eue::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)re

4、ar=front;returnsuccess;}习题5.5：递增有序顺序表A、B分别表示一个集合，设计算法求解A=A-B，并分析其时间性能。data[ia]data[ib]:A当前元素可能在B中，ib++data[ia]=data[ib]:删除A当前元素，ib++；voidsubtraction(list&A,listB){intia,ib,x,y;ia=ib=1;while(ia<=A.length()&&ib<=B.length()){A.get_element(i

5、a,x);B.get_element(ib,y);if(xy)ib++;else{A.delete_element(ia);ib++;}}}时间性能：O(

6、A

7、+

8、B

9、)习题2：假设递增有序顺序表A、B分别表示一个集合，设计算法求解C=A∩B，并分析其时间性能。data[ia]data[ib]:A当前元素可能在B中，ib++data[ia]=data[ib]:将该元素插入C表中ia++,ib++,ic++voidintersection

10、(listA,listB,list&C){intia,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(

11、A

12、+

13、B

14、)习题5-4：假设顺序表L中的元素按从小到大的次序排列，设计算法以删除表中的重复的元素，并要求时间尽可能少。对顺序表(1,1,2

15、,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9)模拟执行本算法，统计移动元素的次数。voidDeleteRepeat(list&L){inti,j,x,y;if(L.length()==0

16、

17、L.length()==1){cout<<"不需删除";return;}i=1;while(ii;j--){L.get_element(j,y);if(x==y)L.delete_element(j);}i++;}}链表练习1：A表

18、分成奇、偶两个子表A、B（A表做删除，B表做插入）voidsplit(list&A,list&B){node*La,*Lb;node*p,*q,*u,*s;La=A.get_head();Lb=B.get_head();