数据结构-实验8查找的算法(2)

8.3

//实现二叉排序树的基本运算 #include //EOF,NULL #include //atoi( ) #include //cout,cin typedef int Status; typedef struct BTNode {

int key;

struct BTNode *lchild; struct BTNode *rchild; }BTNode;

//定义二叉排序树插入结点的算法 int BSTInsert(BTNode *&T,int k) {

if(T==NULL)

{

T=(BTNode *)malloc(sizeof(BTNode)); T->lchild=T->rchild=NULL; T->key=k; return 1; } else {

if(k==T->key) return 0; else if(kkey)

return BSTInsert(T->lchild, k); else

return BSTInsert(T->rchild, k); } }

//定义二叉排序树的创建算法 BTNode *createBST(int k[],int n) {

BTNode *T; T=NULL;

for(int i=0;i<=n-1;i++){

BSTInsert(T,k[i]); } return T; }

//判断是否为二叉排序树 Status Judge(BTNode *&T) { }

//定义二叉排序树的查找算法

BTNode *BSTSearch(BTNode *&T,int k) {

if(T==NULL) return NULL; else

if(T==NULL)

return 1;

else if((T>T->lchild)&&(Trchild)) { }

else return 0;

Judge(T->lchild); Judge(T->rchild);

{ printf(\ if(T->key==k) return T; else if(kkey) {

return BSTSearch(T->lchild, k); } else {

return BSTSearch(T->rchild, k); } } }

void main() {

int a[50]={4,9,0,1,8,6,3,5,2,7}; BTNode *bt=createBST(a,10);

if(Judge(bt)==0) cout<<\不是二叉排序树\else cout<<\是二叉排序树\cout<<\查找关键字6的查找路径:\BTNode *t=BSTSearch(bt,6); cout<

}

8.4

//实现哈希表的相关运算 #include #define MaxSize 100 //定义最大哈希表长度 #define NULLKEY 0 //定义空关键字值 #define DELKEY -1

//定义被删关键字值

typedef int KeyType;

//关键字类型

typedef char * InfoType; //其他数据类型 typedef struct { KeyType key; //关键字域 InfoType data; //其他数据域

int count;

//探查次数域

} HashTable[MaxSize];

//哈希表类型

void InsertHT(HashTable ha,int *n,KeyType k,int p) 中 {

//将关键字k插入到哈希表