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;  
}

运行结果如下：