c - 段。哈希表 ADT 中的错误 - C

Question

编辑:

Hash.c 根据评论进行了更新，我仍然遇到段错误。我一定漏掉了你们所说的一些东西

我已经使用 C 创建了哈希表 ADT，但是当我尝试在 ADT 中调用函数 (find_hash) 时遇到了段错误。

我已经发布了我创建的 parse.c、hash.c 和 hash.h 的所有 3 个文件，因此您可以看到所有变量。我们正在从附件中的 gettysburg.txt 文件中读取

当我调用 find_hash 时，parse.c 中发生段错误。我无法弄清楚这里发生了什么。如果您需要更多信息，我一定可以提供。

对于大量的代码，我已经完全困惑了一个星期，对此深表歉意。提前致谢

我运行程序的方式首先是: gcc -o 解析 parse.c hash.c然后:cat gettysburg.txt |解析

解析.c

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include "hash.h"

#define WORD_SIZE 40
#define DICTIONARY_SIZE 1000

#define TRUE 1
#define FALSE 0


void lower_case_word(char *);
void dump_dictionary(Phash_table ); 

/*Hash and compare functions*/
int hash_func(char *);
int cmp_func(void *, void *);

typedef struct user_data_ {   
    char word[WORD_SIZE];
    int freq_counter;
} user_data, *Puser_data;

int main(void)
{
   char c, word1[WORD_SIZE];
   int char_index = 0, dictionary_size = 0, num_words = 0, i;
   int total=0, largest=0;
   float average = 0.0;

   Phash_table t;                  //Pointer to main hash_table
   int (*Phash_func)(char *)=NULL;         //Function Pointers
   int (*Pcmp_func)(void *, void *)=NULL;
   Puser_data data_node;                   //pointer to hash table above
   user_data * find;


   printf("Parsing input ...\n");

   Phash_func = hash_func;   //Assigning Function pointers
   Pcmp_func = cmp_func;
   t = new_hash(1000,Phash_func,Pcmp_func);

  // Read in characters until end is reached 
  while ((c = getchar()) != EOF) {
    if ((c == ' ') || (c == ',') || (c == '.') || (c == '!') || (c == '"') ||
        (c == ':') || (c == '\n')) {
          // End of a word 
      if (char_index) {
          // Word is not empty 
        word1[char_index] = '\0';
        lower_case_word(word1);

        data_node = (Puser_data)malloc(sizeof(user_data));  
        strcpy(data_node->word,word1);
        printf("%s\n", data_node->word);


    //!!!!!!SEG FAULT HERE!!!!!!

        if (!((user_data *)find_hash(t, data_node->word))){   //SEG FAULT!!!!
         insert_hash(t,word1,(void *)data_node); 
        }

        char_index = 0;
        num_words++;
      }
    } else {
      // Continue assembling word 
      word1[char_index++] = c;
    }
  }

  printf("There were %d words; %d unique words.\n", num_words,
     dictionary_size);
  dump_dictionary(t);  //???

  }

void lower_case_word(char *w){
  int i = 0;

  while (w[i] != '\0') {
    w[i] = tolower(w[i]);
    i++;
  }
}

void dump_dictionary(Phash_table t){  //???
  int i;
  user_data *cur, *cur2;

  stat_hash(t, &(t->total), &(t->largest), &(t->average));   //Call to stat hash
    printf("Number of unique words:  %d\n", t->total);
    printf("Largest Bucket:  %d\n", t->largest);
    printf("Average Bucket:  %f\n", t->average);  

  cur = start_hash_walk(t);
  printf("%s:  %d\n", cur->word, cur->freq_counter);

  for (i = 0; i < t->total; i++)
     cur2 = next_hash_walk(t);
     printf("%s:  %d\n", cur2->word, cur2->freq_counter);
}

int hash_func(char *string){
    int i, sum=0, temp, index;

    for(i=0; i < strlen(string);i++){
        sum += (int)string[i];  
    }
    index = sum % 1000;
return (index); 
}


/*array1 and array2 point to the user defined data struct defined above*/
int cmp_func(void *array1, void *array2){

user_data *cur1= array1;
user_data *cur2= array2;//(user_data *)array2;

    if(cur1->freq_counter < cur2->freq_counter){
        return(-1);}
        else{ if(cur1->freq_counter > cur2->freq_counter){
                return(1);}
                else return(0);}
}

哈希.c

#include "hash.h"

Phash_table new_hash (int size, int(*hash_func)(char*), int(*cmp_func)(void*, void*)){
    int i;
    Phash_table t;

    t = (Phash_table)malloc(sizeof(hash_table));   //creates the main hash table
    t->buckets = (hash_entry **)malloc(sizeof(hash_entry *)*size);  //creates the hash table of "size" buckets
    t->size = size;   //Holds the number of buckets
    t->hash_func = hash_func;   //assigning the pointer to the function in the user's program
    t->cmp_func = cmp_func;     // "  "  
    t->total=0;
    t->largest=0;
    t->average=0;
    t->sorted_array = NULL;
    t->index=0;
    t->sort_num=0;

    for(i=0;i<size;i++){   //Sets all buckets in hash table to NULL
        t->buckets[i] = NULL;}

    return(t);
}

void free_hash(Phash_table table){
    int i;
    hash_entry *cur;

    for(i = 0; i<(table->size);i++){
        if(table->buckets[i] != NULL){
            for(cur=table->buckets[i]; cur->next != NULL; cur=cur->next){
                free(cur->key);  //Freeing memory for key and data
                free(cur->data);
            }
      free(table->buckets[i]);    //free the whole bucket
    }}
    free(table->sorted_array);
    free(table);
}

void insert_hash(Phash_table table, char *key, void *data){
    Phash_entry new_node;   //pointer to a new node of type hash_entry
    int index;

    new_node = (Phash_entry)malloc(sizeof(hash_entry));
    new_node->key = (char *)malloc(sizeof(char)*(strlen(key)+1)); //creates the key array based on the length of the string-based key
    new_node->data = data;       //stores the user's data into the node
    strcpy(new_node->key,key);   //copies the key into the node

                                //calling the hash function in the user's program
    index = table->hash_func(key);    //index will hold the hash table value for where the new node will be placed
    table->buckets[index] = new_node; //Assigns the pointer at the index value to the new node
    table->total++;   //increment the total (total # of buckets)
}

void *find_hash(Phash_table table, char *key){
    int i;
    hash_entry *cur;
   printf("Inside find_hash\n"); //REMOVE

    for(i = 0;i<table->size;i++){
        if(table->buckets[i]!=NULL){            
            for(cur = table->buckets[i]; cur->next != NULL; cur = cur->next){
                if(strcmp(table->buckets[i]->key, key) == 0)
                return((table->buckets[i]->data));}  //returns the data to the user if the key values match
        }    //otherwise return NULL, if no match was found.
    }   
    return NULL;
}
void stat_hash(Phash_table table, int *total, int *largest, float *average){

    int node_num[table->size];  //creates an array, same size as table->size(# of buckets)
    int i,j, count = 0;
    int largest_buck = 0;
    hash_entry *cur;

    for(i = 0; i < table->size; i ++){
        if(table->buckets[i] != NULL){
            for(cur=table->buckets[i]; cur->next!=NULL; cur = cur->next){
                count ++;}
            node_num[i] = count;
            count = 0;}
        }

    for(j = 0; j < table->size; j ++){      
        if(node_num[j] > largest_buck)
            largest_buck = node_num[j];}

    *total = table->total;
    *largest = largest_buck;
    *average = (table->total) / (table->size);
}

void *start_hash_walk(Phash_table table){
    Phash_table temp = table;
    int i, j, k;
    hash_entry *cur;  //CHANGE IF NEEDED to HASH_TABLE *

    if(table->sorted_array != NULL) free(table->sorted_array);

    table->sorted_array = (void**)malloc(sizeof(void*)*(table->total));

    for(i = 0; i < table->total; i++){
        if(table->buckets[i]!=NULL){
            for(cur=table->buckets[i]; cur->next != NULL; cur=cur->next){
                table->sorted_array[i] = table->buckets[i]->data;
        }}
    }

    for(j = (table->total) - 1; j > 0; j --)    {
        for(k = 1; k <= j; k ++){
            if(table->cmp_func(table->sorted_array[k-1], table->sorted_array[k]) == 1){
                temp -> buckets[0]-> data = table->sorted_array[k-1];
                table->sorted_array[k-1] = table->sorted_array[k];
                table->sorted_array[k] = temp->buckets[0] -> data;
            }
        }
    }
    return table->sorted_array[table->sort_num];
}

void *next_hash_walk(Phash_table table){ 

    table->sort_num ++;
    return table->sorted_array[table->sort_num];
}

哈希.h

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

typedef struct hash_entry_ {    //Linked List
    void *data;                 //Generic pointer
    char *key;                  //String-based key value
    struct hash_entry_ *next;   //Self-Referencing pointer
} hash_entry, *Phash_entry;

typedef struct hash_table_ {
    hash_entry **buckets;           //Pointer to a pointer to a Linked List of type hash_entry
    int (*hash_func)(char *);
    int (*cmp_func)(void *, void *);
    int size;
    void **sorted_array;         //Array used to sort each hash entry
    int index;
    int total;
    int largest;
    float average;  
    int sort_num;
} hash_table, *Phash_table;


Phash_table new_hash(int size, int (*hash_func)(char *), int (*cmp_func)(void *, void *));
void free_hash(Phash_table table);
void insert_hash(Phash_table table, char *key, void *data);
void *find_hash(Phash_table table, char *key);
void stat_hash(Phash_table table, int *total, int *largest, float *average);
void *start_hash_walk(Phash_table table);
void *next_hash_walk(Phash_table table);

葛底斯堡.txt

Four score and seven years ago, our fathers brought forth upon this continent a new nation: conceived in liberty, and dedicated to the proposition that all men are created equal.

Now we are engaged in a great civil war. . .testing whether that nation, or any nation so conceived and so dedicated. . . can long endure. We are met on a great battlefield of that war.

We have come to dedicate a portion of that field as a final resting place for those who here gave their lives that that nation might live. It is altogether fitting and proper that we should do this.

But, in a larger sense, we cannot dedicate. . .we cannot consecrate. . . we cannot hallow this ground. The brave men, living and dead, who struggled here have consecrated it, far above our poor power to add or detract. The world will little note, nor long remember, what we say here, but it can never forget what they did here.

It is for us the living, rather, to be dedicated here to the unfinished work which they who fought here have thus far so nobly advanced. It is rather for us to be here dedicated to the great task remaining before us. . .that from these honored dead we take increased devotion to that cause for which they gave the last full measure of devotion. . . that we here highly resolve that these dead shall not have died in vain. . . that this nation, under God, shall have a new birth of freedom. . . and that government of the people. . .by the people. . .for the people. . . shall not perish from the earth. 

Answer 1

这段代码的几个问题之一可能是像这样的循环:

for(table->buckets[i]; 
    table->buckets[i]->next != NULL; 
    table->buckets[i] = table->buckets[i]->next)
  ...

for 循环的初始化部分 (table->buckets[i]) 无效。如果 i 为 0 且 table->buckets[0] == NULL，则此循环的条件 (table->buckets[i]->next != NULL) 将取消引用空指针并崩溃。

这就是您的代码似乎在我的盒子上崩溃的地方，至少。当我将您的几个循环更改为:

if (table->buckets[i] != NULL) {
  for(; 
      table->buckets[i]->next != NULL; 
      table->buckets[i] = table->buckets[i]->next)
    ...
}

...它一直在崩溃，但在不同的地方。也许这会帮助您摆脱困境？

---

编辑:另一个潜在的问题是那些 for 循环是破坏性的。当您调用 find_hash 时，您真的要修改所有这些桶吗？

我建议使用类似的东西:

hash_entry *cur;
// ...
if (table->buckets[i] != NULL) {
  for (cur = table->buckets[i]; cur->next != NULL; cur = cur->next) {
    // ...
  }
}

当我这样做并注释掉您的 dump_dictionary 函数时，您的代码运行时不会崩溃。