在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的元素

回答

相關問題