《数据结构》课程设计手册一、 栈的使用（一）需求分析本程序通过java 语言完成栈的构造，对堆栈的数据进行基本的存储操作。

具体包括，数据的入栈、出栈、读取等。

入栈操作：要求用户从键盘出入要进栈的数值或字符，对栈满的情况作出提示。

出栈操作：删除栈顶元素，并将删除的数据或字符在运行结果中显示。

对栈空的情况作出提示。

读取操作：在插入和删除的任意阶段都可讲栈中的元素读取出来，能够实现对栈中的数据元素个数进行统计。

（二）概要设计1.为了实现上述程序功能，需要定义栈的数据类型有： static int MAX=5;static String[] item =new String[MAX]; static int top; 2.本程序包含4个函数Push() 初始条件：栈未满 操作结果：往栈中插入数据； Pop() 初始条件：存在非空栈 操作结果：将栈中的数据删除；Get() 初始条件：存在非空栈 操作结果：显示非空栈中的所有元素； Main() 操作结果：调用以上函数。

程序流程图：Main() Pop()Push() Get()（三）详细设计具体代码见Stack.java基本操作：Stack()构造一个空的栈，初始状态top的指针为-1；入栈方法public static void push()。

该方法中，首先判断是否栈满(top>=MAX-1)，如果栈满，则输出提示语“栈满 ,栈中最多能容纳5个元素”，否则从键盘输入数据，并且top指针加1。

出栈方法public static void pop()。

首先判断是否栈空(top<0)，如果栈空，则输出提示信息“栈空 ,没有可操作的元素”，否则删除栈顶元素。

Top指针减1。

get()方法public static void get()。

如果栈非空，则显示栈中的元素，并通过count计算出栈中的元素个数。

主函数public static void main（）通过switch-case语句调用相应的方法，从而实现栈的全部操作。

（四）调试分析通过在主函数中顺序调用相关函数来测试相关算法的，测试结果如下：1、测试入栈算法如果遇到栈满的情况，则运行结果为2、测试出栈算法如果栈空，则运行结果为3、获取栈中元素的测试结果已在1和2的测试中体现二、哈夫曼树的使用（一）需求分析该程序旨在实现对任意一个权值集合进行哈夫曼树的构造，对已经建好的哈夫曼树进行编码，并将每个字符的编码输出。

（二）概要设计1、哈夫曼树节点的数据类型定义class HaffmanNode {int weight;int parent,left,right;}2、实现构造哈夫曼树具有n个叶子结点的哈夫曼树共有2n-1个结点。

在已知结点总数的情况下采用采用三叉静态链表存储哈夫曼树。

我把节点信息存放在数组中，用数组weight[i]来存储每个叶子的权值。

3、获得哈弗曼编码在构造哈夫曼树之后，求每一个字符的编码是需要走一条从叶子节点出发、走一条从叶子节点到根节点的路径：译码需要从根节点到叶子节点的路径。

字符的哈弗曼编码由变长的二进制为串组成，每一个字符的哈弗曼编码用一个字符串表示，用HuffmanTree类的huffmanCode（）发放返回当前哈夫曼树中的多有叶子结点表示字符的哈弗曼编码。

（三）详细设计详细代码见HaffmanTree.java（四）调试分析运行结果：程序的不足：输入的权值个数不能按照用户的要求，规定数组的容量为5，所以用户只能按照程序的要求输入任意5个数字，而且只能对数值型数据进行编码，如果输入字符串，则抛出异常。

三、队列的使用（一）需求分析本程序通过java 语言完成队列的构造，对队列的数据进行基本的存储操作。

具体包括，数据的入队、出队、读取等。

入队和出队操作均由用户通过键盘控制，将操作结果在运行窗口中显示。

具体的操作前先对循环队列中的具体情况进行判断，并作出相应的提示，如“队满”，“队空”等。

只要队列非空，读取操作在插入和删除的任意阶段都可将队列中的元素显示，并实现对队列中的数据元素个数进行统计。

（二）概要设计1.为了实现上述程序功能，需要定义栈的数据类型有：int MaxSize =5;static String queue []=new String[MaxSize ]; static int front ,rear ;2.本程序包含4个函数enqueue() 初始条件：队列未满 操作结果：往循环队列中插入数据； dequeue() 初始条件：存在非空队列 操作结果：将队列中的数据删除； Get() 初始条件：存在非空队列 操作结果：显示非空队列中的所有元素； Main() 操作结果：调用以上函数。

程序流程图：Main() Pop()Push() Get()（三）详细设计具体代码见queue.java1、入对方法public static void enqueue()。

该方法中，首先判断是否队满(rear+1)%MaxSize==front)，如果队满，则输出提示语“Queue Full!”，否则从键盘输入数据，并且rear指针加1。

2、出队方法public static void dequeue()。

首先判断是否队空(front==rear)，如果队空，则输出提示信息“队空”，否则删除队头元素。

Rear 指针减1。

3、get()方法public static void get()。

如果队列非空，则显示队中的元素，并通过count计算出队列中的元素个数。

4、主函数public static void main（）通过switch-case语句调用相应的方法，从而实现队列的全部操作。

（四）调试分析通过在主函数中顺序调用相关函数来测试相关算法的，测试结果如下：1、测试入队算法如果遇到队满的情况，则运行结果为2、测试出队算法如果队空，则运行结果为：a)获取环行队列中元素的测试结果已在1和2的测试中体现b)4、问题分析：输入的元素中多了一个NULL，如以上运行结果的截图所示。

用count统计的元素个数比实际队列中的个数多一。

和同学探讨分析后，经过调试，发现循环输出存在问题，即get()方法里面的for循环语句出错，把i>0改成i>front+1后，一切问题都解决了。

最后得运行结果插入：删除：四、图的表示（一）：需求分析有向带权图包括图形的原顶点、终点及权值，所以在定义变量时，定义destination、source、value这三个变量。

默认为0，根据用户的输入将其转化成邻接矩阵，并输出。

（二）：概要设计：定义有向图的行数和列数，通过提示，要求输入者输入原顶点、对应边的权值及目标顶点。

用check（）方法实现对数组的验证功能，验证两个顶点之间是否生成了自循环（source=destination）,是否超出数组范围(source >= MAX || destination >= MAX)。

通过主方法将带权有向图转换为邻接矩阵。

（三）：详细设计：Graph.java（四）：调试分析：1、运行程序后，显示出来的界面：2、3、出现自循环时，界面如下。

4、顶点超出数组范围五、数组的使用、存储（一）：需求分析运用数组存储数据，对数组实行存入数据与删除数据的操作，整个程序用Array一个类来写，下面包含add、delete、tostring、checkint、main这5个方法，main方法里创建了新的数组，在选择相关的步骤后便可对数组进行插入删除读取操作。

（二）：概要设计：（三）：详细设计见Array.java（四）：调试分析：1、当点击开始时，出现如下界面。

2、输入1，则出现“请输入要添加的位置”3、输入正确的添加位置后，显示如下。

4、元素添加成功后，界面又回到最初的样子。

5、此图为显示所有元素的界面。

6、删除元素7、输入的位置格式发生错误时8、当某个位置有数据时，再在该位置添加数据时，原来的数据会向后移一位。

程序的缺陷：缺少结束语句。

当输入的位置不正确时，虽然显示“请正确进行选择”，但还是可以输入元素进行添加。

当某个位置有数据时，再在该位置添加数据时，原来的数据会向后移一位。

六、排序（一）：需求分析1、输入的形式按需要输入学生的个数（整数形式），再输入对应的学生姓名及成绩（整数形式），如果输入形式不对，则程序立即退出。

2、输出形式在按需求选择了排序方法后，按分数高低次序输出每个学生在考试中获得的名次（分数相同的为同一名次），后面紧跟学生名字和成绩。

3、程序所能达到的功能学生的考试成绩表通过键盘输入数据建立，同时对输出进行格式控制，分别用冒泡排序、快速排序和直接选择排序算法实现对成绩的排序。

4、测试数据1）正确的输入及输出结果：输入正确的学生人数后，会要求你输入相应人数的姓名及其对应的成绩。

输入完毕后出现一条虚线以和下面内容进行划分。

在1、2、3内选择一种排序方法，确定后会显示相应的成绩排序和学生姓名、成绩。

2）错误的输入及输出结果：如果学生人数输入不对，程序立即退出，成绩输入错误也会立即退出程序。

如果输入排序方法的数字和要求的不对应，会显示“请输入正确的输入方法”；如果输入的不是数字，则会立即退出程序。

（二）：设计概要（三）：详细设计具体代码请见Client.java&Student.java（四）：调试分析如果输入格式不对，则退出程序。

如下图1、输入学生人数格式错误2、输入排序方式格式错误3、输入成绩错误4、正确输入后，出现的排序结果排序排的只是成绩，与姓名无关，不可能把所有学生的成绩单独拿出来。

所以要对对象进行排序，也就是对Studnet排序。

JA V A中对象本身是不可以排序的，但是JA V A如果一个类实现Comparable接口的话，就可以排序了。

七、课程设计总结（一）09xxxxxx xxx由于前段时间一直在忙挑战杯的事，然后对于这个数据结构课程设计就一直拖啊拖，原本以为这个课程设计和以前上课叫我们编的小程序差不多，最后却发现还是有很大的难度的。

之前的课上作业，代码都从书上抄抄来，然后自己稍加整顿便出来结果了，这次的有些都不行。

正是由于这样，在这次的课程设计中，我对java的运用了解的更多了，对于以前学过的数据结构的内容又重拾了一遍，温故而知新。

在处理排序问题时，排序排的只是成绩，跟姓名没关系，我们不可能把所有学生的成绩单独拿出来。

如果是存放在一个数组里，然后对这个数组进行排序，这样也很麻烦。

在问了同学后，引入了对对象进行排序，也就是对Studnet排序，在JAVA中对象本身是不可以排序的，但是JAVA如果一个类实现Comparable接口的话，就可以排序了。

在处理“定义一个图，然后把它转化为邻接矩阵”在这个题目中，开始完全不知道从何下手，因为关于图的知识之前没学好，现在又有些忘了。