《《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告線性表進(jìn)行算式計(jì)算、排課問題,JAVA語言,截圖完整》由會(huì)員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告線性表進(jìn)行算式計(jì)算、排課問題,JAVA語言,截圖完整（48頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、中南大學(xué) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào) 告 指導(dǎo)教師 學(xué) 院 信息科學(xué)與工程學(xué)院 完成時(shí)間 2010 年 7 月 7 日 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 2 - 目 錄 目 錄 .- 2 - 題目一：利用線性表進(jìn)行算式計(jì)算 .- 1 - 一、實(shí)驗(yàn)名稱： .- 1 - 二、需求分析： .- 1 - 三、概要設(shè)計(jì) .- 1 - 四、詳細(xì)設(shè)計(jì) .- 3 - 五、調(diào)試分析 .- 5 - 六、測(cè)試結(jié)果 .- 5 - 七、課程設(shè)計(jì)總結(jié) .- 7 - 八、參考文獻(xiàn) .- 8 - 九、附錄 .- 9 - 題目三：排課問題 .- 21 - 一、實(shí)驗(yàn)名稱： .- 21 - 二、需求分析： .- 21 - 三、概

2、要設(shè)計(jì) .- 21 - 四、詳細(xì)設(shè)計(jì) .- 24 - 五、調(diào)試分析 .- 33 - 六、測(cè)試結(jié)果 .- 33 - 七、課程設(shè)計(jì)總結(jié) .- 34 - 八、參考文獻(xiàn) .- 35 - 九、附錄 .- 35 - 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 1 - 題目一：利用線性表進(jìn)行算式計(jì)算 一、實(shí)驗(yàn)名稱： 利用線性表進(jìn)行算式計(jì)算 二、需求分析： 設(shè)計(jì)任務(wù)： 界面上出現(xiàn)一個(gè)文本框，輸入一個(gè)算式，點(diǎn)擊按鈕，顯示結(jié)果。該算式內(nèi) 只含有數(shù)字、括號(hào)、+、-、*、/、%這幾種字符，優(yōu)先級(jí)為：括號(hào)-%-*,/- +,-。如輸入：2+3*5，結(jié)果為 17,輸入(2+3)*5 結(jié)果為 25。輸入格式有誤，需 要給予

3、提示。在算法中，必須實(shí)現(xiàn)對(duì)輸入的算式字符串的分析，而不僅僅是得 到結(jié)果。 (1)輸入的形式和輸入值的范圍：數(shù)字和運(yùn)算符（只含有括號(hào)、+、-、*、/、%） 。 (2)輸出的形式：以數(shù)字和運(yùn)算符組成的算式形式輸出。 (3)程序所能達(dá)到的功能：對(duì)輸入數(shù)字和運(yùn)算符進(jìn)行分析，并輸出分析結(jié)果。 (4)測(cè)試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。 三、概要設(shè)計(jì) 抽象數(shù)據(jù)類型的定義： ADT Stack 數(shù)據(jù)對(duì)象：D=a i|aiElemSet,i=1,2,n, n0 數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=1,2,n 基本操作： InitStack( double arrayN; Nu

4、mStack; typedef struct int top; char arrayN; OpStack; 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 4 - /把字符轉(zhuǎn)換為相應(yīng)的整數(shù)的函數(shù) int Cint(char mychar) return (mychar-48); /數(shù)字進(jìn)棧的函數(shù) status PushNum(NumStack numstack.arraynumstack.top-1=num; return OK; else return ERROR; /數(shù)字出棧的函數(shù) status PopNum(NumStack numstack.top-; return OK; else re

5、turn ERROR; /操作符進(jìn)棧的函數(shù) status PushOp(OpStack opstack.arrayopstack.top-1=op; return OK; else return ERROR; 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 5 - /操作符出棧的函數(shù) status PopOp(OpStack opstack.top-; return OK; else return ERROR; /進(jìn)行運(yùn)算的函數(shù) double Calc(double a,double b,char c) double result; 五、調(diào)試分析 1調(diào)試過程中遇到的問題是如何解決的以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)

6、的討論和分析 調(diào)試過程中，對(duì)于非法輸入的測(cè)試很重要，對(duì)于一些不符合常規(guī)的輸入進(jìn) 行測(cè)試，并針對(duì)存在的問題對(duì)源代碼進(jìn)行修改，可以對(duì)于非法輸入進(jìn)行提示。 2算法的時(shí)間復(fù)雜性和可能的改進(jìn)設(shè)想 此算法的運(yùn)行時(shí)間主要花在 while 循環(huán)上，它從頭到尾掃描后綴表達(dá)式中 的每一個(gè)數(shù)據(jù)（每個(gè)操作數(shù)或運(yùn)算符均為一個(gè)數(shù)據(jù)） ，若后綴表達(dá)式由 n 個(gè)數(shù)據(jù) 組成，則此算法的時(shí)間復(fù)雜度為 O(n)。 在轉(zhuǎn)換算法中，中綴算術(shù)表達(dá)式中的每個(gè)字符均需要掃描一遍，對(duì)于掃描 到的每個(gè)運(yùn)算符，最多需要進(jìn)行入棧、出棧和寫入后綴表達(dá)式這三次操作，對(duì) 于掃描到的數(shù)字或小數(shù)點(diǎn)，只需要把它直接寫入到后綴表達(dá)式即可。所以，此 算法的時(shí)間復(fù)雜

7、度為 O(n)，n 為后綴表達(dá)式中字符的個(gè)數(shù)。 六、測(cè)試結(jié)果 1、輸入：5+6*3%2 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 6 - 輸出：5+6*3%2=11.0 2、輸入：3+5*（8-2）%4 輸出：3+5*（8-2）%4=13.0 3、輸入:1*5+2 輸出：對(duì)不起！表達(dá)式有錯(cuò)！ 4、輸入：123321123+456654456 輸出：123321123+456654456=5.7997555E8 5、輸入：1111 輸出：1111=1111.0 6、輸入：5（3+2） 輸出：對(duì)不起！表達(dá)式有錯(cuò)！ 7、輸入：5+9*3-8/4%2 輸出：5+9*3-8/4%2= -Infinit

8、y 界面效果圖 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 7 - 運(yùn)行結(jié)果顯示-1 運(yùn)行結(jié)果顯示-2 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 8 - 七、課程設(shè)計(jì)總結(jié) 通過本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，我有很多收獲，在此，我將我的親身感受回 顧和總結(jié)于下： 在上學(xué)期中學(xué)習(xí)了本專業(yè)的核心課程數(shù)據(jù)結(jié)構(gòu)。什么是數(shù)據(jù)結(jié)構(gòu)呢？ 這是我們首先考慮到的問題：從字面上來看， “數(shù)據(jù)結(jié)構(gòu)”分?jǐn)?shù)據(jù)和結(jié)構(gòu)兩部分， 這就很容易聯(lián)想到數(shù)據(jù)結(jié)構(gòu)的本質(zhì)是一種使數(shù)據(jù)結(jié)構(gòu)化的知識(shí)。通過理論課程 的學(xué)習(xí)，使我初步了解了數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì) 算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。

9、現(xiàn) 代程序設(shè)計(jì)已轉(zhuǎn)型為討論如何在最大程度上處理好數(shù)據(jù)之間的相互關(guān)系并提升 數(shù)據(jù)處理的效率。在這里，數(shù)據(jù)結(jié)構(gòu)就發(fā)揮了重要的作用。數(shù)據(jù)結(jié)構(gòu)可以說是 編程的靈魂，它不是一門語言。數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計(jì)語言本身沒有任何聯(lián)系， 唯一有的關(guān)系就是用程序語言去描述數(shù)據(jù)結(jié)構(gòu)?，F(xiàn)今我們所學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)課 程常用的描述語言主要有 C、C+和 JAVA 等。數(shù)據(jù)結(jié)構(gòu)只是給我們提供處理常 規(guī)問題的一個(gè)思路而已，講的是已經(jīng)成熟的編程思想和算法，適用于所有開發(fā) 語言。所以說，組織好數(shù)據(jù)結(jié)構(gòu)是寫程序的第一步。 數(shù)據(jù)結(jié)構(gòu)是一門實(shí)踐性較強(qiáng)的計(jì)算機(jī)基礎(chǔ)課程，為了學(xué)好這門課程，必須 在掌握理論知識(shí)的同時(shí)，加強(qiáng)上機(jī)實(shí)踐。課程設(shè)計(jì)的目的就

10、是要達(dá)到理論與實(shí) 際應(yīng)用相結(jié)合，使我們能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把 現(xiàn)實(shí)世界中的實(shí)際問題在計(jì)算機(jī)內(nèi)部表示出來，同時(shí)強(qiáng)化對(duì)編程語言的使用， 培養(yǎng)基本的、良好的程序設(shè)計(jì)能力。 我于大二上學(xué)期從軟件學(xué)院軟件工程專業(yè)轉(zhuǎn)到信息學(xué)院計(jì)算機(jī)專業(yè)，在 09 年暑假中，我參加了軟件學(xué)院的 JAVA 實(shí)訓(xùn)，了解了一定的 JAVA 語言知識(shí)，因 為本次課程設(shè)計(jì)要制作界面，所以選擇 JAVA 語言有它的優(yōu)勢(shì)。 通過這次課程設(shè)計(jì)，我體會(huì)到要做出一個(gè)好的程序是很難的，盡管我花了 一個(gè)多星期去做這兩個(gè)項(xiàng)目，但這個(gè)程序還是不夠理想，只是達(dá)到一些基本的 水平而已，跟那些功能強(qiáng)大的程序還是有很大的距離。這個(gè)程

11、序還有一些地方 值得完善的，比如算式計(jì)算中一些非法輸入（如數(shù)字后面連續(xù)輸入括號(hào)無法判 斷非法并影響計(jì)算結(jié)果等） ，這些問題需要程序員考慮得更全面，使實(shí)現(xiàn)的功能 更完善，在今后不斷改進(jìn)。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 9 - 在近兩周的課程設(shè)計(jì)中，我認(rèn)為最大的收獲就是在遇到問題時(shí)解決問題的 過程。如對(duì)語言并不完全了解，如有些函數(shù)的操作需要通過查閱相關(guān)書籍和幫 助來了解，另外，在入棧、出棧的算法設(shè)計(jì)中，曾因?yàn)樗悸凡磺逦诰幋a 時(shí)遇到了困難，對(duì)于運(yùn)算符和數(shù)字的分離和判斷也曾困擾過我。我通過查閱書 籍、上網(wǎng)搜索和向其他同學(xué)詢問，才得以最終完成項(xiàng)目。 通過這次課程設(shè)計(jì)，我學(xué)到了很多，同

12、時(shí)也認(rèn)識(shí)到了自己的不足。學(xué)校的 課程不能將所有的知識(shí)都講授給我們，所以要想學(xué)好一門課程，我們應(yīng)該充分 利用課余時(shí)間多看專業(yè)相關(guān)的書籍，豐富自己的知識(shí)。同時(shí)，作為計(jì)算機(jī)專業(yè) 的學(xué)生，動(dòng)手能力也是非常重要的，在掌握了理論知識(shí)后應(yīng)多多上機(jī)實(shí)踐。只 有多多實(shí)踐，才能更好地學(xué)習(xí)好一門語言，更好地理解課程的內(nèi)容。 八、參考文獻(xiàn) 【1】 清華大學(xué)計(jì)算機(jī)系列教材數(shù)據(jù)結(jié)構(gòu)(C 語言版)/嚴(yán)蔚敏，吳偉民編著 北京：清華大學(xué)出版社，2007.4 【2】 Java JDK 5.0 學(xué)習(xí)筆記/良葛格編著北京：清華大學(xué)出版社， 2006.8 九、附錄 package stack; public class CharSta

13、ck CharNode top; int sum; public CharStack() top=new CharNode(); top.c=#; sum=0; public char pop() /不作有沒有元素的判斷，統(tǒng)一在出棧前進(jìn)行判斷，若沒有元素， 則不調(diào)用此函數(shù) char c=top.node.c; top.node=top.node.node; 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 10 - sum-; return c; public void push(char c) CharNode newNode=new CharNode(); newNode.c=c; newNod

14、e.node=top.node; top.node=newNode; sum+; class CharNode CharNode node; char c; public CharNode() node=null; c= ; package stack; public class CharStack CharNode top; int sum; public CharStack() top=new CharNode(); top.c=#; sum=0; public char pop() /不作有沒有元素的判斷，統(tǒng)一在出棧前進(jìn)行判斷，若沒有元素， 則不調(diào)用此函數(shù) char c=top.node

15、.c; top.node=top.node.node; sum-; return c; public void push(char c) CharNode newNode=new CharNode(); 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 11 - newNode.c=c; newNode.node=top.node; top.node=newNode; sum+; class CharNode CharNode node; char c; public CharNode() node=null; c= ; package stack; import java.awt.GridBagC

16、onstraints; import java.awt.Insets; /* * GBC GridBagLayout * * author ibm * */ public class GBC extends GridBagConstraints /* * () * param x * param y */ public GBC(int x, int y) this.gridx = x; this.gridy = y; 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 12 - public GBC(int gridx, int gridy, int gridwidth, int gridheight

17、) this.gridx = gridx; this.gridy = gridy; this.gridwidth = gridwidth; this.gridheight = gridheight; public GBC setAnchor(int anchor) this.anchor = anchor; return this; /* * 仯 * param fill * return */ public GBC setFill(int fill) this.fill = fill; return this; /* * * param weightx * param weighy * re

18、turn */ public GBC setWeight(double weightx, double weighty) this.weightx = weightx; this.weighty = weighty; return this; /* * * param distance * return */ public GBC setInset(int distance) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 13 - this.insets = new Insets(distance, distance, distance, distance); return this; /* *

19、 * param distance * return */ public GBC setInset(int top, int left, int bottom, int right) this.insets = new Insets(top, left, bottom, right); return this; public GBC setIpad(int ipadx, int ipady) this.ipadx = ipadx; this.ipady = ipady; return this; public class GetPriority public int inSideStack(c

20、har c) int i=0; switch(c) case =: i=1;break; case ): i=1;break; case +: i=3;break; case -: i=3;break; case *: i=5;break; case /: i=5;break; case %: i=7;break; case : i=9;break; case (: i=1;break; return i; public int outSideStack(char c) int i=0; switch(c) case =: i=0;break; case ): i=0;break; case

21、+: i=2;break; 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 14 - case -: i=2;break; case *: i=4;break; case /: i=4;break; case %: i=6;break; case : i=8;break; case (: i=10;break; default : i=-1; /當(dāng)遇到不可識(shí)別的運(yùn)算符識(shí)，設(shè)其優(yōu)先級(jí)為-1，以便在主程 序中能及時(shí)檢查出錯(cuò)誤 return i; package stack; import java.awt.BorderLayout; import java.awt.event.ActionEvent;

22、 import java.awt.event.ActionListener; import javax.swing.*; public class MainClass extends JFrame private static final long serialVersionUID = 8669406311759888678L; MainClass mainClass; JTabbedPane tab; JTextField input, output; JButton btnWork; private JTextArea txtaDisplay; private JTextArea txta

23、Input; private JLabel lblDisplay; private JLabel lblInput; private JButton btnProcess; private JPanel pnlNorth; private JPanel pnlSouth; private JPanel pnl; private JScrollPane scrDisplayPnl; private JScrollPane scrInputPnl; public static void main(String args) new MainClass().init(); public void in

24、it() try UIManager.setLookAndFeel(com.nilo.plaf.nimrod.NimRODLookAndFeel); 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 15 - catch (Exception e) try UIManager.setLookAndFeel(UIManager .getSystemLookAndFeelClassName(); catch (Exception e1) mainClass = new MainClass(); this.setTitle(數(shù)據(jù)結(jié)構(gòu)); this.setSize(500, 400); this.setLo

25、cationRelativeTo(null); this.setDefaultCloseOperation(EXIT_ON_CLOSE); this.add(this.getJTabbedPane(), BorderLayout.CENTER); this.setVisible(true); public JTabbedPane getJTabbedPane() tab = new JTabbedPane(); tab.addTab(線性表, getFirstPanel(); tab.addTab(Huffman, new JPanel(); return tab; public JPanel

26、 getFirstPanel() JPanel panel = new JPanel(); panel.setLayout(new BorderLayout(); txtaDisplay = new JTextArea(8, 10); txtaDisplay.setEditable(false); txtaInput = new JTextArea(8, 15); scrDisplayPnl = new JScrollPane(txtaDisplay); scrInputPnl = new JScrollPane(txtaInput); lblDisplay = new JLabel(分析結(jié)果

27、); lblInput = new JLabel(輸入表達(dá)式：); btnProcess = new JButton(分析); pnlNorth = new JPanel(); pnlSouth = new JPanel(); pnl = new JPanel(); pnlNorth.setLayout(new BorderLayout(); pnlSouth.setLayout(new BorderLayout(); / 組件控制 pnlNorth.add(lblDisplay, BorderLayout.NORTH); pnlNorth.add(scrDisplayPnl, BorderL

28、ayout.CENTER); pnlSouth.add(lblInput, BorderLayout.NORTH); pnlSouth.add(scrInputPnl, BorderLayout.CENTER); pnl.add(btnProcess); panel.add(pnlNorth, BorderLayout.NORTH); 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 16 - panel.add(pnlSouth, BorderLayout.CENTER); panel.add(pnl, BorderLayout.SOUTH); btnProcess.addActionListen

29、er(new ActionListener() public void actionPerformed(ActionEvent e) String source = txtaInput.getText().trim(); txtaInput.setText(); txtaDisplay.setText(calculate(source); ); return panel; public String calculate(String inputStr) String result; CharStack charStack = new CharStack(); NumStack numStack

30、 = new NumStack(); GetPriority priority = new GetPriority(); / GetPriority priority=new GetPriority(); OperationClass operationFunction = new OperationClass(); String str = inputStr + =; / 輸入一個(gè)正確的表達(dá)式 char charArray = str.toCharArray(); float a = 0f; boolean f = false; boolean d = false; boolean judg

31、echar = true; boolean rku = false; int lku = 0; int l = 0; char chInStack; / 這個(gè)字符變量在下面代碼中充當(dāng)存儲(chǔ)從運(yùn)算符棧中出棧的運(yùn)算 符 for (int i = 0; i i + 1) judgechar = false; break; if (mainClass.judge(charArrayi) if (d = true) float k = (float) (charArrayi - 0); for (int j = 0; j = 0 if (t) return true; else return false;

32、 package stack; public class NumStack IntNode top; public NumStack() top=new IntNode(); public float pop() /出棧 /對(duì)于頭結(jié)點(diǎn)，存整數(shù)類型的a屬性存的是棧內(nèi)的元素個(gè)數(shù) /對(duì)于出棧操作，由于本函數(shù)返回值為整數(shù)，故不進(jìn)行判斷是否棧內(nèi)還有元素， /而是在調(diào)用此函數(shù)前，通過top.a的值進(jìn)行判斷 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 20 - float t=top.node.a; top.node=top.node.node; top.a-; return t; public void

33、push(float a) /進(jìn)棧 IntNode newnode=new IntNode(); newnode.a=a; newnode.node=top.node; top.node=newnode; top.a+; class IntNode IntNode node; float a; public IntNode() node=null; a=0f; package stack; public class OperationClass /從numStack 棧中依次取出兩個(gè)數(shù)字進(jìn)行相應(yīng)運(yùn)算符的操作，結(jié)果再壓入numStack棧 中 public boolean operation(c

34、har chInStack,NumStack numStack,CharStack charStack) float a; float b; switch(chInStack) case +: if(numStack.top.a=2)a=numStack.pop();b=numStack.pop();numStack.push(a+b);return true;elsereturn false; case -: if(numStack.top.a=2)a=numStack.pop();b=numStack.pop();numStack.push(b-a);return true;elseret

35、urn false; case *: if(numStack.top.a=2)a=numStack.pop();b=numStack.pop();numStack.push(a*b);return true;elsereturn false; 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 21 - case /: if(numStack.top.a=2)a=numStack.pop();b=numStack.pop();numStack.push(b/a);return true;elsereturn false; case %: if(numStack.top.a=2)a=numStack.p

36、op();b=numStack.pop();numStack.push(b%a);return true;elsereturn false; case : if(numStack.top.a=2)a=numStack.pop();b=numStack.pop();float t=b;for(int i=1;ia;i+)b*=t;numStack.push(b);return true;elsereturn false; case (: return true; default : return true; 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 22 - 題目三：排課問題 一、實(shí)驗(yàn)名稱：

37、排課問題 二、需求分析： 設(shè)計(jì)任務(wù)： 在文件 conf.txt 中保存若干門課程，以及該課程需要哪些前續(xù)課程。要求 一門課程需要一個(gè)學(xué)期才能學(xué)完。保存格式為例如： 大學(xué)物理 C 語言 Java 語言:C 語言 微積分 高級(jí)物理學(xué):微積分,大學(xué)物理 界面上，首先出現(xiàn)一個(gè)按鈕，點(diǎn)擊，載入 conf.txt。點(diǎn)擊另一個(gè)按鈕，顯 示需要幾個(gè)學(xué)期上完這些課程，每學(xué)期各學(xué)習(xí)哪些課程。 (1)輸入的形式和輸入值的范圍：讀入文件。 (2)輸出的形式：文本輸出。 (3)程序所能達(dá)到的功能：從文件中讀出數(shù)據(jù)，采用拓?fù)渑判颍@示出各學(xué)期需 要學(xué)習(xí)哪些課程。 (4)測(cè)試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入

38、及其輸出結(jié)果。 三、概要設(shè)計(jì) 1ADT Stack 數(shù)據(jù)對(duì)象：D=a i|aiElemSet,i=1,2,n, n0 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 23 - 數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=1,2,n 基本操作： InitStack( /對(duì)各頂點(diǎn)求入度 indegree0.vernum-1 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 26 - InitStack(S); for(i=0;inextarc) k=p-adjvex; if(!(-indegreek) Push(S,k); /若入度減為 0，則入棧 /for /while if(countbase=(ElemT

39、ype *)malloc(STACK_INIT_SIZE*sizeof(ElemType); if(!S-base) printf(memory allocation failed, goodbye); exit(1); S-top=S-base; S-stacksize=STACK_INIT_SIZE; 出棧操作函數(shù) 原型：int Pop(SqStack *S,ElemType *e) 功能：刪除 S 的棧頂元素，并用 e 返回； 參數(shù)：SqStack *S,ElemType *e 返回值：int 源代碼： int Pop(SqStack *S,ElemType *e) if(S-top=S

40、-base) return ERROR; *e=*-S-top; 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 28 - return 0; 進(jìn)棧操作函數(shù) 原型 void Push(SqStack *S，ElemType e) 功能：插入元素 e 為新的棧頂元素 參數(shù)：SqStack *S ，ElemType e 返回值：void 源代碼： void Push(SqStack *S,ElemType e)/ if(S-top-S-base=S-stacksize) S-base=(ElemType*)realloc(S-base,(S- stacksize+STACKINCREMENT)* si

41、zeof(ElemType); if(!S-base) printf(memory allocation failed, goodbye); exit(1); S-top = S-base+S-stacksize; *S-top+=e; 判斷棧是否為空的函數(shù) 原型 int StackEmpty(SqStack *S) 功能：判斷棧是否為空 參數(shù)：SqStack *S 返回值：int 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 29 - 源代碼： int StackEmpty(SqStack *S) if(S-top=S-base) return OK; else return ERROR; 創(chuàng)

42、建圖的函數(shù) 原型 void CreatGraph(ALGraph *G) 功能：創(chuàng)建一有向圖 參數(shù)：ALGraph *G 返回值：void 源代碼： void CreatGraph(ALGraph *G) int m, n, i; ArcNode *p; printf(請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):); scanf(%d%d, for (i = 1; i vexnum; i+) G-verticesi.data = i; G-verticesi.firstarc = NULL; for (i = 1; i arcnum; i+) /輸入存在邊的點(diǎn)集合 printf(n 請(qǐng)輸入存在邊的兩個(gè)頂點(diǎn)的序號(hào):);

43、 scanf(%d%d, while (n G-vexnum | m G-vexnum) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 30 - printf(輸入的頂點(diǎn)序號(hào)不正確 請(qǐng)重新輸入:); scanf(%d%d, p = (ArcNode*)malloc(sizeof(ArcNode); if (p = NULL) printf(memory allocation failed,goodbey); exit(1); p-adjvex = m; p-nextarc = G-verticesn.firstarc; G-verticesn.firstarc = p; printf(建立的鄰接

44、表為:n); /輸出建立好的鄰接表 for(i = 1; i vexnum; i+) printf(%d,G-verticesi.data); for(p = G-verticesi.firstarc; p; p = p-nextarc) printf(%3d,p-adjvex); printf(n); 求入度操作函數(shù) 原型 void FindInDegree(ALGraph G, int indegree) 功能：求圖中頂點(diǎn)的入度 參數(shù)：ALGraph G, int indegree 返回值：void 源代碼： void FindInDegree(ALGraph G, int indegre

45、e) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 31 - int i; for (i = 1; i = G.vexnum; i+) indegreei = 0; for (i = 1; i adjvex+; G.verticesi.firstarc = G.verticesi.firstarc-nextarc; 拓?fù)渑判蚝瘮?shù) 原型 void TopologicalSort(ALGraph G) 功能：將一個(gè)偏序排列成一個(gè)全序 參數(shù)：ALGraph G 返回值：void 源代碼： void TopologicalSort(ALGraph G) /進(jìn)行拓?fù)渑判?int indegreeM;/存放

46、頂點(diǎn)的入度 int i, k, n; int count = 0; ArcNode *p; SqStack S; FindInDegree(G, indegree); InitStack( 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 32 - for (i = 1; i = G.vexnum; i+) printf(第%d 個(gè)點(diǎn)的入度為%d n, i, indegreei); printf(n); for ( i = 1; i nextarc) k = p-adjvex; if (!(-indegreek) Push( printf(n); if (count G.vexnum)/該有向圖有回

47、路 printf(出現(xiàn)錯(cuò)誤n); 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 33 - else printf(排序成功n); 2存儲(chǔ)結(jié)構(gòu)： (1),表結(jié)點(diǎn) typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode; (2),鏈表的存儲(chǔ)結(jié)構(gòu) typedef struct VNode int data; ArcNode *firstarc; VNode,AdjListMAX_VEXTEX_NUM; (3),圖的存儲(chǔ)結(jié)構(gòu) typedef struct AdjList vertices; int vexnum, arcnu

48、m; ALGraph; (4),棧的存儲(chǔ)結(jié)構(gòu) typedef struct ElemType *base; ElemType *top; 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 34 - int stacksize; SqStack; 五、調(diào)試分析 算法的時(shí)間復(fù)雜性和可能的改進(jìn)設(shè)想 該拓?fù)渑判蛩惴?，?duì)有 n 個(gè)頂點(diǎn)和 e 條弧的有向圖而言，建立求各頂點(diǎn)的 入度的時(shí)間復(fù)雜度為 O(e)；建立入度頂點(diǎn)棧的時(shí)間復(fù)雜度為 O(n)；在拓?fù)渑判?過程中，若有向圖無環(huán)，則每個(gè)頂點(diǎn)進(jìn)一次棧，出一次棧，入度減 1 的操作在 while 語句中總共執(zhí)行 e 詞，所以，總的時(shí)間復(fù)雜度為 O(n+e)。 六、測(cè)

49、試結(jié)果 界面效果圖 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 35 - 打開文件效果圖 運(yùn)行結(jié)果 七、課程設(shè)計(jì)總結(jié) 在近兩周的課程設(shè)計(jì)中，我認(rèn)為最大的收獲就是在遇到問題時(shí)解決問題的 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 36 - 過程。如對(duì)語言并不完全了解，如有些函數(shù)的操作需要通過查閱相關(guān)書籍和幫 助來了解，同時(shí)也向其他同學(xué)詢問，才得以最終完成項(xiàng)目。這次課程設(shè)計(jì)，培 養(yǎng)了我自己的實(shí)際分析能力、編程和動(dòng)手能力，最終目標(biāo)是想通過這種形式， 幫助自己更加系統(tǒng)的掌握數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容；培養(yǎng)了自己對(duì) JAVA 語言程序設(shè) 計(jì)的興趣，更加有信心學(xué)好這門課程；設(shè)計(jì)了一個(gè)拓?fù)渑判虺绦?，解決實(shí)際問 題，

50、將所學(xué)內(nèi)容運(yùn)用到實(shí)際當(dāng)中。 通過這次課程設(shè)計(jì)，我學(xué)到了很多，同時(shí)也認(rèn)識(shí)到了自己的不足。學(xué)校的 課程不能將所有的知識(shí)都講授給我們，所以要想學(xué)好一門課程，我們應(yīng)該充分 利用課余時(shí)間多看專業(yè)相關(guān)的書籍，豐富自己的知識(shí)。同時(shí)，作為計(jì)算機(jī)專業(yè) 的學(xué)生，動(dòng)手能力也是非常重要的，在掌握了理論知識(shí)后應(yīng)多多上機(jī)實(shí)踐。只 有多多實(shí)踐，才能更好地學(xué)習(xí)好一門語言，更好地理解課程的內(nèi)容。 八、參考文獻(xiàn) 【1】 清華大學(xué)計(jì)算機(jī)系列教材數(shù)據(jù)結(jié)構(gòu)(C 語言版)/嚴(yán)蔚敏，吳偉民編 著北京：清華大學(xué)出版社，2007.4 【2】 Java JDK 5.0 學(xué)習(xí)筆記/良葛格編著北京：清華大學(xué)出版社，2006.8 九、附錄 packa

51、ge sort.test; import sort.Interface; public class Outmain /* * param args */ public static void main(String args) new Interface(); 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 37 - package sort; import java.awt.BorderLayout; import javax.swing.JButton; import javax.swing.JFileChooser; import javax.swing.JFrame; import jav

52、ax.swing.JPanel; import javax.swing.JScrollPane; import javax.swing.JTable; import javax.swing.JTextField; import javax.swing.UIManager; import javax.swing.UnsupportedLookAndFeelException; import com.birosoft.liquid.LiquidLookAndFeel; /* * 輸出界面 * */ public class Interface extends JFrame JTextField t

53、ext; JTable table; JFileChooser fileChooser; static try / UIManager.setLookAndFeel(ch.randelshofer.quaqua.QuaquaLookAndFeel); UIManager.setLookAndFeel(new LiquidLookAndFeel(); catch (UnsupportedLookAndFeelException e) / TODO Auto-generated catch block e.printStackTrace(); public Interface() super(排課

54、); init(); private void init() String title = new String學(xué)期,所修課程; 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 38 - String args = new String00; this.setSize(480, 320); this.setLocationRelativeTo(null); JPanel panel = new JPanel(); text = new JTextField(15); BorderLayout layout = new BorderLayout(); this.setLayout(layout);

55、panel.add(text); JButton button = new JButton(選擇課程文件); button.setActionCommand(open); fileChooser = new JFileChooser(.); panel.add(button); button.addActionListener(new Listener(this); table = new JTable(args,title); JScrollPane pane = new JScrollPane(table, JScrollPane.VERTICAL_SCROLLBAR_ALWAYS , J

56、ScrollPane.HORIZONTAL_SCROLLBAR_ALWAYS); this.add(panel,BorderLayout.NORTH); this.add(pane,BorderLayout.CENTER); this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); this.setVisible(true); package sort; import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import

57、java.io.FileReader; import java.io.IOException; import java.io.LineNumberReader; import java.util.ArrayList; import Exception.DateException; /* * * 實(shí)現(xiàn)排課類 * */ public class Arranging 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 39 - /* * 節(jié)點(diǎn)內(nèi)部類，用來存儲(chǔ)數(shù)據(jù) * 一是存儲(chǔ)課程名和學(xué)該課程前的前提課程 * 二是用來存儲(chǔ)課程安排次序和該次可學(xué)的內(nèi)容 */ public class Node String n

58、ame; ArrayList baseList; /* * 空構(gòu)造器 */ public Arranging() /* * 排課方法 * 第一次排課的課程是 Node 節(jié)點(diǎn)所代表課程該課程的前提課程是空，將其寫入 ArrayList * 再將上次課程從剩余課程的前提課程中刪除，重復(fù)以上過程知道所有課程被排完或 排了 * 8 次后仍未排完（大學(xué)教育只有四年，八個(gè)學(xué)期，若八次不能排完，說明課程安排 存在問題， * 超出本方法處理范圍、不予處理） * param filepath * return * throws */ public ArrayList arrayclass(File filepa

59、th) throws DateException, FileNotFoundException,IOException ArrayList result = new ArrayList();/存儲(chǔ)結(jié)果 ArrayList list = readFile(filepath); Integer i = 1;/記錄排課次序 int t = 1;/標(biāo)記 while(list.size() 0) s.name = i.toString(); s.baseList = new ArrayList(); for(Node tem:list) /提取前提課程為空的節(jié)點(diǎn)，寫入 result 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

60、 計(jì)算機(jī) 0801 - 40 - if(tem.baseList.size() = 0) s.baseList.add(tem.name); /list.remove(tem); for(String tem:s.baseList) /刪除前提課程為空的節(jié)點(diǎn) list.remove(serchIndex(list,tem); for(Node tem:list) /刪除剩余節(jié)點(diǎn)的前提課程已修過課程 for(String tem2:s.baseList) tem.baseList.remove(tem2); result.add(s); i +; return result;/返回 /* * 文

61、件讀取方法 * param * return */ public ArrayList readFile(File filepath) throws DateException ,FileNotFoundException,IOException ArrayList list = new ArrayList(); / File file = new File(filepath); BufferedReader read= new BufferedReader(new LineNumberReader(new FileReader(filepath); try String temp; while

62、(temp = read.readLine() != null) if(.equals(temp.trim() continue; if(!checkchar(temp) Node s = new Node(); s.name = temp; s.baseList = new ArrayList(); list.add(s); else String arg0 = temp.split(:);/按“：”拆分 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 41 - if(arg0.length != 2 ) throw new DateException(); Node s = new Node(

63、); s.name = arg00; String arg1 = arg01.split(,);/按“， ”拆分 ArrayList l = new ArrayList(); for(String tem:arg1) l.add(tem); s.baseList = l; list.add(s); catch (FileNotFoundException e) throw new FileNotFoundException(); catch (IOException e) throw new IOException(); finally read.close();/關(guān)閉 return list

64、; /* * 判斷是否有“：”號(hào) * param str * return */ private boolean checkchar(String str) for(int i = 0;i str.length();i+) if(str.charAt(i) = :) return true; return false; /* * 查找 Node 節(jié)點(diǎn)內(nèi) name 為 Str 的節(jié)點(diǎn) * param list * param str * return */ private Node serchIndex(ArrayList list,String str) for(Node temp: list

65、) if(temp.name.equals(str) return temp; 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 42 - return null; package sort; import java.awt.HeadlessException; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.io.File; import java.io.FileNotFoundException; import java.io.IOException; import java

66、.util.ArrayList; import javax.swing.table.DefaultTableModel; import sort.Arranging.Node; import Exception.DateException; /* * * 監(jiān)聽器類 * * */ public class Listener implements ActionListener Interface face; /* * 構(gòu)造器類 * * param face */ public Listener(Interface face) this.face = face; /* * 監(jiān)聽器 * 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 43 - * param e */ public void actionPerformed(ActionEvent e) / if (輸入.equals(e.getActionCommand() / / String road = face.text.getText(); / if (.equals(road) / / 當(dāng)內(nèi)容為空時(shí)，拋出錯(cuò)誤信息 / new JOpt