Перемешать связанный список в c с указателями - PullRequest
Новая
       17

Перемешать связанный список в c с указателями

0 голосов
/ 29 мая 2019

Я пытаюсь перетасовать связанный список в 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

Надеюсь, вы поможете мне разобраться.Спасибо!

1 Ответ

3 голосов
/ 29 мая 2019

Ошибка лежит в 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 struct, 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.");
    }
}
...