下载文档原格式
数据结构查找实验报告数据结构查找实验报告1·实验目的本实验旨在研究不同的查找算法在不同数据结构下的性能表现，通过实验结果对比分析，选取最优算法来完成查找操作。
2·实验方法2·1 数据结构选择在本实验中，我们选择了常用的数据结构进行查找性能比较，包括线性表、二叉树、哈希表等。
2·2 查找算法选择我们选择了以下常用的查找算法进行实验：●顺序查找●二分查找●插值查找●二叉查找树●平衡二叉查找树（AVL树）●哈希查找3·实验过程3·1 实验环境设置首先，我们需要搭建合适的实验环境，包括编程语言选择、编译器、开发环境等。
在本次实验中，我们选择了C++编程语言，并使用了Visual Studio 2019作为开发环境。
3·2 实验步骤为了比较各个查找算法的性能，我们按照以下步骤进行实验： 1·创建用于查找的数据结构，并初始化数据集合。
2·调用每个查找算法进行查找，并记录查找耗时。
3·分析实验结果，比较各个查找算法的性能。
4·实验结果与分析根据实验步骤中记录的各个查找算法的耗时，我们得到了以下结果：●对于小规模数据集，顺序查找表现较好。
●对于有序数据集，二分查找和插值查找表现最佳。
●对于动态数据集，哈希表的查找效率最高。
5·结论根据实验结果与分析，我们得出以下结论：●不同的数据结构适用于不同的查找需求。
●在静态有序数据集中，二分查找和插值查找是较好的选择。
●在动态数据集中，哈希表具有较高的查找效率。
附件：附件1：实验数据集附件2：查找算法代码法律名词及注释：1·数据结构：数据之间的组织方式和关系，使得我们可以高效地进行数据的存储和操作。
2·查找算法：在给定某个目标值的情况下，在给定数据集内寻找目标值的算法。
3·顺序查找：逐个比较目标值和数据集内的元素，直到找到目标值或者遍历完整个数据集。
实验B06: 静态表的查找操作实验一、实验名称和性质二、实验目的1．掌握顺序查找操作的算法实现。
2．掌握二分查找操作的算法实现及实现该查找的前提。
3．掌握索引查找操作的算法实现。
三、实验内容1．建立顺序查找表，并在此查找表上实现顺序查找操作（验证性内容）。
2．建立有序顺序查找表，并在此查找表上实现二分查找操作（验证性内容）。
3．建立索引查找表，并在此查找表上实现索引查找操作（设计性内容）。
四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号以及模块：Windows环境下的TurboC2.0以上或VC++五、知识准备前期要求掌握查找的含义和顺序查找、二分查找及索引查找操作的方法。
六、验证性实验1．实验要求编程实现如下功能：（1）根据输入的查找表的表长n和n个关键字值，建立顺序查找表，并在此查找表中用顺序查找方法查找给定关键值的记录，最后输出查找结果。
（2）根据输入的查找表的表长n和n个按升排列的关键字值，建立有序顺序查找表，并在此查找表中用二分查找方法查找给定关键值的记录，最后输出查找结果。
（3）主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行哪一种查找操作。
2. 实验相关原理：查找表分别静态查找表和动态查找表两种，其中只能做引用操作的查找表称为静态查找表。
静态查找表采用顺序存储结构的数据描述为：#define MAXSIZE 100 /*顺序查找表的最大长度*/typedef int keytype;typedef struct{keytype key;}redtype;typedef struct{redtype elem[MAXSIZE];int length;}Sstable;【核心算法提示】查找操作是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录的过程。
若查找表中存在这样一个记录，则称“查找成功”。
查找结果给出整个记录的信息，或指示该记录在查找表中的位置；若在查找表中不存在这样的记录，则称“查找不成功”。
一、实验目的1. 理解并掌握几种常见查找算法的基本原理和实现方法。
2. 比较不同查找算法的时间复杂度和空间复杂度。
3. 通过实验验证查找算法的效率和适用场景。
二、实验内容本次实验主要涉及以下查找算法：1. 顺序查找法2. 二分查找法3. 散列查找法三、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发环境：PyCharm四、实验步骤1. 实现顺序查找法2. 实现二分查找法3. 实现散列查找法4. 编写测试程序，分别对三种查找算法进行测试5. 比较三种查找算法的性能五、实验结果与分析1. 顺序查找法（1）实现代码```pythondef sequential_search(arr, target):for i in range(len(arr)):if arr[i] == target:return ireturn -1```（2）测试程序```pythonarr = [5, 3, 8, 6, 2, 7, 4, 9, 1]target = 6print("顺序查找结果：", sequential_search(arr, target))```（3）分析顺序查找法的时间复杂度为O(n)，空间复杂度为O(1)。
当数据量较大时，查找效率较低。
2. 二分查找法（1）实现代码```pythondef binary_search(arr, target):left, right = 0, len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return midelif arr[mid] < target:left = mid + 1else:right = mid - 1return -1```（2）测试程序```pythonarr = [1, 2, 3, 4, 5, 6, 7, 8, 9]target = 6print("二分查找结果：", binary_search(arr, target))```（3）分析二分查找法的时间复杂度为O(log2n)，空间复杂度为O(1)。
实验B06: 静态表的查找操作实验一、实验名称和性质二、实验目的1．掌握顺序查找操作的算法实现。
2．掌握二分查找操作的算法实现及实现该查找的前提。
3．掌握索引查找操作的算法实现。
三、实验内容1．建立顺序查找表，并在此查找表上实现顺序查找操作（验证性内容）。
2．建立有序顺序查找表，并在此查找表上实现二分查找操作（验证性内容）。
3．建立索引查找表，并在此查找表上实现索引查找操作（设计性内容）。
四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号以及模块：Windows环境下的TurboC2.0以上或VC++五、知识准备前期要求掌握查找的含义和顺序查找、二分查找及索引查找操作的方法。
六、验证性实验1．实验要求编程实现如下功能：（1）根据输入的查找表的表长n和n个关键字值，建立顺序查找表，并在此查找表中用顺序查找方法查找给定关键值的记录，最后输出查找结果。
（2）根据输入的查找表的表长n和n个按升排列的关键字值，建立有序顺序查找表，并在此查找表中用二分查找方法查找给定关键值的记录，最后输出查找结果。
（3）主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行哪一种查找操作。
2. 实验相关原理：查找表分别静态查找表和动态查找表两种，其中只能做引用操作的查找表称为静态查找表。
静态查找表采用顺序存储结构的数据描述为：#define MAXSIZE 100 /*顺序查找表的最大长度*/typedef int keytype;typedef struct{keytype key;}redtype;typedef struct{redtype elem[MAXSIZE];int length;}Sstable;【核心算法提示】查找操作是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录的过程。
若查找表中存在这样一个记录，则称“查找成功”。
查找结果给出整个记录的信息，或指示该记录在查找表中的位置；若在查找表中不存在这样的记录，则称“查找不成功”。
实验四——查找一、实验目的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 80typedef struct{int number; umber;for(i=1;[i].number!=0;){cin>>[i].name>>[i].sex>>[i].age;++;cout<<endl;cin>>[++i].number;}}umber<<"\t"<<[i].name<<"\t"<<[i].sex<<"\t"<<[i].age<<endl;}umber==number)return i;}umber)return mid;elseif(number<[mid].number)high=mid-1;elselow=mid+1;}return 0;}void main(){int i,number;seqlist L;create(L);print(L);cout<<"折半查找:"<<endl;cout<<"输入学生学号:";cin>>number;if((i=halffind(L,number))!=0)cout<<"\t"<<[i].number<<"\t"<<[i].name<<"\t"<<[i].sex<<"\t"<<[i].age<<endl;elsecout<<"失败!"<<endl;cout<<"顺序查找:"<<endl;cout<<"输入学生学号:";cin>>number;if((i=find(L,number))!=0)cout<<"\t"<<[i].number<<"\t"<<[i].name<<"\t"<<[i].sex<<"\t"<<[i].age<<endl;elsecout<<"失败!"<<endl;}实验二：#include<>typedef struct{int number; 立二叉排序树"<<"\n\t2.插入学生信息"<<"\n\t3.查找学生信息"<<endl;cout<<"选择:";cin>>choice;switch(choice){case 1:{create(T);cout<<"成功建立!"<<endl;};break;case 2:{insert1(T);cout<<"插入成功!"<<endl;};break;case 3:{cout<<"输入待查学生的学号:";cin>>number;p=search(T,number);if(p)cout<<p-><<"\t"<<p-><<"\t"<<p-><<"\t"<<p-><<endl;elsecout<<"查找失败!"<<endl;};break;}cout<<"Continue(Y/N):";cin>>ctinue;if(ctinue=='y'||ctinue=='y')flag=1;elseflag=0;}}2.实验结果（截图）。
数据结构查找实验报告数据结构查找实验报告1. 简介查找是计算机科学中一种常见的操作，它用于在一组数据中快速定位特定的元素。
数据结构是计算机存储、组织数据的方式，可以有效地支持查找操作。
本实验报告将介绍查找算法的原理和实现，以及实验结果的分析和总结。
2. 查找算法2.1 顺序查找顺序查找是一种简单直观的查找算法，它从数据集的第一个元素开始逐个比较，直至找到目标元素或遍历完所有元素。
顺序查找的时间复杂度为O(n)，其中n是数据集的大小。
2.2 二分查找二分查找是一种高效的查找算法，它要求数据集必须是有序的。
它通过将数据集分成两部分，并与目标元素进行比较，以确定目标元素所在的区间，然后在该区间内继续二分查找，直至找到目标元素或确定目标元素不存在。
二分查找的时间复杂度为O(log n)，其中n是数据集的大小。
2.3 插值查找插值查找是对二分查找的一种改进，它根据目标元素的估计位置来确定比较的起始位置。
它适用于数据集分布均匀的情况，可以进一步减少查找的次数。
插值查找的时间复杂度为O(log(log n))。
3. 实验结果本次实验我们使用了三种查找算法（顺序查找、二分查找和插值查找）在不同大小的数据集上进行了性能测试。
实验结果如下表所示：---- 数据集大小 ---- 顺序查找时间（ms） ---- 二分查找时间（ms） ---- 插值查找时间（ms） ---------------------------------------------------------------------------------------------- 1000 ---- 10 ---- 2 ---- 1 -------- 10000 ---- 100 ---- 4 ---- 2 -------- 100000 ---- 1000 ---- 6 ---- 3 -------- 1000000 ---- 10000 ---- 8 ---- 4 ----从实验结果可以看出，随着数据集的增大，顺序查找的时间成正比增加，而二分查找和插值查找的时间相对较稳定。
数据结构实验实验一静态查找表中的查找一、实验目的：1、理解静态查找表的概念2、掌握顺序查找和折半查找算法及其实现方法3、理解顺序查找和折半查找的特点，学会分析算法的性能二、实验内容：1、按关键字从小到大顺序输入一组记录构造查找表，并且输出该查找表；2、给定一个关键字值，对所构造的查找表分别进行顺序查找和折半查找，输出查找的结果以及查找过程中“比较”操作的执行次数。
三、实验要求：1、查找表的长度、查找表中的记录和待查找的关键字值要从终端输入；2、具体的输入和输出格式不限；3、算法要具有较好的健壮性，对错误操作要做适当处理；4、输出信息中要标明所采用的查找方法类型。
实验二基于二叉排序树的查找一、实验目的：1、理解动态查找表和二叉排序树的概念2、掌握二叉排序树的构造算法及其实现方法3、掌握二叉排序树的查找算法及其实现方法二、实验内容：1、输入一组记录构造一颗二叉排序树，并且输出这棵二叉排序树的中序序列；2、给定一个关键字值，对所构造的二叉排序树进行查找，并输出查找的结果。
三、实验要求：1、二叉排序树中的记录和待查找的关键字值要从终端输入；2、输入的记录格式为(整数，序号)，例如(3, 2)表示关键字值为3，输入序号为2的记录；3、算法要具有较好的健壮性，对错误操作要做适当处理。
四、程序实现：(1)实现顺序查找表和折半查找表：#include<stdio.h>#define MAX_LENGTH 100typedef struct{int key[MAX_LENGTH];int length;}stable;int seqserch(stable ST,int key,int &count){int i;for(i=ST.length;i>0;i--){count++;if(ST.key[i]==key)return i;}return 0;}int binserch(stable ST,int key,int &count){int low=1,high=ST.length,mid;while(low<=high){count++;mid=(low+high)/2;if(ST.key[mid]==key)return mid;else if(key<ST.key[mid])high=mid-1;elselow=mid+1;}return 0;} main(){stable ST1;inta,b,k,x,count1=0,count2=0,temp=0;ST1.length=0;printf("请按从小到大的顺序输入查找表数据：(-1代表结束！)\n");for(a=0;a<MAX_LENGTH;a++){scanf("%d",&temp);if(temp!=-1){ST1.key[a]=temp;ST1.length++;}elsebreak;}printf("输入数据为：\n");for(b=0;b<ST1.length;b++){printf("%d ",ST1.key[b]);}printf("\n请输入要查找的数据：");scanf("%d",&k);a=seqserch(ST1,k,count1)+1;printf("\n顺序查找：该数据的位置在第：%d个\n",a);printf("查找次数为：%d\n\n",count1-1);a=binserch(ST1,k,count2)+1;printf("折半查找：该数据的位置在第：%d个\n",a);printf("查找次数为：%d\n",count2-1);}（2）二叉排序树的查找：#include<stdio.h> #include<malloc.h> typedef struct node {int data;int key;struct node *left,*right;}bitnode,*bittree;void serchbst(bittree T,bittree *F,bittree *C,int data){while(T!=NULL){if(T->data==data){*C=T;break;}else if(data<T->data){*F=T;T=T->left;}else{*F=T;T=T->right;}}return 0;}int insertbst(bittree *T,int key,int data) {bittree F=NULL,C=NULL,s;serchbst(*T,&F,&C,data);if(C!=NULL) return 0;s=(bittree)malloc(sizeof(bitnode));s->data=data;s->key=key;s->left=s->right=NULL;if(F==NULL) *T=s;else if(data<F->data)F->left=s;elseF->right=s;return 1; }void creatbst(bittree *T){int key,data;*T=NULL;printf("请输入数据以构造二叉排序树：(数据格式为:m n (-1000,-1000)代表结束)\n");scanf("%d%d",&key,&data);while(key!=-1000 || data!=-1000){insertbst(T,key,data);scanf("%d%d",&key,&data);}}void midTraverse(bittree T){if(T!=NULL){midTraverse(T->left);printf("(%d,%d)",T->key,T->data);midTraverse(T->right);}}main(){bittreeT=NULL,C=NULL,F=NULL;int key,data,temp;creatbst(&T);printf("此二叉树的中序序列为：");midTraverse(T);printf("\n请输入要查找的关键字：");scanf("%d",&data);serchbst(T,&F,&C,data);printf("此关键字的数据为：%d\n",C->key);}五、实现结果：(1)顺序查找和折半查找：(2)二叉树排序树查找：六、实验之心得体会：（1）在这次实验中，我基本上掌握了顺序查找、折半查找和二叉排序树查找的基本思想和实现方法，让我体会到了写程序时，不仅要考虑是否能够调试出结果，还要考虑程序实现的效率，这是一个编程人员必须要具备的一项总要的素质。
数据结构查找实验报告一、实验目的本次实验的主要目的是深入理解和掌握常见的数据结构查找算法，包括顺序查找、二分查找、哈希查找等，并通过实际编程实现和性能比较，分析它们在不同数据规模和分布情况下的效率和适用场景。
二、实验环境本次实验使用的编程语言为 Python 38，开发环境为 PyCharm。
实验中所使用的数据集生成工具为 numpy 库。
三、实验原理1、顺序查找顺序查找是一种最简单的查找算法，它从数据结构的开头依次逐个比较元素，直到找到目标元素或遍历完整个数据结构。
其平均时间复杂度为 O(n)。
2、二分查找二分查找要求数据结构是有序的。
通过不断将查找区间缩小为原来的一半，直到找到目标元素或者确定目标元素不存在。
其时间复杂度为 O(log n)。
3、哈希查找哈希查找通过将元素映射到一个特定的哈希表中，利用哈希函数计算元素的存储位置，从而实现快速查找。
理想情况下，其平均时间复杂度为 O(1)，但在存在哈希冲突时，性能可能会下降。
四、实验步骤1、数据集生成使用 numpy 库生成不同规模和分布的数据集，包括有序数据集、无序数据集和具有一定重复元素的数据集。
2、顺序查找实现编写顺序查找算法的函数，接受数据集和目标元素作为参数，返回查找结果（是否找到及查找次数）。
3、二分查找实现实现二分查找算法的函数，同样接受数据集和目标元素作为参数，并返回查找结果。
4、哈希查找实现构建哈希表并实现哈希查找函数，处理哈希冲突的情况。
5、性能比较对不同规模和类型的数据集，分别使用三种查找算法进行查找操作，并记录每种算法的查找时间和查找次数。
五、实验结果与分析1、顺序查找在无序数据集中，顺序查找的性能表现较为稳定，查找时间随着数据规模的增大线性增长。
但在有序数据集中，其性能没有优势。
2、二分查找二分查找在有序数据集中表现出色，查找时间随着数据规模的增大增长缓慢，体现了对数级别的时间复杂度优势。
然而，在无序数据集中无法使用。
数据结构——第五章查找：01静态查找表和动态查找表1.查找表可分为两类：（1）静态查找表：仅做查询和检索操作的查找表。
（2）动态查找表：在查询之后，还需要将查询结果为不在查找表中的数据元素插⼊到查找表中；或者，从查找表中删除其查询结果为在查找表中的数据元素。
2.查找的⽅法取决于查找表的结构：由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。
为了提⾼查找效率，需要在查找表中的元素之间⼈为地附加某种确定的关系，⽤另外⼀种结构来表⽰查找表。
3.顺序查找表：以顺序表或线性链表表⽰静态查找表，假设数组0号单元留空。
算法如下：int location(SqList L, ElemType &elem){ i = 1; p = L.elem; while (i <= L.length && *(p++)!= e) { i++; } if (i <= L.length) { return i; } else { return 0; }}此算法每次循环都要判断数组下标是否越界，改进⽅法：加⼊哨兵，将⽬标值赋给数组下标为0的元素，并从后向前查找。
改进后算法如下：int Search_Seq(SSTable ST, KeyType kval) //在顺序表ST中顺序查找其关键字等于key的数据元素。
若找到，则函数值为该元素在表中的位置，否则为0。
{ ST.elem[0].key = kval; //设置哨兵 for (i = ST.length; ST.elem[i].key != kval; i--) //从后往前找，找不到则返回0 { } return 0;}4.顺序表查找的平均查找长度为：(n+1)/2。
5.上述顺序查找表的查找算法简单，但平均查找长度较⼤，不适⽤于表长较⼤的查找表。
若以有序表表⽰静态查找表，则查找过程可以基于折半进⾏。
算法如下：int Search_Bin(SSTable ST, KeyType kval){ low = 1; high = ST.length; //置区间初值 while (low <= high) { mid = (low + high) / 2; if (kval == ST.elem[mid].key) { return mid; //找到待查元素 } else if (kval < ST.elem[mid].key) { high = mid - 1; //继续在前半区间查找 } else { low = mid + 1; //继续在后半区间查找 } } return 0; //顺序表中不存在待查元素} //表长为n的折半查找的判定树的深度和含有n个结点的完全⼆叉树的深度相同6.⼏种查找表的时间复杂度：（1）从查找性能看，最好情况能达到O(logn)，此时要求表有序；（2）从插⼊和删除性能看，最好情况能达到O(1)，此时要求存储结构是链表。
数据结构查找实验报告数据结构查找实验报告一、引言数据结构是计算机科学中的重要概念之一，它涉及到组织和管理数据的方式和方法。
在实际应用中，我们经常需要对大量的数据进行查找操作，因此查找算法的效率和准确性显得尤为重要。
本实验旨在通过对比不同的查找算法，探索其性能和适用场景。
二、实验目的本实验的目的是比较常见的查找算法，包括线性查找、二分查找和哈希查找，分析它们的时间复杂度和空间复杂度，并通过实验数据验证其效率。
三、实验方法1. 实验环境本实验使用C++语言进行编程，选择了Visual Studio作为开发环境，以保证实验结果的准确性和可靠性。
2. 实验步骤（1）线性查找线性查找是最简单直接的查找算法，它的原理是从头到尾逐个比较待查找元素和数组中的元素，直到找到目标元素或遍历完整个数组。
在实验中，我们随机生成一个包含一定数量元素的有序数组，并使用线性查找算法查找目标元素。
（2）二分查找二分查找是一种高效的查找算法，它基于有序数组的特点，通过不断缩小查找范围来快速定位目标元素。
在实验中，我们同样生成一个有序数组，并使用二分查找算法进行查找操作。
（3）哈希查找哈希查找是一种基于哈希表的查找算法，它通过将关键字映射到哈希表中的位置来实现快速查找。
在实验中，我们使用哈希查找算法对一个包含大量元素的数组进行查找。
四、实验结果与分析1. 时间复杂度通过实验数据统计，我们可以得到不同查找算法的平均时间复杂度。
线性查找的时间复杂度为O(n)，其中n为数组的大小；二分查找的时间复杂度为O(logn)，哈希查找的时间复杂度为O(1)。
可以看出，随着数据规模增大，二分查找和哈希查找的效率明显高于线性查找。
2. 空间复杂度线性查找的空间复杂度为O(1)，即不需要额外的存储空间；二分查找的空间复杂度为O(1)，哈希查找的空间复杂度为O(n)，其中n为哈希表的大小。
因此，从空间复杂度的角度来看，线性查找和二分查找相对较优。
3. 实验结果通过多次实验，我们得到了不同查找算法的平均查找时间。
数据结构：静态查找表1.写在前⾯ ►从查找说起： 在英汉字典中查找某个英⽂单词的中⽂解释；在新华字典中查找某个汉字的读⾳、含义；在对数表、平⽅根表中查找某个数的对数、平⽅根；邮递员送信件要按收件⼈的地址确定位置等等。
从计算机、计算机⽹络中查找特定的信息，就需要在计算机中存储包含该特定信息的表。
查找是许多程序中最消耗时间的⼀部分。
因⽽，⼀个好的查找⽅法会⼤⼤提⾼运⾏速度。
►先讨论静态查找表： 静态查找表应该是查找中最为简单的。
仅仅是在固定的表中对元素的查找，⽽不涉及修改表中的元素。
我们讨论的是在⽆序表、顺序表中的遍历查找和快速的折半查找。
2.代码分解 ►⽆序表上的顺序查找 ⽅式：从查找表的⼀端依序与表中的元素进⾏⽐较。
代码是很简单的，直接给出，以便后续分析：#include <iostream>typedef int KeyType;typedef struct {KeyType key;int info;}ElemType;typedef struct {ElemType *elem; // 数据元素存储空间基址，建表时int length; // 表的长度} SSTable;int Sq_search(SSTable ST, KeyType key) {// 在⽆序表中查找元素key，查找成功时，返回元素在表中的位置 ,否则返回0int i=ST.length;while (i>=1&&ST.elem[i].key!=key) i--;return i;}int Init_search(SSTable &ST,int length)//初始化表{ST.length=length;ST.elem = (ElemType *)malloc(sizeof(ElemType)*(length+1));}int Creat_search(SSTable &ST,int length)//创建表{ElemType *ptr = ST.elem;int temp =0;int i=0;ptr++; //我们将第⼀个元素空出来！while (temp!=-1&&(i++)<length){scanf("%d",&temp);ptr++->key=temp;}}int main() {SSTable table;Init_search(table,5);Creat_search(table,5);printf("已经找到位置：%d",Sq_search(table, 13));return 0;}说明： 请注意，我们在0号位置留空，在这⾥仅仅是为了直观显⽰索引位置！ ►设置监视哨 但是我们还可以优化这段代码，那就是设置监视哨。
静态查找表实验报告1. 题目采用长整型、整型、字符型为元素类型和顺序存储为存储结构，实现抽象数据类型静态查找表。
软件环境为Visual C++ 2010 Express。
2.抽象数据类型定义以及各基本操作的简要描述ADT StaticSearchTable{数据对象D：D是具有相同特性的数据元素的集合。
各个数据元素均含有类型相同，可唯一标识数据元素的关键字。
数据关系R：数据元素同属于一个集合。
基本操作P：Create(&ST,n)操作结果: 构造一个含n个数据元素的静态顺序查找表ST。
Destroy(&ST)初始条件：静态查找表ST存在操作结果：销毁表ST。
Search(St,key)初始条件：静态查找表ST存在,key为和关键字类型相同的给定值。
操作结果：若ST中存在关键字等于key的数据元素，则函数值为该元素在表中的位置，否则为“空”。
Traverse(ST,Visit())初始条件：静态查找表ST存在，Visit()是对元素操作的应用函数。
操作结果：按顺序对ST的每个元素调用函数Visit()一次且仅一次，一旦 Visit()失败，则操作失败。
} ADT StaticSearchTable3．存储结构定义公用头文件DS0.h:#include#include#include#include#include#include#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int Status;typedef int Boolean;（1）顺序表#define N 5 /* 数据元素为5个*/typedef int KeyType; /* 设关键字域为整型 */ typedef struct /*数据元素类型（教科书9.1）*/ {long number; /* 准考证号 */char name[9]; /* 姓名 */int politics; /* 政治 */int Chinese; /* 语文 */int English; /* 英语*/int math; /* 数学 */Int physics; /* 物理*/int chemistry; /* 化学*/int biology; /* 生物*/KeyType key;} ElemType;ElemType r[N]={{179324,"何芳",85,89,98,100,93,80,47}, {179325,"陈红",85,86,88,100,92,90,45}, {179326,"陆华",78,75,90,80,95,88,37}, {179327,"张平",82,80,78,98,84,96,40}, {179328,"赵怡",76,85,94,57,77,69,44}};#define total key /* 定义总分(total)为关键字 */对两个数值型关键字的比括较约定为如下的宏定义#define EQ(a,b) ((a)==(b))#define LT(a,b) ((a)<(b))#define LQ(a,b) ((a)<=(b))静态查找括的顺序存储结构typedef struct{ElemType *elem;int length;}SSTable;（2）有序表#define N 11 /* 数据元素个数*/typedef int KeyType; /* 设关键字域为整型*/typedef struct /* 数据元素类型*/{KeyType key; /* 关键字域*/int others; /* 其它部分*/}ElemType;ElemType r[N]={{5,1},{13,2},{19,3},{21,4},{37,5},{56,6},{64, 7},{75,8},{80,9},{88,10},{92,11}}; /* 数据元素(以教科书219数据为例),全局变量*/对两个数值型关键字括较约定为如下的宏定义#define EQ(a,b) ((a)==(b))#define LT(a,b) ((a)<(b))#define LQ(a,b) ((a)<=(b))静态查找表的顺序存储结构typedef struct{ElemType *elem;int length;}SSTable;（3）静态树表#define N 9 /* 数据元素个数 */typedef char KeyType; /* 设关键字域为字符型*/ typedef struct /* 数据元素类型*/{KeyType key;int weight;}ElemType;ElemType r[N]={{'A',1},{'B',1},{'C',2},{'D',5},{'E',3}, {'F',4},{'G',4},{'H',3},{'I',5}}; /*数据元素(以教科书例9-1为例),全局变量*/int sw[N+1]; /* 累计权值，全局变量*/两个数值型关键字的括较约定为如下的宏定义#define EQ(a,b) ((a)==(b))#define LT(a,b) ((a)<(b))#define LQ(a,b) ((a)<=(b))静态查表找的顺序存储结构typedef struct{ElemType *elem;Int length;}SSTable;4.算法设计（1）顺序表的查找Status Creat_Seq(SSTable *ST,int n){ // 操作结果:构造一个含个n数据元素的静态顺查找表ST(数据来自全局数组) int i;(*ST).elem=(ElemType *)calloc(n+1,sizeof(ElemType));if(!(*ST).elem)return ERROR;for(i=1;i<=n;i++)*((*ST).elem+i)=r[i-1]; //把全局数组的值依次赋给ST(*ST).length=n;return OK;}Status Destroy(SST able *ST){ //初始条件:静态查找表存在//操作结果销毁表括STfree((*ST).elem);(*ST).elem=NULL;(*ST).length=0;return OK;}int Search_Seq(SST able ST,KeyType key){ /*初始条件：静态查找表ST存在,key为和关键字类型相同的给定值。
数据结构实验报告课程数据结构 _ 实验名称查找院系专业班级实验地点姓名学号实验时间指导老师实验成绩批改日期一.实验目的1.熟悉静态查找的相关算法二.实验内容及要求1.实现顺序表的查找算法2.实现有序表的折半查找算法三.实验过程及结果实验过程：源程序：1、顺序查找：#include <stdio.h>#define MAX_SIZE 100typedef struct{int key;}element;element list[MAX_SIZE];int seqsearch(element list[],int searchnum,int num);int main(){int i,num,searchnum,k;printf("请输入元素的个数：");scanf("%d",&num);printf("请输入元素：\n");for(i=0;i<num;i++){scanf("%d",&list[i].key);}while(1){printf("请输入要查询的数据元素:");scanf("%d",&searchnum);k=seqsearch(list,searchnum,num);if(k!=-1){printf("所查询元素的下标为：");printf("%d\n",k);}elseprintf("查询元素不存在。
\n");}return 0;}int seqsearch(element list[],int searchnum,int num) {int j;list[num].key=searchnum;for(j=0;list[j].key!=searchnum;j++);return j<num?j:-1;}2、折半查找：#include <stdio.h>#define MAX_SIZE 100#define COMPARE(a,b) (a)>(b)?1:(a)==(b)?0:-1typedef struct{int key;}element;element list[MAX_SIZE];int binsearch(element list[],int searchnum,int num); int main(){int i,num,searchnum,k;printf("请输入元素的个数：");scanf("%d",&num);printf("请输入元素：\n");for(i=0;i<num;i++){scanf("%d",&list[i].key);}while(1){printf("请输入要查询的数据元素:");scanf("%d",&searchnum);k=binsearch(list,searchnum,num);if(k!=-1){printf("所查询元素的下标为：");printf("%d\n",k);}elseprintf("查询元素不存在。
查找实验报告第一篇：查找实验报告实验六查找实验目的：掌握几种查找的思想及算法问题分析：（一）顺序查找 1.查找思想从表的一端开始逐个将记录的关键字和给定K值进行比较，若某个记录的关键字和给定K值相等，查找成功；否则，若扫描完整个表，仍然没有找到相应的记录，则查找失败。
2.算法实现int Seq_Search(SST able ST,int key){int p;} ST.data[0].key=key;/* 设置监视哨兵,失败返回0 */ for(p=ST.length;ST.data[p].key!=key;p--);return(p);3.算法分析设查找每个记录成功的概率相等，即Pi=1/n；查找第i个元素成功的比较次数Ci=n-i+1 ；◆ 查找成功时的平均查找长度ASL：◆包含查找不成功时：查找失败的比较次数为n+1，若成功与不成功的概率相等，对每个记录的查找概率为Pi=1/(2n)，则平均查找长度ASL：（二）折半查找前提条件：查找表中的所有记录是按关键字有序(升序或降序)。
查找过程中，先确定待查找记录在表中的范围，然后逐步缩小范围(每次将待查记录所在区间缩小一半)，直到找到或找不到记录为止。
1.查找思想用Low、High和Mid表示待查找区间的下界、上界和中间位置指针，初值为Low=1，High=n。
⑴取中间位置Mid：Mid=⎣(Low+High)/2⎦；⑵比较中间位置记录的关键字与给定的K值：①相等：查找成功；②大于：待查记录在区间的前半段，修改上界指针：High=Mid-1，转⑴ ；③小于：待查记录在区间的后半段，修改下界指针：Low=Mid+1，转⑴ ；直到越界(Low>High)，查找失败。
2.算法实现int Bin_Search(SST able ST , KeyType k){int low=1，high=ST.length, mid;while(low<=high){mid=(low+high)/2;if(EQ(ST.data[mid].key, k))return(mid);else if(LT(ST.dat[mid].key, k))low=mid+1;else high=mid-1;}return(0);/*查找失败*/ } 3.算法分析①查找时每经过一次比较，查找范围就缩小一半，该过程可用一棵二叉树表示：◆根结点就是第一次进行比较的中间位置的记录；◆ 排在中间位置前面的作为左子树的结点；◆ 排在中间位置后面的作为右子树的结点；对各子树来说都是相同的。
数据结构实验
实验一静态查找表中的查找
一、实验目的：
1、理解静态查找表的概念
2、掌握顺序查找和折半查找算法及其实现方法
3、理解顺序查找和折半查找的特点，学会分析算法的性能
二、实验内容：
1、按关键字从小到大顺序输入一组记录构造查找表，并且输出该查找表；
2、给定一个关键字值，对所构造的查找表分别进行顺序查找和折半查找，输出查找的结果以及查找过程中“比较”操作的执行次数。
三、实验要求：
1、查找表的长度、查找表中的记录和待查找的关键字值要从终端输入；
2、具体的输入和输出格式不限；
3、算法要具有较好的健壮性，对错误操作要做适当处理；
4、输出信息中要标明所采用的查找方法类型。
实验二基于二叉排序树的查找
一、实验目的：
1、理解动态查找表和二叉排序树的概念
2、掌握二叉排序树的构造算法及其实现方法
3、掌握二叉排序树的查找算法及其实现方法
二、实验内容：
1、输入一组记录构造一颗二叉排序树，并且输出这棵二叉排序树的中序序列；
2、给定一个关键字值，对所构造的二叉排序树进行查找，并输出查找的结果。
三、实验要求：
1、二叉排序树中的记录和待查找的关键字值要从终端输入；
2、输入的记录格式为(整数，序号)，例如(3, 2)表示关键字值为3，输入序号为2的记录；
3、算法要具有较好的健壮性，对错误操作要做适当处理。
四、程序实现：
(1)实现顺序查找表和折半查找表：
#include<stdio.h>
#define MAX_LENGTH 100
typedef struct
{
int key[MAX_LENGTH];
int length;
}stable;
int seqserch(stable ST,int key,int &count)
{
int i;
for(i=ST.length;i>0;i--)
{
count++;
if(ST.key[i]==key)
return i;
}
return 0;
}
int binserch(stable ST,int key,int &count)
{
int low=1,high=ST.length,mid;
while(low<=high)
{
count++;
mid=(low+high)/2;
if(ST.key[mid]==key)
return mid;
else if(key<ST.key[mid])
high=mid-1;
else
low=mid+1;
}
return 0;
} main()
{
stable ST1;
int
a,b,k,x,count1=0,count2=0,temp=0;
ST1.length=0;
printf("请按从小到大的顺序输入查找表数据：(-1代表结束！)\n");
for(a=0;a<MAX_LENGTH;a++)
{
scanf("%d",&temp);
if(temp!=-1)
{
ST1.key[a]=temp;
ST1.length++;
}
else
break;
}
printf("输入数据为：\n");
for(b=0;b<ST1.length;b++)
{
printf("%d ",ST1.key[b]);
}
printf("\n请输入要查找的数据：");
scanf("%d",&k);
a=seqserch(ST1,k,count1)+1;
printf("\n顺序查找：该数据的位置在第：%d个\n",a);
printf("查找次数为：%d\n\n",count1-1);
a=binserch(ST1,k,count2)+1;
printf("折半查找：该数据的位置在第：%d个\n",a);
printf("查找次数为：%d\n",count2-1);
}
（2）二叉排序树的查找：
#include<stdio.h> #include<malloc.h> typedef struct node {
int data;
int key;
struct node *left,*right;
}bitnode,*bittree;
void serchbst(bittree T,bittree *F,bittree *C,int data)
{
while(T!=NULL)
{
if(T->data==data)
{
*C=T;
break;
}
else if(data<T->data)
{
*F=T;
T=T->left;
}
else
{
*F=T;
T=T->right;
}
}
return 0;
}
int insertbst(bittree *T,int key,int data) {
bittree F=NULL,C=NULL,s;
serchbst(*T,&F,&C,data);
if(C!=NULL) return 0;
s=(bittree)malloc(sizeof(bitnode));
s->data=data;
s->key=key;
s->left=s->right=NULL;
if(F==NULL) *T=s;
else if(data<F->data)
F->left=s;
else
F->right=s;
return 1; }
void creatbst(bittree *T)
{
int key,data;*T=NULL;
printf("请输入数据以构造二叉排序树：(数据格式为:m n (-1000,-1000)代表结束)\n");
scanf("%d%d",&key,&data);
while(key!=-1000 || data!=-1000)
{
insertbst(T,key,data);
scanf("%d%d",&key,&data);
}
}
void midTraverse(bittree T)
{
if(T!=NULL)
{
midTraverse(T->left);
printf("(%d,%d)
",T->key,T->data);
midTraverse(T->right);
}
}
main()
{
bittree
T=NULL,C=NULL,F=NULL;
int key,data,temp;
creatbst(&T);
printf("此二叉树的中序序列为：");
midTraverse(T);
printf("\n请输入要查找的关键字：");
scanf("%d",&data);
serchbst(T,&F,&C,data);
printf("此关键字的数据为：%d\n",C->key);
}
五、实现结果：
(1)顺序查找和折半查找：
(2)二叉树排序树查找：
六、实验之心得体会：
（1）在这次实验中，我基本上掌握了顺序查找、折半查找和二叉排序树查找的基本思想和实现方法，让我体会到了写程序时，不仅要考虑是否能够调试出结果，还要考虑程序实现的效率，这是一个编程人员必须要具备的一项总要的素质。
（2）通过这次实验，让我体会到同样的数据在不同的查询方法下有着不同的查询效率，就拿实验一来说，用顺序查找法在12个数据中查找一个关键字需要的查找的次数为8次，但是，如果折半查找法却只要两次，由此可以看出，我们在查找时不仅要考虑查找的实现，还要考虑查找的效率和查找所用的时间。
（3）用二叉排序树查找效率也比较高，只要你输入相应的关键字，就可已找到所需要的数据，就我个人看来，用二叉排序树的效率要比顺序查找和折半查找的效率更高，查询的速度更快。
