《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告-線性表進(jìn)行算式計算、排課問題,JAVA語言,截圖完整

1、中南大學(xué)?數(shù)據(jù)結(jié)構(gòu)?課程設(shè)計報告指導(dǎo)教師 學(xué) 院 信息科學(xué)與工程學(xué)院 完成時間 2010年7月7日 目 錄 TOC o 1-3 h z u HYPERLINK l _Toc266454160 目 錄 PAGEREF _Toc266454160 h - 2 - HYPERLINK l _Toc266454161 題目一：利用線性表進(jìn)行算式計算 PAGEREF _Toc266454161 h - 1 - HYPERLINK l _Toc266454162 一、實驗名稱： PAGEREF _Toc266454162 h - 1 - HYPERLINK l _Toc266454163 二、需求分析：

2、PAGEREF _Toc266454163 h - 1 - HYPERLINK l _Toc266454164 三、概要設(shè)計 PAGEREF _Toc266454164 h - 1 - HYPERLINK l _Toc266454165 四、詳細(xì)設(shè)計 PAGEREF _Toc266454165 h - 3 - HYPERLINK l _Toc266454166 五、調(diào)試分析 PAGEREF _Toc266454166 h - 5 - HYPERLINK l _Toc266454167 六、測試結(jié)果 PAGEREF _Toc266454167 h - 5 - HYPERLINK l _Toc26

3、6454168 七、課程設(shè)計總結(jié) PAGEREF _Toc266454168 h - 7 - HYPERLINK l _Toc266454169 八、參考文獻(xiàn) PAGEREF _Toc266454169 h - 8 - HYPERLINK l _Toc266454170 九、附錄 PAGEREF _Toc266454170 h - 9 - HYPERLINK l _Toc266454171 題目三：排課問題 PAGEREF _Toc266454171 h - 21 - HYPERLINK l _Toc266454172 一、實驗名稱： PAGEREF _Toc266454172 h - 21

4、- HYPERLINK l _Toc266454173 二、需求分析： PAGEREF _Toc266454173 h - 21 - HYPERLINK l _Toc266454174 三、概要設(shè)計 PAGEREF _Toc266454174 h - 21 - HYPERLINK l _Toc266454175 四、詳細(xì)設(shè)計 PAGEREF _Toc266454175 h - 24 - HYPERLINK l _Toc266454176 五、調(diào)試分析 PAGEREF _Toc266454176 h - 33 - HYPERLINK l _Toc266454177 六、測試結(jié)果 PAGEREF

5、_Toc266454177 h - 33 - HYPERLINK l _Toc266454178 七、課程設(shè)計總結(jié) PAGEREF _Toc266454178 h - 34 - HYPERLINK l _Toc266454179 八、參考文獻(xiàn) PAGEREF _Toc266454179 h - 35 - HYPERLINK l _Toc266454180 九、附錄 PAGEREF _Toc266454180 h - 35 -題目一：利用線性表進(jìn)行算式計算一、實驗名稱：利用線性表進(jìn)行算式計算二、需求分析：設(shè)計任務(wù)：界面上出現(xiàn)一個文本框，輸入一個算式，點擊按鈕，顯示結(jié)果。該算式內(nèi)只含有數(shù)字、括號、

6、+、-、*、/、%這幾種字符，優(yōu)先級為：括號-%-*,/-+,-。如輸入：2+3*5，結(jié)果為17,輸入(2+3)*5結(jié)果為25。輸入格式有誤，需要給予提示。在算法中，必須實現(xiàn)對輸入的算式字符串的分析，而不僅僅是得到結(jié)果。(1)輸入的形式和輸入值的范圍：數(shù)字和運算符只含有括號、+、-、*、/、%。(2)輸出的形式：以數(shù)字和運算符組成的算式形式輸出。(3)程序所能到達(dá)的功能：對輸入數(shù)字和運算符進(jìn)行分析，并輸出分析結(jié)果。(4)測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。三、概要設(shè)計抽象數(shù)據(jù)類型的定義：ADT Stack 數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,n,

7、n0數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=1,2,n根本操作： InitStack(&S)； 初始化棧S，構(gòu)造一個空棧 StackEmpty(S)； 初始條件：棧S已存在操作結(jié)果：假設(shè)棧為空棧，那么返回true，否那么返回false StackLengthS；初始條件：棧S已存在操作結(jié)果：返回S的元素個數(shù)，即棧的長度GetTop(S,&e)初始條件：棧S已存在且非空操作結(jié)果：用e返回S的棧頂元素Push(&S,e)初始條件：棧S已存在操作結(jié)果：插入元素e為新的棧頂元素Pop(&S,&e)初始條件：棧S已存在且非空操作結(jié)果：刪除S的棧頂元素，并用e返回其值主程序的流程：定義鏈棧，判斷運算符優(yōu)先

8、級，實現(xiàn)具體計算，錯誤處理。四、詳細(xì)設(shè)計主要算法：(偽代碼)#define N 50#define OK 1#define ERROR 0#include #include typedef structint top;double arrayN;NumStack;typedef structint top;char arrayN;OpStack;/把字符轉(zhuǎn)換為相應(yīng)的整數(shù)的函數(shù)int Cint(char mychar)return (mychar-48);/數(shù)字進(jìn)棧的函數(shù)status PushNum(NumStack &numstack,double num)if(numstack.topN)

9、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,char &op)if(opstack.topN) opstack.top+;op

10、stack.arrayopstack.top-1=op;return OK;else return ERROR;/操作符出棧的函數(shù)status PopOp(OpStack &opstack,char &op)if(opstack.top) op=opstack.arrayopstack.top-1;opstack.top-;return OK;else return ERROR;/進(jìn)行運算的函數(shù)double Calc(double a,double b,char c)double result;五、調(diào)試分析1調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計與實現(xiàn)的討論和分析調(diào)試過程中，對于非法輸入的

11、測試很重要，對于一些不符合常規(guī)的輸入進(jìn)行測試，并針對存在的問題對源代碼進(jìn)行修改，可以對于非法輸入進(jìn)行提示。2算法的時間復(fù)雜性和可能的改良設(shè)想此算法的運行時間主要花在while循環(huán)上，它從頭到尾掃描后綴表達(dá)式中的每一個數(shù)據(jù)每個操作數(shù)或運算符均為一個數(shù)據(jù)，假設(shè)后綴表達(dá)式由n個數(shù)據(jù)組成，那么此算法的時間復(fù)雜度為O(n)。在轉(zhuǎn)換算法中，中綴算術(shù)表達(dá)式中的每個字符均需要掃描一遍，對于掃描到的每個運算符，最多需要進(jìn)行入棧、出棧和寫入后綴表達(dá)式這三次操作，對于掃描到的數(shù)字或小數(shù)點，只需要把它直接寫入到后綴表達(dá)式即可。所以，此算法的時間復(fù)雜度為O(n)，n為后綴表達(dá)式中字符的個數(shù)。六、測試結(jié)果 1、輸入：5+

12、6*3%22、輸入：3+5*8-2%4輸出：3、輸入:1*5+2 輸出：對不起！表達(dá)式有錯！4、輸入：123321123+456654456 7555E85、輸入：11116、輸入：53+2 輸出：對不起！表達(dá)式有錯！7、輸入：5+9*3-8/4%2 輸出：5+9*3-8/4%2= -Infinity 界面效果圖運行結(jié)果顯示-1 運行結(jié)果顯示-2七、課程設(shè)計總結(jié)通過本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，我有很多收獲，在此，我將我的親身感受回憶和總結(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)的本

13、質(zhì)是一種使數(shù)據(jù)結(jié)構(gòu)化的知識。通過理論課程的學(xué)習(xí)，使我初步了解了數(shù)據(jù)結(jié)構(gòu)的根本知識。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作的學(xué)科?，F(xiàn)代程序設(shè)計已轉(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è)計語言本身沒有任何聯(lián)系，唯一有的關(guān)系就是用程序語言去描述數(shù)據(jù)結(jié)構(gòu)。現(xiàn)今我們所學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)課程常用的描述語言主要有C、C+和JAVA等。數(shù)據(jù)結(jié)構(gòu)只是給我們提供處理常規(guī)問題的一個思路而已，講的是已經(jīng)成熟的編程思想和算法，適用于所有開發(fā)語言。所以說

14、，組織好數(shù)據(jù)結(jié)構(gòu)是寫程序的第一步。數(shù)據(jù)結(jié)構(gòu)是一門實踐性較強的計算機根底課程，為了學(xué)好這門課程，必須在掌握理論知識的同時，加強上機實踐。課程設(shè)計的目的就是要到達(dá)理論與實際應(yīng)用相結(jié)合，使我們能夠根據(jù)數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，同時強化對編程語言的使用，培養(yǎng)根本的、良好的程序設(shè)計能力。我于大二上學(xué)期從軟件學(xué)院軟件工程專業(yè)轉(zhuǎn)到信息學(xué)院計算機專業(yè)，在09年暑假中，我參加了軟件學(xué)院的JAVA實訓(xùn)，了解了一定的JAVA語言知識，因為本次課程設(shè)計要制作界面，所以選擇JAVA語言有它的優(yōu)勢。通過這次課程設(shè)計，我體會到要做出一個好的程序是很難的，盡管我花了一個

15、多星期去做這兩個工程，但這個程序還是不夠理想，只是到達(dá)一些根本的水平而已，跟那些功能強大的程序還是有很大的距離。這個程序還有一些地方值得完善的，比方算式計算中一些非法輸入如數(shù)字后面連續(xù)輸入括號無法判斷非法并影響計算結(jié)果等，這些問題需要程序員考慮得更全面，使實現(xiàn)的功能更完善，在今后不斷改良。在近兩周的課程設(shè)計中，我認(rèn)為最大的收獲就是在遇到問題時解決問題的過程。如對語言并不完全了解，如有些函數(shù)的操作需要通過查閱相關(guān)書籍和幫助來了解，另外，在入棧、出棧的算法設(shè)計中，曾因為思路不清晰而在編代碼時遇到了困難，對于運算符和數(shù)字的別離和判斷也曾困擾過我。我通過查閱書籍、上網(wǎng)搜索和向其他同學(xué)詢問，才得以最終完

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

17、CharStack() top=new CharNode(); top.c=#; sum=0; public char pop() /不作有沒有元素的判斷，統(tǒng)一在出棧前進(jìn)行判斷，假設(shè)沒有元素，那么不調(diào)用此函數(shù)char c=top.node.c;top.node=top.node.node;sum-;return c;public void push(char c)CharNode newNode=new CharNode();newNode.c=c;newNode.node=top.node;top.node=newNode;sum+;class CharNodeCharNode node;c

18、har 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)行判斷，假設(shè)沒有元素，那么不調(diào)用此函數(shù)char c=top.node.c;top.node=top.node.node;sum-;return c;public void push(char c)CharNode newN

19、ode=new CharNode();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.Insets;/* * GBCGridBagLayout * * author ibm * */public class GBC extends GridBagConstraints

20、/* * () * param x * param y */ public GBC(int x, int y) this.gridx = x; this.gridy = y; public GBC(int gridx, int gridy, int gridwidth, int gridheight) this.gridx = gridx; this.gridy = gridy; this.gridwidth = gridwidth; this.gridheight = gridheight; public GBC setAnchor(int anchor) this.anchor = anc

21、hor; return this; /* * 仯 * param fill * return */ public GBC setFill(int fill) this.fill = fill; return this; /* * * param weightx * param weighy * return */ public GBC setWeight(double weightx, double weighty) this.weightx = weightx; this.weighty = weighty; return this; /* * * param distance * retu

22、rn */ public GBC setInset(int distance) this.insets = new Insets(distance, distance, distance, distance); return this; /* * * 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(i

23、nt 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=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;

24、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; 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ōu)先級為-1，以便在主程序中能及時檢查

25、出錯誤 return i;package stack;import java.awt.BorderLayout;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import javax.swing.*;public class MainClass extends JFrame privateMainClass mainClass;JTabbedPane tab;JTextField input, output;JButton btnWork;private JTextArea txtaDisplay;

26、private JTextArea txtaInput;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();pu

27、blic void init() try UIManager.setLookAndFeel(com.nilo.plaf.nimrod.NimRODLookAndFeel); 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(nu

28、ll);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 getFirstPanel() JPanel pan

29、el = 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é)果);lblInput = new JLabel(輸入表達(dá)式：);bt

30、nProcess = 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, BorderLayout.CENTER);pnlSouth.add(lblInput, BorderL

31、ayout.NORTH);pnlSouth.add(scrInputPnl, BorderLayout.CENTER);pnl.add(btnProcess);panel.add(pnlNorth, BorderLayout.NORTH);panel.add(pnlSouth, BorderLayout.CENTER);panel.add(pnl, BorderLayout.SOUTH);btnProcess.addActionListener(new ActionListener() public void actionPerformed(ActionEvent e) String sour

32、ce = txtaInput.getText().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

33、 GetPriority();OperationClass operationFunction = new OperationClass();String str = inputStr + =; / 輸入一個正確的表達(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; / 這個字符變量在下面代碼中充當(dāng)存儲從運算符棧

34、中出棧的運算符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 & a priority.outSideStack(ch2);if (t)return true;elsereturn false;package stack;public class NumStack IntNode top; public NumStack() top=new

35、IntNode(); public float pop() /出棧 /對于頭結(jié)點，存整數(shù)類型的a屬性存的是棧內(nèi)的元素個數(shù) /對于出棧操作，由于本函數(shù)返回值為整數(shù)，故不進(jìn)行判斷是否棧內(nèi)還有元素， 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=newnode; top.a+; class IntNodeIntNo

36、de node;float a;public IntNode()node=null;a=0f;package stack;public class OperationClass /從numStack棧中依次取出兩個數(shù)字進(jìn)行相應(yīng)運算符的操作，結(jié)果再壓入numStack棧中public boolean operation(char chInStack,NumStack numStack,CharStack charStack) float a; float b;switch(chInStack) case +: if(numStack.top.a=2)a=numStack.pop();b=numS

37、tack.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;elsereturn false; case /: if(numStac

38、k.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();b=numStack.pop();float t=b;for(int i=1;ia;i+)b*=t;nu

39、mStack.push(b);return true;elsereturn false; case (: return true; default : return true;題目三：排課問題一、實驗名稱：排課問題二、需求分析：設(shè)計任務(wù)：在中保存假設(shè)干門課程，以及該課程需要哪些前續(xù)課程。要求一門課程需要一個學(xué)期才能學(xué)完。保存格式為例如：大學(xué)物理C語言Java語言:C語言微積分高級物理學(xué):微積分,大學(xué)物理界面上，首先出現(xiàn)一個按鈕，點擊，載入conf.txt。點擊另一個按鈕，顯示需要幾個學(xué)期上完這些課程，每學(xué)期各學(xué)習(xí)哪些課程。(1)輸入的形式和輸入值的范圍：讀入文件。(2)輸出的形式：文本輸出。(

40、3)程序所能到達(dá)的功能：從文件中讀出數(shù)據(jù)，采用拓?fù)渑判颍@示出各學(xué)期需要學(xué)習(xí)哪些課程。(4)測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。三、概要設(shè)計1ADT Stack 數(shù)據(jù)對象：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)造一個空棧 StackEmpty(S)； 初始條件：棧S已存在操作結(jié)果：假設(shè)棧為空棧，那么返回true，否那么返回false StackLengthS；初始條件：棧S已存在操作結(jié)果：返回S的元素個數(shù)，即棧的長度GetTop(S,&e)初始條

41、件：棧S已存在且非空操作結(jié)果：用e返回S的棧頂元素Push(&S,e)初始條件：棧S已存在操作結(jié)果：插入元素e為新的棧頂元素Pop(&S,&e)初始條件：棧S已存在且非空操作結(jié)果：刪除S的棧頂元素，并用e返回其值2函數(shù)框圖函數(shù)名函數(shù)功能Main總控函數(shù)InitStack初始化棧Pop出棧Push進(jìn)棧StackEmpty棧的判空CreatGraph創(chuàng)立圖FindInDegree求圖中頂點入度TopologicalSort拓?fù)渑判?函數(shù)流程圖： 1主函數(shù)流程圖：2求入度函數(shù)的流程圖： 3創(chuàng)立圖的流程圖： 4拓?fù)渑判蚝瘮?shù)的流程圖：四、詳細(xì)設(shè)計1拓?fù)渑判蛑饕惴ǎ篠tatus TopologicalS

42、ort(ALGraph G)/有向圖G采用鄰接表存儲結(jié)構(gòu)/假設(shè)G無回路，那么輸出G的頂點的一個拓?fù)渑判蛐蛄胁⒎祷豋K，否那么返回ERROR。FindInDegree(G,indegree); /對各頂點求入度indegree0.vernum-1InitStack(S);for(i=0;inextarc) k=p-adjvex; if(!(-indegreek) Push(S,k); /假設(shè)入度減為0，那么入棧 /for/whileif(countbase=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType);if(!S-base)printf(

43、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-base)return ERROR;*e=*-S-top;return 0;進(jìn)棧操作函數(shù)原型void Push(SqStack *S，ElemType e)功能

44、：插入元素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-stacksize;*S-top+=e;判斷棧是否為空的函數(shù)原型i

45、nt StackEmpty(SqStack *S)功能：判斷棧是否為空參數(shù)：SqStack *S返回值：int源代碼：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 *p;printf(請輸入頂點數(shù)和邊數(shù):);scanf(%d%d,&G-vexnum,&G-arcnum);fo

46、r (i = 1; i vexnum; i+)G-verticesi.data = i;G-verticesi.firstarc = NULL;for (i = 1; i arcnum; i+) /輸入存在邊的點集合printf(n請輸入存在邊的兩個頂點的序號:);scanf(%d%d,&n,&m);while (n G-vexnum | m G-vexnum)printf(輸入的頂點序號不正確 請重新輸入:);scanf(%d%d,&n,&m);p = (ArcNode*)malloc(sizeof(ArcNode);if (p = NULL)printf(memory allocation

47、 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-nextarc)printf(%3d,p-adjvex);printf(n);求入度操作函數(shù)原型void FindInDegree(ALGraph G, int ind

48、egree)功能：求圖中頂點的入度參數(shù)：ALGraph G, int indegree返回值：void源代碼：void FindInDegree(ALGraph G, int indegree)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) 功能：將一個偏序排列成一個全序參數(shù)：ALGraph G返回值：void源代碼：v

49、oid TopologicalSort(ALGraph G) /進(jìn)行拓?fù)渑判騣nt indegreeM;/存放頂點的入度int i, k, n;int count = 0;ArcNode *p;SqStack S;FindInDegree(G, indegree);InitStack(&S);for (i = 1; i = G.vexnum; i+)printf(第%d個點的入度為%d n, i, indegreei);printf(n);for ( i = 1; i nextarc)k = p-adjvex;if (!(-indegreek)Push(&S,k);printf(n);if (

50、count G.vexnum)/該有向圖有回路printf(出現(xiàn)錯誤n);elseprintf(排序成功n);2存儲結(jié)構(gòu)：(1),表結(jié)點typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;ArcNode;(2),鏈表的存儲結(jié)構(gòu)typedef struct VNodeint data;ArcNode *firstarc;VNode,AdjListMAX_VEXTEX_NUM;(3),圖的存儲結(jié)構(gòu)typedef structAdjList vertices;int vexnum, arcnum;ALGraph;(4),棧的存儲結(jié)構(gòu)typ

51、edef struct ElemType *base;ElemType *top;int stacksize;SqStack;五、調(diào)試分析算法的時間復(fù)雜性和可能的改良設(shè)想該拓?fù)渑判蛩惴ǎ瑢τ衝個頂點和e條弧的有向圖而言，建立求各頂點的入度的時間復(fù)雜度為O(e)；建立入度頂點棧的時間復(fù)雜度為O(n)；在拓?fù)渑判蜻^程中，假設(shè)有向圖無環(huán)，那么每個頂點進(jìn)一次棧，出一次棧，入度減1的操作在while語句中總共執(zhí)行e詞，所以，總的時間復(fù)雜度為O(n+e)。六、測試結(jié)果 界面效果圖 翻開文件效果圖 運行結(jié)果七、課程設(shè)計總結(jié)在近兩周的課程設(shè)計中，我認(rèn)為最大的收獲就是在遇到問題時解決問題的過程。如對語言并不完全

52、了解，如有些函數(shù)的操作需要通過查閱相關(guān)書籍和幫助來了解，同時也向其他同學(xué)詢問，才得以最終完成工程。這次課程設(shè)計，培養(yǎng)了我自己的實際分析能力、編程和動手能力，最終目標(biāo)是想通過這種形式，幫助自己更加系統(tǒng)的掌握數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容；培養(yǎng)了自己對JAVA語言程序設(shè)計的興趣，更加有信心學(xué)好這門課程；設(shè)計了一個拓?fù)渑判虺绦?，解決實際問題，將所學(xué)內(nèi)容運用到實際當(dāng)中。通過這次課程設(shè)計，我學(xué)到了很多，同時也認(rèn)識到了自己的缺乏。學(xué)校的課程不能將所有的知識都講授給我們，所以要想學(xué)好一門課程，我們應(yīng)該充分利用課余時間多看專業(yè)相關(guān)的書籍，豐富自己的知識。同時，作為計算機專業(yè)的學(xué)生，動手能力也是非常重要的，在掌握了理論知識

53、后應(yīng)多多上機實踐。只有多多實踐，才能更好地學(xué)習(xí)好一門語言，更好地理解課程的內(nèi)容。八、參考文獻(xiàn)【1】 清華大學(xué)計算機系列教材數(shù)據(jù)結(jié)構(gòu)(C語言版)/嚴(yán)蔚敏，吳偉民編著北京：清華大學(xué)出版社，2006.8 九、附錄package sort.test;import sort.Interface;public class Outmain /* * param args */public static void main(String args) new Interface();package sort;import java.awt.BorderLayout;import javax.swing.JBut

54、ton;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.UnsupportedLookAndFeelException;import com.birosoft.liquid.LiquidLookAndFeel;

55、/* * 輸出界面 * */public class Interface extends JFrame JTextField text;JTable table;JFileChooser fileChooser;statictry/UIManager.setLookAndFeel(ch.randelshofer.quaqua.QuaquaLookAndFeel);UIManager.setLookAndFeel(new LiquidLookAndFeel(); catch (UnsupportedLookAndFeelException e)/ TODO Auto-generated catc

56、h blocke.printStackTrace();public Interface() super(排課);init();private void init() String title = new String學(xué)期,所修課程;String args = new String00;this.setSize(480, 320);this.setLocationRelativeTo(null);JPanel panel = new JPanel();text = new JTextField(15);BorderLayout layout = new BorderLayout();this.s

57、etLayout(layout);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_A

58、LWAYS ,JScrollPane.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 j

59、ava.io.FileReader;import java.io.IOException;import java.io.LineNumberReader;import java.util.ArrayList;import Exception.DateException;/* * * 實現(xiàn)排課類 * */public class Arranging /* * 節(jié)點內(nèi)部類，用來存儲數(shù)據(jù) * 一是存儲課程名和學(xué)該課程前的前提課程 * 二是用來存儲課程安排次序和該次可學(xué)的內(nèi)容 */public class NodeString name;ArrayList baseList;/* * 空構(gòu)造器 */p

60、ublic Arranging() /* * 排課方法 * 第一次排課的課程是Node節(jié)點所代表課程該課程的前提課程是空，將其寫入ArrayList * 再將上次課程從剩余課程的前提課程中刪除，重復(fù)以上過程知道所有課程被排完或排了 * 8次后仍未排完大學(xué)教育只有四年，八個學(xué)期，假設(shè)八次不能排完，說明課程安排存在問題， * 超出本方法處理范圍、不予處理 * param filepath * return * throws */public ArrayList arrayclass(File filepath) throws DateException, FileNotFoundException