李春葆《数据结构》-查找-课后习题代码题

一：设计一个折半查找算法，求查找到关键字为 k 的记录所需关键字的比较次数。假设 k 与 R[i].key 的比较得到 3 种情况，即 k==R[i].key，k<R[i].key 或者 k>R[i].key，计为 1 次比较（在教材中讨论关键字比较次数时都是这样假设的）。

代码：

int BinSearch1(RecType R[],int n,KeyType k){int low=0,high=n-1,mid,count=1;while(low<=high){mid=(low+high)/2;if(R[mid].key==k){return count;}else if(R[mid].key>key){high=mid-1;}else{low=mid+1;}count++;}count--;//没找到return count; 
} 

二：设计一个算法，判断给定的二叉树是否是二叉排序树。假设二叉树中结点关键字 均为正整数且均不相同。

代码：

KeyType pre=-32767
bool isBST(BSTNode *bt){int islBST,isrBST;if(bt==NULL){return true;}else{islBST=(bt->lchild);//判断左子树if(isBST==false) return false;if(bt->key<pre)   return false;pre=bt->key;isrBST(bt->rchild);//判断右子树 return isrBST }
}

三：设计一个算法，在一棵非空二叉排序树 bt 中求出指定关键字为 k 结点的层次。

代码：

int Level(BSTNode *bt,KeyType k){int level=1;BTNode *p=bt;while(p!=NULL&&p->key!=k){if(k<p->key){//左子树中找 p=p->lchild;}else{//右子树中找 p=p->rchild;}level++;}if(p!=NULL){return level;}else{return 0;//没有找到 }
} 

四：设计一个哈希表 ha[0..m-1]存放 n 个元素，哈希函数采用除留余数法 H(key)=ke % p（p≤m），解决冲突的方法采用开放定址法中的平方探测法。

（1）设计哈希表的类型。

（2）设计在哈希表中查找指定关键字的算法

#define MaxSize 100 //定义最大哈希表长度
#define NULLKEY -1 //定义空关键字值
#define DELKEY -2 //定义被删关键字值
typedef int KeyType; //关键字类型
typedef char * InfoType; //其他数据类型
typedef struct{KeyType key; //关键字域InfoType data; //其他数据域int count; //探测次数域
} HashTable[MaxSize]; //哈希表类型
int SearchHT1(HashTable ha,int p,int m,KeyType k){//在哈希表中查找关键字 k int adr,adr1,i=1,sign;adr=adr1=k % p; //求哈希函数值sign=1;while (ha[adr].key!=NULLKEY && ha[adr].key!=k){adr=(adr1+sign*i*i) % m;if(sign==1){sign=-1;}else{//sign==-1sign=1;i++;} }if (ha[adr].key==k){//查找成功return adr;}else{//查找失败return -1;}
}

代码：