Попытка найти два случайных узла и поменять их местами в двусвязном списке - PullRequest
Новая
       43

Попытка найти два случайных узла и поменять их местами в двусвязном списке

0 голосов
/ 12 декабря 2018

Эта программа в основном просто перемешивает колоду карт.Карты хранятся в двусвязном списке, то есть 52 узла.Я получаю ошибку доступа для чтения в функции getNode, но я почти уверен, что мой цикл правильный, поэтому я думаю, что ошибка происходит из-за чего-то еще.Может быть, функция подкачки.Мой первый шаг - получение указателей на узлы, которые я пытаюсь поменять местами.

Итак, я сделал функцию, и я почти уверен, что это правильно, за исключением того, что мне интересно, должен ли я возвращать * traverseP вместо просто traverseP.Я так не думаю, потому что я хочу вернуть указатель на узел, а не значение внутри узла. 

template<class T>
typename ReorderableList<T>::Node *ReorderableList<T>::getNode(int i) const
{
    int count = 0;
    for (Node *traverseP = firstP; traverseP != NULL; traverseP = traverseP->nextP) {
        if (count == i)
            return traverseP;
        count++;
    }
    return NULL;
}

Затем я сделал функцию подкачки, которая принимает два целых числа, они представляют значения, которые яперехожу к функции getNode 

    template<class T>
    void ReorderableList<T>::swap(int i, int j)
    {
        // Get pointers to ith and jth nodes.
        Node *iPtr = getNode(i);
        Node *jPtr = getNode(j);

        //create temp Node and store the pointers
        Node *temp = new Node;
        temp = iPtr->prevP;
        temp = iPtr->nextP;

        //adjust the iPtr next/prev pointers
        iPtr->prevP = jPtr->prevP;
        iPtr->nextP = jPtr->nextP;

        //adjust the jPtr next/prev pointers
        jPtr->prevP = temp->prevP;
        jPtr->nextP = temp->prevP;

        //I'm a little unclear on these lines. I think they're checking if
        //iPtr and jPtr have null pointers. I've tried making them equal jPtr and 
        //iPtr and that strangly didn't make any difference.
        if (iPtr->prevP)
            iPtr->prevP->nextP = jPtr;
        if (iPtr->nextP)
            iPtr->nextP->prevP = jPtr;

        if (jPtr->prevP)
            jPtr->prevP->nextP = iPtr;
        if (jPtr->nextP)
            jPtr->nextP->prevP = iPtr;

        delete temp;
    }

Это функция перемешивания, с которой начинается весь этот шабанг 

template<class T>
void randomShuffle(ReorderableList<T> &list, int n)
{
    int randNum = 0;    
    for (int i = n-1; i > 0; i--)
    {
        randNum = (rand() & (i + 1));
        if (randNum > i)
            std::swap(randNum, i);

        list.swap(randNum, i);
    }
}

Я проверил несколько различных ресурсов для функции подкачки и нашелдва, которые оба утверждали, что они были правы, но для меня они выглядели иначе. Ресурс 1 Ресурс 2

...