南华大学 数据结构课程实验报告-归并排序技术

南华大学

计算机科学与技术学院实验报告

（2015 ~ 2016 学年度第1 学期）

课程名称数据结构

实验名称归并排序技术

姓名刘让洲学号20140440734

专业计算机类班级计类07班

地点8-606 教师曹军

归并排序技术

一、实验目的

1.掌握归并排序算法的基本思想；

2.掌握归并排序算法的实现方法；

二、实验内容

给定n个记录的有序序列A[n]和m个记录的有序序列B[m]，将它们归并为一个有序序列，存放在C[m+n]中。

三、设计与编码

1.本实验用到的理论知识

本实验主要用到归并排序技术，归并排序技术的基本思想是：将若干个有序序列逐步归并，最终归并为一个有序序列。

2.算法设计

设三个参数i，j，k分别指向两个待归并的有序序列和最终的有序序列的当前记录，初始值都为0，i=0和j=0表示分别指向数组A[n]和B[m]中的第一个元素，而k=0表示指向存放归并结果的第一个位置。然后，比较i和j所指记录的关键码，取出小的那个元素作为归并结果存放到k所指的位置，并将i和k往后移动，直到两个有序序列之一的所有记录都取完，再讲另一个有序序列剩余的记录顺序复制到归并后的有序序列中。

一次归并的C++算法如下：

void Unoin (int A[ ], int n, int B[ ], int m, int C[ ]) {

int i=0,j=0,k=0;

while(i

if(A[i]<=B[j]) C[k++]=A[i++];

else C[k++]=B[j++];

}

while(i

while(j

}

3.编码（源程序）

#include

using namespace std;

const int N=4;

const int M=6;

//函数声明

void Union(int A[],int n,int B[],int m, int C[]);

//函数功能的实现

void Union(int A[],int n,int B[],int m, int C[]){

int i=0,j=0,k=0;

while(i

if(A[i]<=B[j]) C[k++]=A[i++];

else C[k++]=B[j++];

}

while(i

while(j

}

//主函数

int main(){

int a[N]={3,9,13,15};

int b[M]={1,2,5,10,14,19};

int c[M+N];

Union(a,4,b,6,c);

//输出归并排序的结果

for(int i=0;i<10;i++){

cout<

}

}

四、运行与测试

测试数据：a[N]={3,9,13,15};

b[M]={1,2,5,10,14,19};

程序运行结果：

五、总结与心得

总的来说，这个实验还是比较简单的，花的时间也不是很多，归并排序算法个人觉得还是非常容易理解和接受的。通过本次实验，我对归并排序算法的基本思想以及如何实现归并算法有了更加深刻的了解，真正的学到了一种很容易理解和实现和排序算法。以后遇到需要排序的问题有了新的思路。

最后，非常感谢曹军老师这半学期来的教导，个人觉得曹军老师很负责，尤其上实验课时，都亲自检查同学们写到程序，遇到不懂得问题会及时解答，确保同学们真真正正的学到了知识。

人事管理系统-软件工程实验报告

软件工程实验报告 课题：人事管理系统学生姓名： 学号： 专业班级： 指导教师： 同组成员：

需求分析 一、实验目的 掌握软件需求的结构化分析方法。 二、实验任务与实验要求 导出系统详细的逻辑模型，这里用数据流图来表示。 三、实验内容 （1）功能分析 经过初步分析“人事管理系统”应该具备以下主要功能。 1、职员个人信息资料的增加、修改和删除； 2、职员的考勤录入和查询； 3、职员工资结算和查询； 4、人事管理人员的变化和操作授权； 由于是使用计算机管理，就带来了新的功能：用户登陆、操作人员的管理、基本数据的维护、由数据安全产生的数据备份与恢复。 （2）、关系模式 在满足函数依赖和无损连接的基础上，使数据的设计更加合理。在本系统中只有3个实体，那就是普通员工、管理员、超级管理员，他们权限的不听通过角色来区分。在整个系统中超级管理员只有一人，管理员二人。一个人只可以在普通员工、管理员、超级管理员中处于一个角色，而不可以兼任。其具体的关系模式如下： 普通员工（员工号，密码，姓名，性别，出生年月，身份证号，联系电话，就职时间） 管理员（管理员号，密码，姓名，性别，出生年月，身份证号，联系电话，就职时间） 超级管理员（超级管理员号，密码，姓名，性别，出生年月，身份证号，联系电话，就职时间） 工资（员工号，时间，基本工资，提成，奖金） 考勤（员工号，时间，迟到，早退，管理员号） 注意：“”表示主码，“”表示既是主码又是外码。 E-R图如下所示

数据字典设计： 为了方便数据库的管理和维护，本系统只设计一个数据库workers.mdb，其中包含worker（员工信息表）、manager（考勤信息表）、booklist（工资信息表） 表1-1 worker（员工信息表）各字段设计 表1-2 monit （考勤信息表）各字段设计

(完整版)数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include// 库头文件------ 动态分配内存空间 typedef int elemtype;// 定义数据域的类型 typedef struct linknode// 定义结点类型 { elemtype data;// 定义数据域 struct linknode *next;// 定义结点指针 }nodetype; 2）创建单链表

nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<> d; if(d==0) break;// 以0 表示输入结束 if(i==1)// 建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));// 表示指针h h->data=d;h->next=NULL;t=h;//h 是头指针 } else// 建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t 始终指向生成的单链表的最后一个节点

数据结构课程设计(内部排序算法比较_C语言)

数据结构课程设计 课程名称：内部排序算法比较 年级/院系：11级计算机科学与技术学院 姓名/学号： 指导老师： 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。

第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 （2）选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------|

实验报告格式范文

实验报告格式范文 实验一撰写可行性研究报告 一、实验目的 1、掌握可行性研究步骤； 2、学习编制可行性研究报告。 二、实验要求 硬件：Intel Pentium 120 或以上级别的CPU，大于16MB的内存。 软件：Win dows 95/98/2000 操作系统，Office 97/2000 软件 学时：2学时 写岀此项实验报告 三、实验内容 1、可行性研究(结构化分析)方法； 2、绘制数据流图，使用Word写实验报告。 四、实验步骤 1 ?引言 1.1 编写目的 可行性研究的目的是为了对问题进行研究，以最小的代价在最短的时间内确定问题是否可解。 经过对此项目进行详细调查研究，初拟系统实现报告，对软件开发中将要面临的问题及其解决方案进行初步设计及合理安排。明确开发风险及其所带来的经济效益。本报告经审核后，交软件经理审查。 1 . 2 项目背景 (1 )待开发的软件产品名称：旅行社机票预定系统。 (2)本项目的提岀者：冯剑。开发者：李翀。用户：旅行社 (3)本软件产品将用于旅行社的机票预定和费用的记录。

1 . 3术语说明 DFD (数据流图)：一种描述书记变换的图形工具，是结构化分析方法最普遍采用的表示手段，但数据流图并不是结构化分析模型的全部，数据字典和小说明为数据流图提供了补充，并用以验证图形表示的正确性、一致性和完整性，三者共同构成了被建系统的模型。 1 . 4.系统参考文献 参考文献见附录 2?可行性研究的前提 2.1基本要求 ⑴功能 本软件实现的功能有：为游客提供机票预定服务，提高旅游局的服务质量和服务效率。 对航班数据库的查询和修改，对机票费用记帐数据库的查询和修改，记录旅客信息(姓名、性别、年龄、身份证号、单位、旅行时间、目的地)、航班时间和班次，打印机票和帐单。 (2) 性能 时间：提供的信息必须及时的反映在工作平台上。售票系统的定单必须无差错的存 储在机场的主服务器上。对服务器上的数据必须进行及时正确的刷新。一笔业务在一分钟内完成。空间：运行空间 2M。 (3) 系统的输入和输岀 输入：旅行社定票单。数据完整，详实。 输岀：机票、帐单。简捷，快速，实时。 (4) 处理流程 旅行社将定票信息输入定票系统，系统输岀机票和帐单给旅客。 5 ）安全保密要求

数据结构实验报告完整

华北电力大学 实验报告| | 实验名称数据结构实验 课程名称数据结构 | | 专业班级：学生姓名： 学号：成绩： 指导教师：实验日期：2015/7/3

实验报告说明： 本次实验报告共包含六个实验，分别为：简易停车场管理、约瑟夫环（基于链表和数组）、二叉树的建立和三种遍历、图的建立和两种遍历、hash-telbook和公司招工系统。 编译环境：visual studio 2010 使用语言：C++ 所有程序经调试均能正常运行 实验目录 实验一约瑟夫环（基于链表和数组） 实验二简易停车场管理 实验三二叉树的建立和三种遍历 实验四图的建立和两种遍历 实验五哈希表的设计

实验一：约瑟夫环 一、实验目的 1.熟悉循环链表的定义和有关操作。 二、实验要求 1.认真阅读和掌握实验内容。 2．用循环链表解决约瑟夫问题。 3.输入和运行编出的相关操作的程序。 4.保存程序运行结果 , 并结合输入数据进行分析。 三、所用仪器设备 1.PC机。 2.Microsoft Visual C++运行环境。 四、实验原理 1.约瑟夫问题解决方案： 用两个指针分别指向链表开头和下一个，两指针依次挪动，符合题意就输出结点数据，在调整指针，删掉该结点。 五、代码 1、基于链表 #include using namespace std; struct Node { int data; Node* next; }; void main() { int m,n,j=1; cout<<"请输入m的值：";cin>>m; cout<<"请输入n的值：";cin>>n; Node* head=NULL; Node* s=new Node; for(int i=1;i<=n;i++) { Node* p=new Node; p->data=n+1-i;

数据结构实验八内部排序

实验八内部排序 一、实验目的 1、掌握内部排序的基本算法； 2、分析比较内部排序算法的效率。 二、实验内容和要求 1. 运行下面程序： #include #include #define MAX 50 int slist[MAX]; /*待排序序列*/ void insertSort(int list[], int n); void createList(int list[], int *n); void printList(int list[], int n); void heapAdjust(int list[], int u, int v); void heapSort(int list[], int n); /*直接插入排序*/ void insertSort(int list[], int n) { int i = 0, j = 0, node = 0, count = 1; printf("对序列进行直接插入排序：\n"); printf("初始序列为：\n"); printList(list, n); for(i = 1; i < n; i++) { node = list[i]; j = i - 1; while(j >= 0 && node < list[j]) { list[j+1] = list[j]; --j; } list[j+1] = node; printf("第%d次排序结果：\n", count++); printList(list, n); } } /*堆排序*/ void heapAdjust(int list[], int u, int v)

排序算法比较实验报告

信息学部算法分析 上机报告 学号0901******** 姓名陈龙 指导老师秦明 时间2011.11.1~11.23

一．上机实验题目 实验1 比较归并排序和快速排序的区别。 实验2 利用贪心算法对背包问题进行求解。 二．算法设计思路 归并排序： 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列，设定两个指针，最初位置分别为两个已经排序序列的起始位置，比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置，重复步骤直到某一指针达到序列尾，将另一序列剩下的所 有元素直接复制到合并序列尾。 快速排序： 设置两个变量I、J，排序开始的时候：I=0，J=N-1；以第一个数组元素作为关键数据，赋值给key，即key=A[0]；从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，并与key交换；从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，与key交换；重复第3、4、5步，直到I=J；(3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i，j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。) 背包问题： 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 。可以压缩空间，f[v]=max{f[v],f[v-c[i]]+w[i]}

三. 源程序 归并排序 #include #include # define N 50 int b[N],a[N]; int n,i; void Merge (int low, int mid,int high) //合并 { int i; int l=low,h=mid+1,k=l; while ((l<=mid) && (h<=high)) //部分合并 { if (a[l]<=a[h]) b[k++]=a[l++]; else b[k++]=a[h++]; } if(l>mid) while (h<=high) b[k++]=a[h++]; //转储剩余部分 else while(l<=mid) b[k++]=a[l++]; for (i=0;i<=high;i++) //将b数组转储到a a[i]=b[i]; } int Merge2 (int l,int h) //分类 { for (i=0;i

数据流图实验报告

数据流图实验报告 篇一：软件工程实验报告 篇二：需求分析实验报告 软件工程实践报告 计科12—1班 杨光敏 08123234 （一）软件需求分析 1.实验目的 学习图形工具软件VISIO，掌握结构化需求分析方法，熟练绘制数据流图；学习快速原型工具的使用。 2.基本要求 （1）针对银行ATM系统进行需求分析工作，了解银行ATM系统的功能、流程；（2）安装VISIOXX以上版本软件，熟练应用Visio绘制DFD图，绘制银行ATM系统数据流图，完成系统的软件逻辑模型； （3）安装Axure RP Pro 或者Balsamiq Mockups快速原型软件，学习绘制软件原型，完成银行ATM系统的软件原型。 3.系统概述 （1）ATM系统为银行提供一套高效稳定可靠的终端服务平台，为储户登录，

存款，取款，查询，打印凭条，转账，修改密码等操作提供便利。 图1 ATM工作流程 （2）.用户特点 本软件的用户主要是银行的广大持卡人，大多都具有使用ATM经验。另外，我们的系统要实现的一个重要目标就是当储户取钱出现故障时能在下笔业务进行之前自动恢复。以此来方便用户和保障用户的利益。本系统还为用户提供了足够的界面友好性和易操作性。即使是一个对ATM系统完全陌生的客户，也可以在交易界面的提示下顺利完成交易。 另外一部分的用户是银行工作人员，本系统不予考虑。 4需求说明 (1) 基本描述 ATM终端可以接受一张可识别的银行储蓄卡，通过储户身份验证后，同储户进行各种交互，例如：查询、存款、取款、打印凭条等；处理储户相应的要求，执行对应操作，为储户服务。该系统要求须保持一定时间内的交易记录，系统应每天自动汇总各种交易数据与服务器进行对账。同时，在通讯失败或其他交易结果不确定的情况下，ATM要自动发起冲正交易，以保证账务的完整性。 本系统的实现需要记录一些相关信息，其中包括的信息有：用户信息和交易信息。

数据结构课程设计排序实验报告

《数据结构》课程设计报告 专业 班级 姓名 学号 指导教师 起止时间

课程设计：排序综合 一、任务描述 利用随机函数产生n个随机整数（20000以上），对这些数进行多种方法进行排序。（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 （2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 要求：根据以上任务说明，设计程序完成功能。 二、问题分析 1、功能分析 分析设计课题的要求，要求编程实现以下功能： （1）随机生成N个整数，存放到线性表中； （2）起泡排序并计算所需时间； （3）简单选择排序并计算时间； （4）希尔排序并计算时间； （5）直接插入排序并计算所需时间； （6）时间效率比较。 2、数据对象分析 存储数据的线性表应为顺序存储。 三、数据结构设计 使用顺序表实现，有关定义如下： typedef int Status; typedef int KeyType ; //设排序码为整型量 typedef int InfoType; typedef struct { //定义被排序记录结构类型 KeyType key ; //排序码 I nfoType otherinfo; //其它数据项 } RedType ; typedef struct { RedType * r; //存储带排序记录的顺序表 //r[0]作哨兵或缓冲区 int length ; //顺序表的长度 } SqList ; //定义顺序表类型 四、功能设计 （一）主控菜单设计

实验分析数据流和绘制数据流图

实验报告课程名称_软件工程导论__________ 学院____计算机工程学院_________班级14软件1班 学号2014144141 姓名秦川 2016年11月8日

批阅教师时间实验成绩 课程名称软件工程 学号2014144141姓名秦川实验日期2016.11.8实验名称实验2分析数据流和绘制数据流图 实验目的： 1、掌握数据流的分析方法 2、掌握数据流图的绘制 实验内容： 任务一绘制数据流图 任务二分析数据流和绘制数据流图 案例一：总务办公管理系统 案例二：火车票预订系统 实验原理： 数据流图（DFD）是软件系统系统的逻辑模型，仅仅描绘数据在软件中流动（从输入移动到输出）的过程中所经受的变换（即加工处理）。 数据流图的绘制方法：根据数据流图的四种成分：源点或终点，处理，数据存储和数据流，从问题描述中提取数据流图的四种成分；然后依据“自顶向下、从左到右、由粗到细、逐步求精”的基本原则进行绘制。 基本符号如下：

实验过程与结果： 1．运行Microsoft Office Visio2007 运行Microsoft Office Visio2007 2．选择“软件和数据库”中的“数据流模型图”模板 选中数据流模型图模板

3．用鼠标选拉图标进行绘图 任务一绘制数据流图 试绘制工资管理系统的数据流图，根据数据流图的符号说明仔细理解下图含义： 这是学校教职工工资管理系统，教师根据课时表，职工根据任务表来确定个人工资情况，数据按以下方向传递： 首先，对课时表或任务表进行审核，审核后的数据经排序形成专用表格； 再进行一系列额外计算，包括个人所得说、住房公积金、保险费得出具体所发工资，并将工资表发给银行； 然后，向教职工展示工资所得明细； 最后，形成编制报表，更新分类表后，交于会计。 其中，人事科负责人事数据，教师与职工的工资由银行发放，会计做好报表的统计。

数据结构实验报告图实验

图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;

template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp

#include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) {

数据结构课程设计(内部排序算法比较 C语言)

课题：内部排序算法比较 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------|

|-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| （3.1） （II）方便快捷的操作：用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！如图（3.2所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------|

算法设计实验一归并排序(分治)和插入排序的比较分析

沈阳化工大学实验报告 课程名称算法设计与分析 项目名称归并排序(分治)和插入排序的比较 学院应用技术学院 专业计中职1401 指导教师张雪 报告人张庭浩学号 1422030125 实验时间 2016.11.05 提交时间 2016.11.05

一、实验目的 1.理解和掌握分治算法的相关内容。 2.具体完成插入排序和归并排序性能的比较。 二、实验内容 编写一个真随机函数，随机产生大量数字。在产生相同的一组大量随机数字后，分别用归并排序和插入排序两种算法进行排序，并通过时间函数分别计算出运行的时间。 三、伪代码 1.归并排序 /*数组a[]是原始数组，数组b[]是目标数组*/ 归并排序（数组a[],数组b[]）{ `分割与归并（数组a[],0, a.length,数组b[]) } /*通过递归把要排序的子序列分的足够小*/ 分割与归并（数组a[],起始位置,结束位置,数组b[]){ if(结束位置- 起始位置< 2) 返回 中间位置= （起始位置+结束位置）/2 分割与归并（数组a[],起始位置,中间位置,数组b[]) 分割与归并（数组a[],中间位置,结束位置,数组b[]) 归并（数组a[],起始位置，中间位置，结束位置，数组b[]) 拷贝（数组a[],起始位置，结束位置，数组b[]) } 归并（数组a[],起始位置，中间位置，结束位置，数组b[]){ i0 = 起始位置，i1 = 中间位置 for j = 起始位置到结束位置 if(i0 < 中间位置且（i1 > 结束位置或a[i0] <= a[i1]){ //当i0没有超过中间位置时，有两种情况要将a[i0]复制到b[j]上： //1.i1已经超过结束位置，只要把剩下的复制过来就好； //2.a[i0]比a[i1]小 b[j]=a[i0] i0++ } else { b[j]=a[i1] i1++ } }

南邮数据结构上机实验四内排序算法的实现以及性能比较

实验报告 （2015 / 2016学年第二学期） 课程名称数据结构A 实验名称内排序算法的实现以及性能比较 实验时间2016 年 5 月26 日 指导单位计算机科学与技术系 指导教师骆健 学生姓名耿宙班级学号B14111615 学院(系) 管理学院专业信息管理与信息系统

—— 实习题名:内排序算法的实现及性能比较 班级 B141116 姓名耿宙学号 B14111615 日期2016.05.26 一、问题描述 验证教材的各种内排序算法，分析各种排序算法的时间复杂度；改进教材中的快速排序算法，使得当子集合小于10个元素师改用直接插入排序；使用随即数发生器产生大数据集合，运行上述各排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h”中。 二、概要设计 文件Sort.cpp中包括了简单选择排序SelectSort()，直接插入排序InsertSort()，冒泡排序BubbleSort()，两路合并排序Merge()，快速排序QuickSort()以及改进的快速排序GQuickSort()六个内排序算法函数。主主函数main的代码如下图所示： 三、详细设计 1.类和类的层次设计 在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机 生成的数列进行排列，并进行性能的比较，除此之外还对快速排序进行了改进。下图为主函 数main的流程图：

——

main() 2.核心算法 1)简单选择排序： 简单选择排序的基本思想是：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到

软件工程实验报告

软 件 工 程 实 验 报 告 班级：计算机科学与技术1102班 学号：1108030209 姓名：蒙雨茹

实验一：使用Microsoft Visio 1.1实验目的： (1)熟悉Visio的工作环境及组成。 (2)掌握Visio软件绘制图表的基本操作。 (3)掌握基本流程图的设计方法。 1.2实验内容： 绘制基本流程图 1.3实验步骤： (1)打开一个模板，，在主菜单中依次选择【文件】->【新建】->【选 择绘图类型】，出现“选择绘图类型”窗口，在【类别】下，单击 【流程图】，在【模板】下，单击【基本流程图】。 (2)添加形状，将【形状】窗口中模具上的自己需要的形状拖到绘图页 面中合适的位置。并添加文本、连接不同形状，使流程图完整的显 现出来。 1.4实验结果：

实验二：数据流图 2.1 实验目的 (1)熟悉Visio的工作环境及组成。 ⑵掌握Visio软件绘制图表的基本操作。 ⑶掌握数据流图的设计方法。 2.2 实验内容 习题3-3，3-4，3-5 2.3 实验步骤 （1）打开模板 ①在主菜单中，依次选择【文件】——【新建】——【选择绘图类型】，出现“选择绘图类型”窗口。 ②在左侧【类别】下，单击【软件】。 ③在右侧【模板】下，单击【数据流模型图】。 (2)绘制顶层图 ①在顶层进程页面中添加、移动图形元素并调整其大小。将所需要元素用鼠标拖动到模板里，添加所需的元素符号。 接口：输入源点或输出终点，其中注明源点或终点的名称。 进程：即处理，输入数据在此进行变换产生输出数据，其中注明进程的名称。数据存储：用于代表系统中存储的信息，其中注明信息的名称。 数据流：被加工的数据及其流向。流线上注明数据名称，箭头代表数据流动方向。 ②向图形元素中添加文本，并修改数据流图中的文字和格式。 连接图形元素。 ③使用“数据流”连接线将“接口”、“进程”和“数据存储”等形状互相连接起来。 逻辑连接：将数据流起点、终点拖拽到进程或接口中央位置，进程或接口被红色框包围时松开鼠标，这时可看到数据流符号相应端点为红色方框。拖动进程或接口，可看到流据流的端点随着进程或接口的移动而移动。

数据结构课程设计(内部排序算法比较-C语言)

` 课题：内部排序算法比较… 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： !

|******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| ~ 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 、 第三章系统设计 （I）友好的人机界面设计：（如图所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| ： （）

排序问题实验报告

2010级数据结构实验报告 实验名称：排序 姓名：袁彬 班级： 2009211120 班内序号： 09 学号： 09210552 日期： 2010 年12 月19 日 1．实验要求 试验目的： 通过选择试验内容中的两个题目之一，学习、实现、对比各种排序的算法，掌握各种排序算法的优缺点，以及各种算法使用的情况。 试验内容： 题目一： 使用简单数组实现下面各种排序算法，并进行比较。 排序算法如下： ①插入排序； ②希尔排序 ③冒泡排序； ④快速排序； ⑤简单选择排序； ⑥堆排序 ⑦归并排序 ⑧基数排序 ⑨其他。 具体要求如下： ①测试数据分为三类：正序，逆序，随机数据。 ②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。 ③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。 ④对②和③的结果进行分析，验证上述各种算法的时间复杂度。 ⑤编写main()函数测试各种排序算法的正确性。 题目二： 使用链表实现下面各种排序算法，并进行比较。 排序算法如下： ①插入排序； ②冒泡排序； ③快速排序；

④简单选择排序； ⑤其他。 具体要求如下： ①测试数据分为三类：正序，逆序，随机数据。 ②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。 ③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙（选作） ④对②和③的结果进行分析，验证上述各种算法的时间复杂度。 ⑤编写main()函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构 程序中每一个算法均是用一个类来表示的，类中有自己的构造函数、排序函数。 程序的储存结构采用数组。数组的第一个位置不存储数据。数据从第二个位置开始。数组中的相对位置为数组的下标。 2.2 关键算法分析 ㈠、关键算法： 1、插入排序函数：Insert s ort(int n) ①、从2开始做循环，依次和前面的数进行比较：for(int i=2;i<=n;i++) ②、如果后面的比前面的小，则进行前移：if(number[i]=1;d=d/2) ②、在自己的间隔中进行简单插入排序，进行循环：for(int i=d+1;i<=n;i++) ③、如果后面的数据比前面的小，进行前移：if(number[i]0;j=j-d) ⑥、大的数据后移：number[j+d]=number[j]; ⑦、哨兵归位：number[j+d]=number[0]; 3、冒泡排序函数：Bubble s ort(int n) ①、设置有序无序的边界点：int pos=n; ②、当边界点不为空进行循环：while(pos!=0) ③、边界点传递给bound：int bound=pos; ④、从开始到边界点进行循环：for(int i=1;inumber[i+1]) ⑥、交换：number[0]=number[i];number[i]=number[i+1];number[i+1]=number[0]; ⑦、从小设置边界点：pos=i; 4、一趟快速排序函数：partion(int first,int end) ①、传递设置整个数据的起点和终点：int i=first;int j=end; ②、设置中轴：number[0]=number[i]; ③、当end大于first进行循环：while(i

软件工程实验报告_学生成绩管理系统

软件工程实验报告 学生成绩管理系统的设计与实现 学生姓名 学号 班级 成绩 指导教师 年月日

目录 1 课题描述 (3) 2 可行性研究 (4) 2.1 编写目的 (4) 2.2 项目背景 (4) 2.3 定义（术语） (4) 2.4 数据流程和处理流程 (4) 2.5 可行性分析的前提 (5) 2.6 可行性分析 (5) 3 需求分析 (7) 3.1 学生成绩管理系统功能需求 (7) 3.2 学生成绩管理系统性能要求 (8) 3.3 数据流图 (8) 3.4 数据字典 (9) 3.5 学生信息管理系统逻辑结构图 (12) 3.6 用户信息实体关系图 (12) 4 概要设计 (13) 4.1 编写目的 (13) 4.2 项目背景 (13) 4.3 任务概述 (13) 4.4 总体设计 (13) 4.5接口设计 (17) 4.6数据结构设计 (17) 5 详细设计 (19) 5.1 系统程序流程图 (19) 5.2 界面设计 (21) 5.3 程序界面截图 (22) 5.4 程序源代码 (27) 6 软件测试 (58) 7 总结 (62)

1 课题描述 随着互联网的发展，利用INTERNET 技术来实现“无纸办公”这个概念已经深入人心，校园网作为学校信息化建设的一个平台在完成资源共享、互联网访问、教务管理、电子备课等方面发挥了重要作用。服务教学、提高教学水平和效果是校园网建设的核心目标和核心价值，本系统立足于校园实际，着眼于未来发展，建成符合标准化协议、通用性较强、实用的系统，以提高高校的现代化管理水平，实现信息资源的共享。该项目主要是服务于教学方面，进一步方便教师的工作和学生的学习，从而从侧面达到提高学校的教学方面‘软件’质量。可以说它适用于每一所高校，因此很有开发价值。我们不敢说该产品是所有该系列产品中最好的，但是我们这里要强调的是它具有使用范围广，实用性强，使用简单，所花经费少等优点。我们可以肯定的说它将在高校的使用过程中其优点将得到最充分的体现。 主要功能有三方面： 管理员，登陆，进入系统，可以进行管理员操作，进行学生信息、教师信息、课程信息的编辑、查询、删除、修改、添加、打印等操作。 学生，登陆，进入系统，可以进行查询、修改、打印等操作。 教师，登陆，进入系统，可以进行查询、学生成绩录入、修改、打印等操作。 软件系统目标： （1）本系统具有很强的可靠行，可以对录入的学生信息进行效验，对数据进行修改、删除，规定各种权限。 （2）本系统中的模块具有很强的可续性，可以方便管理人员的修改与维护。 （3）本系统操作方便、灵活、简单。 （4）本系统可高效、快速的查询到学生的基本信息。

数据结构实验报告--图实验

图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e)

{ int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: "; cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } } template void MGraph::DFSTraverse(int v) { cout << vertex[v]; visited[v] = 1; for(int j = 0; j < vertexNum; j++) if(arc[v][j] == 1 && visited[j] == 0) DFSTraverse(j); } template void MGraph::BFSTraverse(int v) { int Q[MaxSize]; int front = -1, rear = -1; cout << vertex[v]; visited[v] = 1; Q[++rear] = v; while(front != rear) { v = Q[++front]; for(int j = 0;j < vertexNum; j++) if(arc[v][j] == 1 && visited[j] == 0){ cout << vertex[j]; visited[j] = 1;