-3

我有一个格式为： [name][number][amount] number 的文件作为字符串。我在 strcmp 中使用它。问题是我遇到了分段错误。我知道在大多数情况下，当 strcmp 标记分段错误时，这意味着参数之一为空或找不到它的“结束”（'\0'）。我检查了 gdb，我不能说这是否是问题。看看：

> (gdb) bt full
> #0  0x08048729 in lookup (hashtable=0x804b008, hashval=27, 
>     number=0x804b740 "6900101001") 
>         list = 0xffffffff
> #1  0x080487ac in add (hashtable=0x804b008, 
>     number=0x804b740 "9900101001", name=0x804b730 "Smithpolow",
> time=6943) 
>         new_elem = 0xffffffff
>         hashval = 27
> #2  0x08048b25 in main (argc=1, argv=0xbffff4b4) 
>         number = 0x804b740 "9900101001"
>         name = 0x804b730 "Smithpolow"
>         time = 6943
>         i = 2

代码：

        typedef struct  HashTable
        {
            int length;
            struct  List *head; 

        } HashTable;

        //(resolving collisions using chaining)
        typedef struct  List
        {
            char *number;
            char *name;
            int time;
            struct List *next;
        } List;

    int primes[]={17,29,51,79,163,331,673,1361,2729,5471,10949,21911,43853,87719,175447,350899};
    *int PrimesIndex=1;* **int PrimesIndex=0;**  **//changed.**


     HashTable *createHashTable(size)
    {
         HashTable *new_table = malloc(sizeof(*new_table)*size);

        if (new_table == NULL)
        {   return NULL;
        }

        int i=0;
        for(i; i<size; i++)
        {   new_table[i].length=0;
            new_table[i].head=NULL;
        }
        return new_table;
    }

    int hash ( HashTable *hashtable,char* number)
    {
        int hashval = 0;
        int i = 0;
        for ( i = 0; i < 10; i++)
        {   hashval = (hashval << 5)|(hashval >> 27);
            hashval += ( int)number[i];
        }

        return hashval % primes[PrimesIndex];
    }

         List *lookup ( HashTable *hashtable,int hashval,char number[10])
        {
         printf("NUMBER:%s\n",number);
          List *list=hashtable[hashval].head;
         for(list; list!=NULL; list=list->next){
           if (strcmp(number,list->number)==0)    
            return list;

         }
         return NULL;
        }


        int add ( HashTable* hashtable,char number[10],char* name,int time)
        {
             List *new_elem;
            int hashval=hash (hashtable,number);

            new_elem=hashtable[hashval].head;
            if(hashtable[hashval].length>0)
            {                   
                  if ((lookup (hashtable,hashval,number))!=NULL) {return 0;}    
            }

            if (!(new_elem=malloc(sizeof(struct  List)))){ return -1;}

            //insert values for the new elem
            new_elem->number=strdup(number);    
            new_elem->name=strdup(name);
            new_elem->time=time;

            hashtable[hashval].head=new_elem;
            new_elem->next=NULL;
            hashtable[hashval].length++;

            /* rehash existing entries if necessary */
            if(hashTableSize(hashtable)>= 2*primes[PrimesIndex])    
            {    
                 hashtable = expand(hashtable);
                 if (hashtable ==NULL){
                   return 0;
                 }

            }

            return 1;
        }

 HashTable* expand( HashTable* h )
{   printf("EXPAND \n");
     HashTable* new;
     List *temp;
    int n;
     List *node,*next;
    PrimesIndex++;
    int new_size= primes[PrimesIndex];      /* double the size,odd length */

    if (!(new=malloc((sizeof(  List*))*new_size))) return NULL;

    for(n=0; n< h->length; ++n) {
        for(node=h[n].head; node; node=next) {
            add (new, node->number, node->name,node->time);
            next=node->next;
            //free(node);
        }
    }
    free(h);
    return new;
}

和主要的：

  int main(int argc, char *argv[])  
    {
        char **token;
        FILE *delimitedFile;
        /*Here's an example of tokenizing lines from an actual file*/
        /*Open file for reading ("r"), and take a FILE pointer, 
          which you can use to fetch lines using fgets()*/

        my_hash_table = createHashTable(17);
        if(my_hash_table==NULL)
        {   return 1;
        }

        FILE * File2;
            if ( ( File2=fopen(" File.txt","r")) !=NULL ) 
            { // File.txt format:  [name number time]
                int li = 0;
                char *lin = (char *) malloc(MAX_LINE * sizeof(char));

                while(fgets(lin, MAX_LINE, File2) != NULL)
                {
                    token = my_linetok(lin, " ");
                    if(token != NULL)
                    {
          char* number ;
          char* name;
          int time;
          int i;
                        for(i = 0; token[i] != NULL; i++)
                        {
           name=strdup(token[0]);
           number=strdup(token[1]);
           time=atoi(token[2]);

           if (i==2)
           { int insertDone=0;
                 insertDone =add(my_hash_table,number,name,time);   

           } 
          }
          free(name); 
          free(number);
          free(token);

                    }
                    else 
             {
                        printf("Error reading line %s\n", lin);
                        exit(1);   
                    }
                }

            } 
            else 
            {
                printf("Error opening file \nEXIT!");
         exit(0);
            }

        return 1;
    }
4

3 回答 3

3

这里的根本问题是您创建了一个包含 17 个存储桶的哈希表：

my_hash_table = createHashTable(17);

但是 C 数组是从 0 开始的，并且PrimesIndex从 1 开始，而不是 0，所以在 内部add()，对 的调用hash()：

int hashval=hash (hashtable,number);

将返回一个介于 0 和 28 之间的数字，而不是介于 0 和 16 之间的数字。因此，在某些时候，将分配一个超出范围的值hashval，以及由 索引的后续访问之一hashval，例如

new_elem=hashtable[hashval].head;

将读取未初始化的内存，最终导致疯狂的指针值，如0xffffffff稍后浮出水面。

解决方案：更改int PrimesIndex = 1;为int PrimesIndex = 0;.

但老实说，我认为很可能还有其他我遗漏的问题。有：

  • 我在评论中指出的for循环内while循环的问题；main()
  • 参数的可疑声明numberto lookup_on_Clients();
  • lookup()有时会调用该函数，有时会调用该函数的事实lookup_on_Clients()（正如 Oli 所注意到的）；
  • 而且我不相信my_linetok()（您没有显示源代码）可以正常工作-至少，除非它使用静态缓冲区，否则它必须分配一个数组char *以保存指向各个令牌的指针，它永远不会被释放——内存泄漏。
于 2011-01-16T13:32:48.790 回答
2

您在number. 您将大小设置number为等于 10 个字符，但您的号码中有 10 位数字，并且没有 \0 空格。

编辑：

我查看了您更新的代码。您创建了初始大小 = 17 的哈希表，但您的 hasval = 27。但是您没有正确扩展哈希表大小的代码。

new_elem=hashtable[hashval].head;
if(hashtable[hashval].length>0) // <-- when hashval is out of array 
                                // hashtable[hashval] can have any value of length and head (not NULL)
于 2011-01-16T12:45:43.873 回答
0

您实际上并没有显示add()大概调用的来源lookup_on_Clients()，并且回溯提到lookup()而不是lookup_on_Clients()，所以我不能确定，但​​这是我的诊断：

  • 回溯说list = 0xffffffff——这绝对不是一个有效的地址，所以它可能list->name是导致 SIGSEGV 的访问。
  • 我还对number参数 tolookup_on_Clients()声明为char number[10]但 gdb 显示它包含一个 10 位数字这一事实感到困扰 - 这表明持有此参数的变量以相同的方式声明，这意味着没有空间一个终止的 0 字节。并且您调用strcmp()它的事实意味着您将其number视为以 nul 结尾的字符串，因此保存传递给lookup_on_Clients()as的参数的变量number（可能是在 ? 中声明的局部变量add()）应声明为大小为的数组至少 11 以避免崩溃。add()如果直接通过它自己的参数，你是安全的，因为它是动态分配的，通​​过 innumber足够大strdup()main()，但我仍然会更改声明lookup_on_Clients()。
于 2011-01-16T12:45:05.050 回答