实验五

时间：2019-05-27 23:36:57 阅读：176 评论：0 收藏：0 [点我收藏+]

part1.二分查找

实现方式1

#include<stdio.h>
const int N=5; 
int binarySearch(int x[], int n, int item); 
int main()
{
     int a[5]={1,3,9,16,21};    
     int i,index, key;  
           
     printf("数组a中的数据:\n");    
     for(i=0;i<N;i++)     
       printf("%d ",a[i]);    
     printf("\n");        
     printf("输入待查找的数据项: ");
     scanf("%d", &key);
     
     index=binarySearch(a,N,key);
     
     if(index>=0)        
      printf("%d在数组中，下标为%d\n", key, index);    
      else     
      printf("%d不在数组中\n", key);  
      
      return 0; 
     
     
 } 
 int binarySearch(int x[],int n, int item){
     int low,high,mid;
     
     low = 0;    
    high = n-1; 
    
    while(low <= high) {      
      mid = (low+high)/2;                
      if (item == x[mid])            
      return mid;        
      else if(item<x[mid])            
      high = mid - 1;        
      else            
      low = mid + 1;    
      }        
      return -1;    
 }

技术分享图片

实现方式2

#include<stdio.h>
const int N=5;
int binarySearch(int *x,int n,int item);
int main()
{
     int a[5]={1,3,9,16,21};    
     int i,index, key;  
           
     printf("数组a中的数据:\n");    
     for(i=0;i<N;i++)     
       printf("%d ",a[i]);    
     printf("\n");        
     printf("输入待查找的数据项: ");
     scanf("%d", &key);
     
    index=binarySearch(a,N,key);
     
     if(index>=0)        
      printf("%d在数组中，下标为%d\n", key, index);    
      else     
      printf("%d不在数组中\n", key);  
      
      return 0; 
}
int binarySearch(int *x,int n, int item){
     int low,high,mid;
     
     low = 0;    
    high = n-1; 
    
    while(low <= high) {      
      mid = (low+high)/2;                
      if (item == *(x+mid))            
      return mid;        
      else if(item<*(x+mid))          
      high = mid - 1;        
      else            
      low = mid + 1;    
      } 
      return -1;
}

技术分享图片

part2选择法

对一组整数从小到大排序

#include<stdio.h>
const int N=5;
void selectSort(int [],int);
void input(int [],int);
void output(int [],int);
int main(){
    int a[N];
    
    printf("输入%d个整数\n", N);    
    input(a, N); 
    printf("排序前的数据:\n");    
    output(a,N);
    
    selectSort(a,N);
    
     printf("排序后的数据:\n");    
     output(a, N);
     
     return 0;  
    
}

void input(int a[], int n) {    
     int i;    
     for(i=0; i<n; i++)      
       scanf("%d", &a[i]); 
       }

void output(int a[], int n) {    
     int i;    
     for(i=0; i<n; i++)       
      printf("%d ", a[i]);    
      printf("\n"); 
      }
      
void selectSort(int a[], int n) {    
int i, j, k, temp;       
 for(i=0; i<n-1; i++) {     
    k = i; // k用于记录当前最小元素的下标                
     for(j=i+1; j<n; j++)         
        if (a[j] < a[k])              
          k = j; // 如果a[j]比当前最小元素还要小，就更新k，确保它总是存放最小元 素的下标                        
        if(k != i) { // 找到最小元素后，交换a[i]和a[k]            
          temp = a[i];           
           a[i] = a[k];            
           a[k] = temp;        
           }    
        }
}

技术分享图片

用选择法对字符串按字典顺序排序

#include<stdio.h>
#include<string.h>
void selectSort(char str[][20],int n);
int main(){
    char name[][20]={"John","Alex","Joseph","Candy","Geoge"};
    int i;
    
    printf("输入初始名单：\n");
    for(i=0;i<5;i++)
    printf("%s\n",name[i]);
    
    selectSort(name,5);
    
    printf("按字典输出名单:\n");
    for(i=0;i<5;i++)
    printf("%s\n",name[i]);
    
    return 0;
} 

void selectSort(char str[][20],int n){
    int i,k,j;
    char t[20];
    for (i=0;i<n;i++){
    k=i;
    for(j=i+1;j<n;j++)
    if(strcmp(str[k],str[j])>0)
    k=j;
    if(k!=i){
        strcpy(t,str[i]);
        strcpy(str[i],str[k]);
        strcpy(str[k],t);    
    }
}
    
}