《《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告線性表進(jìn)行算式計(jì)算、排課問題,JAVA語(yǔ)言,截圖完整》由會(huì)員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告線性表進(jìn)行算式計(jì)算、排課問題,JAVA語(yǔ)言,截圖完整（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ì)算題目一：利用線性表進(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 -三、概要設(shè)計(jì).-

2、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ì)算題目一：利用線性表進(jìn)行算式計(jì)算一、實(shí)驗(yàn)名稱：一、實(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ì)抽象數(shù)據(jù)類型的定義：ADT Stack 數(shù)據(jù)對(duì)象：D=ai|aiElemSet,i=1,2,n, n0數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=1,2,n基本操作： InitStack(&S)； 初始化棧 S，構(gòu)造一個(gè)空棧數(shù)據(jù)結(jié)構(gòu)課

4、程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 2 - StackEmpty(S)； 初始條件：棧 S 已存在操作結(jié)果：若棧為空棧，則返回 true，否則返回 false StackLength（S） ；初始條件：棧 S 已存在操作結(jié)果：返回 S 的元素個(gè)數(shù)，即棧的長(zhǎng)度GetTop(S,&e)初始條件：棧 S 已存在且非空操作結(jié)果：用 e 返回 S 的棧頂元素Push(&S,e)初始條件：棧 S 已存在操作結(jié)果：插入元素 e 為新的棧頂元素Pop(&S,&e)初始條件：棧 S 已存在且非空操作結(jié)果：刪除 S 的棧頂元素，并用 e 返回其值主程序的流程：定義鏈棧，判斷運(yùn)算符優(yōu)先級(jí)，實(shí)現(xiàn)具體計(jì)算，錯(cuò)誤處理。數(shù)據(jù)

5、結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 3 -四、詳細(xì)設(shè)計(jì)四、詳細(xì)設(shè)計(jì)主要算法：(偽代碼)#define N 50#define OK 1#define ERROR 0#include #include typedef structint top;double arrayN;NumStack;typedef structint 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

6、 &numstack,double num)if(numstack.topN) numstack.top+;numstack.arraynumstack.top-1=num;return OK;else return ERROR;/數(shù)字出棧的函數(shù)status PopNum(NumStack &numstack,double &num)if(numstack.top)num=numstack.arraynumstack.top-1;numstack.top-;return OK;else return ERROR;/操作符進(jìn)棧的函數(shù)status PushOp(OpStack &opstack,c

7、har &op)if(opstack.topN) opstack.top+;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,char &op)if(opstack.top) op=opstack.arrayopstack.top-1;opstack.top-;return OK;else return ERROR;/進(jìn)行運(yùn)算的函數(shù)double Calc(double a,double b,char c

8、)double result;五、調(diào)試分析五、調(diào)試分析1調(diào)試過程中遇到的問題是如何解決的以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的討論和分析調(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á)式這三次操作，

9、對(duì)于掃描到的數(shù)字或小數(shù)點(diǎn)，只需要把它直接寫入到后綴表達(dá)式即可。所以，此算法的時(shí)間復(fù)雜度為 O(n)，n 為后綴表達(dá)式中字符的個(gè)數(shù)。六、測(cè)試結(jié)果六、測(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.02、輸入：3+5*（8-2）%4輸出：3+5*（8-2）%4=13.03、輸入:1*5+2 輸出：對(duì)不起！表達(dá)式有錯(cuò)！4、輸入：123321123+456654456 輸出：123321123+456654456=5.7997555E85、輸入：1111 輸出：1111=1111.06、輸入：5（3+2） 輸出：對(duì)不起！表達(dá)式有錯(cuò)！7、輸

10、入：5+9*3-8/4%2 輸出：5+9*3-8/4%2= -Infinity 界面效果圖數(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é)通過本次數(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ù)

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

12、在掌握理論知識(shí)的同時(shí)，加強(qiáng)上機(jī)實(shí)踐。課程設(shè)計(jì)的目的就是要達(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ǔ)言的使用，培養(yǎng)基本的、良好的程序設(shè)計(jì)能力。我于大二上學(xué)期從軟件學(xué)院軟件工程專業(yè)轉(zhuǎn)到信息學(xué)院計(jì)算機(jī)專業(yè)，在 09年暑假中，我參加了軟件學(xué)院的 JAVA 實(shí)訓(xùn)，了解了一定的 JAVA 語(yǔ)言知識(shí)，因?yàn)楸敬握n程設(shè)計(jì)要制作界面，所以選擇 JAVA 語(yǔ)言有它的優(yōu)勢(shì)。通過這次課程設(shè)計(jì)，我體會(huì)到要做出一個(gè)好的程序是很難的，盡管我花了一個(gè)多星期去做這兩個(gè)項(xiàng)目，但這個(gè)程序還是不夠理想，只是達(dá)到一些基本的水平而已，跟那些功能

13、強(qiáng)大的程序還是有很大的距離。這個(gè)程序還有一些地方值得完善的，比如算式計(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ì)語(yǔ)言并不完全了解，如有些函數(shù)的操作需要通過查閱相關(guān)書籍和幫助來了解，另外，在入棧、出棧的算法設(shè)計(jì)中，曾因?yàn)樗悸凡磺逦诰幋a時(shí)遇到了困難，對(duì)于運(yùn)算符和數(shù)字的分離和判斷也曾困擾過我。我通過查閱書籍、上網(wǎng)搜索和向其他同學(xué)詢問，才得以最終完成項(xiàng)目。通過這次課程設(shè)計(jì)，我

14、學(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í)好一門語(yǔ)言，更好地理解課程的內(nèi)容。八、參考文獻(xiàn)八、參考文獻(xiàn)【1】 清華大學(xué)計(jì)算機(jī)系列教材數(shù)據(jù)結(jié)構(gòu)(C C語(yǔ)言版)/嚴(yán)蔚敏，吳偉民編著 北京：清華大學(xué)出版社，2007.4【2】 Java JDK 5.0 學(xué)習(xí)筆記/良葛格編著北京：清華大學(xué)出版社，2006.8 九、附錄九、附錄package stack;public class

15、 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.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;newNode.no

16、de=top.node;top.node=newNode;sum+;class CharNodeCharNode 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.c;top.node=top.

17、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 CharNodeCharNode node;char c;public CharNode() node=null; c= ;package stack;import java.awt.GridBagConstraints;import java.awt.Inset

18、s;/* * GBCGridBagLayout * * 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) this.gridx = gridx; this.gridy = g

19、ridy; 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 * return */ public GBC setWeight(double

20、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; /* * * param distance * return */ public

21、 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(char c) int i=0; switch(c) case =: i=

22、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 +: i=2;break;數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 14

23、- 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;import java.awt.event.ActionListener;import

24、 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 txtaInput;private JLabel lblDisplay;private JLabel lblIn

25、put;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 init() try UIManager.setLookAndFeel(com.nilo.plaf.nimrod.NimRODL

26、ookAndFeel);數(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.setLocationRelativeTo(null);this.setDefaultCloseOperation(EXIT_ON_CLOSE)

27、;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 getFirstPanel() JPanel panel = new JPanel();panel.setLayout(new BorderLayo

28、ut();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é)果);lblInput = new JLabel(輸入表達(dá)式：);btnProcess = new JButton(分析);pnlNorth = new JPanel

29、();pnlSouth = new JPanel();pnl = new JPanel();pnlNorth.setLayout(new BorderLayout();pnlSouth.setLayout(new BorderLayout();/ 組件控制pnlNorth.add(lblDisplay, BorderLayout.NORTH);pnlNorth.add(scrDisplayPnl, BorderLayout.CENTER);pnlSouth.add(lblInput, BorderLayout.NORTH);pnlSouth.add(scrInputPnl, BorderLay

30、out.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.addActionListener(new ActionListener() public void actionPerformed(ActionEvent e) String source = txtaInput.getText

31、().trim();txtaInput.setText();txtaDisplay.setText(calculate(source););return panel;public String calculate(String inputStr) String result;CharStack charStack = new CharStack();NumStack numStack = new NumStack();GetPriority priority = new GetPriority();/ GetPriority priority=new GetPriority();Operati

32、onClass operationFunction = new OperationClass();String str = inputStr + =; / 輸入一個(gè)正確的表達(dá)式char charArray = str.toCharArray();float a = 0f;boolean f = false;boolean d = false;boolean judgechar = true;boolean rku = false;int lku = 0;int l = 0;char chInStack; / 這個(gè)字符變量在下面代碼中充當(dāng)存儲(chǔ)從運(yùn)算符棧中出棧的運(yùn)算符for (int i = 0;

33、 i i + 1) judgechar = false;break;if (mainClass.judge(charArrayi) if (d = true) float k = (float) (charArrayi - 0);for (int j = 0; j = 0 & a priority.outSideStack(ch2);if (t)return true;elsereturn false;package stack;public class NumStack IntNode top; public NumStack() top=new IntNode(); public floa

34、t 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 push(float a) /進(jìn)棧 IntNode newnode=new IntNode(); newnode.a=a; newnode.node=top.node; top.node=newnod

35、e; top.a+; class IntNodeIntNode 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(char chInStack,NumStack numStack,CharStack charStack) float a; float b;switch(chInStack) case +: if(numStack.to

36、p.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;elsereturn false; case *: if(numStack.top.a=2)a=numStack.pop();b=numStack.pop();numStack.push(a*b);return true;elseret

37、urn 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.pop();b=numStack.pop();numStack.push(b%a);return true;elsereturn false; case : if(numStack.top.a=2)a=numStack.pop

38、();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)名稱：一、實(shí)驗(yàn)名稱：排課問題二、需求分析：二、需求分析：設(shè)計(jì)任務(wù)：在文件 conf.txt 中保存若干門課程，以及該課程需要哪些前續(xù)課程。要求一門課程需要一個(gè)學(xué)期才能學(xué)完。保存格式為例如：大學(xué)物理C 語(yǔ)言Java 語(yǔ)言:C

39、 語(yǔ)言微積分高級(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ò)誤的輸入及其輸出結(jié)果。三、概要設(shè)計(jì)三、概要設(shè)計(jì)1ADT Stack 數(shù)據(jù)對(duì)象：D=ai|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

40、,n基本操作： InitStack(&S)； 初始化棧 S，構(gòu)造一個(gè)空棧 StackEmpty(S)； 初始條件：棧 S 已存在操作結(jié)果：若棧為空棧，則返回 true，否則返回 false StackLength（S） ；初始條件：棧 S 已存在操作結(jié)果：返回 S 的元素個(gè)數(shù)，即棧的長(zhǎng)度GetTop(S,&e)初始條件：棧 S 已存在且非空操作結(jié)果：用 e 返回 S 的棧頂元素Push(&S,e)初始條件：棧 S 已存在操作結(jié)果：插入元素 e 為新的棧頂元素Pop(&S,&e)初始條件：棧 S 已存在且非空操作結(jié)果：刪除 S 的棧頂元素，并用 e 返回其值2 2函數(shù)框圖函數(shù)框圖函數(shù)名函數(shù)功能M

41、ain總控函數(shù)InitStack初始化棧Pop出棧Push進(jìn)棧StackEmpty棧的判空CreatGraph創(chuàng)建圖FindInDegree求圖中頂點(diǎn)入度TopologicalSort拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 24 -3 3函數(shù)流程圖：函數(shù)流程圖： （1）主函數(shù)流程圖：（2）求入度函數(shù)的流程圖： （3）創(chuàng)建圖的流程圖： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 25 -（4）拓?fù)渑判蚝瘮?shù)的流程圖：四、詳細(xì)設(shè)計(jì)四、詳細(xì)設(shè)計(jì)1拓?fù)渑判蛑饕惴ǎ和負(fù)渑判蛑饕惴ǎ篠tatus TopologicalSort(ALGraph G)/有向圖 G 采用鄰接表存儲(chǔ)結(jié)構(gòu)/若 G 無

42、回路，則輸出 G 的頂點(diǎn)的一個(gè)拓?fù)渑判蛐蛄胁⒎祷?OK，否則返回 ERROR。FindInDegree(G,indegree); /對(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/whileif(countbase=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType);if(!S-base)printf(memor

43、y 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-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 Pus

44、h(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)*sizeof(ElemType);if(!S-base)printf(memory allocation failed, goodbye);exit(1);S-top = S-base+S-stack

45、size;*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;elsereturn ERROR;創(chuàng)建圖的函數(shù)原型 void CreatGraph(ALGraph *G)功能：創(chuàng)建一有向圖參數(shù)：ALGraph *G返回值：void源代碼：void CreatGraph(ALGraph *G)int m, n, i;ArcNode

46、*p;printf(請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):);scanf(%d%d,&G-vexnum,&G-arcnum);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):);scanf(%d%d,&n,&m);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%

47、d,&n,&m);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(建立的鄰接表為:n); /輸出建立好的鄰接表for(i = 1; i vexnum; i+)printf(%d,G-verticesi.data);for(p = G-verticesi.firstarc; p; p = p-n

48、extarc)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 indegree)數(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 =

49、 G.verticesi.firstarc-nextarc;拓?fù)渑判蚝瘮?shù)原型 void TopologicalSort(ALGraph G) 功能：將一個(gè)偏序排列成一個(gè)全序參數(shù)：ALGraph G返回值：void源代碼：void TopologicalSort(ALGraph G) /進(jìn)行拓?fù)渑判騣nt indegreeM;/存放頂點(diǎn)的入度int i, k, n;int count = 0;ArcNode *p;SqStack S;FindInDegree(G, indegree);InitStack(&S);數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 32 -for (i = 1; i =

50、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(&S,k);printf(n);if (count G.vexnum)/該有向圖有回路printf(出現(xiàn)錯(cuò)誤n);數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 33 -elseprintf(排序成功n);2存儲(chǔ)結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)：(1),表結(jié)點(diǎn)typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;ArcNod

51、e;(2),鏈表的存儲(chǔ)結(jié)構(gòu)typedef struct VNodeint data;ArcNode *firstarc;VNode,AdjListMAX_VEXTEX_NUM;(3),圖的存儲(chǔ)結(jié)構(gòu)typedef structAdjList vertices;int vexnum, arcnum;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)試分析五、調(diào)試分析算法的時(shí)間復(fù)雜性和可能的改進(jìn)設(shè)想算法的時(shí)間復(fù)雜性和可能的改進(jìn)

52、設(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 語(yǔ)句中總共執(zhí)行 e 詞，所以，總的時(shí)間復(fù)雜度為 O(n+e)。六、測(cè)試結(jié)果六、測(cè)試結(jié)果 界面效果圖數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 35 - 打開文件效果圖 運(yùn)行結(jié)果七、課程設(shè)計(jì)總結(jié)七、課程設(shè)計(jì)總結(jié)在近兩周的課程設(shè)計(jì)中，我認(rèn)為最大的收獲就是在遇到問題時(shí)解決問題的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 計(jì)算機(jī) 0801 - 36 -過程。如對(duì)語(yǔ)言并不完全了解，如有些函

53、數(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 語(yǔ)言程序設(shè)計(jì)的興趣，更加有信心學(xué)好這門課程；設(shè)計(jì)了一個(gè)拓?fù)渑判虺绦颍鉀Q實(shí)際問題，將所學(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)多多上

54、機(jī)實(shí)踐。只有多多實(shí)踐，才能更好地學(xué)習(xí)好一門語(yǔ)言，更好地理解課程的內(nèi)容。八、參考文獻(xiàn)八、參考文獻(xiàn)【1】 清華大學(xué)計(jì)算機(jī)系列教材數(shù)據(jù)結(jié)構(gòu)(C C 語(yǔ)言版)/嚴(yán)蔚敏，吳偉民編著北京：清華大學(xué)出版社，2007.4【2】 Java JDK 5.0 學(xué)習(xí)筆記/良葛格編著北京：清華大學(xué)出版社，2006.8 九、附錄九、附錄package 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ì)算

55、機(jī) 0801 - 37 -package sort;import java.awt.BorderLayout;import javax.swing.JButton;import javax.swing.JFileChooser;import javax.swing.JFrame;import javax.swing.JPanel;import javax.swing.JScrollPane;import javax.swing.JTable;import javax.swing.JTextField;import javax.swing.UIManager;import javax.swing

56、.UnsupportedLookAndFeelException;import com.birosoft.liquid.LiquidLookAndFeel;/* * 輸出界面 * */public class Interface extends JFrame JTextField text;JTable table;JFileChooser fileChooser;statictry/UIManager.setLookAndFeel(ch.randelshofer.quaqua.QuaquaLookAndFeel);UIManager.setLookAndFeel(new LiquidLook

57、AndFeel(); catch (UnsupportedLookAndFeelException e)/ TODO Auto-generated catch blocke.printStackTrace();public Interface() super(排課);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(nul

58、l);JPanel panel = new JPanel();text = new JTextField(15);BorderLayout layout = new BorderLayout();this.setLayout(layout);panel.add(text);JButton button = new JButton(選擇課程文件);button.setActionCommand(open);fileChooser = new JFileChooser(.);panel.add(button);button.addActionListener(new Listener(this);

59、table = new JTable(args,title);JScrollPane pane = new JScrollPane(table,JScrollPane.VERTICAL_SCROLLBAR_ALWAYS ,JScrollPane.HORIZONTAL_SCROLLBAR_ALWAYS);this.add(panel,BorderLayout.NORTH);this.add(pane,BorderLayout.CENTER);this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);this.setVisible(true);pack

60、age sort;import java.io.BufferedReader;import java.io.File;import java.io.FileNotFoundException;import 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 -

61、 39 -/* * 節(jié)點(diǎn)內(nèi)部類，用來存儲(chǔ)數(shù)據(jù) * 一是存儲(chǔ)課程名和學(xué)該課程前的前提課程 * 二是用來存儲(chǔ)課程安排次序和該次可學(xué)的內(nèi)容 */public class NodeString name;ArrayList baseList;/* * 空構(gòu)造器 */public Arranging() /* * 排課方法 * 第一次排課的課程是 Node 節(jié)點(diǎn)所代表課程該課程的前提課程是空，將其寫入ArrayList * 再將上次課程從剩余課程的前提課程中刪除，重復(fù)以上過程知道所有課程被排完或排了 * 8 次后仍未排完（大學(xué)教育只有四年，八個(gè)學(xué)期，若八次不能排完，說明課程安排存在問題， * 超出本方法

62、處理范圍、不予處理） * param filepath * return * throws */public ArrayList arrayclass(File filepath) 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)&(t+ = 8) Node s = new

63、Node();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)告 計(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)的前提課程已

64、修過課程for(String tem2:s.baseList) tem.baseList.remove(tem2);result.add(s);i +;return result;/返回/* * 文件讀取方法 * param * return */public ArrayList readFile(File filepath) throws DateException ,FileNotFoundException,IOExceptionArrayList list = new ArrayList();/File file = new File(filepath);BufferedReader

65、read= new BufferedReader(new LineNumberReader(new FileReader(filepath);try String temp;while(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(:);/按“：”拆分?jǐn)?shù)據(jù)結(jié)構(gòu)課程設(shè)

66、計(jì)報(bào)告 計(jì)算機(jī) 0801 - 41 -if(arg0.length != 2 ) throw new DateException();Node s = new Node();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;/* * 判斷是否有“：”號(hào) * param str * return */private boolean checkchar(String str) for(int i = 0;i str.length();i+) if(str.charA