《数据结构》课程设计报告
专业
班级
姓名
学号
指导教师
起止时间
课程设计:排序综合
一、任务描述
利用随机函数产生n个随机整数(20000以上),对这些数进行多种方法进行排序。
(1)至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。并把排序后的结果保存在不同的文件中。
(2)统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的方法。
要求:根据以上任务说明,设计程序完成功能。
二、问题分析
1、功能分析
分析设计课题的要求,要求编程实现以下功能:
(1)随机生成N个整数,存放到线性表中;
(2)起泡排序并计算所需时间;
(3)简单选择排序并计算时间;
(4)希尔排序并计算时间;
(5)直接插入排序并计算所需时间;
(6)时间效率比较。
2、数据对象分析
存储数据的线性表应为顺序存储。
三、数据结构设计
使用顺序表实现,有关定义如下:
typedef int Status;
typedef int KeyType ; 直接插入排序
0. 退出系统
(二)程序模块结构
由课题要求可将程序划分为以下几个模块(即实现程序功能所需的函数):
主控菜单项选择函数menu()
创建排序表函数InitList_Sq()
起泡排序函数Bubble_sort()
简单选择排序函数SelectSort()
希尔排序函数ShellSort();
对顺序表L进行直接插入排序函数Insertsort()
(三)函数调用关系
程序的主要结构(函数调用关系)如下图所示。
其中main()是主函数,它负责调用各函数。进行调用菜单函数menu(),根据选择项0~4调用相应的函数。
main()函数使
for循环实现重复选择。其循环结构如下:
for (;;)
{
long start,end;
switch(menu())
{
case 1:
printf("* 起泡排序*\n");
start=clock();
Bubble_sort(L);
end=clock();
printf("%d ms\n",end-start);
fp=fopen("D: 起泡排序.txt","w");
if(fp==NULL)xt","w");
if(fp==NULL)xt","w");
if(fp==NULL)
N
ey,[j].key))
{
flag=1; 共通过n-1趟,得到一个按排序码从小到大排列的有序序列
流程图:
N
N
代码描述:
void SelectSort(SqList &L)
{ ] 中选择key最小的记录
int k=i;
for(int j=i+1;j<= ; j++)
if ( LT[j].key,[k].key)) k=j;
if(k!=i){
x=[i];
[i]=[j];
[j]=x;
}
}
} ey , [i-dk].key ))
{
[0]= [i];
int j;
for(j=i-dk;(j>0)&&(LT [0].key , [j].key ));j-=dk)
[j+dk]= [j];
[j+dk]= [0];
}
}
}
void ShellSort(SqList &L,int dlta[],int t)
N
N
ey,[i-1].key)) ey,[j].key);j--)
{
[j+1]=[j];
ey的元素
[j+1]=[0]; //将暂存在r[0]中的记录插入到正确位置
}
// printf("%d ",[i]);
}
算法的时间复杂度分析:O(n2)
五、测试数据和结果
1、测试数据
随机产生30000个数
2、测试结果
本程序在VC++环境下实现,下面是对以上测试数据的运行结果。
(1) 主菜单显示如下:
六、结束语
本设计完成了课题要求的任务,较熟练地掌握了各种排序方法。在设计过程中,由于个别代码段设计不当多次出现程序溢出情况。在评判各种排序方法的用时上换了两种计时方
法,现在使用的这个较为准确。从结果可以看出,堆排序和快速排序这两种方法最快。当然或许还有更快的排序方法,此处没有使用并列举出来。
拓扑排序 [基本要求] 用邻接表建立一个有向图的存储结构。利用拓扑排序算法输出该图的拓扑排序序列。 [编程思路] 首先图的创建,采用邻接表建立,逆向插入到单链表中,特别注意有向是不需要对称插入结点,且要把输入的字符在顶点数组中定位(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; /*该弧相关信息的指针*/
1.一元稀疏多项式计算器 [问题描述] 设计一个一元稀疏多项式简单计算器。 [基本要求] 输入并建立多项式; 输出多项式,输出形式为整数序列:n, c1, e1, c2, e2,……, cn, en ,其中n是多项式的项数,ci, ei分别是第i项的系数和指数,序列按指数降序排序; 多项式a和b相加,建立多项式a+b; 多项式a和b相减,建立多项式a-b; [测试数据] (2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3) (1+x+x2+x3+x4+x5)+(-x3-x4)=(x5+x2+x+1) (x+x3)+(-x-x3)=0 (x+x2+x3)+0=(x3+x2+x) [实现提示] 用带头结点的单链表存储多项式,多项式的项数存放在头结点中。 2.背包问题的求解 [问题描述] 假设有一个能装入总体积为T的背包和n件体积分别为w1, w2, …,wn的物品,能否从n件物品中挑选若干件恰好装满背包,即使w1+w2+…+wn=T,要求找出所有满足上述条件的解。例如:当T=10,各件物品的体积为{1,8,4,3,5,2}时,可找到下列4组解:(1,4,3,2)、(1,4,5)、(8,2)、(3,5,2) [实现提示] 可利用回溯法的设计思想来解决背包问题。首先,将物品排成一列,然后顺序选取物品转入背包,假设已选取了前i件物品之后背包还没有装满,则继续选取第i+1件物品,若该件物品“太大”不能装入,则弃之而继续选取下一件,直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包,则说明“刚刚”装入背包的那件物品“不合适”,应将它取出“弃之一边”,继续再从“它之后”的物品中选取,如此重复,直至求得满足条件的解,或者无解。 由于回溯求解的规则是“后进先出”因此自然要用到栈。 3.完全二叉树判断 用一个二叉链表存储的二叉树,判断其是否是完全二叉树。 4.最小生成树求解(1人) 任意创建一个图,利用克鲁斯卡尔算法,求出该图的最小生成树。 5.最小生成树求解(1人) 任意创建一个图,利用普里姆算法,求出该图的最小生成树。 6.树状显示二叉树 编写函数displaytree(二叉树的根指针,数据值宽度,屏幕的宽度)输出树的直观示意图。输出的二叉树是垂直打印的,同层的节点在同一行上。 [问题描述] 假设数据宽度datawidth=2,而屏幕宽度screenwidth为64=26,假设节点的输出位置用 (层号,须打印的空格数)来界定。 第0层:根在(0,32)处输出;
《数据结构》实验报告排序实验题目: 输入十个数,从插入排序,快速排序,选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路: 1. 插入排序:直接插入排序的基本操作是,将一个记录到已排好序的有序表中,从而得到一个新的,记录增一得有序表。 一般情况下,第i 趟直接插入排序的操作为:在含有i-1 个记录的有序子序列r[1..i-1 ]中插入一个记录r[i ]后,变成含有i 个记录的有序子序列r[1..i ];并且,和顺序查找类似,为了在查找插入位置的过程中避免数组下标出界,在r [0]处设置哨兵。在自i-1 起往前搜索的过程中,可以同时后移记录。整个排序过程为进行n-1 趟插入,即:先将序列中的第一个记录看成是一个有序的子序列,然后从第2 个记录起逐个进行插入,直至整个序列变成按关键字非递减有序序列为止。 2. 快速排序:基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 假设待排序的序列为{L.r[s] ,L.r[s+1],…L.r[t]}, 首先任意选取一个记录 (通常可选第一个记录L.r[s])作为枢轴(或支点)(PiVOt ),然后按下述原则重新排列其余记录:将所有关键字较它小的记录都安置在它的位置之前,将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置i 作为界线,将序列{L.r[s] ,… ,L.r[t]} 分割成两个子序列{L.r[i+1],L.[i+2], …,L.r[t]}。这个过程称为一趟快速排序,或一次划分。 一趟快速排序的具体做法是:附设两个指针lOw 和high ,他们的初值分别为lOw 和high ,设枢轴记录的关键字为PiVOtkey ,则首先从high 所指位置起向前搜索找到第一个关键字小于PiVOtkey 的记录和枢轴记录互相交换,然后从lOw 所指位置起向后搜索,找到第一个关键字大于PiVOtkey 的记录和枢轴记录互相 交换,重复这两不直至low=high 为止。 具体实现上述算法是,每交换一对记录需进行3 次记录移动(赋值)的操作。而实际上,
《数据结构I》三级项目报告 大连东软信息学院 电子工程系 ××××年××月
三级项目报告注意事项 1. 按照项目要求书写项目报告,条理清晰,数据准确; 2. 项目报告严禁抄袭,如发现抄袭的情况,则抄袭者与被抄袭者均 以0分计; 3. 课程结束后报告上交教师,并进行考核与存档。 三级项目报告格式规范 1. 正文:宋体,小四号,首行缩进2字符,1.5倍行距,段前段后 各0行; 2. 图表:居中,图名用五号字,中文用宋体,英文用“Times New Roman”,位于图表下方,须全文统一。
目录 一项目设计方案 (3) 二项目设计分析 (4) 三项目设计成果 (4) 四项目创新创业 (5) 五项目展望 (6) 附录一:项目成员 (6) 附录二:相关代码、电路图等 (6)
一项目设计方案 1、项目名称: 垃圾回收 2、项目要求及系统基本功能: 1)利用数据结构的知识独立完成一个应用系统设计 2)程序正常运行,能够实现基本的数据增加、删除、修改、查询等功能3)体现程序实现算法复杂度优化 4)体现程序的健壮性 二项目设计分析 1、系统预期实现基本功能: (结合本系统预期具体实现,描述出对应基本要求(增、删、改、查等)的具体功能) 1. 2. 3. 4. 5. 6. 7. 2、项目模块功能描述 (基本分为组织实施组织、程序功能模块编写、系统说明撰写等。其中程序功能子模块实现) 模块一: 主要任务:XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块二: 主要任务:XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块n: 主要任务:XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
算法与数据结构 实验报告 系(院):计算机科学学院 专业班级:软工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菜单,菜单运行成果如图所示:
数据结构课程设计 课程名称:内部排序算法比较 年级/院系:11级计算机科学与技术学院 姓名/学号: 指导老师: 第一章问题描述 排序是数据结构中重要的一个部分,也是在实际开发中易遇到的问题,所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决!该系统通过对各种内部排序算法如直接插入排序,冒泡排序,简单选择排序,快速排序,希尔排序,堆排序、二路归并排序等,以关键码的比较次数和移动次数分析其特点,并进行比较,估算每种算法的时间消耗,从而比较各种算法的优劣和使用情况!排序表的数据是多种不同的情况,如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。
第二章系统分析 界面的设计如图所示: |******************************| |-------欢迎使用---------| |-----(1)随机取数-------| |-----(2)自行输入-------| |-----(0)退出使用-------| |******************************| 请选择操作方式: 如上图所示该系统的功能有: (1):选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 (2)选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 (3)选择0 打印“谢谢使用!!”退出系统的使用!! 第三章系统设计 (I)友好的人机界面设计:(如图3.1所示) |******************************| |-------欢迎使用---------| |-----(1)随机取数-------| |-----(2)自行输入-------| |-----(0)退出使用-------|
《排序问题求解》实验报告 一、算法的基本思想 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 《数据结构与算法》课程设计报告 学号: 班级序号: 姓名: 指导教师: 成绩: 中国地质大学信息工程学院地理信息系统系 2011年12 月 1.需求规格说明 【问题描述】 利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小,减少存储空间。但是,这要求在首先对一个现有文件进行编码行成新的文件,也就是压缩。在文件使用时,再对压缩文件进行解压缩,也就是译码,复原原有文件。试为完成此功能,写一个压缩/解压缩软件。 【基本要求】 一个完整的系统应具有以下功能: (1)压缩准备。读取指定被压缩文件,对文件进行分析,建立哈夫曼树,并给出分析结果(包括数据集大小,每个数据的权值,压缩前后文件的大小),在屏幕上输出。 (2)压缩。利用已建好的哈夫曼树,对文件进行编码,并将哈夫曼编码及文件编码后的数据一起写入文件中,形成压缩文件(*.Haf)。 (3)解压缩。打开已有压缩文件(*.Haf),读取其中的哈夫曼编码,构建哈夫曼树,读取其中的数据,进行译码后,写入文件,完成解压缩。 (4)程序使用命令行方式运行 压缩命令:SZip A Test.Haf 1.doc 解压缩命令:SZip X Test.Haf 2.doc或SZip X Test.Haf 用户输入的命令不正确时,给出提示。 (5)使用面向对象的思想编程,压缩/解压缩、哈夫曼构建功能分别构建类实现。 2.总体分析与设计 (1)设计思想: 1、压缩准备:1> 读文件,逐个读取字符,统计频率 2> 建立哈夫曼树 3> 获得哈弗曼编码 2、压缩过程: 1> 建立一个新文件,将储存权值和字符的对象数组取存储在文件头 《离散数学》 课程设计 学院计算机学院 学生姓名 学号 指导教师 评阅意见 提交日期 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、排序问题描述 排序是计算机程序设计的一种重要操作,他的功能是将一组任意顺序数据元素(记录),根据某一个(或几个)关键字按一定的顺序重新排列成为有序的序列。简单地说,就是将一组“无序”的记录序列调整为“有序”的记录序列的一种操作。 本次课程设计主要涉及几种常用的排序方法,分析了排序的实质,排序的应用,排序的分类,同时进行各排序方法的效率比较,包括比较次数和交换次数。我们利用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,分别表示待排序序列的起始下 电子科技大学实验报告 课程名称:数据结构与算法 学生姓名: 学号: 点名序号: 指导教师: 实验地点:基础实验大楼 实验时间: 5月20日 2014-2015-2学期 信息与软件工程学院数据结构课程设计报告
离散数学实验报告四个实验
数据结构课程设计-排序
实验报告-排序与查找