陕西科技大学实验报告
班级学号姓名实验组别
实验日期室温报告日期成绩
报告内容:(目的和要求、原理、步骤、数据、计算、小结等)
实验名称:查找与排序算法的实现和应用
实验目的:
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.顺序查找:
在一个已知无(或有序)序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较,直到找出与给定关键字相同的数为止,它的缺点是效率低下。
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
2.哈希查找:
哈希查找的操作步骤:⑴用给定的哈希函数构造哈希表;⑵根据选择的冲突处理方法解
决地址冲突;⑶在哈希表的基础上执行哈希查找。
哈希查找的本质是先将数据映射成它的哈希值。哈希查找的核心是构造一个哈希函数,它将原来直观、整洁的数据映射为看上去似乎是随机的一些整数。哈希查找的产生有这样一种背景——有些数据本身是无法排序的(如图像),有些数据是很难比较的(如图像)。如果数据本身是无法排序的,就不能对它们进行比较查找。如果数据是很难比较的,即使采用折半查找,要比较的次数也是非常多的。因此,哈希查找并不查找数据本身,而是先将数据映射为一个整数(它的哈希值),并将哈希值相同的数据存放在同一个位置一即以哈希值为索引构造一个数组。
在哈希查找的过程中,只需先将要查找的数据映射为它的哈希值,然后查找具有这个哈希值的数据,这就大大减少了查找次数。如果构造哈希函数的参数经过精心设计,内存空间也足以存放哈希表,查找一个数据元素所需的比较次数基本上就接近于一次。
3.排序算法:
排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个关键字有序的序列。
流程图:
是
否
实验代码:
一、查找法
1、顺序查找
#include
#define MAX 100
用户输入
中序遍历 排序创建二叉树
输入查找条件 输出结果 是否继续
结束 开始
typedef int keytype;
typedef struct
{ keytype key;
}elemtype;
typedef struct
{ elemtype elem[MAX+1];
int length;
}SStable;
void create_seq(SStable*list);
int seq_search(SStable*list,keytype k);
void main()
{ SStable *list,table;
keytype key;
int i;
list=&table;
printf("请输入顺序表的长度:");
scanf("%d",&list->length);
create_seq(list);
printf("创建的顺序表内容:\n");
for(i=0;i
printf("list.elem[%d].key=%d\n",i+1,list->elem[i].key);
printf("输入查找关键字:");
scanf("%d",&key);
seq_search(list,key);
}
void create_seq(SStable *list)
{ int i;
printf("请输入顺序表的内容:\n");
for(i=0;i
{ printf("list.elem[%d].key=",i+1);
scanf("%d",&list->elem[i].key);
}
}
int seq_search(SStable*list,keytype k)
{ int i=0,flag=0;
while(i
{ if(list->elem[i].key==k)
{ printf("查找成功.\n");
flag=1;
printf("list.elem[%d].key=%d\n",i+1,k);
}
i++;
}
if(flag==0)
printf("没有找到数据%d!\n",k);
return(flag);
}
2、折半查找
#include
#define MAX 100
typedef struct
{ int elem[MAX+1];
int length;
}Stable;
void creat_seq(Stable*list);
int sort_seq(Stable*list);
int bin_search(Stable*list,int k,int low,int higt);
void main()
{ Stable *list,table;
int i,key;
list=&table;
printf("请输入线性表的长度:");
scanf("%d",&list->length);
creat_seq(list);
sort_seq(list);
printf("排列后的数据\n");
for(i=1;i<=list->length;i++)
printf("list.elem[%d].key=%d\n",i,list->elem[i]);
printf("\n请输入查找的值:");
scanf("%d",&key);
bin_search(list,key,1,list->length);
}
void creat_seq(Stable*list)
{ int i;
printf("请输入顺序表的内容:\n");
for(i=1;i<=list->length;i++)
{printf("list.elem[%d].key=",i);
scanf("%d",&list->elem[i]);
}
}
int sort_seq(Stable*list)
{ int i,j,flag;
for(i=1;i
{flag=0;
for(j=1;j
if (list->elem[j]>list->elem[j+1])
{list->elem[0]=list->elem[j+1];
list->elem[j+1]=list->elem[j];
list->elem[j]=list->elem[0];
flag=1;
}
if(flag==0)return 1;
}
}
int bin_search(Stable*list,int k,int low,int high)
{ int mid;
if(low>high)
{ printf("没有找到要查找的值\n");
return(0);
}
mid=(low+high)/2;
if(list->elem[mid]==k)
{ printf("查找成功\n");
printf("list[%d]=%d\n",mid,k);
return(mid);
}
else
if(list->elem[mid] return(bin_search(list,k,mid+1,high)); else return(bin_search(list,k,low,mid-1)); } 3、二叉树查找 #include #include typedef struct bitnode { int key; struct bitnode *lchild; struct bitnode *rchild; }bnode; void ins_bitree(bnode *p,int k) { bnode *q; if(p->key >k&&p->lchild) ins_bitree(p->lchild,k); else if(p->key<=k&&p->rchild) ins_bitree(p->rchild,k); else { q=(bnode *)malloc(sizeof(bnode)); q->key=k; q->lchild=NULL; q->rchild=NULL; if(p->key>k) p->lchild=q; else p->rchild=q; } } void bit_search(bnode *p,int k) { if(p->key>k&&p->lchild) bit_search(p->lchild,k); else if(p->key bit_search(p->rchild,k); else if(p->key ==k) printf("查找成功!\n"); else printf("%d不存在!\n"); } void inorder(bnode *p) { if(p) { inorder(p->lchild); printf("%4d",p->key); inorder(p->rchild); } } void main () { int k; bnode *p; p=NULL; printf("请输入二叉树结点的值,输入0结束:\n"); scanf("%d",&k); p=(bnode *)malloc(sizeof(bnode)); p->key=k; p->lchild=NULL; p->rchild=NULL; scanf("%d",&k); while (k>0) { ins_bitree(p,k); scanf("%d",&k); } printf("\n"); printf("二叉树排序的结果:"); inorder(p); printf("\n请输入查找的值:\n"); scanf("%d",&k); bit_search(p,k); } 4、哈希表查找 #include #define MAX 11 void ins_hash(int hash[],int key) { int k,k1,k2; k=key%MAX; if(hash[k]==0) { hash[k]=key; return ; } else {k1=k+1; while(k1 k1++; if(k1 { hash[k1]=key; return ; } k2=0; while(k2 k2++; if(k2 { hash[k2]=key; return ; } } } void out_hash(int hash[]) { int i; for(i=0;i if(hash[i]) printf("hash[%d]=%d\n",i,hash[i]); } void hash_search(int hash[],int key) { int k,k1,k2,flag=0; k=key%MAX; if(hash[k]==key) { printf("hash[%d]=%d",k,key); flag=1; } else { k1=k+1; while(k1 k1++; if(k1 {printf("hash[%d]=%d",k1,key); flag=1;} k2=0; if(!flag) {while(k2 k2++; if(k2 {printf("hash[%d]=%d",k2,key); flag=1;} } if(flag) {printf("查找成功!\n"); return; }else {printf("查找失败!\n"); return;} } } void main() {int i,key,k,sum=0; int hash[MAX]; for(i=0;i hash[i]=0; printf("请输入数据,以0结束:\n"); scanf("%d",&key); sum++; while(key&&sum {ins_hash(hash,key); scanf("%d",&key); sum++; } printf("\n"); out_hash(hash); printf("\n"); printf("请输入查找的值:"); scanf("%d",&k); hash_search(hash,k); printf("\n"); } 二、排序算法 #include #include #define size 11 typedef char datatype; typedef struct {int key; datatype others; }rectype; void INSERTSORT(rectype R[]) { int i,j; for (i=2;i<=size;i++) { R[0]=R[i]; j=i-1; while (R[0].key { R[j+1]=R[j];j--;} R[j+1]=R[0];} } void SHELLSORT(rectype R[],int n) {int i,j,h; rectype temp; h=n/2; while(h>0) {for(j=h;j<=n-1;j++) {temp=R[j]; i=j-h; while ((i>=0)&&temp.key {R[i+h]=R[i]; i=i-h;} R[i+h]=temp;} h=h/2;} } int PARTITION(rectype R[],int l,int h) {int i,j; rectype temp; i=1;j=h;temp=R[i]; do {while ((R[j].key>=temp.key)&&(i j--; if(i while ((R[i].key<=temp.key)&&(i i++; if(i while(i!=j); R[i]=temp; return i; } void QUICKSORT(rectype R[],int s1,int t1) { int i; if(s1 { i=PARTITION(R,s1,t1); QUICKSORT(R,s1,i-1); QUICKSORT(R,i+1,t1); } } void main() { rectype R[size]; int i; printf("请输入使用插入算法排序的10个数据\n"); for(i=1;i printf("\n插入排序之前\n"); for(i=1;i INSERTSORT(R); printf("\n插入排序之后\n"); for(i=1;i printf("\n请输入使用希尔顿算法排序的10个数据\n"); for(i=0;i printf("\n希尔排序之前\n"); for(i=0;i SHELLSORT(R,10); printf("\n希尔排序之后\n"); for(i=0;i printf("请输入使用快速算法排序的10个数据\n"); for(i=1;i printf("\n快速排序之前\n"); for(i=1;i QUICKSORT(R,1,10); printf("\n快速排序之后\n"); for(i=1;i } 实验结果 顺序查找: 折半查找: 二叉树查找: 哈希表查找: 排序: 实验小结: 此次操作证明可以用编程实现查找与排序,实验结果正确。通过本次实验,我对查找排序与二分查找、哈希查找、二叉树查找等有了更加深刻的了解。练习了指针,查找等操作,熟练掌握树的操作。对各种算法有了更加深刻的理解。通过这次写实验报告,我深切的理解了这门课的本质。刚开始学这门课时,当时还不清楚这门课程的目的,现在,我真正的理解了:数据结构像是身体的骨骼,而C语言是填充这骨骼的肉体,二者相结合才能使整个程序更加完整,健全。数据结构是个框架,模型,抽象数据类型中列举了各种操作,而所用的C语言,将各种操作描述出来构成算法。数据结构+算法=程序设计。 在这次设计的过程中,我还遇到了,很多的问题。顺序表是按顺序存储的,用了一维数组来存储,又结合C语言的程序设计,但是,在执行时出现了问题。后来问同学,指出我的错误,不过获益不少。我又重新整理思路,把顺序表的基本操作写好了。虽然走了很多弯路,但是让我认识到,一定要创新,大胆,不能按照旧的思路去干新的事情。 但是细节上出了问题。比如说,有些变量的重复定义,有些变量又没有定义,在调用函数,就直接复制过来,没有改参数……通过修改,我深刻理解到:细节决定成败,在以后, 不管做任何事情都要认真,细心。 五种排序算法的分析与比较 广东医学院医学信息专业郭慧玲 摘要:排序算法是计算机程序设计广泛使用的解决问题的方法,研究排序算法具有重要的理论意义和广泛的应用价值。文章通过描述冒泡、选择、插入、归并和快速5种排序算法,总结了它们的时间复杂度、空间复杂度和稳定性。通过实验验证了5种排序算法在随机、正序和逆序3种情况下的性能,指出排序算法的适用原则,以供在不同条件下选择适合的排序算法借鉴。 关键词:冒泡排序;选择排序;插入排序;归并排序;快速排序。 排序是计算机科学中基本的研究课题之一,其目的是方便记录的查找、插入和删除。随着计算机的发展与应用领域的越来越广,基于计算机硬件的速度和存储空间的有限性,如何提高计算机速度并节省存储空间一直成为软件设计人员的努力方向。其中,排序算法已成为程序设计人员考虑的因素之一[1],排序算法选择得当与否直接影响程序的执行效率和内外存储空间的占用量,甚至影响整个软件的综合性能。排序操作[2,3],就是将一组数据记录的任意序列,重新排列成一个按关键字有序的序列。而所谓排序的稳定性[4]是指如果在排序的序列中,存在前后相同的两个元素,排序前和排序后他们的相对位臵不发生变化。 1 算法与特性 1.1冒泡排序 1.1.1冒泡排序的基本思想 冒泡排序的基本思想是[5,6]:首先将第1个记录的关键字和第2个记录的关键字进行比较,若为逆序,则将2个记录交换,然后比较第2个和第3个记录的关键字,依次类推,直至n-1个记录和第n个记录的关键字进行过比较为止。然后再按照上述过程进行下一次排序,直至整个序列有序为止。 1.1.2冒泡排序的特性 容易判断冒泡排序是稳定的。可以分析出它的效率,在最好情况下,只需通过n-1次比较,不需要移动关键字,即时间复杂度为O(n)(即正序);在最坏情况下是初始序列为逆序,则需要进行n-1次排序,需进行n(n-1)/2次比较,因此在最坏情况下时间复杂度为O(n2),附加存储空间为O(1)。 1.2选择排序 1.2.1选择排序的基本思想 选择排序的基本思想是[5,6]:每一次从待排序的记录中选出关键字最小的记录,顺序放在已排好序的文件的最后,直到全部记录排序完毕.常用的选择排序方法有直接选择排序和堆排序,考虑到简单和易理解,这里讨论直接选择排序。直接选择排序的基本思想是n个记录的文件的直接排序可经过n-1次直接选择排序得到有序结果。 1.2.2选择排序的特性 容易得出选择排序是不稳定的。在直接选择排序过程中所需进行记录移动的操作次数最少为0,最大值为3(n-1)。然而,无论记录的初始排序如何,所需进行的关键字间的比较次数相同,均为n(n-1)/2,时间 陕西科技大学实验报告 班级学号姓名实验组别 实验日期室温报告日期成绩 报告内容:(目的和要求、原理、步骤、数据、计算、小结等) 实验名称:查找与排序算法的实现和应用 实验目的: 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. 顺序查找: 在一个已知无(或有序)序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较,直到找出与给定关键字相同的数为止,它的缺点是效率低下。 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以 《数据结构》实验报告排序实验题目: 输入十个数,从插入排序,快速排序,选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路: 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 次记录移动(赋值)的操作。而实际上, 数据结构与算法设计 实验报告 (2016 — 2017 学年第1 学期) 实验名称: 年级: 专业: 班级: 学号: 姓名: 指导教师: 成都信息工程大学通信工程学院 一、实验目的 验证各种简单的排序算法。在调试中体会排序过程。 二、实验要求 (1)从键盘读入一组无序数据,按输入顺序先创建一个线性表。 (2)用带菜单的主函数任意选择一种排序算法将该表进行递增排序,并显示出每一趟排序过程。 三、实验步骤 1、创建工程(附带截图说明) 2、根据算法编写程序(参见第六部分源代码) 3、编译 4、调试 四、实验结果图 图1-直接输入排序 图2-冒泡排序 图3-直接选择排序 五、心得体会 与哈希表的操作实验相比,本次实验遇到的问题较大。由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念,设计思路特别混乱。虽然在理清思路后成功解决了直接输入和直接选择两种算法,但冒泡 排序的算法仍未设计成功。虽然在老师和同学的帮助下完成了冒泡排序的算法,但还需要多练习这方面的习题,平时也应多思考这方面的问题。而且,在直接输入和直接选择的算法设计上也有较为复杂的地方,对照书本做了精简纠正。 本次实验让我发现自己在算法设计上存在一些思虑不周的地方,思考问题过于片面,逻辑思维能力太过单薄,还需要继续练习。 六、源代码 要求:粘贴个人代码,以便检查。 #include 第8章怎样研究算法:排序算法示例 1、排序算法是最基本的算法,很多复杂算法都是以排序为基础进行构造的。关于排序算法,下列说法不正确的是_____。 (A)大规模数据集合中查找有无某些元素的问题,有序数据集合比无序数据集合的查找要快得多; (B)大规模数据集合中按元素分组进行计算的问题,有序数据集合比无序数据集合的计算要快得多; (C)对无序数据集合,两个算法X和Y:X采用无序数据处理,Y采用先将无序数据排序成有序数据,然后进行处理;则对前述(A)、(B)两类问题,Y算法一定比X算法慢; (D)上述说法有不正确的; 答案:C 解释: 本题考核排序算法的研究 在大规模数据集合中查找,有序数据集合有利算法进行和判断,要比无序数据集合查找的快,对于(C)选项,Y算法尽管需要排序后再处理,但排序处理后的数据查找更加快捷,因此可能Y算法比X算法更快。 具体内容请参考排序算法以及第八章课件。 2、下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法:针对一个“学生”数据表,如下示意,找出“成绩”为某一分数的所有学生。 【算法A1】 Start of algorithm A1 Step 1. 从数据表的第1条记录开始,直到其最后一条记录为止,读取每一条记录,做Step 2。Step 2. 对每一条记录,判断成绩是否等于给定的分数:如果是,则输出;如果不是,则不输出。 End of algorithm A1 【算法A2】 Start of algorithm A2 Step 1. 从数据表的第1条记录开始,直到其最后一条记录为止,读取每一条记录,做Step 2和Step 3。 Step 2. 对每一条记录,判断成绩是否等于给定的分数:如果等于,则输出;如果不等于,则不输出。 Step 3. 判断该条记录的成绩是否小于给定的分数:如果不是,则继续;否则,退出循环,算法结束。 End of algorithm A2 【算法A3】 Start of algorithm A3 Step 1. 假设数据表的最大记录数是n,待查询区间的起始记录位置Start为1,终止记录位置Finish为n; Step 2. 计算中间记录位置I = (Start+Finish)/2,读取第I条记录。 Step 3. 判断第I条记录的成绩与给定查找分数: (3.1)如果是小于关系,则调整Finish = I-1;如果Start >Finish则结束,否则继续做Step 2; (3.2)如果是大于关系,则调整Start = I+1;如果Start>Finish则结束,否则继续做Step 2; (3.3)如果是等于关系,则输出,继续读取I周围所有的成绩与给定查找条件相等的记录并输出,直到所有相等记录查询输出完毕则算法结束。 End of algorithm A3 针对上述三个算法,回答下列问题: (1)关于算法A1, A2, A3的快慢问题,下列说法正确的是_____。 (A)算法A1快于算法A2,算法A2快于算法A3; (B)算法A2快于算法A1,算法A2快于算法A3; (C)算法A3快于算法A2,算法A2快于算法A1; (D)算法A1快于算法A3,算法A3快于算法A2; (E)上述都不正确。 答案:C 解释: 本题考核排序算法的研究 首先,数据是有序排列的,从大到小。 算法A1依次搜索,穷举。 算法A2与A1一样,穷举,不同的是它利用数据是从大到小排序的特点,因此,如果当前数据比如果小于目标数,那么说明只有的也一定小于,则目标不在序列中。因此,A2比A1快。 算法A3利用数据有序特点,采用二分查找,每次将目标数与中间值比较,缩小搜索范围,因此A3比A2快。 综上,答案选(C)。 具体内容请参考排序算法以及第八章课件。 电子科技大学实验报告 课程名称:数据结构与算法 学生姓名: 学号: 点名序号: 指导教师: 实验地点:基础实验大楼 实验时间: 5月20日 2014-2015-2学期 信息与软件工程学院五种排序算法的分析与比较
实验8查找与排序算法的实现和应用
《数据结构》实验报告——排序.docx
排序操作实验报告
第8章怎样研究算法排序算法示例练习题答案解析
实验报告-排序与查找