C language to achieve the maximum gap problem example

This paper illustrates the method of realizing the maximum gap problem in C language, which has certain reference value for the design of algorithm. Share with you for your reference. The details are as follows:

The problem is described as follows:

Given n real Numbers x1,x2... ,xn, to find the maximum difference between the two adjacent Numbers of the n real Numbers on the real axis, requires the design of a linear time algorithm.

Solution:

Notice that they want to design a linear time algorithm. If you don't have that, you can sort it first, and it's easy to find out. But we know that the time efficiency of the best sorting algorithm is also nlogn. So it's not feasible.

An interval algorithm is used. The specific steps do not say, give C language code, there are comments to explain.

The specific implementation code is as follows:

#include "stdio.h"
#include "stdlib.h"
#define MAX 10000
float findmin(float data[],int n){
   int index,i;
   float min,temp;
   temp=data[0];
   for(i=1;i<n;i++){
     if(data[i]<temp){
       temp=data[i];
       index=i;
     }
   }
   min=data[index];
   return min;
}
float findmax(float data[],int n){
   int index,i;
   float max,temp;
   temp=data[0];
   for(i=1;i<n;i++){
     if(data[i]>temp){
       temp=data[i];
       index=i;
     }
   }
   max=data[index];
   return max;
}
void initial(int n,int count[],float low[],float high[],float min,float max){
   int i;
   for(i=0;i<n;i++){
     count[i]=0; //Whether the interval has data stored
     low[i]=max; //Maximize the left end of the interval
     high[i]=min; //Copies the minimum value at the right end of the interval
   }
}
void dataIn(float m,int count[],float low[],float high[],int n,float data[],float min){
   int i,location;
   for(i=0;i<n;i++){
     location=int((data[i]-min)/m)+1; //Determine which interval the data enters: according to the bisection interval, the ratio of the difference between the data and the minimum value to the size of the interval +1 is the interval number
     if(location==n)
       location--;
     count[location]++; //The data is stored. Add 1 to the value
     if(data[i]<low[location]) //If the data is smaller than the left - end value, it is the left - end value
       low[location]=data[i];
     if(data[i]>high[location]) //If the data is larger than the right - end value, it is the right - end value
       high[location]=data[i];
   }
}
float findMaxGap(int n,float low[],float high[],int count[]){ 




   int i;
   float maxgap,dhigh,temp;
   dhigh=high[1];
   for(i=2;i<n;i++){
     if(count[i]){
       temp=low[i]-dhigh;
       if(maxgap<temp)
         maxgap=temp;
       dhigh=high[i];
     }
   } 
   return maxgap;
}
int main(){
  float data[MAX];
  int n,i=0;
  float min,max;
  float m,maxgap;
  float low[MAX],high[MAX];
  int count[MAX];
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%f",&data[i]);
  min=findmin(data,n);
  max=findmax(data,n);
  m=(max-min)/(n-1);
  initial(n,count,low,high,min,max);
  dataIn(m,count,low,high,n,data,min);
  maxgap=findMaxGap(n,low,high,count);
  printf("%.1f",maxgap);
  system("pause");
  return 0;
}

Interested friends can test run this article's example to deepen their understanding. It is believed that this paper has certain reference value to the learning of C program algorithm design.