北理工数据结构作业.doc

《北理工数据结构作业.doc》由会员分享，可在线阅读，更多相关《北理工数据结构作业.doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第九章作业1、 分别画出在线性表（ a , b , c , d , e , f , g ）中进行折半查找，以查关键字等于e、f和g的过程。(1)查e1): a b c d e f glow mid high此时de说明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此时df说明f若存在，必在区间mid+1,high令low=mid + 1;2): a b c d e f g low mid high此时mid指向的元素为f，查找

2、成功;(3)查g1): a b c d e f glow mid high此时dg说明g若存在，必在区间mid+1,high令low=mid+1;2): a b c d e f g low mid high此时fhigh) return 0;else mid=(low+high)/2;switchcase s.elemmid.keyK: return BinSearch(s,low,mid-1,K);break;default:;/switch/else/BinSearch3、 编写判别给定二叉树是否为二叉排序树的算法。假设此二叉树是以二叉链表的形式存储的，且树中关键字均不同。typedef

3、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-datadata与其中序前驱last比较大小 last=T-data; if(T-rchild&flag) BiSortTree(T-rchild); return flag;/ BiSortTree实验四输入10个数

4、，从插入排序、快速排序、选择排序三类算法中各选一种编程实现。程序如下（均为.cpp）插入排序：#include #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.RiL.Ri-1) L.R0=L.Ri; L.Ri=L.Ri-1; for(j=i-2;L.R0L.Rj;-j) L.Rj+1=L.Rj; L.Rj+1=L.R0; ma

5、in() int i,n; SqList L; printf(input total number of the sequence:n); scanf(%d,&n); if(nMAXSIZE) 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

6、;i+) printf(%4d,L.Ri);快速排序：#include #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(lowhigh) while(low=p) -high; L.Rlow=L.Rhigh; while(lowhigh&L.Rlow=p) +low; L.Rhigh=L.Rlow; L.Rlow=L.R0; r

7、eturn low;void QSort(SqList &L,int low,int high) int p; if(lowhigh) 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(nMAXSIZE) printf(n must more than 0

8、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 #define MAXSIZE 100#define ERROR 0typedef structint RMAXSIZE+1;int length;SqList;void Se

9、lectSort(SqList &L) int i,j,k; for(i=1;iL.length;i+) k=i; for(j=i+1;j=L.length;j+) if(L.RjL.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(nMAXSIZE) 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);