算法设计及参考答案.doc

算法设计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 = 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) 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比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下： 若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+right)/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时表示查找区间为空，查找失败 /BinSearh4. 基于图的深度优先搜索策略，设计算法判别以邻接表方式存储的有向图中是否存在由顶点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. 什么是二叉排序树?设二叉排序树以二叉链表形式存放设计算法，从大到小输出给定二叉排序树中结点值不小于k的数据元素。二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身又各是一棵二叉排序树。typedef struct BiTnode/*用二叉链表存储二叉树*/ TElemType data; struct BiTnode *lchild,*rchild;BiTnode,*BiTree;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);/释放栈空间 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-lchild); / 若存在左孩子，左孩子进队列 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. （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; /其它信息域， struct node * next; /链表中指针域 recnode; /记录结点类型 typedef recnode * linklist ; /带表头单链表用LINKLIST表示 void mergesort(linklist la,linklist lb,linklist &lc) recnode *p,*q,*s,*r; lc=la; p=la;/P是LA表扫描指针，指向待比较结点的前一位置 q=lb-next;/Q是LB表扫描指针，指向比较的结点 while(p-next&q) if (p-next-keykey) p=p-next; else s=q;q=q-next; s-next=p-next;p-next=s;/将S结点插入到P结点后 p=s; if (!p-next) p-next=q; free(lb);9. 假设表达式由单字母变量和双目四则运算符(+，-，*，/)构成，用类C言设计算法将一个通常书写形式且书写正确的表达式转换为逆波兰式。void Change(char* s1, char* s2) /将字符串s1中的中缀表达式转换为存于字符串s2中的后缀表达式 Stack R; /定义用于暂存运算符的栈 InitStack(R); /初始化栈 Push(R,); /给栈底放入字符，它具有最低优先级0 int i,j; i=0; /用于指示扫描s1串中字符的位置，初值为0 j=0; /用于指示s2串中待存字符的位置，初值为0 char ch=s1i; /ch保存s1串中扫描到的字符，初值为第一个字符 while(ch!=) /顺序处理中缀表达式中的每个字符 if(ch=+|ch=-|ch=*|ch=/) /对于四则运算符，使暂存在栈中的不低于ch优先级的运算符依次出栈并写入到s2中 char w=top(R); while(Precedence(w)=Precedence(ch) / Precedence(w)函数返回运算符形参的优先级 s2j+=w; Pop(R); w=top(R); Push(R,ch); /把ch运算符写入栈中 ch=s1+i; else s2j+=ch;ch=s1+i; /把暂存在栈中的运算符依次出栈并写入到s2串中 while(！Empty(R) s2j+=pop(R); s2j+=0; 求运算符优先级的Precedence函数为： int Precedence(char op)/返回运算符op所对应的优先级数值 switch(op) case +: case -: return 1; /定义加减运算的优先级为1 case *:case /: return 2; /定义乘除运算的优先级为2 case : case (： return 0; /定义在栈中的左括号和栈底字符的优先级为0 10. 基于图的广度优先搜索策略，设计算法判别