#include <stdio.h> #include <stdlib.h> // 顺序查找 int sequentialSearch(int *arr, int n, int key) { for (int i = 0; i < n; ++i) { if (arr[i] == key) { return i; } } return -1; } // 二分查找 int binarySearch(int *arr, int n, int key) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == key) { return mid; } else if (arr[mid] < key) { left = mid + 1; } else { right = mid - 1; } } return -1; } int main() { int n, menu, key; printf("请输入查找表的表长n:"); scanf("%d", &n); int *arr = (int *) malloc(n * sizeof(int)); printf("请输入%d个关键字值:", n); for (int i = 0; i < n; ++i) { scanf("%d", &arr[i]); } while (1) { printf("请选择查找方法:\n"); printf("1. 顺序查找\n"); printf("2. 二分查找\n"); printf("3. 退出程序\n"); scanf("%d", &menu); switch (menu) { case 1: printf("请输入要查找的关键值:"); scanf("%d", &key); int index1 = sequentialSearch(arr, n, key); if (index1 == -1) { printf("没有找到该记录\n"); } else { printf("找到了该记录,位置为:%d\n", index1); } break; case 2: printf("请输入要查找的关键值:"); scanf("%d", &key); int index2 = binarySearch(arr, n, key); if (index2 == -1) { printf("没有找到该记录\n"); } else { printf("找到了该记录,位置为:%d\n", index2); } break; case 3: free(arr); return 0; default: printf("无效的选择,请重新输入\n"); break; } } }此程序的算法描述
时间: 2024-03-26 21:37:49 浏览: 12
这是一个简单的查找算法实现,包括顺序查找和二分查找两种方法。程序的算法描述如下:
1. 顺序查找算法:遍历整个查找表,逐个比较每个元素与目标关键字是否相等,如果找到则返回该元素的下标,否则返回 -1。
2. 二分查找算法:在有序的查找表中,将查找区间不断缩小一半,直到找到目标关键字或者查找区间为空为止。具体实现中,每次取查找区间的中间元素与目标关键字比较,如果相等则返回该元素的下标,如果目标关键字小于中间元素,则在左半部分继续查找,否则在右半部分继续查找。如果最终没有找到目标关键字,则返回 -1。
在程序中,首先用户需要输入一个查找表的长度和具体的关键字值,然后可以选择使用顺序查找或二分查找进行查找。如果找到了目标关键字,则输出该元素的下标,否则输出未找到该记录的提示。用户可以反复使用不同的查找方法查找不同的关键字,直到选择退出程序。
相关问题
用c语言编程实现顺序查找、折半查找、二叉排序树和平衡二叉树
好的,以下是顺序查找、折半查找、二叉排序树和平衡二叉树的 C 语言实现:
顺序查找:
```c
#include <stdio.h>
int sequential_search(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {3, 7, 1, 9, 2, 5};
int n = sizeof(arr) / sizeof(int);
int target = 9;
int index = sequential_search(arr, n, target);
if (index == -1) {
printf("未找到 %d\n", target);
} else {
printf("找到 %d,下标为 %d\n", target, index);
}
return 0;
}
```
折半查找:
```c
#include <stdio.h>
int binary_search(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {1, 2, 3, 5, 7, 9};
int n = sizeof(arr) / sizeof(int);
int target = 5;
int index = binary_search(arr, n, target);
if (index == -1) {
printf("未找到 %d\n", target);
} else {
printf("找到 %d,下标为 %d\n", target, index);
}
return 0;
}
```
二叉排序树:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void insert(struct TreeNode **root, int val) {
if (*root == NULL) {
*root = (struct TreeNode *) malloc(sizeof(struct TreeNode));
(*root)->val = val;
(*root)->left = NULL;
(*root)->right = NULL;
return;
}
if (val < (*root)->val) {
insert(&((*root)->left), val);
} else {
insert(&((*root)->right), val);
}
}
void inorder_traversal(struct TreeNode *root) {
if (root == NULL) {
return;
}
inorder_traversal(root->left);
printf("%d ", root->val);
inorder_traversal(root->right);
}
int main() {
struct TreeNode *root = NULL;
insert(&root, 3);
insert(&root, 1);
insert(&root, 5);
insert(&root, 2);
insert(&root, 4);
inorder_traversal(root);
return 0;
}
```
平衡二叉树:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
int height; // 节点高度
};
struct TreeNode *new_node(int val) {
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
node->height = 1;
return node;
}
int max(int a, int b) {
return a > b ? a : b;
}
int get_height(struct TreeNode *node) {
if (node == NULL) {
return 0;
}
return node->height;
}
int get_balance_factor(struct TreeNode *node) {
if (node == NULL) {
return 0;
}
return get_height(node->left) - get_height(node->right);
}
struct TreeNode *left_rotate(struct TreeNode *node) {
struct TreeNode *new_root = node->right;
node->right = new_root->left;
new_root->left = node;
node->height = 1 + max(get_height(node->left), get_height(node->right));
new_root->height = 1 + max(get_height(new_root->left), get_height(new_root->right));
return new_root;
}
struct TreeNode *right_rotate(struct TreeNode *node) {
struct TreeNode *new_root = node->left;
node->left = new_root->right;
new_root->right = node;
node->height = 1 + max(get_height(node->left), get_height(node->right));
new_root->height = 1 + max(get_height(new_root->left), get_height(new_root->right));
return new_root;
}
void insert(struct TreeNode **root, int val) {
if (*root == NULL) {
*root = new_node(val);
return;
}
if (val < (*root)->val) {
insert(&((*root)->left), val);
} else {
insert(&((*root)->right), val);
}
(*root)->height = 1 + max(get_height((*root)->left), get_height((*root)->right));
int balance_factor = get_balance_factor(*root);
if (balance_factor > 1 && val < ((*root)->left)->val) {
// LL
*root = right_rotate(*root);
} else if (balance_factor > 1 && val > ((*root)->left)->val) {
// LR
(*root)->left = left_rotate((*root)->left);
*root = right_rotate(*root);
} else if (balance_factor < -1 && val > ((*root)->right)->val) {
// RR
*root = left_rotate(*root);
} else if (balance_factor < -1 && val < ((*root)->right)->val) {
// RL
(*root)->right = right_rotate((*root)->right);
*root = left_rotate(*root);
}
}
void inorder_traversal(struct TreeNode *root) {
if (root == NULL) {
return;
}
inorder_traversal(root->left);
printf("%d ", root->val);
inorder_traversal(root->right);
}
int main() {
struct TreeNode *root = NULL;
insert(&root, 3);
insert(&root, 1);
insert(&root, 5);
insert(&root, 2);
insert(&root, 4);
inorder_traversal(root);
return 0;
}
```
以上四种算法的时间复杂度分别为:
- 顺序查找:最坏时间复杂度为 O(n),平均时间复杂度为 O(n);
- 折半查找:最坏时间复杂度为 O(log n),平均时间复杂度为 O(log n);
- 二叉排序树:最坏时间复杂度为 O(n),平均时间复杂度为 O(log n);
- 平衡二叉树:最坏时间复杂度为 O(log n),平均时间复杂度为 O(log n)。
利用顺序查找,二分查找,二叉排序树查找实现对整数的查找,c语言完整程序
好的,这里是一个完整的程序,其中包括了顺序查找、二分查找、二叉排序树查找的实现:
```c
#include <stdio.h>
#include <stdlib.h>
/* 顺序查找 */
int sequentialSearch(int arr[], int n, int x) {
for(int i=0; i<n; i++) {
if(arr[i] == x) {
return i;
}
}
return -1; //未找到
}
/* 二分查找 */
int binarySearch(int arr[], int l, int r, int x) {
if(r >= l) {
int mid = l + (r-l)/2;
if(arr[mid] == x) {
return mid;
}
if(arr[mid] > x) {
return binarySearch(arr, l, mid-1, x);
}
return binarySearch(arr, mid+1, r, x);
}
return -1; //未找到
}
/* 二叉排序树 */
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode* insert(TreeNode* root, int val) {
if(root == NULL) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
if(val < root->val) {
root->left = insert(root->left, val);
} else if(val > root->val) {
root->right = insert(root->right, val);
}
return root;
}
TreeNode* search(TreeNode* root, int val) {
if(root == NULL || root->val == val) {
return root;
}
if(val < root->val) {
return search(root->left, val);
}
return search(root->right, val);
}
void inorderTraversal(TreeNode* root) {
if(root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
}
int main() {
int arr[] = {2, 5, 1, 8, 3, 9, 4, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 5;
/* 顺序查找 */
int index = sequentialSearch(arr, n, x);
if(index != -1) {
printf("%d found at index %d by sequential search.\n", x, index);
} else {
printf("%d not found by sequential search.\n", x);
}
/* 二分查找 */
index = binarySearch(arr, 0, n-1, x);
if(index != -1) {
printf("%d found at index %d by binary search.\n", x, index);
} else {
printf("%d not found by binary search.\n", x);
}
/* 二叉排序树 */
TreeNode* root = NULL;
for(int i=0; i<n; i++) {
root = insert(root, arr[i]);
}
inorderTraversal(root);
TreeNode* node = search(root, x);
if(node != NULL) {
printf("\n%d found in the tree by binary search tree!", node->val);
} else {
printf("\n%d not found in the tree by binary search tree!", x);
}
return 0;
}
```
希望可以帮到您!
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)