'由于超时而终止'。需要帮助优化我的代码

I am trying to implement dictionary. I would appreciate if you find the flaws in my code rather than changing whole logic.

我正在尝试实施字典。如果你发现我的代码中存在缺陷而不是改变整个逻辑，我将不胜感激。

Sample Input
3
sam 99912222
tom 11122222
harry 12299933
sam
edward
harry

样本输入3 sam 99912222 tom 11122222 harry 12299933 sam edward harry

Sample Output :
sam=99912222
Not found
harry=12299933

样品输出：sam = 99912222未找到harry = 12299933

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct Dict {
  char key[100];
  int value;
};

struct Dict *array;
int inputsize;

int getHashKey(char *key){
  return strlen(key)%inputsize;

}

void insert(char *key, int value){
  int i =0;
  int hashkey = getHashKey(key);

  /* Already inserted. Return */
  if(!strcmp (array[hashkey].key,key)){
   return;
  }

  /* Check if empty space. else, Get the next available space. */
  if(array[hashkey].value == 0){
    strcpy(array[hashkey].key,key);
    array[hashkey].value = value;  
  }else{ 
    hashkey++;
    while(array[hashkey].value!=0){
           hashkey++;
           /*if reached end of array. Re-start */
           if(hashkey == inputsize ){
           hashkey = 0;
           }
   }
   strcpy(array[hashkey].key,key);
   array[hashkey].value = value;
  }
}

void search(char *key){

 for(int i =0;i<inputsize;i++){    
    if(!strcmp(array[i].key,key)){
    printf("%s=%d\n",array[i].key,array[i].value);
    return;
    }
 }
 printf("Not found\n");
}



int main() {

  char key[100]; int value;
  scanf("%d",&inputsize);

  char *ptr[inputsize];

  //Initializing array pointer
  for(int i=0;i<inputsize;i++){
  ptr[i] = (char *)malloc(sizeof(char) * 100);
  }

  array = (struct Dict *)malloc(sizeof(struct Dict)*inputsize);

  /*Reading Input.Key & value pair */
  for(int i=0;i<inputsize;i++){
  scanf("\n%20[^ ]",key);
  scanf("%d",&value);
  insert(key,value);
  }

  /*Reading Query */
  for(int i =0; i<inputsize;i++){
  scanf("%s",ptr[i]);
  } 

  /* Searching Query String in Dict */
  for(int i =0;i<inputsize;i++){
  search(ptr[i]);
  }

  return 0;
}

2 个解决方案

#1

The following loop is never ending:

以下循环永无止境：

while (array[hashkey].value != 0) {
    hashkey++;
    /*if reached end of array. Re-start */
    if (hashkey == inputsize) {
        hashkey = 0;
    }
}

You have to review your algorithm to let it properly end. The first thing you can do is to zeroed-out your array in order to be sure that it is properly initialized before using it. malloc is just allocating the memory. It is not performing any initialization for you.

您必须检查您的算法才能正确结束。您可以做的第一件事是将数组清零，以确保在使用之前正确初始化它。 malloc只是分配内存。它没有为您执行任何初始化。

array = (struct Dict *)malloc(sizeof(struct Dict)*inputsize);
memset(array, 0, sizeof(sizeof(struct Dict)*inputsize));

#2

You seem to be building a hash table, but when searching you perform a linear scan. This means that search is O(N) instead of close to O(1) when using linear hashing scheme.

您似乎正在构建哈希表，但在搜索时执行线性扫描。这意味着当使用线性散列方案时，搜索是O（N）而不是接近O（1）。

#1