查找与排序实验报告
实验四:查找与排序 【实验目的】 1.掌握顺序查找算法的实现。 2.掌握折半查找算法的实现。 【实验内容】 1.编写顺序查找程序,对以下数据查找37所在的位置。 5,13,19,21,37,56,64,75,80,88,92 2.编写折半查找程序,对以下数据查找37所在的位置。 5,13,19,21,37,56,64,75,80,88,92 【实验步骤】 1.打开VC++。 2.建立工程:点File->New,选Project标签,在列表中选Win32 Console Application,再在右边的框里为工程起好名字,选好路径,点OK->finish。 至此工程建立完毕。 3.创建源文件或头文件:点File->New,选File标签,在列表里选C++ Source File。给文件起好名字,选好路径,点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4.写好代码 5.编译->链接->调试 #include "stdio.h" #include "malloc.h" #define OVERFLOW -1 #define OK 1 #define MAXNUM 100 typedef int Elemtype; typedef int Status; typedef struct {
Elemtype *elem; int length; }SSTable; Status InitList(SSTable &ST ) { int i,n; ST.elem = (Elemtype*) malloc (MAXNUM*sizeof (Elemtype)); if (!ST.elem) return(OVERFLOW); printf("输入元素个数和各元素的值:"); scanf("%d\n",&n); for(i=1;i<=n;i++) { scanf("%d",&ST.elem[i]); } ST.length = n; return OK; } int Seq_Search(SSTable ST,Elemtype key) { int i; ST.elem[0]=key; for(i=ST.length;ST.elem[i]!=key;--i); return i; } int BinarySearch(SSTable ST,Elemtype key) { int low,high,mid; low=1; high=ST.length;
算法排序问题实验报告
《排序问题求解》实验报告 一、算法得基本思想 1、直接插入排序算法思想 直接插入排序得基本思想就是将一个记录插入到已排好序得序列中,从而得到一个新得, 记录数增 1 得有序序列。 直接插入排序算法得伪代码称为InsertionSort,它得参数就是一个数组A[1、、n],包含了n 个待排序得数。用伪代码表示直接插入排序算法如下: InsertionSort (A) for i←2 ton do key←A[i]//key 表示待插入数 //Insert A[i] into thesortedsequence A[1、、i-1] j←i-1 while j>0 andA[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<high //从表得两端交替地向中间扫描 while low=privotkey do high←high-1 A[low]←A[high] //将比枢轴记录小得记录移到低端 while low<high &&A[low]<=pivotkey)dolow←low+1 A[high]←A[low] //将比枢轴记录大得记录移到高端
微机原理实验报告-冒泡排序
WORD格式 一、实验目的 (1)学习汇编语言循环结构语句的特点,重点掌握冒泡排序的方法。 (2)理解并掌握各种指令的功能,编写完整的汇编源程序。 (3)进一步熟悉DEBUG的调试命令,运用DEBUG进行调试汇编语言程序。 二、实验内容及要求 (1)实验内容:从键盘输入五个有符号数,用冒泡排序法将其按从小到大的顺序排序。(2)实验要求: ①编制程序,对这组数进行排序并输出原数据及排序后的数据; ②利用DEBUG调试工具,用D0命令,查看排序前后内存数据的变化; ③去掉最大值和最小值,求出其余值的平均值,输出最大值、最小值和平均值; ④用压栈PUSH和出栈POP指令,将平均值按位逐个输出; ⑤将平均值转化为二进制串,并将这组二进制串输出; ⑥所有数据输出前要用字符串的输出指令进行输出提示,所有数据结果能清晰显示。 三、程序流程图 开 始(1)主程序:MAIN 初始化 键盘输入数据 调用INPUT子程序 显示输入错误 否 输入是否正确 是 显示原始数据 调用OUTPUT子程序
WORD格式 显示冒泡排序后的数据 调用SORT子程序 调用OUTPUT子程序 显示最小值Min 显示One子程序 显示最大值Max 调用One子程序 显示其余数平均值Average 调用One子程序 显示平均值二进制串Binary 调用One子程序 结束
(2)冒泡排序子程序:SORT COUNT1----外循环次数 进入COUNT2----内循环次数 i----数组下标 初始化 COUNT1=N-1 COUNT2=COUNT1 SI=0 否 Ai≥i A+1 是 Ai与A i+1两数交换 SI=SI+2 COUNT2=COUNT2-1 否 COUNT2=0? 是 COUNT1=COUNT1-1 否 COUNT2=0? 是 返回
大数据结构实验四题目一排序实验报告材料
数据结构实验报告 实验名称:实验四——排序 学生姓名:XX 班级: 班内序号: 学号: 日期: 1.实验要求 实验目的: 通过选择实验内容中的两个题目之一,学习、实现、对比、各种排序的算法,掌握各种排序算法的优劣,以及各种算法使用的情况。 题目1: 使用简单数组实现下面各种排序算法,并进行比较。 排序算法如下: 1、插入排序; 2、希尔排序; 3、冒泡排序; 4、快速排序; 5、简单选择排序; 6、堆排序; 7、归并排序; 8、基数排序(选作); 9、其他。 具体要求如下: 1、测试数据分成三类:正序、逆序、随机数据。 2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关 键字交换记为3次移动)。 3、对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微妙。 4、对2和3的结果进行分析,验证上述各种算法的时间复杂度。 5、编写main()函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构
存储结构:数组 2.2 关键算法分析 一、关键算法: 1、插入排序 a、取排序的第二个数据与前一个比较 b、若比前一个小,则赋值给哨兵 c、从后向前比较,将其插入在比其小的元素后 d、循环排序 2、希尔排序 a、将数组分成两份 b、将第一份数组的元素与哨兵比较 c、若其大与哨兵,其值赋给哨兵 d、哨兵与第二份数组元素比较,将较大的值赋给第二份数组 e、循环进行数组拆分 3、对数据进行编码 a、取数组元素与下一个元素比较 b、若比下一个元素大,则与其交换 c、后移,重复 d、改变总元素值,并重复上述代码 4、快速排序 a、选取标准值 b、比较高低指针指向元素,若指针保持前后顺序,且后指针元素大于标准值,后 指针前移,重新比较 c、否则后面元素赋给前面元素 d、若后指针元素小于标准值,前指针后移,重新比较 e、否则前面元素赋给后面元素 5、简单选择排序 a、从数组中选择出最小元素 b、若不为当前元素,则交换 c、后移将当前元素设为下一个元素 6、堆排序 a、生成小顶堆 b、将堆的根节点移至数组的最后 c、去掉已做过根节点的元素继续生成小顶堆
《数据结构》实验报告查找
实验四——查找 一、实验目的 1.掌握顺序表的查找方法,尤其是折半查找方法; 2.掌握二叉排序树的查找算法。 二、实验内容 1.建立一个顺序表,用顺序查找的方法对其实施查找; 2.建立一个有序表,用折半查找的方法对其实施查找; 3.建立一个二叉排序树,根据给定值对其实施查找; 4.对同一组数据,试用三种方法查找某一相同数据,并尝试进行性能分析。 三、实验预习内容 实验一包括的函数有:typedef struct ,创建函数void create(seqlist & L),输出函数void print(seqlist L),顺序查找int find(seqlist L,int number),折半查找int halffind(seqlist L,int number) 主函数main(). 实验二包括的函数有:结构体typedef struct,插入函数void insert(bnode * & T,bnode * S),void insert1(bnode * & T),创建函数void create(bnode * & T),查找函数bnode * search(bnode * T,int number),主函数main(). 四、上机实验 实验一: 1.实验源程序。 #include<> #define N 80 typedef struct { int number; umber; for(i=1;[i].number!=0;) { cin>>[i].name>>[i].sex>>[i].age; ++; cout<>[++i].number; } } umber<<"\t"<<[i].name<<"\t"<<[i].sex<<"\t"<<[i].age<排序算法实验报告
实验课程:算法分析与设计 实验名称:几种排序算法的平均性能比较(验证型实验) 实验目标: (1)几种排序算法在平均情况下哪一个更快。 (2)加深对时间复杂度概念的理解。 实验任务: (1)实现几种排序算法(selectionsort, insertionsort,bottomupsort,quicksort, 堆排序)。对于快速分类,SPLIT中的划分元素采用三者A(low),A(high),A((low+high)/2)中其值居中者。(2)随机产生20组数据(比如n=5000i,1≤i≤20)。数据均属于范围(0,105)内的整数。对于同一组数据,运行以上几种排序算法,并记录各自的运行时间(以毫秒为单位)。(3)根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数,并得出结论。 实验设备及环境: PC;C/C++等编程语言。 实验主要步骤: (1)明确实验目标和具体任务; (2)理解实验所涉及的几个分类算法; (3)编写程序实现上述分类算法; (4)设计实验数据并运行程序、记录运行的结果; (5)根据实验数据及其结果得出结论; (6)实验后的心得体会。 一:问题分析(包括问题描述、建模、算法的基本思想及程序实现的技巧等):1:随机生成n个0到100000的随机数用来排序的算法如下. for(int n=1000;n<20000;n+=1000) { int a[]=new int[n]; for(int i=0;i排序算法实验报告
数据结构实验报告 八种排序算法实验报告 一、实验内容 编写关于八种排序算法的C语言程序,要求包含直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序和基数排序。 二、实验步骤 各种内部排序算法的比较: 1.八种排序算法的复杂度分析(时间与空间)。 2.八种排序算法的C语言编程实现。 3.八种排序算法的比较,包括比较次数、移动次数。 三、稳定性,时间复杂度和空间复杂度分析 比较时间复杂度函数的情况:
时间复杂度函数O(n)的增长情况 所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。 时间复杂度来说: (1)平方阶(O(n2))排序 各类简单排序:直接插入、直接选择和冒泡排序; (2)线性对数阶(O(nlog2n))排序 快速排序、堆排序和归并排序; (3)O(n1+§))排序,§是介于0和1之间的常数。 希尔排序 (4)线性阶(O(n))排序 基数排序,此外还有桶、箱排序。 说明: 当原表有序或基本有序时,直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数,时间复杂度可降至O(n); 而快速排序则相反,当原表基本有序时,将蜕化为冒泡排序,时间复杂度提高为O(n2); 原表是否有序,对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。 稳定性: 排序算法的稳定性:若待排序的序列中,存在多个具有相同关键字的记录,经过排序,这些记录的相对次序保持不变,则称该算法是稳定的;若经排序后,记录的相对次序发生了改变,则称该算法是不稳定的。 稳定性的好处:排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,可以避免多余的比较; 稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序 不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序
查找排序实验报告
《编程实训》 实验报告书 专业:计算机科学与技术 班级:151班 学号: 姓名: 指导教师: 日期:2016年6月30日
目录 一、需求分析 (3) 1.任务要求 (3) 2.软件功能分析 (3) 3.数据准备 (3) 二、概要设计 (3) 1.功能模块图 (4) 2.模块间调用关系 (4) 3.主程序模块 (5) 4.抽象数据类型描述 (5) 三、详细设计 (6) 1.存储结构定义 (6) 2.各功能模块的详细设计 (7) 四、实现和调试 (7) 1.主要的算法 (7) 2.主要问题及解决 (8) 3.测试执行及结果 (8) 五、改进 (9) 六、附录 (9) 1.查找源程序 (9) 2.排序源程序 (9)
目录 1 需求分析 1.1 任务要求 对于从键盘随机输入的一个序列的数据,存入计算机内,给出各种查找算法的实现; 以及各种排序算法的实现。 1.2 软件功能分析 任意输入n个正整数,该程序可以实现各类查找及排序的功能并将结果输出。 1.3 数据准备 任意输入了5个正整数如下: 12 23 45 56 78 2 概要设计(如果2,3合并可以省略2.4) 2.1 功能模块图(注:含功能说明) 2.2 模块间调用关系 2.3 主程序模块 2.4 抽象数据类型描述 存储结构:数据结构在计算机中的表示(也称映像)叫做物理结构。又称为存储结构。数据类型(data type)是一个“值”的集合和定义在此集合上的一组操作的总称。 3 详细设计 3.1 存储结构定义 查找: typedef int ElemType ; //顺序存储结构 typedef struct { ElemType *elem; //数据元素存储空间基址,建表时按实际长度分配,号单元留空 int length; //表的长度