算法设计及参考答案

1算法设计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，则在左子树中查找，否则在右子树中查找}//endwhilereturn0;}//InsertBST23.举例说明二分查找的基本思想，并用类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；//置当前查找区间上、下界的初值while(low=high){//当前查找区间R[low..high]非空mid=(low+high)/2；if(R[mid].key==K)returnmid；//查找成功返回if(R[mid].kdyK)high=mid-1;//继续在R[low..mid-1]中查找elselow=mid+1；//继续在R[mid+1..high]中查找}return0；//当lowhigh时表示查找区间为空，查找失败}//BinSearh34.基于图的深度优先搜索策略，设计算法判别以邻接表方式存储的有向图中是否存在由顶点vi到vj的路径(ij)。注意，算法中涉及的图的基本操作必须在此存储结构上实现。intDFSPath(GraphG,intv,intw){//如果v到w有路径返回1，否则返回0;G为有向图的邻接表for(intvi=0;viG.vexnum;++vi)visited[vi]=FALSE;visited[v]=TRUE;for(vi=FirstAdjVex(G,v);vi=0;vi=NextAdjVex(G,v,vi)){if(!visited[vi]){visited[vi]=1;if(vi==w)return1;//找到路径else{return(DFSPath(G,vi,w));}}return0;}5.什么是二叉排序树?设二叉排序树以二叉链表形式存放设计算法，从大到小输出给定二叉排序树中结点值不小于k的数据元素。二叉排序树(BinarySortTree)又称二叉查找(搜索)树(BinarySearchTree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；③左、右子树本身又各是一棵二叉排序树。typedefstructBiTnode{/*用二叉链表存储二叉树*/TElemTypedata;structBiTnode*lchild,*rchild;}BiTnode,*BiTree;StatusVisitKey(BiTreeroot,TElemTypekey){//通过右根左遍历顺序依次输出结点值，遇到小于给定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;4}elsebreak;}/*else*/}/*while*/DestroyStack(S);//释放栈空间returnOK;}/*InOrderTraverse*/6.设二叉树以二叉链表形式存放。利用循环队列，用类C语言设计算法实现二叉树的按层次遍历。StatusHierarchyBiTree(BiTreeT,Status(*Visit)(TElemTypee)){LinkQueue*Q;//保存当前节点的左右孩子的队列InitQueue(Q);//初始化队列if(T==NULL)returnERROR;//树为空则返回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);//释放队列空间returnOK;}7.（1）什么是完全二叉树?(2)画出6个顶点的完全二叉树。(3)设二叉树以二叉链表形式存放，用类C语言设计算法判断一棵二叉树是否为完全二叉树。深度为k的，有n个结点的二叉树，当且仅当其中每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。5//完全二叉树按层次有一个空节点后面不会在出现非空接点。intiscompletetree(BiTree&T,LinkQueue&Q)//是完全二叉树返回1，否则返回0、{BiTreep;p=T;if(!T)return1;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)//空节点后还有节点{return0;}}}}return1;}68.用类C语言设计算法将两个有序的单链表合并成一个有序的单链表，要求利用原表的结点空间。typedefstructnode{keytypekey;//关键字域otherinfotypeinfo;//其它信息域，structnode*next;//链表中指针域}recnode;//记录结点类型typedefrecnode*linklist;//带表头单链表用LINKLIST表示voidmergesort(linklistla,linklistlb,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-key=q-key)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);}79.假设表达式由单字母变量和双目四则运算符(+，-，*，/)构成，用类C言设计算法将一个通常书写形式且书写正确的表达式转换为逆波兰式。voidChange(char*s1,char*s2)//将字符串s1中的中缀表达式转换为存于字符串s2中的后缀表达式{StackR;//定义用于暂存运算符的栈InitStack(R);//初始化栈Push(R,'@');//给栈底放入'@'字符，它具有最低优先级0inti,j;i=0;//用于指示扫描s1串中字符的位置，初值为0j=0;//用于指示s2串中待存字符的位置，初值为0charch=s1[i];//ch保存s1串中扫描到的字符，初值为第一个字符while(ch!='@'){//顺序处理中缀表达式中的每个字符if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){//对于四则运算符，使暂存在栈中的不低于ch优先级的运算符依次出栈并写入到s2中charw=top(R);while(Precedence(w)=Precedence(ch)){//Precedence(w)函数返回运算符形参的优先级s2[j++]=w;Pop(R);w=top(R);}Push(R,ch);//把ch运算符写入栈中ch=s1[++i];}else{s2[j++]=ch;ch=s1[++i];}}//把暂存在栈中的运算符依次出栈并写入到s2串中while(！Empty(R)){s2[j++]=pop(R);}s2[j++]='\0';}求运算符优先级的Precedence函数为：intPrecedence(charop)//返回运算符op所对应的优先级数值{switch(op){case'+':case'-':return1;//定义加减运算的优先级为1case'*':case'/':return2;//定义乘除运算的优先级为2case'@':case‘(’：return0;//定义在栈中的左括号和栈底字符的优先级为08}}10.基于图的广度优先搜索策略，设计算法判别以邻接表方式存储的有向图中是否存在由顶点vi到vj的路径(ij)。注意，算法中涉及的图的基本操作必须在此存储结构