C语言结构体时间数据插值搜索异常原因排查求助

你遇到的插值搜索功能异常，主要由几个关键问题导致，咱们一步步拆解：

1. 插值搜索的核心前提不满足：数组未排序 #

插值搜索（Interpolation Search）要求待搜索数组必须按搜索键有序排列，但你定义的struct metrhseis s[SIZE]是完全乱序的——比如s[0]是2014-02-13T06:20:00，s[1]跳到2014-02-13T13:50:00，s[2]又回到2014-02-13T06:00:00。这种乱序会让High（当前high索引的时间值）可能小于Low（当前low索引的时间值），mid的计算完全失去意义。

2. mid值计算顺序错误（整数除法精度丢失） #

你的mid计算公式是：

mid = low + (high-low)/(High-Low)*(In-Low);

C语言中整数除法是截断取整，如果High-Low远大于high-low，(high-low)/(High-Low)会直接变成0，导致mid始终等于low，无法正确定位目标。正确的顺序应该先做乘法再做除法，避免精度丢失：

mid = low + ((In - Low) * (high - low)) / (High - Low);

3. 循环逻辑严重错误：break位置错误 #

看你的interpolation_search函数：

while(low<=high ){
    // ... 计算High、Low、mid
    if(strcmp(arr[mid].time,in)>0){
        high=mid-1;
    } else if(strcmp(arr[mid].time,in)<0){
        low=mid+1;
    } else
        printf("Time: %s Temperatura: %d Hum: %d",arr[mid].time ,arr[mid].temp,arr[mid].hum);
    break; // 这里的break每次循环都会执行！
}

这里的break没有被大括号包裹，导致不管有没有找到目标，循环只会执行一次就跳出，根本没机会进行多次搜索迭代。必须把else分支的代码用大括号包裹，并且只在找到目标时break。

4. 其他小问题 #

• temp字段定义为int，但你赋值用了3.0这种浮点数，虽然编译器会自动转换，但如果需要保留小数温度，应该改成float或double类型。
• 搜索失败时，原代码会直接输出arr[mid].temp和arr[mid].hum，但此时mid可能是无效索引，会导致未定义行为，需要增加搜索失败的判断逻辑。

修正后的完整代码 #

我们先给数组按时间排序，再修正mid计算和循环逻辑：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 11

struct metrhseis{
    char time[21];
    int temp;
    int hum;
};

// 提取时间字符串中的数字转为长整型
long long int string_To_long(const char arr[]);
// 插值搜索函数
void interpolation_search(struct metrhseis arr[], char * in);
// qsort排序用的比较函数（按时间字符串升序）
int compare_metrhseis(const void *a, const void *b);

int main(){
    char in[25];
    struct metrhseis s[SIZE];
    
    // 初始化数据
    strcpy(s[0].time, "2014-02-13T06:20:00");
    s[0].temp=3;
    s[0].hum=93;
    strcpy(s[1].time, "2014-02-13T13:50:00");
    s[1].temp=7;
    s[1].hum=66;
    strcpy(s[2].time, "2014-02-13T06:00:00");
    s[2].temp=2;
    s[2].hum=91;
    strcpy(s[3].time, "2014-02-13T03:00:00");
    s[3].temp=3;
    s[3].hum=84;
    strcpy(s[4].time, "2014-02-13T13:00:00");
    s[4].temp=6;
    s[4].hum=62;
    strcpy(s[5].time, "2014-02-13T18:50:00");
    s[5].temp=4;
    s[5].hum=75;
    strcpy(s[6].time, "2014-02-13T13:20:00");
    s[6].temp=6;
    s[6].hum=70;
    strcpy(s[7].time, "2014-02-13T15:00:00");
    s[7].temp=6;
    s[7].hum=56;
    strcpy(s[8].time, "2014-02-13T08:50:00");
    s[8].temp=4;
    s[8].hum=87;
    strcpy(s[9].time, "2014-02-13T21:50:00");
    s[9].temp=4;
    s[9].hum=75;
    strcpy(s[10].time, "2014-02-13T08:00:00");
    s[10].temp=3;
    s[10].hum=88;
    
    // 按时间排序数组（插值搜索的必要前提）
    qsort(s, SIZE, sizeof(struct metrhseis), compare_metrhseis);
    
    // 打印排序后的数组（可选，用于验证）
    printf("Sorted data:\n");
    for (int i = 0; i < SIZE; i++)
        printf("%s | Temp: %d | Hum: %d\n", s[i].time, s[i].temp, s[i].hum);
    
    printf("\nEnter date (format: YYYY-MM-DDTHH:MM:SS): ");
    scanf("%s", in);
    interpolation_search(s, in);
    
    return 0;
}

// 比较函数：按时间字符串升序排列
int compare_metrhseis(const void *a, const void *b){
    const struct metrhseis *m1 = (const struct metrhseis *)a;
    const struct metrhseis *m2 = (const struct metrhseis *)b;
    return strcmp(m1->time, m2->time);
}

void interpolation_search(struct metrhseis arr[], char * in){
    long long int High, Low, In;
    long long int mid;
    int low = 0;
    int high = SIZE - 1;
    int found = 0; // 标记是否找到目标
    
    In = string_To_long(in);
    
    while(low <= high){
        High = string_To_long(arr[high].time);
        Low = string_To_long(arr[low].time);
        
        // 处理所有元素键值相同的情况，避免除以0
        if(High == Low){
            if(strcmp(arr[low].time, in) == 0){
                mid = low;
                found = 1;
                break;
            } else {
                break;
            }
        }
        
        // 正确的mid计算公式：先乘后除，避免整数精度丢失
        mid = low + ((In - Low) * (high - low)) / (High - Low);
        
        // 确保mid在合法索引范围内，防止计算出界
        if(mid < low || mid > high){
            break;
        }
        
        int cmp_result = strcmp(arr[mid].time, in);
        if(cmp_result > 0){
            high = mid - 1;
        } else if(cmp_result < 0){
            low = mid + 1;
        } else {
            // 找到目标，输出结果
            printf("\nFound: Time: %s | Temperature: %d | Humidity: %d\n", arr[mid].time, arr[mid].temp, arr[mid].hum);
            found = 1;
            break;
        }
    }
    
    if(!found){
        printf("\nError: No data found for time %s\n", in);
    }
}

long long string_To_long(const char arr[]) {
    long long int n = 0;
    for (int i = 0; arr[i] != '\0'; i++) {
        char c = arr[i];
        if (c >= '0' && c <= '9')
            n = n * 10 + (c - '0');
    }
    return n;
}

修正后的关键改进点 #

1. 添加qsort排序，确保数组按时间字符串升序排列，满足插值搜索的有序要求。
2. 修正mid计算公式，先执行乘法再除法，避免整数除法导致的精度丢失。
3. 修复循环中的break逻辑，只有找到目标时才跳出循环，否则继续迭代搜索。
4. 增加索引越界检查和除以0的处理，避免未定义行为。
5. 添加搜索失败的提示逻辑，避免输出无效数据。

现在输入2014-02-13T18:50:00，就能正确返回温度4、湿度75了。

内容的提问来源于stack exchange，提问作者user1555