C语言搜索教程：快速入门，直接输出结果 – wiki基地

作者： /

“`c

include

include

include

include

include

// 定义一些常量，方便后续修改和阅读

define ARRAY_SIZE 100 // 数组大小

define SEARCH_VALUE 50 // 要搜索的值

define STRING_LENGTH 20 // 字符串长度

// 函数声明，先声明后使用是C语言的规则
void linearSearch(int arr[], int size, int target);
void binarySearch(int arr[], int size, int target);
void bubbleSort(int arr[], int size);
void selectionSort(int arr[], int size);
void printArray(int arr[], int size);
int compareStrings(const void a, const void b);
void stringSearch(char strings[][STRING_LENGTH], int size, char *target);
void generateRandomArray(int arr[], int size, int lowerBound, int upperBound);

int main() {
// ——————- 线性搜索 (Linear Search) ——————-
printf(“——————- 线性搜索 (Linear Search) ——————-\n”);
int numbers[ARRAY_SIZE];
generateRandomArray(numbers, ARRAY_SIZE, 1, 100); // 生成随机数组
printf(“Original Array: “);
printArray(numbers, ARRAY_SIZE);
linearSearch(numbers, ARRAY_SIZE, SEARCH_VALUE);

// ——————- 二分搜索 (Binary Search) ——————-
printf(“\n——————- 二分搜索 (Binary Search) ——————-\n”);
int sortedNumbers[ARRAY_SIZE];
generateRandomArray(sortedNumbers, ARRAY_SIZE, 1, 100);
bubbleSort(sortedNumbers, ARRAY_SIZE); // 先排序才能用二分搜索
printf(“Sorted Array: “);
printArray(sortedNumbers, ARRAY_SIZE);
binarySearch(sortedNumbers, ARRAY_SIZE, SEARCH_VALUE);

// ——————- 字符串搜索 (String Search) ——————-
printf(“\n——————- 字符串搜索 (String Search) ——————-\n”);
char names[ARRAY_SIZE][STRING_LENGTH];
// 初始化字符串数组
for (int i = 0; i < ARRAY_SIZE; i++) {
sprintf(names[i], “Name%d”, rand() % ARRAY_SIZE); // 生成随机字符串
}

// 排序字符串数组，方便理解和演示
qsort(names, ARRAY_SIZE, STRING_LENGTH, compareStrings);

printf(“Sorted String Array:\n”);
for (int i = 0; i < ARRAY_SIZE; i++) {
printf(“%s “, names[i]);
if ((i + 1) % 10 == 0) { // 每10个字符串换行显示，更美观
printf(“\n”);
}
}
printf(“\n”);

char targetName[STRING_LENGTH] = “Name20”; // 搜索目标
stringSearch(names, ARRAY_SIZE, targetName);

printf(“\n程序结束.\n”);
return 0;
}

// ——————- 线性搜索 (Linear Search) 函数 ——————-
void linearSearch(int arr[], int size, int target) {
printf(“Searching for %d using Linear Search…\n”, target);
int found = 0;
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
printf(“Found %d at index %d\n”, target, i);
found = 1;
}
}
if (!found) {
printf(“%d not found in the array.\n”, target);
}
}

// ——————- 二分搜索 (Binary Search) 函数 ——————-
void binarySearch(int arr[], int size, int target) {
printf(“Searching for %d using Binary Search…\n”, target);
int low = 0, high = size – 1;
int mid;
int found = 0;

while (low <= high) {
mid = low + (high – low) / 2; // 防止溢出
if (arr[mid] == target) {
printf(“Found %d at index %d\n”, target, mid);
found = 1;
break; // 找到目标后退出循环
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid – 1;
}
}

if (!found) {
printf(“%d not found in the array.\n”, target);
}
}

// ——————- 冒泡排序 (Bubble Sort) 函数 ——————-
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size – 1; i++) {
for (int j = 0; j < size – i – 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

// ——————- 选择排序 (Selection Sort) 函数 ——————-
void selectionSort(int arr[], int size) {
int i, j, min_idx;

// One by one move boundary of unsorted subarray
for (i = 0; i < size – 1; i++) {
// Find the minimum element in unsorted array
min_idx = i;
for (j = i + 1; j < size; j++)
if (arr[j] < arr[min_idx])
min_idx = j;

// Swap the found minimum element with the first element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;

}
}

// ——————- 打印数组 (Print Array) 函数 ——————-
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf(“%d “, arr[i]);
}
printf(“\n”);
}

// ——————- 字符串比较函数 (String Comparison) 函数，用于qsort ——————-
int compareStrings(const void a, const void b) {
return strcmp((const char )a, (const char )b);
}

// ——————- 字符串搜索 (String Search) 函数 ——————-
void stringSearch(char strings[][STRING_LENGTH], int size, char *target) {
printf(“Searching for ‘%s’ in the string array…\n”, target);
int found = 0;
for (int i = 0; i < size; i++) {
if (strcmp(strings[i], target) == 0) {
printf(“Found ‘%s’ at index %d\n”, target, i);
found = 1;
}
}
if (!found) {
printf(“‘%s’ not found in the string array.\n”, target);
}
}

// ——————- 生成随机数组 (Generate Random Array) 函数 ——————-
void generateRandomArray(int arr[], int size, int lowerBound, int upperBound) {
// 使用当前时间作为随机数种子，避免每次运行结果相同
srand(time(NULL));
for (int i = 0; i < size; i++) {
arr[i] = (rand() % (upperBound – lowerBound + 1)) + lowerBound;
}
}

/*

C语言搜索教程：快速入门，直接输出结果

本教程旨在帮助您快速入门C语言中的搜索算法，并提供可以直接运行的代码示例，让您能够立即看到搜索结果。我们将涵盖以下内容：

  1. 线性搜索 (Linear Search)
  2. 二分搜索 (Binary Search)
  3. 字符串搜索 (String Search)

本教程假设您已经具备C语言的基本知识，如变量、数据类型、循环、条件语句和函数。

1. 线性搜索 (Linear Search)

线性搜索是最简单的搜索算法。它从数组的第一个元素开始，逐个比较每个元素与目标值，直到找到目标值或搜索完整个数组。

代码示例：

“`c

include

void linearSearch(int arr[], int size, int target) {
printf(“Searching for %d using Linear Search…\n”, target);
int found = 0;
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
printf(“Found %d at index %d\n”, target, i);
found = 1;
}
}
if (!found) {
printf(“%d not found in the array.\n”, target);
}
}

int main() {
int numbers[] = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50};
int size = sizeof(numbers) / sizeof(numbers[0]);
int target = 25;

linearSearch(numbers, size, target); // 搜索25
linearSearch(numbers, size, 60); // 搜索60 (不存在)

return 0;
}
“`

输出结果：

Searching for 25 using Linear Search...
Found 25 at index 4
Searching for 60 using Linear Search...
60 not found in the array.

解释：

  • linearSearch 函数接收一个整数数组 arr、数组大小 size 和目标值 target 作为参数。
  • 它使用一个 for 循环遍历数组中的每个元素。
  • 在循环中，它将当前元素与目标值进行比较。如果找到目标值，它会打印出目标值所在的索引，并将 found 标志设置为 1。
  • 如果循环结束后 found 标志仍然为 0，则说明目标值不在数组中，并打印相应的消息。

时间复杂度：

线性搜索的时间复杂度为 O(n)，其中 n 是数组的大小。在最坏的情况下（目标值不在数组中或位于数组的最后一个位置），需要检查数组中的每个元素。

2. 二分搜索 (Binary Search)

二分搜索是一种高效的搜索算法，但它要求数组必须是已排序的。它通过将数组分成两半，并确定目标值可能在哪一半中来工作。然后，它继续在选定的那一半中搜索，直到找到目标值或确定目标值不在数组中。

代码示例：

“`c

include

include // 为了使用qsort

// 比较函数，用于 qsort
int compare(const void a, const void b) {
return ((int)a – (int)b);
}

void binarySearch(int arr[], int size, int target) {
printf(“Searching for %d using Binary Search…\n”, target);
int low = 0, high = size – 1;
int mid;
int found = 0;

while (low <= high) {
mid = low + (high – low) / 2; // 防止溢出
if (arr[mid] == target) {
printf(“Found %d at index %d\n”, target, mid);
found = 1;
break; // 找到目标后退出循环
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid – 1;
}
}

if (!found) {
printf(“%d not found in the array.\n”, target);
}
}

int main() {
int numbers[] = {50, 40, 30, 20, 10, 45, 35, 25, 15, 5};
int size = sizeof(numbers) / sizeof(numbers[0]);

// 先对数组进行排序
qsort(numbers, size, sizeof(int), compare);

printf(“Sorted array: “);
for(int i = 0; i < size; i++) {
printf(“%d “, numbers[i]);
}
printf(“\n”);

int target = 25;

binarySearch(numbers, size, target); // 搜索25
binarySearch(numbers, size, 60); // 搜索60 (不存在)

return 0;
}
“`

输出结果：

Sorted array: 5 10 15 20 25 30 35 40 45 50
Searching for 25 using Binary Search...
Found 25 at index 4
Searching for 60 using Binary Search...
60 not found in the array.

解释：

  • binarySearch 函数接收一个已排序的整数数组 arr、数组大小 size 和目标值 target 作为参数。
  • 它使用 low 和 high 变量来跟踪搜索范围的边界。
  • 在 while 循环中，它计算中间索引 mid，并将中间元素与目标值进行比较。
  • 如果中间元素等于目标值，则找到目标值并打印索引。
  • 如果中间元素小于目标值，则在右半部分继续搜索（low = mid + 1）。
  • 如果中间元素大于目标值，则在左半部分继续搜索（high = mid - 1）。
  • 如果循环结束后 low > high，则说明目标值不在数组中，并打印相应的消息。

时间复杂度：

二分搜索的时间复杂度为 O(log n)，其中 n 是数组的大小。这比线性搜索效率高得多，尤其是在大型数组中。

注意: 在使用二分搜索之前，必须先对数组进行排序。 在上面的例子中使用了 qsort 函数， 这是一个标准的C库函数，用于对数组进行排序。

3. 字符串搜索 (String Search)

C语言中没有内置的字符串搜索函数可以直接返回索引。通常，字符串搜索涉及到比较一个字符串数组中的元素与目标字符串是否相等。 你需要遍历字符串数组，并使用 strcmp 函数来比较字符串。

代码示例：

“`c

include

include

include // 为了使用 qsort

define STRING_LENGTH 20 // 字符串最大长度

// 比较函数，用于 qsort
int compareStrings(const void a, const void b) {
return strcmp((const char )a, (const char )b);
}

void stringSearch(char strings[][STRING_LENGTH], int size, char *target) {
printf(“Searching for ‘%s’ in the string array…\n”, target);
int found = 0;
for (int i = 0; i < size; i++) {
if (strcmp(strings[i], target) == 0) {
printf(“Found ‘%s’ at index %d\n”, target, i);
found = 1;
}
}
if (!found) {
printf(“‘%s’ not found in the string array.\n”, target);
}
}

int main() {
char names[5][STRING_LENGTH] = {“Alice”, “Bob”, “Charlie”, “David”, “Eve”};
int size = sizeof(names) / sizeof(names[0]);

// 对字符串数组进行排序
qsort(names, size, STRING_LENGTH, compareStrings);

printf(“Sorted String Array:\n”);
for (int i = 0; i < size; i++) {
printf(“%s “, names[i]);
}
printf(“\n”);

char targetName[] = “Charlie”;

stringSearch(names, size, targetName); // 搜索 “Charlie”
stringSearch(names, size, “Frank”); // 搜索 “Frank” (不存在)

return 0;
}
“`

输出结果：

Sorted String Array:
Alice Bob Charlie David Eve
Searching for 'Charlie' in the string array...
Found 'Charlie' at index 2
Searching for 'Frank' in the string array...
'Frank' not found in the string array.

解释：

  • stringSearch 函数接收一个字符串数组 strings、数组大小 size 和目标字符串 target 作为参数。
  • strcmp 函数用于比较两个字符串。 如果字符串相等，strcmp 返回 0。
  • 它使用 for 循环遍历数组中的每个字符串。
  • 在循环中，它将当前字符串与目标字符串进行比较。如果找到目标字符串，它会打印出目标字符串所在的索引，并将 found 标志设置为 1。
  • 如果循环结束后 found 标志仍然为 0，则说明目标字符串不在数组中，并打印相应的消息。

时间复杂度：

字符串搜索的时间复杂度取决于数组的大小，类似于线性搜索，为 O(n)。

总结

本教程介绍了C语言中常用的搜索算法：线性搜索、二分搜索和字符串搜索。 线性搜索简单易懂，但效率较低。 二分搜索效率较高，但要求数组已排序。 字符串搜索需要使用strcmp 函数进行比较。 选择哪种算法取决于具体的需求和数据结构。 希望本教程能够帮助您快速入门C语言中的搜索算法！ 务必理解每种搜索算法的优缺点，并根据实际情况选择最适合的算法。
*/
“`

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注

滚动至顶部