c - C 中的哈希表项目...取消引用指向不完整类型错误的指针-6ren

c - C 中的哈希表项目...取消引用指向不完整类型错误的指针

转载作者：行者123 更新时间：2023-11-30 19:23:24

我似乎在这个项目上兜圈子!我收到了很多“取消引用指向不完整类型的指针”的错误，并且还有很多其他错误。似乎当我修复另一个时，就会弹出一个来取代它的位置!这是我第一次使用哈希表，我承认我很迷茫，但我认为我至少有了一个很好的开始。任何有关如何解决我的“取消引用指向不完整类型的指针”问题的输入都将是令人惊奇的!

htable.c

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

struct htablerec {
   int size;
   int num_entries;
   hashing_t method;
   char **keys;       
   int *freqs;
   int *stats;
};

void *emalloc(size_t s) {
   void *result = malloc(s);
   if (NULL == result) {
      fprintf(stderr, "Memory allocation failed!\n");
      exit(EXIT_FAILURE);
   }
   return result;
}
/*moves pointer to point to something appropriate*/
htable htable_new(int capacity) {
   int i;
   htable ht = emalloc(sizeof *ht);
   ht->size = size;
   ht->method = method;
   ht->num_keys = 0;
   ht->keys = emalloc(size * sizeof ht->keys[0]);
   ht->freqs = emalloc(size * sizeof ht->freqs[0]);
   ht->stats = emalloc(size * sizeof ht->stats[0]);

   for(i = 0; i<size; i++){
      ht->keys[i] = NULL;
      ht->freqs[i] = 0;
      ht->stats[i] = 0;
   }

   return ht;
}

static unsigned int htable_step(htable h, unsigned int i_key){
   return 1 + (i_key % (h->size - 1));
}

static unsigned int htable_wtoi(char *word){
   unsigned int result = 0;
   while(*word != '\0') result = (*word++ +31 * result);
   return result;
}

static unsigned int htable_hash(htable h, unsigned int i_key){
   return i_key % h->size;
}


void htable_free(htable h) {
   int i;
   for(i = 0; i<h->size; i++){
      if(h->keys[i] != NULL){
         free(h->keys[i]);
      }
   }
   if(h->keys != NULL){
      free(h->keys);
   }
   if(h->freqs != NULL){
      free(h->freqs);
   }
   free(h);
}

static unsigned int htable_word_to_int(char *word) {
   unsigned int result = 0;
   while (*word != '\0') {
      result = (*word++ + 31 * result);
   }
   return result;
}


int htable_insert(htable h, char *str) {
   int num_collisions = 0;
   int i_key = htable_wtoi(key);
   int pos = htable_hash(h, i_key);
   int step = 1;

   if(h->method == DOUBLE)
      step = htable_step(h, i_key);

   while(h->keys[pos]!=NULL && 
         strcmp(h->keys[pos],key)!=0 &&
         num_collisions < h->size ){

      pos = htable_hash(h, pos + step);
      num_collisions++;
   }

   if(h->keys[pos] == NULL){
      h->keys[pos] = emalloc((strlen(key)+1) * sizeof h->keys[0][0]);
      strcpy(h->keys[pos],key);
      h->stats[h->num_keys] = num_collisions; 
      h->num_keys++;
   }

   if(num_collisions >= h->size) /* We must be full, so return zero.*/
      return 0; 

   return  ++(h->freqs[pos]);
}

static int htable_search(htable h, char *key){
   int num_collisions = 0;
   int i_key = htable_wtoi(key);
   int pos = htable_hash(h, i_key); 
   int step = 1;

   if(h->method == DOUBLE)
      step = htable_step(h, i_key);

   while(h->keys[pos]!=NULL && 
         strcmp(h->keys[pos],key)!=0 &&
         num_collisions < h->size ){

      pos = htable_hash(h, pos + step);
      num_keys++;
   }

   if(num_keys >= h->size)
      return 0;
   else 
      return h->freqs[pos];
}


void htable_print(htable h, FILE *stream){
   int i;
   for(i = 0; i<h->size; i++){
      if(h->keys[i] != NULL)
         fprintf(stream, "%d\t%s\n",i, h->freqs[i], h->keys[i]);
   }
}

void htable_print_entire_table(htable h, FILE *stream) {
   int i;
   for (i=0; loop < h->capacity; i++) {
      if (h->key[i] != NULL) {
         fprintf("%d\t%s\n", h->freqs[i], h->key[i]);
      }
   }
}

/**
 * Prints a line of data indicating the state of the hash table when
 * it is a given percentage full.
 * 
 * The data is printed out right justified (with the given field widths,
 * and decimal places) in this order:
 *
 * - How full the hash-table is as a percentage            (4)
 * - How many keys are in the hash-table at that point     (11)
 * - What percentage of those keys were placed 'at home'   (12, 1 dp)
 * - The average number of collisions per key placed       (12, 2 dp)
 * - The maximum number of collisions while placing a key  (12)
 *
 * @param h the hash-table to get data from.
 * @param stream the place to send output to.
 * @param percent_full the point at which to print the statistics.
 *                     If the hashtable is less full than that, then
 *                     nothing will be printed.
 */
static void print_stats_line(htable h, FILE *stream, int percent_full) {
   int current_entries = h->capacity * percent_full / 100;
   double average_collisions = 0.0;
   int at_home = 0;
   int max_collisions = 0;
   int i = 0;

   if (current_entries > 0 && current_entries <= h->num_keys) {
      for (i = 0; i < current_entries; i++) {
         if (h->stats[i] == 0) {
            at_home++;
         } 
         if (h->stats[i] > max_collisions) {
            max_collisions = h->stats[i];
         }
         average_collisions += h->stats[i];
      }

      fprintf(stream, "%4d%11d%12.1f%12.2f%12d\n", percent_full,
              current_entries, at_home * 100.0 / current_entries,
              average_collisions / current_entries, max_collisions);
   }
}

void htable_print_stats(htable ht, FILE *stream, int num_stats) {
   int i;
   fprintf(stream, "Percent   Current   Percent    Average      Maximum\n");
   fprintf(stream, " Full    Entries   At Home    Collisions   Collisions\n");
   fprintf(stream, "-----------------------------------------------------\n");

   for (i = 1; i <= num_stats; i++) {
      print_stats_line(ht, stream, 100 * i / num_stats);
   }

   fprintf(stream, "-----------------------------------------------------\n\n");
}

htable.h

#ifndef HTABLE_H
#define HTABLE_H

#include <stdio.h>

typedef struct hashtable *htable;

typedef enum hashing_e { LINEAR, DOUBLE } hashing_t;

extern htable htable_new(int size);
extern void htable_destroy(htable ht);
extern int htable_insert(htable h, char *key);
extern int htable_search(htable h, char *key);
extern void htable_print(htable h, FILE *stream);
extern void htable_print_stats(htable ht, FILE *stream, int num_stats);

#endif

main.c(由导师提供以适应项目)

/**
 * @file main.c
 * @author Iain Hewson
 * @date August 2012
 * 
 * This program is written to test the hash table ADT specified in
 * Cosc242 assignment two.  It creates a hash table which can use
 * linear-probing or double-hashing as a collision resolution
 * strategy.  Various options are provided which make it possible to
 * examine a hash table as well as see how it performs while being
 * filled.
 */

#include <stdio.h>
#include <stdlib.h>
#include <getopt.h>
#include "mylib.h"
#include "htable.h"

/* A boolean type which can be TRUE or FALSE */
typedef enum bool_e {FALSE, TRUE} bool_t;

/* function declarations */
static void usage(char *progname);
static void setup(int argc, char **argv, bool_t *double_hashing,
                      bool_t *entire_table, bool_t *print_stats,
                      int *snapshots, int *tablesize);

/**
 *
 * Creates a hash-table and inserts words into it read from stdin.
 * Arguments on the command line alter the behaviour of the program
 * as follows:
 *  -   -d       Use double hashing (linear probing is the default)
 *  -   -e       Display entire contents of hash-table on stderr
 *  -   -n NUM   Show NUM statistics snapshots (if -p is used)
 *  -   -p       Print stats info instead of frequencies & words
 *  -   -s SIZE  Use the first prime >= SIZE as htable size
 *  -   -h       Display this message
 *
 *  By default each word and it's frequency are printed to stdout.
 *      
 *  @param argc the number of command-line arguments.
 *  @param argv an array of strings containing the command-line arguments.
 *
 *  @return EXIT_SUCCESS if the program is successful.
 */
int main(int argc,char **argv) {
   bool_t entire_table = FALSE, double_hashing = FALSE, print_stats = FALSE;
   int tablesize = 0, snapshots = 0;
   char word[256];
   htable ht;

   setup(argc, argv, &double_hashing, &entire_table, &print_stats,
             &snapshots, &tablesize);

   ht = htable_new(tablesize, (double_hashing) ? DOUBLE_H : LINEAR_P);

   while (getword(word, sizeof word, stdin) != EOF) {
      htable_insert(ht, word);
   }
   if (entire_table) {
      htable_print_entire_table(ht, stderr);
   }
   if (print_stats) {
      htable_print_stats(ht, stdout, snapshots);
   } else {
      htable_print(ht, stdout);  /* print words and frequencies */
   }
   htable_free(ht);

   return EXIT_SUCCESS;
}

/**
 * Prints out a usage message to stderr outlining all of the options.
 * @param prog_name the name of the program to include in usage message.
 */
static void usage(char *prog_name) {
   fprintf(stderr, "Usage: %s [OPTION]... <STDIN>\n\n%s%s", prog_name,
      "Perform various operations using a hash-table.  By default read\n"
      "words from stdin and print them with their frequencies to stdout.\n\n"
      " -d       Use double hashing (linear probing is the default)\n"
      " -e       Display entire contents of hash-table on stderr\n",
      " -n NUM   Show NUM stats snapshots (if -p is used)\n"
      " -p       Print stats info instead of frequencies & words\n"
      " -s SIZE  Use the first prime >= SIZE as htable size\n\n"
      " -h       Display this message\n\n");
}

/**
 * Handle options given on the command-line by setting a number of
 * variables appropriately.  May call usage() if incorrect arguments
 * or -h given.
 *
 * @param argc the number of command-line arguments.
 * @param argv an array of strings contain the command-line arguments.
 * @param double_hashing set to TRUE if -d given
 * @param entire_table set to TRUE if -e given
 * @param snapshots set to NUM if -n NUM given and NUM > 0 else set to 10 
 * @param print_stats set to TRUE if -p given
 * @param tablesize set to SIZE if -t SIZE given and SIZE > 0 else set to 113
 */
static void setup(int argc, char **argv, bool_t *double_hashing,
                      bool_t *entire_table, bool_t *print_stats,
                      int *snapshots, int *tablesize) {
   const char *optstring = "dehpn:s:";
   char option;

   while ((option = getopt(argc, argv, optstring)) != EOF) {
      switch (option) {
      case 'd':
         *double_hashing = TRUE;
         break;
      case 'e':
         *entire_table = TRUE;
         break;
      case 'p':
         *print_stats = TRUE;
         break;
      case 'n':
         *snapshots = atoi(optarg);
         break;
      case 's':
         *tablesize = atoi(optarg);
         break;
      case 'h':
      default:
         usage(argv[0]);
         exit(EXIT_SUCCESS);
      }
   }
   /* set default values if nothing sensible entered */
   if (*tablesize < 1) *tablesize = 113;
   if (*snapshots < 1) *snapshots = 10;
}

mylib.c

#include <stdlib.h>
#include "mylib.h"


/**************************
 *                        *
 *   emalloc              *
 *                        *
 **************************

 Used to handle new memory allocation to a pointer and handle exceptions 
 which may arrise if memory allocation fails, which happens all the time 
 when you try and enter negative values. 

 PARAMETERS: s       = calculated size of required memory. 

 RETURN VALUE: a pointer of any type.

*/

void *emalloc(size_t s){
   void *result = malloc(s);
   if(NULL == result){
      fprintf(stderr, "Memory allocation failed!\n");
      exit(EXIT_FAILURE);
   }
   return result;
}

/**************************
 *                        *
 *   erealloc             *
 *                        *
 **************************

 Handles the reallocation of an updated amount of memory to an existing
 with existing data attached.

 PARAMETERS: p       = the existing pointer we would like additional memory
                       allocated to.
             s       = calculated size of required memory. 

 RETURN VALUE: a pointer of any type.

*/

void *erealloc(void *p, size_t s){
   void *result = realloc(p,s);
   if(NULL == result){
      fprintf(stderr, "Memory allocation failed!\n");
      exit(EXIT_FAILURE);
   }
   return result;
}

/**************************
 *                        *
 *   getword              *
 *                        *
 **************************

 Is used to read input from the designated file stream (standard in for the 
 assignment). Getword removes white space with the first while loop. And only
 returns one word. Maintaining continous input is therefore the responsibility
 of the calling function.

 PARAMETERS: s       = the pointer to the character array.
             limit   = the maximum size a word can be.
              stream  = where to read from.

 RETURN VALUE: the integer value of the character at s[0]. The string s does
               not need to be returned, since it is an array and is passed as 
               a memory address. If no chars were read into the string s, then
                s[0] would have the '\0' [NULL] value which equates to 0 if used
                in a boolean equation.

*/

int getword(char *s, int limit, FILE *stream){
   int c;

   while(!isalnum( c = getc(stream)) && c != EOF);

   if(c == EOF)
      return EOF;
   else
      *s++ = tolower(c);

   while(--limit > 0){
      if(isalnum(c = getc(stream)))
         *s++ = tolower(c);
      else if('\'' == c) continue;
      else break;
   }
   *s = '\0';
   return s[0];
}

/**************************
 *                        *
 *   stoi                 *
 *                        *
 **************************

 Not using this function now.

 PARAMETERS: s       = string representation of a number. 

 RETURN VALUE: the integer value.

*/

int stoi(char *s){
   int i,j,r;
   int sign = 1;
   i=1;
   r=0;

   for(j=my_strlen(s)-1; j>=0; j--){
      if(j == 0 && s[j] == '-')
         sign = -1;
      else {
         if(s[j]>='0' && s[j]<='9'){
            r+=((s[j]-'0')*i);
            i*=10;
         } else {
            fprintf(stderr, "Invalid input for String to int\n");
            exit(EXIT_FAILURE);
         }
      }
   }
   return r * sign;
}

/**************************
 *                        *
 *   my_strlen            *
 *                        *
 **************************

 I am using my own string length function, but I wrote it with the stoi
 function, so am using it here. Perhaps not as safe as the library 
 functions?

 PARAMETERS: s       = a string delimited by the NULL character. 

 RETURN VALUE: the number of characters in the string.

*/

int my_strlen(char *s){
   int i=0;
   while(s[i]!='\0')
      i++;
   return i;
}

/**************************
 *                        *
 *   factors              *
 *                        *
 **************************

 Another unrequired function used to calculate the possiblity of factorisation.

 PARAMETERS: x       = An integer to be factored towards. 

 RETURN VALUE: 0 if x has factors, 1 if x is a prime number.

*/


static int factors(int x){
   int f = 2;
   while(f*f < x){
      if(x % f == 0){
         return 0;
      } else { 
         f++;
      }
   }
   return 1;
}

/**************************
 *                        *
 *   prime_gt             *
 *                        *
 **************************

 Used in conjunction with factors to find factorless integers. We increment
 bound until it is truely prime.

 Bound   - We start with bound, sending it to the factors function. If it is 
           a prime number, then stop searching. Otherwise loop until we find
            an prime integer larger than the input integer.

 PARAMETERS: s       = the input integer. 

 RETURN VALUE: Bound, for it is now a prime number.

*/

static int prime_gt(int s){
   int bound = s;
   while(bound > 0){
      if(factors(bound))
         break;
      else 
         bound++;
   }
   return bound;
}

/**************************
 *                        *
 *   relative_prime       *
 *                        *
 **************************

 Decides on a prime number to use to set the table size to.

 PARAMETERS: s       = the required size of the table. 

 RETURN VALUE: the newer beter prime number size for the table.

*/

unsigned int relative_prime(int s){
   return prime_gt(s);
}