在c中搜索数组类型struct的元素

我有一个结构数组，存储有关公司内一台pc（代码，模型，连接到互联网）的一些基本信息。在c中搜索数组类型struct的元素

typedef struct database{ 
    char code[5]; 
    char brand[20]; 
    char model[20]; 
    int lab; 
    int connect; 
}database;

现在我想通过数组搜索找到的PC coresponding的代码C01A

这里是存储在结构信息的一个小例子：

C01A HP SJH1740 1 0 
B02A HP SJ1290 3 1 
A03B DELL PQ240 2 1 
A02B DELL PQ240 3 1 
C09H FUJITSU NP0001 1 0 
A06D DELL PQ240 3 1 
C00X FUJITSU LP1050 2 0 
B89A HP SJ1290 3 1 
A03F DELL PT1000 2 0 
C12P HP AA0012 1 1 
D01D DELL BB2300H 3 0

你可以看到第一台电脑的代码是C01A。在这里我们看到了11个pc，我从其中可能有数百万个pc的文件中随机挑选出来（想象一个大公司，阵列能够容纳1000万pc，因为我可以）。

我可以只搜索数组中的每个元素，直到找到合适的元素。但（使用快速计算dunno，如果没关系）。这意味着我必须滚动10.5MB的内存，如果搜索过程没有最优化，这是相当多的。

于是我想出了这一点：

step 1：把程序启动时对数组进行排序。

第2步：开始在阵列中，检查元素

第3步：如果我要搜索的元素比检查元素小，检查上半场中段，否则检查下半部分中间

第4步：重复，直到找到该元素，或直到检查了相同的元素两次，在这种情况下该元素不存在。

这里是一个快速的代码，我想：

database searchpc(database temp[],int n){ 
    int i=n/2; 
    char code [5]; 
    printf("incerici codice da cercare: "); 
    scanf("%s",code); 
    getchar(); 
    while(strcmp(temp[i].code,code)!=0){ 
     if(strcmp(temp[i].code,code)>0) 
      i=i/2; 
     else 
      i=i*2; 
    } 
    return temp[i]; 
}

这个返回元素如果找到了，否则它陷在一个循环（这是在制品）

我测试在上面的信息和我搜索，就像在这个例子中，为C01A电脑。但它也卡住了。

我在做什么错？如果我真的需要通过很多电脑，这可以做得更快吗？

来源

2015-05-14 BRHSM

你想要做的是一个快速排序，这不是实现它的方式。谷歌“快速排序”和研究.. – LPs

@LPs我搜索了它，但我得到了非常不同的代码为每个网站，我看到像'如果x <枢轴然后添加x到少'的事情 – BRHSM

你刚刚描述了二进制搜索一个排序sequence.Your算法这样做是错误的，因为你不是通过简单地乘以或除以两来减小你的分区大小。每跳应减少一半的分区值，*然后*根据结果（较小或较大）通过减去或添加分区值以正确的方向移动。说实话，为什么要重新发明轮子，[bsearch（）]（http://en.cppreference.com/w/c/algorithm/bsearch）会为你做这件事情（假设数据是排序的，一个['qsort （）']（http://en.cppreference.com/w/c/algorithm/qsort）会很方便）。 – WhozCraig

如果i为零并且您尝试将其减半，或者如果i * 2大于n，则无法找到该结构。

来源

2015-05-14 08:41:34

那我该怎么做呢？ – BRHSM

@CoderGuy为这些情况添加检查？ –

你试图实现的是二进制搜索。您的实施不正确。它应该是这样的：

/* 
* searches for a value in sorted array 
* arr is an array to search in 
* value is searched value  
* left is an index of left boundary 
* right is an index of right boundary 
* returns position of searched value, if it presents in the array 
* or -1, if it is absent 
*/ 

int binarySearch(int arr[], int value, int left, int right) { 
     while (left <= right) { 
      int middle = (left + right)/2; 
      if (arr[middle] == value) 
        return middle; 
      else if (arr[middle] > value) 
        right = middle - 1; 
      else 
        left = middle + 1; 
     } 
     return -1; 
}

来源

2015-05-14 09:29:43 Maciej

在c中搜索数组类型struct的元素

回答

相关问题