二叉排序树
#include "c1.h"
#include "stdio.h"
#include "stdlib.h"
typedef int KeyType;
typedef struct node{
KeyType key;
struct node *lchild,*rchild;
}BiTNode,*BiTree;
void InsertBST(BiTree &bst,KeyType key)
{
BiTNode *t;
if(bst==NULL)
{
t=(BiTree)malloc(sizeof(BiTNode));
t->key=key;
t->lchild=NULL;
t->rchild=NULL;
bst=t;
}
else if(key<bst->key)
InsertBST(bst->lchild,key);
else if(key>bst->key)
InsertBST(bst->rchild,key);
}
void CreateBST(BiTree &bst)
{
int i;
int n;
KeyType key=0;
bst=NULL;
printf("请输入二叉排序树中元素的个数：");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("请输入二叉排序数中的第%d个元素：",i);
scanf("%d",&key);
InsertBST(bst,key);
}
}
BiTree SearchBST(BiTree bst,KeyType key)
{
if(!bst)
return NULL;
else if(bst->key==key)
return bst;
else if(key<bst->key)
return SearchBST(bst->lchild,key);
else
return SearchBST(bst->rchild,key);
}
int main()
{
BiTree bst;
CreateBST(bst);
KeyType temp;
printf("请输入你要查找的元素：");
scanf("%d",&temp);
BiTree T;
T=SearchBST(bst,temp);
if(T==NULL)
printf("\n\n查找失败\n");
else
{
printf("\n\n查找成功\n");
printf("二叉排序树中查到的元素为：%d\n",T->key);
}
}
折半查找和顺序查找
#include "stdio.h"
#include "stdlib.h"
#include "c1.h"
#define N 20
typedef struct
{
int Key;
}ElemType;
typedef struct SSTable {
ElemType *elem;
int length;
}SSTable;
int Search_Seq(SSTable ST,int Key)
{
int i;
ST.elem[0].Key=Key;
for(i=ST.length;ST.elem[i].Key!=Key;i--);
return i;
}
int count;
int Search_Bin(SSTable ST,int Key)
{
int low=1;
int high=ST.length;
int mid;
count=0;
while(low<=high)
{
count++;
mid=(low+high)/2;
if(ST.elem[mid].Key==Key)
return mid;
else if(Key<ST.elem[mid].Key)
high=mid-1;
else
low=mid+1;
}
return 0;
}
int main()
{
SSTable ST;
ST.elem=(ElemType *)malloc(N*sizeof(ElemType));
if(!ST.elem)
exit(0);
int len;
printf("请输入查找表的长度：");
scanf("%d",&len);
int i;
printf("请按顺序输入表中元素：");
for(i=1;i<=len;i++)
scanf("%d",&ST.elem[i].Key);
ST.length=len;
int key=0;
while (key!=-1)
{printf("请输入你要查找的关键字：");
scanf("%d",&key);
if(key==-1)
break;
printf("顺序查找的查找结果为: %d\n",Search_Seq(ST,key));
printf("顺序查找的次数为: %d\n",ST.length-Search_Seq(ST,key)+1);
printf("二分查找的查找结果为：%d\n",Search_Bin(ST,key));
printf("二分查找的次数为：%d\n",count);
}
}。