顺序表的查找

顺序表的按位查找(时间复杂度：O(1))

GetElem(L,i)：按位查找操作，获取表L中第i个位置的元素的值

静态分配：

//顺序表的按位查找（静态分配）

#include <stdio.h>

#define MaxSize 10  //定义最大长度

typedef struct{
    int data[MaxSize];  //用静态的“数组”存放数据元素
    int length;  //顺序表的当前长度
}SqList;  //顺序表的类型定义

//基本操作：初始化一个顺序表
void InitList(SqList *L){
    for(int i=0;i<MaxSize;i++){
        L->data[i]=0;  //将所有数据元素设置为默认初始值
    }
    L->length=0;  //顺序表初始长度为0
}

int GetElem(SqList *L,int i){
    
    return L->data[i-1];
}

int main(){
    
    SqList L;  //声明一个顺序表
    InitList(&L);  //初始化顺序表
    
    //...此处插入几个元素
    
    int num=GetElem(&L, 3); //查找表L中第3个位置的元素的值
    
    return 0;
}

动态分配：

//顺序表的按位查找（动态分配）

#include <stdio.h>
#include <stdlib.h>

#define InitSize 10  //默认的最大长度

typedef struct{
    int *data;  //指示动态分配数组的指针
    int MaxSize;  //顺序表的最大容量
    int length;  //顺序表的当前长度
}SeqList;

void InitList(SeqList *L){
    //用malloc函数申请一片连续的存储空间
    L->data=(int *)malloc(InitSize*sizeof(int));
    L->length=0;
    L->MaxSize=InitSize;
}

int GetElem(SeqList *L,int i){
    
    return L->data[i-1];
}

int main(){
    SeqList L;  //声明一个顺序表
    InitList(&L);  //初始化顺序表
    //...往顺序表加入几个元素
    
    int num=GetElem(&L, 3);  //查找表L中第3个位置的元素的值

    return 0;
}

顺序表的按值查找(最好O(1),最坏O(n),平均O(n))

LocateElem(L,e)：按值查找操作，在表L中查找具有给定关键字值的元素

//顺序表的按值查找

#include <stdio.h>
#include <stdlib.h>

#define InitSize 10  //默认的最大长度

typedef struct{
    int *data;  //指示动态分配数组的指针
    int MaxSize;  //顺序表的最大容量
    int length;  //顺序表的当前长度
}SeqList;

void InitList(SeqList *L){
    //用malloc函数申请一片连续的存储空间
    L->data=(int *)malloc(InitSize*sizeof(int));
    L->length=0;
    L->MaxSize=InitSize;
}

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList *L,int e){
    
    for(int i=0;i<L->length;i++){
        if(L->data[i] == e){
            return i+1;  //数组下标为i的元素值等于e，返回其位序i+1
        }
    }
    return 0;  //退出循环，说明查找失败
}

int main(){
    SeqList L;  //声明一个顺序表
    InitList(&L);  //初始化顺序表
    //...往顺序表加入几个元素
    
    int num=LocateElem(&L, 3);  //查找表L中第3个位置的元素的值

    return 0;
}