建立顺序查找表,并在此查找表上实现顺序查找操作。
时间: 2023-10-01 12:09:59 浏览: 87
建立顺序查找表的方法是:先定义一个结构体,包含两个成员变量,一个是要查找的关键字,另一个是与关键字相关的数据项。然后使用一个数组来存储这些结构体。
以下是一个示例代码:
```c
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100
// 定义一个结构体,包含关键字和数据项
typedef struct {
int key;
char data[20];
} DataType;
// 定义顺序查找表
typedef struct {
DataType data[MAX_SIZE];
int length;
} SeqList;
// 初始化顺序查找表
void InitList(SeqList *L)
{
L->length = 0;
}
// 在顺序查找表中查找关键字为key的数据项
int SeqSearch(SeqList L, int key)
{
int i;
for (i = 0; i < L.length; i++) {
if (L.data[i].key == key) {
return i;
}
}
return -1;
}
// 测试代码
int main()
{
SeqList L;
InitList(&L);
int i;
// 插入数据
for (i = 0; i < 5; i++) {
L.data[i].key = i;
sprintf(L.data[i].data, "data%d", i);
L.length++;
}
// 查找数据
int index = SeqSearch(L, 3);
if (index != -1) {
printf("关键字为%d的数据项为%s\n", L.data[index].key, L.data[index].data);
} else {
printf("未找到关键字为3的数据项\n");
}
return 0;
}
```
输出结果为:
```
关键字为3的数据项为data3
```
在这个示例代码中,我们首先定义了一个结构体 `DataType`,包含了一个整型的关键字和一个字符串类型的数据项。然后我们定义了一个顺序查找表 `SeqList`,其中包含了一个 `DataType` 类型的数组和一个 `length` 变量,用于记录数组的长度。
在主函数中,我们首先使用 `InitList()` 函数初始化了顺序查找表。然后我们插入了一些数据项,这里我们插入了5个关键字分别为0~4的数据项。接着我们使用 `SeqSearch()` 函数在顺序查找表中查找关键字为3的数据项,如果找到了则输出关键字和数据项,否则输出未找到信息。
需要注意的是,顺序查找的时间复杂度为 O(n),即最坏情况下需要遍历整个数组才能找到目标数据项。因此,顺序查找适用于数据量较小的情况。如果数据量较大,可以使用其他高效的查找算法,如二分查找、哈希查找等。
阅读全文