小贝子编程

C语言 在设置头指向链表中的新节点时遇到麻烦



所以我试图插入一些东西作为链表的新头部(我为它创建了一个函数和所有这些)-但由于某种原因，当我运行代码时，我得到一个分段错误-我已经缩小了节点的原因，但我不确定为什么它会引起问题?

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: %sn", (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: %sn",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 countern",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)nn");
    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] != '' || 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.nn");
            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");
    }
}

文本文件(从终端执行时作为参数读入)

bat
bat
bat
ant

我认为问题在于*head = new_node行，但我不能确切地弄清楚为什么这会引起问题?

从根本上说，问题是与SortedInsert()的接口。你有:

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

这将阻止SortedInsert()报告一个新的磁头。不能改变主叫码中的head。有两种可能的设计(都有效):

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

显然，它们的用法不同:

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

您的代码还有许多其他问题。其中我记得修复:

  • 在你尝试使用最后一个条目两次之前，你不会可靠地检测EOF。
  • 你有一个奇怪的组织与str_buffer全局变量和temp_buffer变量。
  • 在ReadLine()函数中，您读取的是单词，而不是行。
  • 当你可能指的是word_node(或struct word_node)时，你在各种函数原型中使用struct node。(练习:你知道为什么编译器没有报错吗?)
  • 你声明的函数没有实现(所以你的代码不是一个MCVE(最小的，完整的，可验证的例子)。
    • 您的测试代码没有在每次添加元素时打印列表。这是一个常见的错误。你需要一个打印功能;您需要在空列表、单元素列表和双元素列表等上执行该函数。这样你可以更快地发现问题。(代码的早期版本很高兴地添加了bat，但未能添加cat，但成功添加了ant，但没有添加任何其他内容。在每个条目添加后打印列表时很容易发现。)
  • 您在多个地方创建了单词节点，而不是始终使用单个函数。
  • (未修复)您没有明确定义的包的外部接口。所有类型的内部管理函数(PushNewHead(), CreateNode())在应该是静态的情况下都公开为全局函数。而且你没有将main()和测试代码与"生产"代码分开。
  • 当增加一个现有单词的计数而不是添加一个单词时，由于没有释放str_buffer而导致内存泄漏。

下面的一些代码解决了上面的大部分问题，可能还修复了一些其他问题。它存储在单个文件(ll19.c)中，但是头文件可以很容易地分开。此版本使用'V2'接口。

#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: %sn", (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: %sn", word);
        while (current != NULL)
        {
            char *currentNodeWord = current->word;
            if (strcmp(word, currentNodeWord) == 0)
            {
                printf("%s is already in the list, updating the frequency countern", 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 filen", 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;
}

示例文件data.1:

bat
bat
bat
ant

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)

示例文件data.2:

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

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

代码现在是完美的吗?不，远非如此。但是它已经在valgrind下运行，并且有一个干净的健康清单-没有内存泄漏的代码与所示的两个测试文件。(我不打算声称没有其他测试文件可以发现泄漏，但我是适度乐观的。)

相关内容

  • 没有找到相关文章

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium