常见数据结构及算法分析

第11章 常见数据结构及算法分析【1】设有一数列：a1=3，a2=8，an=2an-1+2an-2，使用堆栈结构输出an的若干项。解答：代码如下，运行程序时需要输入一个参数，指出想要输出数列的前多少项import java.util.Stack;public class StackShow public static void main(String args) Stack st = new Stack(); int count = Integer.valueOf(args0).intValue(); int temp; Integer first = new Integer(3); Integer second = new Integer(8); st.add(first); st.add(second); for (int i = 0; i < count - 2; i+) temp = first.intValue() + second.intValue(); st.add(new Integer(temp); first = second; second = new Integer(temp); System.out.println("输出这个系列的前" + count + "个数："); Object result = st.toArray(); int wanghang = 0; for (int i = result.length - 1; i >= 0 ; i-) System.out.print(st.pop() + " "); wanghang+; if(wanghang % 5 = 0) System.out.println("n"); 输入13时的运行结果如下：【2】编写一程序，用哈希表实现学生成绩单的存储与查询。解答：学生类Student，代码如下：class Student private String no; private String name; private Integer score; public String getNo() return no; public void setNo(String no) this.no = no; public String getName() return name; public void setName(String name) this.name = name; public Integer getScore() return score; public void setScore(Integer score) this.score = score; public String toString() return "学号：" + no + " 姓名：" + name + " 成绩：" + score; 主类HashTest，代码如下：import javax.swing.*;import java.util.Vector;import java.util.Hashtable;import java.awt.*;import java.awt.event.ActionListener;import java.awt.event.ActionEvent;public class HashTest extends JFrame JLabel lblsearchbyidorname; JTextField txfidorname; JButton btnsearchbyidorname; JTable reader; JButton btnadd; JButton btndelete; Hashtable ht; Vector colnames; JLabel lblno; JLabel lblname; JLabel lblscore; JTextField addno; JTextField addname; JTextField addscore; Vector data; public HashTest() throws HeadlessException super("学生成绩管理"); ht = new Hashtable(); lblsearchbyidorname = new JLabel("学号："); txfidorname = new JTextField(20); lblno = new JLabel("学号"); lblname = new JLabel("姓名"); lblscore = new JLabel("分数"); addno = new JTextField(10); addname = new JTextField(12); addscore = new JTextField(10); btnsearchbyidorname = new JButton("查找->"); btnadd = new JButton("新增"); btndelete = new JButton("删除"); colnames = new Vector(); colnames.add("学号"); colnames.add("姓名"); colnames.add("成绩"); data = new Vector(); reader = new JTable(new ReaderTableModel(data,colnames); reader.setPreferredSize(new Dimension(700,260); JPanel pnlsearch = new JPanel(); pnlsearch.add(lblsearchbyidorname); pnlsearch.add(txfidorname); pnlsearch.add(btnsearchbyidorname); pnlsearch.add(btndelete); JScrollPane scptable = new JScrollPane(reader, ScrollPaneConstants.VERTICAL_SCROLLBAR_AS_NEEDED, ScrollPaneConstants.HORIZONTAL_SCROLLBAR_ALWAYS); JPanel pnladd = new JPanel(); pnladd.add(lblno); pnladd.add(addno); pnladd.add(lblname); pnladd.add(addname); pnladd.add(lblscore); pnladd.add(addscore); pnladd.add(btnadd); reader.setSelectionMode(ListSelectionModel.SINGLE_SELECTION); ScoreHandler sh = new ScoreHandler(); btnadd.addActionListener(sh); btndelete.addActionListener(sh); btnsearchbyidorname.addActionListener(sh); Container c = getContentPane(); c.add(pnlsearch,BorderLayout.NORTH); c.add(scptable,BorderLayout.CENTER); c.add(pnladd,BorderLayout.SOUTH); setSize(600,400); setVisible(true); public static void main(String args) new HashTest(); class ScoreHandler implements ActionListener public void actionPerformed(ActionEvent e) JButton btn = (JButton)e.getSource(); if(btn = btnsearchbyidorname) Object obj = ht.get(txfidorname.getText().trim(); if(obj = null) JOptionPane.showMessageDialog(null,"没有找到！"); else JOptionPane.showMessageDialog(null,"查询结果如下：n" + obj.toString(); else if(btn = btnadd) Student stu = new Student(); stu.setName(addname.getText().trim(); stu.setNo(addno.getText().trim(); stu.setScore(Integer.valueOf(addscore.getText().trim(); ht.put(stu.getNo(),stu); addDataToTable(stu); addname.setText(""); addno.setText(""); addscore.setText(""); else if(btn = btndelete) int index = reader.getSelectedRow(); if (index = -1) JOptionPane.showMessageDialog(null,"你没有选择学生！"); else String no = (String)reader.getValueAt(index,0); Student stu = (Student)ht.remove(no); JOptionPane.showMessageDialog(null,"学生成绩删除！n" + stu.toString(); data.remove(index); reader.repaint(); public void addDataToTable(Student stu) Vector temp = new Vector(); temp.add(stu.getNo(); temp.add(stu.getName(); temp.add(stu.getScore(); data.add(temp); reader.repaint(); 运行效果如下：查找：【3】（走迷宫）下列由符号和点组成的图形代表一个迷宫，用一个双下标数组存放。其中，代表迷宫的墙，点代表路径，只有数组中含有点的地方才能走。解答：对于用如下二维数组表示的迷宫1,1,0,1,1,1,1,1, 1,0,0,1,0,0,0,1, 1,1,0,0,0,1,1,1, 1,0,0,1,0,0,0,1, 1,1,1,1,0,1,1,1, 1,0,0,0,0,0,0,1, 1,0,1,0,1,0,0,1, 1,1,1,0,1,1,1,1为了简化算法，假设入口是（0，2），出口是（7，3），程序如下：类Position用来描述点在数组中的位置和该点旁边四个点是否可以通过的状态，程序如下：class Position private int px; private int py; private boolean forwardFlag; private boolean backFlag; private boolean leftFlag; private boolean rightFlag; public Position(int px,int py,int allData) this.px = px; this.py = py; int row = allData.length; int col = allData0.length; int forward = px + 1; int back = px - 1; int left = py + 1; int right = py - 1; if(forward = row | allDataforwardpy = 1) forwardFlag = false; else forwardFlag = true; if(back = -1 | allDatabackpy = 1) backFlag = false; else backFlag = true; if(left = col | allDatapxleft = 1) leftFlag = false; else leftFlag = true; if(right = -1 | allDatapxright = 1) rightFlag = false; else rightFlag = true; public boolean isForwardFlag() return forwardFlag; public void setForwardFlag(boolean forwardFlag) this.forwardFlag = forwardFlag; public boolean isBackFlag() return backFlag; public void setBackFlag(boolean backFlag) this.backFlag = backFlag; public boolean isLeftFlag() return leftFlag; public void setLeftFlag(boolean leftFlag) this.leftFlag = leftFlag; public boolean isRightFlag() return rightFlag; public void setRightFlag(boolean rightFlag) this.rightFlag = rightFlag; public int getPx() return px; public void setPx(int px) this.px = px; public int getPy() return py; public void setPy(int py) this.py = py; public String toString() return "(" + px + "," + py + ")" 主类：import java.util.Stack;import java.util.Enumeration;import java.util.Iterator;public class PassMaze int maze = 1,1,0,1,1,1,1,1, 1,0,0,1,0,0,0,1, 1,1,0,0,0,1,1,1, 1,0,0,1,0,0,0,1, 1,1,1,1,0,1,1,1, 1,0,0,0,0,0,0,1, 1,0,1,0,1,0,0,1, 1,1,1,0,1,1,1,1; private Stack st; public PassMaze() direct = new Stack(); st = new Stack(); Position current = new Position(0,2,maze); st.push(current); while(!isSuccessful(current) boolean status = calPassWay(current); if(!status) st.pop(); if(st.empty() break; setFlag(Position)st.peek(),(String)direct.pop(); current = (Position)st.peek(); if(st.empty() System.out.println("迷宫没有出路！"); else System.out.println("迷宫的出路如下："); Iterator it = st.iterator(); while(it.hasNext() System.out.println(it.next().toString(); private boolean calPassWay(Position pos) boolean result = false; if(pos.isBackFlag() Position temp = new Position(pos.getPx() - 1,pos.getPy(),maze); temp.setForwardFlag(false); if(contains(temp) pos.setBackFlag(false); else st.push(temp); direct.push("Back"); result = true; else if(pos.isForwardFlag() Position temp = new Position(pos.getPx() + 1,pos.getPy(),maze); temp.setBackFlag(false); if(contains(temp) pos.setForwardFlag(false); else st.push(temp); direct.push("Forward"); result = true; else if(pos.isLeftFlag() Position temp = new Position(pos.getPx(),pos.getPy() + 1,maze); temp.setRightFlag(false); if(contains(temp) pos.setLeftFlag(false); else st.push(temp); direct.push("Left"); result = true; else if(pos.isRightFlag() Position temp = new Position(pos.getPx(),pos.getPy() - 1,maze); temp.setLeftFlag(false); if(contains(temp) pos.setRightFlag(false); else st.push(temp); direct.push("Right"); result = true; return result; private boolean contains(Position p) boolean result = false; Iterator it = st.iterator(); while(it.hasNext() Position temp = (Position)it.next(); if(p.getPx() = temp.getPx() && p.getPy() = temp.getPy() result = true; break; return result; private void setFlag(Position current,String dirction) if("Back".equals(dirction) current.setBackFlag(false); else if("Forward".equals(dirction) current.setForwardFlag(false); else if("Left".equals(dirction) current.setLeftFlag(false); else if("Right".equals(dirction) current.setRightFlag(false); private boolean isSuccessful(Position pt) return pt.getPx() = 7 && pt.getPy() = 3; public static void main(String args) new PassMaze(); 11