数据结构专题实验.docx

实验目的通过实验更好的理解、应用本学期数据结构所学知识,例如线性表、树、图、排序、查找、索引。将三大结构和两个应用融会贯通,理论运用于实践。在实验中提高自身的编程能力,同时学会比较不同程序的时间空间成本,力求写出更加优质的程序。养成用所学知识解决实际问题的习惯,学以致用而不是死学知识。实验内容背包问题的求解【栈(线性表)】问题描述假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…wn的物品,能否从n件物品中挑选若干件恰好装满背包,即使w1+w2+…+wm=T,要求找出所有满足上述条件的解。例如:当T=10,各件物品的体积{1,8,4,3,5,2}时,可找到下列4组解: (1,4,3,2) (1,4,5) (8,2) (3,5,2)。基本要求设计基础:堆栈分析设计课题的要求,要求编程实现以下功能:<1>从n件物品中挑选若干件恰好装满背包<2>要求找出所有满足上述条件的解,例如:当T=10,各件物品的体积{1,8,4,3,5,2}时,可找到下列4组解:(1,4,3,2)、(1,4,5)、(8,2)、(3,5,2)。算法分析首先将n件物品排成一列,依次选取;若装入某件物品后,背包内物品的总质量不超过背包最大装载质量时,则装入(进栈);否则放弃这件物品的选择,选择下一件物品试探,直至装入的物品总和正好是背包的最大转载质量为止。这时我们称背包装满。若装入若干物品的背包没有满,而且又无其他物品可以选入背包,说明已装入背包的物品中有不合格者,需从背包中取出最后装入的物品(退栈),然后在未装入的物品中挑选,重复此过程,直至装满背包(有解),或无物品可选(无解)为止。实验代码#include"iostream"usingnamespacestd;template<classElem>classStack{ private: intsize; inttop; public: Elem*listArray; Stack(intsz=DefaultListSize) { size=sz; top=0; listArray=newElem[sz]; } ~Stack() { delete[]listArray; } voidclear() {top=0;} boolpush(constElem&item) { if(top==size) returnfalse; else { listArray[top++]=item; returntrue; } } intpop(Elem&it) { if(top==0)return-1; else { it=listArray[--top]; returnit; } } inttopvalue(Elem&it)const { if(top==0) return-1; else { it=listArray[top-1]; returnit; } } intlength()const {returntop;}};intmain(){ Stack<int>beibao(100); intweight[100],n,T; inti=0,k=0,a[100]; cout<<"请输入背包总体积T:"; cin>>T; cout<<"请输入物品件数n:"; cin>>n; cout<<"请输入物品质量weight:"; for(i=0;i<n;i++) cin>>weight[i]; do{while(T>0&&k<n){if(T>=weight[k]){//(weight[k]);T-=weight[k];}k++;//不符合则考察下一个背包}if(T==0){//找到一种方法,输出cout<<"找到方法:";for(i=0;i<();i++) {cout<<[i]<<"";}cout<<endl;} (a[0]); for(i=0;i<n;i++) { if(a[0]==weight[i])break; }k=i;//找不到方法,则前一个入栈的背包出栈,继续考察下一个背包T+=weight[k];k++;}while(!(()==0&&k==n));//当栈空且k==N时,所有可能的组合都考察完毕,推出循环return0;}实验结果农夫过河问题的求解【图】问题描述一个农夫带着一只狼、一只羊和一棵白菜,身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船,船只能容下他和一件物品,另外只有农夫才能撑船。如果农夫在场,则狼不能吃羊,羊不能吃白菜,否则狼会吃羊,羊会吃白菜,所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开,而狼不吃白菜。请求出农夫将所有的东西