Добавление узла в случайное место в связанном списке - PullRequest
Новая
       48

Добавление узла в случайное место в связанном списке

0 голосов
/ 23 сентября 2018

Итак, у меня есть функция, которая добавляет узел в связанный список, но вместо того, чтобы просто добавить элемент в конец связанного списка, я пытаюсь получить пользовательский ввод для того места, в которое пользователь хочет добавить его. Затем янужно добавить его и переместить все остальное, не удаляя ничего другого.У меня много проблем с этим.

Ниже я покажу свой код, он немного запутанный, но я объясню, как смогу. 

void InsertGraphicElement(struct RasterGraphic *pA) {
    int counter = 1;
    int response = 0;
    char tempString[256];
    struct GraphicElement *newNode = malloc(sizeof(*newNode));
    if (newNode == NULL)
        return;

    newNode->fileName = malloc(256 * sizeof(char));
    if (newNode->fileName == NULL)
        return;
    newNode->pNext = NULL;

    printf("Insert a GraphicElement in the RasterGraphic\nPlease enter the GraphicElement filename: ");
    scanf("%s", newNode->fileName);

    if (pA->GraphicElements == NULL) {
        pA->GraphicElements = newNode;
        printf("This is the first GraphicElement in the list\n");
    } else {
        struct GraphicElement *tempHead = pA->GraphicElements;
        struct GraphicElement *tempTail = pA->GraphicElements;
        while (tempHead->pNext != NULL) {
            tempHead = tempHead->pNext;
            counter++;
        }
        tempHead->pNext = newNode;

        printf("There are %d GraphicElement(s) in the list. Please specify the position (<= %d) to insert at :", counter, counter);
        scanf("%d", &response);

        if (response == counter) {
            return;
        } else {
            while (response < counter) {
                tempTail = tempTail->pNext;
                response++;
            }       
        }
    }
    return;
}

Он неполон Я пытался разобраться с кодом, пытаясь выяснить его, нокак вы видите, я могу добавить без проблем в конце списка.У меня проблемы с тем, что в списке, например, 1,2,3,4,,5 есть 5 элементов, и я добавляю шестой, список, очевидно, будет выглядеть так: 1,2,3,4,5,6.То, что я хочу сделать, - это принять пользовательский ввод, например, добавить шестой элемент, возможно, в точку 3, чтобы список выглядел следующим образом 1,2,6,3,4,5.Я попробовал несколько вещей, указав в правильном направлении, или некоторая помощь будет принята с благодарностью.Спасибо,

Ниже приведены мои определения структуры 

struct GraphicElement {
    char *fileName;
    struct GraphicElement *pNext;
};
struct RasterGraphic {
    //int numNodes;
    struct GraphicElement *GraphicElements;
};

1 Ответ

0 голосов
/ 23 сентября 2018

В настоящее время у вас есть следующее: 

if (response == counter) {
    return;
}
else {
    while(response < counter){
        tempTail = tempTail->pNext;
        response++;
    }
}

Я бы исправил это так: 

if (response > counter+1 || response < 1) { // These are all invalid values
    return;
}
else if (response == 1) { // We are replacing the head node
    newNode->pNext = tempTail->pNext;
    pA->GraphicElements = newNode;
}
else {
    while(response-- > 2) { // Responses are 1-indexed
        tempTail = tempTail->pNext;
    }
    newNode->pNext = tempTail->pNext; // IMPORTANT: Update newNode reference FIRST
    tempTail->pNext = newNode; // Update tempTail to point to newNode
}

Отказ от ответственности - никак не проверен

Я пытался комментировать вещи, которые я считал важными здесь и там.Однако здесь следует помнить, что для того, чтобы вставить что-то в односвязный список, вы должны обновить свой новый узел, чтобы он указывал на остальную часть связанного списка, ПРЕЖДЕ ЧЕМ вы обновите ссылку на узел, предшествующий ему, или иначепоследний бит вашего списка будет потерян навсегда, и у вас будет циклическая ссылка на последний узел.

В качестве примечания, похоже, что вы пересекаете весь связанный список дважды каждый раз, когда хотитедобавить новый элемент к нему.Я мог бы порекомендовать вести постоянный счетчик количества элементов в связанном списке, который вы обновляете каждый раз, когда добавляете в него что-то, чтобы избежать затрат на пересчет этого значения, если вы цените эффективность.

Надеюсь, это поможет!

РЕДАКТИРОВАТЬ: Однако вам придется удалить строку, которая добавляет новый узел в конец списка выше в функции, чтобы это работало."tempHead-> pNext = newNode;"

...