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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 計算機(jī)0801 中南大學(xué) 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告 指導(dǎo)教師 學(xué) 院 信息科學(xué)與工程學(xué)院 完成時間 2010年7月7日 目 錄 目 錄 - 2 - 題目一：利用線性表進(jìn)行算式計算 - 1 - 一、實驗名稱： - 1 -

2、 二、需求分析： - 1 - 三、概要設(shè)計 - 1 - 四、詳細(xì)設(shè)計 - 3 - 五、調(diào)試分析 - 5 - 六、測試結(jié)果 - 5 - 七、課程設(shè)計總結(jié) - 7 - 八、參考文獻(xiàn) - 8 - 九、附錄 - 9 - 題目三：排課問題 - 21 - 一、實驗名稱： - 21 - 二、需求分析： - 21 - 三、概要設(shè)計 - 21 - 四、詳細(xì)設(shè)計 - 24 - 五、調(diào)試分析 - 33 - 六、測試結(jié)果 - 33 - 七、課程設(shè)計總結(jié) - 34 - 八、參考文獻(xiàn) - 35 - 九、附錄 - 35 - - 45 - 題目一：利用線性表進(jìn)行算式計算 一、

3、實驗名稱： 利用線性表進(jìn)行算式計算 二、需求分析： 設(shè)計任務(wù)： 界面上出現(xiàn)一個文本框，輸入一個算式，點擊按鈕，顯示結(jié)果。該算式內(nèi)只含有數(shù)字、括號、+、-、*、/、%這幾種字符，優(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、4)測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。 三、概要設(shè)計 抽象數(shù)據(jù)類型的定義： ADT Stack { 數(shù)據(jù)對象：D={ai|ai?ElemSet,i=1,2,…n, n30} 數(shù)據(jù)關(guān)系：R1={|ai-1,ai?D,i=1,2,…,n} 基本操作： ??? InitStack(&S)； ??? ／／初始化棧S，構(gòu)造一個空棧 ??? StackEmpty(S)； ??? ／／初始條件：棧S已存在 操作結(jié)果：若棧為空棧，則返回true，否則返回false ??? StackLength（S）

5、； ／／初始條件：棧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)先級，實現(xiàn)具體計算，錯誤處理。 四、詳細(xì)設(shè)計 主要算法：(偽代碼) #define N 50 #define OK 1 #define ERROR 0 #include

6、 #include typedef struct{ int top; double array[N]; }NumStack; typedef struct{ int top; char array[N]; }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.top {numstack.top++; numsta

7、ck.array[numstack.top-1]=num; return OK; } else return ERROR; } //數(shù)字出棧的函數(shù) status PopNum(NumStack &numstack,double &num){ if(numstack.top>０){ num=numstack.array[numstack.top-1]; numstack.top--; return OK; } else return ERROR; } //操作符進(jìn)棧的函數(shù) status PushOp(OpStack &opstack,char &op){ if(o

8、pstack.top opstack.top++; opstack.array[opstack.top-1]=op; return OK; } else return ERROR; } //操作符出棧的函數(shù) status PopOp(OpStack &opstack,char &op){ if(opstack.top>０){ op=opstack.array[opstack.top-1]; opstack.top--; return OK; } else return ERROR; } //進(jìn)行運算的函數(shù) double Calc(dou

9、ble a,double b,char c){ double result; 五、調(diào)試分析 1．調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計與實現(xiàn)的討論和分析 調(diào)試過程中，對于非法輸入的測試很重要，對于一些不符合常規(guī)的輸入進(jìn)行測試，并針對存在的問題對源代碼進(jìn)行修改，可以對于非法輸入進(jìn)行提示。 2．算法的時間復(fù)雜性和可能的改進(jìn)設(shè)想 此算法的運行時間主要花在while循環(huán)上，它從頭到尾掃描后綴表達(dá)式中的每一個數(shù)據(jù)（每個操作數(shù)或運算符均為一個數(shù)據(jù)），若后綴表達(dá)式由n個數(shù)據(jù)組成，則此算法的時間復(fù)雜度為O(n)。 在轉(zhuǎn)換算法中，中綴算術(shù)表達(dá)式中的每個字符均需要掃描一遍，對于掃描到的每個運算符

10、，最多需要進(jìn)行入棧、出棧和寫入后綴表達(dá)式這三次操作，對于掃描到的數(shù)字或小數(shù)點，只需要把它直接寫入到后綴表達(dá)式即可。所以，此算法的時間復(fù)雜度為O(n)，n為后綴表達(dá)式中字符的個數(shù)。 六、測試結(jié)果 1、輸入：5+6*3%2 輸出：5+6*3%2=11.0 2、輸入：3+5*（8-2）%4 輸出：3+5*（8-2）%4=13.0 3、輸入:1*5++2 輸出：對不起！表達(dá)式有錯！ 4、輸入：123321123+456654456 輸出：123321123+456654456=5.7997555E8 5、輸入：1111 輸出：1111=1111.0 6、輸入

11、：5（3+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)的本質(zhì)是一種使數(shù)據(jù)結(jié)構(gòu)化

12、的知識。通過理論課程的學(xué)習(xí)，使我初步了解了數(shù)據(jù)結(jié)構(gòu)的基本知識。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的關(guān)系和操作的學(xué)科。現(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ā)語言。所以說，組織好數(shù)據(jù)結(jié)構(gòu)是

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

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

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

16、 九、附錄 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.node.node; sum--; return c;

17、} public void push(char c) { CharNode newNode=new CharNode(); newNode.c=c; newNode.node=top.node; top.node=newNode; sum++; } } class CharNode { CharNode node; char c; public CharNode() { node=null; c=' '; } } package stack; public class CharStack { Char

18、Node 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; sum--; return c; } public void push(char c) { CharNode newNode=new Ch

19、arNode(); 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.GridBagConstraints; import java.awt.Insets; /** * ????GBC?????????

20、????????GridBagLayout?????????????????????? * λ?á???С??????????????? * @author ibm * */ public class GBC extends GridBagConstraints { /** * ??????????λ??(λ??????????) * @param x * @param y */ public GBC(int x, int y) { this.gridx = x; this.gridy = y; }

21、 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 = anchor; return this; } /** * ??????

22、??????????????????С????????С????????仯??? * @param fill * @return */ public GBC setFill(int fill) { this.fill = fill; return this; } /** * ?????????????? * @param weightx * @param weighy * @return */ public GBC setWeight(double weightx, double wei

23、ghty) { this.weightx = weightx; this.weighty = weighty; return this; } /** * ???????????????????????С * @param distance * @return */ public GBC setInset(int distance) { this.insets = new Insets(distance, distance, distance, distance); return this;

24、 } /** * ???????????????????????С * @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 =

25、 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 '/':

26、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; case '-': i=2;break;

27、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，以便在主程序中能及時檢查出錯誤 } return i; } } package stack; import java.awt.BorderLayout; import java.awt.event.Act

28、ionEvent; 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 txt

29、aDisplay; 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

30、(String[] args) { new MainClass().init(); } public void init() { try { UIManager.setLookAndFeel("com.nilo.plaf.nimrod.NimRODLookAndFeel"); } catch (Exception e) { try { UIManager.setLookAndFeel(UIManager .getSystemLookAndFeelClassName()); } catch (Exception e1) {

31、 } } mainClass = new MainClass(); this.setTitle("數(shù)據(jù)結(jié)構(gòu)"); this.setSize(500, 400); this.setLocationRelativeTo(null); this.setDefaultCloseOperation(EXIT_ON_CLOSE); this.add(this.getJTabbedPane(), BorderLayout.CENTER); this.setVisible(true); } public JTabbedPane getJTabbe

32、dPane() { tab = new JTabbedPane(); tab.addTab("線性表", getFirstPanel()); tab.addTab("Huffman", new JPanel()); return tab; } public JPanel getFirstPanel() { JPanel panel = new JPanel(); panel.setLayout(new BorderLayout()); txtaDisplay = new JTextArea(8, 10); txtaDisplay.setE

33、ditable(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(); pnlSouth = new

34、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(scrIn

35、putPnl, 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 so

36、urce = 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

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

38、echar = true; boolean rku = false; int lku = 0; int l = 0; char chInStack; // 這個字符變量在下面代碼中充當(dāng)存儲從運算符棧中出棧的運算符 for (int i = 0; i < charArray.length; i++) { if (charArray[0] == ')') { judgechar = false; break; } if (charArray[i] == '=' && charArray.length > i + 1) {

39、 judgechar = false; break; } if (mainClass.judge(charArray[i])) { if (d == true) { float k = (float) (charArray[i] - '0'); for (int j = 0; j < l; j++) { k = k / 10; } a += k; l++; } else { a = a * 10f + (float) (int) (charArray[i]

40、- '0'); } f = true; // 證明a確實被更改過 } else if (charArray[i] == '.') { d = true; l = 1; } else // 如果遇到運算符，把數(shù)字壓入棧中 { if (true == f) { numStack.push(a); a = 0f; f = false; d = false; l = 1; if (charArray[i] == '(') { lku++;

41、 } else if (charArray[i] == ')') { lku--; rku = true; } } else // 當(dāng)a沒有被改變過但又接到一個運算符，這時我們得判斷一下表達(dá)示的正確性了 { if (charArray[i] == '(') { if (rku) { judgechar = false; break; } else { lku++; } } else if (charArray[i]

42、 == ')') { lku--; rku = true; } else { if (rku) { rku = false; } else { judgechar = false; break; } } } if (priority.outSideStack(charArray[i]) == -1) { judgechar = false; break; } // 在這里開始填寫運算符壓入或

43、出棧操作代碼 if (charStack.sum == 0) { charStack.push(charArray[i]); } else { chInStack = charStack.pop(); while (true) { if (mainClass.inOrOut(chInStack, charArray[i])) { // 這里填寫運算符要出棧的代碼 if (operationFunction.operation(chInStack, numStack, c

44、harStack)) { if (chInStack == '(' && charArray[i] == ')') { break; } // 運算完括號內(nèi)的表達(dá)示之后，停止循環(huán)（同時，括號外的“）”不應(yīng)壓入棧中） else if (charStack.sum == 0) { if (charArray[i] == '=') break; else { charStack.push(charArray[i]); br

45、eak; } } else { chInStack = charStack.pop(); } } else { judgechar = false; break; } } else { charStack.push(chInStack); charStack.push(charArray[i]); break; } } } } } if

46、 (judgechar == true && lku == 0) { if (numStack.top.a != 1) result = "對不起！表達(dá)式有錯！"; else result = str + " " + numStack.pop(); } else result = "對不起！表達(dá)式有錯！"; return result; } public boolean judge(char c) { int a; a = (int) (c - '0'); if (a >= 0 && a <= 9)

47、return true; else return false; } public boolean inOrOut(char ch1, char ch2) // 運算符若要出棧，則返回true，否則返回false,ch1代表棧內(nèi)的運算符 { GetPriority priority = new GetPriority(); // 判斷棧內(nèi)和棧外的運算符的優(yōu)先級 boolean t = priority.inSideStack(ch1) > priority.outSideStack(ch2); if (t) return true;

48、else return false; } } package stack; public class NumStack { IntNode top; public NumStack() { top=new IntNode(); } public float pop() //出棧 { //對于頭結(jié)點，存整數(shù)類型的a屬性存的是棧內(nèi)的元素個數(shù) //對于出棧操作，由于本函數(shù)返回值為整數(shù)，故不進(jìn)行判斷是否棧內(nèi)還有元素， //而是在調(diào)用此函數(shù)前，通過top.a的值進(jìn)行判斷 float

49、 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 IntNode { IntNode node; float a; public In

50、tNode() { 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) { cas

51、e '+': if(numStack.top.a>=2){a=numStack.pop();b=numStack.pop();numStack.push(a+b);return true;}else{return false;} case '-': if(numStack.top.a>=2){a=numStack.pop();b=numStack.pop();numStack.push(b-a);return true;}else{return false;} case '*': if(numStack.top.a>=2){a=numStack.pop();b=numSta

52、ck.pop();numStack.push(a*b);return true;}else{return false;} case '/': if(numStack.top.a>=2){a=numStack.pop();b=numStack.pop();numStack.push(b/a);return true;}else{return false;} case '%': if(numStack.top.a>=2){a=numStack.pop();b=numStack.pop();numStack.push(b%a);return true;}else{return f

53、alse;} case '^': if(numStack.top.a>=2){a=numStack.pop();b=numStack.pop();float t=b;for(int i=1;i

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

55、ck { 數(shù)據(jù)對象：D={ai|ai?ElemSet,i=1,2,…n, n30} 數(shù)據(jù)關(guān)系：R1={|ai-1,ai?D,i=1,2,…,n} 基本操作： ??? InitStack(&S)； ??? ／／初始化棧S，構(gòu)造一個空棧 ??? StackEmpty(S)； ??? ／／初始條件：棧S已存在 操作結(jié)果：若棧為空棧，則返回true，否則返回false ??? StackLength（S）； ／／初始條件：棧S已存在 操作結(jié)果：返回S的元素個數(shù)，即棧的長度 GetTop(S,&e) ／／初始條件：棧S已存在

56、且非空 操作結(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ù)渑判? 3．函數(shù)流程圖： （1）主函數(shù)流程圖： （2）求入度

57、函數(shù)的流程圖： （3）創(chuàng)建圖的流程圖： （4）拓?fù)渑判蚝瘮?shù)的流程圖： 四、詳細(xì)設(shè)計 1．拓?fù)渑判蛑饕惴ǎ? Status TopologicalSort(ALGraph G){ //有向圖G

58、采用鄰接表存儲結(jié)構(gòu) //若G無回路，則輸出G的頂點的一個拓?fù)渑判蛐蛄胁⒎祷豋K，否則返回ERROR。 FindInDegree(G,indegree); //對各頂點求入度indegree[0..vernum-1] InitStack(S); for(i=0;i

59、G.vertices[i].data); ++count; //輸出i號頂點并計數(shù) for(p=G.vertices[i].firstarc;p;p=p->nextarc){ k=p->adjvex; if(!(--indegree[k])) Push(S,k); //若入度減為0，則入棧 } //for }//while if(count

60、功能：總控功能； 參數(shù)：void 返回值：0。 源代碼： int main(void) { ALGraph G; printf("歡迎進(jìn)入拓?fù)渑判虻某绦?!\n"); CreatGraph(&G); TopologicalSort(G); return 0; } l 初始化棧函數(shù) 原型：void InitStack(SqStack *S) 功能：構(gòu)造一個空棧 參數(shù)：SqStack *S 返回值：void 源代碼： void InitStack(SqStack *S)// { S->base=(ElemType *)ma

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

62、 *S,ElemType *e) { if(S->top==S->base) { return ERROR; } *e=*--S->top; return 0; } l 進(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=(ElemTyp

63、e*)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; } l 判斷棧是否為空的函數(shù) 原型int StackEmpty(SqStack *S) 功能：判斷棧是否為空 參數(shù)：SqStack *S 返回值：int 源代碼：

64、int StackEmpty(SqStack *S) { if(S->top==S->base) return OK; else return ERROR; } l 創(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);

65、 for (i = 1; i <= G->vexnum; i++) { G->vertices[i].data = i; G->vertices[i].firstarc = NULL; } for (i = 1; i <= G->arcnum; i++) //輸入存在邊的點集合 { printf("\n請輸入存在邊的兩個頂點的序號:"); scanf("%d%d",&n,&m); while (n < 0 || n > G->vexnum || m < 0 || m > G->vexnum) { printf("輸入的頂點序

66、號不正確 請重新輸入:"); scanf("%d%d",&n,&m); } p = (ArcNode*)malloc(sizeof(ArcNode)); if (p == NULL) { printf("memory allocation failed,goodbey"); exit(1); } p->adjvex = m; p->nextarc = G->vertices[n].firstarc; G->vertices[n].firstarc = p; } printf("建立的鄰接表為:\n"); //輸出建立好的鄰接表 for(i = 1; i <= G->vexnum; i++) { printf("%d",G->vertices[i].data); for(p = G->vertices[i].firstarc; p; p = p->nextarc) printf("%3d",p->adjvex); printf("\n"); } } l