发布时间 : 星期四 文章数据结构 第八章 查找表更新完毕开始阅读
48．时间复杂度是判断检索方法的一个重要指标，但不是唯一指标。使用什么检索方法要综合考虑。哈希检索时间O（1），查找速度最快，但需构建哈希函数，进行计算哈希地址，查找时要有解决冲突的方法；二分检索时间O（log2n），需要元素有序且顺序存储，排序操作的时间开销大；顺时检索时间最差为O（n），但对检索表无要求，数据有序无序均可，在数据量较小时使用方便。 返回
五．算法设计题
1． 1． 根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与
其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。 #define true 1 #define false 0 typedef struct node
{datatype data; struct node *llink,*rlink;} *BTree; void JudgeBST（BTree t,int flag）
// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 { if（t!=null && flag）
{ Judgebst（t->llink,flag）；// 中序遍历左子树
if（pre==null）pre=t；// 中序遍历的第一个结点不必判断 else if（pre->data
本题的另一算法是照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下：
int JudgeBST（BTree t）
//判断二叉树t是否是二叉排序树，若是，返回true，否则，返回false {if（t==null）return true；
if（Judgebst（t->llink）&& Judgebst（t->rlink））//若左右子树均为二叉排序树
{m=max（t->llink）；n=min（t->rlink）；//左子树中最大值和右子树中最小值 return （t->data>m && t->data int max（BTree p）//求二叉树左子树的最大值 {if（p==null） return -maxint；//返回机器最小整数 else{while（p->rlink！=null）p=p->rlink； return p->data；} } int min（BTree p）//求二叉树右子树的最小值 {if（p==null） return maxint；//返回机器最大整数 else{while（p->llink！=null）p=p->llink； return p->data；} } 2．[题目分析]借助于分块查找思想，在建立数据顺序表的同时，建立一索引表。数据表中按k个集合分块（元素个数不一定相等），索引表中有两个域，一是各集合最后一个元素在数据表中的位置（一维数组中的下标），二是集合的个数（k）。实现数据运算时，根据给定的二元组（i，x），首先在索引表中找到集合i的位置，然后在数据表中查找x。如查到x ，则查找成功，返回x在数据表中的位置，否则查找失败。若要插入，则将数据表中的数据后移，插入x，同时修改索引表。 typedef struct {datatype data；}rectype； typedef struct {int a[]；//a数组容量够大，存储各集合最后一个数据在数据表中的下标 int k； //集合个数 }index； int SetSearch_Insert（rectype R[]，index id，datatype x，int i） //数据表R，查找第i个集合的元素x，若查找成功，返回其位置，否则将其插入第i个集合 {if（i<1 || i>id.k）printf（“无第%d个集合\\n”，i）；exit（0）；} if（i==1）first=0；else first=id.a[i-1]+1； //first指向第i个集合在数据表的首址 last= id.a[i]；//last是第i个集合在数据表中的末址 for（j=first；j≤last；j++） if（R[j]==x）return （j）；//查找成功 for（j=id.a[id.k]；j>id.a[i]；j--） //查找失败，将x插入数据表 R[j+1]=R[j]；//元素后移 R[j+1]=x； //将x插入到原第i个集合最后一个元素之后。 for（j=i；j≤k；j++）id.a[j]++；//修改索引表中各集合最后一个元素的下标 }结束SetSearch_Insert 由于各集合元素个数不等，各块长度不等且块间无序，索引表中用数组表示，数组中元素值是各集合最后一个元素在数据表中的下标。按本算法插入（2,11.2）和（1,5.3），数据表前后状态如下： 0 插入前 10.2 1.7 4.8 16.2 1.7 8.4 0.5 4.8 4.2 3.6 2.7 5.1 3.9 插入后 10.2 1.7 4.8 16.2 5.3 1.7 8.4 0.5 11.2 4.8 4.2 3.6 2.7 5.1 3.9 3． void Delete（BSTree t，p） // 在二叉排序树t中，删除f所指结点的右孩子（由p所指向）的算法 {if（p->lchild==null）{f->rchild=p->rchild；free（p）；} //p无左子女 else //用p左子树中的最大值代替p结点的值 {q=p->lchild；s=q； while（q->rchild）{s=q；q=q->rchild ；}//查p左子树中序序列最右结点 if（s==p->lchild） //p左子树的根结点无右子女 {p->data=s->data；p->lchild=s->lchild；free（s）；} else{p->data=q->data；s->rchild=q->lchild；free（q）；} } }//Delete 4．[题目分析]上题用被删结点左子树中最大值结点代替被删结点，本题用被删结点右子树中最小值（中序遍历第一个）结点代替被删结点。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 void Delete(BSTree bst,p,fp) //在二叉排序树bst上，删除fp所指结点的左子女（由p所指向）的算法。 {if（!p->lchild）{fp->lchild=p->rchild；free（p）；} //p无左子女 else if（!p->rchild）{fp->lchild=p->lchild；free（p）；} //p无右子女 else // p有左子女和右子女 {q=p->rchild；s=q；//用p右子树中的最小值代替p结点的值 while（q->lchild）{s=q；q=q->lchild ；}//查p右子树中序序列最左结点 if（s==p->rchild） //p右子树的根结点无左子女 {p->data=s->data；p->rchild=s->rchild；free（s）；} else{p->data=q->data；s->lchild=q->rchild；free（q）；} }//Delete 5．[题目分析] 在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。 void Delete(BSTree bst, keytype X) //在二叉排序树bst上，删除其关键字为X的结点。 {BSTree f,p=bst; while (p && p->key!=X) //查找值为X的结点 if (p->key>X) {f=p; p=p->lchild;} else {f=p; p=p->rchild;} if (p==null) {printf(“无关键字为X的结点\\n”); exit(0);} if {p->lchild==null} //被删结点无左子树 if (f->lchild==p) f->lchild=p->rchild;//将被删结点的右子树接到其双亲上 else f->rchild=p->rchild; else {q=p; s=p->lchild; //被删结点有左子树 while (s->rchild !=null) //查左子树中最右下的结点（中序最后结点） {q=s; s=s->rchild;} p->key=s->key; //结点值用其左子树最右下的结点的值代替 if (q==p) p->lchild=s->lchild;//被删结点左子树的根结点无右子女