建设银行的网站用户名,中天建设集团有限公司第一建设公司,地图标注申请入口免费,网站官网域名要多少钱一#xff1a;设计一个折半查找算法#xff0c;求查找到关键字为 k 的记录所需关键字的比较次数。假设 k 与 R[i].key 的比较得到 3 种情况#xff0c;即 kR[i].key#xff0c;kR[i].key 或者 kR[i].key#xff0c;计为 1 次比较#xff08;在教材中讨论关键字比…一设计一个折半查找算法求查找到关键字为 k 的记录所需关键字的比较次数。假设 k 与 R[i].key 的比较得到 3 种情况即 kR[i].keykR[i].key 或者 kR[i].key计为 1 次比较在教材中讨论关键字比较次数时都是这样假设的。
代码
int BinSearch1(RecType R[],int n,KeyType k){int low0,highn-1,mid,count1;while(lowhigh){mid(lowhigh)/2;if(R[mid].keyk){return count;}else if(R[mid].keykey){highmid-1;}else{lowmid1;}count;}count--;//没找到return count;
} 二设计一个算法判断给定的二叉树是否是二叉排序树。假设二叉树中结点关键字 均为正整数且均不相同。
代码
KeyType pre-32767
bool isBST(BSTNode *bt){int islBST,isrBST;if(btNULL){return true;}else{islBST(bt-lchild);//判断左子树if(isBSTfalse) return false;if(bt-keypre) return false;prebt-key;isrBST(bt-rchild);//判断右子树 return isrBST }
}
三设计一个算法在一棵非空二叉排序树 bt 中求出指定关键字为 k 结点的层次。
代码
int Level(BSTNode *bt,KeyType k){int level1;BTNode *pbt;while(p!NULLp-key!k){if(kp-key){//左子树中找 pp-lchild;}else{//右子树中找 pp-rchild;}level;}if(p!NULL){return level;}else{return 0;//没有找到 }
}
四设计一个哈希表 ha[0..m-1]存放 n 个元素哈希函数采用除留余数法 H(key)ke % pp≤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,i1,sign;adradr1k % p; //求哈希函数值sign1;while (ha[adr].key!NULLKEY ha[adr].key!k){adr(adr1sign*i*i) % m;if(sign1){sign-1;}else{//sign-1sign1;i;} }if (ha[adr].keyk){//查找成功return adr;}else{//查找失败return -1;}
}代码
