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

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

3、式字符串的分析，而不僅僅是得 到結(jié)果。 (1)輸入的形式和輸入值的范圍：數(shù)字和運算符（只含有括號、+、-、*、/、%） 。 (2)輸出的形式：以數(shù)字和運算符組成的算式形式輸出。 (3)程序所能達(dá)到的功能：對輸入數(shù)字和運算符進(jìn)行分析，并輸出分析結(jié)果。 (4)測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。 三、概要設(shè)計三、概要設(shè)計 抽象數(shù)據(jù)類型的定義： adt stack 數(shù)據(jù)對象：d=ai|aielemset,i=1,2,n, n0 數(shù)據(jù)關(guān)系：r1=|ai-1,aid,i=1,2,n 基本操作： initstack( double arrayn; numstack; type

4、def struct int 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.arraynumstack.top-1=num; return ok; else return error; /數(shù)字出棧的函數(shù) status popnum(numstack numstack.top-; return ok; else return error; /操作符進(jìn)棧的函數(shù) status pushop(op

5、stack opstack.arrayopstack.top-1=op; return ok; else return error; /操作符出棧的函數(shù) status popop(opstack opstack.top-; return ok; else return error; /進(jìn)行運算的函數(shù) double calc(double a,double b,char c) double result; 五、調(diào)試分析五、調(diào)試分析 1調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計與實現(xiàn)的討論和分析 調(diào)試過程中，對于非法輸入的測試很重要，對于一些不符合常規(guī)的輸入進(jìn) 行測試，并針對存在的問題對源代碼進(jìn)行

6、修改，可以對于非法輸入進(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á)式中的每個字符均需要掃描一遍，對于掃描 到的每個運算符，最多需要進(jìn)行入棧、出棧和寫入后綴表達(dá)式這三次操作，對 于掃描到的數(shù)字或小數(shù)點，只需要把它直接寫入到后綴表達(dá)式即可。所以，此 算法的時間復(fù)雜度為 o(n)，n 為后綴表達(dá)式中字符的個數(shù)。 六、測試結(jié)果六、測試結(jié)果 1、輸入：5+6*3%2 輸出：5+6*3

7、%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、輸入：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è)計總結(jié) 通過本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，我有很多收獲，在此，我將我的親身感受回 顧和

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

9、述數(shù)據(jù)結(jié)構(gòu)?，F(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)是寫程序的第一步。 數(shù)據(jù)結(jié)構(gòu)是一門實踐性較強(qiáng)的計算機(jī)基礎(chǔ)課程，為了學(xué)好這門課程，必須 在掌握理論知識的同時，加強(qiáng)上機(jī)實踐。課程設(shè)計的目的就是要達(dá)到理論與實 際應(yīng)用相結(jié)合，使我們能夠根據(jù)數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的方法，能把 現(xiàn)實世界中的實際問題在計算機(jī)內(nèi)部表示出來，同時強(qiáng)化對編程語言的使用， 培養(yǎng)基本的、良好的程序設(shè)計能力。 我于大二上學(xué)期從軟件學(xué)院軟件工程專業(yè)轉(zhuǎn)到信息學(xué)院計算

10、機(jī)專業(yè)，在 09 年暑假中，我參加了軟件學(xué)院的 java 實訓(xùn)，了解了一定的 java 語言知識，因 為本次課程設(shè)計要制作界面，所以選擇 java 語言有它的優(yōu)勢。 通過這次課程設(shè)計，我體會到要做出一個好的程序是很難的，盡管我花了 一個多星期去做這兩個項目，但這個程序還是不夠理想，只是達(dá)到一些基本的 水平而已，跟那些功能強(qiáng)大的程序還是有很大的距離。這個程序還有一些地方 值得完善的，比如算式計算中一些非法輸入（如數(shù)字后面連續(xù)輸入括號無法判 斷非法并影響計算結(jié)果等） ，這些問題需要程序員考慮得更全面，使實現(xiàn)的功能 更完善，在今后不斷改進(jìn)。 在近兩周的課程設(shè)計中，我認(rèn)為最大的收獲就是在遇到問題時解決

11、問題的 過程。如對語言并不完全了解，如有些函數(shù)的操作需要通過查閱相關(guān)書籍和幫 助來了解，另外，在入棧、出棧的算法設(shè)計中，曾因為思路不清晰而在編代碼 時遇到了困難，對于運算符和數(shù)字的分離和判斷也曾困擾過我。我通過查閱書 籍、上網(wǎng)搜索和向其他同學(xué)詢問，才得以最終完成項目。 通過這次課程設(shè)計，我學(xué)到了很多，同時也認(rèn)識到了自己的不足。學(xué)校的 課程不能將所有的知識都講授給我們，所以要想學(xué)好一門課程，我們應(yīng)該充分 利用課余時間多看專業(yè)相關(guān)的書籍，豐富自己的知識。同時，作為計算機(jī)專業(yè) 的學(xué)生，動手能力也是非常重要的，在掌握了理論知識后應(yīng)多多上機(jī)實踐。只 有多多實踐，才能更好地學(xué)習(xí)好一門語言，更好地理解課程的

12、內(nèi)容。 八、參考文獻(xiàn)八、參考文獻(xiàn) 【1】 清華大學(xué)計算機(jī)系列教材數(shù)據(jù)結(jié)構(gòu)(c c語言版)/嚴(yán)蔚敏，吳偉民編著 北京：清華大學(xué)出版社，2007.4 【2】 java jdk 5.0 學(xué)習(xí)筆記/良葛格編著北京：清華大學(xué)出版社， 2006.8 九、附錄九、附錄 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ù)

13、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 charnode charnode node; char c; public charnode() node=null; c= ; package stack; public class charstack charnode top;

14、 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 charnode(); newnode.c=c; newnode.node=top.node; top.node=newnode; sum+; cl

15、ass charnode charnode 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 /* * () * param x * param y */ public gbc(int x, int y) this.gridx =

16、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 = anchor; return this; /* * 仯 * param fill * return */ public gbc setfill(

17、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 * return */ public gbc setinset(int distance) this.insets = new insets(dist

18、ance, 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(int ipadx, int ipady) this.ipadx = ipadx; this.ipady = ipady; return t

19、his; 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; case (: i=1;break; return i; public int outsidestack(char c) int i=0;

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

21、java.awt.event.actionevent; 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 txtadisp

22、lay; 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 maincla

23、ss().init(); public 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.setlo

24、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

25、 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é)果

26、); 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

27、ayout.center); pnlsouth.add(lblinput, borderlayout.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() pub

28、lic 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 = new numstack(); getprior

29、ity 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 judgechar = true; boolean rku =

30、 false; int lku = 0; int l = 0; char chinstack; / 這個字符變量在下面代碼中充當(dāng)存儲從運算符棧中出棧的運算 符 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; package stack; public clas

31、s 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 t=top.node.a; top.node=top.node.node; top.a-; return t; public void push(float a) /進(jìn)棧 intnode newnode=new intnode(); newno

32、de.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棧中依次取出兩個數(shù)字進(jìn)行相應(yīng)運算符的操作，結(jié)果再壓入numstack棧 中 public boolean operation(char chinstack,numstack numstack,charstack charstack) fl

33、oat 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;elsereturn false; case *: if(numstack.top.a=2)a=numstack.pop()

34、;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(b%a);return true;elsereturn false; case : if(n

35、umstack.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è)計任務(wù)： 在文件 conf.txt 中保存若干門課程，以及該課程需要哪些前續(xù)課程。要求 一門課程需要一個學(xué)期才能學(xué)完。保存格式為例如： 大學(xué)物理

36、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è)計三、概要設(shè)計 1adt stack 數(shù)據(jù)對象：d=ai|aielemset,i=1,2,n, n0 數(shù)據(jù)關(guān)系：r1=|ai-1,aid,i=1,2

37、,n 基本操作： initstack( /對各頂點求入度 indegree0.vernum-1 initstack(s); for(i=0;inextarc) k=p-adjvex; if(!(-indegreek) push(s,k); /若入度減為 0，則入棧 /for /while if(countbase=(elemtype *)malloc(stack_init_size*sizeof(elemtype); if(!s-base) printf(memory allocation failed, goodbye); exit(1); s-top=s-base; s-stacksize

38、=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) 功能：插入元素 e 為新的棧頂元素 參數(shù)：sqstack *s，elemtype e 返回值：voi

39、d 源代碼： 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ù) 原型 int stackempty(sqstack *s) 功能：判

40、斷棧是否為空 參數(shù)：sqstack *s 返回值：int 源代碼： int stackempty(sqstack *s) if(s-top=s-base) return ok; else return 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, for (i = 1; i vexnum; i+) g-ver

41、ticesi.data = i; g-verticesi.firstarc = null; for (i = 1; i arcnum; i+) /輸入存在邊的點集合 printf(n 請輸入存在邊的兩個頂點的序號:); scanf(%d%d, while (n g-vexnum | m g-vexnum) printf(輸入的頂點序號不正確 請重新輸入:); scanf(%d%d, p = (arcnode*)malloc(sizeof(arcnode); if (p = null) printf(memory allocation failed,goodbey); exit(1); p-ad

42、jvex = 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 indegree) 功能：求圖中頂點的入度

43、 參數(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 源代碼： vo

44、id topologicalsort(algraph g) /進(jìn)行拓?fù)渑判?int indegreem;/存放頂點的入度 int i, k, n; int count = 0; arcnode *p; sqstack s; findindegree(g, indegree); initstack( 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( printf(n)

45、; if (count g.vexnum)/該有向圖有回路 printf(出現(xiàn)錯誤n); else printf(排序成功n); 2存儲結(jié)構(gòu)：存儲結(jié)構(gòu)： (1),表結(jié)點 typedef struct arcnode int adjvex; struct arcnode *nextarc; arcnode; (2),鏈表的存儲結(jié)構(gòu) typedef struct vnode int data; arcnode *firstarc; vnode,adjlistmax_vextex_num; (3),圖的存儲結(jié)構(gòu) typedef struct adjlist vertices; int vexnum,

46、 arcnum; algraph; (4),棧的存儲結(jié)構(gòu) typedef struct elemtype *base; elemtype *top; int stacksize; sqstack; 五、調(diào)試分析五、調(diào)試分析 算法的時間復(fù)雜性和可能的改進(jìn)設(shè)想算法的時間復(fù)雜性和可能的改進(jìn)設(shè)想 該拓?fù)渑判蛩惴?，對?n 個頂點和 e 條弧的有向圖而言，建立求各頂點的 入度的時間復(fù)雜度為 o(e)；建立入度頂點棧的時間復(fù)雜度為 o(n)；在拓?fù)渑判?過程中，若有向圖無環(huán)，則每個頂點進(jìn)一次棧，出一次棧，入度減 1 的操作在 while 語句中總共執(zhí)行 e 詞，所以，總的時間復(fù)雜度為 o(n+e)。 六、

47、測試結(jié)果六、測試結(jié)果 界面效果圖 打開文件效果圖 運行結(jié)果 七、課程設(shè)計總結(jié)七、課程設(shè)計總結(jié) 在近兩周的課程設(shè)計中，我認(rèn)為最大的收獲就是在遇到問題時解決問題的 過程。如對語言并不完全了解，如有些函數(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)識到了自己

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

49、nterface; public class outmain /* * param args */ public static void main(string args) new interface(); 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; impor

50、t 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 text; jtable table; jfilechooser filechooser; static tr

51、y /uimanager.setlookandfeel(ch.randelshofer.quaqua.quaqualookandfeel); uimanager.setlookandfeel(new liquidlookandfeel(); catch (unsupportedlookandfeelexception e) / todo auto-generated catch block e.printstacktrace(); public interface() super(排課); init(); private void init() string title = new strin

52、g學(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.setlayout(layout); panel.add(text); jbutton button = new jbutton(選擇課程文件); button.setactioncommand(ope

53、n); 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 , jscrollpane.horizontal_scrollbar_always); this.add(panel,borderlayout.north); this.

54、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 java.io.filereader; import java.io.ioexception; import java.io.linenumberreader; i

55、mport java.util.arraylist; import exception.dateexception; /* * * 實現(xiàn)排課類 * */ public class arranging /* * 節(jié)點內(nèi)部類，用來存儲數(shù)據(jù) * 一是存儲課程名和學(xué)該課程前的前提課程 * 二是用來存儲課程安排次序和該次可學(xué)的內(nèi)容 */ public class node string name; arraylist baselist; /* * 空構(gòu)造器 */ public arranging() /* * 排課方法 * 第一次排課的課程是 node 節(jié)點所代表課程該課程的前提課程是空，將其寫入 ar

56、raylist * 再將上次課程從剩余課程的前提課程中刪除，重復(fù)以上過程知道所有課程被排完或 排了 * 8 次后仍未排完（大學(xué)教育只有四年，八個學(xué)期，若八次不能排完，說明課程安排 存在問題， * 超出本方法處理范圍、不予處理） * param filepath * return * throws */ public arraylist arrayclass(file filepath) throws dateexception, filenotfoundexception,ioexception arraylist result = new arraylist();/存儲結(jié)果 arraylis

57、t list = readfile(filepath); integer i = 1;/記錄排課次序 int t = 1;/標(biāo)記 while(list.size() 0) = i.tostring(); s.baselist = new arraylist(); for(node tem:list) /提取前提課程為空的節(jié)點，寫入 result if(tem.baselist.size() = 0) s.baselist.add(); /list.remove(tem); for(string tem:s.baselist) /刪除前提課程為空的節(jié)點 list.r

58、emove(serchindex(list,tem); for(node tem:list) /刪除剩余節(jié)點的前提課程已修過課程 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,ioexception arraylist lis

59、t = new arraylist(); /file file = new file(filepath); bufferedreader 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(); = temp; s.baselist = ne

60、w arraylist(); list.add(s); else string arg0 = temp.split(:);/按“：”拆分 if(arg0.length != 2 ) throw new dateexception(); node s = new node(); = arg00; string arg1 = arg01.split(,);/按“， ”拆分 arraylist l = new arraylist(); for(string tem:arg1) l.add(tem); s.baselist = l; list.add(s); catch (filenot