资源描述
数据结构课程设计报告 计算机0801 中南大学数据结构课程设计报告指导教师 学 院 信息科学与工程学院 完成时间 2010年7月7日 目 录目 录- 2 -题目一：利用线性表进行算式计算- 1 -一、实验名称：- 1 -二、需求分析：- 1 -三、概要设计- 1 -四、详细设计- 3 -五、调试分析- 5 -六、测试结果- 5 -七、课程设计总结- 7 -八、参考文献- 8 -九、附录- 9 -题目三：排课问题- 21 -一、实验名称：- 21 -二、需求分析：- 21 -三、概要设计- 21 -四、详细设计- 24 -五、调试分析- 33 -六、测试结果- 33 -七、课程设计总结- 34 -八、参考文献- 35 -九、附录- 35 - 45 -题目一：利用线性表进行算式计算一、实验名称：利用线性表进行算式计算二、需求分析：设计任务：界面上出现一个文本框，输入一个算式，点击按钮，显示结果。该算式内只含有数字、括号、+、-、*、/、%这几种字符，优先级为：括号-%-*,/-+,-。如输入：2+3*5，结果为17,输入(2+3)*5结果为25。输入格式有误，需要给予提示。在算法中，必须实现对输入的算式字符串的分析，而不仅仅是得到结果。(1)输入的形式和输入值的范围：数字和运算符（只含有括号、+、-、*、/、%）。(2)输出的形式：以数字和运算符组成的算式形式输出。(3)程序所能达到的功能：对输入数字和运算符进行分析，并输出分析结果。(4)测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。三、概要设计抽象数据类型的定义：ADT Stack 数据对象：D=ai|aiElemSet,i=1,2,n, n0数据关系：R1=|ai-1,aiD,i=1,2,n基本操作： InitStack(&S)； 初始化栈S，构造一个空栈 StackEmpty(S)； 初始条件：栈S已存在操作结果：若栈为空栈，则返回true，否则返回false StackLength（S）；初始条件：栈S已存在操作结果：返回S的元素个数，即栈的长度GetTop(S,&e)初始条件：栈S已存在且非空操作结果：用e返回S的栈顶元素Push(&S,e)初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop(&S,&e)初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值主程序的流程：定义链栈，判断运算符优先级，实现具体计算，错误处理。四、详细设计主要算法：(伪代码)#define N 50#define OK 1#define ERROR 0#include #include typedef structint top;double arrayN;NumStack;typedef structint top;char arrayN;OpStack;/把字符转换为相应的整数的函数int Cint(char mychar)return (mychar-48);/数字进栈的函数status PushNum(NumStack &numstack,double num)if(numstack.topN) numstack.top+;numstack.arraynumstack.top-1=num;return OK;else return ERROR;/数字出栈的函数status PopNum(NumStack &numstack,double &num)if(numstack.top)num=numstack.arraynumstack.top-1;numstack.top-;return OK;else return ERROR;/操作符进栈的函数status PushOp(OpStack &opstack,char &op)if(opstack.topN) opstack.top+;opstack.arrayopstack.top-1=op;return OK;else return ERROR;/操作符出栈的函数status PopOp(OpStack &opstack,char &op)if(opstack.top) op=opstack.arrayopstack.top-1;opstack.top-;return OK;else return ERROR;/进行运算的函数double Calc(double a,double b,char c)double result;五、调试分析1调试过程中遇到的问题是如何解决的以及对设计与实现的讨论和分析调试过程中，对于非法输入的测试很重要，对于一些不符合常规的输入进行测试，并针对存在的问题对源代码进行修改，可以对于非法输入进行提示。2算法的时间复杂性和可能的改进设想此算法的运行时间主要花在while循环上，它从头到尾扫描后缀表达式中的每一个数据（每个操作数或运算符均为一个数据），若后缀表达式由n个数据组成，则此算法的时间复杂度为O(n)。在转换算法中，中缀算术表达式中的每个字符均需要扫描一遍，对于扫描到的每个运算符，最多需要进行入栈、出栈和写入后缀表达式这三次操作，对于扫描到的数字或小数点，只需要把它直接写入到后缀表达式即可。所以，此算法的时间复杂度为O(n)，n为后缀表达式中字符的个数。六、测试结果 1、输入：5+6*3%2输出：5+6*3%2=11.02、输入：3+5*（8-2）%4输出：3+5*（8-2）%4=13.03、输入:1*5+2 输出：对不起！表达式有错！4、输入：123321123+456654456 输出：123321123+456654456=5.7997555E85、输入：1111 输出：1111=1111.06、输入：5（3+2） 输出：对不起！表达式有错！7、输入：5+9*3-8/4%2 输出：5+9*3-8/4%2= -Infinity 界面效果图运行结果显示-1 运行结果显示-2七、课程设计总结通过本次数据结构课程设计，我有很多收获，在此，我将我的亲身感受回顾和总结于下：在上学期中学习了本专业的核心课程数据结构。什么是数据结构呢？这是我们首先考虑到的问题：从字面上来看，“数据结构”分数据和结构两部分，这就很容易联想到数据结构的本质是一种使数据结构化的知识。通过理论课程的学习，使我初步了解了数据结构的基本知识。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。现代程序设计已转型为讨论如何在最大程度上处理好数据之间的相互关系并提升数据处理的效率。在这里，数据结构就发挥了重要的作用。数据结构可以说是编程的灵魂，它不是一门语言。数据结构和程序设计语言本身没有任何联系，唯一有的关系就是用程序语言去描述数据结构。现今我们所学习的数据结构课程常用的描述语言主要有C、C+和JAVA等。数据结构只是给我们提供处理常规问题的一个思路而已，讲的是已经成熟的编程思想和算法，适用于所有开发语言。所以说，组织好数据结构是写程序的第一步。数据结构是一门实践性较强的计算机基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。课程设计的目的就是要达到理论与实际应用相结合，使我们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，同时强化对编程语言的使用，培养基本的、良好的程序设计能力。我于大二上学期从软件学院软件工程专业转到信息学院计算机专业，在09年暑假中，我参加了软件学院的JAVA实训，了解了一定的JAVA语言知识，因为本次课程设计要制作界面，所以选择JAVA语言有它的优势。通过这次课程设计，我体会到要做出一个好的程序是很难的，尽管我花了一个多星期去做这两个项目，但这个程序还是不够理想，只是达到一些基本的水平而已，跟那些功能强大的程序还是有很大的距离。这个程序还有一些地方值得完善的，比如算式计算中一些非法输入（如数字后面连续输入括号无法判断非法并影响计算结果等），这些问题需要程序员考虑得更全面，使实现的功能更完善，在今后不断改进。在近两周的课程设计中，我认为最大的收获就是在遇到问题时解决问题的过程。如对语言并不完全了解，如有些函数的操作需要通过查阅相关书籍和帮助来了解，另外，在入栈、出栈的算法设计中，曾因为思路不清晰而在编代码时遇到了困难，对于运算符和数字的分离和判断也曾困扰过我。我通过查阅书籍、上网搜索和向其他同学询问，才得以最终完成项目。通过这次课程设计，我学到了很多，同时也认识到了自己的不足。学校的课程不能将所有的知识都讲授给我们，所以要想学好一门课程，我们应该充分利用课余时间多看专业相关的书籍，丰富自己的知识。同时，作为计算机专业的学生，动手能力也是非常重要的，在掌握了理论知识后应多多上机实践。只有多多实践，才能更好地学习好一门语言，更好地理解课程的内容。八、参考文献【1】 清华大学计算机系列教材数据结构(C语言版)/严蔚敏，吴伟民编著 北京：清华大学出版社，2007.4【2】 Java JDK 5.0学习笔记/良葛格编著北京：清华大学出版社，2006.8 九、附录package stack;public class CharStack CharNode top;int sum;public CharStack() top=new CharNode(); top.c=#; sum=0; public char pop() /不作有没有元素的判断，统一在出栈前进行判断，若没有元素，则不调用此函数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;char 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() /不作有没有元素的判断，统一在出栈前进行判断，若没有元素，则不调用此函数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;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 = 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(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(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(int 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; 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; /当遇到不可识别的运算符识，设其优先级为-1，以便在主程序中能及时检查出错误 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 private static final long serialVersionUID = 8669406311759888678L;MainClass mainClass;JTabbedPane tab;JTextField input, output;JButton btnWork;private JTextArea txtaDisplay;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();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(数据结构);this.setSize(500, 400);this.setLocationRelativeTo(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 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(分析结果);lblInput = new JLabel(输入表达式：);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, BorderLayout.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() public 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();GetPriority priority = new GetPriority();/ GetPriority priority=new GetPriority();OperationClass operationFunction = new OperationClass();String str = inputStr + =; / 输入一个正确的表达式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; / 这个字符变量在下面代码中充当存储从运算符栈中出栈的运算符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 IntNode(); public float pop() /出栈 /对于头结点，存整数类型的a属性存的是栈内的元素个数 /对于出栈操作，由于本函数返回值为整数，故不进行判断是否栈内还有元素， /而是在调用此函数前，通过top.a的值进行判断 float t=top.node.a; top.node=top.node.node; top.a-; return t; public void push(float a) /进栈 IntNode newnode=new IntNode(); newnode.a=a; newnode.node=top.node; top.node=newnode; top.a+; class IntNodeIntNode node;float a;public IntNode()node=null;a=0f;package stack;public class OperationClass /从numStack栈中依次取出两个数字进行相应运算符的操作，结果再压入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=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(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(numStack.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;题目三：排课问题一、实验名称：排课问题二、需求分析：设计任务：在文件conf.txt中保存若干门课程，以及该课程需要哪些前续课程。要求一门课程需要一个学期才能学完。保存格式为例如：大学物理C语言Java语言:C语言微积分高级物理学:微积分,大学物理界面上，首先出现一个按钮，点击，载入conf.txt。点击另一个按钮，显示需要几个学期上完这些课程，每学期各学习哪些课程。(1)输入的形式和输入值的范围：读入文件。(2)输出的形式：文本输出。(3)程序所能达到的功能：从文件中读出数据，采用拓扑排序，显示出各学期需要学习哪些课程。(4)测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。三、概要设计1ADT Stack 数据对象：D=ai|aiElemSet,i=1,2,n, n0数据关系：R1=|ai-1,aiD,i=1,2,n基本操作： InitStack(&S)； 初始化栈S，构造一个空栈 StackEmpty(S)； 初始条件：栈S已存在操作结果：若栈为空栈，则返回true，否则返回false StackLength（S）；初始条件：栈S已存在操作结果：返回S的元素个数，即栈的长度GetTop(S,&e)初始条件：栈S已存在且非空操作结果：用e返回S的栈顶元素Push(&S,e)初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop(&S,&e)初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值2函数框图函数名函数功能Main总控函数InitStack初始化栈Pop出栈Push进栈StackEmpty栈的判空CreatGraph创建图FindInDegree求图中顶点入度TopologicalSort拓扑排序3函数流程图： （1）主函数流程图：（2）求入度函数的流程图： （3）创建图的流程图： （4）拓扑排序函数的流程图：四、详细设计1拓扑排序主要算法：Status TopologicalSort(ALGraph G)/有向图G采用邻接表存储结构/若G无回路，则输出G的顶点的一个拓扑排序序列并返回OK，否则返回ERROR。FindInDegree(G,indegree); /对各顶点求入度indegree0.vernum-1InitStack(S);for(i=0;inextarc) k=p-adjvex; if(!(-indegreek) Push(S,k); /若入度减为0，则入栈 /for/whileif(countbase=(ElemType *)malloc(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 出栈操作函数原型：int Pop(SqStack *S,ElemType *e)功能：删除S的栈顶元素，并用e返回；参数：SqStack *S,ElemType *e返回值：int源代码：int Pop(SqStack *S,ElemType *e)if(S-top=S-base)return ERROR;*e=*-S-top;return 0;l 进栈操作函数原型void Push(SqStack *S，ElemType e)功能：插入元素e为新的栈顶元素参数：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;l 判断栈是否为空的函数原型int StackEmpty(SqStack *S)功能：判断栈是否为空参数：SqStack *S返回值：int源代码：int StackEmpty(SqStack *S)if(S-top=S-base)return OK;elsereturn ERROR;l 创建图的函数原型void CreatGraph(ALGraph *G)功能：创建一有向图参数：ALGraph *G返回值：void源代码：void CreatGraph(ALGraph *G)int m, n, i;ArcNode *p;printf(请输入顶点数和边数:);scanf(%d%d,&G-vexnum,&G-arcnum);for (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 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);l
展开阅读全文