1

我需要一些有关单链表的帮助。我正在尝试为从我的文本文件中读取的每个单词插入一个新节点，并将其与字典文件中的单词进行比较。从那里，新节点被插入到哈希表中。我觉得我很接近（也许是渴望的想法)，但每次运行程序时都会出现分段错误。从我的代码的外观来看，有没有人知道可能出了什么问题？

typedef struct Node {    

 char word[LENGTH+1];  

 struct Node *Next;    
 } Node;

hash_table_t  *create_hash_table(int size)
hashtable = malloc(sizeof(hash_table_t));

if (hashtable == NULL) 
{

return NULL;

}

 hashtable->table= malloc(size* sizeof(struct Node *) )  ;

if (hashtable->table== NULL)
{
  return NULL;
}
for(int i=0; i<size; i++) 
{ 
  hashtable->table[i]=NULL;
  hashtable->size =size;

}
 return hashtable;



typedef struct hash_table_t{
    int size;       /* the size of the table */
  struct  Node **table; /* the table elements */
} hash_table_t;

File *inptr;    

Node* TempNode=NULL;    
Node* new_node=NULL;
Node* Head=NULL;

char buffer[46];

unsigned int hashval;

int j=0;
int count=0;    
int update_counter=0;

inptr= fopen(dictionary, "r"); 

if (inptr == NULL)
{
    printf("Could not open dictionary file");
    printf("\n");
    return 0;
} 

int ch = fgetc(inptr);   
for ( ;; )     
{        
    if ( ch == EOF )    //determines how many words are in the file        
    {           
        break;                
    }        
    if (isalpha(ch) || isdigit(ch) || ispunct(ch))        
    {           
        update_counter = 1;          
    }         
    if (isspace(ch) && update_counter )      
    {           
        count++;           
        update_counter = 0;       
    }     
}
if (update_counter) 
{
    count++;
} 

sizeOfDictionary=count;
rewind(inptr);

hashtable=create_hash_table(sizeOfDictionary);

while(fread(buffer,sizeof(buffer),1,inptr)!=0)
{        
    if(Head==NULL)
    {
        hashval = hash(buffer);
        Head = malloc(sizeof(Node));
        strcpy(&Head->word[j],buffer); 
        Head->Next = hashtable->table[hashval];

        hashtable->table[hashval]=Head;
        Head=Head->Next;

        TempNode =  Head; 
    }
    else if(Head!=NULL)
    {
        new_node = malloc(sizeof(Node));
        hashval = hash(buffer);
        strcpy(&new_node->word[j],buffer);
        new_node->Next = hashtable->table[hashval];
        hashtable->table[hashval]=new_node;
        TempNode=new_node->Next;        
    } 
}
return true;
4

1 回答 1

2

让我试着解释一下步骤中发生的事情：

  • Head = malloc(sizeof(Node));

    strcpy(&Head->word[j],buffer);

    Head
 ----------
|          |
|  buffer  |
|          |
 ----------

  • Head->Next = hashtable->table[hashval];

    Head=Head->Next;

    TempNode = Head;

                         TempNode
                           Head
 ----------          -----------------
|          |  Next  |                 |
|  buffer  | -----> |  table[hashval] |
|          |        |                 |
 ----------          -----------------
     ^
 This is now
 lost forever

  • new_node = malloc(sizeof(Node));

    strcpy(&new_node->word[j],buffer);

    new_node->Next = hashtable->table[hashval];

    TempNode=new_node->Next;

                           Head                   new_node               TempNode
 ----------          -----------------           ----------          ----------------- 
|          |  Next  |                 |         |          |  Next  |                 | 
|  buffer  | -----> |  table[hashval] | No link |  buffer  | -----> |  table[hashval] |
|          |        |                 |  here!  |          |        |                 |
 ----------          -----------------           ----------          -----------------
     ^
 This is now
 lost forever

等等。

我怀疑“这里没有链接！” 上图中的部分导致您的段错误。我也不知道你打算如何使用你的table[hashval]，但不管怎样。该解决方案只是弥补了您的链表中的空白。

解决方案：

用这个替换你的while循环：

TempNode = Head = NULL;

while(fread(buffer,sizeof(buffer),1,inptr)!=0)
{        
    if(Head==NULL)
    {
        hashval = hash(buffer);
        Head = malloc(sizeof(Node));
        strcpy(&Head->word[j],buffer); 
        Head->Next = hashtable->table[hashval];
        Head->Next->Next = NULL;

        TempNode = hashtable->table[hashval] = Head;
    }
    else
    {
        new_node = malloc(sizeof(Node));
        hashval = hash(buffer);
        strcpy(&new_node->word[j],buffer);
        new_node->Next = hashtable->table[hashval];
        hashtable->table[hashval]=new_node;
        new_node->Next->Next = NULL;
        TempNode->Next = new_node;        
        TempNode = new_node;
    } 
    TempNode = TempNode->Next;
}

视觉上的区别是：

  • Head = malloc(sizeof(Node));

    strcpy(&Head->word[j],buffer);

    Head->Next = hashtable->table[hashval];

    Head->Next->Next = NULL;

    TempNode = hashtable->table[hashval] = Head;

  TempNode
    Head                  
 ----------          -----------------
|          |  Next  |                 |  Next
|  buffer  | -----> |  table[hashval] | -----> NULL
|          |        |                 |
 ----------          -----------------
  • TempNode = TempNode->Next
    Head                 TempNode                  
 ----------          -----------------
|          |  Next  |                 |  Next
|  buffer  | -----> |  table[hashval] | -----> NULL
|          |        |                 |
 ----------          -----------------

  • new_node = malloc(sizeof(Node));

    strcpy(&new_node->word[j],buffer);

    new_node->Next = hashtable->table[hashval];

    new_node->Next->Next = NULL;

    Head                 TempNode                 new_node               
 ----------          -----------------           ----------          ----------------- 
|          |  Next  |                 |         |          |  Next  |                 | 
|  buffer  | -----> |  table[hashval] | No link |  buffer  | -----> |  table[hashval] | ----> NULL
|          |        |                 |  here!  |          |        |                 |
 ----------          -----------------           ----------          -----------------
  • TempNode->Next = new_node;
    Head                 TempNode                new_node               
 ----------          -----------------          ----------          ----------------- 
|          |  Next  |                 |  Next  |          |  Next  |                 | 
|  buffer  | -----> |  table[hashval] | -----> |  buffer  | -----> |  table[hashval] | ----> NULL
|          |        |                 |        |          |        |                 |
 ----------          -----------------          ----------          -----------------
  • TempNode = new_node;
                                                 TempNode
    Head                                         new_node               
 ----------          -----------------          ----------          ----------------- 
|          |  Next  |                 |  Next  |          |  Next  |                 | 
|  buffer  | -----> |  table[hashval] | -----> |  buffer  | -----> |  table[hashval] | ----> NULL
|          |        |                 |        |          |        |                 |
 ----------          -----------------          ----------          -----------------

等等。

尖端：

  • 释放你malloc最后编辑的任何内存。
  • 不要移动Head指针（除非您需要删除第一个元素或出于其他原因）。
于 2013-03-07T06:17:08.407 回答