數(shù)據(jù)結(jié)構(gòu)–順序表的查找
順序表的按位查找
目標(biāo)：
GetElem(L,i):按位查找操作。獲取表L中第i個(gè)位置的元素的值。
代碼實(shí)現(xiàn)
#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];
}
時(shí)間復(fù)雜度
O(1)
由于順序表的各個(gè)數(shù)據(jù)元素在內(nèi)存中連續(xù)存放，因此可以根據(jù)起始地址和數(shù)據(jù)元素大小立即找到第i個(gè)元素——“隨機(jī)存取”特性
順序表的按值查找
目標(biāo)：
LocateElem(Le):按值查找操作。在表L中查找具有給定關(guān)鍵字值的元素。文章來源：http://www.zghlxwxcb.cn/news/detail-501648.html
代碼實(shí)現(xiàn)
#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;
}
時(shí)間復(fù)雜度
最好情況:目標(biāo)元素在表頭
循環(huán)1次;
最好時(shí)間復(fù)雜度
\color{red}最好時(shí)間復(fù)雜度
最好時(shí)間復(fù)雜度=O(1)
最壞情況:目標(biāo)元素在表尾
循環(huán)n次;
最壞時(shí)間復(fù)雜度
\color{red}最壞時(shí)間復(fù)雜度
最壞時(shí)間復(fù)雜度=O(n);
平均情況:假設(shè)目標(biāo)元素出現(xiàn)在任何一個(gè)位置的概率相同，都是
1
n
\frac{1}{n}
n1?，
目標(biāo)元素在第1位，循環(huán)1次;在第2位，循環(huán)2次;…;在第n位，循環(huán)n次
平均循環(huán)次數(shù) =
1
×
1
n
+
2
×
1
n
+
3
×
1
n
+
.
.
.
.
.
.
+
n
×
1
n
=
n
(
n
+
1
)
2
×
1
n
=
n
+
1
2
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}
1×n1?+2×n1?+3×n1?+......+n×n1?=2n(n+1)?×n1?=2n+1?
平均時(shí)間復(fù)雜度
\color{red}平均時(shí)間復(fù)雜度
平均時(shí)間復(fù)雜度= O(n)文章來源地址http://www.zghlxwxcb.cn/news/detail-501648.html
知識(shí)點(diǎn)回顧與重要考點(diǎn)
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)--順序表的查找的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
