用C语言实现实验： 建立一个记录有序表并实现其上的折半查找。 实验要求： (1) 应用线性表的顺序表实现一个记录有序表； (2) 编码实现在有序表中折半查找某个元素；

在C语言中，你可以使用结构体来创建一个动态数组作为有序列表的基础。首先，我们定义一个结构体来表示我们的记录，并创建一个链表（这里使用单向链表）来存储有序数据。接着，我们将实现折半查找算法。

#include <stdio.h>
#include <stdlib.h>

// 定义记录结构体
typedef struct Record {
    int value;
    struct Record* next; // 链接指针
} Record;

// 初始化链表
Record* createList() {
    Record* head = (Record*)malloc(sizeof(Record));
    head->value = -1; // 空表初始化为无效值
    head->next = NULL;
    return head;
}

// 插入新记录保持有序
void insert(Record** head, int value) {
    Record* new_node = (Record*)malloc(sizeof(Record));
    new_node->value = value;
    new_node->next = *head;
    
    if (*head != NULL && value < (*head)->value)
        (*head)->value = value;
    else {
        while ((*head)->next != NULL && value > (*head)->next->value)
            head = &(*head)->next;
        (*head)->next = new_node;
    }
}

// 折半查找
Record* binarySearch(Record* head, int target) {
    Record* left = head;
    Record* right = head->next;

    while (left != right) {
        int mid_index = (right->value - left->value) / 2 + left->value; // 计算中间位置
        if (mid_index == target)
            return mid_index ? left : right; // 如果找到直接返回

        if (target < mid_index)
            right = mid_index - 1; // 向左移动右边界
        else
            left = mid_index + 1; // 向右移动左边界
    }

    if (left->value == target)
        return left; // 如果未找到，判断最后一个元素是否为目标值

    return NULL; // 没有找到目标值，返回NULL
}

int main() {
    Record* list = createList();
    // 插入一些有序值
    insert(&list, 5);
    insert(&list, 3);
    insert(&list, 7);
    insert(&list, 1);
    insert(&list, 9);

    int search_target = 7;
    Record* found = binarySearch(list, search_target);
    if (found)
        printf("Element %d found at position %p\n", search_target, found);
    else
        printf("Element %d not found in the list.\n", search_target);

    free(list); // 别忘了释放内存
    return 0;
}