0

我有一个结构，

    typedef struct song{
    string title;
    string artist;
    string album;
    string genre;
    float rating;
    struct song *next;
    }song_t;

和删除功能，

    song_t *DeleteSong(song_t *head, string key){
    song_t *temp, *temp2, *holder;
    holder = (song_t *)malloc(sizeof(song_t));  
    temp = head;


    while(temp != NULL && strcasecmp(temp->title, key) != 0){
        temp = temp->next;
    }
    if(temp == NULL){
        newline;
        printf("Song not found.");
        newline;
        newline;
    }

    else if(temp == head){
        if(temp->next == NULL){
            temp->next = NULL;
            free(temp);
            return NULL;
        }
        else{
        head = temp->next;
        }
    }

    else if(temp->next == NULL){
        temp2 = head;

        while(temp2->next->next != NULL){
            temp2 = temp2->next;
        }
        holder = temp2->next->next;
        temp2->next = NULL;
    }

    else{
        temp2 = head;
        while(temp2->next != temp){
            temp2 = temp2->next;
        }
        holder = temp;
        temp2->next = temp->next;
        free(holder);
    }
    return head;
    }

最后，一个删除重复的功能，

song_t *RemoveDuplicate(song_t *head){
    song_t *temp;
    song_t *temp2;
    temp = head;
    temp2 = temp->next;

    while(temp != NULL){
        while(temp2 != NULL){
            if(strcasecmp(temp->title,temp2->title) == 0 && strcasecmp(temp->artist,temp2->artist) == 0 && strcasecmp(temp->album,temp2->album) == 0 && strcasecmp(temp->genre,temp2->genre) == 0){
                if(temp2 == temp->next){
                    temp = DeleteSong(temp,temp2->title);
                }
                else{
                    temp2 = DeleteSong(temp2->next,temp2->title);
                }
            }
            temp2 = temp2->next;
        }
        temp = temp->next;
    }

    }

但是，每当我在 main 中包含删除重复函数时，head = RemoveDuplicate(head);

结果总是只返回一个结构并删除整个列表。我认为 RemoveDuplicate 函数有问题，因为我测试了 DeleteSong 函数并且它运行良好。

4

2 回答 2

0

如果列表中的前两个条目是重复的，那么您第一次检查时似乎是：

if(temp2 == temp->next){
    temp = DeleteSong(temp,temp2->title);
}

它将在列表的开头评估为 true。如果您的列表突然减少到列表的头部，您可能想检查从那里会发生什么。

我怀疑这个错误实际上可能是在 DeleteSong 函数中发现的，因为它看起来比我从我见过的其他单链表中回忆的要复杂一些。

在伪 C 中，我可能会尝试这样的事情：

to_delete = find_node_by_key( key )
return if to_delete == null

current = head
last    = null

if to_delete == current
{
    head = current->next
    to_mem_free = current
}
else do
{
    if to_delete == current
    {
        to_mem_free = current
        if ( last != null ) last->next = current->next
        break
    }

    last = current

} while (current = current->next) != null

您可以将搜索要删除的节点与实际删除相结合，这样您就不必遍历列表两次。除非绝对必要，否则您可能还想尽量避免使用“temp”作为变量名，因为它经常引起混淆。

许多工具链都包含一个提供单链表的库。通过使用这样的库，您可以节省数小时的编码和调试时间，它可能还提供排序树或哈希列表，从而显着加快搜索速度，例如歌曲标题。

于 2012-10-06T12:17:11.913 回答
0 
holder = (song_t *)malloc(sizeof(song_t));
/* snip */
/* else if */
    holder = temp2->next->next;
/* else */
    holder = temp;
    temp2->next = temp->next;
    free(holder);

当您分配时holder = temp2->next->next;（顺便说一句，它总是NULL在那里），或者holder = temp;，您将失去对malloced 内存的引用。由于您根本没有真正使用holder，因此解决方法是将其从函数中删除。在第一种情况下，除了分配一个 complex 之外，您没有以任何方式使用它NULL，在第二种情况下，删除holder = temp;和freeingtemp是正确的方法。

还有一些奇怪的事情和错误：

song_t *DeleteSong(song_t *head, string key){
    song_t *temp, *temp2, *holder;
    holder = (song_t *)malloc(sizeof(song_t));  // as said, remove holder completely
    temp = head;

    /* Find song with given title */
    while(temp != NULL && strcasecmp(temp->title, key) != 0){
        temp = temp->next;
    }
    if(temp == NULL){
        newline;
        printf("Song not found.");
        newline;
        newline;
    }
    /* It's the very first in the list */
    else if(temp == head){
        if(temp->next == NULL){
            /* It's even the only one */
            temp->next = NULL;    // This runs only if temp->next is already NULL
            free(temp);           // Also free the members of temp, or you're leaking
            return NULL;
        }
        else{
            head = temp->next;    // You should now free temp and members, or you're leaking memory
        }
    }
    /* It's the last one in the list, but not the first */
    else if(temp->next == NULL){
        temp2 = head;
        /* Find the penultimate song */
        while(temp2->next->next != NULL){
            temp2 = temp2->next;
        }
        holder = temp2->next->next;
        temp2->next = NULL;    // You should now free temp and members, or you're leaking memory
    }
    /* Neither first nor last */
    else{
        temp2 = head;
        /* Find song before */
        while(temp2->next != temp){
            temp2 = temp2->next;
        }
        holder = temp;
        temp2->next = temp->next;
        free(holder);
    }
    return head;
}

但除了泄漏之外，它是正确的，尽管不必要地复杂。

song_t *DeleteSong(song_t *head, string key) {
    song_t *prev = NULL, curr = head;
    /* Find song and node before that */
    while(curr != NULL && strcasecmp(curr->title, key) != 0) {
        prev = curr;
        curr = curr->next;
    }
    if (curr == NULL) {
        /* Not found */
        newline;
        printf("Song not found.");
        newline;
        newline;
    } else if (prev == NULL) {
        /* It's the very first song in the list
         * so let head point to its successor
         * and free the song; it doesn't matter
         * if it's the last in the list
         */
        head = curr->next;
        free(curr->title);   // Probably, but not if title isn't malloced
        free(curr->artist);  // Ditto
        free(curr->album);
        free(curr->genre);
        free(curr);
    } else {
        /* We have a predecessor, let that point
         * to the successor and free the song
         */
        prev->next = curr->next;
        free(curr->title); // See above
        free(curr->artist);
        free(curr->album);
        free(curr->genre);
        free(curr);
    }
    return head;
}

RemoveDuplicate另一方面，您的功能并没有达到您的预期。除了副本立即跟随原件的情况和不复制的情况之间的区别（我看不出任何原因）之外，分配temp = DeleteSong(temp,temp2->title);分别。temp2 = DeleteSong(temp2->next,temp2->title);改变什么temp。temp2指向，但不是列表中相应的前任指向的位置。让我们用一点 ASCII 艺术来说明这个问题：

       temp    temp2
         |      |
         v      v
song1->song2->song3->song4->song5->...

在哪里song2和song3是重复的。现在在 中temp = DeleteSong(temp,temp2->title);，由于两首歌是重复的，已经匹配的head参数，并且在你的版本中，已经完成了，所以列表根本没有改变，你只是得到DeleteSongDeleteSonghead = temp->next; return head;

            temp temp2
              |   |
              v   v
song1->song2->song3->song4->...

两个指针都指向同一个列表节点。在我的版本中，DeleteSong它释放了节点，song1.next现在将指向freed 内存，哎呀。

如果副本没有立即跟随原始，temp2 = DeleteSong(temp2->next,temp2->title);则可能找不到具有匹配标题的歌曲，因为搜索在已知匹配之后开始，在这种情况下，列表根本没有修改，temp2只是更改为指向后继。如果之后有匹配标题的歌曲，找到的副本仍然没有从列表中删除，并且之后的部分可能会改变，可能导致不健全的状态。如果temp2指向列表中倒数第二个节点，并且最后一个节点具有匹配的标题，则最后一个节点是freed，但是next副本的指针没有改变，所以现在它指向freed 内存，你有一个悬空指针（这是一个等待发生的段错误）。

另一个问题是DeleteSong和的删除标准RemoveDuplicate不同，前者只检查标题，后者还检查艺术家、专辑和流派，因此在后者中使用前一个功能可能会删除不应删除的歌曲（考虑封面版本）。

当你想从一个单链表中删除一个节点时，你需要一个指向前一个节点的指针才能改变它所指向的内容，否则你将创建悬空指针。我在上面给出了一个标准的方法，你基本上可以将它复制到内部循环中，但是在这里我们永远不会想要删除第一个节点，所以它有点简单：

// void, since head is never changed, only duplicates after the original are removed
void RemoveDuplicates(song_t *head) {
    song_t *orig = head, prev, curr;
    while(orig != NULL && orig->next != NULL) {
        prev = orig;
        curr = orig->next;
        while(curr != NULL) {
            // Find next song to remove
            while(curr != NULL && !meets_deletion_criteria(orig, curr)) {
                prev = curr;
                curr = curr->next;
            }
            // Now either curr is NULL, or it shall be deleted
            if (curr != NULL) {
                // Let the predecessor point to curr's successor
                prev->next = curr->next;
                clean_up(curr); // free all malloced members and the node itself
                curr = prev->next;
            }
        }
        orig = orig->next;
    }
}
于 2012-10-06T14:04:08.110 回答