实验七查找和排序算法的实现
?实验目的及要求
(1)学生在实验中体会各种查找和内部排序算法的基本思想、适用场合,理解开发高效算法的可能性和寻找、构造高效算法的方法。
(2)掌握运用查找和排序解决一些实际应用问题。
二.实验内容:
(1)编程实现一种查找算法(如折半查找、二叉排序树的查找、哈希查找等)算相应的ASL。
(2)编程实现一种内部排序算法(如插入排序、快速排序等)。
三.实验主要流程、基本操作或核心代码、算法片段(该部分如不够填写,请另加附页)
(1)编程实现一种查找算法(如折半查找、二叉排序树的查找、哈希查找等)算相应的ASL。
程序代码:
折半查找:
头文件:
#defi ne EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)v(b))
#defi ne maxle ngth 20 typedef int ElemType;
typedef struct{
ElemType key;
ElemType other;
}card;〃每条记录包含的数据项
typedef struct{
card r[maxle ngth];
int len gth;
}SSTable;〃一张表中包含的记录容量
void Create(SSTable & L); int Search(SSTable L,i nt elem);
功能函数:
#i nclude"1.h" #i nclude"stdio.h",并计,并计
void Create(SSTable &L)
{
printf(" 新的线性表已经创建,请确定元素个数(不超过20) \n");
scanf("%d",&L.length);
printf(" 请按递增序列输入具体的相应个数的整数元素(空格隔开) \n"); for(int i=0;i { scanf("%d",&L.r[i].key); } } int Search(SSTable L,int elem) { if(L.r[L.length-1].key { printf(" 表中没有该元素(不在范围内) \n"); return 0; } int low=0,high=L.length-1; int mid; while(low<=high) { mid=(low+high)/2; if(EQ(L.r[mid].key,elem)){printf(" else if(LT(elem,L.r[mid].key)) { high=mid-1; } else { low=mid+1; } } printf(" 表中没有该元素(不在范围内) return 0; } 主函数: #include"stdio.h" #include"1.h" int main() {该元素在第%d 位\n",mid+1); return 0;} \n"); SSTable L; Create(L); prin tf("\n"); printf("此时的线性表元素:\n"); for(i nt a=0;a { prin tf("%d "丄.r[a].key); } prin tf("\n"); prin tf("\n"); int elem; do { printf("请输入要查找的元素(输入000表示结束程序)\n"); sea nf("%d", &elem); if(elem!=000) { Seareh(L,elem); } }while(elem!=000); return 0; } 运行结果: (2)编程实现一种内部排序算法(如插入排序、快速排序等)。程序代码部分: 直接插入排序 头文件: #defi ne maxle ngth 20/最大数据容量 #defi ne OK 1 typedef int Other; typedef int KeyType; typedef int Status; typedef struct{ KeyType key; Other data; }Red; typedef struct{ Red r[maxle ngth+1];〃加了个哨兵的位置int len gth;//当前数据个数 }SqList; Status Init(SqList &L); Status Insertsort(SqList &L); 功能函数: #include"stdio.h" #include"1.h" Status Init(SqList &L) { printf(" 新的线性表以创建,请确定元素个数(不超过20)\n"); scanf("%d",&L.length); printf(" 请输入具体的相应个数的整数元素(空格隔开) \n"); for(int i=1/* 将哨兵的位置【0】空出来*/;i { scanf("%d",&L.r[i].key); } return OK; } Status Insertsort(SqList &L) { for(int i=2;i { L.r[0]=L.r[i];// 交换的应该是该位置记录的完整数据项,而不仅仅是数据项中的一个key for(i nt j=i;j>0&&L.r[0].key 排序的,所以比较的是key,而不是一条记录的所有数据项*/;j--) { L.r[j]=L.r[j-1]; } L.r[j]=L.r[0]; return OK; } 主函数:#include"stdio.h" #include"1.h" int main() { SqList L; Init(L); printf("\n"); printf(" 排序前的线性表元素:\n"); for(int a=1;a { } printf("%d ",L.r[a].key); } printf("\n"); printf("\n"); Insertsort(L); printf(" 排序后的线性表元素:\n"); for(int b=1;b { printf("%d ",L.r[b].key); } printf("\n"); return 0; } 快速排序 头文件: #define maxlength 20//最大数据容量#define OK 1 typedef int Other; typedef int KeyType; typedef struct{ KeyType key; Other data; }Red; typedef struct{ Red r[maxle ngth+1];〃加了个哨兵的位置 int len gth;//当前数据个数 }SqList; void Init(SqList &L); Status Partition(SqList &L,int low,int high); void QSort(SqList &L,int low,int high); 功能函数: #include"stdio.h" #include"1.h" void Init(SqList &L) { printf(" 新的线性表以创建,请确定元素个数(不超过20)\n"); scanf("%d",&L.length); printf(" 请输入具体的相应个数的整数元素(空格隔开) \n"); typedef int Status; for(int i=1/* 将存放枢轴中关键字所在记录完整信息的位置【0】空出来 */;i { scanf("%d",&L.r[i].key); } } Status Partition(SqList &L,int low,int high) { int pivotkey; pivotkey=L.r[low].key;// 用第一条记录的关键字作枢轴 L.r[0]=L.r[low];// 存放作为枢轴的关键字所在记录的完整信息 while(low { while(low while(low L.r[high]=L.r[low]; } L.r[low]=L.r[0]; return low; } void QSort(SqList &L,int low,int high) { int pivotloc; if(low { pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); } } 主函数: #include"stdio.h" #include"1.h" int main() { SqList L; Init(L); printf("\n"); printf(" 排序前的线性表元素:\n"); for(int a=1;a { printf("%d ",L.r[a].key); } printf("\n"); printf("\n"); printf(" 请输入无序子列的开始和结束位置(有序子列不用管) int \n"); low,high; scanf("%d %d",&low,&high); QSort(L,low,high); printf(" 排序后的线性表元素:\n"); for(int b=1;b { printf("%d ",L.r[b].key); } printf("\n"); return 0; 运行结果: 四.实验结果的分析与评价(该部分如不够填写,请另加附页) 1?快速排序利用了递归的思想; 2?折半查找使用前提为:数列有序 各种排序算法的总结和比较 1 快速排序(QuickSort) 快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。 (1)如果不多于1个数据,直接返回。 (2)一般选择序列最左边的值作为支点数据。(3)将序列分成2部分,一部分都大于支点数据,另外一部分都小于支点数据。 (4)对两边利用递归排序数列。 快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法,但是就通常情况而言,没有比它更快的了。快速排序是递归的,对于内存非常有限的机器来说,它不是一个好的选择。 2 归并排序(MergeSort) 归并排序先分解要排序的序列,从1分成2,2分成4,依次分解,当分解到只有1个一组的时候,就可以排序这些分组,然后依次合并回原来的序列中,这样就可以排序所有数据。合并排序比堆排序稍微快一点,但是需要比堆排序多一倍的内存空间,因为它需要一个额外的数组。 3 堆排序(HeapSort) 堆排序适合于数据量非常大的场合(百万数据)。 堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录,因为快速排序,归并排序都使用递归来设计算法,在数据量非常大的时候,可能会发生堆栈溢出错误。 堆排序会将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆,交换数据,依次下去,就可以排序所有的数据。 Shell排序通过将数据分成不同的组,先对每一组进行排序,然后再对所有的元素进行一次插入排序,以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。 Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相对比较简单,它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。 5 插入排序(InsertSort) 插入排序通过把序列中的值插入一个已经排序好的序列中,直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序,或者重复排序超过200数据项的序列。 陕西科技大学实验报告 班级学号姓名实验组别 实验日期室温报告日期成绩 报告内容:(目的和要求、原理、步骤、数据、计算、小结等) 实验名称:查找与排序算法的实现和应用 实验目的: 1. 掌握顺序表中查找的实现及监视哨的作用。 2. 掌握折半查找所需的条件、折半查找的过程和实现方法。 3. 掌握二叉排序树的创建过程,掌握二叉排序树查找过程的实现。 4. 掌握哈希表的基本概念,熟悉哈希函数的选择方法,掌握使用线性探测法和链地址法进行冲突解决的方 法。 5. 掌握直接插入排序、希尔排序、快速排序算法的实现。 实验环境(硬/软件要求):Windows 2000,Visual C++ 6.0 实验内容: 通过具体算法程序,进一步加深对各种查找算法的掌握,以及对实际应用中问题解决方 法的掌握。各查找算法的输入序列为:26 5 37 1 61 11 59 15 48 19输出 要求:查找关键字37,给出查找结果。对于给定的某无序序列,分别用直接插入排序、希尔排序、快速排序等方法进行排序,并输出每种排序下的各趟排序结果。 各排序算法输入的无序序列为:26 5 37 1 61 11 59 15 48 19。 实验要求: 一、查找法 1. 顺序查找 首先从键盘输入一个数据序列生成一个顺序表,然后从键盘上任意输入一个值,在顺序 表中进行查找。 2. 折半查找 任意输入一组数据作为个数据元素的键值,首先将此序列进行排序,然后再改有序表上 使用折半查找算法进对给定值key 的查找。 3. 二叉树查找 任意输入一组数据作为二叉排序树中节点的键值,首先创建一颗二叉排序树,然后再次二叉排序树上实现对一 定k的查找过程。 4. 哈希表查找 任意输入一组数值作为个元素的键值,哈希函数为Hash (key )=key%11, 用线性探测再散列法解决冲突问题。 二、排序算法 编程实现直接插入排序、希尔排序、快速排序各算法函数;并编写主函数对各排序函数进行测试。 实验原理: 1. 顺序查找: 在一个已知无(或有序)序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较,直到找出与给定关键字相同的数为止,它的缺点是效率低下。 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以 这个星期做数据结构课设,涉及到两个基于链表的排序算法,分别是基于链表的选择排序算法和归并排序算法。写出来跟大家一起分享一下,希望对数据结构初学朋友有所帮助,高手就直接忽视它吧。话不多说,下面就看代码吧。 [c-sharp]view plaincopy 1.node *sorted(node *sub_root) 2.{ 3.if (sub_root->next) 4. { 5. node * second_half = NULL; 6. node * first_half = sub_root; 7. node * temp = sub_root->next->next; 8.while (temp) 9. { 10. first_half = first_half->next; 11. temp = temp->next; 12.if(temp) 13. temp = temp->next; 14. } 15. second_half = first_half->next; 16. first_half->next = NULL; 17. node * lChild = sorted(sub_root); 18. node * rChild = sorted(second_half); 19.if (lChild->data < rChild->data) 20. { 21. sub_root = temp = lChild; 22. lChild = lChild->next; 23. } 24.else 25. { 26. sub_root = temp = rChild; 27. rChild = rChild->next; 28. } 29.while (lChild&&rChild) 30. { 31.if (lChild->data < rChild->data ) 32. { 33. temp->next = lChild; 34. temp = temp->next; 35. lChild = lChild->next; 36. } 37.else 38. { 实验六、七:查找、排序算法的应用 班级 10511 学号 20103051114 姓名高卫娜 一、实验目的 1 掌握查找的不同方法,并能用高级语言实现查找算法。 2 熟练掌握顺序表和有序表的顺序查找和二分查找方法。 3 掌握排序的不同方法,并能用高级语言实现排序算法。 4 熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现。 二、实验内容 1 创建给定的顺序表。表中共包含八条学生信息,信息如下: 学号姓名班级C++ 数据结构 1 王立03511 85 76 2 张秋03511 78 88 3 刘丽03511 90 79 4 王通03511 7 5 86 5 赵阳03511 60 71 6 李艳03511 58 68 7 钱娜03511 95 89 8 孙胜03511 45 60 2 使用顺序查找方法,从查找表中查找姓名为赵阳和王夏的学生。如果查找成功,则显示该生的相关信息;如果查找不成功,则给出相应的提示信息。 3 使用二分查找方法,从查找表中查找学号为7和12的学生。如果查找成功,则显示该生的相关信息;如果查找不成功,则给出相应的提示信息。(注意:创建静态查找表时必须按学号的从小到大排列!) 4 使用直接插入排序方法,对学生信息中的姓名进行排序。输出排序前和排序后的学生信息表,验证排序结果。 5 使用直接选择排序方法,对学生信息中的C成绩进行排序。输出排序前和排序后的学生信息表,验证排序结果。 6 使用冒泡排序方法,对学生信息中的数据结构成绩进行排序。输出排序前和排序后的学生信息表,验证排序结果。 7 编写一个主函数,将上面函数连在一起,构成一个完整程序。 8 将实验源程序调试并运行。 三、实验结果 源程序代码为: #include 实验报告 课程名称数据结构实验名称查找与排序的实现 系别专业班级指导教师11 学号姓名实验日期实验成绩 一、实验目的 (1)掌握交换排序算法(冒泡排序)的基本思想; (2)掌握交换排序算法(冒泡排序)的实现方法; (3)掌握折半查找算法的基本思想; (4)掌握折半查找算法的实现方法; 二、实验内容 1.对同一组数据分别进行冒泡排序,输出排序结果。要求: 1)设计三种输入数据序列:正序、反序、无序 2)修改程序: a)将序列采用手工输入的方式输入 b)增加记录比较次数、移动次数的变量并输出其值,分析三种序列状态的算法时间复杂 性 2.对给定的有序查找集合,通过折半查找与给定值k相等的元素。 3.在冒泡算法中若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置, 算法如何改进? 三、设计与编码 1.本实验用到的理论知识 2.算法设计 3.编码 package sort_search; import java.util.Scanner; public class Sort_Search { //冒泡排序算法 public void BubbleSort(int r[]){ int temp; int count=0,move=0; boolean flag=true; for(int i=1;i 实验七查找 一、实验目的 1. 掌握查找的不同方法,并能用高级语言实现查找算法; 2. 熟练掌握二叉排序树的构造和查找方法。 3. 熟练掌握静态查找表及哈希表查找方法。 二、实验内容 设计一个读入一串整数,然后构造二叉排序树,进行查找。 三、实验步骤 1. 从空的二叉树开始,每输入一个结点数据,就建立一个新结点插入到当前已生成的二叉排序树中。 2. 在二叉排序树中查找某一结点。 3.用其它查找算法进行排序(课后自己做)。 四、实现提示 1. 定义结构 typedef struct node { int key; int other; struct node *lchild, *rchild; } bstnode; void inorder ( t ) { if (t!=Null) { inorder(t→lchild); printf(“%4d”, t→key); inorder(t→rchild); } } bstnode *insertbst(t, s) bstnode *s, *t; { bstnode *f, *p; p=t; while(p!=Null) { f=p; if (s→key= =p→key) return t; if (s→key 数据结构各种排序算法总结 2009-08-19 11:09 计算机排序与人进行排序的不同:计算机程序不能象人一样通览所有的数据,只能根据计算机的"比较"原理,在同一时间内对两个队员进行比较,这是算法的一种"短视"。 1. 冒泡排序 BubbleSort 最简单的一个 public void bubbleSort() { int out, in; for(out=nElems-1; out>0; out--) // outer loop (backward) for(in=0; in swap(out, min); // swap them } // end for(out) } // end selectionSort() 效率:O(N2) 3. 插入排序 insertSort 在插入排序中,一组数据在某个时刻实局部有序的,为在冒泡和选择排序中实完全有序的。 public void insertionSort() { int in, out; for(out=1; out 实验五 查找算法实现 1、实验目的 熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法,比较它们的平均查找长度。 2、问题描述 查找表是数据处理的重要操作,试建立有100个结点的二叉排序树进行查找,然后用原数据建立AVL树,并比较两者的平均查找长度。 3、基本要求 (1)以链表作为存储结构,实现二叉排序树的建立、查找和删除。 (2)根据给定的数据建立平衡二叉树。 4、测试数据 随即生成 5、源程序 #include<> #include<> #include<> #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)>(b)) typedef int Keytype; typedef struct { Keytype key; //关键字域 }ElemType; typedef struct BSTnode { ElemType data; int bf; struct BSTnode *lchild,*rchild; }BSTnode,*BSTree; void InitBSTree(BSTree &T) {T=NULL; } void R_Rotate(BSTree &p) {BSTnode *lc; lc=p->lchild; p->lchild=lc->rchild; lc->rchild=p; p=lc; } void L_Rotate(BSTree &p) {BSTnode *rc; rc=p->rchild; p->rchild=rc->lchild; 数据结构-各类排序算法总结 原文转自: https://www.wendangku.net/doc/5e4260538.html,/zjf280441589/article/details/38387103各类排序算法总结 一. 排序的基本概念 排序(Sorting)是计算机程序设计中的一种重要操作,其功能是对一个数据元素集合或序列重新排列成一个按数据元素 某个项值有序的序列。 有n 个记录的序列{R1,R2,…,Rn},其相应关键字的序列是{K1,K2,…,Kn},相应的下标序列为1,2,…,n。通过排序,要求找出当前下标序列1,2,…,n 的一种排列p1,p2,…,pn,使得相应关键字满足如下的非递减(或非递增)关系,即:Kp1≤Kp2≤…≤Kpn,这样就得到一个按关键字有序的记录序列{Rp1,Rp2,…,Rpn}。 作为排序依据的数据项称为“排序码”,也即数据元素的关键码。若关键码是主关键码,则对于任意待排序序列,经排序后得到的结果是唯一的;若关键码是次关键码,排序结果可 能不唯一。实现排序的基本操作有两个: (1)“比较”序列中两个关键字的大小; (2)“移动”记录。 若对任意的数据元素序列,使用某个排序方法,对它按关键码进行排序:若相同关键码元素间的位置关系,排序前与排序后保持一致,称此排序方法是稳定的;而不能保持一致的排序方法则称为不稳定的。 二.插入类排序 1.直接插入排序直接插入排序是最简单的插入类排序。仅有一个记录的表总是有序的,因此,对n 个记录的表,可从第二个记录开始直到第n 个记录,逐个向有序表中进行插入操作,从而得到n个记录按关键码有序的表。它是利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。 电子科技大学实验报告 课程名称:数据结构与算法 学生姓名: 学号: 点名序号: 指导教师: 实验地点:基础实验大楼 实验时间: 5月20日 2014-2015-2学期 信息与软件工程学院各种排序算法的总结和比较
实验8查找与排序算法的实现和应用
链表排序算法总结
实验6 查找和排序 (2)(1)
数据结构实验五-查找与排序的实现
数据结构实验七 查找
数据结构 各种排序算法
数据结构实验——查找算法的实现
数据结构-各类排序算法总结
实验报告-排序与查找