顺序表查找算法

实现顺序表的各种基本运算的算法顺序表是一种基本的数据结构，它可以存储线性结构，支持随机访问，具有较好的存储效率。

在实际应用中，我们需要实现顺序表的各种基本运算，包括插入、删除、查找、遍历、排序等操作。

下面介绍一些实现顺序表基本运算的算法。

1.插入算法顺序表插入算法的基本思路是：将插入位置之后的所有元素向后移动一位，然后将待插入元素放入插入位置。

具体实现如下：```void Insert(SqList &L, int pos, int data){if (pos < 1 || pos > L.length + 1) // 插入位置非法return;if (L.length == L.MAXSIZE) // 顺序表已满return;for (int i = L.length; i >= pos; i--) // 将pos以后的元素依次后移，腾出pos位置L.data[i] = L.data[i - 1];L.data[pos - 1] = data; // 将新元素插入pos位置L.length++; // 顺序表长度+1}```2.删除算法顺序表删除算法的基本思路是：将待删除元素之后的所有元素向前移动一位，然后将顺序表长度减1。

具体实现如下：```void Delete(SqList &L, int pos){if (pos < 1 || pos > L.length) // 删除位置非法return;for (int i = pos; i < L.length; i++) // 将pos以后的元素依次前移，覆盖pos位置L.data[i - 1] = L.data[i];L.length--; // 顺序表长度-1}```3.查找算法顺序表查找算法的基本思路是：从表头开始逐个比较元素，直到找到目标元素或者搜索到表尾。

具体实现如下：```int Search(SqList L, int data){for (int i = 0; i < L.length; i++){if (L.data[i] == data) // 找到目标元素，返回其下标return i;}return -1; // 未找到目标元素，返回-1}```4.遍历算法顺序表遍历算法的基本思路是：从表头开始依次输出元素。

顺序查找的思路顺序查找是指从一个有序表或者无序表中，一个个地去查找给定的关键字，把符合条件的关键字找出来的一种方法。

它是最简单也是最基本的一种查找算法，是一种只要能够比较和排序的查找算法。

顺序查找的思路就是：从表的第一个元素开始，依次与给定的关键字比较，若比较成功，则表示找到了要查找的关键字；若比较失败，则比较下一个元素；如此反复，直到把表中所有元素都比较一遍为止，这样就完成了顺序查找。

顺序查找的优缺点优点：1、顺序查找是基于比较的查找方法，能够支持任意的数据类型，并且不依赖于数据的存储结构；2、实现起来比较简单，查找的效率也比较高；3、它能够用在无序和有序的表中。

缺点：1、查找效率是随着表的长度而增加的，当表的长度增加，查找的时间就会越长；2、对于大规模的表来说，它效率低，比较次数较多，查找速度也较慢；3、顺序表需要较多的存储空间。

顺序查找的实现1、首先要明确要查询的关键字，然后从顺序表的第一个元素开始；2、比较每一个元素与关键字是否相同，若相同则找到了要查找的关键字；3、若不相同，则将当前元素放到下一个元素进行比较，如此循环比较；4、如果顺序表的元素都比较完，却没有找到要查找的关键字，则表示查找失败，结束查找。

顺序查找的应用1、在编程语言中，我们经常用顺序查找来查找字符串；2、在数据库系统中，也会使用顺序查找来查找特定的数据；3、在文件搜索器中，也可以使用顺序查找来搜索文件；4、在编译器中，编译器会使用顺序查找来查找关键字；5、在网络资源中，也可以使用顺序查找来搜索想要的资源。

总结顺序查找是指一次比较一个元素，然后依次比较下一个元素，直到顺序表的所有元素都比较完为止，也就是要比较整张表。

它是一种简单易实现的查找算法，能够适用于无序和有序的表中，但是由于其时间复杂度较高，在大规模的表中查找效率不高，因此开发人员不会选择它。

因此，在开发实际应用程序时，应该根据实际的情况，根据需要使用不同的查找算法，以便更好地提升查找的效率。

实验五查找的应用一、实验目的：1、掌握各种查找方法及适用场合，并能在解决实际问题时灵活应用。

2、增强上机编程调试能力。

二、问题描述1.分别利用顺序查找和折半查找方法完成查找。

有序表（3,4,5,7,24,30,42,54,63,72,87,95）输入示例：请输入查找元素：52输出示例：顺序查找：第一次比较元素95第二次比较元素87 ……..查找成功，i=**/查找失败折半查找：第一次比较元素30第二次比较元素63 …..2.利用序列（12,7,17,11,16,2,13,9,21,4）建立二叉排序树，并完成指定元素的查询。

输入输出示例同题1的要求。

三、数据结构设计（选用的数据逻辑结构和存储结构实现形式说明）（1）逻辑结构设计顺序查找和折半查找采用线性表的结构，二叉排序树的查找则是建立一棵二叉树，采用的非线性逻辑结构。

（2）存储结构设计采用顺序存储的结构，开辟一块空间用于存放元素。

（3）存储结构形式说明分别建立查找关键字，顺序表数据和二叉树数据的结构体进行存储数据四、算法设计（1）算法列表（说明各个函数的名称，作用，完成什么操作）序号 名称 函数表示符 操作说明1 顺序查找 Search_Seq 在顺序表中顺序查找关键字的数据元素2 折半查找 Search_Bin 在顺序表中折半查找关键字的数据元素3 初始化 Init 对顺序表进行初始化，并输入元素4 树初始化 CreateBST 创建一棵二叉排序树5 插入 InsertBST 将输入元素插入到二叉排序树中6 查找 SearchBST在根指针所指二叉排序树中递归查找关键字数据元素 （2）各函数间调用关系（画出函数之间调用关系）typedef struct { ElemType *R; int length;}SSTable;typedef struct BSTNode{Elem data; //结点数据域 BSTNode *lchild,*rchild; //左右孩子指针}BSTNode,*BSTree; typedef struct Elem{ int key; }Elem;typedef struct {int key;//关键字域}ElemType;（3）算法描述int Search_Seq(SSTable ST, int key){//在顺序表ST中顺序查找其关键字等于key的数据元素。

实现顺序表的各种基本运算的算法
1.初始化顺序表：首先需要定义一个数组来存储顺序表中的元素，在初始化顺序表时，需要给定顺序表的大小，即可创建一个空的顺序表。

2. 插入元素：要在顺序表中插入一个元素，需要确定插入位置
和插入元素的值。

插入元素时，需要将插入位置后面的元素都向后移动一位，然后将插入元素插入到插入位置。

3. 删除元素：要从顺序表中删除一个元素，需要确定删除位置。

删除元素时，需要将删除位置后面的元素都向前移动一位，然后将最后一个元素移到删除位置处，即可完成删除操作。

4. 查找元素：要在顺序表中查找一个元素，可以使用顺序查找
或者二分查找算法。

顺序查找需要遍历整个顺序表，而二分查找需要先对顺序表进行排序，然后再进行查找。

5. 修改元素：要修改顺序表中的一个元素，需要先查找到该元
素的位置，然后再进行修改操作。

6. 获取顺序表长度：顺序表的长度就是顺序表中元素的个数，
可以通过遍历整个顺序表来获取其长度。

7. 清空顺序表：清空顺序表就是将顺序表中的元素全部删除，
可以通过遍历整个顺序表进行删除操作来实现。

8. 销毁顺序表：销毁顺序表就是释放顺序表所占用的内存空间，可以通过调用系统函数来实现。

以上就是实现顺序表的各种基本运算的算法。

实现顺序表的各种基本运算的算法1. 初始化顺序表算法实现：初始化操作就是将顺序表中所有元素的值设置为默认值，对于数值类型，可以将其设置为0，对于字符类型，可以将其设置为空格字符。

初始化的时间复杂度为O(n)，其中n为顺序表的长度。

2. 插入操作算法实现：顺序表的插入操作就是在指定位置上插入一个元素，需要将该位置后面的元素全部后移，在指定位置上插入新元素。

若顺序表已满，则需要进行扩容操作，将顺序表长度扩大一倍或者按一定的比例扩大。

插入操作的时间复杂度为O(n)，其中n为顺序表长度。

3. 删除操作算法实现：顺序表的删除操作需要将指定位置上的元素删除，并将该位置后面的元素全部前移。

删除操作后，如果顺序表的实际长度小于等于其总长度的1/4，则需要进行缩容操作，将顺序表长度缩小一倍或者按一定的比例缩小。

删除操作的时间复杂度为O(n)，其中n为顺序表长度。

4. 修改操作算法实现：顺序表的修改操作就是将指定位置上的元素赋予新的值。

修改操作的时间复杂度为O(1)。

5. 查找操作算法实现：顺序表的查找操作就是在顺序表中找到指定位置的元素，并返回其值。

查找操作的时间复杂度为O(1)。

6. 遍历操作算法实现：顺序表的遍历操作就是依次访问顺序表中的每个元素，遍历操作的时间复杂度为O(n)，其中n为顺序表的长度。

7. 合并操作算法实现：顺序表的合并操作就是将两个顺序表合并成一个新的顺序表，新的顺序表的长度为两个顺序表的长度之和。

合并操作的时间复杂度为O(n)，其中n为两个顺序表的长度之和。

总结：顺序表是一种简单而高效的数据结构，其基本运算包括初始化、插入、删除、修改、查找、遍历和合并等操作。

其中，插入、删除、遍历和合并操作的时间复杂度比较高，需要进行相应的优化处理。

同时，在实际应用中，还需要注意顺序表的扩容和缩容操作，避免造成资源浪费或者性能下降。

数据结构顺序查找与折半查找1，顺序查找顺序查找⼜称线性查找，它对顺序表和链表都适⽤。

（1）以下给出相关函数1 typedef struct{2 ElemType *elem; //元素存储空间地址，建表时按实际长度分配，0号单元留空3int TableLen; //表的长度4 }SSTable;5int Search_Seq(SSTable ST,ElemType key)6 {7 ST.elem[0]=key; //把要查找的关键字放在0号位置，称“哨兵”8for(int i=ST.TableLen;ST.elem!=key;i--) //从后往前找9 {10return i; //若表中不存在关键字为key的元素，将查找i=0时退出循环11 }12 }在上述算法中，将ST.elem[0]称为“哨兵”。

引⼊它的⽬的是使得Search_Seq内的循环不必判断数组是否会越界。

因为满⾜i=0时，循环⼀定会跳出。

除此之外，引⼊“哨兵”可以避免很多不必要的判断语句，从⽽提⾼算法的执⾏效率。

（2）算法效率分析当每个元素查找概率相同时，平均查找长度ASL=（n+1)/2, 查找不成功时，需要⽐较整个顺序表，所以⽐较次数时（n+1)次，从⽽顺序查找不成功的平均查找长度为(n+1)。

2.有序表的顺序查找（假设从⼩到⼤排列）有序表的顺序查找成功的平均查找长度与⼀般的线性表⼀样，即（n+1)/2.当查找失败时，待查找的元素为key,当查找第i个元素时，发现第i个元素的对应的关键字⼩于key,但第i+1个元素对应的关键字⼤于key,这时就可以返回查找失败的信息。

查找失败的平均查找长度为ASL=n/2+n/(n+1).3.折半查找前提：折半查找仅适⽤于有序的顺序表。

折半查找原理：将给定的key与中间元素⽐较，直到查到要找的元素。

以下是相关函数1int Binary_Search(SeqList L,ElemType key){2int low=0,high=L.TableLen-1,mid;//low指向表头，high指向表尾，mid中间值3while(low<=high)4 {5 mid=(low+high)/2;6if(L.elem[mid]==key) //中间值等于要查找元素7return mid;8else if(L.elem[mid]<key) //要查找元素在中间值右边9 low=mid+1;10else11 hign=mid-1; //要查找元素在中间值左边12 }13 }查找成功的时间复杂度为log2n，平均情况下⽐顺序查找效率⾼⼀些。

元素之后的所有数据都前移一个位置，最将线性表长减1。

3．顺序表查找操作的基本步骤：要在顺序表中查找一个给定值的数据元素则可以采用顺序查找的方法，从表中第 1 个数据元素开始依次将值与给定值进行比较，若相等则返回该数据元素在顺序表中的位置，否则返回0 值。

线性表的动态分配顺序存储结构—C语言实现#define MaxSize 50//存储空间的分配量Typedef char ElemType；Typedef struct{ElemType data[MaxSize];int length; //表长度（表中有多少个元素）}SqList;动态创建一个空顺序表的算法：void InitList(SqList *&L) //初始化线性表{L=(SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间L->length=0; //置空线性表长度为0}线性表的插入：status Sqlist_insert(Sqlist &L,int i,Elemtype x)/*在顺序表L中第i个元素前插入新元素x*/{ if (i<1||i>L.length+1) return ERROR; /*插入位置不正确则出错*/if (L.length>=MAXLEN)return OVERFLOW;/*顺序表L中已放满元素，再做插入操作则溢出*/for(j=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j]; /*将第i个元素及后续元素位置向后移一位*/L.elem[i-1]=x; /*在第i个元素位置处插入新元素x*/L.length++; /*顺序表L的长度加1*/return OK;}线性表的删除：status Sqlist_delete(Sqlist &L,int i,Elemtype &e)/*在顺序表L中删除第i个元素*{ if (i<1||i>L.length) return ERROR; /*删除位置不正确则出错*/for(j=i;j<=L.length-1;j++)L.elem[j-1]=L.elem[j]; /*将第i+1个元素及后继元素位置向前移一位*/L.length--;/*顺序表L的长度减1*/return OK；}线性表元素的查找：int LocateElem(SqList *L, ElemType e) //按元素值查找{int i=0;while (i<L->length && L->data[i]!=e)i++; //查找元素eif (i>=L->length) //未找到时返回0return 0;elsereturn i+1; //找到后返回其逻辑序号}输出线性表：void DispList(SqList *L) //输出线性表{int i;if (ListEmpty(L)) return;for (i=0;i<L->length;i++)printf("%c ",L->data[i]);printf("\n");}输出线性表第i个元素的值：bool GetElem(SqList *L,int i,ElemType &e)//求线性表中某个数据元素值{if (i<1 || i>L->length)return false; //参数错误时返回falsee=L->data[i-1]; //取元素值return true; //成功找到元素时返回true}代码：#include <stdio.h>#include <malloc.h>#define MaxSize 50typedef char ElemType;typedef struct{ElemType data[MaxSize];int length;} SqList;void InitList(SqList *&L);void DestroyList(SqList *L);bool ListEmpty(SqList *L);int ListLength(SqList *L);void DispList(SqList *L);bool GetElem(SqList *L,int i,ElemType &e);int LocateElem(SqList *L, ElemType e);bool ListInsert(SqList *&L,int i,ElemType e);bool ListDelete(SqList *&L,int i,ElemType &e);void InitList(SqList *&L)//初始化线性表{L=(SqList *)malloc(sizeof(SqList));//分配存放线性表的空间L->length=0;//置空线性表长度为0 }void DestroyList(SqList *L)//销毁线性表{free(L);}bool ListEmpty(SqList *L)//判线性表是否为空表{return(L->length==0);}int ListLength(SqList *L)//求线性表的长度{return(L->length);}void DispList(SqList *L)//输出线性表{int i;if (ListEmpty(L)) return;for (i=0;i<L->length;i++)printf("%c ",L->data[i]);printf("\n");}bool GetElem(SqList *L,int i,ElemType &e)//求线性表中某个数据元素值{if (i<1 || i>L->length)return false;//参数错误时返回falsee=L->data[i-1];//取元素值return true;//成功找到元素时返回true}int LocateElem(SqList *L, ElemType e)//按元素值查找{int i=0;while (i<L->length && L->data[i]!=e)i++;//查找元素eif (i>=L->length)//未找到时返回0return 0;elsereturn i+1;//找到后返回其逻辑序号}bool ListInsert(SqList *&L,int i,ElemType e)//插入数据元素{int j;if (i<1 || i>L->length+1)return false;//参数错误时返回falsei--;//将顺序表逻辑序号转化为物理序号for (j=L->length;j>i;j--)//将data[i]及后面元素后移一个位置L->data[j]=L->data[j-1];L->data[i]=e;//插入元素eL->length++;//顺序表长度增1return true;//成功插入返回true}bool ListDelete(SqList *&L,int i,ElemType &e)//删除数据元素{int j;if (i<1 || i>L->length)//参数错误时返回falsereturn false;i--;//将顺序表逻辑序号转化为物理序号e=L->data[i];for (j=i;j<L->length-1;j++)//将data[i]之后的元素前移一个位置L->data[j]=L->data[j+1];L->length--;//顺序表长度减1return true;//成功删除返回true}void main(){SqList *L;ElemType e;printf("顺序表的基本运算如下:\n");printf(" (1)初始化顺序表L\n");InitList(L);printf(" (2)依次采用尾插法插入a,b,c,d,e元素\n");ListInsert(L,1,'a');ListInsert(L,2,'b');ListInsert(L,3,'c');ListInsert(L,4,'d');ListInsert(L,5,'e');printf(" (3)输出顺序表L:");DispList(L);printf(" (4)顺序表L长度=%d\n",ListLength(L));printf(" (5)顺序表L为%s\n",(ListEmpty(L)?"空":"非空"));GetElem(L,3,e);printf(" (6)顺序表L的第3个元素=%c\n",e);实验结果：心得体会：通过本次实验，实现了数据结构在程序设计上的作用，了解了数据结构语言，加深了对c语言的认识掌并掌握了线性表的顺序存储结构的表示和实现方法，掌握顺序表基本操作的算法实现，同时了解了顺序表的应用。