《算法设计及参考答案.doc》由会员分享，可在线阅读，更多相关《算法设计及参考答案.doc（8页珍藏版）》请在金锄头文库上搜索。
1、算法设计1. 设二叉树以二叉链表形式存放。设计非递归算法，实现二叉树的中序遍历。typedef struct BiTnode/*用二叉链表存储二叉树*/ TElemType data; struct BiTnode *lchild,*rchild;BiTnode,*BiTree;Status InOrderTraverse(BiTree root, Status (*visit)(TElemType 2) InitStack(S);/ 初始化栈空间BiTNode* p = root; while(p!=NULL|!StackEmpty(S) /*不是空树*/if(p) Push(S,p); p
2、 = p-lchild;else Pop(S,p); Visist(p-data); p=p-rchild;/*else*/ /*while*/ return OK;/*InOrderTraverse*/2. 设二叉排序树以二叉链表形式存放，设计非递归算法判断二叉排序树中是否存在值为X的结点，若存在，返回其地址，否则返回空指针。typedef struct BiTnode/*用二叉链表存储二叉树*/ int data; struct BiTnode *lchild,*rchild;BSTnode,*BSTree;BSNode* InsertBST(BSTree Tptr，KeyType key
3、) BSTNode *f，*p=TPtr; /p的初值指向根结点while(p) /查找插入位置if(p-key=key) return p;/找到key，返回其地址p=(p-keykey)?p-lchild：p-rchild;/若p-keykey，则在左子树中查找，否则在右子树中查找 /endwhilereturn 0; /InsertBST3. 举例说明二分查找的基本思想，并用类C语言设计算法实现二分查找(折半查找)。二分查找的基本思想是：（设Rlow.high是当前的查找区间） （1）首先确定该区间的中点位置： mid=(low+high)/2; （2）然后将待查的K值与Rmid.key
4、比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下： 若Rmid.keyK，则由表的有序性可知Rmid.n.keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R1.mid-1中，故新的查找区间是左子表R1.mid-1。 类似地，若Rmid.keyK，则要查找的K必在mid的右子表Rmid+1.n中，即新的查找区间是右子表Rmid+1.n。下一次查找是针对新的查找区间进行的。例如：对于序列：05，13，19，21，37，56，64，75，80，88，92，查找21时：初始，查找范围是1-11，mid = (left+ri
5、ght)/2=6; 因为2119;查找范围变为4-5，mid = (left+right)/2=4; 因为21=21;查找成功类C语言设计算法实现二分查找:int BinSearch(SeqList R，KeyType K) /在有序表R1.n中进行二分查找，成功时返回结点的位置，失败时返回零 int low=1，high=n，mid； /置当前查找区间上、下界的初值 while(lowK) high=mid-1; /继续在Rlow.mid-1中查找 else low=mid+1； /继续在Rmid+1.high中查找 return 0； /当lowhigh时表示查找区间为空，查找失败 /Bi
6、nSearh4. 基于图的深度优先搜索策略，设计算法判别以邻接表方式存储的有向图中是否存在由顶点vi到vj的路径(ij)。注意，算法中涉及的图的基本操作必须在此存储结构上实现。int DFSPath(Graph G, int v, int w)/如果v到w有路径返回1，否则返回0;G为有向图的邻接表 for (int vi = 0; vi =0;vi=NextAdjVex(G,v,vi) if(!visitedvi) visitedvi=1;if(vi=w) return 1; /找到路径else return(DFSPath(G,vi,w) ;return 0;5. 什么是二叉排序树?设二叉
7、排序树以二叉链表形式存放设计算法，从大到小输出给定二叉排序树中结点值不小于k的数据元素。二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身又各是一棵二叉排序树。typedef struct BiTnode/*用二叉链表存储二叉树*/ TElemType data; struct BiTnode *lchild,*rchild;BiTnode,*Bi
8、Tree;Status VisitKey(BiTree root, TElemType key)/通过右根左遍历顺序依次输出结点值，遇到小于给定key值的节点停止 InitStack(S);/ 初始化栈空间BiTNode* p = root; while(p!=NULL|!StackEmpty(S) /*不是空子树*/if(p) Push(S,p); p = p-rchild;else Pop(S,p); if(p-data=key) printf(c，q-data); q=q-lchild; else break;/*else*/ /*while*/DestroyStack(S);/释放栈空
9、间 return OK;/*InOrderTraverse*/6. 设二叉树以二叉链表形式存放。利用循环队列，用类C语言设计算法实现二叉树的按层次遍历。Status HierarchyBiTree(BiTree T, Status (*Visit)(TElemType e) LinkQueue *Q; / 保存当前节点的左右孩子的队列 InitQueue(Q); / 初始化队列 if (T = NULL) return ERROR; /树为空则返回 p = T; / 临时保存树根T到指针p中 Visit(p-data); / 访问根节点 if (p-lchild) EnQueue(Q, p-l
10、child); / 若存在左孩子，左孩子进队列 if (p-rchild) EnQueue(Q, p-rchild); / 若存在右孩子，右孩子进队列 while (!QueueEmpty(Q) / 若队列不空，则层序遍历 DeQueue(Q, p); / 出队列 Visit(p-data); / 访问当前节点 if (p-lchild) EnQueue(Q, p-lchild); / 若存在左孩子，左孩子进队列 if (p-rchild) EnQueue(Q, p-rchild); / 若存在右孩子，右孩子进队列 DestroyQueue(Q); / 释放队列空间 return OK;7.
11、（1）什么是完全二叉树?(2)画出6个顶点的完全二叉树。(3)设二叉树以二叉链表形式存放，用类C语言设计算法判断一棵二叉树是否为完全二叉树。深度为k的，有n个结点的二叉树，当且仅当其中每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。/完全二叉树按层次有一个空节点后面不会在出现非空接点。int iscompletetree(BiTree &T,LinkQueue &Q)/是完全二叉树返回1，否则返回0、 BiTree p; p=T; if(!T) return 1; initqueue(Q); enqueue(Q,T); while(！queueempty(Q) dequeue(Q,p); if(p) enqueue(Q,p-lchild); enqueue(Q,p-rchild); if(!p) while(！queueempty(Q) dequeue(Q,p); if(p) /空节点后还有节点 return 0; return 1;8. 用类C语言设计算法将两个有序的单链表合并成一个有序的单链表，要求利用原表的结点空间。typedef struct node keytype key; /关键字域 otherinfotype info; /其它信息域， str
