C ++程序使用二进制搜索方法查找给定数字的出现次数
这是一个使用BinarySearch方法查找给定数字出现次数的C++程序。
演算法
Begin
function Insert() to insert nodes into the tree:
Arguments:
root, d.
Body of the function:
Create node using data from argument list.
If tree is completely empty, then insert new node as root.
If d = tmp->data, increase the count of that particular node.
If d < tmp->data, move the tmp pointer to the left child.
If d > tmp->data, move the tmp pointer to the right child.
End
Begin
function SearchNode() to search item in the tree:
Arguments:
root, d.
Body of the function:
Run the for loop until temp points to a NULL pointer or data item is found.
If d < tmp->data, move the tmp pointer to the left child.
If d > tmp->data, move the tmp pointer to the right child.
If d = tmp->data, print the item found and it’s count and then return to main.
Else
Print data not found.
End示例
#include<iostream>
using namespace std;
struct nod //declaration of node
{
int data;
int cnt;
nod *l;
nod *r;
};
nod* CreateNod(int d) //creation of new node
{
nod *newnod = new nod;
newnod->data = d;
newnod->cnt = 1;
newnod->l= NULL;
newnod->r = NULL;
return newnod;
}
nod* Insert(nod* root, int d) //perform insertion
{
nod *tmp = CreateNod(d);
nod *t = new nod;
t = root;
if(root == NULL)
root = tmp;
else {
while(t != NULL) {
if(t->data == d) {
t->cnt++;
break;
} else if(t->data < d ) {
if(t->r== NULL) {
t->r= tmp;
break;
}
t = t->r;
} else if(t->data > d) {
if(t->l== NULL) {
t->l= tmp;
break;
}
t = t->l;
}
}
}
return root;
}
void SearchNode(nod *root, int d) //perform searching
{
nod *tmp = new nod;
tmp = root;
while(tmp != NULL) {
if(tmp->data == d) {
cout<<"\nData item "<<d<<" is present "<<tmp->cnt<<" 次数。";
return;
} else if(tmp->data > d)
tmp = tmp->l;
else
tmp = tmp->r;
}
cout<<"\n Data not found";
return;
}
int main() {
char c;
int n, i, a[20] = {8,1,3,6,4,7,10,14,13,7,6,1,26,4,26,20,21,12,10,1}; //take the elements of the array
nod *root = new nod;
root = NULL;
for(i = 0; i < 20; i++)
root = Insert(root, a[i]);
up:
cout<<"\nEnter the Element to be searched: ";
cin>>n;
SearchNode(root, n);
cout<<"\n\nWant to search more...enter choice(y/n)?";
cin>>c;
if(c == 'Y' || c == 'y')
goto up;
return 0;
}输出结果
Enter the Element to be searched: 7 Data item 7 is present 2 次数。 Want to search more...enter choice(y/n)?y Enter the Element to be searched: 6 Data item 6 is present 2 次数。 Want to search more...enter choice(y/n)?y Enter the Element to be searched: 4 Data item 4 is present 2 次数。 Want to search more...enter choice(y/n)?y Enter the Element to be searched: 15 Data not found Want to search more...enter choice(y/n)?n