数据结构17-顺序查找与二分查找
好的，下面我们将详细介绍C语言中的顺序查找和二分查找，特别是针对键值对的情况。我们会从基本概念、数据结构、实现方法和代码示例等方面进行系统讲解。
一、顺序查找（Sequential Search）
1. 概念
顺序查找是一种简单的查找算法，它从数据集的第一个元素开始，逐个检查每个元素，直到找到目标元素或到达数据集的末尾。顺序查找的时间复杂度为 (O(n))，其中 (n) 是数据集的大小。
2. 数据结构
我们使用一个数组来存储键值对。键值对可以使用结构体来表示。
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int key;
int value;
} KeyValuePair;
typedef struct {
KeyValuePair data[MAX_SIZE];
int size;
} SequentialTable;
3. 初始化顺序表
初始化顺序表时，我们需要设置初始大小为0。
void initTable(SequentialTable *table) {
table->size = 0;
}
4. 添加键值对
向顺序表中添加键值对。
bool addKeyValuePair(SequentialTable *table, int key, int value) {
if (table->size >= MAX_SIZE) {
return false; // 表已满
}
table->data[table->size].key = key;
table->data[table->size].value = value;
table->size++;
return true;
}
5. 顺序查找函数
实现顺序查找函数，返回键对应的值。
int sequentialSearch(SequentialTable *table, int key) {
for (int i = 0; i < table->size; i++) {
if (table->data[i].key == key) {
return table->data[i].value;
}
}
return -1; // 未找到
}
6. 完整示例代码
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int key;
int value;
} KeyValuePair;
typedef struct {
KeyValuePair data[MAX_SIZE];
int size;
} SequentialTable;
void initTable(SequentialTable *table) {
table->size = 0;
}
bool addKeyValuePair(SequentialTable *table, int key, int value) {
if (table->size >= MAX_SIZE) {
return false; // 表已满
}
table->data[table->size].key = key;
table->data[table->size].value = value;
table->size++;
return true;
}
int sequentialSearch(SequentialTable *table, int key) {
for (int i = 0; i < table->size; i++) {
if (table->data[i].key == key) {
return table->data[i].value;
}
}
return -1; // 未找到
}
int main() {
SequentialTable table;
initTable(&table);
addKeyValuePair(&table, 1, 100);
addKeyValuePair(&table, 2, 200);
addKeyValuePair(&table, 3, 300);
int key = 2;
int value = sequentialSearch(&table, key);
if (value != -1) {
printf("Key %d found with value %d\n", key, value);
} else {
printf("Key %d not found\n", key);
}
return 0;
}
二、二分查找（Binary Search）
1. 概念
二分查找是一种高效的查找算法，适用于有序数组。它通过反复将查找范围减半来缩小查找范围。二分查找的时间复杂度为 (O(\log n))，其中 (n) 是数据集的大小。
2. 数据结构
与顺序查找类似，我们使用一个数组来存储键值对，并确保数组是按键排序的。
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int key;
int value;
} KeyValuePair;
typedef struct {
KeyValuePair data[MAX_SIZE];
int size;
} SortedTable;
3. 初始化顺序表
初始化顺序表时，我们需要设置初始大小为0。
void initTable(SortedTable *table) {
table->size = 0;
}
4. 添加键值对
向顺序表中添加键值对，并保持数组有序。
bool addKeyValuePair(SortedTable *table, int key, int value) {
if (table->size >= MAX_SIZE) {
return false; // 表已满
}
int i;
for (i = table->size - 1; (i >= 0 && table->data[i].key > key); i--) {
table->data[i + 1] = table->data[i];
}
table->data[i + 1].key = key;
table->data[i + 1].value = value;
table->size++;
return true;
}
5. 二分查找函数
实现二分查找函数，返回键对应的值。
int binarySearch(SortedTable *table, int key) {
int left = 0;
int right = table->size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (table->data[mid].key == key) {
return table->data[mid].value;
} else if (table->data[mid].key < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 未找到
}
6. 完整示例代码
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int key;
int value;
} KeyValuePair;
typedef struct {
KeyValuePair data[MAX_SIZE];
int size;
} SortedTable;
void initTable(SortedTable *table) {
table->size = 0;
}
bool addKeyValuePair(SortedTable *table, int key, int value) {
if (table->size >= MAX_SIZE) {
return false; // 表已满
}
int i;
for (i = table->size - 1; (i >= 0 && table->data[i].key > key); i--) {
table->data[i + 1] = table->data[i];
}
table->data[i + 1].key = key;
table->data[i + 1].value = value;
table->size++;
return true;
}
int binarySearch(SortedTable *table, int key) {
int left = 0;
int right = table->size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (table->data[mid].key == key) {
return table->data[mid].value;
} else if (table->data[mid].key < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 未找到
}
int main() {
SortedTable table;
initTable(&table);
addKeyValuePair(&table, 1, 100);
addKeyValuePair(&table, 3, 300);
addKeyValuePair(&table, 2, 200);
int key = 2;
int value = binarySearch(&table, key);
if (value != -1) {
printf("Key %d found with value %d\n", key, value);
} else {
printf("Key %d not found\n", key);
}
return 0;
}
总结
顺序查找和二分查找是两种常见的查找算法，各有优缺点。顺序查找适用于小规模数据集或无序数据集，而二分查找适用于有序数据集，并在大规模数据集上表现更优。选择哪种查找算法取决于具体的应用场景和数据特点。
闵帆老师写的
代码
/**
* Sequential search and binary search.
*
* @author Fan Min [email protected].
*/
#include <stdio.h>
#include <malloc.h>
/**
* <key, value> pair.
*/
typedef struct Node{
int key;
char value;
}Node, *NodePtr;
/**
* The data structure of the sequential list.
*/
typedef struct SequentialList{
int length;
NodePtr elements;
}SequentialList, *ListPtr;
/**
* Initialize a data array.
*/
ListPtr initList(int* paraKeys, char* paraValues, int paraLength){
int i;
ListPtr resultPtr = (ListPtr)malloc(sizeof(struct SequentialList));
resultPtr->length = paraLength;
resultPtr->elements = (NodePtr)malloc((paraLength + 1) * sizeof(struct Node));
for (i = 0; i < paraLength; i ++){
//printf("setting key for index %d: %d and value: %c\r\n", i, paraKeys[i], paraValues[i]);
resultPtr->elements[i + 1].key = paraKeys[i];
resultPtr->elements[i + 1].value = paraValues[i];
}//Of for i
return resultPtr;
}//Of initList
/**
* Sequential search.
* @return The value.
*/
char sequentialSearch(ListPtr paraListPtr, int paraKey){
int i = paraListPtr->length;
paraListPtr->elements[0].key = paraKey;
paraListPtr->elements[0].value = 'x';
while(paraListPtr->elements[i].key != paraKey){
i--;
}//Of while
return paraListPtr->elements[i].value;
}//Of sequentialSearch
/**
* Test the sequential search function.
*/
void sequentialSearchTest() {
int tempUnsortedKeys[] = { 4, 5, 3, 6, 10, 7, 1, 9 };
char tempContents[] = { 'h', 'e', 'l', 'o', 'w', 'r', 'd', '!' };
ListPtr tempListPtr = initList(tempUnsortedKeys, tempContents, 8);
printf("Search result of 10 is: %c\r\n", sequentialSearch(tempListPtr, 10));
printf("Search result of 5 is: %c\r\n", sequentialSearch(tempListPtr, 5));
printf("Search result of 4 is: %c\r\n", sequentialSearch(tempListPtr, 4));
printf("Search result of 2 is: %c\r\n", sequentialSearch(tempListPtr, 2));
}// Of sequentialSearchTest
/**
* Binary search.
* @return The value.
*/
char binarySearch(ListPtr paraListPtr, int paraKey){
int tempLeft = 1;
int tempRight = paraListPtr->length;
int tempMiddle = (tempLeft + tempRight) / 2;
while (tempLeft <= tempRight) {
tempMiddle = (tempLeft + tempRight) / 2;
if (paraListPtr->elements[tempMiddle].key == paraKey) {
return paraListPtr->elements[tempMiddle].value;
} else if (paraListPtr->elements[tempMiddle].key <= paraKey) {
tempLeft = tempMiddle + 1;
} else {
tempRight = tempMiddle - 1;
}//Of if
} // Of while
// Not found.
return 'x';
}//Of binarySearch
/**
* Test the binary search function.
*/
void binarySearchTest() {
int tempUnsortedKeys[] = { 1, 3, 4, 5, 6, 7, 9, 10 };
char tempContents[] = { 'h', 'e', 'l', 'o', 'w', 'r', 'd', '!' };
ListPtr tempListPtr = initList(tempUnsortedKeys, tempContents, 8);
printf("Search result of 10 is: %c\r\n", binarySearch(tempListPtr, 10));
printf("Search result of 5 is: %c\r\n", binarySearch(tempListPtr, 5));
printf("Search result of 4 is: %c\r\n", binarySearch(tempListPtr, 4));
printf("Search result of 2 is: %c\r\n", binarySearch(tempListPtr, 2));
}// Of binarySearchTest
/**
* The entrance.
*/
int main(){
printf("\r\n-------sequentialSearchTest-------\r\n");
sequentialSearchTest();
printf("\r\n-------binarySearchTest-------\r\n");
binarySearchTest();
return 1;
}// Of main
运行结果
-------sequentialSearchTest-------
Search result of 10 is: w
Search result of 5 is: e
Search result of 4 is: h
Search result of 2 is: x
-------binarySearchTest-------
Search result of 10 is: !
Search result of 5 is: o
Search result of 4 is: l
Search result of 2 is: x
Press any key to continue