c - 用指针在c中打乱链表

Question

我正在尝试在 C 中打乱链表。我正在考虑通过遍历整个列表来做到这一点，对于每个对象，我将尝试随机化一个索引并在它们之间交换。代码似乎可以正常工作，但运行代码几次后，列表的一部分似乎消失了，有时我会被踢出应用程序。

代码如下:

void main() {
    Song* head = createSong(1, "aaaa", "aaaa");
    Song* song2 = createSong(2, "bbbb", "bbbb");
    Song* song3 = createSong(3, "cccc", "cccc");
    addSongToTheEndOfTheList(head, song2);
    addSongToTheEndOfTheList(head, song3);
    printPlaylist(head);
    shuffleList(head);
    printPlaylist(head);
    //freePlaylist(head);
}
int countList(Song* head) {
    Song* currentSong = head;
    int i = 0;
    if (currentSong)
    {
        while (currentSong->next)
        {
            currentSong = currentSong->next;
            i++;
        }       
        i++;
    }
    return i;
}
void swapSong(Song* head,Song* Source, int id) {
    Song* tempSong = (Song*)malloc(sizeof(Song));
    Song* currentSong = head;
    while(currentSong && currentSong->id != id){
        currentSong = currentSong->next;
    }
    if (currentSong) {
        tempSong->id = currentSong->id;
        tempSong->name = currentSong->name;
        tempSong->artist = currentSong->artist;
        tempSong->next = currentSong->next;
        currentSong->id = Source->id;
        currentSong->name = Source->name;
        currentSong->artist = Source->artist;
        currentSong->next = Source->next;
        Source->id = tempSong->id;
        Source->name = tempSong->name;
        Source->artist = tempSong->artist;
        Source->next = tempSong->next;
        free(tempSong);
    }
    else {
        printf("The list is empty.");
    }

}
void shuffleList(Song* head) {
    Song* currentSong = head;
    int listLength = countList(head);
    int randNum;
    srand(time(NULL));
    if (currentSong) {
        for (int i = 1; currentSong;i++) {
            swapSong(head, currentSong, rand()%listLength+1);
            currentSong = currentSong->next;
        }
    }
    else {
        printf("The list is empty.");
    }
}

完整代码在这里: https://pastebin.com/fSS3rrTv

希望你能帮我弄清楚。谢谢!

Answer 1

错误在swapSong。有两种可能的方式来交换列表中的元素:

• 要么交换数据，要么不触碰next指针
• 或者您不触摸数据添加更改指针

前者对于内部数据很少的单链表更简单(这是您的用例)，后者更适用于双向链表。

这里只要将swapSong改成:

void swapSong(Song* head,Song* Source, int id) {
    Song* tempSong = (Song*)malloc(sizeof(Song));
    Song* currentSong = head;
    while(currentSong && currentSong->id != id){
        currentSong = currentSong->next;
    }
    if (currentSong) {
        tempSong->id = currentSong->id;
        tempSong->name = currentSong->name;
        tempSong->artist = currentSong->artist;
        //tempSong->next = currentSong->next;
        currentSong->id = Source->id;
        currentSong->name = Source->name;
        currentSong->artist = Source->artist;
        //currentSong->next = Source->next;
        Source->id = tempSong->id;
        Source->name = tempSong->name;
        Source->artist = tempSong->artist;
        //Source->next = tempSong->next;
        free(tempSong);
    }
    else {
        printf("The list is empty.");
    }

}

---

顺便说一句，在 Song 结构中，id 被声明为 int *，而它被用作 int。更改为以下内容以删除一些警告:

typedef struct Song {
    int id;
    char* name;
    char* artist;
    struct Song* next;
}Song;

正如@500-InternalServerError 所注意到的，您不需要在 swapSong 中分配任何内容:只需使用本地结构:

void swapSong(Song* head,Song* Source, int id) {
    Song* currentSong = head;
    while(currentSong && currentSong->id != id){
        currentSong = currentSong->next;
    }
    if (currentSong) {
        Song tempSong = *currentSong;
        currentSong->id = Source->id;
        currentSong->name = Source->name;
        currentSong->artist = Source->artist;
        Source->id = tempSong.id;
        Source->name = tempSong.name;
        Source->artist = tempSong.artist;
    }
    else {
        printf("The list is empty.");
    }
}