数据结构作业中的算法设计题参考答案

《数据结构作业中的算法设计题参考答案》由会员分享，可在线阅读，更多相关《数据结构作业中的算法设计题参考答案（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

11、 T)/层序遍历二叉树 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); /LayerOrder 9.26 int Search_Bin_Recursive(SSTable ST,int key,int low,int high)/折半查找的递归算法if(lowhigh) return 0; /查找不到时返回0mid=(low+high)/2;if(

12、ST.elemmid.key=key) return mid;else if(ST.elemmid.keykey)return Search_Bin_Recursive(ST,key,low,mid-1);else return Search_Bin_Recursive(ST,key,mid+1,high);/Search_Bin_Recursive10.23 void Insert_Sort1(SqList &L)/监视哨设在高下标端的插入排序算法 k=L.length; for(i=k-1;i;-i) /从后向前逐个插入排序 if(L.ri.keyL.ri+1.key) L.rk+1.ke

13、y=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_Sort1 10.27 void Bubble_Sort2(int a ,int n)/相邻两趟是反方向起泡的冒泡排序算法 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=1; low+; /修改下界 /while /Bubble_Sort2 10.29 void OE_Sort(int a ,int n)/奇偶交换排序的算法 change=1; while(change) change=0; for(i=1;iai+1) aiai+1; change=1; for(i=0;iai+1) aiai+1; change=1; /while /OE_Sort 分析:本算法的结束条件是连续两趟比较无交换发生