算法设计及参考答案.pdfVIP

算法设计

1.设二叉树以二叉链表形式存放。设计非递归算法，实现二叉树的中序遍历。

typedefstructBiTnode{/*用二叉链表存储二叉树*/

TElemTypedata;

structBiTnode*lchild,*rchild;

}BiTnode,*BiTree;

StatusInOrderTraverse(BiTreeroot,Status(*visit)(TElemType2)){

InitStack(S);//初始化栈空间

BiTNode*p=root;

while(p!=NULL||!StackEmpty(S)){/*不是空树*/

if(p){Push(S,p);p=p-lchild;}

else{

Pop(S,p);

Visist(p-data);

p=p-rchild;

}/*else*/

}/*while*/

returnOK;

}/*InOrderTraverse*/

2.设二叉排序树以二叉链表形式存放，设计非递归算

法判断二叉排序树中是否存在值为X的结点，若存在，

返回其地址，否则返回空指针。

typedefstructBiTnode{/*用二叉链表存储二叉树*/

intdata;

structBiTnode*lchild,*rchild;

}BSTnode,*BSTree;

BSNode*InsertBST(BSTreeTptr，KeyTypekey)

{

BSTNode*f，*p=TPtr;//p的初值指向根结点

while(p){//查找插入位置

if(p-key==key)returnp;//找到key，返回其地址

p=(p-keykey)?p-lchild：p-rchild;

//若p-keykey，则在左子树中查找，否则在右子树中查找

}//endwhile

return0;

}//InsertBST

1

3.举例说明二分查找的基本思想，

并用类C语言设计算法实现二分查找(折半查找)。

二分查找的基本思想是：（设R[low..high]是当前的查找区间）

（1）首先确定该区间的中点位置：

mid=(low+high)/2;

（2）然后将待查的K值与R[mid].key比较：

若相等，则查找成功并返回此位置，

否则须确定新的查找区间，继续二分查找，具体方法如下：

①若R[mid].keyK，则由表的有序性可知R[mid..n].

keys均大于K，因此若表中存在关键字等于K的结点，则该结点

必定是在位置mid左边的子表R[1..mid-1]中，故新的查找区间

是左子表R[1..mid-1]。

②类似地，若R[mid].keyK，则要查找的K必在mid的右

子表R[mid+1..n]中，即新的查找区间是右子表R[mid+1..n]。

下一次查找是针对新的查找区间进行的。

例如：

对于序列：05，13，19，21，37，56，64，75，80，88，92，查找21时：

初始，查找范围是1-11，mid=(left+right)/2=6;因为2156;

查找范围变为1-5，mid=(left+right)/2=3;因为2119;

查找范围变为4-5，mid=(left+right)/2=4;因为21==21;查找成功

类C语言设计算法实现二分查找:

intBinSearch(SeqListR，KeyTypeK)

{//在有序表R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零

intlow=1，high=n，mid；//置当前查找区间上、下界的初值

whil