#include<stdio.h> #include<stdlib.h> int Binary_search(int *s,int length,int key);//二分查找函数 void sort(int *s,int length);//对数组进行排序函数 int main() { int m; int i; int key; int n[100];//待排序数组 scanf("%d",&m); for(i=0;i<m;i++) scanf("%d",&n[i]); sort(n,m); printf("数据递增排序的结果:\n"); for(i=0;i<m;i++) printf("%d ",n[i]); printf("\n"); scanf("%d",&key); int pos=Binary_search(n,m,key); if(pos==-1) printf("没有找到需要查询的数据:\n"); else printf("数据%d的索引位置 %d\n",key,pos); return 0; } void sort(int *s,int length)//对数组进行排序函数 { //改进版的冒泡排序算法 递增排序 int i=length-1;//比较的次数 int j; int t; int flag=1; while(flag) { flag=0; for(j=0;j<i;j++) { if(s[j]>s[j+1]) { t=s[j]; ; s[j+1]=t;//交换数据 flag=1; } } i--; } } int Binary_search(int *s,int length,int key)//二分查找函数 { int L,H,M; L=0; H=length-1; while(L<=H) { ; if(s[M]==key) return M; if(key<s[M]) H= ; else L=M+1; } return -1; }请将下面二分查找程序补充完整。

下面是完整的二分查找程序：

int Binary_search(int *s, int length, int key)
{
    int L, H, M;
    L = 0;
    H = length - 1;
    while (L <= H) {
        M = (L + H) / 2;
        if (s[M] == key)
            return M;
        if (key < s[M])
            H = M - 1;
        else
            L = M + 1;
    }
    return -1;
}

二分查找的思路是：首先将待查找的区间的左端点L设为0，将右端点H设为n-1（n为数组长度），然后计算中间位置M。如果要查找的值等于s[M]，则查找成功，返回M；否则，如果要查找的值小于s[M]，则在左半区间继续查找；如果要查找的值大于s[M]，则在右半区间继续查找。每次查找都将待查找区间缩小一半，直到找到要查找的值或者区间缩小到只有一个元素为止。如果最终没有找到要查找的值，则返回-1表示查找失败。

相关问题

先依次输入元素为简单类型（int、char）的数个数据元素建立顺序存储的线性表，然后以该线性表为查找表进行顺序查找；再用冒泡排序对该线性表按某个关键字值进行排序，在排序之后的线性表之上进行折半查找。用C语言实现

好的，以下是实现代码：

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

// 定义线性表结构体
typedef struct {
    int* data;  // 数据指针
    int length; // 线性表长度
} SqList;

// 初始化线性表
void InitList(SqList* L, int length) {
    L->data = (int*)malloc(sizeof(int) * length); // 申请内存
    L->length = length;
    printf("请输入 %d 个整数：\n", length);
    for (int i = 0; i < length; i++) {
        scanf("%d", &(L->data[i])); // 逐个输入数据元素
    }
}

// 顺序查找
int SequentialSearch(SqList L, int key) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == key) {
            return i; // 找到返回下标
        }
    }
    return -1; // 未找到返回-1
}

// 冒泡排序
void BubbleSort(SqList* L) {
    for (int i = 0; i < L->length - 1; i++) {
        for (int j = 0; j < L->length - i - 1; j++) {
            if (L->data[j] > L->data[j + 1]) {
                int temp = L->data[j];
                L->data[j] = L->data[j + 1];
                L->data[j + 1] = temp;
            }
        }
    }
}

// 折半查找
int BinarySearch(SqList L, int key) {
    int left = 0, right = L.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (L.data[mid] == key) {
            return mid;
        } else if (L.data[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 未找到返回-1
}

int main() {
    SqList L;
    int length, key;

    printf("请输入线性表长度：\n");
    scanf("%d", &length);

    InitList(&L, length);
    printf("请输入要查找的关键字：\n");
    scanf("%d", &key);

    int index = SequentialSearch(L, key);
    if (index != -1) {
        printf("在顺序表中找到了关键字 %d，下标为 %d\n", key, index);
    } else {
        printf("在顺序表中未找到关键字 %d\n", key);
    }

    BubbleSort(&L);
    printf("排序后的线性表为：\n");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n请输入要查找的关键字：\n");
    scanf("%d", &key);

    index = BinarySearch(L, key);
    if (index != -1) {
        printf("在排序后的线性表中找到了关键字 %d，下标为 %d\n", key, index);
    } else {
        printf("在排序后的线性表中未找到关键字 %d\n", key);
    }

    free(L.data); // 释放内存
    return 0;
}

希望可以帮到你！

先依次输入元素为简单类型（int、char）或自定义结构体类型（如订单信息或学生信息或员工信息）的数个数据元素建立顺序存储的线性表，然后①以该线性表为查找表进行顺序查找；②用冒泡排序对该线性表按某个关键字值进行排序，在排序之后的线性表之上进行折半查找。用C语言实现

好的，以下是 C 语言实现的代码示例：

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

// 自定义结构体类型
typedef struct {
    char name[20];
    int age;
} Student;

// 定义线性表结构体
typedef struct {
    void *data;  // 指向数据的指针
    int length;  // 线性表长度
    int size;    // 数据元素大小
} List;

// 初始化线性表
void initList(List *list, int size, int length) {
    list->data = malloc(size * length);
    list->length = 0;
    list->size = size;
}

// 增加元素
void add(List *list, void *data) {
    memcpy((char*)list->data + list->length * list->size, data, list->size);
    list->length++;
}

// 顺序查找
int seqSearch(List *list, void *key, int (*cmp)(const void *, const void *)) {
    for (int i = 0; i < list->length; i++) {
        if (cmp((char*)list->data + i * list->size, key) == 0) {
            return i;
        }
    }
    return -1;
}

// 冒泡排序
void bubbleSort(List *list, int (*cmp)(const void *, const void *)) {
    for (int i = 0; i < list->length - 1; i++) {
        for (int j = 0; j < list->length - i - 1; j++) {
            if (cmp((char*)list->data + j * list->size, (char*)list->data + (j + 1) * list->size) > 0) {
                // 交换相邻两个元素
                char *temp = malloc(list->size);
                memcpy(temp, (char*)list->data + j * list->size, list->size);
                memcpy((char*)list->data + j * list->size, (char*)list->data + (j + 1) * list->size, list->size);
                memcpy((char*)list->data + (j + 1) * list->size, temp, list->size);
                free(temp);
            }
        }
    }
}

// 折半查找
int binarySearch(List *list, void *key, int (*cmp)(const void *, const void *)) {
    int low = 0, high = list->length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (cmp((char*)list->data + mid * list->size, key) == 0) {
            return mid;
        } else if (cmp((char*)list->data + mid * list->size, key) < 0) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

// 比较函数，用于比较两个学生的年龄
int cmp(const void *a, const void *b) {
    return ((Student*)a)->age - ((Student*)b)->age;
}

int main() {
    // 建立顺序存储的线性表
    List list;
    initList(&list, sizeof(Student), 5);
    Student s1 = {"Tom", 18};
    Student s2 = {"Jerry", 20};
    Student s3 = {"Lucy", 19};
    Student s4 = {"Peter", 22};
    Student s5 = {"Mary", 21};
    add(&list, &s1);
    add(&list, &s2);
    add(&list, &s3);
    add(&list, &s4);
    add(&list, &s5);

    // 顺序查找
    Student key1 = {"Jerry", 0};
    int index1 = seqSearch(&list, &key1, cmp);
    if (index1 == -1) {
        printf("未找到该学生\n");
    } else {
        printf("该学生的位置为：%d\n", index1);
    }

    // 冒泡排序
    bubbleSort(&list, cmp);

    // 折半查找
    Student key2 = {"Peter", 0};
    int index2 = binarySearch(&list, &key2, cmp);
    if (index2 == -1) {
        printf("未找到该学生\n");
    } else {
        printf("该学生的位置为：%d\n", index2);
    }

    // 释放内存
    free(list.data);

    return 0;
}

上述代码中，我们使用了 void 指针和 memcpy 函数来实现对不同数据类型的支持。在比较函数 cmp 中，我们比较的是两个学生的年龄大小。您可以根据实际需要修改代码中的数据类型和比较函数。