本文实例展示了C语言实现最大间隙问题的方法，对于算法的设计有一定的借鉴价值。分享给大家供大家参考。具体如下：

问题描述如下：

给定n个实数x1,x2,...,xn,求这n个实数在实轴上相邻2个数之间的最大差值,要求设计线性的时间算法。

解决思路：

注意题中要求设计线性时间算法。如果没有这个要求，就可以先排序，找出来就很方便。但我们知道排序最优良的算法的时间效率也是nlogn的。所以不可行。

采用一种区间算法。具体步骤就不说了，给出C语言代码，有注释加以说明。

具体实现代码如下：

#include "stdio.h"#include "stdlib.h"#define MAX 10000float 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; //区间是否有数据存入 low[i]=max; //将区间的左端赋值最大值 high[i]=min; //将区间的右端复制最小值 }}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; //判断数据进入哪个区间:按照等分区间，数据与最小值的差与区间大小的比值+1就是区间编号 if(location==n) location--; count[location]++; //有数据存入，计数值加1 if(data[i]<low[location]) //如果数据比左端值小，则作为左端值 low[location]=data[i]; if(data[i]>high[location]) //如果数据比右端值大，则作为右端值 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;}

感兴趣的朋友可以测试运行本文实例以加深理解。相信本文所述对大家C程序算法设计的学习有一定的借鉴价值。