查找-顺序查找-蒲公英云

查找-顺序查找

野性酷女 2022-05-13 07:28 277阅读 0赞

顺序查找的思路：

从数据的第一个元素开始，依次将扫描到的关键字和给定值key比较。若当前扫描到的关键字和key相等，则查找成功；若扫描结束还没有找到和key相等的元素，就表示查找给定的值不在表中。

时间复杂度：

O(n).

优点：

1.算法简单

2.对表结构没有任何要求，用顺序表或者用链表都可以。

3.表中元素之间是否有序，仍然可适用。

例子：查找数组{3,6,2,10,1,8,5,7,4,9}中的关键字为5的元素位置

查找过程演示图：

算法例子：

（1）顺序表顺序查找-结构体数组：

#include<stdio.h>
#define MAXL 100
typedef struct
{
    int key;
}Table;
typedef Table SeqList[MAXL];
int SeqSearch(SeqList r,int n,int key2)
{
    int i=0;
    while(i<n && r[i].key!=key2)
    {
        i++;
    }
    if(i>=n)
        return -1;
    else
    {
        return i;
    }
}
void main()
{
    SeqList r;
    int n=10,i;
    int key3=5;
    int a[]={3,6,2,10,1,8,5,7,4,9};
    for(i=0;i<n;i++)
    {
        r[i].key=a[i];
    }
    if((i=SeqSearch(r,n,key3))!=-1)
    {
        printf("%d元素的位置：%d\n",key3,i);
    }
    else
        printf("该元素不在表中",key3);
}

（2）顺序表顺序查找-数组1：

#include<stdio.h>
int  SeqSearch(int *a,int lengh,int key)
{
    for(int i = 0 ; i < lengh ; i++)
    {
        if(a[i] == key)
            return i;
    }
    return -1;
}
void main()
{
    int arr[] = {3,6,2,10,1,8,5,7,4,9};
    int result, num =5;
    result = SeqSearch(arr,sizeof(arr),num);
    if(result == -1)
        printf("该元素不在表中");
    else
        printf("%d元素的位置：%d\n",num,result);
}

（3）顺序表顺序查找-数组2：

#include<stdio.h>
int SeqSearch(int a[],int value)
{
    for(int i=0;i<sizeof(a);i++)
    {
        if(a[i]==value)
            return i;
    }
    return -1;
}
void main()
{
    int a[]={3,6,2,10,1,8,5,7,4,9};
    int value=5;
    int i;
    if(i=(SeqSearch(a,value))!=-1)
        printf("%d元素的位置：%d",value,i);
}

（4）链表顺序查找

#include<stdio.h>
#include<malloc.h>
typedef struct ListNode
{
    int key;
    ListNode* nextNode;
}ListNodeTable;
//创建链表
void InitList(ListNodeTable *&l)
{
    l=(ListNodeTable*)malloc(sizeof(ListNodeTable));
    l->nextNode=NULL;
}
//链表插入元素
bool ListInsert(ListNodeTable *&l,int n,int keyvalue)
{
    int i=0;
    ListNodeTable *p=l,*templist;
    while(i<n-1&&p!=NULL)
    {
        i++;
        p=p->nextNode;
    }
    if(p==NULL)
    {
        return false;
    }
    else
    {
        templist=(ListNodeTable*)malloc(sizeof(ListNodeTable));
        templist->key=keyvalue;
        templist->nextNode=p->nextNode;
        p->nextNode=templist;
        return true;
    }
}
//顺序查找
int seqsearch(ListNodeTable *l,int key)
{
    int i=1;
    ListNodeTable *p=l->nextNode;
    while(p!=NULL&&p->key!=key)
    {
        p=p->nextNode;
        i++;
    }
    if(p==NULL)
    {
        printf("该元素不存在表中");
        return -1;
    }    
    else
        return i;
}
void main()
{
    ListNodeTable *l;
    int key;
    InitList(l);
    int n=10;
    int a[]={3,6,2,10,1,8,5,7,4,9};
    int j;
    for(int i=1;i<=n;i++)
    {
        ListInsert(l,i,a[i-1]);
    }
    if((j=seqsearch(l,5))!=-1)
    {
        printf("5元素的位置：%d\n",j);
    }    
}