《Java语言程序设计》课程设计报告——排序
JAVA语言程序设计课程设计报告书
院系名称计算机与网络安全学院
专业班级 2015级软件工程3班
学号
姓名
指导教师
完成时间 2016年12月1-2号
目录1.系统功能及任务描述
1.1系统总体功能描述
1.2主要任务描述
2.系统的实现
3.系统的测试
4.总结
4.1自我评价及收获
4.2有待解决的问题及进一步完善的思路
5.参考文献
6.附录（代码附后）
1.系统功能及任务描述
1.1系统总体功能描述
本课程设计主要功能就是利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。
1.2主要任务描述
1) 至少采用两种方法实现上述问题求解（提示，可采用的方法有插入排
序、冒泡排序、选择排序、交换排序等）。并把排序后的结果保存在不同的文件中。
2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行
对比），找出其中两种较快的方法。
3) 如果采用4种或4种以上的方法者，可适当加分。
2.系统的实现
2.1开发环境
2.1.1工具
Eclipse：版本 Mars.1 Release (4.5.1)，windows 64位
JDK：版本jdk-7u51-windows-x64.exe
2.1.2 电脑机型
华硕R556L，系统64位
2.2界面设计
界面采用Swing轻量级组件开发，在1个JFrame窗体中放置5个JLabel标签，5个JButton按钮，3个JTextField文本框。
2.3 类设计
2.4 主要代码说明
2.4.1 主要按钮触发事件
2.4.1.1 “确定”按钮
给“确定”按钮添加事件监听器addActionListener方法，内部类里实现actionPerform ed(ActionEvent e)方法，获取文本框
JTextField的数据，然后产生随机数，用LinkedList集合存储进
RandomNumber.txt文件，方便增加删除。
//确定按钮事件
jButton_confirm.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
// TODO自动生成的方法存根
//集合，用于存储数据
LinkedList
LinkedList
//获取文本框数据
int begin =
Integer.parseInt(jTextField_begin.getText());
int end = Integer.parseInt(jTextField_end.getText());
int num = Integer.parseInt(jTextField_num.getText());
//产生随机数
for(int i=0;i int temp= (int) (Math.random() * (end-begin))+begin; linkedList.add(temp); } //输出到屏幕 for(int i=0;i System.out.println("Random随机数 ---"+linkedList.get(i)); } System.out.println("随机数个数 ------------------"+linkedList.size()); //存储到RandomNumber.txt文件中 File file = new File("RandomNumber.txt"); try { OutputStreamWriter write= new OutputStreamWriter(new FileOutputStream(file),"UTF-8"); BufferedWriter bufferedWriter = new BufferedWriter(write); for(int i=0;i String str = String.valueOf(linkedList.get(i)); String string = new String(str.getBytes("iso8859-1"),"UTF-8"); bufferedWriter.write(string+'\n'); } bufferedWriter.close(); } catch (IOException e1) { // TODO自动生成的 catch 块 e1.printStackTrace(); } //读取RandomNumber.txt文件 InputStreamReader reader; try { reader = new InputStreamReader(new FileInputStream(file),"UTF-8"); BufferedReader bufferedReader = new BufferedReader(reader); String line = null; try { while((line= bufferedReader.readLine()) != null) { System.out.println("RandomNumber文件 ---"+line); } bufferedReader.close(); } catch (IOException e1) { // TODO自动生成的 catch 块 e1.printStackTrace(); } } catch (UnsupportedEncodingException e1) { // TODO自动生成的 catch 块 e1.printStackTrace(); } catch (FileNotFoundException e1) { // TODO自动生成的 catch 块 e1.printStackTrace(); } } }); 2.4.1.1 “冒泡”按钮 同样给“冒泡”按钮添加监听器，在actionPerform ed(ActionEvent e)方法里创建Bubble类对象，重新创建一个新的LinkedList readerToFile() bubbleSort(linkedList) writerToFile(linkedList)三个方法， 其中将在bubbleSort()方法前后获取当前系统时间，最后得到排序所用时间，显示在窗体中。 //冒泡排序事件 jButton_bubble.addActionListener(new ActionListener() { @Override public void actionPerformed(ActionEvent e) { // TODO自动生成的方法存根 Bubble bubble = new Bubble(); LinkedList LinkedList linkedList = bubble.readerToFile(); long begin = System.currentTimeMillis(); linkedList = bubble.bubbleSort(linkedList); long end = System.currentTimeMillis(); jLabel_time.setText("冒泡排序所用时间： "+String.valueOf(end-begin)+"ms"); bubble.writerToFile(linkedList); } }); 2.4.2 排序函数 2.4.2.1 冒泡排序 //冒泡排序 LinkedList Integer temp; for(i=0;i for(j=1;j if(linkedList.get(j) temp = linkedList.get(j); linkedList.set(j, linkedList.get(j-1)); linkedList.set((j-1), temp); } } } System.out.println("排序后********"+linkedList); //排序后 return linkedList; } 2.4.2.2 直接插入排序 //直接插入排序 LinkedList Integer temp; for(i=0;i temp = linkedList.get(i); j = i-1; while(j>=0 && temp linkedList.set((j+1), linkedList.get(j)); j--; } linkedList.set((j+1), temp); } System.out.println("排序后********"+linkedList); //排序后 return linkedList; } 2.4.2.2 直接选择排序 //直接选择排序 LinkedList int i,j,k; Integer temp; for(i=0;i k = i; for(j=i+1;j if(linkedList.get(j) k = j; if(k!=i){ temp = linkedList.get(i); linkedList.set(i, linkedList.get(k)); linkedList.set(k, temp); } } } System.out.println("排序后********"+linkedList); //排序后 return linkedList; } 2.4.2.2 快速排序 //直接选择排序 LinkedList linkedList,int s,int t){ int i=s,j=t; int temp; if(s temp = linkedList.get(s); while(i!=j){ while(j>i && linkedList.get(j)>=temp) j--; linkedList.set(i, linkedList.get(j)); while(i i++; linkedList.set(j, linkedList.get(i)); } linkedList.set(i, temp); quickSort(linkedList,s,i-1); quickSort(linkedList, i+1, t); } return linkedList; } 3.系统的测试 3.1 排序测试 先测试产生5个随机数，并依次点击“冒泡”、“直接插入”、“直接选择”、“快速”排序按钮，输出链表，结果正确。（出现0ms原因：随机数太少，CPU 运行速度太快） 3.2计算时间 使用2000个随机数测试，并分别计算各排序所用时间。（20000个数用直接插入排序我等了40分钟，还没好...可能我电脑太烂~~~~(>_<)~~~~，老师如果你电脑好一点，你试试） 1）冒泡排序用了15709 ms 2）直接插入排序用了6599 ms 3）直接选择排序用了22012 ms 4）快速排序用了141 ms 验证文件确实有数据 4.总结 4.1自我评价及收获 自我感觉良好，经过老师一年的精心栽培，最后能达到如此成果，呕心沥血做完，倍感荣幸，受益匪浅，老师之恩，来日再报！下面是获益之处： 1）更加熟悉了各排序的方法和效率； 2）认识GUI界面设计，运用了Swing组件的几种组件，从MFC过渡到java 实现界面，颇有一种从地狱到天堂的快感； 3）更加深刻的了解了IO流、文件的读取操作、乱码以及格式转换等。4.2有待解决的问题及进一步完善的思路 1）文本框输入为空时，会报错； 2）本次界面采用绝对布局，可以考虑采用流式布局，方格式布局，减少代码的臃肿性； 3）没有美化各组件，相对原始。 5.参考文献 1）课本《java基础入门》 2）《java从入门到精通》 3）相关链接： 1.Java读取文本文件中文乱码问题 https://www.wendangku.net/doc/086136786.html,/greenqingqingws/article/details/7395213 2.在线API文档 https://www.wendangku.net/doc/086136786.html,/apidocs 3.java中的随机数Random https://www.wendangku.net/doc/086136786.html,/xiaorubj001/article/details/5984017 4.Java 如何将String转化为Int https://https://www.wendangku.net/doc/086136786.html,/question/38519769.html 6.附录（代码附后） 6.1 RandomSort类 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.UnsupportedEncodingException; import java.util.LinkedList; public class Quick { void writerToFile(LinkedList //存储到Quick.txt文件中 File file = new File("Quick.txt"); try { OutputStreamWriter write= new OutputStreamWriter(new FileOutputStream(file),"UTF-8"); BufferedWriter bufferedWriter = new BufferedWriter(write); for(int i=0;i String str = String.valueOf(linkedList.get(i)); String string = new String(str.getBytes("iso8859-1"),"UTF-8"); bufferedWriter.write(string+'\n'); } bufferedWriter.close(); } catch (IOException e1) { // TODO自动生成的 catch 块 e1.printStackTrace(); } } //直接选择排序 LinkedList int i=s,j=t; int temp; if(s temp = linkedList.get(s); while(i!=j){ while(j>i && linkedList.get(j)>=temp) j--; linkedList.set(i, linkedList.get(j)); while(i i++; linkedList.set(j, linkedList.get(i)); } linkedList.set(i, temp); quickSort(linkedList,s,i-1); quickSort(linkedList, i+1, t); } return linkedList; } LinkedList LinkedList File file = new File("RandomNumber.txt"); InputStreamReader reader; try { reader = new InputStreamReader(new FileInputStream(file),"UTF-8"); BufferedReader bufferedReader = new BufferedReader(reader); String line = null; try { while ((line = bufferedReader.readLine()) != null) { int temp = Integer.parseInt(line); //System.out.println("bubble---"+temp); linkedList.add(temp); } bufferedReader.close(); } catch (IOException e1) { // TODO自动生成的 catch 块 e1.printStackTrace(); } } catch (UnsupportedEncodingException e1) { // TODO自动生成的 catch 块 e1.printStackTrace(); } catch (FileNotFoundException e1) { // TODO自动生成的 catch 块 e1.printStackTrace(); } return linkedList; } } 6.2 Bubble类 import java.io.*; import java.util.LinkedList; public class Bubble { void writerToFile(LinkedList //存储到Bubble.txt文件中 File file = new File("Bubble.txt"); try { OutputStreamWriter write = new OutputStreamWriter(new FileOutputStream(file),"UTF-8"); BufferedWriter bufferedWriter = new BufferedWriter(write); for(int i=0;i String str = String.valueOf(linkedList.get(i)); String string = new String(str.getBytes("iso8859-1"),"UTF-8"); bufferedWriter.write(string+'\n'); } bufferedWriter.close(); } catch (IOException e1) { // TODO 自动生成的 catch 块 e1.printStackTrace(); } } //冒泡排序 LinkedList Integer temp; for(i=0;i for(j=1;j if(linkedList.get(j) temp = linkedList.get(j); linkedList.set(j, linkedList.get(j-1)); linkedList.set((j-1), temp); } } } return linkedList; } LinkedList LinkedList File file = new File("RandomNumber.txt"); InputStreamReader reader; try { reader = new InputStreamReader(new FileInputStream(file),"UTF-8"); BufferedReader bufferedReader = new BufferedReader(reader); String line = null; try { while ((line = bufferedReader.readLine()) != null) { int temp = Integer.parseInt(line); //System.out.println("bubble---"+temp); linkedList.add(temp); } bufferedReader.close(); } catch (IOException e1) { // TODO 自动生成的 catch 块 e1.printStackTrace(); } } catch (UnsupportedEncodingException e1) { // TODO 自动生成的 catch 块 e1.printStackTrace(); } catch (FileNotFoundException e1) { // TODO 自动生成的 catch 块 e1.printStackTrace(); } return linkedList; } } 6.3 DirectInsert类 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.UnsupportedEncodingException; import java.util.LinkedList; public class DirectInsert { void writerToFile(LinkedList //存储到DirectInsert.txt文件中 File file = new File("DirectInsert.txt"); try { OutputStreamWriter write = new OutputStreamWriter(new FileOutputStream(file),"UTF-8"); BufferedWriter bufferedWriter = new BufferedWriter(write); for(int i=0;i String str = String.valueOf(linkedList.get(i)); String string = new String(str.getBytes("iso8859-1"),"UTF-8"); bufferedWriter.write(string+'\n'); } bufferedWriter.close(); } catch (IOException e1) { // TODO 自动生成的 catch 块 e1.printStackTrace(); } } //直接插入排序 LinkedList int i,j; Integer temp; for(i=0;i temp = linkedList.get(i); j = i-1; while(j>=0 && temp linkedList.set((j+1), linkedList.get(j)); j--; } linkedList.set((j+1), temp); } return linkedList; } LinkedList LinkedList File file = new File("RandomNumber.txt"); InputStreamReader reader; try { reader = new InputStreamReader(new FileInputStream(file),"UTF-8"); BufferedReader bufferedReader = new BufferedReader(reader); String line = null; try { while ((line = bufferedReader.readLine()) != null) { int temp = Integer.parseInt(line); //System.out.println("bubble---"+temp); linkedList.add(temp); } bufferedReader.close(); } catch (IOException e1) { // TODO 自动生成的 catch 块 e1.printStackTrace(); } } catch (UnsupportedEncodingException e1) { // TODO 自动生成的 catch 块 e1.printStackTrace(); } catch (FileNotFoundException e1) { // TODO 自动生成的 catch 块 e1.printStackTrace(); } return linkedList; } } 6.4 DirectSelect类 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.UnsupportedEncodingException; import java.util.LinkedList; public class DirectSelect { void writerToFile(LinkedList //存储到DirectSelect.txt文件中 File file = new File("DirectSelect.txt"); try { OutputStreamWriter write = new OutputStreamWriter(new FileOutputStream(file),"UTF-8"); 一、问题描述 1、排序问题描述 排序是计算机程序设计的一种重要操作，他的功能是将一组任意顺序数据元素（记录），根据某一个（或几个）关键字按一定的顺序重新排列成为有序的序列。简单地说，就是将一组“无序”的记录序列调整为“有序”的记录序列的一种操作。 本次课程设计主要涉及几种常用的排序方法，分析了排序的实质，排序的应用，排序的分类，同时进行各排序方法的效率比较，包括比较次数和交换次数。我们利用java语言来实现本排序综合系统，该系统包含了：插入排序、交换排序、选择排序、归并排序。其中包括： （1）插入排序的有关算法：不带监视哨的直接插入排序的实现； （2）交换排序有关算法：冒泡排序、快速排序的实现； （3）选择排序的有关算法：直接选择排序、堆排序的实现； （4）归并排序的有关算法：2-路归并排序的实现。 2、界面设计模块问题描述 设计一个菜单式界面，让用户可以选择要解决的问题，同时可以退出程序。界面要求简洁明了，大方得体，便于用户的使用，同时，对于用户的错误选择可以进行有效的处理。 二、问题分析 本人设计的是交换排序，它的基本思想是两两比较带排序记录的关键字，若两个记录的次序相反则交换这两个记录，直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有冒泡排序和快速排序。 冒泡排序的基本思想是：将待排序的数组看作从上到下排列，把关键字值较小的记录看作“较轻的”，关键字值较大的纪录看作“较重的”，较小关键字值的记录好像水中的气泡一样，向上浮；较大关键字值的纪录如水中的石块向下沉，当所有的气泡都浮到了相应的位置，并且所有的石块都沉到了水中，排序就结束了。 冒泡排序的步骤： 1)置初值i=1； 2)在无序序列｛r[0],r[1],…，r[n-i]｝中，从头至尾依次比较相邻的两个记录r[j] 与r[j+1]（0<=j<=n-i-1）,若r[j].key>r[j+1].key，则交换位置； 3)i=i+1； 4)重复步骤2）和3），直到步骤2）中未发生记录交换或i=n-1为止； 要实现上述步骤，需要引入一个布尔变量flag，用来标记相邻记录是否发生交换。 快速排序的基本思想是：通过一趟排序将要排序的记录分割成独立的两个部分，其中一部分的所有记录的关键字值都比另外一部分的所有记录关键字值小，然后再按此方法对这两部分记录分别进行快速排序，整个排序过程可以递归进行，以此达到整个记录序列变成有序。 快速排序步骤： 1)设置两个变量i、j，初值分别为low和high，分别表示待排序序列的起始下 拓扑排序 [基本要求] 用邻接表建立一个有向图的存储结构。利用拓扑排序算法输出该图的拓扑排序序列。 [编程思路] 首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意有向是不需要对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，几乎和图的创建一样，图的顶点定义时加入int indegree，关键在于indegree 的计算，而最好的就是在创建的时候就算出入度，（没有采用书上的indegree【】数组的方法，那样会增加一个indegree算法，而是在创建的时候假如一句计数的代码(G.vertices[j].indegree)++;）最后调用拓扑排序的算法，得出拓扑序列。 [程序代码] 头文件： #define MAX_VERTEX_NUM 30 #define STACKSIZE 30 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define TRUE 1 #define FALSE 0 typedef int Status; typedef int InfoType; typedef int Status; typedef int SElemType; /* 定义弧的结构*/ typedef struct ArcNode{ int adjvex; /*该边所指向的顶点的位置*/ struct ArcNode *nextarc; /*指向下一条边的指针*/ InfoType info; /*该弧相关信息的指针*/ 课题二拓扑排序 2．1 问题的提出2.1 问题的提出 任务：编写函数实现图的拓扑排序。 程序所实现的功能：建立对应的邻接表，对该图进行拓扑排序，并显示排序 结果。 输入： 顶点数, 边数及各顶点信息(数据格式为整形) 输出： 拓扑排序结果。 2. 2 概要设计 1.拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。更直观地讲，一个偏序是自反的、反对称的，用图表示时每个点都有环且只有单向边。拓扑排序的任务是在这个偏序上得到一个全序，即得到一个完成整个项目的各步骤的序列。 2．解决拓扑排序的方法如下： （1）在有向图中选一个没有前驱的顶点且输出之。 （2）从图中删除该顶点和所有以它为尾的弧。 重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。具体的算法实现参照源程序。 3．构造邻接表图：typedef struct{ AdjList vertices; int vexnum,arcnum; }Graph;//邻接表图 4.为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入度为零的顶点：typedef struct stack{ int *base; int *top; int stacksize; }sqstack;//栈的结构，存储图的顶点序号 2．3 流程图2.根据算法思想，画流程图如下： 2．4 源代码 //采用尾插法创的邻接图 #include 《排序问题求解》实验报告 一、算法的基本思想 1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中，从而得到一个新的，记录数增1 的有序序列。 直接插入排序算法的伪代码称为InsertionSort，它的参数是一个数组A[1..n]，包含了n 个待排序的数。用伪代码表示直接插入排序算法如下： InsertionSort (A) for i←2 to n do key←A[i] //key 表示待插入数 //Insert A[i] into the sorted sequence A[1..i-1] j←i-1 while j>0 and A[j]>key do A[j+1]←A[j] j←j-1 A[j+1]←key 2、快速排序算法思想 快速排序算法的基本思想是，通过一趟排序将待排序序列分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序序列为数组A[1..n]，首先选取第一个数A[0]，作为枢轴（pivot），然后按照下述原则重新排列其余数：将所有比A[0]大的数都排在它的位置之前，将所有比A[0] 小的数都排在它的位置之后，由此以A[0]最后所在的位置i 作为分界线，将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序，对子数组A[1..i-1]和A[i+1..n]排序。 一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey，则首先从high 所指位置起向前搜索，找到第一个小于pivotkey 的数，并将其移到低端，然后从low 所指位置起向后搜索，找到第一个大于pivotkey 的数，并将其移到高端，重复这两步直至low=high。最后，将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下： Partition ( A, low, high) A[0]←A[low] //用数组的第一个记录做枢轴记录 privotkey←A[low] //枢轴记录关键字 while low 可用C++(Visual C++ 6.0),JA V A（JSP，STRUTS），C#(https://www.wendangku.net/doc/086136786.html, ，Visual Studio 2005)，试题目而定。 1、综合购物频道（限最多3人选） 项目描述：是一个在线销售系统，是一个B-C模式的电子商务系统，由前台的B/S模式购物系统和后台的C/S模式的管理系统两部分组成。该电子商务系统可以实现会员注册、浏览商品、查看商品详细信息、选购商品、取消订单和查看订单等功能，前台系统的详细功能。目的：了解项目开发的一个基本流程以及如何运用现行的框架搭建一个大型的综合型系统2、某大型企业内部OA（限最多3人选） 项目描述：采用网络办公自动化系统，不仅能快速提高企业的运作效率，节省大量的办公费用，能全面提升企业的核心竞争力和生产力以及提高工作效率。该企业内部OA系统采用模型组件与WEB技术结合的方式，具有强大的功能，广泛的适用性、可靠安全性和可扩展性。目的：学习运用当前热门的前台技术。 3、产品展示厅（限最多3人选） 项目描述： 在互联网发达的今天，当您想客户宣传自己的产品时，最好的方式是拥有自己的网站，通过网络来传播和展示您的产品信息。产品展示系统，为客户详细介绍自己的产品，提供了一个功能强大的平台。 系统界面友好、功能强大、操作简便，用户可以方便迅速掌握系统的操作。 4人事管理系统（限最多3人选） 项目描述：人事档案完整资料、人事分类管理（员工户口状况、员工政治面貌、员工生理状况、员工婚姻状况、员工合同管理、员工投保情况、员工担保情况）、考勤管理、加班管理、出差管理、人事变动管理（新进员工登记、员工离职登记、人员变更记录）、员工培训管理（员工培训、员工学历）、考核奖惩、养老保险等几大模块。系统具有人事档案资料完备，打印灵活，多样、专业的报表设计，灵活的查询功能等特点。 主要技能：掌握项目的开发流程：需求分析、详细设计、测试等；熟悉VC的多文档的开发技能和技巧；利用ADO技术操作SQL Server数据库；掌握数据库的开发和操作技能。 5、即时通讯系统（限最多3人选） 项目描述：系统采用UDP协议，具有：收发在线和离线消息、添加/删除好友、服务器端存储好友列表、在客户端存储好友资料和聊天记录、添加/删除好友组、可以群发消息、收发文件等功能。 主要技能：掌握项目的开发流程：需求分析、详细设计、测试等；熟悉VC的网络通信的开发技能和技巧，包括：TCP和UDP协议、线程等；利用ADO技术操作SQL Server数据库； 6、推箱子（限最多3人选） 【规则】本游戏的目的就是把所有的箱子都推到目标位置上。箱子只能推动而不能拉动。一次只能推动一个箱子。 经典的推箱子是一个来自日本的古老游戏,目的是在训练你的逻辑思考能力。在一个狭小的仓库中,要求把木箱放到指定的位置,稍不小心就会出现箱子无法移动或者通道被堵住的情况,所以需要巧妙的利用有限的空间和通道~！ 7、贪吃蛇（限最多3人选） 【规则】： A 用键盘的方向键控制蛇的上下左右移动。 B 游戏分为三种难度，SLUG为慢速，每吃一朵花得1分；WORM 为中速，每吃一朵花得2分；PYTHON为快速，每吃一朵花得3分。 C 游戏目标：操纵屏幕上那条可爱的小蛇，在黑框中不停吃花，而每吃一朵 算法与数据结构 实验报告 系（院）：计算机科学学院 专业班级：软工11102 姓名：潘香杰 学号： 201104449 班级序号： 18 指导教师：詹泽梅老师 实验时间：2013.6.17 - 2013.6.29 实验地点：4号楼5楼机房 目录 1、课程设计目的．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 2、设计任务．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 3、设计方案．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 4、实现过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 5、测试．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 6、使用说明．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 7、难点与收获．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8、实现代码．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 9、可改进的地方．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 算法与数据结构课程设计是在学完数据结构课程之后的实践教学环节。本实践教学是培养学生数据抽象能力，进行复杂程序设计的训练过程。要求学生能对所涉及问题选择合适的数据结构、存储结构及算法，并编写出结构清楚且正确易读的程序，提高程序设计基本技能和技巧。 一．设计目的 1．提高数据抽象能力。根据实际问题，能利用数据结构理论课中所学到的知识选择合适的逻辑结构以及存储结构，并设计出有效解决问题的算法。 2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3．初步了解开发过程中问题分析、整体设计、程序编码、测试等基本方法和技能。二．设计任务 设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下： ①创建无向图的邻接表 ②无向图的深度优先遍历 ③无向创建无向图的邻接矩阵 ④无向图的基本操作及应用 ⑤图的广度优先遍历 1．有向图的基本操作及应用 ①创建有向图的邻接矩阵 ②创建有向图的邻接表 ③拓扑排序 2．无向网的基本操作及应用 ①创建无向网的邻接矩阵 ②创建无向网的邻接表 ③求最小生成树 3．有向网的基本操作及应用 ①创建有向网的邻接矩阵 ②创建有向网的邻接表 ③关键路径 ④单源最短路径 三．设计方案 第一步：根据设计任务，设计DOS菜单，菜单运行成果如图所示： 数据结构课程设计 设计题目：有向图拓扑排序 专业：信息与计算科学 学号：021240616 姓名：黄秋实 指导教师：文军 2013年11月28日 数据结构课程设计 ----拓扑排序 一需求分析 1.问题描述 本次课程设计题目是：用邻接表构造图然后进行拓扑排序，输出拓扑排序序列 拓扑排序的基本思想为： 1).从有向图中选一个无前驱的顶点输出；2).将此顶点和以它为起点的弧删除；3). 重复1),2)直到不存在无前驱的顶点；4). 若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。 2.拓扑排序有向图拓朴排序算法的基本步骤如下：①从图中选择一个入度为0的顶点，输出该顶点；②从图中删除该顶点及其相关联的弧，调整被删弧的弧头结点的入度（入度-1）；③重复执行①、②直到所有顶点均被输出，拓朴排序完成或者图中再也没有入度为0的顶点（此种情况说明原有向图含有环）。 3基本要求 (1) 输入的形式和输入值的范围； 首先是输入要排序的顶点数和弧数，都为整型，中间用分隔符隔开；再输入各顶点的值，为正型，中间用分隔符隔开；然后输入各条弧的两个顶点值，先输入弧头，再输入弧尾，中间用分隔符隔开，输入的值只能是开始输入的顶点值否则系统会提示输入的值的顶点值不正确，请重新输入，只要继续输入正确的值就行。 (2) 输出的形式； 首先输出建立的邻接表，然后是最终各顶点的出度数，再是拓扑排序的序列，并且每输出一个顶点，就会输出一次各顶点的入度数。 (3) 程序所能达到的功能； 因为该程序是求拓扑排序，所以算法的功能就是要输出拓扑排序的序列，在一个有向图中，若用顶点表示活动，有向边就表示活动间先后顺序，那么输出的拓扑序列就表示各顶点间的关系为反映出各点的存储结构，以邻接表存储并输出各顶点的入度。 二概要设计 1. 算法中用到的所有各种数据类型的定义 在该程序中用邻接表作为图的存储结构。首先，定义表结点和头结点的结构类型，然后定义图的结构类型。创建图用邻接表存储的函数，其中根据要求输入图的顶点和边数，并根据要求设定每条边的起始位置，构建邻接表依次将顶点插入到邻接表中。 拓扑排序的函数在该函数中首先要对各顶点求入度，其中要用到求入度的函数，为了避免重复检测入度为零的顶点，设置一个辅助栈，因此要定义顺序栈类型，以及栈的函数：入栈，出栈，判断栈是否为空。 2.各程序模块之间的层次调用关系 第一部分，void ALGraph *G函数构建图，用邻接表存储。这个函数没有调 ? & 数据结构课程设计报告 —几种排序算法的演示( ； 时间：2010-1-14 … 一需求分析 运行环境 Microsoft Visual Studio 2005 程序所实现的功能 对直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序算法的演示，并且输出每一趟的排序情况。 程序的输入（包含输入的数据格式和说明） % <1>排序种类三输入 <2>排序数的个数的输入 <3>所需排序的所有数的输入 程序的输出（程序输出的形式） <1>主菜单的输出 <2>每一趟排序的输出，即排序过程的输出 " 二设计说明 算法设计思想 <1>交换排序（冒泡排序、快速排序） 交换排序的基本思想是：对排序表中的数据元素按关键字进行两两比较，如果发生逆序（即排列顺序与排序后的次序正好相反），则两者交换位置，直到所有数据元素都排好序为止。 <2>插入排序（直接插入排序、折半插入排序） % 插入排序的基本思想是：每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数据元素。然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序列后，整个排序工作就完成了。 <3>选择排序（简单选择排序、堆排序） 选择排序的基本思想是：第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素，依次重复，每一趟（例如第i趟，i=1，…，n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟选择结束，待排序数据元素仅剩下一个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。 <4>归并排序（两路归并排序） 两路归并排序的基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为 《HTML网页编程技术综合课程设计》教学实施方案 ————————————————————————————————作者：————————————————————————————————日期： 《网页编程技术综合课程设计》教学方案 一、课程设计目标 通过该课程设计综合应用本学期所学的网页制作知识，全面建立对网站的认知，建立网站设计与网页制作的基本思想；学会网站功能规划、网站布局、网页制作、网页配色等的基本技巧，掌握网页制作与网站设计相关软件的使用方法；通过课程设计教学环节能够制作有一定实用性的网站；能解决一些实际应用问题并以此为基础进一步扩展到相关的学科上；通过本课程设计提高网页的审美意识；通过团队合作制作网站，培养团队协作精神，初步了解软件企业开发软件系统模式，为将来适应工作打开良好的基础。 二、设计要求 1．本课程设计分小组进行，各小组成员原则上2~4人，不得超过4人,由小组长协调分工,每个组员充分发挥团队协作精神。 2．自选主题，使用Dreamweaver网页设计与制作软件，设计并制作一个内容完整、结构规范合理的静态网站，要求选取内容健康，网站中出现一定数量的图像和多媒体。网站主题应大小适中、内容健康、具有时代气息；网站提供的信息应与网站主题相符合, 主题突出、内容丰富； 3.页面设计合理、美观，有创意，适用于各种显示器的分辨率和颜色。 4.每个页面都要求有导航条和页脚信息，需要将这些信息制作成库项目，然后根据需要将之插入到模板或其它页面中。各个页面都要有标题，而且布局要合理、美观、大方。布局网页时要尽量主流布局方法（必须使用Div、表格等），并要有一定复杂度。 5.页面中需要有文字、图像、多媒体、超链接等，要求达到图文并茂的效果。所使用的文字的大小、字体和颜色要认真处理，除非特殊需要，不能出现空链接，文字不能简单用截图代替；所需图像和多媒体素材尽量自己设计，如有下载，自己必须再作处理，不得直接使用现有商业网站标志。 6. 为了保证页面的设计效果更好地兼容各种浏览器以及便于改版，要求用独立的CSS文件设置页面内容格式。 7.为主页添加背景音乐。 8.需要使用一定量的JavaScript脚本，使网页具有一定的交互功能。每小组必须制作一个表单，表单输入内容需要使用正则表达式进行验证。 《离散数学》 课程设计 学院计算机学院 学生姓名 学号 指导教师 评阅意见 提交日期 2011 年 11 月 25 日 引言 《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。 实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性） 一、前言引语：二元关系是离散数学中重要的内容。因为事物之间总是可以根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之 间存在的关系。 二、数学原理：自反、对称、传递关系 设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R 就是A×B的一个合于{()∈A×}的子集合 设R是集合A上的二元关系： 自反关系：对任意的x∈A,都满足<>∈R，则称R是自反的，或称R具有自反性，即R在A上是自反的?(?x)((x∈A)→(<>∈R))=1 对称关系：对任意的∈A，如果<>∈R，那么<>∈R，则称关系R是对称的，或称R具有对称性，即R在A上是对称的? (?x)(?y)((x∈A)∧(y∈A)∧(<>∈R)→(<>∈R))=1 传递关系：对任意的∈A，如果<>∈R且<>∈R，那么<>∈R，则称关系R是传递的，或称R具有传递性，即R在A上是传递的? (?x)(?y)(?z)[(x∈A)∧(y∈A)∧(z ∈A)∧((<>∈R)∧(<>∈R)→(<>∈R))]=1 三、实验原理：通过二元关系与关系矩阵的联系，可以引入N维数组，以数组的运算来实现二元关系的判断。 图示： 数据结构课程设计：拓扑排序和关键路径 1 ABSTRACT 1.1图和栈的结构定义 struct SqStack////栈部分 { SElemType *base;//栈底指针 SElemType *top;//栈顶指针 int stacksize;//栈的大小 int element_count;//栈中元素个素 }; /////////AOE网的存储结构 struct ArcNode //表结点 { int lastcompletetime;//活动最晚开始时间 int adjvex; //点结点位置 int info; //所对应的弧的权值 struct ArcNode *next;//指向下一个表结点指针 }; struct VNode //点结点 { VertexType data; //结点标志 int indegree; //该结点入度数 int ve; //记录结点的最早开始时间 int vl; //记录结点的最晚开始时间 struct ArcNode *first_out_arc; //存储下一个出度的表结点struct ArcNode *first_in_arc;//存储下一个入度的表结点 }; struct ALGraph { VNode *vertices; //结点数组 int vexnum; //结点数 int arcnum; //弧数 int kind; //该图的类型 }; 2系统总分析 2.1关键路径概念分析 2.1.1什么是关键路径 关键路径法(Critical Path Method, CPM)最早出现于20世纪50年代，它是通过分析项目过程中哪个活动序列进度安排的总时差最少来预测项目工期的网络分析。这种方法产生的背景是，在当时出现了许多庞大而复杂的科研和工程项目，这些项目常常需要运用大量的人力、物力和财力，因此如何合理而有效地对这些项目进行组织，在有限资源下以最短的时间和最低的成本费用下完成整个项目就成为一个突出的问题，这样CPM就应运而生了。对于一个项目而言，只有项目网络中最长的或耗时最多的活动完成之后，项目才能结束，这条最长的活动路线就叫关键路径（Critical Path），组成关键路径的活动称为关键活动。 2.1.2关键路径特点 关键路径上的活动持续时间决定了项目的工期，关键路径上所有活动的持续时间总和就是项目的工期。 关键路径上的任何一个活动都是关键活动，其中任何一个活动的延迟都会导致整个项目完工时间的延迟。 排序算法： (1) 直接插入排序 (2) 折半插入排序(3) 冒泡排序 (4) 简单选择排序 (5) 快速排序(6) 堆排序 (7) 归并排序 【算法分析】 （1）直接插入排序；它是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的序的有序表中，从而得到一个新的、记录数增加1的有序表。 （2）折半插入排序：插入排序的基本操作是在一个有序表中进行查找和插入，我们知道这个查找操作可以利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。 （3）冒泡排序：比较相邻关键字，若为逆序（非递增），则交换，最终将最大的记录放到最后一个记录的位置上，此为第一趟冒泡排序；对前n-1记录重复上操作，确定倒数第二个位置记录；……以此类推，直至的到一个递增的表。 (4)简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换之。 (5)快速排序:它是对冒泡排序的一种改进，基本思想是，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 (6)堆排序: 使记录序列按关键字非递减有序排列，在堆排序的算法中先建一个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1记录进行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。 (7)归并排序:归并的含义是将两个或两个以上的有序表组合成一个新的有序表。假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序称为2-路归并排序。 【算法实现】 （1）直接插入排序： void InsertSort(SqList &L){ for(i=2;i<=L.length ;i++) if(L.elem[i] 题目1： 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 要求： 1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结 果保存在不同的文件中。 2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 代码如下： #include 设计题目： 示例数据：输入：学期数：5，课程数：12，课程间的先后关系数：16，课程的代表值：v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。课程间两两间的先后关系：v1 v2,v1 v3, v1 v4,v1 v12,v2 v3,v3 v5,v3 v7,v3 v8,v4 v5, v5 v7,v6 v8,v9 v10, v9 v11 , v9 v12,v10 v12,v11 v6 输出：第1学期应学的课程：v1 v9 第2学期应学的课程：v2 v4 v10 v11 第3学期应学的课程：v3 v6 v12 第4学期应学的课程：v5 v8 第5学期应学的课程：v7 一需求分析 1.1 引言 通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义： 若集合X上的关系是R,且R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。 设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。 比较简单的理解：偏序是指集合中只有部分成员可以比较，全序是指集合中所有的成员之间均可以比较。 一般应用：拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。 1.2 拓扑排序的了解 ①.问题的描述 在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排，根据课程之 数据结构课程设计报告 —几种排序算法的演示 时间：2010-1-14 一需求分析 运行环境 Microsoft Visual Studio 2005 程序所实现的功能 对直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序算法的演示，并且输出每一趟的排序情况。 程序的输入（包含输入的数据格式和说明） <1>排序种类三输入 <2>排序数的个数的输入 <3>所需排序的所有数的输入 程序的输出（程序输出的形式） <1>主菜单的输出 <2>每一趟排序的输出，即排序过程的输出 二设计说明 算法设计思想 <1>交换排序（冒泡排序、快速排序） 交换排序的基本思想是：对排序表中的数据元素按关键字进行两两比较，如果发生逆序（即排列顺序与排序后的次序正好相反），则两者交换位置，直到所有数据元素都排好序为止。 <2>插入排序（直接插入排序、折半插入排序） 插入排序的基本思想是：每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数据元素。然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序列后，整个排序工作就完成了。 <3>选择排序（简单选择排序、堆排序） 选择排序的基本思想是：第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素，依次重复，每一趟（例如第i趟，i=1，…，n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟选择结束，待排序数据元素仅剩下一个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。 <4>归并排序（两路归并排序） 两路归并排序的基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为1的首尾相接的n个有序子表（以后称它们为归并项），先做两两归并，得n/2上取整个长度为2的归并项（如果n为奇数，则最后一个归并项的长度为1）；再做两两归并，……，如此重复，最后得到一个长度为n的有序序列。 程序的主要流程图 综合课程设计1 一、考核方法和内容 根据课程设计过程中学生的学生态度、题目完成情况、课程设计报告书的质量和回答问题的情况等按照10%、40%、30%、20%加权综合打分。成绩评定实行优秀、良好、中等、及格和不及格五个等级。评分标准： 优秀：答辩所有问题都能答出+报告良好 或报告良好+实现“提高部分”的功能； 良好：答辩所有问题都能答出+报告一般； 或报告一般+实现“提高部分”的功能； 中等：答辩大部分问题能答出+报告良好； 及格：答辩大部分问题能答出+报告一般； 以下四种，都不及格： 1)答辩几乎答不出问题； 2)报告几乎都是代码； 3)雷同部分达到60%以上； 4)课设报告与数据结构和c/c++关联不大。 课设报告的装订顺序如下： 任务书（签名，把题目要求贴在相应位置，注意下划线）-----目录（注意目录的格式，页码）-----1、设计任务（题目要求）-----2、需求分析（准备选用什么数据逻辑结构？数据元素包含哪些属性？需要哪些函数？为什么要这样设计？最后列出抽象数据类型定义）-----3、系统设计（设计实现抽象数据类型，包含选择什么物理存储方式？数据元素的结构体或类定义，以及各函数的设计思路，算法，程序流程图等）----4、编码实现（重要函数的实现代码）-----5、调试分析（选择多组测试数据、运行截图、结果分析）-----6、课设总结（心得体会）-----7、谢辞-----8、参考文献； 课设报告打印要求： B5纸张打印，报告总页数控制在10—15页内，报告中不能全是代码，报告中代码总量控制在3页内。版式：无页眉，有页码，页码居中 字号：小四，单倍行距 字体：宋体+Times new Romar 截图：截图要配图的编号和图的题目，如：“图1 Insert函数流程图” 二、课程设计的具体内容 1.想要优，必须实现“提高部分”的功能，但，实现“提高部分”不代表一定优； 2.其他成绩，不用完成“提高部分”。 要求：全部采用数据结构课程中的内容实现，采用C或C++实现，逻辑结构只能选线性结构、树型结构、图型结构、集合结构中的一种，不能用数据库。 1、算术表达式求解 基本要求：给定一个算术表达式，通过程序求出最后的结果。 (1)从键盘输入要求解的算术表达式； (2)采用栈结构进行算术表达式的求解过程； 实验六图的应用及其实现 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 [题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。 测试数据：教材图7.28 [题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据：教材图7.29 三、实验步骤 ㈠、数据结构与核心算法的设计描述 基本数据结构： #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如OK 等*/ #define INFINITY INT_MAX //定义无穷大∞ #define MAX_VERTEX_NUM 20 typedef int V ertexType; typedef int InfoType; typedef struct ArcNode // 表结点定义 { InfoType info; int adjvex; //邻接点域，存放与V i邻接的点在表头数组中的位置ArcNode *nextarc; //链域，指示依附于vi的下一条边或弧的结点， }ArcNode; typedef struct VNode //表头结点 { int data; //存放顶点信息 struct ArcNode *firstarc; //指示第一个邻接点 }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { //图的结构定义 沈阳航空航天大学 课程设计报告 课程设计名称：数据结构课程设计 课程设计题目：拓扑排序算法 院（系）：计算机学院 专业：计算机科学与技术（嵌入式系统方向） 班级：14010105班 学号：2011040101221 姓名：王芃然 指导教师：丁一军 目录 沈阳航空航天大学.................................................... I 1 课程设计介绍.. (1) 1.1课程设计内容 (1) 1.2课程设计要求 (1) 2 课程设计原理 (2) 2.1课设题目粗略分析 (2) 2.2原理图介绍 (2) 2.2.1 功能模块图 (2) 2.2.2 流程图分析 (3) 3 数据结构分析 (7) 3.1存储结构 (7) 3.2算法描述 (7) 4 调试与分析 (12) 4.1调试过程 (12) 4.2程序执行过程 (12) 参考文献 (15) 附录（关键部分程序清单） (16) 1 课程设计介绍 1.1 课程设计内容 由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。若在图一的有向图上人为的加一个表示V2<=V3的弧(“<=”表示V2领先于V3)则图一表示的亦为全序且这个全序称为拓扑有序,而由偏序定义得到拓扑有序的操作便是拓扑排序。在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。编写算法建立有向无环图，主要功能如下： 1.能够求解该有向无环图的拓扑排序并输出出来； 2.拓扑排序应该能处理出现环的情况； 3.顶点信息要有几种情况可以选择。 1.2 课程设计要求 1.输出拓扑排序数据外，还要输出邻接表数据； 2.参考相应的资料，独立完成课程设计任务； 3.交规范课程设计报告和软件代码。 数据结构课程设计报告 学院：计算机科学与工程 专业：计算机科学与技术 班级：09级班 学号： 姓名： 指导老师: 时间: 2010年12月 一、课程设计题目：1、哈夫曼编码的实现 2、城市辖区地铁线路设计 3、综合排序算法的比较 二、小组成员： 三、题目要求： 1．哈夫曼编码的实现 （1）打开若干篇英文文章，统计该文章中每个字符出现的次数，进一步统一各字符出现的概率。 （2）针对上述统计结果，对各字符实现哈夫曼编码 （3）对任意文章，用哈夫曼编码对其进行编码 （4）对任意文章，对收到的电文进行解码 2．某城市要在其各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要合理安排地铁的建设路线。 （1）从包含各辖区的地图文件中读取辖区的名称和各辖区的直接距离 （2）根据上述读入的信息，给出一种铺设地铁线路的解决方案。使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。 （3）输出应该建设的地铁路线及所需要建设的总里程信息。 3．综合排序算法的比较 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概的执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动的次数。 （1）对以下各种常用的内部排序算法进行比较： 直接插入排序，折半插入排序，二路归并排序，希尔排序，冒泡排序，快速排序，简单选择排序，堆排序，归并排序，基数排序。 （2）待排序的表长不少于100，要求采用随机数。 （3）至少要用5组不同的输入数据做比较：比较的次数为有关键字参加的比较次数和关键字移动的次数 （4）改变数据量的大小，观察统计数据的变化情况。 （5）对试验统计数据进行分析。对各类排序算法进行综合评价。 四、项目安排： 1、小组内分工合作 分工：负责哈夫曼编码的实现，负责城市辖区地铁线路设计，负责综合排序算法的比较。 合作：组内，组外进行交流，组长帮助解决组员的在项目过程中的困难，并控制进度。 五、完成自己的任务：数据结构课程设计-排序
大数据结构拓扑排序实验报告材料
数据结构拓扑排序课程设计
算法排序问题实验报告
综合课程设计
实验报告
拓扑排序课程设计报告
数据结构课程设计报告---几种排序算法的演示(附源代码)
《HTML网页编程技术综合课程设计》教学实施方案
离散数学实验报告四个实验
数据结构课程设计：拓扑排序和关键路径复习进程
数据结构课程设计排序算法总结
数据结构课程设计之综合排序代码及使用方法
教学计划安排检验程序(拓扑排序)报告书
数据结构课程设计报告---几种排序算法的演示(附源代码)
综合课程设计1题目2016-2017.2
图的应用的实验报告
拓扑排序课程设计报告
数据结构 课程设计报告(排序算法比较)