查找与排序实验报告
实验四:查找与排序 【实验目的】 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.从键盘输入10个整数,产生顺序表,并输入结点值。 2.从键盘输入1个整数,在顺序表中查找该结点的位置。若找到,输出结点的位置;若找 不到,则显示“找不到”。 3.从键盘输入2个整数,一个表示欲插入的位置i,另一个表示欲插入的数值x,将x插 入在对应位置上,输出顺序表所有结点值,观察输出结果。 4.从键盘输入1个整数,表示欲删除结点的位置,输出顺序表所有结点值,观察输出结果。 二、源程序及注释: #include #include /*顺序表的定义:*/ #include #define ListSize 100 /*表空间大小可根据实际需要而定,这里假设为100*/ typedef int DataType; /*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct { DataType data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; void main() { SeqList L; int i,x; int n=10; /*欲建立的顺序表长度*/ L.length=0; void CreateList(SeqList *L,int n); void PrintList(SeqList L,int n); int LocateList(SeqList L,DataType x); void InsertList(SeqList *L,DataType x,int i); void DeleteList(SeqList *L,int i);
河南工业大学实验报告——查找和排序(排序)——张伟龙
河南工业大学实验报告 课程名称数据结构实验项目实验三查找和排序(二)——排序院系信息学院计科系专业班级计科1203 姓名张伟龙学号 201216010313 指导老师范艳峰日期 2013.6.5 批改日期成绩 一实验目的 掌握希尔排序、快速排序、堆排序的算法实现。 二实验内容及要求 实验内容:1.实现希尔排序。 2.实现快速排序。 3. 实现堆排序。 (三选一) 实验要求:1. 根据所选题目,用C语言编写程序源代码。 2. 源程序必须编译调试成功,独立完成。 三实验过程及运行结果 选择第三题: Source Code: #include #include using namespace std; void HeapAdjust(int *a,int i,int size) //调整堆 { int lchild=2*i; //i的左孩子节点序号
int rchild=2*i+1; //i的右孩子节点序号 int max=i; //临时变量 if(i<=size/2) //如果i是叶节点就不用进行调整 { if(lchild<=size&&a[lchild]>a[max]) { max=lchild; } if(rchild<=size&&a[rchild]>a[max]) { max=rchild; } if(max!=i) { swap(a[i],a[max]); HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆 } } } void BuildHeap(int *a,int size) //建立堆 { int i; for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2 { HeapAdjust(a,i,size); } }
查找、排序综合实验
淮海工学院计算机科学系实验报告书 课程名:《数据结构》 题目:查找、排序的应用实验 班级:软件102 学号:111003215 姓名:鹿迅
排序、查找的应用实验报告要求 1目的与要求: 1)查找、排序是日常数据处理过程中经常要进行的操作和运算,掌握其算法与应用对于提高学生数据处理能力和综合应用能力显得十分重要。 2)本次实验前,要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用的数据存储结构; 3)利用C或C++语言独立完成本次实验内容或题目,程序具有良好的交互性(以菜单机制实现实验程序的交互运行)和实用性; 4)本次实验属于验收平分性质实验,希望同学们认真对待,并按时完成实验任务; 5)认真书写实验报告(包括程序清单及相关实验数据与完整运行结果),并按时提交。 2 实验内容或题目 题目:对记录序列(查找表):{55,13,23,72,109,67,2,78,13}分别实现如下操作: 1)顺序查找; 2)分别使用直接插入排序、冒泡排序、快速排序对原纪录序列进行排序(暂时人工排序); 3)对排好序的纪录序列表进行折半查找; 4)利用原纪录序列建立一颗二叉排序树,并在其上实现特定关键字值结点的查找; 5)按照“除留余数法”哈希构造函数和线性探测再散列的冲突处理方法创建表长为m=11的哈希表 (暂时不做,下次实验做); 6)实现5)创建哈希表上的查找。 3 实验步骤与源程序 #include #include #define maxsize 12 #define TRUE 1 #define FALSE 0 #define NULL 0 #define listsize 9 #define keysize 9 typedef int keytype; typedef struct { int key; int flag; }Elemtype; typedef struct node
排序与查找
排序与查找 1.实验目的 掌握在数组上进行排序和查找的方法和算法 理解方法特点,并能灵活运用 加深对排序和查找方法的理解,逐步培养解决实际问题的编程能力 题1 编写程序,使用冒泡排序法对给定数组进行排序。(数组可自定,例如a[]={210,108,65,49,72,88,67,5,19,36, 90,35,1,112,215,6,23,46,51,29,77,19,0,55,27,48,18,22,30,56}) 实验流程图如下:
题2 使用折半查找法对给定的有序数组进行查找。数组可自行定义。
题一的实验结果如下 : 分析: 冒泡排序既是将数据一个一个比较,将大的不断往后放,知道所有数据都进行了比较,循环结束。 题二实验结果如下: 分析: 折半查找需要数据有序,本实验在递增的情况下进行的,所以对数据需要输入递增序列,然后将数据与最中间的进行比较,如果大,则在后一半进行查找,然后继续依次比较,直至查找到对应数据,如果没有,则显示没有。
附代码: 题1 编写程序,使用冒泡排序法对给定数组进行排序。(数组可自定,例如a[]={210,108,65,49,72,88,67,5,19,36, 90,35,1,112,215,6,23,46,51,29,77,19,0,55,27,48,18,22,30,56}) 题2 使用折半查找法对给定的有序数组进行查找。数组可自行定义。 #include void main() { int i, n=30, j, m; int a[]={210,108,65,49,72,88,67,5,19,36, 90,35,1,112,215,6,23,46,51,29, 77,19,0,55,27,48,18,22,30,56}; printf("\nThese integers are as below:\n\n"); for (i=0; ia[j+1]) { m=a[j];
《数据结构》实验报告查找
实验四——查找 一、实验目的 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<查找排序实验报告
《编程实训》 实验报告书 专业:计算机科学与技术 班级: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; //表的长度
实验五查找及排序讲解
实验五 查找及排序 实验课程名: 数据结构与算法 一、实验目的及要求 1、掌握查找的不同方法,并能用高级语言实现查找算法。 2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法。 3、掌握常用的排序方法,并能用高级语言实现排序算法。 4、深刻理解排序的定义和各种排序方法的特点,并能加以灵活运用。 5、了解各种方法的排序过程及依据的原则,并掌握各种排序方法的时间复杂度的分析方法。 二、实验内容 任务一:顺序表的顺序查找。 有序表的折半查找。 完成下列程序,该程序实现高考成绩表(如下表所示)的顺序查找,在输出结果中显示查找成功与查找不成功信息。 解答: (1)源代码:#include // EOF(=^Z 或F6),NULL #include // atoi() #include // eof() #include // floor(),ceil(),abs() #include // exit() #include // cout,cin // 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 // #define OVERFLOW -2 因为在math.h 中已定义OVERFLOW 的值为3,故去掉 此行 typedef int Status; // Status 是函数的类型,其值是函数结果状态代码, 如OK 等 typedef int Boolean; // Boolean 是布尔类型,其值是TRUE 或FALSE #define MAX_LENGTH 100 #include 准考证号 姓名 各科成绩 总分 政治 语文 外语 数学 物理 化学 生物 179328 何芳芳 85 89 98 100 93 80 47 592 179325 陈红 85 86 88 100 92 90 45 586 179326 陆华 78 75 90 80 95 88 37 543 179327 张平 82 80 78 98 84 96 40 558 179324 赵小怡 76 85 94 57 77 69 44 502
各种排序实验报告
【一】需求分析 课程题目是排序算法的实现,课程设计一共要设计八种排序算法。这八种算法共包括:堆排序,归并排序,希尔排序,冒泡排序,快速排序,基数排序,折半插入排序,直接插入排序。 为了运行时的方便,将八种排序方法进行编号,其中1为堆排序,2为归并排序,3为希尔排序,4为冒泡排序,5为快速排序,6为基数排序,7为折半插入排序8为直接插入排序。 【二】概要设计 1.堆排序 ⑴算法思想:堆排序只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。 ⑵程序实现及核心代码的注释: for(j=2*i+1; j<=m; j=j*2+1) { if(j=su[j]) break; su[i]=su[j]; i=j; } su[i]=temp; } void dpx() //堆排序 { int i,temp; cout<<"排序之前的数组为:"<=0; i--) { head(i,N); } for(i=N-1; i>0; i--) {
temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为:"<几种常用的查找和排序算法
#include #include #define N 11 /*用监视哨查找*/ int search(int array[],int n,int k) { int i; i=n-1; array[0]=k; while(array[i]!=k) i--; return(i); } /*折半查找法*/ int halfsearch(int array[],int n,int k) { int i,j,mid; i=1;j=n; while(i<=j) { mid=(i+j)/2; if(k==array[mid]) return(mid); else if(karray[j]) { a=array[i]; array[i]=array[j]; array[j]=a; } } /*直接插入排序*/ void insertsort(int array[]) { int i,j;
for(i=2;i2018年浙江省选考信息技术查找与排序强化习题一答案
第二轮排序和查找算法综合1 行政班:教学班:姓名:学号: 根据课本上的排序算法和查找算法回答1-6题: 1.【加试题】有一个数组,采用冒泡排序,第一遍排序后的结果为:4,10,5,32,6,7,9,17,24那么该数组的原始顺序不可能 ...的是() A.10,5,32,6,7,9,17,24,4 B.10,5,32,6,7,9,4,17,24 C.10,5,32,4,6,7,9,17,24 D.4,10,5,32,17,9,24,6,7 2.【加试题】对下列数据序列进行冒泡升序排序,排序效率最低的序列() A.31,29,24,20,15,10 B.10,15,20,24,29,31 C.29,10,31,15,20,24 D.24,29,31,20,15,10 3.【加试题2】数组变量d(1)到d(8)的值依次为87、76、69、66、56、45、37、23,用“对分查找”找到“69”的过程中,依次被访问到的数据是() A.69 B.66、69 C.66、76、69 D.56、66、76、69 4.【加试题2】用对分查找法和顺序查找法在数字序列“1,2,3,5,8,13,21,34,55”中查找数字13,两种方法都能访问到的数字是() A.3 B.5 C.8 D.34 5.【加试题2】在有序单词序列“bike,cake,data,easy,feel,great,hive,mark,sweet”中,用对分查找算法找到“easy”过程中,依次被访问到的数据为() A.feel, data, easy B.great, data, easy C.bike, cake, dada,easy D.feel,cake,data,easy 6.【加试题2】下列有关查找的说法,正确的是() A.进行对分查找时,被查找的数据必须已按升序排列 B.进行对分查找时,如果查找的数据不存在,则无需输出结果 C.在新华字典中查找某个汉字,最适合使用顺序查找 D.对规模为n的数据进行顺序查找,平均查找次数是21 n 7. 【加试题】实现某排序算法的部分VB程序如下:数组元素a(1)到a(5)的数据依次为“38,70,53,57,30”。经过下列程序“加工”后数组元素a(1)到a(5)的数据应该是() For i = 1 To 1 For j = 5 To i + 1 Step -1 If a(j) > a(j - 1) Then t = a(j) a(j) = a(j - 1) a(j - 1) = t End If Next j Next i 命题:杜宗飞 A.70,57,38,53,30 B.30, 38,70,53,57 C.70,38,57,53,30 D.30, 38,57,53,70 8.【加试题】有如下程序段:
河南工业大学实验报告_实验三 查找和排序(一)——查找
xxx大学实验报告 课程名称数据结构实验项目实验三查找和排序(一)——查找 院系信息学院计类系专业班级计类1501 姓名学号 指导老师日期 批改日期成绩 一实验目的 1.掌握哈希函数——除留余数法的应用; 2. 掌握哈希表的建立; 3. 掌握冲突的解决方法; 4. 掌握哈希查找算法的实现。 二实验内容及要求 实验内容:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79),哈希 函数定义为:H(key)=key MOD 13, 哈希表长为m=16。实现该哈希表的散列,并 计算平均查找长度(设每个记录的查找概率相等)。 实验要求:1. 哈希表定义为定长的数组结构;2. 使用线性探测再散列或链 地址法解决冲突;3. 散列完成后在屏幕上输出数组内容或链表;4. 输出等概率 查找下的平均查找长度;5. 完成散列后,输入关键字完成查找操作,要分别测 试查找成功与不成功两种情况。 注意:不同解决冲突的方法会使得平均查找长度不同,可尝试使用不同解决 冲突的办法,比较平均查找长度。(根据完成情况自选,但至少能使用一种方法 解决冲突) 三实验过程及运行结果 #include #include #include #define hashsize 16
#define q 13 int sign=2; typedef struct Hash { int date; //值域 int sign; //标记 }HashNode; void compare(HashNode H[],int p,int i,int key[]) //线性冲突处理{ p++; if(H[p].sign!=0) { sign++; compare(H,p,i,key); } else { H[p].date=key[i]; H[p].sign=sign; sign=2; } } void Hashlist(HashNode H[],int key[]) { int p; for(int i=0;i<12;i++) { p=key[i]%q; if(H[p].sign==0) { H[p].date=key[i]; H[p].sign=1; } else compare(H,p,i,key); } } int judge(HashNode H[],int num,int n) //查找冲突处理 {
八种排序和三大查找
每天都在叫嚣自己会什么技术,什么框架,可否意识到你每天都在被这些新名词、新技术所迷惑,.NET、XML等等技术固然诱人,可是如果自己的基础不扎实,就像是在云里雾里行走一样,只能看到眼前,不能看到更远的地方。这些新鲜的技术掩盖了许多底层的原理,要想真正的学习技术还是走下云端,扎扎实实的把基础知识学好,有了这些基础,要掌握那些新技术也就很容易了。 要编写出优秀的代码同样要扎实的基础,如果排序和查找算法学的不好,怎么对程序的性能进行优化?废话不多说,本文要介绍的这些排序算法就是基础中的基础,程序员必知! 1、直接插入排序
(1)基本思想:在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排 好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数 也是排好顺序的。如此反复循环,直到全部排好顺序。 (2)实例 2、希尔排序(也称最小增量排序) (1)基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。当增量减到1时,进行直接插入排序后,排序完成。 (2)实例:
3、简单选择排序 (1)基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换; 然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。 (2)实例: 4、堆排序 (1)基本思想:堆排序是一种树形选择排序,是对直接选择排序的有效改进。堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当满足 (hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项(大顶堆)。完全二叉树可以很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储序,使之成为一个堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。 (2)实例: 初始序列:46,79,56,38,40,84 建堆: