數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)讀書報(bào)告

1、算術(shù)表達(dá)式一、基本理論闡述棧是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入，刪除的這一端為棧頂，另一端為棧底。當(dāng)表中沒有元素時(shí)稱空棧。由上述定義，每次刪除（退棧）的總是當(dāng)前棧中“最新”的元素，即最后插入（進(jìn)棧）的元素，而最先插入的是被放在棧的底部，要到最后才刪除。也就是說，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧又稱為后進(jìn)先出的線性表，簡稱LIFO表。棧的基本運(yùn)算有五種：置?？眨袟？眨M(jìn)棧，退棧，取棧頂。隊(duì)列也是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一端為隊(duì)頭，允許插入的一端為隊(duì)尾。隊(duì)列亦稱作先進(jìn)先出的線性表，簡稱FIFO表。隊(duì)列的基本運(yùn)

2、算有五種：置隊(duì)列空，判隊(duì)列空，取隊(duì)頭元素，入隊(duì)，出隊(duì)。A） 棧1)棧的定義:棧：是限定僅在表尾進(jìn)行插入或刪除操作的線性表。棧頂：進(jìn)行插入和刪除操作的那端，即表尾。棧底：表的另一端，即表頭。2)基本操作：組件的添加以及事件處理private JPanel panel1=new JPanel();private JPanel panel2=new JPanel();JButton button1;JButton button2;JButton button3;JButton button4;JButton button5;JButton button6;JButton button7;JButto

3、n button8;JButton button9;JButton button10;JButton button11;JButton button12;JButton button13;JButton button14;JButton button15;JButton button16;JButton button17;JButton button18;JButton button19;JButton button20;JTextField text;StringBuilder flag=new StringBuilder();public A()setBounds(400,220,250,

4、300);this.setResizable(false);this.setBackground(Color.blue);setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);this.setTitle("計(jì)算器");add(panel1,BorderLayout.NORTH);add(panel2,BorderLayout.CENTER);layoutPanel1();layoutPanel2();public void layoutPanel1()text=new JTextField(20);text.setEditable(f

5、alse);panel1.add(text);public void layoutPanel2()button1=new JButton("1"); button2=new JButton("2");button3=new JButton("3");button4=new JButton("4");button5=new JButton("5");button6=new JButton("6");button7=new JButton("7");butto

6、n8=new JButton("8");button9=new JButton("9");button10=new JButton("+");button11=new JButton("-");button12=new JButton("*");button13=new JButton("/");button14=new JButton("(");button15=new JButton(")");button16=new JButto

7、n("=");button17=new JButton(".");button18=new JButton("<<");button19=new JButton("0");button20=new JButton("C");panel2.setLayout(new GridLayout(5,4);panel2.add(button1);panel2.add(button2);panel2.add(button3);panel2.add(button10);panel2.add(but

8、ton4);panel2.add(button5);panel2.add(button6);panel2.add(button11);panel2.add(button7);panel2.add(button8);panel2.add(button9);panel2.add(button12);panel2.add(button14);panel2.add(button19);panel2.add(button15);panel2.add(button13); panel2.add(button17);panel2.add(button18); panel2.add(button16);pan

9、el2.add(button20);button1.addActionListener(this);button2.addActionListener(this);button3.addActionListener(this);button4.addActionListener(this);button5.addActionListener(this);button6.addActionListener(this);button7.addActionListener(this);button8.addActionListener(this);button9.addActionListener(

10、this);button10.addActionListener(this);button11.addActionListener(this);button12.addActionListener(this);button13.addActionListener(this);button14.addActionListener(this);button15.addActionListener(this);button16.addActionListener(this);button17.addActionListener(this);button18.addActionListener(thi

11、s);button19.addActionListener(this);button20.addActionListener(this);public void actionPerformed(ActionEvent e) if(e.getSource()=button20)text.setText("");if(e.getSource()=button1)flag.append('1');text.setText(flag.toString();if(e.getSource()=button2)flag.append('2');text.s

12、etText(flag.toString();if(e.getSource()=button3)flag.append('3');text.setText(flag.toString();if(e.getSource()=button4)flag.append('4');text.setText(flag.toString();if(e.getSource()=button5)flag.append('5');text.setText(flag.toString();if(e.getSource()=button6)flag.append(

13、9;6');text.setText(flag.toString();if(e.getSource()=button7)flag.append('7');text.setText(flag.toString();if(e.getSource()=button8)flag.append('8');text.setText(flag.toString();if(e.getSource()=button9)flag.append('9');text.setText(flag.toString();if(e.getSource()=button1

14、0)flag.append('+');text.setText(flag.toString();if(e.getSource()=button11)flag.append('-');text.setText(flag.toString();if(e.getSource()=button12)flag.append('*');text.setText(flag.toString();if(e.getSource()=button13)flag.append('/');text.setText(flag.toString();if(e

15、.getSource()=button14)flag.append('(');text.setText(flag.toString();if(e.getSource()=button15)flag.append(')');text.setText(flag.toString();if(e.getSource()=button17)flag.append('.');text.setText(flag.toString();if(e.getSource()=button18)flag.delete(flag.length()-1,flag.lengt

16、h();text.setText(flag.toString();if(e.getSource()=button19)flag.append('0');text.setText(flag.toString();if(e.getSource()=button20)flag.delete(0,flag.length();text.setText("0");if(e.getSource()=button16)B t=new B();String a=t.calString(flag.toString();text.setText(a); 棧的實(shí)現(xiàn) InitStac

17、k(&S) 操作結(jié)果：構(gòu)造一個(gè)空棧S。 DestroyStack(&S) 初始條件：棧S已存在。 操作結(jié)果：棧S被銷毀。 ClearStack(&S) 初始條件：棧S已存在。 操作結(jié)果：將S清為空棧。 StackEmpty(S) 初始條件：棧S已存在。 操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALE。 StackLength(S) 初始條件：棧S已存在。 操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長度。 GetTop(S, &e) 初始條件：棧S已存在且非空。 操作結(jié)果：用e返回S的棧頂元素。 Push(&S, e) 初始條件：棧S已存在。 操作結(jié)果：插入

18、元素e為新的棧頂元素。 Pop(&S, &e) 初始條件：棧S已存在且非空。 操作結(jié)果：刪除S的棧頂元素，并用e返回其值。 ADT Stack3)分類:1順序棧順序棧的類型定義 #define StackSize 100 /假定預(yù)分配的棧空間最多為100個(gè)元素 typedef char DataType;/假定棧元素的數(shù)據(jù)類型為字符 typedef struct DataType dataStackSize; int top; SeqStack; 2鏈棧鏈棧是沒有附加頭結(jié)點(diǎn)的運(yùn)算受限的單鏈表。棧頂指針就是鏈表的頭指針。創(chuàng)建鏈表（頭插法，尾插法）二、課程設(shè)計(jì)過程中的應(yīng)用與實(shí)踐（1

19、）、設(shè)計(jì)一個(gè)程序，求解算術(shù)表達(dá)式問題描述：以字符序列的形式從鍵盤輸入語法正確的、不含變量的整數(shù)表達(dá)式，實(shí)現(xiàn)對算術(shù)四則混合運(yùn)算表達(dá)式的求值。要求：自己設(shè)計(jì)界面，使用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)對運(yùn)算符、操作作數(shù)進(jìn)行處理。(2)功能模塊及數(shù)據(jù)結(jié)構(gòu)描述 OperatorStack ； data=new char100; 字符棧，存放字符OpreaStack ； data=new double100; 數(shù)字棧，存放數(shù)字Gettop() 為取棧頂元素Pop() 出棧Push() 入棧Isempty() 判斷棧是否為空public Calculator() 對計(jì)算器進(jìn)行界面設(shè)置public String toBehin

20、dExpress() 將中序表達(dá)式轉(zhuǎn)換成后序表達(dá)式public int priorityLevel(char ch) 進(jìn)行優(yōu)先級比較public double getResult(String express) 利用后序表達(dá)式進(jìn)行求值public class CalculatorTest 主函數(shù)（3）主要算法流程描述首先創(chuàng)建兩個(gè)棧，一個(gè)棧存放字符，一個(gè)棧存放數(shù)字，這個(gè)程序使用java做的，首先，我設(shè)計(jì)了一個(gè)計(jì)算器的界面，在里面添加各個(gè)數(shù)字和運(yùn)算符，我把寫在text上面的字符串當(dāng)成是中序表達(dá)式，第一步求的時(shí)候，我是將中序表達(dá)式轉(zhuǎn)換成后序表達(dá)式，在這里，用到了字符棧，然后利用后序表達(dá)式進(jìn)行求解運(yùn)算

21、，這時(shí)了數(shù)字棧。（5）實(shí)驗(yàn)與總結(jié)在做此實(shí)驗(yàn)時(shí)，雖然在之前對數(shù)據(jù)結(jié)構(gòu)關(guān)于棧的部分進(jìn)行了充分的復(fù)習(xí)，并且充分的閱讀課外資料，但還是遇到了一些問題。比如： 輸入的操作數(shù)和運(yùn)算符由于是字符串類型的，在原設(shè)計(jì)中實(shí)現(xiàn)的操作都是對個(gè)位數(shù)實(shí)現(xiàn)的。所以在考慮多位數(shù)的輸入時(shí)困惑了，剛開始我準(zhǔn)備利用字符串拆分，對每個(gè)數(shù)字，進(jìn)行拆分，但是最終沒有成功，最后再別人的提點(diǎn)下，我想到用樹來解決，遇到數(shù)字，直接進(jìn)入字符串，最紅得到解決。在這次試驗(yàn)中，遇到的問題還有很多，但是通過自己的查閱和別人的提點(diǎn)，最終做出來了，我會(huì)更加努力，爭取最好。校園導(dǎo)游一 基本理念闡述圖圖是由一個(gè)頂點(diǎn)集 V 和一個(gè)弧集 VR構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。 Gra

22、ph = (V, VR )其中，VR<v,w>| v,wV 且 P(v,w) ，<v,w>表示從 v 到 w 的一條弧，并稱 v 為弧尾，w 為弧頭。謂詞 P(v,w) 定義了弧 <v,w>的意義或信息。由于“弧”是有方向的，因此稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖。由頂點(diǎn)集和邊 集 構(gòu)成的圖稱作無向圖。圖的存儲(chǔ)結(jié)構(gòu)：圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示，圖的鄰 接表存儲(chǔ)表示。圖的遍歷：深度優(yōu)先搜索遍歷，廣度優(yōu)先搜索遍歷。生成樹和最小生成樹：構(gòu)造網(wǎng)的一棵最小生成樹：普里姆算法，克魯斯卡爾算法。檢查有向圖中是否存在回路的方法之一，是對有向圖進(jìn)行拓?fù)渑判颉Ｗ疃搪窂剑呵髥卧醋?/p>

23、短路徑：迪杰斯特拉算法。求所有頂點(diǎn)對之間的最短路徑：弗洛伊德算法。B）弗洛伊德算法1）弗洛伊德算法思想對于從vi到vj的弧，進(jìn)行n次試探：首先考慮路徑vi,v0,vj是否存在，如果存在，則比較vi,vj和vi,v0,vj的路徑長度，取較短者為從vi到vj的中間頂點(diǎn)的序號不大于0的最短路徑。在路徑上再增加一個(gè)頂點(diǎn)v1，依此類推，在經(jīng)過n次比較后，最后求得的必是從頂點(diǎn)vi到頂點(diǎn)vj的最短路徑。 2）圖求最短路徑有兩種情況，一種是單源最短路徑問題，即對于給定的有向網(wǎng)絡(luò)G=(V,E)及單個(gè)源點(diǎn)v，求從v到G的其余各頂點(diǎn)的最短路徑。這時(shí)候就需要用Dijkstra算法。Dijkstra算法主要特點(diǎn)是以起始

24、點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。基本思想：設(shè)置一個(gè)集合S存放已經(jīng)找到最短路徑的頂點(diǎn)，S的初始狀態(tài)只包含源點(diǎn)v，對viV-S，假設(shè)從源點(diǎn)v到vi的有向邊為最短路徑。以后每求得一條最短路徑v, , vk，就將vk加入集合S中，并將路徑v, , vk , vi與原來的最短路徑相比較，取路徑長度較小者為最短路徑。重復(fù)上述過程，直到集合V中全部頂點(diǎn)加入到集合S中。另一種是所有頂點(diǎn)對之間的最短路徑問題，即對于給定的有向網(wǎng)絡(luò)G=(V,E)，要對G中任意兩個(gè)頂點(diǎn)v，w（v!=w），找出v到w的最短路徑。這時(shí)候就需要用Floyd算法。Floyd算法的核心思想是通過一個(gè)圖的權(quán)值矩陣求出它的每兩點(diǎn)間的最短

25、路徑矩陣?；舅枷耄簩τ趶膙i到vj的弧，進(jìn)行n次試探：首先考慮路徑vi,v0,vj是否存在，如果存在，則比較vi,vj和vi,v0,vj的路徑長度，取較短者為從vi到vj的中間頂點(diǎn)的序號不大于0的最短路徑。在路徑上再增加一個(gè)頂點(diǎn)v1，依此類推，在經(jīng)過n次比較后，最后求得的必是從頂點(diǎn)vi到頂點(diǎn)vj的最短路徑。這是一種簡便算法，其實(shí)也可以每次以一個(gè)頂點(diǎn)為源點(diǎn)，調(diào)用Dijkstra算法n次來解決。但我認(rèn)為Floyd算法此時(shí)更簡單。 二、課程設(shè)計(jì)過程中的應(yīng)用與實(shí)踐一、設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來訪的客人提供信息查詢服務(wù)。要求：（1）設(shè)計(jì)學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)，以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，

26、存放景點(diǎn)名稱、代號、簡介等信息，以邊表示路徑，存放路徑長度等相關(guān)信息。（2）為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢；（3）為來訪客人提供從校門口到圖中任意景點(diǎn)的問路查詢；（4）為來訪客人提供圖中任意景點(diǎn)間的問路查詢；（此項(xiàng)選作）(2)功能模塊及數(shù)據(jù)結(jié)構(gòu)描述問題分析：1.首先在學(xué)校平面圖中選取20個(gè)景點(diǎn)，抽象成一個(gè)無向帶權(quán)圖。以頂點(diǎn)表示景點(diǎn)，邊上的權(quán)值表示兩地的距離；2.編寫程序要實(shí)現(xiàn)兩點(diǎn)功能： 1) 景點(diǎn)查詢：根據(jù)用戶指定的景點(diǎn)輸出景點(diǎn)編號信息。2) 最短路徑查詢：根據(jù)用戶指定的始點(diǎn)和終點(diǎn)輸出相應(yīng)路徑及最短距離。3、程序運(yùn)行時(shí)，只要用戶輸入起點(diǎn)和終點(diǎn)信息，就能成功查詢?nèi)肿兞浚簂 arcsM

27、axnumMaxnum邊的值，即表示兩地的距離 l ShortestPath_DIJ(AMGraph G,int start,int end)表示兩點(diǎn)間的最短距離l Pathstartend用于表示終點(diǎn)直接前驅(qū)結(jié)點(diǎn)l GetLocation(AMGraph G , int v)表示所求景點(diǎn)位置信息l Stack利用棧Stack輸出景點(diǎn)（3）主要算法流程描述先選擇20個(gè)景點(diǎn)，然后給各個(gè)經(jīng)典編號，寫出這20個(gè)景點(diǎn)之間的權(quán)值，如下strcpy(G.vexs0,"黑龍江大學(xué)正門");strcpy(G.vexs1,"主樓");strcpy(G.vexs2,&quo

28、t;匯文樓"); strcpy(G.vexs3,"音樂廳");strcpy(G.vexs4,"藝術(shù)樓");strcpy(G.vexs5,"體育館");strcpy(G.vexs6,"圖書館");strcpy(G.vexs7,"三號樓");strcpy(G.vexs8,"博文樓");strcpy(G.vexs9,"實(shí)驗(yàn)樓");strcpy(G.vexs10,"二號樓");strcpy(G.vexs11,"陽光講壇&qu

29、ot;);strcpy(G.vexs12,"A區(qū)食堂");strcpy(G.vexs13,"B區(qū)綜合樓");strcpy(G.vexs14,"C區(qū)食堂");strcpy(G.vexs15,"C區(qū)游泳館");strcpy(G.vexs16,"留學(xué)生公寓");strcpy(G.vexs17,"聯(lián)通廣場");strcpy(G.vexs18,"網(wǎng)球場"); strcpy(G.vexs19,"池塘");G.arcs01=10;G.arcs05=5

30、0;G.arcs018=70;G.arcs10=10;G.arcs50=50;G.arcs180=70;G.arcs15=30;G.arcs110=60;G.arcs118=50;G.arcs51=30;G.arcs101=60;G.arcs181=50;G.arcs23=260;G.arcs29=320;G.arcs213=380;G.arcs132=380;G.arcs92=320;G.arcs211=250;G.arcs26=220;G.arcs32=260;G.arcs112=250;G.arcs62=220;G.arcs311=20;G.arcs113=20;G.arcs415=80

31、;G.arcs416=100;G.arcs414=150;G.arcs154=80;G.arcs164=100;G.arcs144=150;G.arcs510=140;G.arcs105=140;G.arcs617=30;G.arcs611=40;G.arcs69=240;G.arcs176=30;G.arcs116=40;G.arcs96=240;G.arcs713=270;G.arcs715=200;G.arcs137=270;G.arcs157=200;G.arcs89=80;G.arcs812=60;G.arcs98=80;G.arcs128=60;G.arcs919=40;G.arcs912=50;G.arcs917=220;G.arcs199=40;G.arcs129=50;G.arcs179=220;G.arcs1018=100;G.arcs1017=10;G.arcs1810=100;G.arcs1710=10;G.arcs1219=50;G.a