数据结构--顺序表的查找-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构--顺序表的查找。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构–顺序表的查找

顺序表的按位查找

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

代码实现

#define MaxSize 10
typedef struct
{
    ElemType data[MaxSize];
    int len;
}Sqlist;


ElemType GetElem(Sqlist L, int i)
{
	return L.data[i-1];
}

#define InitSize 10
typedef struct
{
    ElemType *data;
    int MaxSize;
    int len
}Sqlist;

ElemType GetElem(Sqlist L, int i)
{
	return L.data[i-1];
}

时间复杂度

O(1)
由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素——“随机存取”特性

顺序表的按值查找

目标：
LocateElem(Le):按值查找操作。在表L中查找具有给定关键字值的元素。

代码实现

#define InitSize 10

typedef struct 
{
    Elemtype *date;
    int MaxSize;
    int len;
} SeqList;

int LocateElem(SeqList L, Elemtype e)
{
    for (int i = 0; i <L.len; i++)
        if (L.date[i] == e)
            return i + 1;
        return 0;
}

时间复杂度

最好情况:目标元素在表头
循环1次; $\color{red}最好时间复杂度$ =O(1)
最坏情况:目标元素在表尾
循环n次; $\color{red}最坏时间复杂度$ =O(n);
平均情况:假设目标元素出现在任何一个位置的概率相同，都是 $\frac{1}{n}$ ，
目标元素在第1位，循环1次;在第2位，循环2次;…;在第n位，循环n次
平均循环次数 = $1\times\frac{1}{n}+ 2\times \frac{1}{n} +3 \times \frac{1}{n} + ...... + n \times \frac{1}{n} = \frac{n(n+1)}{2} \times \frac{1}{n}=\frac{n+1}{2}$
$\color{red}平均时间复杂度$ = O(n)文章来源地址https://www.toymoban.com/news/detail-501648.html