.png)
Các thuật toán tìm kiếm
#include<conio.h>#include<iostream>
#include<math.h>
#include<iomanip>
#define Max 10
using namespace std;
struct Node{
int key;
Node *left,*right;
} *T;
void insert(int x,Node *&T)
{
if(T==NULL){
T=new Node;
T->left=NULL;
T->right=NULL;
T->key=x;
}
else if(T->key<x) insert(x,T->right);
else insert(x,T->left);
}
void nhapcay(Node *&T,int a[],int n)
{
for(int i=0;i<n;i++)
{
insert(a[i],T);
}
}
void hienpre(Node *T)
{
if(T!=NULL){
cout<<T->key<<setw(5);
hienpre(T->left);
hienpre(T->right);
}
}
void nhap(int a[],int &n)
{
cout<<"nhap vao so phan tu cua mang : "; cin>>n;
for(int i=0;i<n;i++){
cout<<"a["<<i<<"] = ";
cin>>a[i];
}
}
void hien(int a[],int n)
{
for(int i=0;i<n;i++)
cout<<a[i]<<setw(5);
cout<<"\n";
}
int tktt(int x,int a[],int n) //tim kiem tuan tu bang vong lap
{
a[n]=x;int i=0;
while(a[i]!=x) i++;
if(i<n) return 1;
else return 0;
}
int tktt2(int x,int a[],int n)//tim kiem tuan tu su dung de quy
{
if(n<0) return 0;
if(a[n]==x) return 1;
else tktt2(x,a,n-1);
}
int tktt3(int x,int a[],int n) //tim kiem trong day da sap tang
{
a[n]=x; int i=0;
while(a[i]<x) i++;
if(i<n&&a[i]==x) return 1;
else return 0;
}
int tknp(int x,int a[],int n)
{
int l=0,r=n-1,m;
while(l<=r){
m=l+r/2;
if(a[m]==x) return 1;
if(a[m]>x) r=m-1;
else l=m+1;
}
return 0;
}
int tknp2(int x,int a[],int l,int r)
{
if(l>r) return 0;
int k;
k=(l+r);
if(a[k]==x) return 1;
if(a[k]>x) return tknp2(x,a,l,k-1);
else return tknp2(x,a,k+1,l);
}
int tkcnp(int x,Node *T) //tim kiem su dung vong lap
{
while(T!=NULL){
if(T->key==x) return 1;
if(T->key<x) T=T->right;
else T=T->left;
}
return 0;
}
int tkcnp2(int x,Node *T) //tim kiem de quy
{
if(T==NULL) return 0;
if(T->key==x) return 1;
else if(T->key<x) tkcnp2(x,T->right);
else tkcnp2(x,T->left);
}
int main()
{
int a[Max],n,x;
nhap(a,n);
hien(a,n);
// nhapcay(T,a,n);
// hienpre(T);
cout<<"\nNhap x muon tim :"; cin>>x;
//if(tktt(x,a,n)==1) cout<<"tim thay x trong mang"; else cout<<"tim mai roi ma khong thay x dau ca !!!";
//if(tktt2(x,a,n)==1) cout<<"tim thay x trong mang"; else cout<<"tim mai roi ma khong thay x dau ca !!!";
//if(tktt3(x,a,n)==1) cout<<"tim thay x trong mang "; else cout<<"tim mai roi ma khong thay x dau ca !!!";
//if(tknp(x,a,n)==1) cout<<"tim thay x trong mang "; else cout<<"tim mai roi ma khong thay x dau ca !!!";
if(tknp2(x,a,0,n-1)==1) cout<<"tim thay x trong mang "; else cout<<"tim mai roi ma khong thay x dau ca !!!";
//if(tkcnp(x,T)==1) cout<<"tim thay x trong mang "; else cout<<"tim mai roi ma khong thay x dau ca !!!";
//if(tkcnp2(x,T)==1) cout<<"tim thay x trong mang "; else cout<<"tim mai roi ma khong thay x dau ca !!!";
getch();
}
0 nhận xét: