用C语言或C1.输入一组关键字并存储。 2.用不同排序算法对关键字进行排序 3.给一关键字序列,查找给定关键字所在的位序,若不在表中,则返回0。
时间: 2023-12-16 13:06:21 浏览: 79
以下是用C语言实现的代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_KEYWORDS 100
void bubble_sort(char *keywords[], int n);
void selection_sort(char *keywords[], int n);
void insertion_sort(char *keywords[], int n);
int binary_search(char *keywords[], int n, char *key);
int main() {
char *keywords[MAX_KEYWORDS];
int n;
// 输入关键字并存储
printf("请输入关键字数目(不超过%d个):", MAX_KEYWORDS);
scanf("%d", &n);
getchar(); // 吃掉换行符
printf("请输入%d个关键字,以空格分隔:\n", n);
char input[1000];
fgets(input, 1000, stdin);
char *token = strtok(input, " ");
int i = 0;
while (token != NULL) {
keywords[i++] = strdup(token); // 使用strdup复制字符串
token = strtok(NULL, " ");
}
// 用不同排序算法对关键字进行排序
bubble_sort(keywords, n);
printf("冒泡排序结果:\n");
for (int i = 0; i < n; i++) {
printf("%s ", keywords[i]);
}
printf("\n");
selection_sort(keywords, n);
printf("选择排序结果:\n");
for (int i = 0; i < n; i++) {
printf("%s ", keywords[i]);
}
printf("\n");
insertion_sort(keywords, n);
printf("插入排序结果:\n");
for (int i = 0; i < n; i++) {
printf("%s ", keywords[i]);
}
printf("\n");
// 给一关键字序列,查找给定关键字所在的位序
char key[100];
printf("请输入要查找的关键字:");
scanf("%s", key);
int index = binary_search(keywords, n, key);
if (index == 0) {
printf("关键字不在表中\n");
} else {
printf("关键字在第%d个位置\n", index);
}
// 释放内存
for (int i = 0; i < n; i++) {
free(keywords[i]);
}
return 0;
}
// 冒泡排序
void bubble_sort(char *keywords[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (strcmp(keywords[j], keywords[j + 1]) > 0) {
char *temp = keywords[j];
keywords[j] = keywords[j + 1];
keywords[j + 1] = temp;
}
}
}
}
// 选择排序
void selection_sort(char *keywords[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_index = i;
for (int j = i + 1; j < n; j++) {
if (strcmp(keywords[j], keywords[min_index]) < 0) {
min_index = j;
}
}
if (min_index != i) {
char *temp = keywords[i];
keywords[i] = keywords[min_index];
keywords[min_index] = temp;
}
}
}
// 插入排序
void insertion_sort(char *keywords[], int n) {
for (int i = 1; i < n; i++) {
char *key = keywords[i];
int j = i - 1;
while (j >= 0 && strcmp(key, keywords[j]) < 0) {
keywords[j + 1] = keywords[j];
j--;
}
keywords[j + 1] = key;
}
}
// 二分查找
int binary_search(char *keywords[], int n, char *key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
int cmp = strcmp(keywords[mid], key);
if (cmp == 0) {
return mid + 1; // 返回位序(从1开始)
} else if (cmp < 0) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return 0; // 没找到返回0
}
```
注意,上述代码中使用了`strdup`函数来复制字符串,这个函数不是标准C库函数,而是POSIX标准定义的函数。如果编译器不支持该函数,可以自己实现一个:
```
#include <stdlib.h>
#include <string.h>
char *strdup(const char *s) {
size_t len = strlen(s) + 1;
char *p = malloc(len);
if (p != NULL) {
memcpy(p, s, len);
}
return p;
}
```
阅读全文