当前位置:首页 >> 其它课程 >>

北理工数据结构作业5


第九章作业

1、分别画出在线性表( a , b , c , d , e , f , g )中进行折半查找,以查关键字等 于 e、f 和 g 的过程。
(1)查 e 1): a b c d e f g ↑low ↑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=mid–1; 3): a b c d e f g high↑low ↑mid 此时 mid 指向的元素为 e,查找成功; (2)查 f 1): a b c d e f g ↑low ↑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)查 g 1): a b c d e f g ↑low ↑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 g high↑low ↑mid 此时 mid 指向的元素为 g,查找成功;

2、请将折半查找的算法改写为递归算法。 int BinSearch(SSTable s;int low,int high;keyType K) { if(low>high) return 0; else { mid=(low+high)/2; switch{ case s.elem[mid].key<K: return BinSearch(s,mid+1,high,K); break; case s.elem[mid].key==K: return mid; break; case s.elem[mid].key>K: return BinSearch(s,low,mid-1,K); break; default:; }//switch }//else }//BinSearch 3、编写判别给定二叉树是否为二叉排序树的算法。假设此二叉树是以二叉链表 的形式存储的,且树中关键字均不同。 typedef struct BiTNode{ TElemType 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 0

typedef struct{ int R[MAXSIZE+1]; int length; }SqList;

void InsertSort(SqList &L) { //对顺序表 L 作直接插入排序 int i,j; for(i=2;i<=L.length;++i) if(L.R[i]<L.R[i-1])

{ L.R[0]=L.R[i]; L.R[i]=L.R[i-1]; for(j=i-2;L.R[0]<L.R[j];--j) L.R[j+1]=L.R[j]; L.R[j+1]=L.R[0]; } }

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.R[i]); InsertSort(L); printf("\nSequence after sort:\n");

for(i=1;i<=n;i++) printf("%4d",L.R[i]); }

快速排序: #include <stdio.h> #define MAXSIZE 100 #define ERROR 0

typedef struct{ int R[MAXSIZE+1]; int length; }SqList;

int Partition(SqList &L,int low,int high){

int p; L.R[0]=L.R[low]; p=L.R[low]; while(low<high){ while(low<high&&L.R[high]>=p) --high; L.R[low]=L.R[high]; while(low<high&&L.R[low]<=p) ++low; L.R[high]=L.R[low]; } L.R[low]=L.R[0]; 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.R[i]); QuickSort(L); printf("\nSequence after sort:\n"); for(i=1;i<=n;i++) printf("%4d",L.R[i]); }

选择排序: #include <stdio.h> #define MAXSIZE 100 #define ERROR 0

typedef struct{ int R[MAXSIZE+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.R[j]<L.R[k]) k=j; if(k!=i) { L.R[0]=L.R[i]; L.R[i]=L.R[k]; L.R[k]=L.R[0]; } } }

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.R[i]);

SelectSort(L); printf("\nSequence after sort:\n"); for(i=1;i<=n;i++) printf("%4d",L.R[i]); }


相关文章:
北理工数据结构作业5
北​理​工​数​据​结​构​作​业​5 暂无评价|0人阅读|0次下载|举报文档第九章作业 1、分别画出在线性表( a , b , c , d , e ...
北理工数据结构作业4
第七章作业 1、已知有向图,请给出该图的 (1) 每个顶点的入/出度; 顶点 1 2 3 4 5 6 入度 3 2 1 1 2 2 出度 0 2 2 3 1 3 (2) 邻接...
北理工数据结构作业2
第三章作业 1、写出下列程序段的输出结果。 viod main ( ) { Stack S; ...例如,输入:4+2*5= 输入:(4+2)*(2-10)= 输出:14 输出:-48 程序如下...
北理工数据结构作业1
(1)p = p->next; (2)p->next = p; (3)p->next = p->next->next; (4)p = p->next->next; (5)while ( p!=NULL ) p=p->next; (6)...
数据结构作业5
数据结构作业5_IT认证_资格考试/认证_教育专区。第五次作业 1.已知如图所示的有向图,请给出该图的: (1) 每个顶点的入/出度; (2) 邻接矩阵; (3) 邻接...
数据结构作业5
数据结构作业 2012 11206045 杨明芳 土木与水利学院 结构工程作业 5. 查找、排序 非编程作业: 1.对下标为 1~9 的有序表进行折半查找,画出折半查找的判定树;...
北京理工大学数据结构编程练习答案
的外框为墙,每一步走一格,每格有四个可走的方向,探索顺序为:南、东、北、...北京理工大学数据结构与... 暂无评价 14页 ¥5.00 北京理工大学程序设计(...
北理工《数据结构与算法》在线作业
北理工数据结构与算法》在线作业_电大_成人教育_教育专区。北理工数据结构与算法》在线作业 试卷总分:100 测试时间:-试卷得分:99.5 一、单选题(共 40 道...
16秋北理工《数据结构与算法》在线作业
16秋北理工数据结构与算法》在线作业_工学_高等教育_教育专区。北理工《数据...4 D. 5 正确答案: 35. 由于数据的逻辑结构通过不同的存储映像方法可得到不...
北理工《数据结构与算法》在线作业_4
北理工数据结构与算法》在线作业_4_电大_成人教育_教育专区。北理工《数据...活动提前完成,那么整个工程将会提前完成 正确答案:B 满分:2.5 分 得分:2.5 5....
更多相关标签:
北理工数据结构 | 北理工数据结构实验四 | 北理工889数据结构 | 北理工数据结构课件 | 数据结构大作业 | 数据结构作业 | 数据结构大作业题目 | 数据结构作业答案 |