C语言基础（三十一）

1、线性搜索：

#include "date.h"
#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  // 希尔排序  
void shellSort(int arr[], int n) {  for (int gap = n / 2; gap > 0; gap /= 2) {  for (int i = gap; i < n; i++) {  int temp = arr[i];  int j;  for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {  arr[j] = arr[j - gap];  }  arr[j] = temp;  }  }  
}  // 线性搜索并计算相同元素个数，打印序号  
void linearSearchAndCount(int arr[], int n, int target) {  int count = 0;  printf("Found at indices: ");  for (int i = 0; i < n; i++) {  if (arr[i] == target) {  printf("%d ", i);  count++;  }  }  if (count == 0) {  printf("Not found.\n");  } else {  printf("\nTotal occurrences: %d\n", count);  }  
}  // 打印数组  
void printArray(int arr[], int n) {  for (int i = 0; i < n; i++) {  printf("%d ", arr[i]);  }  printf("\n");  
}  int main() {  int times = getTime();int n, target;  printf("Enter the size of the array: ");  scanf("%d", &n);  int *arr = (int *)malloc(n * sizeof(int));  if (arr == NULL) {  printf("Memory allocation failed.\n");  return 1;  }  srand(time(NULL));  for (int i = 0; i < n; i++) {  arr[i] = rand() % 100; // 假设生成0到99之间的随机数  }  printf("Original array: ");  printArray(arr, n); // 打印排序前的数组  shellSort(arr, n);  printf("Sorted array: ");  printArray(arr, n); // 打印排序后的数组  printf("Enter the target number to search: ");  scanf("%d", &target);  linearSearchAndCount(arr, n, target); // 线性搜索并打印结果  free(arr);  return 0;  
}

运行结果如下：

2、二分搜索：

#include "date.h" 
#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  // 希尔排序  
void shellSort(int arr[], int n) {  for (int gap = n / 2; gap > 0; gap /= 2) {  for (int i = gap; i < n; i++) {  int temp = arr[i];  int j;  for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)  arr[j] = arr[j - gap];  arr[j] = temp;  }  }  
}  // 线性搜索计算相同元素  
int countAndPrintSame(int arr[], int n, int target) {  int count = 0;  int firstIndex = -1;  for (int i = 0; i < n; i++) {  if (arr[i] == target) {  if (firstIndex == -1) firstIndex = i;  count++;  }  }  if (count > 0) {  printf("Found %d occurrences of %d, first at index %d.\n", count, target, firstIndex);  } else {  printf("Element %d not found in the array.\n", target);  }  return count;  
}  // 二分查找  
int binarySearch(int arr[], int l, int r, int x) {  while (l <= r) {  int m = l + (r - l) / 2;  // 检查mid是否是要找的元素  if (arr[m] == x) return m;  // 如果元素小于mid，则它只可能出现在左子数组中  if (arr[m] < x)  l = m + 1;  // 否则，元素只能出现在右子数组中  else  r = m - 1;  }  // 如果到达这里，元素不在数组中  return -1;  
}  int main() {  int times = getTime();int n, target;  printf("Enter the number of elements: ");  scanf("%d", &n);  int* arr = (int*)malloc(n * sizeof(int));  srand(time(NULL));  printf("Generated array:\n ");  for (int i = 0; i < n; i++) {  arr[i] = rand() % 100; // 生成0到99之间的随机数  printf("%d ", arr[i]);  }  printf("\n");  shellSort(arr, n);  printf("Sorted array: \n");  for (int i = 0; i < n; i++) {  printf("%d ", arr[i]);  }  printf("\n");  printf("Enter the element to search: ");  scanf("%d", &target);  int result = binarySearch(arr, 0, n - 1, target);  if (result != -1) {  printf("Element found at index %d.\n", result);  countAndPrintSame(arr, n, target);  } else {  printf("Element not found.\n");  }  free(arr); return 0;  
}

运行结果如下：

3、插值搜索：

#include "date.h"
#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  
// 希尔排序对整数数组arr进行排序。
// 通过缩小增量序列（gap）逐渐逼近最终的排序状态。 
void shellSort(int arr[], int n) {  for (int gap = n / 2; gap > 0; gap /= 2) {  for (int i = gap; i < n; i++) {  int temp = arr[i];  int j;  for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {  arr[j] = arr[j - gap];  }  arr[j] = temp;  }  }  
}  
// 插值搜索是一种在有序数组中查找特定元素的算法，基于元素值分布的特性来预测目标值可能的位置，从而减少搜索空间。  
int interpolationSearch(int arr[], int n, int x) {  int low = 0, high = n - 1;  while (low <= high && x >= arr[low] && x <= arr[high]) {  if (high == low) {  if (arr[low] == x) return low;  return -1;  }  int pos = low + (((double)(high - low) / (arr[high] - arr[low])) * (x - arr[low]));  if (arr[pos] == x) return pos;  if (arr[pos] < x)  low = pos + 1;  else  high = pos - 1;  }  return -1;  
}  int main() { int times = getTime(); int n, i, searchValue;  printf("Enter the number of elements: ");  scanf("%d", &n);  // 动态分配内存  int *arr = (int*)malloc(n * sizeof(int));  if (!arr) {  printf("Memory allocation failed\n");  return 1;  }  // 生成随机数并填充数组  srand(time(NULL));  for (i = 0; i < n; i++) {  arr[i] = rand() % 100; }  // 打印原始数组printf("Original array: ");  for (i = 0; i < n; i++) {  printf("%d ", arr[i]);  }  printf("\n");  // 对数组进行希尔排序shellSort(arr, n);  // 打印排序后的数组printf("Sorted array: \n");  for (i = 0; i < n; i++) {  printf("%d ", arr[i]);  }  printf("\n");  // 读取要搜索的值并进行插值搜索printf("Enter the value to search: \n");  scanf("%d", &searchValue);  // 插值搜索int index = interpolationSearch(arr, n, searchValue); // 遍历数组以计算并打印目标值的所有出现的位置。 if (index != -1) {  printf("Element found at index %d\n", index);  } else {  printf("Element not found\n");  }  // 如果搜索一个值，只要找到就打印。 // 计算出现次数，需要遍历数组。 int count = 0;  for (i = 0; i < n; i++) {  if (arr[i] == searchValue) {  count++;  printf("Found %d at index %d\n", searchValue, i);  }  }  printf("Total occurrences of %d: %d\n", searchValue, count);  free(arr);  return 0;  
}

运行结果如下：