Односвязаный список

Question

не могу понять где допустил ошибку при имплементации односвязного списка.

Для входящих данных:

2 -> количество итераций
3 1 2 0 (3 это сколько операций в данной итерации )
14 1 0 1 1 2 0 2 0 2 0 1 2 0 0

По заданию если код операции "0", нужно удалить первый елемент и выписать цифру.

Если код(k) операции больше 0, тогда нужно сделать новый узел с ключом k и вставить на k место.

Т.е для тех данных я должен получить такой ответ:

1
1 1 2 2 1 2

Ответ моей программы:

1
1 1 2 1 1 2

Мой код довольно тривиален:

Сама структура списка:

typedef struct list{
    int data;
    struct list * next;
}tList;



tList * init(int x)
{
    tList *lst = (struct list*)malloc(sizeof(struct list));
    lst->data = x;
    lst->next = NULL;
    return(lst);
}

Добавленния элемента

void  push(int x, tList **head) {
    tList *tmp = (tList*) malloc(sizeof(tList));
    tmp->data = x;
    tmp->next = (*head);
    (*head) = tmp;

}

Добавленния на позицию Н:

void push_n_pos(int n, tList *head) {
    tList *tmp = NULL;

    int count = 0;

    while (count < n && head->next) {
        head = head->next;
        count++;
    }

    tmp = (tList*) malloc(sizeof(tList));

    tmp->data = n;
    if(head->next) {
        tmp->next = head->next;
    } else {
        tmp->next = NULL;
    }
    head->next = tmp;
}

Получения первого элемента:

int pop(tList **head) {
    tList  *prev = NULL;
    int val;

    prev = (*head);
    val = prev->data;
    (*head) = (*head)->next;
    free(prev);
    return val;
}

Реализация:

int main() {
    int operation;
    tList *head = NULL;
    cin >> operation;


    while (operation--) {
        int x;
        cin >> x;
        while (x--) {
            int z;
            cin >> z;
            if (z > 0) {
                if (z == 1) {
                    push(z, &head);
                } else
                    push_n_pos(z, head);
            } else if (z == 0) {
                cout << pop(&head) << " ";
            }
        }
            free(head);
            cout << "\n";
    }

    return 0;
}

Пробовал чтобы добавлять самый первый элемент один раз, создавал для этого флаг. Но к сожалению ничего не получилось. Не прошу решения задачи, только подсказки, где ошибка

Answer 1

Как и ожидалось ошибка в вашей функции push_n_pos.

Например сейчас мы на 1 0 1 1 2 и все что вывелось, это 1, а в данный момент список у вас 1 1 и вы хотите добавить 2. Чтобы получить вывод 1 1 2 вам нужно вставить двойку таким образом 1 2 1 то есть, чтобы она находилась под индексом n - 1 => 1, то есть после первого элемента.

Так что вам в первом цикле, нужно при n == 2, чтобы head указывал на первый элемент, по этому нужно писать так:

while (count < n - 2 && head->next)

Я тестировал на c++ (т.к. вы используете cin и cout) и выход у меня такой, как у вас в примере.

БЛОГ НА HUSL

Односвязаный список

Ответы (1 шт):