顺序表操作--查找_顺序表的查找

顺序表的查找分为：按位查找和按值查找

1、顺序表基本操作–按位查找

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

ElemType GetElem(SeqList L,int i){
    return L.data[i-1]
}
                  
1
2
3
4

• 按位查找的时间复杂度最好/最坏/平均都是O(1)

2、顺序表基本操作–按值查找

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

#define InitSize 10  //顺序表的初始长度
typedef struct{
    ElemType *data;  //只是动态分配数组的指针
    int MaxSize;     //顺序表的最大容量
    int length;		 //顺序表的当前长度
}SeqList;            //顺序表的类型定义(动态分配方式)

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L,ElemType e){
    for(int i=0;i<L.length;i++)
        if(L.data[i]==e)
            return i+1;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 按值查找最好/最坏/平均时间复杂度分别是：O(1)、O(n)、O(n)