实验十 查找技术验证实验

查找技术

实验十 查找技术验证实验

一、折半查找验证

1. 实验目的

⑴ 掌握折半查找算法的基本思想； ⑵ 掌握折半查找算法的实现方法； ⑶ 掌握折半查找算法的时间性能。 2. 实验内容

对给定的有序数组（假设长度为n），查找数组中与给定值k相等的元素。 3. 实现提示

折半查找的基本思想为：在有序数组中，取中间元素作为比较对象，若给定值与中间元素相等，则查找成功；若给定值小于中间元素，则在中间元素的左半区继续查找；若给定值大于中间元素，则在中间元素的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无元素，查找失败。为了统计在折半查找过程中元素的比较次数，设置一个计数器count来记载比较次数，算法如下：

折半查找非递归算法BinSearch1 int BinSearch1(int r[ ], int n, int k) { low=1; high=n; count=0; while (low<=high) { mid=(low+high)/2; count++; if (kr[mid]) low=mid+1; else { cout<<\比较次数是：\ return mid;

}

}

cout<<\比较次数是：\ return 0; }

查找技术

二、二叉排序树的建立

1. 实验目的

⑴ 掌握二叉排序树定义和特性； ⑵ 掌握二叉排序树的建立方法； ⑶ 实现基于二叉排序树的查找技术； ⑷ 掌握二叉排序树的查找性能。

2. 实验内容

⑴ 对给定的一组无序序列，建立一棵二叉排序树； ⑵ 对建立的二叉排序树实现查找操作。

3. 实现提示

二叉排序树通常采用二叉链表的形式进行存储，其结点结构定义如下（本章假定数据域均为整数）：

struct BiNode {

int data;

BiNode *lchild, *rchild; };

设计实验用二叉排序树类BiSortTree，包括插入和查找操作。

class BiSortTree

{

public:

BiSortTree(int a[ ], int n); //建立查找集合a[n]的二叉排序树

~ BiSortTree( ); //析构函数，释放二叉排序树中所有结点，同二叉链表的析构函数 void InsertBST(BiNode *root, BiNode *s); //在二叉排序树中插入一个结点s BiNode *SearchBST(BiNode *root, int k); //查找值为k的结点 private:

BiNode *root; //二叉排序树（即二叉链表）的根指针 };

⑴ 设计构造函数，即构造一棵二叉排序树的二叉链表存储，其过程是从空的二叉排序树开始，依次插入一个个结点。

在二叉排序树中插入结点的算法如下：

查找技术

二叉排序树插入算法 void BiSortTree::InsertBST(BiNode *root, BiNode *s) { if (root==NULL) root=s; else if (s->data二叉排序树的构造函数算法如下： data) InsertBST(root->lchild, s); else InsertBST(root->rchild, s); } 二叉排序树构造函数算法 BiSortTree::BiSortTree(int r[ ], int n) { for (i=0; idata=r[i]; s->lchild=s->rchild=NULL; InsertBST(root, s); } } ⑵ 设计查找函数，在二叉排序树上进行查找的过程是一个递归的过程，算法如下： 二叉排序树查找算法SearchBST BiNode * BiSortTree::SearchBST(BiNode *root, int k) { if (root==NULL) return NULL； else if (root->data==k) return root; else if (kdata) return SearchBST(root->lchild, k); else return SearchBST(root->rchild, k); }