严蔚敏-数据结构集合习题 下载本文

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->datarlink; else p=p->llink;} if(!p) // 无值为x的结点,插入之

{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

17.[题目分析] 因为二叉树各结点已标明了平衡因子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);//平衡二叉树的高度

} //算法结束

18.[题目分析]二叉排序树的建立问题请参见上面题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

19.本题的分析同第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) {while(t)

{S[++top]=t;t=t->rchild ;} //沿右分枝向下 if(top>0) {t=S[top--];

if(!t->lchild && t->rchild)printf(t->data:4); t=t->lchild; // 去左分枝

}//if

}//while }//算法结束

20.[题目分析]这是一个在单链表中查找结点,在结点内查找给定值的过程,先定义存储结构:

typedef struct node

{int A[m]; //每个结点内含有m个正整数,本例中m为5 struct node *next;//指向下一结点的指针 }LNode,*LinkList; typedef struct

{int j;// 正整数在结点内的序号 struct node *s;// 结点的指针 }rcd;

rcd *LSearch(LinkList head,int n)

//在链表中查找正整数n,若查找成功,返回该结点指针及n在结点中的序号; //否则返回空指针表示失败。 {rcd *R;

P=head->next;// 假定链表带头结点,P指向链表第一元素结点 found=0;

while(P && !found) {for(i=0;i

if(P->A[i]==n) found=1 //查找成功 P=P->next; //下一结点 }

if(P==null)return (null);

else {R.j=i; R.s=P; return (R);} }//LSearch

21.int Search(rectype R[],int n,K)

// 在具有n个元素的有序表R中,顺序查找值为K的结点,查找成功返回其位置, //否则返回-1表示失败 {i=0;

while(i

{if(R[i]==K) return (i);

else if(R[i]>K) return (-1); i++;

}//while

return (-1); }//结束search

在等概率情况下,则查找成功的平均查找长度为(n+1)/2,查找失败的平均查找长度为(n+2)/2(失败位置除小于每一个,还存在大于最后一个)。若查找成功和不成功的概率也相等,则查找成功时和关键字比较的个数的期望值约为(n+1)/4。

22.[题目分析]本题采用中序遍历,将遍历结点与前驱比较,若相同,则不输出并记数。 void BSTPrint(BSTree t,int *count)

//递增序输出二叉排序树中结点的值,滤去重复元素

{if(t)

{BSTPrint(t->lchild); //中序遍历左子树

if(pre==null)pre=t; //pre是当前访问结点的前驱,调用本算法时初值为null else if(pre->key==t->key)*count++;//*count记重复元素,调用本算法时初值为0

else {printf(“M”,t->key);pre=t;} // 前驱后移

BSTPrint(t->rchild); //中序遍历右子树 }//if

}//结束BSTPrint 算法

23.[题目分析]本题算法之一是如上题一样,中序遍历二叉树,在“访问根结点”处判断结点值是否≥x,如是则输出,并记住第一个≥x值结点的指针。这里给出另一个算法,利用二叉排序树的性质,如果根结点的值>=x,则除左分枝中可能有

从根结点开始查找,找到结点值

// 中序输出以t为根的二叉排序树的结点 {if(t){Print(t->lchild); printf(t->data:4); Print(t->rchild); } }

void PrintAllx(BSTree bst,datatype x)

//在二叉排序树bst中,查找值≥x的结点并输出

{p=bst; if(p)

{while(p && p->datarchild;//沿右分枝找第一个值≥x的结点 bst=p; //bst所指结点是值≥x的结点的树的根 if(p)

{f=p; p=p->lchild ;//找第一个值

while(p && p->data≥x)//沿左分枝向下,找第一个值

{f=p;p=p->lchild ;} //f是p的双亲结点的指针,且指向第一个值≥x的结点

if(p) f->lchild=null; //双亲与找到的第一个值

Print(bst);//输出以bst为根的子树

}//while }//内层if(p) }//第一层if(p)

}//PrintAllx

24.[题目分析] 因为T是二叉排序树,则可利用二叉排序树的性质,从根往下查找结点*x。若T的左子树为空,则其中序序号为1,否则为T->lchild->size+1。设T的中序序号为r,其左子女p的中序序号和右子女q的中序序号分别为r-p->rchild->size-1和r+q->lchild->size+1。

int Rank(tree T,node *x)

// 在二叉排序树T上,求结点x的中序序号

{if(T->lchild)r=T->lchild->size+1;else r=1;//根结点的中序序号 while(T)

if(T->key>x->key)//到左子树去查找 {T=T->lchild;

if(T){if(T->rchild)r=r-T->rchild->size-1;else r=r-1;} }

else if(T->keykey)//到右子树去查找 {T=T->rchild;

if(T){if(T->lchild)r=r+T->lchild->size+1;else r=r+1;}

}

else return (r);//返回*x结点的中序序号

return (0); //T树上无x结点。