青岛理工大学数据结构第二次实验报告

1青岛理工大学数据结构课程实验报告课程名称数据结构班级Abcxxx实验日期2015.9.25姓名Abc学号2014xxxxx实验成绩实验名称顺序表和链表的实现和应用实验目的及要求（1）掌握顺序表的顺序存储方法和基本操作；（2）掌握链表表的链式存储方法和基本操作；（3）了解顺序表和链表的优缺点和适用场合；（3）能够运用顺序表或链表解决问题。实验环境硬件平台：普通的PC机软件平台：Windows2003操作系统编程环境：VisualC++实验内容1.采用递增有序的顺序表表示集合，求解两个集合的交集、并集和差集（1）定义顺序表的存储结构；（2）实现存储递增有序集合的顺序表的建立、求交集、并集和差集等运算；（3）要求算法的时间性能在线性时间复杂度内；（4）和采用无序顺序表所表示的集合的有关运算的时间性能进行比较。2.采用递增有序的链表表示集合，求解两个集合的交集、并集和差集（1）定义链表的存储结构；（2）实现存储递增有序集合的链表的建立、求交集、并集和差集等运算；（3）要求算法的时间性能在线性时间复杂度内；（4）和采用无序链表所表示的集合的有关运算的时间性能进行比较。3.比较顺序表和链表的优缺点和适用场合2算法描述及实验步骤templateclassTclassSQList//顺序表templateclassTclassSQListjcb//顺序表的交叉并templateclassTclassSQLnode//单链表templateclassTclassSQLnodejcb//链表的交叉并调试过程及实验结果总结本次试验对于顺序表和链表的优缺点的认识更加深刻。顺序表中进行查找操作时较方便，而链表则适合进行插入和删除运算。顺序表存储密度大，存储空间利用率高；链表插入和删除运算时很方便，使用灵活。求集合的交并差运算用顺序表和链表实现时，顺序表的程序比较好做一点，因为是使用另一个数组C来存储运算结果，所以并没有在数组中进行插入和删除运算，程序较简单；而做链表时遇到了困难，再插入新节点时程序总是不能运行。附录#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERLOW-2#includeiostream#includestring#includewindows.husingnamespacestd;3typedefintStatus;constintLIST_INIT_SIZE=100;constintLISTINCREMENT=10;templateclassTclassSQList//顺序表{private:T*elem;T*newbase;intlength;intlistsize;public:T*Getelem(){returnelem;}intGetlength(){returnthis-length;}SQList(){elem=newT[LIST_INIT_SIZE];if(!elem){exit(OVERLOW);}length=0;listsize=LIST_INIT_SIZE;}StatusListInsert(inti,Te){if(i1||ilength+1)returnERROR;if(lengthlistsize){newbase=(T*)realloc(elem,listsize+LISTINCREMENT);if(!newbase)exit(OVERLOW);elem=newbase;listsize+=LISTINCREMENT;}T*p=&elem[i-1];4T*q=&elem[length-1];for(q;q=p;q--){*(q+1)=*q;}*p=e;length++;returnOK;}StatusListAdd(Te){this-elem[this-length]=e;this-length++;returnOK;}StatusListDelete(inti,T&e){if(ilength||i1)returnERROR;T*p=&elem[i-1];e=*p;T*q=&elem[this-length-1];for(++p;p=q;p++){*(p-1)=*p;}length--;returnOK;}StatusListShow(){for(inti=0;ilength;i++){coutelem[i]endl;}returnOK;}};templateclassTclassSQListjcb//顺序表的交叉并{public:voidJiaoJi(SQListTa,SQListTb){5SQListinth;int*p=a.Getelem();int*q=b.Getelem();if(a.Getlength()b.Getlength()){for(inti=0;ib.Getlength();i++){for(intj=0;ja.Getlength();j++){if(q[i]==p[j]){h.ListAdd(q[i]);break;}}}}else{for(inti=0;ib.Getlength();i++){for(intj=0;ja.Getlength();j++){if(q[i]==p[j]){h.ListAdd(q[i]);break;}}}}if(h.Getlength()==0){cout交集为空endl;}else{cout交集为：endl;h.ListShow();}}6voidbingji(SQListTa,SQListTb){SQListintc;intv;int*pa=a.Getelem();int*pb=b.Getelem();int*pc=c.Getelem();while(paa.Getelem()+a.Getlength()&&pbb.Getelem()+b.Getlength()){if(*pa=*pb){c.ListAdd(*pa);pa++;}else{c.ListAdd(*pb);pb++;}}if(pa==a.Getelem()+a.Getlength()){for(pb;pbb.Getelem()+b.Getlength();pb++){c.ListAdd(*pb);}}else{for(pa;paa.Getelem()+a.Getlength();pa++){c.ListAdd(*pa);}}for(inti=1;ic.Getlength();i++){intj=i;inth=j--;if(pc[j]==pc[h]){c.ListDelete(i+1,v);}7}cout并集为：endl;c.ListShow();}voidchaji(SQListTa,SQListTb){SQListinth;intw;int*p=a.Getelem();int*q=b.Getelem();int*qh=h.Getelem();if(a.Getlength()b.Getlength()){for(inti=0;ib.Getlength();i++){for(intj=0;ja.Getlength();j++){if(q[i]==p[j]){h.ListAdd(q[i]);break;}}}for(inti=0;ih.Getlength();i++){for(intj=0;ja.Getlength();j++){if(qh[i]==p[j]){intt=j;t++;a.ListDelete(t,w);break;}}}cout差集为：endl;a.ListShow();}else{for(inti=0;ib.Getlength();i++){8for(intj=0;ja.Getlength();j++){if(q[i]==p[j]){h.ListAdd(q[i]);break;}}}for(inti=0;ih.Getlength();i++){for(intj=0;jb.Getlength();j++){if(qh[i]==q[j]){intt=j;t++;b.ListDelete(t,w);break;}}}cout差集为：endl;b.ListShow();}}};templateclassTstructLnode//链表的节点结构体{TData;Lnode*next;};templateclassTclassSQLnode//单链表{public:LnodeT*head;SQLnodeT(){this-head=newLnodeT();this-head-next=NULL;}9StatusSQLnodeAdd(Te){LnodeT*p=newLnodeT();LnodeT*q=head;p-Data=e;p-next=NULL;if(head-next==NULL){head-next=p;}else{while(q-next!=NULL){q=q-next;}q-next=p;}returnOK;}StatusSQLnodeInsert(inti,Te){LnodeT*p=head;intj=0;while(p&&ji-1)//当i为0或1时，都在第一个节点前插入一个元素，p决定表是否遍历完，j决定i是否合法{p=p-next;j++;}if(!p||ji-1)returnERROR;LnodeT*s=newLnodeT();s-Data=e;s-next=p-next;p-next=s;returnOK;}StatusSQLnodeDelete(inti,T&e){LnodeT*p=head;intj=0;while(p-next&&ji-1)10{p=p-next;}if(p-next||ji-1)returnERROR;LnodeT*q=p-next;p-next=q-next;e=q-Data;delete(q);returnOK;}StatusSQLShow(){LnodeT*p=head-next;while(p-next!=NULL){coutp-Dataendl;p=p-next;}coutp-Dataendl;returnOK;}intSQLGetLength(){inti=0;LnodeT*p=head;while(p-next){p=p-next;i++;}returni;}};templateclassTclassSQLnodejcb//链表的交叉并{public:SQLnodeTBingji(SQLnodeTa,SQLnodeTb){SQLnodeTc;LnodeT*la=a.head;LnodeT*lb=b.head;LnodeT**lc=&c.head;11LnodeT*pb,*pa,*pc;pa=la-next;pb=lb-next;*lc=pc=la;while(pa&&pb){if(pa-Data=pb-Data){pc-next=pa;pc=pa;pa=pa-next;}else{pc-next=pb;pc=pb;pb=pb-next;}}pc-next=pa?pa:pb;free(lb);LnodeT*newhead=*lc;LnodeT*p;newhead=newhead-next;while(newhead-next){p=newhead-next;if(newhead-Data==p-Data){newhead-next=p-next;delete(p);}elsenewhead=newhea