采用顺序存储结构创建静态查找表,对查找表进行顺序查找和改进的顺序查找,并对其查找效率进行比较,用C语言编码
时间: 2024-04-29 11:19:50 浏览: 93
好的,下面是采用顺序存储结构创建静态查找表,对查找表进行顺序查找和改进的顺序查找的代码实现,并对其查找效率进行比较的C语言代码:
```c
#include <stdio.h>
// 定义静态查找表
typedef struct {
int key; // 关键字
int value; // 数据元素
} StaticTable;
// 顺序查找
int sequentialSearch(StaticTable table[], int n, int key) {
int i;
for (i = 0; i < n; i++) {
if (table[i].key == key) {
return table[i].value;
}
}
return -1; // 若找不到,则返回-1
}
// 改进的顺序查找
int improvedSequentialSearch(StaticTable table[], int n, int key) {
int i;
table[0].key = key; // 设置哨兵
i = n;
while (table[i].key != key) {
i--;
}
return table[i].value;
}
int main() {
// 创建静态查找表
StaticTable table[] = {
{1, 10},
{2, 20},
{3, 30},
{4, 40},
{5, 50},
{6, 60},
{7, 70},
{8, 80},
{9, 90},
{10, 100}
};
int n = sizeof(table) / sizeof(StaticTable);
// 进行顺序查找
int result1 = sequentialSearch(table, n, 7);
printf("Sequential Search Result: %d\n", result1);
// 进行改进的顺序查找
int result2 = improvedSequentialSearch(table, n, 7);
printf("Improved Sequential Search Result: %d\n", result2);
return 0;
}
```
在上述代码中,我们通过定义 `StaticTable` 结构体来表示静态查找表,其中包含了关键字 `key` 和数据元素 `value` 两个成员变量。然后,我们分别实现了顺序查找和改进的顺序查找两种算法,并在 `main` 函数中进行了调用和比较。
需要注意的是,在改进的顺序查找中,为了避免每次查找都需要判断是否查找到了最后一个元素,我们在查找前额外设置了一个关键字为待查找的 `key` 的哨兵元素,这样即使查找到了最后一个元素,也不需要进行额外的判断。