当前位置：首页 > 数据结构 第八章 查找表
//在散列表HS中，删除关键字K，K的散列地址是i，因解决冲突而将其物理地置于表中j。算法查找关键字K的同义词，将其最后一个同义词移到位置j，并将其同义词的位置置空。
{di=1；last=j；x=(j+di)% m；// 探测地址序列，last记K的最后一个同义词的位置 while（x!=i） //可能要探测一圈
{if（HS[x]==null）break； // 探测到空位置，结束探测 else if（HS[x]%P==i）last=x；// 关键字K的同义词 di=di+1；x=(j+di) % m； // 取下一地址探测 }
HS[j]=HS[last]; HS[last]=null; //将哈希地址last的关键字移到哈希地址j
}
[算法讨论] 由于用线性探测解决冲突，可能发生“二次聚集”（两个第一哈希地址不同的记录争夺同一后继哈希地址）。象上面这样处理后，对于哈希地址为i的记录没有问题了，但由于将地址j置空，有可能截断了其它记录的探测通路。最明显的是哈希地址为j的记录就查不到了。解决的办法是继续调整，直到当前哈希表中的每个记录的查找都是正确的为止。
14．[题目分析]利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于x，则顺左子树向下查找，直到某结点的值小于等于x，则该结点及其左子树均应删除。下面设计一查找算法，确定被删除子树的根结点，再设计一删除算法，删除以被删结点为根的子树。
typedef struct node
{int data； struct node *left，*right; }BiTNode，*BSTree； void DelTree(BSTree r） //非递归删除以r为根的二叉排序树
{BSTree S[]；// 栈，容量足够大，栈中元素是二叉排序树结点的指针 top=0；
while （r!=null || top>0） {while（r!=null） // 沿左分枝向下
{S[++top]=r；r=r->left ；}
if（top>0） // 退栈，沿栈顶结点的右子树向下删除，释放被删除结点空间 {p=S[top--]；r=p->right；free（p）；} }
}// DelTree
void DeleteAllx(BSTree Ｔ，int x）
//在二叉排序树Ｔ中，删除所有小于等于x的结点 {BSTree p=T，q；
while（T && T->data≤x） //根结点的值小于等于x {p=T；T=T->right；p->right=null；
DelTree（p）；} //删除二叉树p,删除持续到“根”结点值大于x或T为空树为止 if (T)
{q=T；p=T->left；
while（p && p->data>x） //沿根结点左分枝向下，查小于等于x的结点 {while（p && p->data>x） { q=p；p=p->left；} // q记p的双亲 if（p） //p结点的值小于等于x
{q->left=p->right；p->right=null；DelTree（p）； } p=q->left；// 再查原p的右子树中小于等于x的结点 }} }// DeleteAllx 15．typedef struct node {datatype data； int count；
struct node * llink，*rlink； }BiTNode，*BSTree；
void Search_InsertX(BSTree t，datatype X）
//在二叉排序树t中查找值为X的结点，若查到，则其结点的count域值增1，否则，
//将其插入到二叉排序树中。
{p=t；
while（p!=null && p->data!=X） //查找值为X的结点，f指向当前结点的双亲
{f=p；
if（p->data
{p=（BiTNode *）malloc(sizeof （BiTNode））； p->data=X；p->llink=null；p->rlink=null；
if（f->data>X）f->llink=p；else f->rlink=p； }
else p->count++；// 查询成功，值域为X的结点的count增1。 }// Search_InsertX
16．[题目分析] 因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分枝向下查找，若b不为0，则沿左（当b=1时）或右（当b=-1时）向下查找。 int Height（BSTree t） // 求平衡二叉树t的高度 {level=0；p=t； while（p）
{level++； // 树的高度增1
if（p->bf<0）p=p->rchild；//bf=-1 沿右分枝向下
//bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存
储定义
else p=p->lchild； //bf>=0 沿左分枝向下
}//while
return （level）；//平衡二叉树的高度
} //算法结束
17．[题目分析]二叉排序树的建立问题请参见上面题3（1）。将二叉排序树上的各整数按降序写入磁盘的问题，要对二叉排序树进行“中序遍历”。这里的“中序遍历”要采取“右根左”。为方便起见，先将整数写入一全局变量数组中，再写入磁盘文件中。
int i=0,a[n];//长度为n的整型数组 void InOrder(BSTree t)
//先右后左的中序遍历二叉排序树t，假定该树t已在本题（1）中生成 {if (t)
{ InOrder(t->rchild) a[i++]=t->key; InOrder(t->lchild) } }//InOrder void SaveToDisk()
//将二叉排序树上的各整数按降序写入磁盘 {FILE *fp;
if ((fp=fopen(“file1.dat”, “wb”))==null) {printf(“file can not open!\\n”);exit(0); }
fwrite(a,sizeof (int),n,fp);//将数组a中的n个整数写入磁盘 fclose(fp);//关闭文件 }//SaveToDisk 18．（1）递归算法
void DecPrint(BSTree t）
//递减序输出二叉排序树t中所有左子树为空右子树非空的结点数据域的值。 {if（t）
{DecPrint(t->rchild)；
if（!t->lchild && t->rchild）printf(t->data：4） DecPrint(t->lchild）； } }//DecPrint （2）非递归算法
void DecPrint(BSTree t）
// 递减序输出二叉排序树t中所有左子女为空右子女非空的结点的值 {BSTree S[]；//S是二叉排序树结点指针的栈，容量足够大 int top=0； while（t || top>0）
本文作者：...共分享92篇相关文档
