数据结构专题实验.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"
using namespace std;
template <class Elem> class Stack
{
private:
int size;
int top;
public:
Elem *listArray;
Stack(int sz=DefaultListSize)
{
size=sz;
top=0;
listArray=new Elem[sz];
}
~Stack()
{
delete []listArray;
}
void clear()
{top=0;}
bool push(const Elem& item)
{
if (top==size)
return false;
else
{
listArray[top++]=item;
return true;
}
}
int pop(Elem& it)
{
if(top==0) return -1;
else
{
it=listArray[--top];
return it;
}
}
int topvalue(Elem& it)const
{
if(top==0)
return -1;
else
{
it=listArray[top-1];
return it;
}
}
int length()const
{return top;}
};
int main()
{
Stack<int> beibao(100);
int weight[100],n,T;
int i=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; //找不到方法,则前一个入栈的背包