当前位置: 动力学知识库 > 问答 > 编程问答 >

c - Having trouble setting the header to point to a new node in a linked list

问题描述:

So I'm attempting to insert something as the new head of a linked list (I created a function for it and all that) - but for some reason when I run the code I get a segmentation error - I've narrowed down where the cause of the node is, but I'm not sure why it's causing a problem?

most_freq.h

#ifndef MOST_FREQ_H_

#define MOST_FREQ_H_

#include <stdio.h>

//used to hold each "word" in the list

typedef struct word_node

{

char *word;

unsigned int freq; //frequency of word

struct word_node *next;

} word_node;

struct node *readStringList(FILE *infile);

int ReadLine(FILE *infile, char * line_buffer);

struct node *GetMostFrequent(struct word_node *head, unsigned int num_to_select);

void PrintStringList(struct word_node *head);

void FreeStringList(struct word_node *head);

void SortedInsert(char * word, word_node *head);

void PushNewHead(node_t ** head, char * word);

struct word_node* CreateNode(char * string);

char *strip_copy(const char *s); //removes any new line characters from strings

#endif

most_freq.c

#include "most_freq.h"

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

char* str_buffer = NULL;

struct word_node* CreateNode(char * string) {

word_node* new_node = malloc(sizeof(word_node));

new_node->word = string;

new_node->freq = 1;

new_node->next = NULL;

return new_node;

}

void PushNewHead(word_node ** head, char * word) {

word_node * new_node;

new_node = malloc(sizeof(word_node));

new_node->word = word;

new_node->next = *head;

printf("*Head word is: %s\n", (new_node->next)->word);

*head = new_node;

return;

}

void SortedInsert(char * word, word_node *head) {

//first check if head node is empty

if(head->word == NULL) { //if head->word is null, then list is empty

//setup head node

head->word = word;

head->freq = 1;

head->next = NULL;

return;

}

else { //otherwise, list isn't empty and we need to traverse it

word_node * current = head; //set current to head parameter

word_node * prev = NULL; //set previous to NULL (to track previous node)

printf("Attempting to insert: %s\n",word);

while(current != NULL) { //while current isn't null

char* currentNodeWord = current->word;

if(strcmp(word,currentNodeWord) == 0) { //word matches current node's word

printf("%s is already in the list, updating the frequency counter\n",word);

current->freq++; //increase node's frequency

break;

}

else if(strcmp(word,currentNodeWord) > 0) { //word comes after current node's word alphabetically

prev = current;

current = current->next; //move current node pointer

}

else if(strcmp(word,currentNodeWord) < 0) { //word comes before current node's word alphabetically

//prepare node for insertion

if(current = head) { //if current = head, then we're at the first item in the list

printf("%s is the new head node.\n",word);

PushNewHead(&head,word);

}

struct word_node * new_node = malloc(sizeof(word_node));

new_node = CreateNode(word);

prev->next = new_node;

new_node->next = current;

}

}

//if current node is null, we're at the end of the list, so insert the new node

}

}

void PrintStringList(struct word_node *head) {

word_node * current = head;

printf("List of Strings (and Frequencies)\n\n");

while(current != NULL) {

printf("%s (Frequency: %d)\n", current->word, current->freq);

current = current->next;

}

}

int ReadLine(FILE *infile, char * line_buffer) {

fscanf(infile, "%s", line_buffer);

str_buffer = strdup(line_buffer);

if(str_buffer[0] != '\0' || strcmp(str_buffer, "") != 0) {

return EXIT_SUCCESS; //return success code

}

else {

return EXIT_FAILURE; //return failure code

}

}

struct node *readStringList(FILE *infile) {

//setup empty linked list

word_node * root = NULL;

root = malloc(sizeof(word_node));

if(root == NULL) { //check if root was successfully allocated

printf("Not enough memory to create linked list.\n");

exit(EXIT_FAILURE);

}

char* temp_buffer = malloc (sizeof(char) * 255); //buffer for 255 chars

while(!feof(infile) && ReadLine(infile, temp_buffer) == EXIT_SUCCESS) { //while there is still something to be read from the file

SortedInsert(str_buffer, root); //pass in root node to str_buffer

}

printf("Preparing to print list.\n");

PrintStringList(root);

}

int main(int argc, char *argv[])

{

if (argc == 2) // no arguments were passed

{

FILE *file = fopen(argv[1], "r"); /* "r" = open for reading, the first command is stored in argv[1] */

if ( file == 0 )

{

printf( "Could not open file.\n" );

}

else

{

printf("Starting program.\n\n");

readStringList(file);

}

}

else if (argc < 3) {

printf("You didn't pass the proper arguments! The necessary arguments are: <number of most frequent words to print> <file to read>\n");

}

}

text file (read in as an argument when executing from terminal)

bat

bat

bat

ant

I think the issue lies in the line *head = new_node but I can't figure out exactly why that would be causing a problem?

网友答案:

Fundamentally, the problem is the interface to SortedInsert(). You have:

void SortedInsert(char *word, word_node *head);

This prevents SortedInsert() from reporting on a new head. It cannot change the head in the calling code. There are two possible designs (both of which work):

word_node *SortedInsert(char *word, word_node *head);  // V1
void SortedInsert(char *word, word_node **head);       // V2

Clearly, they're used differently:

head = SortInserted(new_word, head);  // V1
SortInserted(new_word, &head);        // V2

Your code also has numerous other issues. Among the ones I remember fixing:

  • You don't detect EOF reliably until after you've tried using the last entry twice.
  • You have a weird organization with the str_buffer global variable and the temp_buffer variable.
  • You read words, not lines, in the function ReadLine().
  • You use struct node in various function prototypes when you probably mean word_node (or struct word_node). (Exercise: do you know why the compiler didn't complain?)
  • You declared functions that are not implemented (so your code isn't an MCVE (Minimal, Complete, Verfiable Example).
  • Your testing code didn't print the list each time an element is added. This is something that is a common mistake. You need a printing function; you need to exercise that function on empty lists, and one element lists, and two element lists, etc. You can spot trouble much more quickly that way. (An early version of the code added bat happily, but failed to add cat, but was successful adding ant, but not anything else. It was easy to spot when the list was printed after each entry was added.)
  • You had multiple places where you created word nodes, rather than consistently using a single function.
  • (Unfixed) You don't have a clearly defined external interface to the package. All sorts of internal administrative functions (PushNewHead(), CreateNode()) are exposed as global functions when they should be static. And you don't separate the main() and test code from the 'production' code.
  • Memory leaked due to not freeing str_buffer when incrementing the count for an existing word instead of adding a word.

Here is some code that resolves most of the issues above, and probably fixes a number of other issues. It stored in a single file (ll19.c), but the header could be separated easily. This version uses the 'V2' interface.

#ifndef MOST_FREQ_H_
#define MOST_FREQ_H_

#include <stdio.h>

typedef struct word_node
{
    char *word;
    unsigned int freq;
    struct word_node *next;
} word_node;

word_node *readStringList(FILE *infile);
char *ReadWord(FILE *infile);
void PrintStringList(struct word_node *head);
void FreeStringList(struct word_node *head);
void SortedInsert(char *word, word_node **head);
void PushNewHead(word_node **head, char *word);
word_node *CreateNode(char *string);

#endif

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

struct word_node *CreateNode(char *string)
{
    word_node *new_node = malloc(sizeof(word_node));
    new_node->word = string;
    new_node->freq = 1;
    new_node->next = NULL;

    return new_node;
}

void PushNewHead(word_node **head, char *word)
{
    word_node *new_node = CreateNode(word);
    new_node->next = *head;
    printf("*Head word is: %s\n", (new_node->next)->word);
    *head = new_node;
}

void SortedInsert(char *word, word_node **head)
{
    assert(head != 0);
    if (*head == NULL)
    {
        printf("New head word: [%s]\n", word);
        *head = CreateNode(word);
    }
    else
    {
        word_node *current = *head;
        word_node *prev = NULL;
        printf("Attempting to insert: %s\n", word);
        while (current != NULL)
        {
            char *currentNodeWord = current->word;
            if (strcmp(word, currentNodeWord) == 0)
            {
                printf("%s is already in the list, updating the frequency counter\n", word);
                current->freq++;
                free(word);
                return;
            }
            else if (strcmp(word, currentNodeWord) > 0)
            {
                printf("[%s] comes after [%s]\n", word, currentNodeWord);
                prev = current;
                current = current->next;
            }
            else 
            {
                assert(strcmp(word, currentNodeWord) < 0);
                if (current == *head)
                {
                    printf("[%s] is the new head node.\n", word);
                    PushNewHead(head, word);
                    return;
                }
                break;
            }
        }
        printf("Regular word: [%s] after [%s]\n", word, prev->word);
        struct word_node *new_node = CreateNode(word);
        prev->next = new_node;
        new_node->next = current;
    }
}

void PrintStringList(struct word_node *head)
{
    word_node *current = head;
    printf("List of Strings (and Frequencies):\n");
    while (current != NULL)
    {
        printf("%s (Frequency: %d)\n", current->word, current->freq);
        current = current->next;
    }
    putchar('\n');
}

char *ReadWord(FILE *infile)
{
    char line_buffer[255];
    if (fscanf(infile, "%254s", line_buffer) == 1)
    {
        char *str_buffer = strdup(line_buffer);
        if (str_buffer != 0 && strcmp(str_buffer, "") != 0)
            return str_buffer;
        free(str_buffer);
    }
    return 0;
}

struct word_node *readStringList(FILE *infile)
{
    word_node *root = NULL;
    char *str_buffer;

    while ((str_buffer = ReadWord(infile)) != NULL)
    {
        printf("Line: [%s]\n", str_buffer);
        SortedInsert(str_buffer, &root);
        PrintStringList(root);
    }
    return root;
}

void FreeStringList(word_node *node)
{
    while (node != NULL)
    {
        free(node->word);
        word_node *next = node->next;
        free(node);
        node = next;
    }
}

int main(int argc, char *argv[])
{
    if (argc != 2)
    {
        fprintf(stderr, "Usage: %s file\n", argv[0]);
        return EXIT_FAILURE;
    }
    FILE *file = fopen(argv[1], "r");
    if (file == 0)
    {
        fprintf(stderr, "%s: could not open file %s for reading.\n", argv[0], argv[1]);
        return EXIT_FAILURE;
    }
    printf("Starting program - reading %s.\n", argv[1]);
    word_node *root = readStringList(file);
    printf("Read complete.\n");
    PrintStringList(root);
    FreeStringList(root);
    fclose(file);
    return EXIT_SUCCESS;
}

Example file data.1:

bat
bat
bat
ant

Output from running on data.1:

Starting program - reading data.
Line: [bat]
New head word: [bat]
List of Strings (and Frequencies):
bat (Frequency: 1)

Line: [bat]
Attempting to insert: bat
bat is already in the list, updating the frequency counter
List of Strings (and Frequencies):
bat (Frequency: 2)

Line: [bat]
Attempting to insert: bat
bat is already in the list, updating the frequency counter
List of Strings (and Frequencies):
bat (Frequency: 3)

Line: [ant]
Attempting to insert: ant
[ant] is the new head node.
*Head word is: bat
List of Strings (and Frequencies):
ant (Frequency: 1)
bat (Frequency: 3)

Read complete.
List of Strings (and Frequencies):
ant (Frequency: 1)
bat (Frequency: 3)

Example file data.2:

bat
bat
cat
bat
auk
dog
ant
bee
ant
cow
bat
pig
hen

Output from running on data.2:

Starting program - reading data.2.
Line: [bat]
New head word: [bat]
List of Strings (and Frequencies):
bat (Frequency: 1)

Line: [bat]
Attempting to insert: bat
bat is already in the list, updating the frequency counter
List of Strings (and Frequencies):
bat (Frequency: 2)

Line: [cat]
Attempting to insert: cat
[cat] comes after [bat]
Regular word: [cat] after [bat]
List of Strings (and Frequencies):
bat (Frequency: 2)
cat (Frequency: 1)

Line: [bat]
Attempting to insert: bat
bat is already in the list, updating the frequency counter
List of Strings (and Frequencies):
bat (Frequency: 3)
cat (Frequency: 1)

Line: [auk]
Attempting to insert: auk
[auk] is the new head node.
*Head word is: bat
List of Strings (and Frequencies):
auk (Frequency: 1)
bat (Frequency: 3)
cat (Frequency: 1)

Line: [dog]
Attempting to insert: dog
[dog] comes after [auk]
[dog] comes after [bat]
[dog] comes after [cat]
Regular word: [dog] after [cat]
List of Strings (and Frequencies):
auk (Frequency: 1)
bat (Frequency: 3)
cat (Frequency: 1)
dog (Frequency: 1)

Line: [ant]
Attempting to insert: ant
[ant] is the new head node.
*Head word is: auk
List of Strings (and Frequencies):
ant (Frequency: 1)
auk (Frequency: 1)
bat (Frequency: 3)
cat (Frequency: 1)
dog (Frequency: 1)

Line: [bee]
Attempting to insert: bee
[bee] comes after [ant]
[bee] comes after [auk]
[bee] comes after [bat]
Regular word: [bee] after [bat]
List of Strings (and Frequencies):
ant (Frequency: 1)
auk (Frequency: 1)
bat (Frequency: 3)
bee (Frequency: 1)
cat (Frequency: 1)
dog (Frequency: 1)

Line: [ant]
Attempting to insert: ant
ant is already in the list, updating the frequency counter
List of Strings (and Frequencies):
ant (Frequency: 2)
auk (Frequency: 1)
bat (Frequency: 3)
bee (Frequency: 1)
cat (Frequency: 1)
dog (Frequency: 1)

Line: [cow]
Attempting to insert: cow
[cow] comes after [ant]
[cow] comes after [auk]
[cow] comes after [bat]
[cow] comes after [bee]
[cow] comes after [cat]
Regular word: [cow] after [cat]
List of Strings (and Frequencies):
ant (Frequency: 2)
auk (Frequency: 1)
bat (Frequency: 3)
bee (Frequency: 1)
cat (Frequency: 1)
cow (Frequency: 1)
dog (Frequency: 1)

Line: [bat]
Attempting to insert: bat
[bat] comes after [ant]
[bat] comes after [auk]
bat is already in the list, updating the frequency counter
List of Strings (and Frequencies):
ant (Frequency: 2)
auk (Frequency: 1)
bat (Frequency: 4)
bee (Frequency: 1)
cat (Frequency: 1)
cow (Frequency: 1)
dog (Frequency: 1)

Line: [pig]
Attempting to insert: pig
[pig] comes after [ant]
[pig] comes after [auk]
[pig] comes after [bat]
[pig] comes after [bee]
[pig] comes after [cat]
[pig] comes after [cow]
[pig] comes after [dog]
Regular word: [pig] after [dog]
List of Strings (and Frequencies):
ant (Frequency: 2)
auk (Frequency: 1)
bat (Frequency: 4)
bee (Frequency: 1)
cat (Frequency: 1)
cow (Frequency: 1)
dog (Frequency: 1)
pig (Frequency: 1)

Line: [hen]
Attempting to insert: hen
[hen] comes after [ant]
[hen] comes after [auk]
[hen] comes after [bat]
[hen] comes after [bee]
[hen] comes after [cat]
[hen] comes after [cow]
[hen] comes after [dog]
Regular word: [hen] after [dog]
List of Strings (and Frequencies):
ant (Frequency: 2)
auk (Frequency: 1)
bat (Frequency: 4)
bee (Frequency: 1)
cat (Frequency: 1)
cow (Frequency: 1)
dog (Frequency: 1)
hen (Frequency: 1)
pig (Frequency: 1)

Read complete.
List of Strings (and Frequencies):
ant (Frequency: 2)
auk (Frequency: 1)
bat (Frequency: 4)
bee (Frequency: 1)
cat (Frequency: 1)
cow (Frequency: 1)
dog (Frequency: 1)
hen (Frequency: 1)
pig (Frequency: 1)

Is the code perfect now? No, far from it. But it has been run under valgrind and has a clean bill of health — no memory leaks from this code with the two test files shown. (I'm not going to claim that no other test file could find a leak, but I'm modestly optimistic.)

分享给朋友:
您可能感兴趣的文章:
随机阅读: