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

1、读书破万卷下笔如有神2.11Status Iiiseit_SqList(SqList &vajnt x)把 x 插入递增有序表 va 中 ( if(va.length+1 >va.listsize) return ERROR;va.lengtli+；fbr(i=va.length-l ;va.elemi>x&&i>=O;i") va.elemi+ l=va.elemi;va.elemi+l=x;return OK;/IiiseivSqList2.13LNode* Locate(LnikList Lant x)链表上的元素查找.返回指针 ( f

2、br(p=L->next;p&&p->data! =x;p=p->next);return p;/,<Locate2.14mt Length(LinkList L) 求链表的长度 (fbr(k=O.p=L;p->next;p=p->next,k+);return k;5/"Length2.15void ListConcat(LuikList ha,LuikList hb.LiiikList &hc)把链表 hb 接在 ha 后面形成链表 he ( hc=ha;p=ha;while(p->next) p=p->ne

3、xt;p->next=hb->next;fiee(hb);/*ListConcat2.22void LinkList_ieveise(Linklist &L)/利用头插法实现链表的就地逆置;为简化算法,假设表长大于2 ( p=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; /LiiikList_re

4、verse分析:本算法的思想是，利用头插法，逐个地把L的当前元素q插入新的链表头部,p为新表的首元结点.补充题：(是题2.14的扩充)int number(LinkedNode head) 计算带头结点的单循环链表的结点个数 (p=head;i=0;while(p->next = head) i+； p=p->next; ) ietiun i;3.16void Tiaui_anaiige(char这里用字符串train表示火车表示硬席表示软席( p=tiam;q=tiain;InitStack(s); while(*p) ( if(*p=H) push(sjp); 把 H 存入栈中

5、 else *(q+)=*p; 把S调到前部 P+； 1 ) while(! StackEmpty(s) ( pop(s,c);*(q+尸c;把H接在后部 /Train_anange3.17intIsReverse()/判断输入的字符串中代前和&后部分是否为逆串，是则返回1,否则返回0 ( InitStack(s);while(e=getchar()?=,&,) push(s,e);while(e=getchar()!='') ( if(StackEmpty(s) return 0; pop c);if(e!=c) return 0; if(!StackEmpt

6、y(s) retuin 0;return 1;/IsReverse3.18Status Bracket_Test(chai *sti)判别表达式中小括号是否匹配 (count=0;fbr(p=str;*p;p-H-)(if(*p='(') count+;else if(*p=)') count"if (count<0) leturn ERROR;1 )if(count) retuin ERROR; 注意括号不匹配的两种情况return OK;/Biacket_Test3.19Status AllBrackets_Test(chai- *sti)判别表达式

7、中三种括号是否匹配 (InitStack(s);fbr(p=str;*p;p-H-)(if(*p=，(*p=TU*p=，)push(s,*p);else if(*p-)'|*p=,'|*p,)(if(StackEmpty(s) return ERROR;pop(s,c);if(*p=)'&&c !='(') retuin ERROR:if(*p=T&&c !=*) retuin ERROR:if(*p=,&&c!=,(')iennii ERROR; 必须与当前栈顶括号匹配/forif(! Stack

8、Empty(s) retuin ERROR;return OK;/AllBrackets_Test3.24Status g(int m,int n,mt &s)求递归函数 g 的值 s(if(m=0&&n>=0) s=0;else if(m>0&&n>=0) s=n+g(m-l,2*n);else return ERROR;return OK;g3.25Status F_recursive(int njnt &s)递归算法 (if(n<0) return ERROR:if(n=O) s=n+l;else(F_recurve

9、(n/2,t);s=n*r;return OK;/ZF_recursive331mtPalindiome_Test0判别输入的字符串是否回文序列，是则返回1,否则返回0(LutStack(S);IiHtQiieue(Q);wlule(c=getchar()!=,)(Pusli(S,c);EnQueue(Q.c); /同时使用栈和队列两种结构)wlule(! StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b) renini ERROR;)return OK; /Palindi ome_Test6.36mt Bitree_Sim(Bitree B1 ,Bitie

10、e B2)判断两棵树是否相似的递归算法(if(!Bl&&!B2) return 1;else if(B 1 &&B2&&Bitree_Sim(B 1 ->lchild,B2->lchild)&&Bitree_Sim(B 1 ->rchild,B2->ichild) feturn 1;else feturn 0;/7Bitree_Sun6.41mt c,k; 这里把k和计数器c作为全局变量处理 void Get_PreSeq(Bitree T)求先序序列为k的结点的值 (if(C+; 每访问一个子树的根都会使

11、前序序号计数器加1 if(c=k) (piiiitf(nValue is %diT',T->data);exit(l); else(Get_PreSeq(T->lchild); 在左子树中查找Get_PreSeq(T->icluld); 在右子树中查找 /if/Get_PieSeq6.42int LeafCount_BiTiee(Bitiee T)/求二叉树中叶子结点的数目(if(!T) letuin 0; 空树没有叶子else if(!T->lchild&&!T->rchild) letuni 1; 叶子结点else letuni Lea

12、f_Count(T->lcliild)+Leaf_Count(T->icluld);左子树的叶子数加上右子树的叶 子数/LeafC ount_B iTiee6.43void Bitree_Revolute(Bitree T)交换所有结点的左右子树 (T->lchild->T->rchild; 交换左右子树if(T->lcluld) Bitree_Revolute(T->lcliild);if(T->rchild) Bitree_Revolute(T->icluld); 左右子树再分别交换各自的左右子树 /Bitree_Revolute6.4

13、4mt Get_Sub_Depth(Bitree T,mt x)求二叉树中以值为x的结点为根的子树深度 (if(T->data=x) (pnntf("dn”,Get_Depth);找到了值为x的结点，求其深度 exit 1; else(if(T->lcluld) Get_Sub_Deptli(T->lcluld,x);if(T->icluld) Get_Sub_Depth(T->ichild,x); 在左右子树中继续寻找 /Get_Sub_Depthmt Get_Deptli(Bitiee T)求子树深度的递归算法 (return 0; else (m=

14、Get_Depth(T->lcliild);n=Get_Depth(T->rcluld); return (m>n?m:n)+l; /Get_Depth6.45void Del_Sub_x(Bitiee T,int x)删除所有以元素x为根的子树 ( if(T->data=x) Del_Sub(T); /删除该子树 else(if(T->lcluld) Del_Sub_x(T->lchild,x);if(T->rcluld) Del_Sub_x(T->tchild,x); 在左右子树中继续查找 /else /Del Sub xvoid DeLSu

15、b(Bitiee T)删除子树 T (if(T->lcliild) Del_Sub(T->lchild);if(T->icliild) DeLSub(T->rcluld); free(T);/Del_Sub6.47void LayerOrder(Bitree T)层序遍历二叉树 (ImtQueue(Q); 建立工作队列EnQueue(Q.T);while(! QueueEmpty(Q) (DeQueue(Q.p);visit(p);if(p->lchild) EnQueue(Q.p->lcluld);if(p->rchild) EnQueue(Q.p-

16、>icluld);/*LayerOrder9.26mt Seaich_Bm_Recursive(S STable ST,int keyiiit low,int high)/折半查找的递归算法 (if(low>high) return 0; 查找不到时返回 0nud=(low+lugh)/2;if(ST.eleminid .key=key) retuin nud;else if(ST.elemniid .key>key)return Search_Bm_Recuisive(ST,keyJow,niid-1);else return Search_Bin_Recuisive(ST

17、.key4iud+1 Jiigh);/Seaich_Bin_Recuisive10.23void Iiiseit_Sortl(SqList &L)监视哨设在高下标端的插入排序算法 (k=L.length;foKi=k-l;i;-i)从后向前逐个插入排序if(L.ri .key>L.ri+1 .key)(L.rk+l.key=L.ri.key; /监视哨for(j=i+l：L.rIj.key>L.ri.key;+j)L.ri-l.key=L.rj.key; /前移L.rj-l.key=L.rk+l.key； /ISA/Iiisert_Soitl10.27void Bubble-Son2(mt a ,int n)相邻两趟是反方向起泡的冒泡排序算法 (lov=0;high=n-1; 冒泡的上下界change=l;while(low<high&&change)(change=0;for(i=low;i<high;i+) 从上向下起泡if(ai>ai+l)(ai<->ai+l;change=l;lugh-; 修改上界fbr(i=high;i>low;i-) 从下向上起泡if(ai<ai-l)(ai<->ai-l;change=l;