1

我一直在从 Java 过渡到学习 C 的课程。当前的一个练习是为 LinkedList 实现 removeAtFront()、searchNode() 和 freeList() 方法。我从理论上理解它是如何工作的——我会在 Java 中快速完成它，我已经尝试了几个小时并且不明白为什么下面的代码不起作用。

remove 方法似乎可以工作，生成正确的修改列表，直到在删除节点之后调用 search 方法。然后总是产生段故障 11。free 方法也总是产生段错误。

我不是要求人们做我的功课，但如果我能指出正确的方向，那将不胜感激！

给定的 Node* 结构是：

typedef struct Node
{
  char  *word;
  struct Node  *next;
} Node;

main() 之外的方法如下所示：

void insertAtFront( Node **head, char * key )
{
    Node *new =  malloc( sizeof(Node) );
    if (!new)  fatal("Malloc of new Node failed");
    new->word = key;
    new->next = *head;
    *head = new;
}

void insertAtTail( Node **head, char * word )
{
    if (!(*head)) insertAtFront(head, word);    
    else insertAtTail(&(*head)->next, word);
}

void removeAtFront( Node ** head )
{
    Node *tmp = *head;
    if (!tmp) return;

    *head = tmp->next;
    free(tmp->word);
    free (tmp); 
}

void removeNode( Node ** head, char * key )
{
    Node *tmp = searchNode(*head, key);
    if (tmp) removeAtFront (&tmp);
}

Node * searchNode ( Node * head, char * key )
{   
    if (!head || (strcmp(head->word, key) == 0)) return head;
    return searchNode(head->next, key);
}

void freeList(  Node ** head )
{
    if (!head) return;
if (&(*head)->next) freeList (&(*head)->next);
    removeAtFront(head);
}

编辑：其中一条评论解决了我使用 freeList() 方法的问题，但其他人要求提供更多代码。这个分配的问题是我只能修改 insertAtTail()、removeAtFront()、remove()、search() 和 freeList() 方法。不过，我将在下面发布主要方法。我认为单词值在其中被正确分配。

Node *searchNode( Node * head, char * key );
void insertAtFront( Node **head, char * key );  // ALREADY WRITTEN FOR YOU 
void insertAtTail( Node **head, char * key );
void removeAtFront( Node ** head );
void removeNode( Node **head, char * key );
void freeList( Node **head );
void printList( Node * head ); // ALREADY WRITTEN FOR YOU
void fatal( char * msg ); // ALREADY WRITTEN FOR YOU

#define BUFFER_CAP 20

int main() 
{
  Node *head = NULL;

  while (1)
  {
    char option;
    printf("\nChoose 'H'ead Insert, 'T'ail insert, 'R'emove, 'S'earch, F'ree,     'Q'uit " );
    fflush( stdout );
    int result = scanf(" %c%*[^\n]", &option); getchar();  // MAGIC BULLET TO CORRECTLY READ A SINGLE CHAR FROM STDIN
    if (result <1) fatal("failure reading from stdin\n");

    if (option == 'H' )
    {
        char * word=malloc(BUFFER_CAP);  // DONT ENTER ANY LONG WORDS!
        printf("Enter a word to insertAtFront: " );
        fflush( stdout );
        char * result = fgets( word, BUFFER_CAP, stdin );
        if (result==NULL) fatal("failure reading from stdin\n");
        strtok(word,"\n"); // overwrites '\n' with  '\0'
        insertAtFront( &head, word ); /* shallow copy string into list   */
        printList( head );
    }
    if (option == 'T' )
    {
        char * word=malloc(BUFFER_CAP);  // DONT ENTER ANY LONG WORDS!
        printf("Enter a word to insertAtTail: " );
        fflush( stdout );
        char * result = fgets( word, BUFFER_CAP, stdin );
        if (result==NULL) fatal("failure reading from stdin\n");
        strtok(word,"\n"); // overwrites '\n' with  '\0'
        insertAtTail( &head, word ); /* shallow copy string into list   */
        printList( head );
    }
        if (option == 'R' )
    {
        char * word=malloc(BUFFER_CAP);  // DONT ENTER ANY LONG WORDS!
        printf("Enter a word to remove: " );
        fflush( stdout );
        char * result = fgets( word, BUFFER_CAP, stdin );
        if (result==NULL) fatal("failure reading from stdin\n");
        strtok(word,"\n"); // overwrites '\n' with  '\0'
        removeNode( &head, word );
        printList( head );
        free( word ); // we were just using it for matching
    }
    if (option == 'S' )
    {
        char * word=malloc(BUFFER_CAP);  // DONT ENTER ANY LONG WORDS!
        printf("Enter a word to find: " );
        fflush( stdout );
        char * result = fgets( word, BUFFER_CAP, stdin );
        if (result==NULL) fatal("failure reading from stdin\n");
        strtok(word,"\n"); // overwrites '\n' with  '\0'
        if (searchNode( head, word ))
            fprintf(stderr, "%s FOUND\n",word );
        else
            fprintf(stderr, "%s NOT FOUND\n",word );
        printList( head );
        free( word ); // we were just using it for matching
    }
    if (option == 'F' ) // free the entire list (remember to set head to NULL)
    {
        freeList( &head );
        printList( head );
    }
    else if (option == 'Q' )
        exit( 0 );
} // END WHILE

return 0;
}
4

2 回答 2

2

当您使用 为节点分配内存时Node *new = malloc( sizeof(Node) );，您正在为指针分配内存，而不是为数据分配内存。您确实为 char 分配内存也喜欢：（这只是一个想法） 

new->word= malloc(sizeof(char)*(strlen(key) + 1));
strcpy(new->word, key)

否则，您必须使用key 动态分配内存。（因为你这样做free(tmp->word);）

我认为您应该添加更多代码。你怎么通过key？

于 2013-02-08T17:55:17.470 回答
0

是的，如前面的答案所示，尽管您已经为节点分配了内存，但您并没有在每个节点中为 word 分配内存。有时它可能会起作用，而不会导致段错误，当时您正在使用您尚未声明的“某人”内存，从而导致损坏该内存位置。

于 2013-02-08T18:24:48.720 回答