c - 需要单链表的帮助

Question

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

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;

Answer 1

让我尝试逐步解释发生的事情:

• 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->下一步;

---

                           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
|          |        |                 |        |          |        |                 |
 ----------          -----------------          ----------          -----------------

---

等等。

提示:

• 释放你在最后 malloced 的任何内存。
• 不要移动您的 Head 指针(除非您需要删除第一个元素或出于其他原因)。