Java課程設(shè)計-連通問題

第1章課題概述本次Java課程設(shè)計的題目是求解一個bmp格式圖片中像素點互相連通的面積。1.1課題的目的連通問題在日常生活中非常常見，比如說互聯(lián)網(wǎng)絡(luò)、每個城市的道路連通都屬于連通相關(guān)的問題，在本次課設(shè)中是求解一個bmp格式圖片中像素點之間的連通，可以通過本程序來，采用數(shù)據(jù)結(jié)構(gòu)中圖的知識可以高效率直接計算出圖片中連通分量的數(shù)量和每一個連通分量的面積，這樣比人為判斷連通問題更加簡單、快捷。1.2課題的要求1.2.1文件格式的概述BMP文件格式，又稱為Bitmap（位圖）或是DIB(Device-Independent

Device，設(shè)備無關(guān)位圖)，是Windows系統(tǒng)中廣泛使用的圖像文件格式。由于它可以不作任何變換地保存圖像像素域的數(shù)據(jù)，因此成為我們?nèi)〉肦AW數(shù)據(jù)的重要來源。Windows的圖形用戶界面（graphical

user

interfaces）也在它的內(nèi)建圖像子系統(tǒng)GDI中對BMP格式提供了支持。

下面以UltraEdit為分析工具，用16進制打開bmp格式圖片，其內(nèi)容信息如下所示:圖1-1Bmp格式詳解圖1.2.2程序?qū)崿F(xiàn)的功能要求程序的目標是：根據(jù)給定的黑白位圖，分析出所有獨立連通的群體，輸出每個連通群體的面積。所謂面積，就是它含有的像素的個數(shù)。第2章課設(shè)概要2.1程序運行流程根據(jù)課設(shè)的題目的要求，要實現(xiàn)bmp圖片中像素點連通的數(shù)量和每個連通分量的面積，程序只需要選擇本地的一張圖片，不需要進行程序的輸入和輸出。圖2-1整個程序各功能模塊間的流程2.2bmp格式圖片數(shù)據(jù)的存儲結(jié)構(gòu)in.bmp文件如下：t1.bmp文件如下：BMP是常見的圖像存儲格式。如果用來存黑白圖像（顏色深度=1），則其信息比較容易讀取。與之相關(guān)的數(shù)據(jù)：（以下偏移均是從文件頭開始）偏移：10字節(jié),長度4字節(jié)：圖像數(shù)據(jù)真正開始的位置。偏移：18字節(jié),長度4字節(jié)：位圖的寬度，單位是像素。偏移：22字節(jié),長度4字節(jié)：位圖的高度，單位是像素。從圖像數(shù)據(jù)開始處，每個像素用1個二進制位表示。從圖片的底行開始，一行一行向上存儲。Windows規(guī)定圖像文件中一個掃描行所占的字節(jié)數(shù)必須是4字節(jié)的倍數(shù)，不足的位均以0填充。例如，圖片寬度為45像素，實際上每行會占用8個字節(jié)?？梢酝ㄟ^Windows自帶的畫圖工具生成和編輯二進制圖像。需要在“屬性”中選擇“黑白”，指定為二值圖像?？赡苄枰ㄟ^查看|縮放|自定義...把圖像變大比例一些，更易于操作。圖像的左下角為圖像數(shù)據(jù)的開始位置。白色對應(yīng)1，黑色對應(yīng)0我們可以定義：兩個點距離如果小于2個像素，則認為這兩個點連通。也就是說：以一個點為中心的九宮格中，圍繞它的8個點與它都是連通的。如：t1.bmp所示，左下角的點組成一個連通的群體；而右上角的點都是孤立的。2.3圖片選擇的合法性判斷Bmp格式圖片Windows系統(tǒng)最基本的圖片信息存儲格式，格式文件用固定的格式來存儲每一張圖片的信息，只有選擇了正確圖片，才能保證IO流對文件的正確讀寫，保證程序不會崩潰。如果用戶選擇一個不是bmp格式的文件，在讀取文件信息的就會出現(xiàn)相應(yīng)的異常，可以針對這種異常進行判斷程序格式圖片選擇是否合法。2.4各個操作算法的描述2.4.1遞歸算法在定義一個過程或函數(shù)時出現(xiàn)調(diào)用本過程或本函數(shù)的成分,稱之為遞歸[1]。若調(diào)用自身,稱之為直接遞歸。若過程或函數(shù)p調(diào)用過程或函數(shù)q,而q又調(diào)用p,稱之為間接遞歸。如果一個遞歸過程或遞歸函數(shù)中遞歸調(diào)用語句是最后一條執(zhí)行語句,則稱這種遞歸調(diào)用為尾遞歸。圖2-1遞歸算法示意圖2.4.2圖的深度優(yōu)先遍歷算法圖的深度優(yōu)先遍歷[2]是連通圖的一種遍歷策略。其基本思想如下：設(shè)x是當前被訪問頂點，在對x做過訪問標記后，選擇一條從x出發(fā)的未檢測過的邊(x，y)。若發(fā)現(xiàn)頂點y已訪問過，則重新選擇另一條從x出發(fā)的未檢測過的邊，否則沿邊(x，y)到達未曾訪問過的y，對y訪問并將其標記為已訪問過；然后從y開始搜索，直到搜索完從y出發(fā)的所有路徑，即訪問完所有從y出發(fā)可達的頂點之后，才回溯到頂點x，并且再選擇一條從x出發(fā)的未檢測過的邊。上述過程直至從x出發(fā)的所有邊都已檢測過為止。圖的深度優(yōu)先遍歷示意圖如下：圖2-1圖的深度優(yōu)先搜索示意圖第3章程序圖形界面的設(shè)計3.1主窗體的設(shè)計3.2.1主窗體的布局和設(shè)計程序的主窗體是一個JFrame頂級窗體，采用的是邊界布局管理器（BorderLayout）,為主窗體定義一個靜態(tài)的桌面面板組件，用于存放所有的內(nèi)部窗體，將其至于主窗體邊界布局的中心部位，然后定義一個標簽組件，設(shè)置內(nèi)容為圖片，將其置于桌面面板的最底部，顯示主窗體的主界面圖片。圖3-1程序主界面設(shè)計主窗體的代碼展示/** * */ privatestaticfinallongserialVersionUID=1L;//版本號 publicstaticJDesktopPaneDESKTOP_PANE=newJDesktopPane();//創(chuàng)建桌面面板 JMenuItemconnetion_item,exit_item,help_item,exit_system;//聲明菜單項 publicstaticMap<String,JInternalFrame>map=newHashMap<String,JInternalFrame>();//創(chuàng)建集合，用來保存的所有的內(nèi)部窗格 MainJFrame(){ Containerc=this.getContentPane(); setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); setSize(780,600); ImageIconicon=CreateIcon.getIcon("image.jpg"); if(icon.getIconWidth()==-1){//當沒有讀取到圖片的時候 JOptionPane.showMessageDialog(this, "圖片加載失敗,頭圖像設(shè)置失敗!\n請將images文件夾放置至D盤下再重新運行!"); System.exit(-1); }else this.setIconImage(icon.getImage()); //在屏幕中間顯示頂級窗體 Toolkittoolkit=Toolkit.getDefaultToolkit(); DimensionscreenSize=toolkit.getScreenSize(); intx=(screenSize.width-getSize().width)/2; inty=(screenSize.height-getSize().height)/2; setLocation(x,y); setResizable(false);//設(shè)置窗口不可改變大小 setTitle("連通問題"); JMenuBarjmb=null; jmb=createJMenuBar(); setJMenuBar(jmb);//設(shè)置菜單欄 //設(shè)置背景圖片標簽 JLabellabel=newJLabel(); icon=CreateIcon.getIcon("back.jpg"); if(icon.getIconWidth()==-1){ JOptionPane.showMessageDialog(this,"背景圖片加載失敗,窗體打開失敗!"); System.exit(-1); }else{ label.setBounds(0,0,icon.getIconWidth(),icon.getIconHeight()); label.setIcon(icon); } //向面板中添加組件 DESKTOP_PANE.add(label,newInteger(Integer.MIN_VALUE)); c.add(DESKTOP_PANE,BorderLayout.CENTER); setVisible(true);//設(shè)置窗體可見 } /** *創(chuàng)建菜單欄 * *@return菜單欄 */ privateJMenuBarcreateJMenuBar(){ JMenuBarmenuBar=newJMenuBar(); JMenuopen=newJMenu(); open.setIcon(CreateIcon.getIcon("open.jpg"));//打開 connetion_item=newJMenuItem(); connetion_item.setIcon(CreateIcon.getIcon("connection.jpg")); connetion_item.addActionListener(this); open.add(connetion_item); exit_item=newJMenuItem(); exit_item.setIcon(CreateIcon.getIcon("exists.jpg")); exit_item.addActionListener(this); open.addSeparator(); open.add(exit_item); menuBar.add(open); JMenuhelp=newJMenu(); help.setIcon(CreateIcon.getIcon("help.jpg"));//幫助 help_item=newJMenuItem(); help_item.setIcon(CreateIcon.getIcon("Instructions.jpg")); help_item.addActionListener(this); help.add(help_item); menuBar.add(help); JMenuexit=newJMenu(); exit.setIcon(CreateIcon.getIcon("exist.jpg"));//退出 exit_system=newJMenuItem(); exit_system.setIcon(CreateIcon.getIcon("exists.jpg")); exit_system.addActionListener(this); exit.add(exit_system); menuBar.add(exit); returnmenuBar; }3.2內(nèi)部窗體的設(shè)計3.2.1連通求解窗體的設(shè)計連通問題求解窗體是一個內(nèi)部窗體，是鑲嵌在主窗體的內(nèi)部，其采用邊界布局管理器（BorderLayout）,北部添加一個圖片標簽；南部添加一個面板，面板設(shè)置成流布局管理器，右對齊，再在面板中添加確定和取消按鈕，并加堅監(jiān)聽效果；中部添加一個面板，設(shè)置成流布局，在中部面板中添加文本面板和相應(yīng)的標簽和文本框。最后選擇圖片后，在文本面板中顯示連通詳細。圖3-2連通求解窗體設(shè)計連通求解內(nèi)部窗體的代碼展示/** * */ privatestaticfinallongserialVersionUID=1L; JTextFieldfileName,result; JTextPanetextPane; JButtonconfirm,cancel,openFile; publicConnectionFrame(){ Containerc=this.getContentPane(); c.setLayout(newBorderLayout()); setIconifiable(true);//設(shè)置窗體可最小化 setResizable(false);//設(shè)置窗體不可改變大小 setClosable(true);//設(shè)置窗體可關(guān)閉 setTitle("連通問題");//設(shè)置窗體標題 setBounds(100,10,600,500);//設(shè)置窗體位置和大小 Iconicon=CreateIcon.getIcon("headLabel.jpg"); if(icon.getIconWidth()==-1) JOptionPane.showMessageDialog(this,"圖片丟失,圖標設(shè)置失敗!"); else setFrameIcon(icon); //北部面板 JPanelnorthPane=newJPanel(); northPane.setBorder(newEtchedBorder()); JLabell1=newJLabel(); icon=CreateIcon.getIcon("bb.jpg"); if(icon.getIconWidth()==-1) JOptionPane.showMessageDialog(this,"圖片丟失,請先添加圖片再重新啟動!"); else l1.setIcon(icon); northPane.add(l1); //中間面板 JPanelcenterPane=newJPanel(); centerPane.setBorder(newTitledBorder("連通圖片")); centerPane.setLayout(newFlowLayout(FlowLayout.CENTER)); textPane=newJTextPane(); textPane.setCaretColor(Color.BLUE); textPane.setSelectedTextColor(Color.RED); textPane.setEditable(false); textPane.setPreferredSize(newDimension(500,250)); JScrollPanejsp=newJScrollPane(textPane); jsp.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS);//始終顯示滾動條 openFile=newJButton(); openFile.addActionListener(this); openFile.setIcon(CreateIcon.getIcon("openFile.jpg")); openFile.setPreferredSize(newDimension(77,29));//設(shè)定指定組件的大小 JLabeljl1=newJLabel("文件:"); fileName=newJTextField(10); fileName.setFont(newFont("宋體",Font.BOLD,18)); JLabeljl2=newJLabel("連通結(jié)果:"); result=newJTextField(18); result.setFont(newFont("宋體",Font.BOLD,16)); result.setEditable(false); JPaneljp4=newJPanel(); jp4.setLayout(newFlowLayout(FlowLayout.RIGHT,20,10)); jp4.add(jl1); jp4.add(fileName); jp4.add(openFile); jp4.add(jl2); jp4.add(result); centerPane.add(jsp); centerPane.add(jp4); //南部面板 JPanelsouthPanel=newJPanel(); southPanel.setBorder(newEtchedBorder()); southPanel.setLayout(newFlowLayout(FlowLayout.RIGHT,60,5)); confirm=newJButton(); confirm.addActionListener(this); confirm.setPreferredSize(newDimension(65,34)); confirm.setIcon(CreateIcon.getIcon("confirm.jpg")); cancel=newJButton(); cancel.addActionListener(this); cancel.setPreferredSize(newDimension(65,34)); cancel.setIcon(CreateIcon.getIcon("cancel.jpg")); southPanel.add(confirm); southPanel.add(cancel); //將各個面便添加到容器中 c.add(northPane,BorderLayout.NORTH); c.add(centerPane,BorderLayout.CENTER); c.add(southPanel,BorderLayout.SOUTH); setVisible(true); }3.2.2使用說明窗體設(shè)計使用說明窗體為內(nèi)部窗體，采用邊界布局管理器，在中部添加一個滾動面板，在面板中添加一個使用圖片標簽，并設(shè)置內(nèi)部窗體為可最小化，可關(guān)閉屬性。圖3-3使用說明窗體設(shè)計使用說明窗體代碼展示/** * */ privatestaticfinallongserialVersionUID=1L; publicUseInstructions(){ Containerc=this.getContentPane(); c.setLayout(newBorderLayout()); setIconifiable(true);//設(shè)置窗體可最小化 setClosable(true);//設(shè)置窗體可關(guān)閉 setTitle("使用說明");//設(shè)置窗體標題 setBounds(60,10,650,500);//設(shè)置窗體位置和大小 Iconicon=CreateIcon.getIcon("headLabel.jpg"); if(icon.getIconWidth()==-1) JOptionPane.showMessageDialog(this,"圖片加載失敗!頭標簽設(shè)置失敗!"); else setFrameIcon(icon); //設(shè)置中間面板 JPanelcenter=newJPanel(); center.setBorder(newEtchedBorder());//設(shè)置邊框 JLabellabel=newJLabel(); icon=CreateIcon.getIcon("useInstructions.jpg"); if(icon.getIconWidth()==-1) JOptionPane.showMessageDialog(this,"圖片加載失敗!"); else label.setIcon(icon); JScrollPanescrollPane=newJScrollPane(label); c.add(scrollPane); setVisible(true); }第4章程序功能的實現(xiàn)4.1bmp格式文件的讀取4.2.1bmp圖片分辨率的讀取偏移：18字節(jié),長度4字節(jié)：位圖的寬度，單位是像素。偏移：22字節(jié),長度4字節(jié)：位圖的高度，單位是像素。創(chuàng)建Java隨機讀取文件流，從文件頭開始跳過18個字節(jié)，開始讀取解析文件的大小，將讀取出來的信息存放在一個二維數(shù)組中:RandomAccessFilera=newRandomAccessFile(file,"r"); ra.seek(18); byteb[]=newbyte[8];//儲存八個字節(jié)大小的圖片的寬度和高度 for(inti=0;i<b.length;i++){ b[i]=ra.readByte(); }在bmp格式圖片存儲文件中，存儲圖片寬度或高度有4byte,前一個字節(jié)為低位，而最后一個字節(jié)為高位，因此要用位運算符進行解析數(shù)據(jù)，如圖:圖4-1圖片大小存儲格式解析圖高度和寬度的計算://讀取圖片的寬度和高度 width=(int)((b[0]&0xFF)|((b[1])<<8&0xFF00) |((b[2]<<16)&0xFF0000)|((b[3]<<24)&0xFF000000)); height=(int)((b[4]&0xFF)|((b[5])<<8&0xFF00) |((b[6]<<16)&0xFF0000)|((b[7]<<24)&0xFF000000)); point=newint[height][width];4.2.2bmp圖片連通信息的讀取要獲取連通信息，必須將讀取的信息保存起來，這里定義一個二維數(shù)組用來保存圖片信息，即每一個像素點的信息（0或1），所以二維數(shù)組的行數(shù)為圖片的高度，列數(shù)為圖片的寬度。publicstaticint[][]point;//鄰接矩陣存儲二維數(shù)組，存儲文件信息point=newint[height][width];Windows規(guī)定圖像文件中一個掃描行所占的字節(jié)數(shù)必須是4字節(jié)的倍數(shù)，不足的位均以0填充，因此必須先確定每一行的字節(jié)數(shù)，保證其字節(jié)數(shù)為4的倍數(shù)。//計算出每行所需的最少字節(jié)數(shù),保證每行的字節(jié)數(shù)是4的倍數(shù) intwByteNum=(width%8==0)?(width/8):(width/8+1);//字節(jié)數(shù) if(wByteNum%4!=0){ wByteNum=(wByteNum/4+1)*4;//將每一行的字節(jié)數(shù)變成4字節(jié)的倍數(shù) }從圖像數(shù)據(jù)開始處，每個像素用1個二進制位表示。所以每次從文件中讀取一個字節(jié)，讀取出來的是一個整數(shù)，用Java內(nèi)庫的方法將該整數(shù)轉(zhuǎn)換成一個String型的二進制數(shù)，但是這個二進制數(shù)可能長度超過8，也可能小于8，因此要用字符串變量對其字符串進行處理，長度大于8時截取字符串的后8個字符，當長度小于8時，對其前面補0處理，最后將字符串型的二進制串解析成整數(shù)存在二位數(shù)組中，最后通過判斷二位數(shù)組的信息來判斷連通信息。StringBuffersb; for(inti=0;i<height;i++){ for(intp=0,j=0;p<wByteNum;p++){ sb=newStringBuffer(Integer.toBinaryString(ra.readByte())); //當二進位字符串長度大于8，截取低8位 if(sb.length()>8){ sb.delete(0,sb.length()-8); } //當二進位字符串長度小于8，前面補0直至二進制位為8位 while(sb.length()<8){ sb.insert(0,0); } //將二進制字符串轉(zhuǎn)換成整數(shù)，存到二維數(shù)組中 for(intch=0;ch<sb.length()&&j<width;ch++){ point[i][j++]=Integer.parseInt(sb.charAt(ch)+""); } } }4.2連通求解功能的實現(xiàn)用Windows系統(tǒng)的中畫圖軟件打開bmp格式文件，將其放大，可以看到圖片中每一個像素點的信息，它對應(yīng)著二位數(shù)組中的數(shù)值，即每一個黑色像素點代表二位數(shù)組值為0的單元，反之白色代表數(shù)值1的單元，可以通過判斷二位數(shù)組中的值的信息來判斷像素點之間的連通情況。圖4-2bmp圖片像素點信息判斷像素點之間連通情況，必須用數(shù)據(jù)結(jié)構(gòu)中的遞歸算法和圖的深度優(yōu)先遍歷算法，這里可以將所有黑點看作是一個數(shù)據(jù)結(jié)構(gòu)中的圖，每一個黑點代表圖中的一個頂點，從二維數(shù)組的0行0列開始遍歷，另外定義一個布爾型的二維數(shù)組，標記每一個定點是否被訪問過，當該定點被訪問過，將其值設(shè)為true,否則為false,避免程序下一次再重新訪問。當訪問到下一個沒有被訪問的頂點時，遞歸調(diào)用該方法訪問該點周圍的8個定點，當周圍的頂點已被訪問過就不訪問，直到該連通分量的每一個點都被訪問且周圍8個定點都為白色像素點，即該連通分量結(jié)束，繼續(xù)訪問下一個連通分量。當二維數(shù)組中的每一點都被訪問過了，整個圖的遍歷就結(jié)束。//訪問二維數(shù)組，判斷是否連通 for(intx=point.length-1;x>=0;x--){ for(inty=0;y<point[x].length;y++){ result=0; resultList.add(0); scanner(x,y);//掃描當前點 if(result==0){ resultList.remove(resultList.size()-1); } } } ra.close();//關(guān)閉流,釋放資源 } /** *掃描每一個點的周圍點 * *@paramx *@paramy */ publicvoidscanner(intx,inty){ if(x<0||x>=height||y<0||y>=width){ return; } if(!visited[x][y]){ visited[x][y]=true; resultList.set(resultList.size()-1,result); if(point[x][y]==0){ result++; //遞歸調(diào)用,分別判斷該點與周圍八個點是否于當前點連通 scanner(x-1,y); scanner(x-1,y-1); scanner(x-1,y+1); scanner(x+1,y); scanner(x+1,y-1); scanner(x+1,y+1); scanner(x,y-1); scanner(x,y+1); } } }}第5章程序的調(diào)試和問題的解決在進行課程設(shè)計的過程中，遇到了很多的Bug，最后通過網(wǎng)上查閱資料和在老師的指導(dǎo)下，終于解決了所有的錯誤，其出現(xiàn)的問題及解決辦法如下所示:1.在進行圖片大小的讀取的過程中，為什么讀到的寬度和高度為負數(shù)？解決辦法:當時讀取圖片寬度和高度的時候，只讀取了最低位的一個字節(jié)，8bit，剛好該字節(jié)的最高位為1，此時程序把第一位當作了符號位，結(jié)果讀出來的就是一個負數(shù)；最后將存儲寬度的4個字節(jié)全部讀取到一個字節(jié)數(shù)組中，進行移位運算，最后得到正確的答案。2.在程序運行過程之中，二位數(shù)組的連通信息和像素點的信息已經(jīng)保持一致，但是判斷連通分量和面積的時候為什么判斷出來的面積錯誤呢?解決辦法:當掃描二位數(shù)組中的數(shù)據(jù)時候，正常情況下掃描到圖片的尾端就不進行掃描了，但是由于程序中沒有進行終止，導(dǎo)致程序又進行錯誤的掃描，最后導(dǎo)致結(jié)果錯誤。 if(x<0||x>=height||y<0||y>=width){ return; }第6章程序測試及分析運行程序，首先顯示的是程序主界面，可以進行功能的選擇，即連通求解、使用說明、退出程序。圖6-1程序運行主窗體主窗體顯示出來之后，打開連通求解內(nèi)部窗體，選擇正確的bmp格式圖片，求解圖片中連通信息，這里選擇課設(shè)要求進行測試連通