《数据结构》作业中的算法设计题参考答案教程文件

1、Good is good, but better carries it.精益求精，善益求善。数据结构作业中的算法设计题参考答案-2.11StatusInsert_SqList(SqList&va,intx)/把x插入递增有序表va中if(va.length+1va.listsize)returnERROR;va.length+;for(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.elemi+1=x;returnOK;/Insert_SqList2.13LNode*Locate(LinkListL,intx)/链表上的元素查找,返回

2、指针for(p=L-next;p&p-data!=x;p=p-next);returnp;/Locate2.14intLength(LinkListL)/求链表的长度for(k=0,p=L;p-next;p=p-next,k+);returnk;/Length2.15voidListConcat(LinkListha,LinkListhb,LinkList&hc)/把链表hb接在ha后面形成链表hchc=ha;p=ha;while(p-next)p=p-next;p-next=hb-next;free(hb);/ListConcat2.22voidLinkList_reverse(Linkli

3、st&L)/利用头插法实现链表的就地逆置;为简化算法,假设表长大于2p=L-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的扩充)intnumber(LinkedNodehead)/计算带头结点的单循环链表的结点个数p=head;i=0;while(p-next!=

4、head)i+;p=p-next;returni;3.16voidTrain_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_arrange3.17intIsReverse()/判断输入的字符串中&前和&后部分是否为逆串,是则返回1,否则返回0InitStack(s);whil

5、e(e=getchar()!=&)push(s,e);while(e=getchar()!=)if(StackEmpty(s)return0;pop(s,c);if(e!=c)return0;if(!StackEmpty(s)return0;return1;/IsReverse3.18StatusBracket_Test(char*str)/判别表达式中小括号是否匹配count=0;for(p=str;*p;p+)if(*p=()count+;elseif(*p=)count-;if(count=0)s=0;elseif(m0&n=0)s=n+g(m-1,2*n);elsereturnERRO

6、R;returnOK;/g3.25StatusF_recursive(intn,int&s)/递归算法if(nlchild,B2-lchild)&Bitree_Sim(B1-rchild,B2-rchild)return1;elsereturn0;/Bitree_Sim6.41intc,k;/这里把k和计数器c作为全局变量处理voidGet_PreSeq(BitreeT)/求先序序列为k的结点的值if(T)c+;/每访问一个子树的根都会使前序序号计数器加1if(c=k)printf(Valueis%dn,T-data);exit(1);elseGet_PreSeq(T-lchild);/在左子

7、树中查找Get_PreSeq(T-rchild);/在右子树中查找/if/Get_PreSeq6.42intLeafCount_BiTree(BitreeT)/求二叉树中叶子结点的数目if(!T)return0;/空树没有叶子elseif(!T-lchild&!T-rchild)return1;/叶子结点elsereturnLeaf_Count(T-lchild)+Leaf_Count(T-rchild);/左子树的叶子数加上右子树的叶子数/LeafCount_BiTree6.43voidBitree_Revolute(BitreeT)/交换所有结点的左右子树T-lchildT-rchild;

8、/交换左右子树if(T-lchild)Bitree_Revolute(T-lchild);if(T-rchild)Bitree_Revolute(T-rchild);/左右子树再分别交换各自的左右子树/Bitree_Revolute6.44intGet_Sub_Depth(BitreeT,intx)/求二叉树中以值为x的结点为根的子树深度if(T-data=x)printf(%dn,Get_Depth(T);/找到了值为x的结点,求其深度exit1;elseif(T-lchild)Get_Sub_Depth(T-lchild,x);if(T-rchild)Get_Sub_Depth(T-rch

9、ild,x);/在左右子树中继续寻找/Get_Sub_DepthintGet_Depth(BitreeT)/求子树深度的递归算法if(!T)return0;elsem=Get_Depth(T-lchild);n=Get_Depth(T-rchild);return(mn?m:n)+1;/Get_Depth6.45voidDel_Sub_x(BitreeT,intx)/删除所有以元素x为根的子树if(T-data=x)Del_Sub(T);/删除该子树elseif(T-lchild)Del_Sub_x(T-lchild,x);if(T-rchild)Del_Sub_x(T-rchild,x);/

10、在左右子树中继续查找/else/Del_Sub_xvoidDel_Sub(BitreeT)/删除子树Tif(T-lchild)Del_Sub(T-lchild);if(T-rchild)Del_Sub(T-rchild);free(T);/Del_Sub6.47voidLayerOrder(BitreeT)/层序遍历二叉树InitQueue(Q);/建立工作队列EnQueue(Q,T);while(!QueueEmpty(Q)DeQueue(Q,p);visit(p);if(p-lchild)EnQueue(Q,p-lchild);if(p-rchild)EnQueue(Q,p-rchild)

11、;/LayerOrder9.26intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)/折半查找的递归算法if(lowhigh)return0;/查找不到时返回0mid=(low+high)/2;if(ST.elemmid.key=key)returnmid;elseif(ST.elemmid.keykey)returnSearch_Bin_Recursive(ST,key,low,mid-1);elsereturnSearch_Bin_Recursive(ST,key,mid+1,high);/Search_Bin_Recursive

12、10.23voidInsert_Sort1(SqList&L)/监视哨设在高下标端的插入排序算法k=L.length;for(i=k-1;i;-i)/从后向前逐个插入排序if(L.ri.keyL.ri+1.key)L.rk+1.key=L.ri.key;/监视哨for(j=i+1;L.rj.keyL.ri.key;+j)L.rj-1.key=L.rj.key;/前移L.rj-1.key=L.rk+1.key;/插入/Insert_Sort110.27voidBubble_Sort2(inta,intn)/相邻两趟是反方向起泡的冒泡排序算法low=0;high=n-1;/冒泡的上下界change=1;while(lowhigh&change)change=0;for(i=low;iai+1)aiai+1;change=1;high-;/修改上界for(i=high;ilow;i-)/从下向上起泡if(aiai-1)aiai-1;change=