数据结构习题解析与实验指导第七章(查找)课后算法设计题

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.已知二叉排序树采用二叉链表存储结构，根结点的指针为$T$，链结点的结构为$(lchild,data,rchild)$，其中$lchild$、$rchild$分别指向该结点左右孩子的指针，$data$域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值$\ge 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.已知二叉树$T$的结点形式为$(llink,data,count,rlink)$，在树中查找值为$X$的结点，若找到，则计数(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.假设一棵平衡二叉树的每个结点都表明了平衡因子$b$, 试设计一个算法，求平衡二叉树的高度。

#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.分别写出在散列表中插入和删除关键字为$K$的一个记录的算法，设散列函数为$H$，解决冲突的办法为链地址法。

#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; }