1

Необходимо отсортировать массив. Есть N, необходимо создать массив длинной в 2 * N элементов таким образом: a1, aN + 1, a2, aN + 2, a3, AN + 3, ... aN, a2 * N;

Входной массив:

0 1 2 3 4 5 6 7 8 9

Результат после сортировки:

0 5 1 6 2 7 3 8 4 9

Проблема задачи в том, что использовать дополнительные массивы запрещено. Можно использовать только переменные типа int tmp;

Пытался сделать такое, но удается лишь добиться такого успеха:

0 5 1 6 3 7 2 8 4 9

Задача вообще для перекомпоновки списков на СИ, но с массивами почти также. Не могу дойти до правильного алгоритма самостоятельно. Заранее спасибо!

UPD: Мой код для списка:

void CHANGE_STRUCT(int n) {

List *P = BegL;
List *Pk = BegL;
List *Pl = BegL;
int tmp;


for(int i = 1; i <= n; i++) {
    Pk = Pk -> link;
}

Pl = Pl -> link;
for(int i = 1; i < n; i++){
    P = P -> link;
    Pl = Pl -> link;
    tmp = Pk -> A;
    Pk -> A = P -> A;
    P -> A = tmp;
    tmp = Pl -> A;
    Pl -> A = Pk -> A;
    Pk -> A = tmp;
    Pk = Pk -> link;
    Pl = Pl -> link;
    P = P -> link;
}
printf("\nNew struct\n");
PRINT_STRUCT();}
7
  • Так все же — список или массив? список-то перекомпоновать куда проще... просто берем нужный элемент с номером n+1 и далее и переносим куда надо. С массивом так просто не получится...
    – Harry
    12 июн 2022 в 13:42
  • Вообще необходимо список. Он может быть как односвязный так и двусвязный. Я пробовал сделать с односвязным. Элементы после N (5,6,7,8,9) становятся идеально, а с а1 до N уже проблема. Не вижу правильного решения. Например если N <= 3, то с моим решением всё работает, а дальше уже живет своей жизнью.
    – Илья
    12 июн 2022 в 13:49
  • С двусвязным проще :) - не надо держать лишние переменные.
    – Harry
    12 июн 2022 в 14:05
  • Со списком ведь будет действительно проще. Я ведь могу не переставлять элементы таким образом, а сделать иначе: я могу после а1 сделать вставку aN+1, а потом удалить старый aN + 1. Правильно?
    – Илья
    12 июн 2022 в 14:05
  • Не "вставить-удалить", а "перенести". Например, у вас некий a, после которого надо вставить некий p. Вытаскиваем его из его старого места, типа p->prev->next = p->next; p->next->prev = p->prev; (конечно, надо проверять, не конец ли это списка с той или иной стороны — на NULL), а потом поместить в новое место типа p->next = a->next; p->prev=a; a->next->prev = p; a->next = p;. Где-то так. Еще раз — нужны проверки на концах списка. И идти не индексами, а указателями...
    – Harry
    12 июн 2022 в 14:12

2 ответа 2

1

В C односвязные списки можно редактировать передавая в функции адрес поля next в предыдущем узле. Так работает insert, который вставляет новый узел в начало списка. Так работает cut, который срезает голову списка и возвращает её. reorder использует два бегущих указателя - для первой и для второй половин списка. Узел указываемый вторым указателем вырезается и вставляется после узла указываемого первым.

Обратите внимание на нотацию: если функция не меняет список, она вызывается с указателем на голову списка: print(head). Если функция меняет список, она вызывается с указателем на указатель на голову. Голова может поменяться, это необходимо: insert(&head, ...). Про функцию reorder известно что она не меняет голову списка, её можно было бы вызывать как reorder(head, ...). Проявляем твёрдость, добавляем ещё один уровень косвенности: reorder(&head, ...). Нотация.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node_t node_t;
struct node_t {
    int value;
    node_t *next;
};

void insert(node_t **head, node_t *node) {
    assert(node->next == NULL);
    node->next = *head;
    *head = node;
}

node_t *cut(node_t **head) {
    node_t *node = *head;
    *head = (*head)->next;
    node->next = NULL;
    return node;
}

void reorder(node_t **head, int n) {
    node_t **n1 = head;
    node_t **n2 = head;
    for (int i = 0; i < n; ++i) {
        n2 = &(*n2)->next;
    }
    for (int i = 0; i < n; ++i) {
        n1 = &(*n1)->next;
        insert(n1, cut(n2));
        n1 = &(*n1)->next;
    }
}

void print(node_t *head) {
    printf("[ ");
    for (; head != NULL; head = head->next) {
        printf("%d ", head->value);
    }
    puts("]");
}

int main() {
    node_t *head = NULL;
    for (int i = 9; i >= 0; --i) {
        node_t *node = malloc(sizeof(node_t));
        node->value = i;
        node->next = NULL;
        insert(&head, node);
    }
    print(head);
    reorder(&head, 5);
    print(head);
}
0

Функция move_to по индексу определяет где должен оказаться элемент с этого индекса. Если её последовательно применять в цикле i = move_to(i), окажется что индексы бегают по циклу. В этом цикле все числа надо переставить на следующую позицию (rearrange_loop). Чтобы не обрабатывать цикл несколько раз (что испортит результат) он обрабатывается только тогда когда встречен первый раз (fresh_loop).

Алгоритм квадратичный - это плата за неиспользование дополнительной линейной памяти. Есть ли способ решить без дополнительной памяти за линейное время для данной конкретной перестановки - не знаю.

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

int move_to(int n, int i) {
    if (i < n) {
        return 2 * i;
    } 
    return 2 * i + 1 - 2 * n;
}

bool fresh_loop(int n, int i) {
    for (int j = move_to(n, i); j != i; j = move_to(n, j)) {
        if (j < i) {
            return false;
        }
    }
    return true;
}

void rearrange_loop(int n, int i, int a[/* 2n */]) {
    int v = a[i];
    for (int j = move_to(n, i); j != i; j = move_to(n, j)) {
        int tmp = a[j];
        a[j] = v;
        v = tmp;
    }
    a[i] = v;
}

void rearrange(int n, int a[/* 2n */]) {
    for (int i = 0; i < 2 * n; ++i) {
        if (fresh_loop(n, i)) {
            rearrange_loop(n, i, a);
        }
    }
}

void print(int n, int a[/* 2n */]) {
    printf("[ ");
    for (int i = 0; i < 2 * n; ++i) {
        printf("%d ", a[i]);
    }
    puts("]");
}

int main() {
    int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    print(5, a);
    rearrange(5, a);
    print(5, a);
}

Ваш ответ

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

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