0

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

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

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;
}

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

6
  • 1
    Можете подробней объяснить как вы получаете на второй итерации 1 1 2 2 1 2 вы добавляете 1 в начало, потом удаляете выписывая его, далее 2 единицы вставляете, потом двойку и получаете по идее 1 1 2 и потом удаляете 1 выписывая, потом вставляете 2 получая 1 2 2 и потом опять убираете 1 выписываете, и получаете 1 1 1?? 14 янв 2021 в 21:21
  • @ПавелЕриков это ответ который должен быть по условии задания. Задания "очередь к врачу". Вот что в задании о входящих данных: The first line of input contains the number of test cases D. Each test case starts with number N of the events taking place in the clinic (1<=N<=1000). Afterwards there are N natural numbers. A positive number is the number given by the receptionist to a new patient (not greater than the current number of patients in the queue plus 1), and number 0 means that the doctor calls a patient.
    – kiker
    14 янв 2021 в 21:32
  • 1
    Объясните простым языком, подробней как работает алгоритм 14 янв 2021 в 21:58
  • @ПавелЕриков постараюсь просто, у нас есть очередь к врачу, у каждого пациента есть свой номер. Первое число это к-лво наборов данных, дальше это количество данных в данном наборе. Если число равно нулю это значит что нужно удалить первый елемент списка и выписать на эеран, если число(n) больше 0 - нужно создать узел с ключем n и вставить на n место. Это дополнительное задание с универе. Все это нужно сделать на односвязаным списке.
    – kiker
    14 янв 2021 в 23:06
  • 1
    XD я прошу вас рассказать поэтапно. В 1 комментарии я расписал, поэтапно как я понял алгоритм, но он получает 1 1 1 а не 1 1 2. Вот я прошу вас так же расписать :) условие то я прочитал уже не раз 14 янв 2021 в 23:14

1 ответ 1

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) и выход у меня такой, как у вас в примере.

1
  • спасибо большое
    – kiker
    15 янв 2021 в 11:26

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.