北理工数据结构作业.doc
第九章作业1、 分别画出在线性表（ a , b , c , d , e , f , g ）中进行折半查找，以查关键字等于e、f和g的过程。(1)查e1): a b c d e f glow mid high此时d<e说明d若存在，必在区间mid+1,high令low=mid+1;2): a b c d e f g low mid high此时f>e说明d若存在，必在区间low,mid-1令high=mid1;3): a b c d e f ghighlowmid此时mid指向的元素为e，查找成功;(2)查f1): a b c d e f glow mid high此时d<f说明f若存在，必在区间mid+1,high令low=mid + 1;2): a b c d e f g low mid high此时mid指向的元素为f，查找成功;(3)查g1): a b c d e f glow mid high此时d<g说明g若存在，必在区间mid+1,high令low=mid+1;2): a b c d e f g low mid high此时f<g说明g若存在，必在区间mid+1,high令low=mid+1;3): a b c d e f ghighlowmid此时mid指向的元素为g，查找成功;2、 请将折半查找的算法改写为递归算法。int BinSearch(SSTable s;int low,int high;keyType K)if(low>high) return 0;else mid=(low+high)/2;switchcase s.elemmid.key<K: return BinSearch(s,mid+1,high,K);break;case s.elemmid.key=K: return mid;break;case s.elemmid.key>K: return BinSearch(s,low,mid-1,K);break;default:;/switch/else/BinSearch3、 编写判别给定二叉树是否为二叉排序树的算法。假设此二叉树是以二叉链表的形式存储的，且树中关键字均不同。typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;int flag=1,last=0; int BiSortTree(Bitree T)/判断二叉树T是否二叉排序树,是则返回1,否则返回0 if(T->lchild&&flag) BiSortTree(T->lchild); if(T->data<last) flag=0; /将T->data与其中序前驱last比较大小 last=T->data; if(T->rchild&&flag) BiSortTree(T->rchild); return flag;/ BiSortTree实验四输入10个数，从插入排序、快速排序、选择排序三类算法中各选一种编程实现。程序如下（均为.cpp）插入排序：#include <stdio.h>#define MAXSIZE 100#define ERROR 0typedef structint RMAXSIZE+1;int length;SqList;void InsertSort(SqList &L) /对顺序表L作直接插入排序 int i,j; for(i=2;i<=L.length;+i) if(L.Ri<L.Ri-1) L.R0=L.Ri; L.Ri=L.Ri-1; for(j=i-2;L.R0<L.Rj;-j) L.Rj+1=L.Rj; L.Rj+1=L.R0; main() int i,n; SqList L; printf("input total number of the sequence:n"); scanf("%d",&n); if(n<=0|n>MAXSIZE) printf("n must more than 0 and less than %d.n",MAXSIZE); return ERROR ; L.length=n; printf("input the elements:n"); for(i=1;i<=n;i+) scanf("%d",&L.Ri); InsertSort(L); printf("nSequence after sort:n"); for(i=1;i<=n;i+) printf("%4d",L.Ri);快速排序：#include <stdio.h>#define MAXSIZE 100#define ERROR 0typedef structint RMAXSIZE+1;int length;SqList;int Partition(SqList &L,int low,int high) int p; L.R0=L.Rlow; p=L.Rlow; while(low<high) while(low<high&&L.Rhigh>=p) -high; L.Rlow=L.Rhigh; while(low<high&&L.Rlow<=p) +low; L.Rhigh=L.Rlow; L.Rlow=L.R0; return low;void QSort(SqList &L,int low,int high) int p; if(low<high) p=Partition(L,low,high); QSort(L,low,p-1); QSort(L,p+1,high); void QuickSort(SqList &L)QSort(L,1,L.length);main() int i,n; SqList L; printf("input total number of the sequence:n"); scanf("%d",&n); if(n<=0|n>MAXSIZE) printf("n must more than 0 and less than %d.n",MAXSIZE); return ERROR ; L.length=n; printf("input the elements:n"); for(i=1;i<=n;i+) scanf("%d",&L.Ri); QuickSort(L); printf("nSequence after sort:n"); for(i=1;i<=n;i+) printf("%4d",L.Ri);选择排序：#include <stdio.h>#define MAXSIZE 100#define ERROR 0typedef structint RMAXSIZE+1;int length;SqList;void SelectSort(SqList &L) int i,j,k; for(i=1;i<L.length;i+) k=i; for(j=i+1;j<=L.length;j+) if(L.Rj<L.Rk) k=j; if(k!=i) L.R0=L.Ri; L.Ri=L.Rk; L.Rk=L.R0; main() int i,n; SqList L; printf("input total number of the sequence:n"); scanf("%d",&n); if(n<=0|n>MAXSIZE) printf("n must more than 0 and less than %d.n",MAXSIZE); return ERROR ; L.length=n; printf("input the elements:n"); for(i=1;i<=n;i+) scanf("%d",&L.Ri); SelectSort(L); printf("nSequence after sort:n"); for(i=1;i<=n;i+) printf("%4d",L.Ri);
