《数据结构与算法分析专题实验_ 西安交大_ 赵仲孟》由会员分享，可在线阅读，更多相关《数据结构与算法分析专题实验_ 西安交大_ 赵仲孟（43页珍藏版）》请在金锄头文库上搜索。
1、. . . . .西安交通大学数据结构与算法课程实验实验名称：数据结构与算法课程专题实验所属学院：电信学院专业班级：计算机32班小组成员：指导老师：赵仲孟 教授 实验一 背包问题的求解1.问题描述 假设有一个能装入总体积为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)。 2.实现提示 可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后，顺序选取
2、物品装入背包，若已选取第i件物品后未满，则继续选取第i+1件，若该件物品“太大”不能装入，则弃之，继续选取下一件，直至背包装满为止。 如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入的物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直到求得满足条件的解，或者无解。 由于回溯求解的规则是“后进先出”，自然要用到“栈”。 3.问题分析1、设计基础 后进先出，用到栈结构。2、分析设计课题的要求，要求编程实现以下功能： a从n件物品中挑选若干件恰好装满背包 b. 要求找出所有满足上述条件的解，例如：当T=10，各件物品的体积1，8，4， 3，5，2时，
3、可找到下列4组解：（1，4，3，2）、（1，4，5）、（8，2）、（3，5，2）3，要使物品价值最高，即p1*x1+p2*x1+.+pi*xi(其1=inext; delete temp; size=0; void push(int it, int b) top=new Link(it,top); asize=b; size+; int pop() int it=top-m; Link * ltemp=top-next; delete top; top=ltemp; size-; return it; int topValue() return top-m; int length() retu
4、rn size; int sum() int s=0; for(int i=0;isize;i+) s=s+ai; return s; void print() for(int i=0;isize;i+) coutai ; coutpop()+1;isum()+x2ipush(i,x2i); if(x4-sum()=x1) x4-print(); break; if(x4-length()=1&x4-topValue()=n-1) return ; else panduan(x1, n,x2,x4);int main()LStack *ll=new LStack(0);int m100;int
5、 n,z;cout输入物品个数n;cout输入物品大小endl;for(int i=0;imi;cout输入背包大小z;ll-push(-1,0);cout符合条件的解endl;panduan(z,n,m,ll);return 0;结果1：代码2：#include# includeusing namespace std;struct Bag int V; /背包体积 int number; /物品数量 int v20; /物品体积 int value20; /物品价值 int dp2020; /最大价值bag;int max(int a,int b) return ab?a:b;int mai
6、n() cout请输入背包的容量：bag.V; cout请输入物品的数量：bag.number; cout请输入每件物品的体积：endl; for(int i=1;ibag.vi; cout请输入每件物品的价值：endl; for(int i=1;ibag.valuei; memset(bag.dp,0,sizeof(bag.dp); /dp中的每一个元素置零 for(int i=1;i=bag.number;i+) for(int j=0;j=bag.vi) bag.dpij=max(bag.dpi-1j,bag.dpi-1j-bag.vi+bag.valuei); else bag.dpi
7、j=bag.dpi-1j; cout最大价值：bag.dpbag.numberbag.V=0，则该物品可选；若sum-weightin，则需退栈，若此时栈空，则说明无解。实验二 二叉排序树的实现1. 问题描述 分别采用二叉链表和顺序表作存储结构，实现对二叉排序树的操作。2. 基本要求（选择其中之一方式实现） (1)用二叉链表作存储结构实现二叉排序树。 (2)以回车符(n)为输入结束标志，输入数列L，生成一棵二叉排序树T； (3)对二叉排序树T作中序遍历，输出结果； (4)计算二叉排序树T查找成功的平均查找长度，输出结果； (5)输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作
8、中序遍历(执行操作2)；否则，输出信息“无x”；3.问题分析 可以再二叉树建立时记录每个节点移动到正确位置所需要的移动步数，再用总的移动步数除以总的节点数就是平均查找步数。4.算法实现代码：#includeiostream#includemath.h#includestring.h#includestdlib.husing namespace std;class BSTNodepublic: double it; BSTNode *lc; BSTNode *rc; BSTNode() lc=rc=NULL; BSTNode(double a,BSTNode* l=NULL, BSTNode* r=NULL) it=a; lc=l; rc=r; BSTNode() double getele() return it; void setele(double a) it=a; inline BSTNode* getlc() return lc; inline BSTNode* getrc() retu
