数据结构实训
院(系): 软件学院
专业年级: 软件工程 20##级
姓 名: 李乾坤
学 号: 091530108
指导教师: 刘高原 讲师
20##年06月18日
查找排序
一、 需求分析
对一组无序数据进行排序，找出排序后某一数据所在的位置。
二、 概要设计 略
三、 详细设计 略
四、 算法分析
简单地说，冒泡法就是先找最小值，再找次小值……，快排则是在一次循环中使它们局部有序，多次循环，直至全部有序为止。二分查找充分利用了有序序列的特性，从某种意义上讲，二分查找侧重的不是比较两个数是不是相等，而是确定要查找的数的范围。
五、 程序总结
这个算法给我的最大启发就是我们要充分利用已有的信息。比如对已经排好序的数据进行查找，如果只是平淡的顺序查找，就比二分查找的效率低很多。为什么？因为二分查找考虑并利用了这些信息。同样的理论还可以用来解释为什么快排就比冒泡来得快，排序说白了就是为每一个数找到一个它应该呆的位置。假如为1~10排序，冒泡排序说白了就是一开始先找最大值移到最上边，这没错，关键是次小值又从底部开始找，使以前做的许多移动又有一部分重复了。快排则是，我不管以前怎么着，8碰到5就得放5的右边这总没错吧，以后碰到合适的再移动，但8和5的相对移动不会再重复了。由此观之，消除程序中的重复工作是提高效率的关键，不过高效率的算法可不是长在树上的（说有就有的），比如二分搜索排序，即使看起来很简单，能想起来这么做却是非常不简单的。
0-1背包问题（Bag）
一、 需求分析
从若干个具有一定价值和质量的物品挑出一些放入具有容量限制的背包，使背包的所容纳物品的价值最大。
二、 概要设计
三个面板类，用card布局依次显示
三、 详细设计
1）第一个card负责设置背包容量和最大物品个数
2）第二个card负责输入物品名称、重量、价格
3）第三个card显示结果
四、 算法分析
本算法的关键是建立递归公式：m[i][j],m[n][j]
m(i,j)= max{m(i+1,j),m(i+1,j-wi)+vi} j>=wi
m[i][j]=
m(i+1,j) 0=<j<wn
m(n,j)= vn j>wi
m[i][j]=
0=<j<wi
算法的主要思路就是将这个公式程序化，所以说数学建模很重要。在这里我觉得最精华的倒不是算法实现，最重要的有两点：一、动态规划法的思维方式，这种解题方式可以说是递归迭代，也可以认为是建了一个表去记录已经完成的运算成果以方便后边使用，避免重复运算。二、是用一种间接的方式保存被选中的物品，也就是这个表（m(i,j)），没有这个表就没有这个算法。
五、 程序总结
通过完成此次试验，对动态规划法感慨良多。0-1背包问题的本质就是判断一个物品该不该放到背包里，然而这种判断还依赖于其他物品的选择，比较方便的方法就是穷举法，判断所有可能的状况，但这样的效率就太低了。解决一问题总有一个量来衡量解决这个问题所需要做的最少工作，编程的一个目标就是如何是计算机的效率更好的逼近这个量。研究穷举法我们会发现有很多重复的运算，优化穷举法的重要思路就是利用动态规划法的思想：利用已有的成果以避免重复运算，未进行的运算可以以已进行的运算为基础。因此我们必须有一种信息的表示方式来说明这个运算已经进行过了，反映到数学上就是发现运算之间的迭代关系。
我们再从另一个角度去理解。吃饭要一口一口的吃，解决问题的一个重要方法就是缩小问题规模。如何缩小问题规模是个大学问，我们解决问题一般都有两种方法论——递推和递归，递推在这里很明显需要大量的回溯，或者直接就是低效率的穷举法。如果从递归方面看，我们先假设一个最优的结果，然后再看背包容量减少后的最优结果，这样一直迭代。算法的设计是最费脑筋的，但是查看一个优秀的算法非常有助于培养人们灵活的思维方式。
最短路径问题（LJ）
一、 需求分析
为用户提供一种输入手段获得一个无向图（或邻接矩阵），出发点和目的地，通过一定算法得到出发点到目的地的最短路径，显示给用户。
二、 概要设计
三、详细设计
1. 数据类
1）结点类Node
此类负责记录结点信息：坐标（x,y），结点名称，结点序号
2）边类
此类负责记录结点之间连线的信息：起点序号，终点序号，起点和终点的距离
我们在用户输入界面中建立两个向量对象，分别是结点类型和边类型，当新建一个结点和边时，添加到相应的向量中。
2.用户输入界面（F）
用户界面需要提供一个面板供用户画无向图，一个面板为用户提供画图时的结点坐标、距离、角度等辅助信息，一个面板供用户输入出发点和目的地。由此将主界面设计成中、东、南的BorderLayout布局。
1）中间的面板类Center
因为有用户画图的需要，所以必须重写该类的paint方法。该类有两个任务：画结点（要标明结点名称）、画结点之间的连线（要标明结点距离）。因此该类对象在执行repaint方法前应该明确任务类型（画点还是画线），明确需要标明的串值，明确结点坐标，这也就明确了该类应具有的属性值和方法。
2）东边的面板类
该类只是利用面板的布局作用，故不用单独定义。用户画无向图时需要的辅助信息有:结点的位置坐标，一个结点相对于另一个结点的距离、角度，连线的起点、终点。
于是，我们需要一个文本框供用户输入节点名称，记录节点个数，一个下拉列表供用户选择参照点，两个文本框显示未选点到参照点的距离和角度，两个下拉列表供用户选择起点和终点。
这就需要Center对象监听鼠标事件获取鼠标指针的位置，获取用户选择的参照点的位置坐标，由此得到未选点到参照点的距离和角度。获取用户选择的起点坐标和终点坐标，以此得到边的长度。
3）南边的面板类
该类只是利用面板的布局作用，故不用单独定义。我们需要两个下拉列表供用户选择最短路径的起点和终点，单击按钮获取最短路径。为了更加的人性化，我们提供取消上一步的功能。取消上一步的功能实现：程序中准备一个专门存储结点和边对象的序号的向量类，取消上一步时，获取最后一个序号，判断边类型和节点类型，根据该序号搜索节点向量和边向量，得到相应的属性，再用Center类对象的背景色将该对象重画一遍，覆盖原来的图形，即可得到取消上一步的效果。同时，在结点向量和边向量中去掉取消的结点对象或边对象。
3、算法类
我们从界面类获得了一个结点类型向量，一个边类型向量，最短路径的起点和终点。在该类的构造函数中我们边向量中的数据转换成一个邻接矩阵供Floyd算法使用
四、 算法分析
假设有向图用邻接矩阵存储，另外设置一个二维数组A用于存放当前顶点之间的最短路径长度，分量A[i][j]表示当前顶点vi到顶点vj的最短路径长度。弗洛伊德的基本思想是递归产生一个矩阵序列A0,A1……Ak……An,其中Ak[i][j]表示从vi到顶点vj的路径上所经过的顶点编号不大于k的最短路径。换句话说Ak[i][j]表示，考虑过点K之后，点i到点j的最短距离。
五、程序总结
通过此次实验，使我明白编程序就像盖房子，有两件事非常重要：一、根据客户的要求、客户对房子的定位设计好房子该如何建，这该有什么，那该有什么，即设计好房子的图纸，既要简洁美观又要实用；二，把图纸变成实实在在的房子。这需要点什么材料，先做什么，后做什么。反映到编程就是，给一个项目或客户需求，如何把它编程具有可操作性的系统说明书，如何从理论上实现这个项目，这需要较高的系统分析能力。然后具体的编写程序，这就要求较高的算法能力。
此次试验，如果单纯的借鉴已有的弗洛伊德算法，那么最复杂的就不是算法实现，而是如何规范并获取用户输入的信息并将这些信息转换成算法需要的邻接矩阵。这实际上是一个更困难的问题，因为这直接影响了整个程序的结构。而算法反而居于次要的位置了，因为不管程序结构如何，你只要将弗洛伊德算法弄一个类放在那里即可。
经济学和历史上都认为，商品交换是现代文明的基础之一而不是商品生产。如何进行信息的交换也是编程的重要问题。很多时候是数据交换决定了该程序的架构，如何更好的表示信息、组织信息、处理信息实际上成为了程序的核心工作，也是编程人员应该培养的核心能力。算法设计对这样的能力要求也很高，如果你明白背包问题中如何表示已经选中的物品，你基本就了解了解决背包问题算法的一切。
附 录
Main类程序入口
package LI;
public class Main {
public static void main(String args[]){
new F("最短路径问题");
}
}
主窗口F类
package LI;
import java.awt.*;
import java.awt.event.*;
import java.util.Vector;
import javax.swing.*;
class F extends JFrame implements ActionListener,MouseListener,MouseMotionListener,ItemListener{
/**
*
*/
private static final long serialVersionUID = 1L;
JPanel east=null,south=null;
Center center=null;
JTextField text[]=null;
JComboBox list[]=null;
JButton edge=null,button=null,reset=null;
//int x,y,nodeNumber=0,edgeNumber=1000,
int x,y, cx=0,cy=0;//参照点坐标
String string=null;
Vector<Node> vector1=null;//存储点类型的向量
Vector<Edge> vector2=null;//存储边类型的向量
Vector<Integer> recode=null;//取消上一步中存储点或边的序号
JLabel label=null;
Cursor c1=null,c2=null;
F(String s){//构造函数
super(s);
c1=Cursor.getPredefinedCursor(Cursor.DEFAULT_CURSOR);//默认指针
c2=Cursor.getPredefinedCursor(Cursor.HAND_CURSOR);//手型指针
vector1=new Vector<Node>();
vector2=new Vector<Edge>();
recode=new Vector<Integer>();
text=new JTextField[5];
for(int i=0;i<5;i++){
text[i]=new JTextField(8);
}
Box basebox=Box.createVerticalBox();
Box box[]=new Box[11];
for(int i=0;i<11;i++){
box[i]=Box.createHorizontalBox();
}
list=new JComboBox[5];
for(int i=0;i<5;i++){
list[i]=new JComboBox();
}
list[0].addItem("原点(0,0)");
list[0].addItemListener(this);
Container con=getContentPane();
//color=con.getBackground();
con.setBackground(Color.cyan);//种花得柳，这样center显示出来了
center=new Center();
center.addMouseListener(this);
center.addMouseMotionListener(this);
con.add(center,BorderLayout.CENTER);
label=new JLabel("第1个结点名称:");
box[0].add(label);
box[0].add(Box.createHorizontalStrut(8));
box[0].add(text[0]);
box[1].add(new JLabel("结点位置:"));//
box[1].add(Box.createHorizontalStrut(130));
box[2].add(Box.createHorizontalStrut(20));
box[2].add(new JLabel("X:"));
box[2].add(Box.createHorizontalStrut(8));
box[2].add(text[1]);
box[3].add(Box.createHorizontalStrut(20));
box[3].add(new JLabel("Y:"));
box[3].add(Box.createHorizontalStrut(8));
box[3].add(text[2]);
box[4].add(new JLabel("参照点:"));
box[4].add(Box.createHorizontalStrut(8));
box[4].add(list[0]);
box[5].add(new JLabel("距离"));
box[5].add(Box.createHorizontalStrut(8));
box[5].add(text[3]);
box[6].add(new JLabel("角度"));
box[6].add(Box.createHorizontalStrut(8));
box[6].add(text[4]);
box[7].add(new JLabel("连接起点和终点:"));
box[7].add(Box.createHorizontalStrut(90));
box[8].add(Box.createHorizontalStrut(20));
box[8].add(new JLabel("起点"));
box[8].add(Box.createHorizontalStrut(8));
box[8].add(list[1]);
box[9].add(Box.createHorizontalStrut(20));
box[9].add(new JLabel("终点"));
box[9].add(Box.createHorizontalStrut(8));
box[9].add(list[2]);
edge=new JButton("连接");
edge.addActionListener(this);
box[10].add(edge);
basebox.add(Box.createVerticalStrut(20));
for(int i=0;i<11;i++){
basebox.add(box[i]);
basebox.add(Box.createVerticalStrut(10));
}
east=new JPanel();
east.add(basebox);
con.add(east,BorderLayout.EAST);
south=new JPanel();
south.add(new JLabel("出发点"));
south.add(list[3]);
south.add(new JLabel("目的地"));
south.add(list[4]);
button=new JButton("最短路径 ");
button.addActionListener(this);
south.add(button);
reset=new JButton("取消上一步");//想做到这一点就得来一个向量记录点和边的编号
reset.addActionListener(this);
south.add(reset);
con.add(south,BorderLayout.SOUTH);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
setBounds(400,400,500,500);
setVisible(true);
validate();
}
public void itemStateChanged(ItemEvent e){//更换参照点的坐标
if(e.getSource()==list[0]){
int s=list[0].getSelectedIndex();
if(s==0){
cx=0;
cy=0;
}
else{
cx=vector1.elementAt(s-1).getX()+5;
cy=vector1.elementAt(s-1).getY()+5;//加5之后才是圆心
//System.out.println("cx:"+cx+"cy:"+cy);
}
}
}
public void actionPerformed(ActionEvent e){
if(e.getSource()==edge){//连接两个节点
int s=list[1].getSelectedIndex();
int d=list[2].getSelectedIndex();
if(s==d){
JOptionPane.showMessageDialog(this,"起点和邻接点不能相同！","警告对话框",JOptionPane.WARNING_MESSAGE);
}
else{
int x1=vector1.elementAt(s).getX();
int y1=vector1.elementAt(s).getY();
int a1=vector1.elementAt(d).getX();
int b1=vector1.elementAt(d).getY();
int edgeNumber=vector2.size()+1000;//加上1000，作为点和边的区别
System.out.println("edgeNumber-->"+edgeNumber);
Edge edge=new Edge();
edge.setSD(s,d);
edge.setNumber(edgeNumber);
recode.add(new Integer(edgeNumber));
//edgeNumber++;
double dis=Math.sqrt((x1-a1)*(x1-a1)+(y1-b1)*(y1-b1));
int distance=new Double(dis).intValue();//只保留double值的整数部分
edge.setDistance(distance);
vector2.add(edge);
center.setC(Color.black);
center.setMode(2);
center.setXY(x1, y1);
center.setAB(a1, b1);
center.setString(""+distance);
center.repaint();
}
}
else if(e.getSource()==button){//获取出发点和目的地，返回最短路径
int s=list[3].getSelectedIndex();
int d=list[4].getSelectedIndex();
if(s==d){
JOptionPane.showMessageDialog(this,"出发点和目的地不能相同！","警告对话框",JOptionPane.WARNING_MESSAGE);
}
else{
Floyd floyd=new Floyd(vector1,vector2,s,d);
JOptionPane.showMessageDialog(this,"最短路径："+floyd.getLJ()+"\n最短长度："+floyd.getDistance(),"消息对话框",JOptionPane.WARNING_MESSAGE);
}
}
else if(e.getSource()==reset){//取消上一步
center.setC(Color.CYAN);
if(recode.size()>0){
int number=recode.lastElement().intValue();
//System.out.println("number-->"+number);
if(number>=1000){//边的编号从1000开始
//number=number-1000;
Edge ed=vector2.elementAt(number-1000);
int dis=ed.getDistance();
int x1=vector1.elementAt(ed.getSource()).getX();
int y1=vector1.elementAt(ed.getSource()).getY();
int x2=vector1.elementAt(ed.getDestination()).getX();
int y2=vector1.elementAt(ed.getDestination()).getY();
center.setMode(2);//模式2为边，再画一条和背景色相同的边
center.setXY(x1,y1);
center.setAB(x2,y2);
center.setString(""+dis);
vector2.removeElementAt(number-1000);//边向量中删掉这一条边的数据
}
else{
Node no=vector1.elementAt(number);
int x0=no.getX();
int y0=no.getY();
String name=no.getName();
center.setMode(1);//模式1为点，再画一条和背景色相同的点
center.setXY(x0, y0);
center.setString(name);
vector1.removeElementAt(number);//点向量中删掉关于这个点的数据
label.setText("第"+(vector1.size()+1)+"个结点名称:");
for(int i=1;i<5;i++){
list[i].removeItemAt(number);
}
list[0].removeItemAt(number+1);
}
center.repaint();
recode.removeElementAt(recode.size()-1);//删除最后边的点或边的序号
System.out.println("number1-->"+number);
}
else
JOptionPane.showMessageDialog(this,"已取消完毕！","警告对话框",JOptionPane.WARNING_MESSAGE);
}
}
public void mousePressed(MouseEvent e){//鼠标按下以后
x=e.getX()+5;
y=e.getY()+5;
if(e.getModifiers()==InputEvent.BUTTON1_MASK){//如果单击左键
string=text[0].getText();
if(string.equals("")){
JOptionPane.showMessageDialog(this,"请输入结点名称！","警告对话框",JOptionPane.WARNING_MESSAGE);
}
else{
Node node=new Node();
node.setLocation(x, y);
node.setName(string);
int nodeNumber=vector1.size();
System.out.println("nodeNumber-->"+nodeNumber);
node.setNumber(nodeNumber);
recode.add(new Integer(nodeNumber));
vector1.add(node);
center.setC(Color.black);
center.setMode(1);
center.setXY(x, y);
center.setString(string);
center.repaint();
for(int i=0;i<5;i++){
list[i].addItem(string);
}
//nodeNumber++;
text[0].setText("");
label.setText("第"+(nodeNumber+2)+"个结点名称:");
}
}
}
public void mouseReleased(MouseEvent e){}
public void mouseEntered(MouseEvent e){}
public void mouseExited(MouseEvent e){//鼠标离开以后
setCursor(c1);
}
public void mouseClicked(MouseEvent e){}
public void mouseDragged(MouseEvent e){}
public void mouseMoved(MouseEvent e){//鼠标在Center类上移动
setCursor(c2);
int x0=e.getX()+5;
int y0=e.getY()+5;
double dis=Math.sqrt((x0-cx)*(x0-cx)+(y0-cy)*(y0-cy));
int distance=new Double(dis).intValue();//只保留double值的整数部分
text[1].setText(""+x0);
text[2].setText(""+y0);
text[3].setText(""+distance);
text[4].setText(""+f1(x0,y0,cx,cy));
}
public int f1(int x0,int y0,int cx,int cy){//根据所给的临边和对边的起点和终点坐标得到角度
double angle=0;
int jiaodu=0;
angle=Math.atan2(cy-y0,x0-cx);//两个参数分别为邻边、对边
angle=angle*180/Math.PI;
jiaodu=new Double(angle).intValue();//只保留double值的整数部分
return jiaodu;
}
}
点类Node，存放结点的一些信息
package LI;
class Node {
String name=null;
int x,y,number;
public void setName(String name){
this.name=name;
}
public void setLocation(int a,int b){
x=a;
y=b;
}
public String getName(){
return name;
}
public int getX(){
return x;
}
public int getY(){
return y;
}
public void setNumber(int n){
number=n;
}
public int getNumber(){
return number;
}
}
边类：Edge，存放边的一些信息
package LI;
class Edge {
int source=0,destination=0,distance=0,number=0;
//为了不让点和边的number混淆，我们将边的number的基数设为1000
public void setSD(int s,int d){
source=s;
destination=d;
}
public int getSource(){
return source;
}
public int getDestination(){
return destination;
}
public void setDistance(int dis){
distance=dis;
}
public int getDistance(){
return distance;
}
public void setNumber(int number){
this.number=number;
}
}
Center类，主窗口负责绘制无向图的类
package LI;
import java.awt.Color;
import java.awt.Graphics;
import javax.swing.JPanel;
class Center extends JPanel{
/**
*
*/
private static final long serialVersionUID = 1L;
int x,y,mode,a,b,
x1,y1;
String string="";
Color color=Color.black;
Center(){
setBackground(Color.cyan);
}
public void setC(Color c){
color=c;
}
public void setXY(int x,int y){
this.x=x;
this.y=y;
}
public void setAB(int a,int b){
this.a=a;
this.b=b;
}
public void setString(String str){
string=str;
}
public void setMode(int m){
mode=m;
}
public void paint(Graphics g){
g.setColor(color);
if(mode==1){//模式为1时画点
g.fillOval(x, y, 10, 10);
g.drawString(string, x, y);
}
else if(mode==2){//模式为2时画边
g.drawLine(x+5, y+5, a+5, b+5);//加5是为了让其画到圆心
g.drawString(string, (x+a+10)/2, (y+b+10)/2);
}
}
/*void f(){
double angle0,angle1,angle2,k1,k2;
//k0=(b-y)/(a-x);
angle0=Math.atan2(y-b, a-x)*180/Math.PI;
angle1=angle0+20;
angle2=angle1-20;
k1=Math.tan(angle1);
double k;
k=(b-y)/(a-x);
}*/
/* public void update(Graphics g){
//g.clearRect(x, y, width, height);
paint(g);
}*/
//如何画箭头：1 得到斜线的斜率 2 得到该斜线的角度 3得到箭头两条线的角度
//假设是20 4得到两条线角度tan植 5 得到两个点
//能画箭头就可以得到有向图
}
算法类：Floyd
package LI;
import java.util.Vector;
class Floyd { Vector<Node> node=null;
Vector<Edge> edge=null;
Vector<Integer> pn=null;
int distance=0,number=0,source,destination;
String lujing="";
int A[][],path[][];
boolean bool=false;
Floyd(Vector<Node> n,Vector<Edge> ed,int sour,int dest){ //构造函数将两个向量类变成邻接矩阵
node=n;
edge=ed;
source=sour;
pn=new Vector<Integer>();
destination=dest;
number=node.size();
A=new int[number][number];
path=new int[number][number];
for(int i=0;i<number;i++){
for(int j=0;j<number;j++){
if(i==j)
A[i][j]=0;
else
A[i][j]=10000;
path[i][j]=-1;
}
}
for(int i=0;i<edge.size();i++){
Edge e=edge.elementAt(i);
int s=e.getSource();
int d=e.getDestination();
int dis=e.getDistance();
A[s][d]=dis;
A[d][s]=dis;
}
}
public int getDistance(){
if(bool){}
else
f();
return distance;
}
public String getLJ(){
f();
bool=true;
return lujing;
}
public void f(){//根据path得到最短路径的字符串值
int i,j,k;
for(k=0;k<number;k++)
for(i=0;i<number;i++)
for(j=0;j<number;j++)
if(A[i][j]>A[i][k]+A[k][j]){
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
pn.add(new Integer(source));
Ppath(path,source,destination);
pn.add(new Integer(destination));
for(int m=0;m<pn.size()-1;m++){
int node1=pn.elementAt(m).intValue();
int node2=pn.elementAt(m+1).intValue();
distance=distance+A[node1][node2];
String name=node.elementAt(node1).getName();
lujing=lujing+name+"-->";
}
lujing=lujing+node.elementAt(destination).getName();
}
public void Ppath(int p[][],int i,int j){//根据Floyd算法思想进行运算
int k;
k=path[i][j];
if(k==-1)
return;
Ppath(p,i,k);
pn.add(new Integer(k));
Ppath(path,k,j);
}
}
参考文献[gaoyuan1]
[1]耿祥义、张跃平 《java2实用教程》 清华大学出版社
[gaoyuan1]参考文献必须写