算法设计: 1.实现线性表的二分(折半)查找算法。 2.实现树表的二叉排序树的创建、插入、删除、查找算法。 3*.实现散列表的散列查找方法。C语言
时间: 2024-02-06 21:11:57 浏览: 74
1. 线性表的二分(折半)查找算法
```c
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 没有找到目标元素
}
```
2. 树表的二叉排序树的创建、插入、删除、查找算法
```c
// 二叉排序树结点定义
typedef struct BSTNode {
int data;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode;
// 创建二叉排序树
BSTNode *createBST(int arr[], int n) {
if (n == 0) return NULL;
BSTNode *root = (BSTNode *)malloc(sizeof(BSTNode));
root->data = arr[0];
root->left = root->right = NULL;
for (int i = 1; i < n; i++) {
BSTNode *p = root, *q = NULL;
while (p) {
q = p;
if (arr[i] < p->data) {
p = p->left;
} else {
p = p->right;
}
}
BSTNode *newNode = (BSTNode *)malloc(sizeof(BSTNode));
newNode->data = arr[i];
newNode->left = newNode->right = NULL;
if (arr[i] < q->data) {
q->left = newNode;
} else {
q->right = newNode;
}
}
return root;
}
// 插入结点
void insertBST(BSTNode **root, int data) {
if (*root == NULL) {
BSTNode *newNode = (BSTNode *)malloc(sizeof(BSTNode));
newNode->data = data;
newNode->left = newNode->right = NULL;
*root = newNode;
return;
}
if (data < (*root)->data) {
insertBST(&(*root)->left, data);
} else {
insertBST(&(*root)->right, data);
}
}
// 删除结点
BSTNode *deleteBST(BSTNode *root, int data) {
if (root == NULL) return NULL;
if (data < root->data) {
root->left = deleteBST(root->left, data);
} else if (data > root->data) {
root->right = deleteBST(root->right, data);
} else {
if (root->left == NULL) {
BSTNode *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
BSTNode *temp = root->left;
free(root);
return temp;
} else {
BSTNode *temp = root->right;
while (temp->left) {
temp = temp->left;
}
root->data = temp->data;
root->right = deleteBST(root->right, temp->data);
}
}
return root;
}
// 查找结点
BSTNode *searchBST(BSTNode *root, int data) {
if (root == NULL || root->data == data) {
return root;
}
if (data < root->data) {
return searchBST(root->left, data);
} else {
return searchBST(root->right, data);
}
}
```
3. 散列表的散列查找方法
```c
#define MAX_SIZE 1000
typedef struct {
int key;
int value;
} KeyValuePair;
typedef struct {
KeyValuePair data;
int isDeleted;
} HashTableItem;
typedef struct {
HashTableItem items[MAX_SIZE];
int count;
} HashTable;
// 散列函数
int hash(int key) {
return key % MAX_SIZE;
}
// 插入元素
void insert(HashTable *table, KeyValuePair item) {
int index = hash(item.key);
while (table->items[index].isDeleted == 0) {
index = (index + 1) % MAX_SIZE; // 线性探测法解决冲突
}
table->items[index].data = item;
table->items[index].isDeleted = 0;
table->count++;
}
// 删除元素
void remove(HashTable *table, int key) {
int index = hash(key);
while (table->items[index].isDeleted == 0) {
if (table->items[index].data.key == key) {
table->items[index].isDeleted = 1;
table->count--;
return;
}
index = (index + 1) % MAX_SIZE;
}
}
// 查找元素
KeyValuePair *find(HashTable *table, int key) {
int index = hash(key);
while (table->items[index].isDeleted == 0) {
if (table->items[index].data.key == key) {
return &table->items[index].data;
}
index = (index + 1) % MAX_SIZE;
}
return NULL;
}
```
阅读全文