sherwood.c

舍伍德算法（sherwood概率算法

#include"random.c"
#define N 1000
int val[N],ptr[N],head;
void init();
void output();

void main()
{
	int i;
	
    init();

    output();
}
void init(){
        int p,q,i;
		srand(time(NULL));
        val[1]=(int)(rand()/MAX_INT*N);   
        ptr[1]=0;
        for(i=2;i<N;i++){
            val[i]=(int)(rand()/MAX_INT*N*N);   
            ptr[i]=0;
            q=0;
            for(p=head;val[i]>=val[p]&& p!=0;){
                //查找val[i]的位置
                q=p;
                p=ptr[p];
            }
           if(q==0) //直接插入第一个位置    
           {    ptr[i]=head;head=i;}
           else
              if(p==0)//插入的位置为最后一个
                  ptr[q]=i;
              else
              {   ptr[i]=p; ptr[q]=i;  }                   
        }              
    }
void output(){
  int i;
  i=head;
  while(i!=0)
  {  printf("%d\t",val[i]);
     printf("%d\t",i);
	 i=ptr[i];}
}