数据结构课程设计读书报告

1、算术表达式一、基本理论阐述栈是限制仅在表的一端进行插入和删除运算的线性表，通常称插入，删除的这一端为栈顶，另一端为栈底。当表中没有元素时称空栈。由上述定义，每次删除（退栈）的总是当前栈中“最新”的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才删除。也就是说，栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出的线性表，简称LIFO表。栈的基本运算有五种：置栈空，判栈空，进栈，退栈，取栈顶。队列也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端为队头，允许插入的一端为队尾。队列亦称作先进先出的线性表，简称FIFO表。队列的基本运

2、算有五种：置队列空，判队列空，取队头元素，入队，出队。A） 栈1)栈的定义:栈：是限定仅在表尾进行插入或删除操作的线性表。栈顶：进行插入和删除操作的那端，即表尾。栈底：表的另一端，即表头。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("计算器");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); 栈的实现 InitStac

17、k(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：栈S被销毁。 ClearStack(&S) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回TRUE，否则FALE。 StackLength(S) 初始条件：栈S已存在。 操作结果：返回S的元素个数，即栈的长度。 GetTop(S, &e) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push(&S, e) 初始条件：栈S已存在。 操作结果：插入

18、元素e为新的栈顶元素。 Pop(&S, &e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 ADT Stack3)分类:1顺序栈顺序栈的类型定义 #define StackSize 100 /假定预分配的栈空间最多为100个元素 typedef char DataType;/假定栈元素的数据类型为字符 typedef struct DataType dataStackSize; int top; SeqStack; 2链栈链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。创建链表（头插法，尾插法）二、课程设计过程中的应用与实践（1

19、）、设计一个程序，求解算术表达式问题描述：以字符序列的形式从键盘输入语法正确的、不含变量的整数表达式，实现对算术四则混合运算表达式的求值。要求：自己设计界面，使用适当的数据结构对运算符、操作作数进行处理。(2)功能模块及数据结构描述 OperatorStack ； data=new char100; 字符栈，存放字符OpreaStack ； data=new double100; 数字栈，存放数字Gettop() 为取栈顶元素Pop() 出栈Push() 入栈Isempty() 判断栈是否为空public Calculator() 对计算器进行界面设置public String toBehin

20、dExpress() 将中序表达式转换成后序表达式public int priorityLevel(char ch) 进行优先级比较public double getResult(String express) 利用后序表达式进行求值public class CalculatorTest 主函数（3）主要算法流程描述首先创建两个栈，一个栈存放字符，一个栈存放数字，这个程序使用java做的，首先，我设计了一个计算器的界面，在里面添加各个数字和运算符，我把写在text上面的字符串当成是中序表达式，第一步求的时候，我是将中序表达式转换成后序表达式，在这里，用到了字符栈，然后利用后序表达式进行求解运算

21、，这时了数字栈。（5）实验与总结在做此实验时，虽然在之前对数据结构关于栈的部分进行了充分的复习，并且充分的阅读课外资料，但还是遇到了一些问题。比如： 输入的操作数和运算符由于是字符串类型的，在原设计中实现的操作都是对个位数实现的。所以在考虑多位数的输入时困惑了，刚开始我准备利用字符串拆分，对每个数字，进行拆分，但是最终没有成功，最后再别人的提点下，我想到用树来解决，遇到数字，直接进入字符串，最红得到解决。在这次试验中，遇到的问题还有很多，但是通过自己的查阅和别人的提点，最终做出来了，我会更加努力，争取最好。校园导游一 基本理念阐述图图是由一个顶点集 V 和一个弧集 VR构成的数据结构。 Gra

22、ph = (V, VR )其中，VR<v,w>| v,wV 且 P(v,w) ，<v,w>表示从 v 到 w 的一条弧，并称 v 为弧尾，w 为弧头。谓词 P(v,w) 定义了弧 <v,w>的意义或信息。由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。由顶点集和边 集 构成的图称作无向图。图的存储结构：图的数组(邻接矩阵)存储表示，图的邻 接表存储表示。图的遍历：深度优先搜索遍历，广度优先搜索遍历。生成树和最小生成树：构造网的一棵最小生成树：普里姆算法，克鲁斯卡尔算法。检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。最短路径：求单源最

23、短路径：迪杰斯特拉算法。求所有顶点对之间的最短路径：弗洛伊德算法。B）弗洛伊德算法1）弗洛伊德算法思想对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。 2）图求最短路径有两种情况，一种是单源最短路径问题，即对于给定的有向网络G=(V,E)及单个源点v，求从v到G的其余各顶点的最短路径。这时候就需要用Dijkstra算法。Dijkstra算法主要特点是以起始

24、点为中心向外层层扩展，直到扩展到终点为止。基本思想：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对viV-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, , vk，就将vk加入集合S中，并将路径v, , vk , vi与原来的最短路径相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。另一种是所有顶点对之间的最短路径问题，即对于给定的有向网络G=(V,E)，要对G中任意两个顶点v，w（v!=w），找出v到w的最短路径。这时候就需要用Floyd算法。Floyd算法的核心思想是通过一个图的权值矩阵求出它的每两点间的最短

25、路径矩阵。基本思想：对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。这是一种简便算法，其实也可以每次以一个顶点为源点，调用Dijkstra算法n次来解决。但我认为Floyd算法此时更简单。 二、课程设计过程中的应用与实践一、设计一个校园导游程序，为来访的客人提供信息查询服务。要求：（1）设计学校的校园平面图，所含景点不少于10个，以图中顶点表示校内各景点，

26、存放景点名称、代号、简介等信息，以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意景点相关信息的查询；（3）为来访客人提供从校门口到图中任意景点的问路查询；（4）为来访客人提供图中任意景点间的问路查询；（此项选作）(2)功能模块及数据结构描述问题分析：1.首先在学校平面图中选取20个景点，抽象成一个无向带权图。以顶点表示景点，边上的权值表示两地的距离；2.编写程序要实现两点功能： 1) 景点查询：根据用户指定的景点输出景点编号信息。2) 最短路径查询：根据用户指定的始点和终点输出相应路径及最短距离。3、程序运行时，只要用户输入起点和终点信息，就能成功查询全局变量：l arcsM

27、axnumMaxnum边的值，即表示两地的距离 l ShortestPath_DIJ(AMGraph G,int start,int end)表示两点间的最短距离l Pathstartend用于表示终点直接前驱结点l GetLocation(AMGraph G , int v)表示所求景点位置信息l Stack利用栈Stack输出景点（3）主要算法流程描述先选择20个景点，然后给各个经典编号，写出这20个景点之间的权值，如下strcpy(G.vexs0,"黑龙江大学正门");strcpy(G.vexs1,"主楼");strcpy(G.vexs2,&quo

28、t;汇文楼"); strcpy(G.vexs3,"音乐厅");strcpy(G.vexs4,"艺术楼");strcpy(G.vexs5,"体育馆");strcpy(G.vexs6,"图书馆");strcpy(G.vexs7,"三号楼");strcpy(G.vexs8,"博文楼");strcpy(G.vexs9,"实验楼");strcpy(G.vexs10,"二号楼");strcpy(G.vexs11,"阳光讲坛&qu

29、ot;);strcpy(G.vexs12,"A区食堂");strcpy(G.vexs13,"B区综合楼");strcpy(G.vexs14,"C区食堂");strcpy(G.vexs15,"C区游泳馆");strcpy(G.vexs16,"留学生公寓");strcpy(G.vexs17,"联通广场");strcpy(G.vexs18,"网球场"); 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