第七章 查找
1、对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较? 找最大元和最小元至少需要进行n-1次比较。
2、若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试讨论在查找成功两者在等概率时的平均查找长度： 有序表与无序表一样，都为(n+1)/2。 3、为什么有序的单链表不能进行折半查找?
因为折半查找需要随机知道每个数据元素的位置，这是单链表做不到的。
4、对给定的关键字集合，以不同的次序插入初始为空的树中，是否有可能得到同一棵二叉排序树? 不可能。
5、写出顺序表上实现顺序查找的算法，并将监视哨设在高地址端。 int seqsearch(S_TBL tbl, int key)
{
tbl.elem[0].key = key; int i = 0;
for(i = tbl.length; i >= 0 && tbl.elem[i].key != key; --i) { ;
}
return i; }
6、试写出二分查找的递归算法。
int Binarysearch(S_TBL tbl, int low, int high, int key)
{
if(key == tbl.elem[(low+high)/2]) {
printf(“Find succeed!”); return (low+high)/2;
}
else if(key
return Binarysearch(tbl, low, (low+high)/2-1, key);
} else {
return Binarysearch(tbl, (low+high)/2+1, high-1, key); } }
7、在有序表上顺序查找的算法,监视哨设在高下标端。 int Search_Sq(SSTable ST,int key) {
ST.elem[ST.length+1].key = key; for(i = 1;ST.elem[i].key > key;++i); if(i > ST.length || ST.elem[i].key
return ERROR; }
return i; }/*Search_Sq*/
分析:本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为ST.length. 8、折半查找的递归算法。
int Search_Bin_Recursive(SSTable ST,int key,int low,int high) {
if(low > high) {
return 0; /*查找不到时返回*/ }
mid = (low+high)/2;
if(ST.elem[mid].key == key) {
return mid; }
else if(ST.elem[mid].key>key) {
return Search_Bin_Recursive(ST,key,low,mid-1); } else
{
return Search_Bin_Recursive(ST,key,mid+1,high); } }
}//Search_Bin_Recursive
9、折半查找,返回小于或等于待查元素的最后一个结点号。 int Locate_Bin(SSTable ST,int key) {
int *r; r = ST.elem; if(key
return 0;
}
else if(key >= r[ST.length].key) {
return ST.length; } low = 1;
high = ST.length; while(low
mid = (low+high)/2;
if(key >= r[mid].key && key
return mid;
}
else if(key
high = mid; } else {
low = mid;
}
} /*本算法不存在查找失败的情况,不需要return 0*/
}//Locate_Bin
10、分块查找,用折半查找法确定记录所在块,块内采用顺序查找法。 typedef struct {
int maxkey; int firstloc; } Index; typedef struct {
int *elem; int length;
Index idx[MAXBLOCK]; /*每块起始位置和最大元素,其中idx[0]不利用,其内容初始化为{0,0}以利于折半查找*/ int blknum; /*块的数目*/ } IdxSqList; /*索引顺序表类型 */ int Search_IdxSeq(IdxSqList L,int key) {
if(key > L.idx[L.blknum].maxkey) {
return ERROR; /*超过最大元素*/ } low = 1;
high = L.blknum;
found = 0;
while(low
mid = (low+high)/2;
if(key L.idx[mid-1].maxkey) {
found = 1;
}
else if(key > L.idx[mid].maxkey) {
low = mid+1;
} else {
high=mid-1; }
}
i = L.idx[mid].firstloc; /*块的下界*/ j = i + blksize - 1; /*块的上界*/ temp = L.elem[i-1]; /保存相邻元素*/ L.elem[i-1] = key; /*设置监视哨*/
for(k = j;L.elem[k] != key; --k); /*顺序查找*/ L.elem[i-1] = temp; /*恢复元素*/
if(k
return ERROR; /*未找到*/ }
return k; }/*Search_IdxSeq*/
分析:在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失.
11、在有序单循环链表存储结构上的查找算法,假定每次查找都成功。 typedef struct {
LNode *h; /*h指向最小元素*/ LNode *t; /*t指向上次查找的结点*/ } CSList;
LNode *Search_CSList(CSList &L,int key) {
if(L.t->data == key) {
return L.t; }
else if(L.t->data>key) {
for(p = L.h,i = 1;p->data != key;p = p->next,++i);
} else {
for(p = L.t,i = L.tpos;p->data != key;p = p->next,++i); }
L.t = p; /*更新t指针*/ return p; }/*Search_CSList*/
分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3.
12、在有序双向循环链表存储结构上的查找算法,假定每次查找都成功。 typedef struct {
DLNode *pre; int data; DLNode *next; } DLNode; typedef struct {
DLNode *sp; int length;
} DSList; /*供查找的双向循环链表类型 */ DLNode *Search_DSList(DSList &L,int key)
{
p = L.sp;
if(p->data > key) {
while(p->data > key) {
p = p->pre; }
L.sp = p; }
else if(p->data
while(p->data
p = p->next; }
L.sp = p; }
return p; }/*Search_DSList*/
13、判断二叉树T是否二叉排序树,是则返回1,否则返回0。 int last = 0; int flag = 1;
int Is_BSTree(Bitree T) {
if(T->lchild && flag) {
Is_BSTree(T->lchild); }
if(T->data
flag=0; /*与其中序前驱相比较*/ }
last = T->data; if(T->rchild && flag) {
Is_BSTree(T->rchild); }
return flag; }/*Is_BSTree */
14、找到二叉排序树T中小于x的最大元素和大于x的最小元素。 int last = 0;
void MaxLT_MinGT(BiTree T,int x) {
if(T->lchild) {
MaxLT_MinGT(T->lchild,x); /*本算法仍是借助中序遍历来实现*/
}
if(lastdata >= x) /*找到了小于x的最大元素*/
{
printf("a=%d\n",last);
}
if(last data > x) /*找到了大于x的最小元素*/
{
printf("b=%d\n",T->data);
}
last = T->data;
if(T->rchild)
{
MaxLT_MinGT(T->rchild,x);
}
}/*MaxLT_MinGT */
15、从大到小输出二叉排序树T中所有不小于x的元素。
void Print_NLT(BiTree T,int x)
{
if(T->rchild)
{
Print_NLT(T->rchild,x);
}
if(T->data
{
exit(); /*当遇到小于x的元素时立即结束运行*/
}
printf("%d\n",T->data);
if(T->lchild)
{
Print_NLT(T->lchild,x); /*先右后左的中序遍历*/
}
}/*Print_NLT */
16、删除二叉排序树T中所有不小于x元素结点,并释放空间。
void Delete_NLT(BiTree &T,int x)
{
if(T->rchild)
{
Delete_NLT(T->rchild,x);
}
if(T->data
{
exit(); /*当遇到小于x的元素时立即结束运行*/
}
q = T;
T = T->lchild;
free(q); /*如果树根不小于x,则删除树根,并以左子树的根作为新的树根*/ if(T)
{
Delete_NLT(T,x); /*继续在左子树中执行算法*/
}
}/*Delete_NLT */
17、打印输出后继线索二叉排序树T中所有大于a且小于b的元素。 void Print_Between(BiThrTree T,int a,int b)
{
p = T;
while(!p->ltag)
{
p = p->lchild; /*找到最小元素*/
}
while(p && p->data
{
if(p->data > a)
{
printf("%d\n",p->data); /*输出符合条件的元素*/
}
if(p->rtag)
{
p = p->rtag;
}
else
{
p = p->rchild; while(!p->ltag)
{
p=p->lchild;
}
} /*转到中序后继*/ }/*while*/
}/*Print_Between */
第七章 查找
1、对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较? 找最大元和最小元至少需要进行n-1次比较。
2、若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试讨论在查找成功两者在等概率时的平均查找长度： 有序表与无序表一样，都为(n+1)/2。 3、为什么有序的单链表不能进行折半查找?
因为折半查找需要随机知道每个数据元素的位置，这是单链表做不到的。
4、对给定的关键字集合，以不同的次序插入初始为空的树中，是否有可能得到同一棵二叉排序树? 不可能。
5、写出顺序表上实现顺序查找的算法，并将监视哨设在高地址端。 int seqsearch(S_TBL tbl, int key)
{
tbl.elem[0].key = key; int i = 0;
for(i = tbl.length; i >= 0 && tbl.elem[i].key != key; --i) { ;
}
return i; }
6、试写出二分查找的递归算法。
int Binarysearch(S_TBL tbl, int low, int high, int key)
{
if(key == tbl.elem[(low+high)/2]) {
printf(“Find succeed!”); return (low+high)/2;
}
else if(key
return Binarysearch(tbl, low, (low+high)/2-1, key);
} else {
return Binarysearch(tbl, (low+high)/2+1, high-1, key); } }
7、在有序表上顺序查找的算法,监视哨设在高下标端。 int Search_Sq(SSTable ST,int key) {
ST.elem[ST.length+1].key = key; for(i = 1;ST.elem[i].key > key;++i); if(i > ST.length || ST.elem[i].key
return ERROR; }
return i; }/*Search_Sq*/
分析:本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为ST.length. 8、折半查找的递归算法。
int Search_Bin_Recursive(SSTable ST,int key,int low,int high) {
if(low > high) {
return 0; /*查找不到时返回*/ }
mid = (low+high)/2;
if(ST.elem[mid].key == key) {
return mid; }
else if(ST.elem[mid].key>key) {
return Search_Bin_Recursive(ST,key,low,mid-1); } else
{
return Search_Bin_Recursive(ST,key,mid+1,high); } }
}//Search_Bin_Recursive
9、折半查找,返回小于或等于待查元素的最后一个结点号。 int Locate_Bin(SSTable ST,int key) {
int *r; r = ST.elem; if(key
return 0;
}
else if(key >= r[ST.length].key) {
return ST.length; } low = 1;
high = ST.length; while(low
mid = (low+high)/2;
if(key >= r[mid].key && key
return mid;
}
else if(key
high = mid; } else {
low = mid;
}
} /*本算法不存在查找失败的情况,不需要return 0*/
}//Locate_Bin
10、分块查找,用折半查找法确定记录所在块,块内采用顺序查找法。 typedef struct {
int maxkey; int firstloc; } Index; typedef struct {
int *elem; int length;
Index idx[MAXBLOCK]; /*每块起始位置和最大元素,其中idx[0]不利用,其内容初始化为{0,0}以利于折半查找*/ int blknum; /*块的数目*/ } IdxSqList; /*索引顺序表类型 */ int Search_IdxSeq(IdxSqList L,int key) {
if(key > L.idx[L.blknum].maxkey) {
return ERROR; /*超过最大元素*/ } low = 1;
high = L.blknum;
found = 0;
while(low
mid = (low+high)/2;
if(key L.idx[mid-1].maxkey) {
found = 1;
}
else if(key > L.idx[mid].maxkey) {
low = mid+1;
} else {
high=mid-1; }
}
i = L.idx[mid].firstloc; /*块的下界*/ j = i + blksize - 1; /*块的上界*/ temp = L.elem[i-1]; /保存相邻元素*/ L.elem[i-1] = key; /*设置监视哨*/
for(k = j;L.elem[k] != key; --k); /*顺序查找*/ L.elem[i-1] = temp; /*恢复元素*/
if(k
return ERROR; /*未找到*/ }
return k; }/*Search_IdxSeq*/
分析:在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失.
11、在有序单循环链表存储结构上的查找算法,假定每次查找都成功。 typedef struct {
LNode *h; /*h指向最小元素*/ LNode *t; /*t指向上次查找的结点*/ } CSList;
LNode *Search_CSList(CSList &L,int key) {
if(L.t->data == key) {
return L.t; }
else if(L.t->data>key) {
for(p = L.h,i = 1;p->data != key;p = p->next,++i);
} else {
for(p = L.t,i = L.tpos;p->data != key;p = p->next,++i); }
L.t = p; /*更新t指针*/ return p; }/*Search_CSList*/
分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3.
12、在有序双向循环链表存储结构上的查找算法,假定每次查找都成功。 typedef struct {
DLNode *pre; int data; DLNode *next; } DLNode; typedef struct {
DLNode *sp; int length;
} DSList; /*供查找的双向循环链表类型 */ DLNode *Search_DSList(DSList &L,int key)
{
p = L.sp;
if(p->data > key) {
while(p->data > key) {
p = p->pre; }
L.sp = p; }
else if(p->data
while(p->data
p = p->next; }
L.sp = p; }
return p; }/*Search_DSList*/
13、判断二叉树T是否二叉排序树,是则返回1,否则返回0。 int last = 0; int flag = 1;
int Is_BSTree(Bitree T) {
if(T->lchild && flag) {
Is_BSTree(T->lchild); }
if(T->data
flag=0; /*与其中序前驱相比较*/ }
last = T->data; if(T->rchild && flag) {
Is_BSTree(T->rchild); }
return flag; }/*Is_BSTree */
14、找到二叉排序树T中小于x的最大元素和大于x的最小元素。 int last = 0;
void MaxLT_MinGT(BiTree T,int x) {
if(T->lchild) {
MaxLT_MinGT(T->lchild,x); /*本算法仍是借助中序遍历来实现*/
}
if(lastdata >= x) /*找到了小于x的最大元素*/
{
printf("a=%d\n",last);
}
if(last data > x) /*找到了大于x的最小元素*/
{
printf("b=%d\n",T->data);
}
last = T->data;
if(T->rchild)
{
MaxLT_MinGT(T->rchild,x);
}
}/*MaxLT_MinGT */
15、从大到小输出二叉排序树T中所有不小于x的元素。
void Print_NLT(BiTree T,int x)
{
if(T->rchild)
{
Print_NLT(T->rchild,x);
}
if(T->data
{
exit(); /*当遇到小于x的元素时立即结束运行*/
}
printf("%d\n",T->data);
if(T->lchild)
{
Print_NLT(T->lchild,x); /*先右后左的中序遍历*/
}
}/*Print_NLT */
16、删除二叉排序树T中所有不小于x元素结点,并释放空间。
void Delete_NLT(BiTree &T,int x)
{
if(T->rchild)
{
Delete_NLT(T->rchild,x);
}
if(T->data
{
exit(); /*当遇到小于x的元素时立即结束运行*/
}
q = T;
T = T->lchild;
free(q); /*如果树根不小于x,则删除树根,并以左子树的根作为新的树根*/ if(T)
{
Delete_NLT(T,x); /*继续在左子树中执行算法*/
}
}/*Delete_NLT */
17、打印输出后继线索二叉排序树T中所有大于a且小于b的元素。 void Print_Between(BiThrTree T,int a,int b)
{
p = T;
while(!p->ltag)
{
p = p->lchild; /*找到最小元素*/
}
while(p && p->data
{
if(p->data > a)
{
printf("%d\n",p->data); /*输出符合条件的元素*/
}
if(p->rtag)
{
p = p->rtag;
}
else
{
p = p->rchild; while(!p->ltag)
{
p=p->lchild;
}
} /*转到中序后继*/ }/*while*/
}/*Print_Between */