现有给定序列通过c语言实现顺序查找和折半查找,如果是无序的记录集考虑先排序
时间: 2024-05-15 12:13:08 浏览: 8
顺序查找:
```c
int sequential_search(int arr[], int n, int x) {
for(int i=0; i<n; i++) {
if(arr[i] == x) {
return i;
}
}
return -1; //未找到
}
```
折半查找(前提是数组有序):
```c
int binary_search(int arr[], int n, int x) {
int left = 0, right = n - 1;
while(left <= right) {
int mid = (left + right) / 2;
if(arr[mid] == x) {
return mid;
} else if(arr[mid] > x) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1; //未找到
}
```
对于无序的记录集,需要先排序,再进行查找。可以使用C语言标准库中的`qsort`函数对数组进行排序,具体用法可以参考C语言标准库文档。
相关问题
用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语言中的顺序查找代码实现如下:
```
int seqSearch(int arr[], int len, int target)
{
for (int i = 0; i < len; i++)
{
if (arr[i] == target)
return i;
}
return -1; //未找到目标元素,返回-1
}
```
折半查找的实现则需要借助有序序列的特点,其基本思路是将序列分成两个部分,如果目标元素比中间元素小,则在左半部分继续查找;否则在右半部分查找,直到找到目标元素或左右指针重合。C语言中的折半查找代码实现如下:
```
int binarySearch(int arr[], int len, int target)
{
int left = 0, right = len - 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; //未找到目标元素,返回-1
}
```
以上就是C语言中顺序查找和折半查找的代码实现,通过掌握这些算法,在实际编程中可以根据不同的需求来选择合适的算法来查找目标元素。