第11章 常見數(shù)據(jù)結(jié)構(gòu)及算法分析【1】設(shè)有一數(shù)列：a1=3，a2=8，an=2an-1+2an-2，使用堆棧結(jié)構(gòu)輸出an的若干項(xiàng)。解答：代碼如下，運(yùn)行程序時(shí)需要輸入一個(gè)參數(shù)，指出想要輸出數(shù)列的前多少項(xiàng)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 = 0 ; i-) System.out.print(st.pop() + ); wanghang+; if(wanghang % 5 = 0) System.out.println(n); 輸入13時(shí)的運(yùn)行結(jié)果如下：【2】編寫一程序，用哈希表實(shí)現(xiàn)學(xué)生成績單的存儲(chǔ)與查詢。解答：學(xué)生類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) = name; public Integer getScore() return score; public void setScore(Integer score) this.score = score; public String toString() return 學(xué)號(hào)： + 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(學(xué)生成績管理); ht = new Hashtable(); lblsearchbyidorname = new JLabel(學(xué)號(hào)：); txfidorname = new JTextField(20); lblno = new JLabel(學(xué)號(hào)); lblname = new JLabel(姓名); lblscore = new JLabel(分?jǐn)?shù)); 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(學(xué)號(hào)); 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,查詢結(jié)果如下：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,你沒有選擇學(xué)生！); else String no = (String)reader.getValueAt(index,0); Student stu = (Student)ht.remove(no); JOptionPane.showMessageDialog(null,學(xué)生成績刪除！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(); 運(yùn)行效果如下：查找：【3】（走迷宮）下列由符號(hào)和點(diǎn)組成的圖形代表一個(gè)迷宮，用一個(gè)雙下標(biāo)數(shù)組存放。其中，代表迷宮的墻，點(diǎn)代表路徑，只有數(shù)組中含有點(diǎn)的地方才能走。解答：對(duì)于用如下二維數(shù)組表示的迷宮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為了簡化算法，假設(shè)入口是（0，2），出口是（7，3），程序如下：類Position用來描述點(diǎn)在數(shù)組中的位置和該點(diǎn)旁邊四個(gè)點(diǎn)是否可以通過的狀態(tài)，程序如下：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)