下载文档原格式
查找排序实验报告一、实验目的本次实验的主要目的是深入理解和比较不同的查找和排序算法在性能和效率方面的差异。
通过实际编程实现和测试，掌握常见查找排序算法的原理和应用场景，为今后在实际编程中能够选择合适的算法解决问题提供实践经验。
二、实验环境本次实验使用的编程语言为 Python，开发环境为 PyCharm。
计算机配置为：处理器_____，内存_____，操作系统_____。
三、实验内容1、查找算法顺序查找二分查找2、排序算法冒泡排序插入排序选择排序快速排序四、算法原理1、顺序查找顺序查找是一种最简单的查找算法。
它从数组的一端开始，依次比较每个元素，直到找到目标元素或者遍历完整个数组。
其时间复杂度为 O(n)，在最坏情况下需要遍历整个数组。
2、二分查找二分查找适用于已排序的数组。
它通过不断将数组中间的元素与目标元素进行比较，将查找范围缩小为原来的一半，直到找到目标元素或者确定目标元素不存在。
其时间复杂度为 O(log n)，效率较高。
3、冒泡排序冒泡排序通过反复比较相邻的两个元素并交换它们的位置，将最大的元素逐步“浮”到数组的末尾。
每次遍历都能确定一个最大的元素，经过 n-1 次遍历完成排序。
其时间复杂度为 O(n^2)。
4、插入排序插入排序将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的合适位置。
其时间复杂度在最坏情况下为 O(n^2)，但在接近有序的情况下性能较好。
5、选择排序选择排序每次从待排序数组中选择最小的元素，与当前位置的元素交换。
经过 n-1 次选择完成排序。
其时间复杂度为 O(n^2)。
6、快速排序快速排序采用分治的思想，选择一个基准元素，将数组分为小于基准和大于基准两部分，然后对这两部分分别递归排序。
其平均时间复杂度为 O(n log n)，在大多数情况下性能优异。
五、实验步骤1、算法实现使用Python 语言实现上述六种查找排序算法，并分别封装成函数，以便后续调用和测试。
c程序实验报告C程序实验报告引言在计算机科学领域中，C语言是一种被广泛使用的编程语言，它具有高效、灵活和可移植等特点。
为了更好地掌握C语言的基本概念和编程技巧，我们进行了一系列的C程序实验。
本实验报告将对实验过程、实验结果和实验心得进行详细描述和分析。
实验一：Hello World在第一个实验中，我们编写了一个简单的C程序，输出了"Hello World"这个经典的字符串。
通过这个实验，我们熟悉了C语言的基本语法和编译运行的流程。
这个简单的程序为我们后续的实验打下了坚实的基础。
实验二：计算器在第二个实验中，我们设计了一个简单的计算器程序。
该程序可以进行基本的加、减、乘、除运算，并能够根据用户的输入进行相应的计算。
通过这个实验，我们学会了如何使用变量、运算符和控制语句来实现简单的计算功能。
同时，我们也了解了C语言中的数据类型和输入输出函数的使用。
实验三：学生成绩管理系统在第三个实验中，我们开发了一个学生成绩管理系统。
该系统可以实现学生信息的录入、查询和统计功能。
我们使用了结构体和数组来存储学生信息，并通过循环和条件语句实现了不同功能的选择。
这个实验让我们更深入地了解了C语言中的复合数据类型和数组的使用。
实验四：文件操作在第四个实验中，我们学习了C语言中的文件操作。
我们通过编写一个简单的文件管理系统，实现了文件的创建、读取、写入和删除等功能。
通过这个实验，我们掌握了C语言中文件操作函数的使用方法，并了解了文件的打开和关闭过程。
实验五：排序算法在第五个实验中，我们研究了几种常见的排序算法，包括冒泡排序、插入排序和快速排序。
我们通过编写这些排序算法的C程序，对它们的原理和实现进行了深入的分析。
这个实验让我们更加熟悉了C语言中的循环和条件语句，并提高了我们的编程能力。
实验六：链表在第六个实验中，我们学习了链表这种常见的数据结构。
我们编写了一个简单的链表程序，实现了链表的创建、插入和删除等操作。
一、实验目的1. 熟悉常用的查找和排序算法，掌握它们的原理和实现方法。
2. 提高编程能力，提高算法分析能力。
3. 通过实验验证查找和排序算法的性能。
二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm三、实验内容1. 查找算法：二分查找、线性查找2. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序四、实验步骤1. 设计一个数据结构，用于存储待查找和排序的数据。
2. 实现二分查找算法，用于查找特定元素。
3. 实现线性查找算法，用于查找特定元素。
4. 实现冒泡排序、选择排序、插入排序、快速排序、归并排序算法，对数据进行排序。
5. 分别测试查找和排序算法的性能，记录时间消耗。
五、实验结果与分析1. 查找算法（1）二分查找算法输入数据：[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]查找目标：11查找结果：成功，位置为5（2）线性查找算法输入数据：[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]查找目标：11查找结果：成功，位置为52. 排序算法（1）冒泡排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]（2）选择排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]（3）插入排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]（4）快速排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]（5）归并排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]3. 性能测试（1）查找算法性能测试二分查找算法在数据量较大的情况下，查找效率明显优于线性查找算法。
（2）排序算法性能测试在数据量较大的情况下，快速排序和归并排序的性能明显优于冒泡排序、选择排序和插入排序。
排序和查找的实验报告实验报告：排序和查找引言排序和查找是计算机科学中非常重要的基本算法。
排序算法用于将一组数据按照一定的顺序排列，而查找算法则用于在已排序的数据中寻找特定的元素。
本实验旨在比较不同排序和查找算法的性能，并分析它们的优缺点。
实验设计为了比较不同排序算法的性能，我们选择了常见的几种排序算法，包括冒泡排序、插入排序、选择排序、快速排序和归并排序。
我们使用相同的随机数据集对这些算法进行了测试，并记录了它们的执行时间和占用空间。
在查找算法的比较实验中，我们选择了顺序查找和二分查找两种常见的算法。
同样地，我们使用相同的随机数据集对这些算法进行了测试，并记录了它们的执行时间和占用空间。
实验结果在排序算法的比较实验中，我们发现快速排序和归并排序在大多数情况下表现最好，它们的平均执行时间和空间占用都要优于其他排序算法。
而冒泡排序和插入排序则表现较差，它们的执行时间和空间占用相对较高。
在查找算法的比较实验中，二分查找明显优于顺序查找，尤其是在数据规模较大时。
二分查找的平均执行时间远远小于顺序查找，并且占用的空间也更少。
结论通过本实验的比较，我们得出了一些结论。
首先，快速排序和归并排序是较优的排序算法，可以在大多数情况下获得较好的性能。
其次，二分查找是一种高效的查找算法，特别适用于已排序的数据集。
最后，我们也发现了一些排序和查找算法的局限性，比如冒泡排序和插入排序在大数据规模下性能较差。
总的来说，本实验为我们提供了对排序和查找算法性能的深入了解，同时也为我们在实际应用中选择合适的算法提供了一定的参考。
希望我们的实验结果能够对相关领域的研究和应用有所帮助。
实验七顺序查找一、实验目的1．掌握顺序查找操作的算法实现。
二、实验平台操作系统：Windows7或Windows XP开发环境：JA V A三、实验内容及要求1．建立顺序查找表，并在此查找表上实现顺序查找操作。
四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号以及模块：Netbeans 6.5以上或Eclipse、MyEclipse等编程环境下。
五、知识准备前期要求掌握查找的含义和顺序查找操作的方法。
六、验证性实验1．实验要求编程实现如下功能：（1）根据输入的查找表的表长n和n个关键字值，建立顺序查找表，并在此查找表中用顺序查找方法查找给定关键值的记录，最后输出查找结果。
2. 实验相关原理：查找表分别静态查找表和动态查找表两种，其中只能做引用操作的查找表称为静态查找表。
静态查找表采用顺序存储结构，待查找的记录类可描述如下：public class RecordNode {private Comparable key; //关键字private Object element; //数据元素……}待排序的顺序表类描述如下：public class SeqList {private RecordNode[] r; //顺序表记录结点数组private int curlen; //顺序表长度，即记录个数// 顺序表的构造方法，构造一个存储空间容量为maxSize的顺序表public SeqList(int maxSize) {this.r = new RecordNode[maxSize]; // 为顺序表分配maxSize个存储单元this.curlen = 0; // 置顺序表的当前长度为0}……}【核心算法提示】查找操作是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录的过程。
若查找表中存在这样一个记录，则称“查找成功”。
查找结果给出整个记录的信息，或指示该记录在查找表中的位置；若在查找表中不存在这样的记录，则称“查找不成功”。
实验七查找和排序算法的实现一．实验目的及要求（1）学生在实验中体会各种查找和部排序算法的基本思想、适用场合，理解开发高效算法的可能性和寻找、构造高效算法的方法。
（2）掌握运用查找和排序解决一些实际应用问题。
二.实验容：（1）编程实现一种查找算法（如折半查找、二叉排序树的查找、哈希查找等），并计算相应的ASL。
（2）编程实现一种部排序算法（如插入排序、快速排序等）。
三.实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现一种查找算法（如折半查找、二叉排序树的查找、哈希查找等），并计算相应的ASL。
➢程序代码：折半查找：头文件：#define EQ(a,b) ((a)==(b))#define LT(a,b) ((a)<(b))#define maxlength 20typedef int ElemType;typedef struct{ElemType key;ElemType other;}card;//每条记录包含的数据项typedef struct{card r[maxlength];int length;}SSTable;//一表中包含的记录容量void Create(SSTable &L);int Search(SSTable L,int elem);功能函数：#include"1.h"#include"stdio.h"void Create(SSTable &L){printf("新的线性表已经创建，请确定元素个数（不超过20）\n");scanf("%d",&L.length);printf("请按递增序列输入具体的相应个数的整数元素（空格隔开）\n");for(int i=0;i<L.length;i++){scanf("%d",&L.r[i].key);}}int Search(SSTable L,int elem){if(L.r[L.length-1].key<elem||L.r[0].key>elem){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("该元素在第%d位\n",mid+1); return 0;}else if(LT(elem,L.r[mid].key)){high=mid-1;}else{low=mid+1;}}printf("表中没有该元素（不在围）\n");return 0;}主函数：#include"stdio.h"#include"1.h"int main(){SSTable L;Create(L);printf("\n");printf("此时的线性表元素：\n");for(int a=0;a<L.length;a++){printf("%d ",L.r[a].key);}printf("\n");printf("\n");int elem;do{printf("请输入要查找的元素(输入000表示结束程序)\n");scanf("%d",&elem);if(elem!=000){Search(L,elem);}}while(elem!=000);return 0;}➢运行结果：（2）编程实现一种部排序算法（如插入排序、快速排序等）。
实验七查找、排序的应用一、实验目的1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。
2、学会比较各种排序与查找算法的优劣。
3、学会针对所给问题选用最适合的算法。
4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。
二、实验内容[问题描述]对学生的基本信息进行管理。
[基本要求]设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。
要求实现以下功能：1．总成绩要求自动计算；2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；3．排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。
[测试数据]由学生依据软件工程的测试技术自己确定。
三、实验前的准备工作1、掌握哈希表的定义，哈希函数的构造方法。
2、掌握一些常用的查找方法。
1、掌握几种常用的排序方法。
2、掌握直接排序方法。
四、实验报告要求1、实验报告要按照实验报告格式规范书写。
2、实验上要写出多批测试数据的运行结果。
3、结合运行结果，对程序进行分析。
五、算法设计a、折半查找设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。
初始时，令low=1,high=n,mid=(low+high)/2，让key与mid指向的记录比较，若key==r[mid].key，查找成功若key<r[mid].key，则high=mid-1若key>r[mid].key，则low=mid+1重复上述操作，直至low>high时，查找失败b、顺序查找从表的一端开始逐个进行记录的关键字和给定值的比较。
在这里从表尾开始并把下标为0的作为哨兵。
void chaxun(SqList &ST) //查询信息{ cout<<"\n************************"<<endl;cout<<"~ (1)根据学号查询 ~"<<endl;cout<<"~ (2)根据姓名查询 ~"<<endl;cout<<"~ (3)根据性别查询 ~"<<endl;cout<<"~ (4)退出 ~"<<endl;cout<<"************************"<<endl; if(m==1) 折半查找算法：for(int i=1;i<ST.length;i++)//使学号变为有序for(int j=i;j>=1;j--)if(ST.r[j].xuehao<ST.r[j-1].xuehao){LI=ST.r[j];ST.r[j]=ST.r[j-1];ST.r[j-1]=LI;}int a=0;cout<<"输入要查找的学号"<<endl;cin>>n;int low,high,mid;low=0;high=ST.length-1; // 置区间初值while (low<=high){mid=(low+high)/2;if(n==ST.r[mid].xuehao){cout<<ST.r[mid].xuehao<<""<<ST.r[mid].xingming<<""<<ST.r[mid].xingbei<<""<<ST.r[mid].chengji1<<""<<ST.r[mid].chengji2<<""<<ST.r[mid].zong<<endl;a=1;break;}else if(n<ST.r[mid].xuehao )high=mid-1; // 继续在前半区间进行查找elselow=mid+1; // 继续在后半区间进行查找顺序查找算法:cout<<"输入要查找的姓名"<<endl;cin>>name;for(int i=0;i<ST.length;i++){if(name==ST.r[i].xingming){cout<<ST.r[i].xuehao<<""<<ST.r[i].xingming<<""<<ST.r[i].xingbei<<""<<ST.r[i].chengji1<<""<<ST.r[i].chengji2<<""<<ST.r[i].zong<<endl;a=1;}1、插入排序每步将一个待排序的记录，按其关键码大小，插入到前面已经排好序的一组记录的适当位置上，直到记录全部插入为止。
查找和排序实验报告
本实验主要针对以查找、排序算法为主要实现目标的软件开发，进行实验室研究。
实
验包括：冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、基数排序，
以及折半查找算法。
实验采用C语言编写，在完成以上排序以及查找方法的基础上，针对实验的工程要求，进行了性能分析，分析了算法空间复杂度以及时间复杂度。
通过首先采用循环方式，构建未排序数组，在此基础上，调用算法实现查找和排序。
也对不同算法进行对比分析，将数据量在100个至30000个之间进行测试。
结果表明：快速排序与希尔排序在时间复杂度方面具有最好的表现，而冒泡排序和选
择排序时间复杂度较高。
在空间复杂度方面，基数排序表现最佳，折半查找的空间复杂度
则比较可观。
在工程应用中，根据对不同排序算法的研究，可以更准确、有效地选择正确的算法实现，有效应用C语言搭建软件系统，提高软件应用效率。
（建议加入算法图）
本实验结束前，可以得出结论：
另外，也可以从这些研究中发现，在使用C语言实现软件系统时，应该重视算法支持
能力，以提高软件应用效率。
由于查找和排序算法在软件应用中占有重要地位，此次实验
对此有贡献，可为未来开发提供支持。
实验七查找和排序算法的实现一．实验目的及要求（1）学生在实验中体会各种查找和内部排序算法的基本思想、适用场合，理解开发高效算法的可能性和寻找、构造高效算法的方法。
（2）掌握运用查找和排序解决一些实际应用问题。
二.实验内容：（1）编程实现一种查找算法（如折半查找、二叉排序树的查找、哈希查找等），并计算相应的ASL。
（2）编程实现一种内部排序算法（如插入排序、快速排序等）。
三.实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现一种查找算法（如折半查找、二叉排序树的查找、哈希查找等），并计算相应的ASL。
➢程序代码：折半查找：头文件：#define EQ(a,b) ((a)==(b))#define LT(a,b) ((a)<(b))#define maxlength 20typedef int ElemType;typedef struct{ElemType key;ElemType other;}card;//每条记录包含的数据项typedef struct{card r[maxlength];int length;}SSTable;//一张表中包含的记录容量void Create(SSTable &L);int Search(SSTable L,int elem);功能函数：#include"1.h"#include"stdio.h"void Create(SSTable &L){printf("新的线性表已经创建，请确定元素个数（不超过20）\n");scanf("%d",&L.length);printf("请按递增序列输入具体的相应个数的整数元素（空格隔开）\n");for(int i=0;i<L.length;i++){scanf("%d",&L.r[i].key);}}int Search(SSTable L,int elem){if(L.r[L.length-1].key<elem||L.r[0].key>elem){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("该元素在第%d位\n",mid+1); return 0;}else if(LT(elem,L.r[mid].key)){high=mid-1;}else{low=mid+1;}}printf("表中没有该元素（不在范围内）\n");return 0;}主函数：#include"stdio.h"#include"1.h"int main(){SSTable L;Create(L);printf("\n");printf("此时的线性表元素：\n");for(int a=0;a<L.length;a++){printf("%d ",L.r[a].key);}printf("\n");printf("\n");int elem;do{printf("请输入要查找的元素(输入000表示结束程序)\n");scanf("%d",&elem);if(elem!=000){Search(L,elem);}}while(elem!=000);return 0;}➢运行结果：（2）编程实现一种内部排序算法（如插入排序、快速排序等）。
程序代码部分：直接插入排序头文件：#define maxlength 20//最大数据容量#define OK 1typedef int Status;typedef int Other;typedef int KeyType;typedef struct{KeyType key;Other data;}Red;typedef struct{Red r[maxlength+1];//加了个哨兵的位置int length;//当前数据个数}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<L.length+1;i++){scanf("%d",&L.r[i].key);}return OK;}Status Insertsort(SqList &L){for(int i=2;i<L.length+1;i++){L.r[0]=L.r[i];//交换的应该是该位置记录的完整数据项，而不仅仅是数据项中的一个keyfor(int j=i;j>0&&L.r[0].key<L.r[j-1].key/*这里是依据记录中的数据项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<L.length+1;a++){printf("%d ",L.r[a].key);}printf("\n");printf("\n");Insertsort(L);printf("排序后的线性表元素：\n");for(int b=1;b<L.length+1;b++){printf("%d ",L.r[b].key);}printf("\n");return 0;}快速排序头文件：#define maxlength 20//最大数据容量#define OK 1typedef int Status;typedef int Other;typedef int KeyType;typedef struct{KeyType key;Other data;}Red;typedef struct{Red r[maxlength+1];//加了个哨兵的位置int length;//当前数据个数}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");for(int i=1/*将存放枢轴中关键字所在记录完整信息的位置【0】空出来*/;i<L.length+1;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<high){while(low<high&&L.r[high].key>=pivotkey){high--;}//从右端往左L.r[low]=L.r[high];while(low<high&&L.r[low].key<=pivotkey){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<high){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<L.length+1;a++){printf("%d ",L.r[a].key);}printf("\n");printf("\n");printf("请输入无序子列的开始和结束位置（有序子列不用管）\n");int low,high;scanf("%d %d",&low,&high);QSort(L,low,high);printf("排序后的线性表元素：\n");for(int b=1;b<L.length+1;b++){printf("%d ",L.r[b].key);}printf("\n");return 0;➢运行结果：四.实验结果的分析与评价（该部分如不够填写，请另加附页）1.快速排序利用了递归的思想；2.折半查找使用前提为：数列有序注：实验成绩等级分为（90－100分）优，（80－89分）良，(70-79分)中，（60－69分）及格，（59分）不及格。
