算法分析-随机数生成、顺序搜索、二分搜索

算法作业终于还是竣工了，虽然还有很多地方要改进。发上来和偶尔能看到我博客的人，能看到这篇文章的，又能对你有帮助的朋友分享一下。

顺序搜索
//The algorithm is Sequentialsearch.
//The target is to get the average case.
//The program use a technique to obtain a list of random numebers.
//Author:Haibo Feng
//Time:Nov.3rd,2007


#include"stdio.h"
#include"stdlib.h"

//The rannum function.
long int Rannum()
{
int seed=40;//The seed can be changed.
int p=25173;
int i=13849;
long int m=65536;
seed=(seed*p+i)%m;
return (long int)seed/m;
}

//The Sequentialsearch function
long int ssearch(long int *p,long int n)
{ long int i,skip;
long int location=1;
long int freecount;
printf("Pleae input the quantity of the text data:");
scanf("%d",&n);
p=(long int *)malloc(n*sizeof(long int));
if(!p)
{
printf("out of memory\n");
}
for(i=1;i<=n;i++)
p[i]=0;
freecount=n;
for(i=1;i<=n;i++)
{
skip=freecount*Rannum()+1;
while(skip>0)
{
location=(location%n)+1;
if(p[location]==0)
skip=skip-1;
}
p[location]=i;
freecount=freecount-1;
}
long int j;
double ave,c=0;
for(i=1;i<=n;i++)
{for(j=0;j if(p[j]==i)
{c++;
break;
}
else c++;
}
ave=c/n;
printf("The average comparisons is:%.0f",ave);
printf("\n");
printf("The total comparisons is:%.0f",c);
}

//The main function.
main()
{ long int *p;
long int n;
long int j;
printf("The result of Sequentialsearch\n");
printf("\n");
ssearch(p,n);
printf("\n");
}


二分搜索（1）
//The algorithm is Binarysearch.
//The program use a way of arithmetic progression to obtain a ordered list.
//The target is to get the average case and total comparisons.
//Author:Haibo Feng
//Time:Oct.25th,2007

#include
#include

long int Rannum()
{
int seed=40;
int p=25173;
int i=13849;
int m=65536;
seed=(seed*p+i)%m;
return (long int)seed/m;
}

//
int *randnum(int n)
{ int i,skip;
int *p;
int location=1;
int freecount;
p=(int *)malloc(n*sizeof(int));
if(!p)
{
printf("out of memory\n");
}
for(i=1;i<=n;i++)
p[i]=0;
freecount=n;
for(i=1;i<=n;i++)
{
skip=freecount*Rannum()+1;
while(skip>0)
{
location=(location%n)+1;
if(p[location]==0)
skip=skip-1;
}
p[location]=i;
freecount=freecount-1;
}
return p;
}

//The swap function.
void swap(long int a,long int b)
{
long int temp;
temp=a;
a=b;
b=temp;
}

//The pivotlist of the quicksort algorithm.
int pivotlist(int *list,long int first,long int last)
{
int pivotvalue;
long int pivotpoint;
long int index;
pivotvalue=*(list+first-1);
pivotpoint=first;

for(index=first+1;index<=last;index++)
{if(*(list+index-1) {
pivotpoint++;
swap(*(list+pivotpoint-1),*(list+index-1));
}
}
swap(*(list+first-1),*(list+pivotpoint-1));
return pivotpoint;
}

//The quicksort algorithm.
int * quicksort(int *list,long int first,long int last)
{
long int pivot;
if(first {
pivot=pivotlist(list,first,last);
quicksort(list,first,pivot-1);
quicksort(list,pivot+1,last);
}
return list;
}

//The main function.
void main()
{
long int n,i;
int m;
int *p;
int *list;
int start,end,mid;
float total=0;
float ave;
printf("The result of Binarysearch(2)");
printf("\n");
printf("\n");
printf("Please input the quantity of the text data：");
scanf("%d",&n);
list=randnum(n);
p=quicksort(list,1,n);

for(i=1;i<=n;i++)
{start=1;
end=n;
while(start<=end)
{
mid=(start+end)/2;
m=*(p+mid-1)-i;
total++;
if(m<0)start=mid+1;
else
if(m>0)end=mid-1;
else break;
}
}
ave=total/n;
printf("The average comparisons is:%.1f",ave);
printf("\n");
printf("The total comparisons is:%.0f",total);
printf("\n");
}



二分搜索（2）
//The algorithm is Binarysearch.
//The program use a way of arithmetic progression to obtain a ordered list.
//The target is to get the average case and total comparisons.
//Author:Haibo Feng
//Time:Oct.25th,2007

#include
#include

//The binarysearch function.
int binarysearch(int *p,int n)
{
int start,end,mid;
float c=0;
int i,m;
for(i=0;i { start=0;
end=n-1;
while(start<=end)
{
mid=(start+end)/2;
m=*(p+mid)-i;
c++;
if(m<0) start=mid+1;
else if(m>0) end=mid-1;
else break;
}
}
printf("\n");
printf("The average comparisons is:%.1f",c/n);
printf("\n");
printf("The total comparisons is:%.0f",c);
printf("\n");
}

//The main function.
int main()
{int n,i,*p;
printf("The result of Binarysearch(1)\n");
printf("\n");
printf("Please input the quantity of the text data：");
scanf("%d",&n);
p=(int *)malloc(n*sizeof(int));
if(!p)
{
printf("out of memory!\n");
exit(0);
}
p[0]=1;
//printf("%d\n",p[0]);
for(i=1;i //{
p[i]=p[i-1]+1;
//To get a arithmetic progression, arithmetic progression proportion can be changed.
//printf("%d\n",p[i]); }
//There are too much numbers.so I make them unprinted.
binarysearch(p,n);//Transfer the binarysearch algorithm to search.
}