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

2.11Status Insert_SqList(SqList &va,int x)//把 x 插入递增有序表 va 中{if(va.length+1>va.listsize) return ERROR;va.length++;for(i=va.length-1;va.elem[i]>x&&i>=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+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.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 后面形成链表 hc{hc=ha;p=ha;while(p->next) p=p->next;p->next=hb->next;free(hb);}//ListConcat 2.22 void LinkList_reverse(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;}//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;}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); while((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(m>0&&n>=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) { printf("Value is %d\n",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);//左子树的叶子数加上右子树的叶子数}//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("%d\n",Get_Depth(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 (m>n?m:n)+1; } }//Get_Depth 6.45 void Del_Sub_x(Bitree 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) 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(low>high) return 0; //查找不到时返回 0mid=(low+high)/2;if(ST.elem[mid].key==key) return mid;else if(ST.elem[mid].key>key)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.r[i].key>L.r[i+1].key) { L.r[k+1].key=L.r[i].key; //监视哨 for(j=i+1;L.r[j].key>L.r[i].key;++j) L.r[j-1].key=L.r[j].key; //前移 L.r[j-1].key=L.r[k+1].key; //插入 } }//Insert_Sort1 10.27 void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法 { low=0;high=n-1; //冒泡的上下界 change=1; while(lowa[i+1]) { a[i]a[i+1]; change=1; } high--; //修改上界 for(i=high;i>low;i--) //从下向上起泡 if(a[i]a[i-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;ia[i+1]) { a[i]a[i+1]; change=1; } for(i=0;ia[i+1]) { a[i]a[i+1]; change=1; } }//while 天津理工大学本科教学教案第 页}//OE_Sort 分析:本算法的结束条件是连续两趟比较无交换发生