顺序表按值查找算法Locate

c语言中常用的查找C语言中常用的查找引言：在编程中，查找是一项非常常见且重要的操作。

无论是在数组、链表、树还是图等数据结构中，都需要进行查找操作来寻找特定的数据或者确定某个元素的存在与否。

C语言提供了多种查找算法和数据结构，本文将介绍C语言中常用的查找方法。

一、线性查找线性查找是最简单的查找方法之一，也称为顺序查找。

其基本思想是从数据集合的起始位置开始逐个比较待查找元素与集合中的元素，直到找到目标元素或者遍历完整个集合。

在C语言中，可以使用for循环或者while循环实现线性查找。

线性查找的时间复杂度为O(n)，其中n为数据集合中元素的个数。

二、二分查找二分查找又称为折半查找，是一种高效的查找算法，但要求数据集合必须是有序的。

其基本思想是将数据集合分为两部分，然后通过与目标元素的比较来确定目标元素在哪个部分中，从而缩小查找范围。

重复这个过程直到找到目标元素或者确定目标元素不存在于数据集合中。

二分查找的时间复杂度为O(logn)，其中n为数据集合中元素的个数。

三、哈希表查找哈希表是一种通过哈希函数将关键字映射到存储位置的数据结构，它能够以常数时间复杂度O(1)进行查找操作。

在C语言中，可以使用数组和链表的结合来实现哈希表。

哈希表的关键之处在于哈希函数的设计，良好的哈希函数能够将关键字均匀地映射到不同的存储位置，从而提高查找效率。

四、二叉搜索树查找二叉搜索树是一种常用的数据结构，它满足以下性质：对于任意节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。

在C语言中，可以使用指针和递归的方式来实现二叉搜索树。

通过比较目标值与当前节点的值，可以确定目标值位于左子树还是右子树中，从而缩小查找范围。

五、图的遍历在图的数据结构中，查找操作通常是指遍历操作。

图的遍历有两种方式：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索通过递归的方式依次访问图中的每个节点，直到找到目标节点或者遍历完整个图。

顺序表顺序表声明顺序表类型#define MaxSize 100typedef int ElemType;//假设顺序表中的元素类型typedef struct{ElemType data[MaxSize];//存放元素int length;//长度}SqList;//类型⼀、顺序表的基本运算⽅法1、初始化void InitList(SqList &L)2、销毁void DestroyList(SqList L)3、求长度int GetLength(SqList L)4、求第i个元素int GetElem(SqList L,int i,ElemType &e)5、按值查找int Locate(SqList L,ElemType x)6、插⼊int InsElem(SqList &L,ElemType x,int i)7、删除int DelElem(SqList &L,int i)8、输出void DispList(SqList L)9、判读是否为空bool ListEmpty(SqList L)//判断顺序表是否为空{return(L.length==0);}int GetLength(SqList L){return L.length;}SqList.cpp#include <stdio.h>#define MaxSize 100typedef int ElemType; //假设顺序表中所有元素为int类型typedef struct{ ElemType data[MaxSize]; //存放顺序表的元素int length; //顺序表的实际长度} SqList; //顺序表类型void InitList(SqList &L) //由于L要回传给值参，所以⽤引⽤类型{L.length=0;}void DestroyList(SqList L){}bool ListEmpty(SqList L)//判断顺序表是否为空{return(L.length==0);}int GetLength(SqList L){return L.length;}int GetElem(SqList L,int i,ElemType &e){ if (i<1 || i>L.length) //⽆效的i值return 0;else{ e=L.data[i-1];return 1;}}int Locate(SqList L,ElemType x){ int i=0;while (i<L.length && L.data[i]!=x)i++; //查找值为x的第1个元素,查找范围为0～L.length-1if (i>=L.length) return(0); //未找到返回0else return(i+1); //找到后返回其逻辑序号}int InsElem(SqList &L,ElemType x,int i){ int j;if (i<1 || i>L.length+1) //⽆效的参数ireturn 0;for (j=L.length;j>i;j--) //将位置为i的结点及之后的结点后移L.data[j]=L.data[j-1];L.data[i-1]=x; //在位置i处放⼊xL.length++; //线性表长度增1return 1;}int DelElem(SqList &L,int i){ int j;if (i<1 || i>L.length) //⽆效的参数ireturn 0;for (j=i;j<L.length;j++) //将位置为i的结点之后的结点前移L.data[j-1]=L.data[j];L.length--; //线性表长度减1return 1;}void DispList(SqList L){ int i;for (i=0;i<L.length;i++)printf("%d ",L.data[i]);printf("\n");}⼆、实验题⽬：设计⼀个程序sy1_main.cpp，并完成如下功能。

实验一顺序表操作验证一、实验目的⑴掌握线性表的顺序存储结构；⑵验证顺序表及其基本操作的实现；⑶掌握数据结构及算法的程序实现的基本方法。

二、实验内容⑴建立含有若干个元素的顺序表；⑵对已建立的顺序表实现插入、删除、查找等基本操作。

三、设计与编码(a)本实验用到的理论知识首先定义顺序表的数据类型——顺序表类SeqList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。

(b)算法设计const int MaxSize=10;template <class T> //定义模板类SeqListclass SeqList{public:SeqList( ){length=0;} //无参构造函数SeqList(T a[ ], int n);//有参构造函数-可编辑修改-void Insert(int i, T x); //在线性表中第i个位置插入值为x的元素T Delete(int i); //删除线性表的第i个元素int Locate(T x ); //按值查找，求线性表中值为x的元素序号void PrintList( ); //遍历线性表，按序号依次输出各元素private:T data[MaxSize]; //存放数据元素的数组int length; //线性表的长度};其次，建立含有n个数据元素的顺序表，即设计构造函数。

算法如下：顺序表有参构造函数SeqListtemplate <class T>SeqList:: SeqList(T a[ ], int n){if (n>MaxSize) throw "参数非法";for (i=0; i<n; i++)data[i]=a[i];length=n;}最后，对建立的顺序表设计插入、删除、查找等基本操作的算法。

⑴插入算法顺序表插入算法Inserttemplate <class T>void SeqList::Insert(int i, T x){if (length>=MaxSize) throw "上溢";if (i<1 | | i>length+1) throw "位置";for (j=length; j>=i; j--)data[j]=data[j-1]; //注意第j个元素存在数组下标为j-1处data[i-1]=x;length++;}-可编辑修改- ⑵删除算法⑶查找算法template <class T>T SeqList::Delete (int i ){if (length==0) throw "下溢";if (i<1 | | i>length ) throw "位置";x=data[i -1];for (j=i; j<length; j++)data[j-1]=data[j];//注意此处j 已经是元素所在的数组下标length--;return x;}顺序表删除算法Deletetemplate <class T>int SeqList::Locate (T x ){for (i=0; i<length; i++)if (data[i]==x ) return i+1; //下标为i 的元素等于x ，返回其序号i+1return 0;//退出循环，说明查找失败}顺序表按值查找算法Locate(c)编码#include<iostream>#include<stdlib.h>using namespace std;const int MaxSize=50;class SeqList{public:SeqList(){length=0;}SeqList(char a[],int n){if(n>MaxSize)throw"参数非法";for(int i=0;i<n;i++)data[i]=a[i];length=n;}~SeqList(){}int Length(){return length;}char Get(int i){if(i<1&&i>length)throw"查找位置非法"; else return data[i-1];}int Locate(char x){for(int i=0;i<length;i++)if(data[i]==x)return i+1;return 0;}void Insert(int i,char x){if(length>=MaxSize)throw"上溢";if(i<1||i>length+1)throw"位置";for(int j=length;j>=i;j--)data[j]=data[j-1];data[i-1]=x;length++;-可编辑修改-}char Delete(int i){if(length==0) throw "下溢";if (i<1||i>length) throw "位置";char x=data[i-1];for (int j=i; j<length; j++)data[j-1]=data[j];length--;return x;}void PrintList(){for(int i=0;i<length;i++)cout<<data[i]<<endl;}private:char data[MaxSize];int length;};void main(){int xh1,xh2,xh3;char x[10],xm1,xm2;cout<<"输入需要记录的数据："<<endl;for(int i=0;i<10;i++){cin>>x[i];}SeqList studentx(x,10);cout<<"表长为："<<studentx.Length()<<endl;cout<<"输入数据位置：";cin>>xh1;cout<<"查找的数据为："<<studentx.Get(xh1)<<endl;cout<<"输入需要查找的数据：";cin>>xm1;cout<<"该数据位置为："<<studentx.Locate(xm1)<<endl;cout<<"添加数据，输入位置：";cin>>xh2;cout<<"输入数据：";cin>>xm2;-可编辑修改-studentx.Insert(xh2,xm2);cout<<"删除数据，输入位置：";cin>>xh3;cout<<"删除结果为："<<studentx.Delete(xh3)<<endl;cout<<"输出数据："<<endl;studentx.PrintList();}五、运行与调试(a)在调试程序的过程中遇到什么问题，是如何解决的？数据类型定义错误，将int改为char解决。

顺序查找算法是一种用来查找指定的特定值在一个数组里的搜索算法。

它从一端到另一端开始寻找，直到命中要查找的值，然后返回其中的
位置。

顺序查找也被称为线性查找，它的基本思想是将要查找的目标
和数组中的每一个元素一个个比较，直到找到那个特定的值，然后返
回其在数组中的位置，如果没有找到，则返回 -1 。

顺序查找算法的时间复杂度为O(n)，即需要对每一个元素都进行一次
查找，所以如果数组中有n个元素，则查找算法需要n次比较才能找
到目标元素。

因此，该查找算法时间复杂度为O(n)。

顺序查找算法的优点在于数据结构的要求非常少，只要将数组的元素
组织成线性次序，都可以构成该算法。

因为没有额外的数据结构消耗
存储空间，实现也很简单，因此也是一种非常受欢迎的搜索算法。

缺点是查询性能不是很高，时间复杂度高，即使待查找的值非常少量，但其运行时间也是相当的。

另外，它的存储数据的顺序比较严格，往
往需要先对数组元素进行排序，才能实现顺序查找。

总的来说，顺序查找算法是一种传统的基本的搜索算法，它的实现简单，存储数据的要求也很少，但是时间复杂度较高，查询效率不高。

在实际应用中，顺序查找算法适用于查找表中元素相对较少，或者查
找表本身就接近有序，而查找表中元素较多或无序时，顺序查找可能
会耗费大量的时间，并不太实用。

1.顺序表的定义、取值、查找、插入、删除的基本运算顺序表是一种数据结构，通过数组的形式存储和组织数据。

顺序表中的元素在内存中是连续存储的，元素之间的顺序是由其在数组中的位置决定的。

1. 定义顺序表：顺序表可以通过定义一个数组和一个变量来表示。

数组用于存储元素，变量用于记录顺序表的长度。

例如，一个顺序表可以定义如下：```const int MAX_SIZE = 100; // 假设顺序表最大长度为100struct SeqList {int data[MAX_SIZE]; // 数组用于存储元素int length; // 记录顺序表的长度};```2. 取值：可以通过索引来访问顺序表中的元素。

索引从0开始，从左到右逐个增加。

例如，要访问第i个元素，可以使用`seqList.data[i]`来获取。

3. 查找：要查找顺序表中的某个元素，可以遍历顺序表，逐个比较元素的值与目标值是否相等。

如果找到了目标值，则返回该元素的索引；如果没有找到，则返回-1表示未找到。

```int search(SeqList seqList, int target) {for (int i = 0; i < seqList.length; i++) {if (seqList.data[i] == target) {return i; // 找到目标值，返回索引}}return -1; // 未找到目标值}```4. 插入：要在顺序表中插入一个元素，需要将插入位置之后的元素向后移动，然后将新元素插入到指定位置。

```bool insert(SeqList &seqList, int index, int value) {// 检查插入位置是否有效if (index < 0 || index > seqList.length) {return false; // 插入位置无效，插入失败}// 将插入位置之后的元素向后移动for (int i = seqList.length - 1; i >= index; i--) {seqList.data[i + 1] = seqList.data[i];}// 插入新元素seqList.data[index] = value;// 更新顺序表的长度seqList.length++;return true; // 插入成功}```5. 删除：要删除顺序表中的一个元素，需要将删除位置之后的元素向前移动，然后将顺序表的长度减1。

消除递归不一定需要使用栈。

答案:正确在开散列表中不会出现堆积现象。

答案:正确在链栈上进行进栈操作时，不需判断栈满。

答案:正确算法的正确性，一般不进行形式化的证明，而是用测试来验证。

答案:正确顺序表不需存放指针，链表要存放指针，故链表的存储空间要求总是比顺序表大。

答案:错误如果n个顶点的无向图有n条边，则图中肯定有回路。

答案:正确图G的生成树T是G的子图。

答案:正确数组的基本运算有读、写、插入、删除等。

答案:错误不管树的深度和形态如何，也不可能构造出一棵有100个结点的哈夫曼树。

答案:正确如果根结点的左子树和右子树高度差不超过1，则该二叉树是平衡二叉树。

答案:错误排序的目的是为了方便以后的查找。

答案:正确以中序方式遍历一个堆，则得到一个有序序列。

答案:正确二叉树中可能所有结点的度都小于2。

答案:正确顺序表可以按序号随机存取。

答案:正确在二叉排序树中，即使删除一个结点后马上再插入该结点，该二叉排序树的形态也可能不同。

答案:正确队列在使用中必须设置两个指针，分别指向真正的队头和队尾的位置。

答案:错误数据的逻辑结构和运算集组成问题的数学模型，与计算机无关。

对称矩阵压缩存储后仍然可以随机存取。

答案:正确有向图中顶点i的出度等于邻接矩阵中第i行中1的个数；入度等于第i列中1的个数。

答案:错误树和森林都可转化为二叉树，故对给定的二叉树，不能区分是由树还是森林转换来的。

答案:错误循环队列中入队和出队的节点位置可出现在数组的任一端，已不满足“一端进另一端出”的要求，故实际上已不是队列了。

答案:错误顺序查找法不仅可用于顺序表上的查找，也可用于链表上的查找。

答案:正确有向图中边数等于邻接矩阵中1的个数；也等于邻接表中的边表结点数。

答案:正确直接插入排序是稳定的，而Shell排序就是调用若干趟直接插入排序，故也是稳定的。

答案:错误基数排序不需进行关键字间的比较，故执行时间比基于比较的排序方法要快。

答案:错误由二叉树的先根和后根序列可以唯一确定该二叉树。

顺序表的定位算法
顺序表是一种常用的数据结构，它能够快速地存储和处理数据。

在使用顺序表时，我们经常需要进行定位操作，即根据元素的值或下标，快速地找到该元素在顺序表中的位置。

针对不同的定位需求，顺序表有不同的定位算法。

顺序表的按值定位算法是最常见的一种算法。

该算法要求顺序表中的元素必须是有序的，否则无法进行二分查找。

在使用按值定位算法时，我们首先将顺序表中的元素按照从小到大的顺序排列，然后通过比较查找值与中间元素的大小关系，来缩小查找范围，最终找到目标元素的位置。

与按值定位算法不同的是，按下标定位算法不要求顺序表中的元素有序。

该算法通过对目标下标进行简单的数学计算，即将目标下标与顺序表的起始地址相加，来得到目标元素的地址。

这种算法通常用于需要快速访问顺序表中某个位置的情况。

除了按值和按下标定位算法外，顺序表还有一种特殊的定位算法，即分块定位算法。

该算法将顺序表分成若干块，并对每个块进行内部排序。

通过对块的查找，可以快速定位到目标元素所在的块，并在块内部查找目标元素。

这种算法适用于顺序表中元素较多的情况，可以快速地定位到目标元素。

总之，顺序表的定位算法是数据结构中非常重要的一部分，不同的算法适用于不同的情况。

在使用顺序表时，我们需要根据具体的需求选择合适的算法，并注意算法的时间复杂度和空间复杂度。

顺序表的查找-顺序查找查找（search）：给定结点的关键字值 x ，查找值等于 x 的结点的存储地址。

按关键字 x 查：①成功，表中有 x ，返回 x 的存储地址；②不成功，x 不在表中，返回⽆效地址。

顺序查找就是以表的⼀端为起点，向另⼀个端点逐个元素查看，可以是从表头→表尾的顺序，也可以是从表尾→表头的顺序顺序查找⽅法，既适⽤于⽆序表，⼜适⽤于有序表。

顺序查找属于 “穷尽式搜索法”：通常以查找长度，度量查找算法的时间复杂性。

查找长度：即查找过程中测试的节点数⽬。

顺序查找的查找长度 = for 循环体的执⾏次数，最⼩为1，最多为n。

等概率下：平均查找长度 = （n + 1）/ 2最坏情况和平均情况：T（n）= O（n）效率最低的查找算法我们观察⼀下上图那两个 for循环体，不难发现，每次执⾏都需要判断两个条件：①测试是否循环到头；②测试是否找到元素 x。

因此我们不妨使⽤ “监督元” 技术，不仅简化了程序结构，也提⾼了查找速度。

若从表尾→表头的顺序查找，监督元则在表头处，称为 “表头监督元”，如下图：若从表头→表尾的顺序查找，监督元则在表头处，称为 “表尾监督元”，如下图：带表头监督元的顺序查找算法：int SQsearch（int a[]，int x，int n）{ // SQsearch 是函数名，仅此。

int i； i = n； a[0] = x； while（a[i] != x） i -- ； return i；}算法思想：① i = n；// 设置查找起点② a[0] = x；// 放置监督元，因为在进⼊循环体之前，已经预先在 a[0] 放置了⼀个元素 x，所以 x ⽆论是否真的在表中，总能找到 x ，使第三句的循环中⽌。

注意a[1] 到 a[n] 存储的才是真正的表元素。

如果 x 真存在表中，必然在某个 i ⼤于 0 时找到 x，循环终⽌。

如果循环变量 i 的值变到 0 时循环才终⽌，那就说明 x 不在表中。