数据结构习题解析与实验指导第七章(查找)课后算法设计题
·
1.试写出折半查找的递归算法。
#include <iostream>
using namespace std;
int find(int data[], int start, int end, int k) {
if (start < end) {
int mid = (start + end) / 2;
if (data[mid] == k) {
return mid;
}
else if (k < data[mid]) {
return find(data, start, mid - 1, k);
}
else {
return find(data, mid + 1, end, k);
}
}
return -1;
}
int main() {
int data[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
cout << find(data, 0, 10, 3) << endl;
cout << find(data, 0, 10, 10) << endl;
cout << find(data, 0, 10, 1) << endl;
cout << find(data, 0, 10, 11) << endl;
return 0;
}
2.试写出一个判定给定二叉树是否为二叉排序树的算法。
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int data = 0, Node* left = 0, Node* right = 0) :
data(data),
left(left),
right(right)
{
}
};
void insert(Node* & biSortTree, int num) {
if (biSortTree == 0) {
biSortTree = new Node(num);
}
else if (num < biSortTree->data) {
insert(biSortTree->left, num);
}
else {
insert(biSortTree->right, num);
}
}
Node* find(Node* biSortTree, int num) {
if (biSortTree != 0) {
if (biSortTree->data == num) {
return biSortTree;
}
else if (num < biSortTree->data) {
return find(biSortTree->left, num);
}
else {
return find(biSortTree->right, num);
}
}
return 0;
}
/*
void delete(Node* biSortTree, int num){
....
}
*/
void release(Node* tree) {
if (tree != 0) {
release(tree->left);
release(tree->right);
delete tree;
}
}
/*题目要求的算法，本质是二叉排序树的遍历*/
bool isBiSortTree(Node* tree) {
if (tree != 0) {
return isBiSortTree(tree->left) && isBiSortTree(tree->right) &&
(tree->left != 0 ? tree->left->data < tree->data : true) &&
(tree->right != 0 ? tree->right->data >= tree->data : true);
}
return true;
}
int main() {
Node* biSortTree = 0;
insert(biSortTree, 18);
insert(biSortTree, 89);
insert(biSortTree, 42);
insert(biSortTree, 28);
insert(biSortTree, 13);
insert(biSortTree, 96);
insert(biSortTree, 35);
insert(biSortTree, 25);
insert(biSortTree, 7);
insert(biSortTree, 85);
cout << find(biSortTree, 25)->data << endl;
cout << find(biSortTree, 42)->data << endl;
cout << find(biSortTree, 6) << endl;
cout << "isBST: " << isBiSortTree(biSortTree) << endl;
Node* plainTree = new Node(0, new Node(1, new Node(3), new Node(4)), new Node(2));
cout << "isBST: " << isBiSortTree(plainTree) << endl;
release(biSortTree);
release(plainTree);
return 0;
}
3.已知二叉排序树采用二叉链表存储结构，根结点的指针为TTT，链结点的结构为(lchild,data,rchild)(lchild, data, rchild)(lchild,data,rchild)，其中lchildlchildlchild、rchildrchildrchild分别指向该结点左右孩子的指针，datadatadata域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值≥x\ge x≥x的结点的数据。要求先找到第一个满足条件的结点后，再依次输出其它满足条件的结点。
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int data = 0, Node* left = 0, Node* right = 0) :
data(data),
left(left),
right(right)
{
}
};
void insert(Node* & biSortTree, int num) {
if (biSortTree == 0) {
biSortTree = new Node(num);
}
else if (num < biSortTree->data) {
insert(biSortTree->left, num);
}
else {
insert(biSortTree->right, num);
}
}
Node* find(Node* biSortTree, int num) {
if (biSortTree != 0) {
if (biSortTree->data == num) {
return biSortTree;
}
else if (num < biSortTree->data) {
return find(biSortTree->left, num);
}
else {
return find(biSortTree->right, num);
}
}
return 0;
}
/*
void delete(Node* biSortTree, int num){
....
althought it is easy, I am unwilling to write.
}
*/
void release(Node* tree) {
if (tree != 0) {
release(tree->left);
release(tree->right);
delete tree;
}
}
/*题目要求的算法: 本质是一个中序遍历*/
void showAllGreatEqualX(Node* biSortTree, int x) {
if (biSortTree != 0) {
showAllGreatEqualX(biSortTree->left, x);
if(biSortTree->data >= x)
cout << biSortTree->data << " ";
showAllGreatEqualX(biSortTree->right, x);
}
}
int main() {
Node* biSortTree = 0;
insert(biSortTree, 18);
insert(biSortTree, 89);
insert(biSortTree, 42);
insert(biSortTree, 28);
insert(biSortTree, 13);
insert(biSortTree, 96);
insert(biSortTree, 35);
insert(biSortTree, 25);
insert(biSortTree, 7);
insert(biSortTree, 85);
showAllGreatEqualX(biSortTree, 35);
release(biSortTree);
return 0;
}
4.已知二叉树TTT的结点形式为(llink,data,count,rlink)(llink, data, count, rlink)(llink,data,count,rlink)，在树中查找值为XXX的结点，若找到，则计数(count)加1；否则作为新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
#include <iostream>
#include <stack>
using namespace std;
struct Node {
int data;
int count;
Node* llink;
Node* rlink;
Node(int data = 0, Node* llink = 0, Node* rlink = 0) :
data(data),
llink(llink),
rlink(rlink),
count(1)
{
}
};
/*题目要求的算法*/
void insert(Node*& BST, int num) {
Node** node = &BST;
while (true) {
if ((*node) == 0) {
*node = (new Node(num));
break;
}
else if ((*node)->data == num) {
(*node)->count++;
break;
}
else if (num < (*node)->data) {
node = &((*node)->llink);
}
else {
node = &((*node)->rlink);
}
}
}
void display(Node* BST) {
if (BST != 0) {
display(BST->llink);
cout << "(" << BST->data << ", " << BST->count << ")" << endl;
display(BST->rlink);
}
}
void release(Node* tree) {
if (tree != 0) {
release(tree->llink);
release(tree->rlink);
delete tree;
}
}
int main() {
Node* BST = 0;
insert(BST, 67);
insert(BST, 6);
insert(BST, 32);
insert(BST, 99);
insert(BST, 81);
insert(BST, 47);
insert(BST, 12);
insert(BST, 77);
insert(BST, 6);
insert(BST, 76);
insert(BST, 56);
insert(BST, 99);
insert(BST, 47);
insert(BST, 47);
display(BST);
release(BST);
return 0;
}
5.假设一棵平衡二叉树的每个结点都表明了平衡因子bbb, 试设计一个算法，求平衡二叉树的高度。
#include <iostream>
#include <stack>
using namespace std;
struct Node {
int data;
int factor; //平衡因子
Node* left;
Node* right;
Node(int data = 0, int factor = 0, Node* left = 0, Node* right = 0) :
data(data),
left(left),
right(right),
factor(factor)
{
}
};
/*题目要求的算法*/
int level(Node* AVL) {
if (AVL != 0) {
if (AVL->factor <= 0) { //说明右边可能更高
return 1 + level(AVL->right);
}
else {
return 1 + level(AVL->left);
}
}
return 0;
}
void release(Node* tree) {
if (tree != 0) {
release(tree->left);
release(tree->right);
delete tree;
}
}
int main() {
Node* n1 = new Node(0, -1);
Node* n2 = new Node(0, 1);
Node* n3 = new Node(0, -1);
Node* n4 = new Node(0, 0);
Node* n5 = new Node(0, 0);
Node* n6 = new Node(0, 1);
Node* n7 = new Node(0, 0);
Node* AVL = n1;
n1->left = n2;
n1->right = n3;
n2->left = n4;
n3->left = n5;
n3->right = n6;
n6->left = n7;
cout << "level: " << level(AVL) << endl;
release(AVL);
return 0;
}
6.分别写出在散列表中插入和删除关键字为KKK的一个记录的算法，设散列函数为HHH，解决冲突的办法为链地址法。
#include <iostream>
using namespace std;
template<int size>
class HashTable {
public:
static struct Node {
int key;
int value;
Node* next;
Node(int key = 0, int value = 0, Node* next = 0) :
key(key),
value(value),
next(next)
{
}
};
explicit HashTable() {
}
virtual ~HashTable() {
for (int i = 0; i < size; i++) {
Node* head = &table[i];
while (head->next != 0)
{
Node* node = head->next;
head->next = head->next->next;
delete node;
}
}
}
int hash(int k) {
return k % size;
}
void set(int k, int v) {
Node* head = &table[hash(k)];
Node* p = head->next;
while (p != 0) {
if (p->key == k) {
p->value = v;
return;
}
p = p->next;
}
head->next = new Node(k, v, head->next);
}
void remove(int k) {
Node* head = &table[hash(k)];
Node* p = head;
while (p->next != 0) {
if (p->next->key == k) {
Node* temp = p->next;
p->next = p->next->next;
delete temp;
return;
}
p = p->next;
}
}
Node* get(int k) {
Node* head = &table[hash(k)];
Node* p = head->next;
while (p != 0) {
if (p->key == k) {
return p;
}
p = p->next;
}
return 0;
}
private:
Node table[size];
HashTable(const HashTable&);
HashTable& operator=(const HashTable&);
};
int main() {
HashTable<5> table;
table.set(1, 11);
table.set(2, 22);
table.set(3, 33);
table.set(4, 44);
table.set(5, 55);
table.set(6, 66);
table.set(7, 77);
table.set(8, 88);
table.set(9, 99);
table.set(10, 100);
cout << table.get(6)->value << endl;
table.set(6, 666);
cout << table.get(6)->value << endl;
table.remove(6);
cout << table.get(6) << endl;
cout << table.get(1)->value << endl;
table.set(1, 111);
cout << table.get(1)->value << endl;
table.remove(1);
cout << table.get(1) << endl;
return 0;
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
3
0- 0
已为社区贡献3条内容
所有评论(0)