数据结构_顺序查找(C语言)
#include <>
#define size 10
// 普通顺序查找
int Search_Sq01(int *num, int len, int key)
{
int i, count = 0;
for(i = 1; i <= len; i++)
{
// 每次循环都需要两次判断，（i < len和 num[i] == key）
count += 2;
if (num[i] == key)
{
return count;
}
}
return -1;
}
// 设置哨兵的顺序查找
int Search_Sq02(int *num, int len, int key)
{
int i, count = 0;
// 设置哨兵
num[0] = key;
for (i = len - 1; num[i] != key; i--)
{
count++;
}
count += 2;
return i != 0 ? count : -1;
}
int main()
{
int num[size + 1] = {0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int i, count, sum;
sum = 0;
for (i = 0; i < 10; i++)
{
count = Search_Sq01(num, size + 1, i);
sum += count;
printf("查找 %d , 判断次数 = %d\n", i, count);
}
printf("普通顺序查找的平均判断次数 = %d\n", sum / size);
sum = 0;
for (i = 0; i < 10; i++)
{
count = Search_Sq02(num, size + 1, i);
sum += count;
printf("查找 %d , 判断次数 = %d\n", i, count);
}
printf("哨兵顺序查找的平均判断次数 = %d\n", sum / size);
return 0;
}