Задачи модуля "Файл и вектор": от реверса до слияния файлов

Доступ к файлу строго последовательный - читать его с конца нельзя. Какая структура из этой темы позволит обойти это ограничение?

Реверс файла в чистом виде невозможен: чтение идет строго слева направо. Поэтому используется дополнительная память - вектор:

1. Открываем файл для чтения и считываем все числа в динамический массив. Когда массив заполняется, расширяем его через realloc (удобно удваивать емкость).
2. Закрываем файл и открываем его же в режиме записи "w" - файл при этом очищается.
3. Проходим по массиву с конца (от count - 1 до 0) и записываем числа в файл.
4. Освобождаем память.

Здесь встречаются обе структуры темы: файл дает долговременное хранение, вектор - доступ по индексу, которого файлу не хватает.

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

void ReverseFile(const char* filename) {
    /* 1. Читаем все числа файла в вектор */
    FILE* file = fopen(filename, "r");
    if (file == NULL) {
        printf("Не удалось открыть файл %s для чтения.\n", filename);
        return;
    }

    int capacity = 10;
    int count = 0;
    int* arr = (int*)malloc(capacity * sizeof(int));

    int temp;
    while (fscanf(file, "%d", &temp) == 1) {
        if (count == capacity) {
            capacity *= 2; /* вектор заполнен - удваиваем емкость */
            arr = (int*)realloc(arr, capacity * sizeof(int));
        }
        arr[count] = temp;
        count++;
    }
    fclose(file);

    /* 2. Открываем файл на перезапись (режим "w" очищает его) */
    file = fopen(filename, "w");
    if (file == NULL) {
        printf("Не удалось открыть файл %s для записи.\n", filename);
        free(arr);
        return;
    }

    /* 3. Записываем числа с конца массива */
    for (int i = count - 1; i >= 0; i--) {
        fprintf(file, "%d ", arr[i]);
    }

    fclose(file);
    free(arr);
}

int main(void) {
    const char* filename = "numbers.txt";

    /* Создаем файл с числами для демонстрации */
    FILE* f = fopen(filename, "w");
    if (f != NULL) {
        fprintf(f, "1 2 3 4 5");
        fclose(f);
    }

    ReverseFile(filename); /* в файле станет: 5 4 3 2 1 */
    return 0;
}

Какие размеры у результата, если исходная матрица имела M строк и N столбцов? Что происходит с элементом A[i][j]?

При транспонировании строки становятся столбцами: матрица M × N превращается в N × M, а элемент A[i][j] переходит в B[j][i].

1. Читаем из файла размеры rows и cols.
2. Выделяем память под матрицу rows × cols и считываем элементы. Двумерный массив в C строится как вектор указателей на векторы-строки.
3. Выделяем память под результат cols × rows - размеры меняются местами.
4. Двойным циклом копируем: transposed[j][i] = matrix[i][j].
5. Выводим результат и освобождаем обе матрицы.

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

int main(void) {
    /* Создаем тестовый файл: матрица 2 x 3 */
    FILE* init_file = fopen("matrix.txt", "w");
    if (init_file) {
        fprintf(init_file, "2 3\n");
        fprintf(init_file, "1 2 3\n");
        fprintf(init_file, "4 5 6\n");
        fclose(init_file);
    }

    FILE* file = fopen("matrix.txt", "r");
    if (file == NULL) {
        printf("Ошибка открытия файла.\n");
        return 1;
    }

    int rows, cols;
    fscanf(file, "%d %d", &rows, &cols);

    /* Исходная матрица: вектор указателей на строки */
    int** matrix = (int**)malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; i++) {
        matrix[i] = (int*)malloc(cols * sizeof(int));
        for (int j = 0; j < cols; j++) {
            fscanf(file, "%d", &matrix[i][j]);
        }
    }
    fclose(file);

    /* Результат: размеры меняются местами */
    int** transposed = (int**)malloc(cols * sizeof(int*));
    for (int i = 0; i < cols; i++) {
        transposed[i] = (int*)malloc(rows * sizeof(int));
    }

    /* Транспонирование: индексы i и j меняются местами */
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            transposed[j][i] = matrix[i][j];
        }
    }

    printf("Транспонированная матрица (%d x %d):\n", cols, rows);
    for (int i = 0; i < cols; i++) {
        for (int j = 0; j < rows; j++) {
            printf("%d ", transposed[i][j]);
        }
        printf("\n");
    }

    for (int i = 0; i < rows; i++) free(matrix[i]);
    free(matrix);
    for (int i = 0; i < cols; i++) free(transposed[i]);
    free(transposed);

    return 0;
}

В каждый момент времени достаточно видеть только по одному текущему числу из каждого файла. Какое из трех чисел должно уйти в результат первым?

Классическое трехпутевое слияние (K-way merge) - алгоритм работает в один проход, храня в памяти всего три числа:

1. Открываем три исходных файла для чтения и выходной для записи.
2. Считываем по первому числу из каждого файла: A, B, C.
3. Если какой-то файл закончился, его текущее значение заменяется "бесконечностью" - константой INT_MAX. Так исчерпанный файл никогда не выиграет сравнение.
4. Записываем в выходной файл наименьшее из трех значений и считываем новое число только из того файла, откуда взяли минимум.
5. Повторяем, пока все три значения не станут равны INT_MAX.

Именно так работает внешняя сортировка огромных файлов, не влезающих в оперативную память, - к ней курс вернется в теме "Сортировки".

#include <stdio.h>
#include <limits.h> /* INT_MAX */

/* Читает следующее число; если файл кончился - возвращает INT_MAX */
int ReadNext(FILE* file) {
    int val;
    if (fscanf(file, "%d", &val) == 1) {
        return val;
    }
    return INT_MAX;
}

void MergeThreeFiles(const char* f1, const char* f2,
                     const char* f3, const char* out) {
    FILE* file1 = fopen(f1, "r");
    FILE* file2 = fopen(f2, "r");
    FILE* file3 = fopen(f3, "r");
    FILE* file_out = fopen(out, "w");

    if (!file1 || !file2 || !file3 || !file_out) {
        printf("Ошибка открытия файлов.\n");
        return;
    }

    int val1 = ReadNext(file1);
    int val2 = ReadNext(file2);
    int val3 = ReadNext(file3);

    /* Пока хотя бы один файл не дочитан */
    while (val1 != INT_MAX || val2 != INT_MAX || val3 != INT_MAX) {
        int min_val = val1;
        if (val2 < min_val) min_val = val2;
        if (val3 < min_val) min_val = val3;

        fprintf(file_out, "%d ", min_val);

        /* Продвигаем только тот файл, откуда взяли минимум */
        if (min_val == val1) {
            val1 = ReadNext(file1);
        } else if (min_val == val2) {
            val2 = ReadNext(file2);
        } else {
            val3 = ReadNext(file3);
        }
    }

    fclose(file1);
    fclose(file2);
    fclose(file3);
    fclose(file_out);
}

int main(void) {
    /* Ожидаются отсортированные файлы, например:
       f1.txt: 1 5 9
       f2.txt: 2 6 10
       f3.txt: 3 7 8   */
    MergeThreeFiles("f1.txt", "f2.txt", "f3.txt", "out.txt");
    printf("Слияние завершено.\n");
    return 0;
}