Question

一道C语言的题目

1、以顺序存储结构来实现；
2、实现顺序查找、折半查找、分块查找算法；
3、所有查找算法应该以函数的形式表示；
4、数据通过随机函数产生

如果能运行成功还有加分 谢谢~
题目就是：通过随机产生1组数据里，查找用户输入的关键字

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
const int ARRSIZE= 10015;
// 从小到大排序数组元素

void asort(int *a, int s)
{
int i, j, k, t;

for (i = 0; i < s-1; ++i)
{
k = i;

for (j = i + 1; j < s; ++j)
{
if (a[k] > a[j])
{
k = j;
}
}

if (k != i)
{
t = a[i];
a[i] = a[k];
a[k] = t;
}
}
}

// 顺序查找，找到返回该元素数组下标，否则返回-1
int SeqSearch(int *a, int s, int k)
{
int i;
for (i = 0; i < s; ++i)
{
if (k == a[i])
return i;
}

return -1;
}

// 折半查找，找到返回该元素数组下标，否则返回-1
int BinSearch(int *a, int s, int k)
{
int low = 0;
int high = s - 1;

while (low <= high)
{
int mid = (low + high) / 2;

if (k == a[mid])
{
return mid;
}
else
{
if (k < a[mid])
high = mid - 1;
else
low = mid + 1;
}
}

return -1;
}

// 分块查找，找到返回该元素数组下标，否则返回-1，bs表示数列分成的块数
int BlkSearch(int *a, int s, int k, int bs)
{
int i, j, t = s / bs;

for (i = 0; i < bs; ++i)
{
if (k >= a[i*t] && k <= a[i*t+t-1])
{
int e = i*t+t;
for (j = i*t; j < e; ++j)
if (k == a[j])
return j;
}
}

--i;
for (i = i * bs; i < s; ++i)
{
if (k == a[i])
return i;
}
return -1;
}

void main()
{
int i, k, a[ARRSIZE];

srand(time(NULL));
for (i = 0; i < ARRSIZE; ++i)
a[i] = rand() % ARRSIZE;

asort(a, ARRSIZE);

/*
for (i = 0; i < ARRSIZE; ++i)
printf("%d ", a[i]);
*/
putchar('\n');
scanf("%d", &k);
if (SeqSearch(a, ARRSIZE, k) != -1)
printf("%d is found in array\n", k);
if (BinSearch(a, ARRSIZE, k) != -1)
printf("%d is found in array\n", k);
if (BlkSearch(a, ARRSIZE, k, 100) != -1)
printf("%d is found in array\n", k);

}

Answer 2

题目呢？怎么只有要求？

Answer 3

#include<iostream>
#include<algorithm>
using namespace std;
int num[1001];//顺序存储结构...
int randnum(int n){return rand()%(n+1);}//产生0..n的随机数...
void randinit(int n)//随机产生数据...
{
int i;
for(i=0;i<n;++i)
num[i]=randnum(1001);
}
int bins(int l,int r,int val)//l-左边界,r-右边界,val-要找的值...必须保证num有序...
{
int mid;
while(l<=r)
{
mid=(l+r)/2;
if(num[mid]==val)
return mid;
if(num[mid]<val)
l=mid+1;
else
r=mid-1;
}
return -1;
}
int lines(int n,int val)//线性查找val...
{
int i;
for(i=0;i<n;++i)if(num[i]==val)return i;
return -1;
}
int lineseg(int l,int r,int val)//[l,r]区间块内查找val...
{
int i;
for(i=l;i<=r;++i)
if(num[i]==val)
return i;
return -1;
}
int main()
{
int n;
scanf("%d",&n);
randinit(n);
sort(num,num+n);//要想折半查找，排序是必须的...这里是从小到大排..
return 0;
}