(06)王道数据结构-顺序表的查找

按位查找：

#define InitSize 10 //默认最大长度
#include<stdio.h>
#include<stdlib.h>
typedef struct {
    int *data;      //指示动态分配数组的指针
    int MaxSize;    //顺序表的最大容量
    int length;     //顺序表的当前长度
}SqList;
//初始化数组
void InitList(SqList &L);
//获取数组元素（按位）
int GetElem(SqList L, int i);
//判断数组是否已满
bool IsFull(SqList &L);
//追加元素
bool ListAppend(SqList &L,int e);
int main(void) {
    SqList L;
    //初始化顺序表
    InitList(L);

    //插入元素
    ListAppend(L, 11);
    ListAppend(L, 22);
    ListAppend(L, 33);
    ListAppend(L, 44);
    ListAppend(L, 55);
    ListAppend(L, 66);
    ListAppend(L, 77);

    //获取数组元素
    int num = GetElem(L, 3);
    printf("获取到%d", num);
    return 0;
}

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

int GetElem(SqList L, int i) {
    //和数组的获取方法相同
    return L.data[i-1];
}

bool IsFull(SqList &L) {
    //顺序表当前长度和最大长度一样说明满了
    if (L.length == L.MaxSize) {
        return true;
    } else {
        return false;
    }
}

bool ListAppend(SqList &L,int e) {
    if (IsFull(L)) {
        printf("数组满了！\n");
        return false;
    } else {
        //数组当前位置插入e
        L.data[L.length] = e;
        //插入后长度+1
        L.length++;
        return true;
    }
}

时间复杂度

时间复杂度: O(1), 因为在内存中是连续存放的，可以根据起始地址和数据元素大小立即找到第i个元素

按值查找：

#define InitSize 10 //默认最大长度
#include<stdio.h>
#include<stdlib.h>
typedef struct {
    int *data;      //指示动态分配数组的指针
    int MaxSize;    //顺序表的最大容量
    int length;     //顺序表的当前长度
}SqList;
//初始化数组
void InitList(SqList &L);
//获取数组元素（按值）
int LocateElem(SqList L, int e);
//判断数组是否已满
bool IsFull(SqList &L);
//追加元素
bool ListAppend(SqList &L,int e);
int main(void) {
    SqList L;
    //初始化顺序表
    InitList(L);

    //插入元素
    ListAppend(L, 11);
    ListAppend(L, 22);
    ListAppend(L, 33);
    ListAppend(L, 44);
    ListAppend(L, 55);
    ListAppend(L, 66);
    ListAppend(L, 77);

    //获取数组元素下标
    int local = LocateElem(L, 33);
    printf("获取到%d", local);
    return 0;
}

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

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

bool IsFull(SqList &L) {
    //顺序表当前长度和最大长度一样说明满了
    if (L.length == L.MaxSize) {
        return true;
    } else {
        return false;
    }
}

bool ListAppend(SqList &L,int e) {
    if (IsFull(L)) {
        printf("数组满了！\n");
        return false;
    } else {
        //数组当前位置插入e
        L.data[L.length] = e;
        //插入后长度+1
        L.length++;
        return true;
    }
}

时间复杂度

最好情况：目标元素在表头，循环1次，最好时间复杂度=O(1) 最坏情况：目标元素在表尾，循环n次，最坏时间复杂度=O(n) 平均情况：假设目标元素出现在任何一个位置的概率相同，都是 $$ \frac{1}{n} $$ 目标元素在第1位，循环1次；在第2位，循环2次；在第n位，循环n次 平均循环次数= $$ 1·\frac{1}{n} + 2·\frac{1}{n} + 3·\frac{1}{n} + … + n·\frac{1}{n} = \frac{n(n+1)}{2}·\frac{1}{n}=\frac{n+1}{2} $$