数据结构--顺序查找和二分查找
|
题目：?顺序查找，在顺序表R[0..n-1]中查找关键字为k的记录，成功时返回找到的记录位置，失败时返回-1；二分查找，在有序表R[0..n-1]中进行二分查找，成功时返回记录的位置，失败时返回-1。 顺序查找： #include #define MaxSize 100 typedef int DataType; typedef struct { DataType key[MaxSize]; int size; } SeqList; void ListInitiate(SeqList *L)/*初始化顺序表L*/ { L->size = 0;/*定义初始数据元素个数*/ } int ListLength(SeqList L)/*返回顺序表L的当前数据元素个数*/ { return L.size; } int ListInsert(SeqList *L,int i,DataType x) /*在顺序表L的位置i（0 ≤ i ≤ size）前插入数据元素值x*/ /*插入成功返回1，插入失败返回0*/ { int j; if(L->size >= MaxSize) { printf("顺序表已满无法插入! n"); return 0; } else if(i < 0 || i > L->size ) { printf("参数i不合法! n"); return 0; } else { for(j = L->size; j >= i; j--) L->key[j+1] = L->key[j];/*为插入做准备*/ L->key[i] = x;/*插入*/ L->size ++;/*元素个数加1*/ return 1; } } int SeqSearch(SeqList *R,int n,DataType k)//查找K，返回k的位置 { int i=0; while(i { i++; } if(i>=n) return -1; else { printf("%dn",R->key[i]); return i; } } void main(void) { SeqList myList; int i,x,a,b; ListInitiate(&myList); printf("输入查找数：n"); scanf("%d",&x); printf("输入顺序表的5个数："); for(i = 0; i < 5; i++) { scanf("%d",&b); ListInsert(&myList,i,b); } a=SeqSearch(&myList,x); if(a==-1) printf("查找失败"); else printf("关键字的位置为:%d",a); } 二分查找（也叫折半查找） #include #define MaxSize 100 typedef int DataType; typedef struct { DataType key[MaxSize]; int size; } SeqList; void ListInitiate(SeqList *L)/*初始化顺序表L*/ { L->size = 0;/*定义初始数据元素个数*/ } int ListLength(SeqList L)/*返回顺序表L的当前数据元素个数*/ { return L.size; } int ListInsert(SeqList *L,DataType x) /*在顺序表L的位置i（0 ≤ i ≤ size）前插入数据元素值x*/ /*插入成功返回1，插入失败返回0*/ { int j; if(L->size >= MaxSize) { printf("顺序表已满无法插入! n"); return 0; } else if(i < 0 || i > L->size ) { printf("参数i不合法! n"); return 0; } else { for(j = L->size; j >= i; j--) L->key[j+1] = L->key[j];/*为插入做准备*/ L->key[i] = x;/*插入*/ L->size ++;/*元素个数加1*/ return 1; } } int BinSearch(SeqList *R,DataType k)//查找K，返回k的位置 { int low=0,high=n-1,mid,count=0; while(low<=high) { mid=(low+high)/2; printf("第%d次查找：在[ %d,%d]中找到元素R[%d]:%dn ",++count,low+1,high+1,mid+1,R->key[mid]); if(R->key[mid]==k) return mid; if(R->key[mid]>k) high=mid-1; else low=mid+1; } return -1; } void main(void) { SeqList myList; int i,&x); printf("输入顺序表的10个有序数："); for(i = 0; i < 10; i++) { scanf("%d",b); } a=BinSearch(&myList,a+1); } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |