Блог

Главная - Вопросы по программированию - Учитывая массив l1, l2,l3 . . . ln создайте новый массив следующим образом: (l1 ln),(l2 l[n-1]), . . .(l[n / 2] l[n / 2 1])

Учитывая массив l1, l2,l3 . . . ln создайте новый массив следующим образом: (l1 ln),(l2 l[n-1]), . . .(l[n / 2] l[n / 2 1])

#c #algorithm

#c #алгоритм

Вопрос:

Итак, у меня следующая проблема:

Учитывая массив l1, l2,l3 . . . ln, создайте новый массив следующим образом: (l1 ln),(l2 l[n-1]), . . .(l[n / 2] l[n / 2 1]). Эта проблема имеет следующие правила и информацию:

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

Я много раз пытался решить эту проблему, и хотя я был близок к решению, результат по-прежнему находится в неправильном порядке. Далее я показываю свой текущий сценарий тестирования:

 struct No
{
int Value;
 Нет * Следующий;
 };
typedef No* Noptr;
 
 int main()
 {
 Noptr L = NULL;
 InsertList(L,1);
 InsertList(L,2);
 InsertList(L,3);
 InsertList(L,5);
 InsertList(L,4);
 InsertList(L,3);
 InsertList(L,9);
 InsertList(L,2);
 InsertList(L,7);
 InsertList(L,1);
 InsertList(L,10);
 InsertList(L,12);
 InsertList(L,11);
 InsertList(L,15);
 InsertList(L,19);
 InsertList(L,16);
 Noptr L4 = SumValues(L);
 Список (L4);
 
 возвращает 0;
 }
 
 
 Noptr суммирует значения (Noptramp; L)
 {
if(L == NULL){
 верните L;
 }
 Noptr L1 = NULL;
 Noptr L2 = NULL;
 Noptr aux1 = L;
bool Even= false;
 while(aux1 != NULL)
 {
если(!Четный)
 {
 InsertLista(L1,aux1->Значение);
 }
 ещё
 {
 InsertLista(L2,aux1->Значение);
 }
 Четный = !Четный;
 aux1 = aux1->Следующий;
 }
 L2 = InverterLista(L2);
 Noptr LReturn = NULL;
 aux1 = L1;
 Noptr aux2 = L2;
в то время как(aux1!= NULL){
 InsertList(LReturn ,(aux1->Значение  aux2-> Значение));
 aux1 = aux1->Следующий;
 aux2 = aux2->Следующий;
 }
освободить(L1);
 освободить(L2);
 свободно(aux1);
 свободно(aux2);
 верните LReturn;
}

Я ожидал, что массив: 17, 21, 18, 16, 16, 13, 10, 9; вместо этого я получил: 17, 18, 16, 10, 9, 13, 16, 21 Для лучшей визуализации я создал таблицу

  [00] [01] [02] [03] [04] [05] [06] [07] INDEX

 17   21   18   16   16   13   10   09  EXPECTED

 17   18   16   10   09   13   16   21  RESULT

Что я сделал не так?

Комментарии:

1. Невозможно воспроизвести. Вместо этого я получаю 11 ошибок компилятора.

2. Используйте меньшие и более легко анализируемые тестовые примеры.

3. Подготавливая список L1 и L2 , не нарушаете ли вы это условие — не разрешается создавать вспомогательный список для чтения данных более одного раза. ?

4. Похоже, вы перепутали это упражнение с другим. Там нет упоминания о четных и нечетных элементах, просто первая половина добавляется к обратной части второй половины.

5. @H.S. Это правило должно было предотвратить создание чего-то вроде: Lcopy = Loriginal; читайте Lcopy столько раз, сколько хотите, потому что это не Loriginal. Извините, если это сбило с толку. Molbdnilo, код был всего лишь одной из моих попыток, поскольку список может содержать любое количество элементов, если их четное число, я подумал, что разделение их на 2 подсписка поможет.

Ответ №1:

Алгоритм:

  1. Переверните первую половину исходного списка.
  2. Перейдите к первой половине и второй половине списка:
    • Позаботьтесь о размере списка:
      • Если размер исходного списка нечетный, то среднее значение узла будет последним значением узла нового списка.
      • Если размер исходного списка четный, то сумма значений n/2 th node и n/2 1 th node будет последним значением узла нового списка. Обратите внимание, что n/2 th-узел является первым узлом перевернутого списка, а n/2 1 th-узел — первым узлом второй половины списка.
    • Добавьте значение обоих узлов списка и присвоите это значение новому узлу списка. Перейдите к следующему узлу в обоих списках.
    • Добавьте каждый узел нового узла списка в начало нового списка.
  3. Повторяйте шаг 2, пока ни один из указателей списка не достигнет nullptr .
  4. Верните исходный список в исходную форму (снова переверните первую половину).

Реализация:
(не чисто объектно-ориентированная реализация, но достаточно для понимания)

 #include <iostream>
#include <cstdlib>

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x):val(x),next(nullptr){}
    ~ListNode(){/*take care of deallocation*/}
};

struct ListNode * getNode(int x) {
    struct ListNode *temp = new ListNode(x);
    if (temp == nullptr) {
        exit (EXIT_FAILURE);
    }

    return temp;
}

void insert(int d, struct ListNode ** head) {
    struct ListNode *temp = getNode(d);

    if (temp == nullptr) {
        exit (EXIT_FAILURE);
    }

    struct ListNode **curr = head;
    while (*curr) {
        curr = amp;((*curr)->next);
    }

    *curr = temp;
}

// Algorithm implementation
struct ListNode * sumValues(struct ListNode *head){
    int odd = 0;
    struct ListNode *slowPtr = head;
    struct ListNode *fastPtr = head;
    struct ListNode *newList = nullptr;
    struct ListNode *prev = nullptr;

    // Reverse first half of original list
    while (fastPtr) {
        fastPtr = fastPtr->next;
        if (!fastPtr) {
            odd = 1;
            break;
        }
        fastPtr = fastPtr->next;
        struct ListNode *curr = slowPtr->next;
        slowPtr->next = prev;
        prev = slowPtr;
        slowPtr = curr;
    }

    struct ListNode *L1 = prev;
    struct ListNode *L2 = nullptr;
    L2 = slowPtr;

    // The middle node of original list will be last node of new list if orignal list has odd number of nodes
    if (odd) {
        L2 = L2->next;
        newList = getNode(slowPtr->val);
    }

    // Traverse both first half (reversed) and second half of original list and prepare new list
    while (L2) {
        struct ListNode *tmp = getNode(L1->val   L2->val);
        tmp->next = newList;
        newList = tmp;
        L2 = L2->next;
        L1 = L1->next;
    }

    // Reset the original list
    struct ListNode *tmp = prev;
    prev = slowPtr;
    while (tmp) {
        struct ListNode *curr = tmp->next;
        tmp->next = prev;
        prev = tmp;
        tmp = curr;
    }

    return newList;
}

void printList(struct ListNode * newList, struct ListNode *origList) {
    struct ListNode *x = origList;
    std::cout << "nPrint listsn";
    std::cout << "Original list : ";
    while (x) {
        std::cout << x->val << " ";
        x = x->next;
    }

    std::cout << "n"; 
    x = newList;
    std::cout << "Sum List : ";
    while (x) {
        std::cout << x->val << " ";
        x = x->next;
    }

    std::cout << "n"; 
}

// Driver code
int main() {
    struct ListNode *head = nullptr;
    struct ListNode *newList = nullptr;

    insert (1, amp;head);
    // list =>  1 -> null
    newList = sumValues(head);
    printList(newList, head);

    insert (2, amp;head);
    // list =>  1 -> 2 -> null
    newList = sumValues(head);
    printList(newList, head);

    insert (3, amp;head);
    // list => 1 -> 2 -> 3 -> null 
    newList = sumValues(head);
    printList(newList, head);

    insert (4, amp;head);
    // list =>  1 -> 2 -> 3 -> 4 -> null
    newList = sumValues(head);
    printList(newList, head);

    insert (5, amp;head);
    // list =>  1 -> 2 -> 3 -> 4 -> 5 -> null
    newList = sumValues(head);
    printList(newList, head);

    insert (4, amp;head);
    // list =>  1 -> 2 -> 3 -> 4 -> 5 -> 4 -> null
    newList = sumValues(head);
    printList(newList, head);

    insert (2, amp;head);
    // list =>  1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 2 -> null
    newList = sumValues(head);
    printList(newList, head);

    insert (4, amp;head);
    // list =>  1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 2 -> 4 -> null
    newList = sumValues(head);
    printList(newList, head);

    insert (1, amp;head);
    // list =>  1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 2 -> 4 -> 1 -> null
    newList = sumValues(head);
    printList(newList, head);

    // Make sure to deallocate both the list

    return 0;
}

Вывод:

 # ./a.out

Print lists
Original list : 1 
Sum List : 1 

Print lists
Original list : 1 2 
Sum List : 3 

Print lists
Original list : 1 2 3 
Sum List : 4 2 

Print lists
Original list : 1 2 3 4 
Sum List : 5 5 

Print lists
Original list : 1 2 3 4 5 
Sum List : 6 6 3 

Print lists
Original list : 1 2 3 4 5 4 
Sum List : 5 7 7 

Print lists
Original list : 1 2 3 4 5 4 2 
Sum List : 3 6 8 4 

Print lists
Original list : 1 2 3 4 5 4 2 4 
Sum List : 5 4 7 9 

Print lists
Original list : 1 2 3 4 5 4 2 4 1 
Sum List : 2 6 5 8 5

Если не разрешено манипулировать исходным списком, вы можете использовать stack для подготовки списка сумм. Алгоритм с использованием стека:

  1. Поместите первую половину исходного списка в стек.
  2. Пройдите вторую половину исходного списка:
    • Позаботьтесь о размере списка:
      • Если размер исходного списка нечетный, то среднее значение узла будет последним значением узла нового списка.
      • Если размер исходного списка четный, то сумма значений n/2 th node и n/2 1 th node будет последним значением узла нового списка. Обратите внимание, что n/2 th-узел является первым узлом стека, а n/2 1 th-узел — первым узлом второй половины списка.
    • Выберите верхнее значение из стека и добавьте значение текущего узла второй половины списка и назначьте новому узлу списка. Извлеките значение из стека и переместите указатель второй половины на его next .
    • Добавьте каждый узел нового узла списка в начало нового списка.
  3. Повторяйте шаг 2, пока стек не опустеет или указатель на вторую половину обхода не достигнет nullptr .

Алгоритм, использующий очередь с двойным завершением:

  1. Возьмите очередь с двойным завершением.
  2. Пройдитесь по всему списку и поместите элементы списка в конец очереди.
  3. Извлеките элемент из передней и задней части очереди, добавьте их и присвоите это значение значению узла, который будет добавлен в конец нового списка.
  4. Повторяйте шаг 3, пока очередь не опустеет.