《数据结构作业中的算法设计题参考答案》由会员分享，可在线阅读，更多相关《数据结构作业中的算法设计题参考答案（9页珍藏版）》请在金锄头文库上搜索。
1、2.11Status Insert_SqList(SqList &va,int x)/把x插入递增有序表va中if(va.length+1va.listsize) return ERROR;va.length+;for(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.elemi+1=x;return OK;/Insert_SqList 2.13 LNode* Locate(LinkList L,int x)/链表上的元素查找,返回指针for(p=L-next;p&p-data!=x;p=p-next);return p;/Locate
2、 2.14 int Length(LinkList L)/求链表的长度for(k=0,p=L;p-next;p=p-next,k+);return k;/Length2.15 void ListConcat(LinkList ha,LinkList hb,LinkList &hc)/把链表hb接在ha后面形成链表hchc=ha;p=ha;while(p-next) p=p-next;p-next=hb-next;free(hb);/ListConcat 2.22 void LinkList_reverse(Linklist &L)/利用头插法实现链表的就地逆置;为简化算法,假设表长大于2p=L
3、-next;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p;p=q;q=s;s=s-next; /把L的元素逐个插入新表表头q-next=p;s-next=q;L-next=s;/LinkList_reverse分析:本算法的思想是,利用头插法,逐个地把L的当前元素q插入新的链表头部,p为新表的首元结点.补充题：(是题2.14的扩充)int number(LinkedNode head) /计算带头结点的单循环链表的结点个数 p=head; i=0; while(p-next != head) i+; p=p-next; return i
4、; 3.16 void Train_arrange(char *train)/这里用字符串train表示火车,H表示硬席,S表示软席 p=train;q=train; InitStack(s); while(*p) if(*p=H) push(s,*p); /把H存入栈中 else *(q+)=*p; /把S调到前部 p+; while(!StackEmpty(s) pop(s,c); *(q+)=c; /把H接在后部 /Train_arrange 3.17 int IsReverse()/判断输入的字符串中&前和&后部分是否为逆串,是则返回1,否则返回0 InitStack(s); whil
5、e(e=getchar()!=&) push(s,e); while(e=getchar()!=) if(StackEmpty(s) return 0; pop(s,c); if(e!=c) return 0; if(!StackEmpty(s) return 0; return 1; /IsReverse 3.18 Status Bracket_Test(char *str)/判别表达式中小括号是否匹配 count=0; for(p=str;*p;p+) if(*p=() count+; else if(*p=) count-; if (count=0) s=0; else if(m0&n=
6、0) s=n+g(m-1,2*n); else return ERROR; return OK; /g 3.25 Status F_recursive(int n,int &s)/递归算法 if(nlchild,B2-lchild)&Bitree_Sim(B1-rchild,B2-rchild)return 1;else return 0;/Bitree_Sim 6.41 int c,k; /这里把k和计数器c作为全局变量处理 void Get_PreSeq(Bitree T)/求先序序列为k的结点的值 if(T) c+; /每访问一个子树的根都会使前序序号计数器加1 if(c=k) prin
7、tf(Value is %dn,T-data); exit (1); else Get_PreSeq(T-lchild); /在左子树中查找 Get_PreSeq(T-rchild); /在右子树中查找 /if /Get_PreSeq 6.42 int LeafCount_BiTree(Bitree T)/求二叉树中叶子结点的数目if(!T) return 0; /空树没有叶子else if(!T-lchild&!T-rchild) return 1; /叶子结点else return Leaf_Count(T-lchild)+Leaf_Count(T-rchild);/左子树的叶子数加上右子
8、树的叶子数/LeafCount_BiTree 6.43 void Bitree_Revolute(Bitree T)/交换所有结点的左右子树T-lchildT-rchild; /交换左右子树if(T-lchild) Bitree_Revolute(T-lchild);if(T-rchild) Bitree_Revolute(T-rchild); /左右子树再分别交换各自的左右子树/Bitree_Revolute 6.44 int Get_Sub_Depth(Bitree T,int x)/求二叉树中以值为x的结点为根的子树深度 if(T-data=x) printf(%dn,Get_Depth
9、(T); /找到了值为x的结点,求其深度 exit 1; else if(T-lchild) Get_Sub_Depth(T-lchild,x); if(T-rchild) Get_Sub_Depth(T-rchild,x); /在左右子树中继续寻找 /Get_Sub_Depth int Get_Depth(Bitree T)/求子树深度的递归算法 if(!T) return 0; else m=Get_Depth(T-lchild); n=Get_Depth(T-rchild); return (mn?m:n)+1; /Get_Depth 6.45 void Del_Sub_x(Bitree
10、 T,int x)/删除所有以元素x为根的子树 if(T-data=x) Del_Sub(T); /删除该子树 else if(T-lchild) Del_Sub_x(T-lchild,x); if(T-rchild) Del_Sub_x(T-rchild,x); /在左右子树中继续查找 /else /Del_Sub_x void Del_Sub(Bitree T)/删除子树T if(T-lchild) Del_Sub(T-lchild); if(T-rchild) Del_Sub(T-rchild); free(T); /Del_Sub 6.47 void LayerOrder(Bitree T)/层序遍历二叉树 InitQueue(Q); /建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); visit(p); if(p-lchild) EnQue
