Вот этот код:
#include <fcntl.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>
#define BLOCK_SIZE 4096
#define NODE_SIZE 12
#define NODES_PER_BLOCK (BLOCK_SIZE / NODE_SIZE)
#define SHIFT_4 4
#define SHIFT_8 8
#define SHIFT_16 16
#define SHIFT_24 24
struct Node {
int32_t key;
int32_t left_idx;
int32_t right_idx;
};
struct FileCache {
int fd;
size_t block_num;
size_t buffer_size;
unsigned char buffer[BLOCK_SIZE];
};
bool first_printed = false;
int32_t read_int32_le(const unsigned char *buf) {
return (int32_t)(((int32_t)buf[0]) | ((int32_t)buf[1] << SHIFT_8) |
((int32_t)buf[2] << SHIFT_16) |
((int32_t)buf[3] << SHIFT_24));
}
int read_node(size_t node_idx, struct FileCache *cache, struct Node *out_node,
size_t total_nodes) {
size_t block_num = node_idx / NODES_PER_BLOCK;
size_t node_offset_in_block = node_idx % NODES_PER_BLOCK;

if (cache->block_num != block_num) {
    off_t offset = (off_t)(block_num * BLOCK_SIZE);
    size_t bytes_to_read = BLOCK_SIZE;

    if (offset + BLOCK_SIZE > (off_t)(total_nodes * NODE_SIZE)) {
        if ((off_t)(total_nodes * NODE_SIZE) < offset) {
            return -1;
        }
        bytes_to_read = (size_t)((off_t)(total_nodes * NODE_SIZE) - offset);
        bytes_to_read -= bytes_to_read % NODE_SIZE;
    }
    if (bytes_to_read < NODE_SIZE) {
        return -1;
    }

    ssize_t bytes_read =
        pread(cache->fd, cache->buffer, sizeof(cache->buffer), offset);
    if (bytes_read != (ssize_t)bytes_to_read) {
        return -1;
    }
    cache->block_num = block_num;
    cache->buffer_size = bytes_to_read / NODE_SIZE;
}

unsigned char *node_buf = cache->buffer + node_offset_in_block * NODE_SIZE;
out_node->key = read_int32_le(node_buf);
out_node->left_idx = read_int32_le(node_buf + SHIFT_4);
out_node->right_idx = read_int32_le(node_buf + SHIFT_8);

return 0;
}
void traverse(size_t node_idx, struct FileCache *cache, size_t total_nodes) {
if (node_idx >= total_nodes) {
return;
}

struct Node current_node;
if (read_node(node_idx, cache, &current_node, total_nodes) != 0) {
    return;
}

if (current_node.right_idx != 0) {
    traverse(current_node.right_idx, cache, total_nodes);
}

if (first_printed) {
    printf(" %d", current_node.key);
} else {
    printf("%d", current_node.key);
    first_printed = true;
}

if (current_node.left_idx != 0) {
    traverse(current_node.left_idx, cache, total_nodes);
}
}
int main(int argc, char *argv[]) {
if (argc != 2) {
return 1;
}

const char *filename = argv[1];
int fd = open(filename, O_RDONLY);
if (fd < 0) {
    perror("open");
    return 1;
}

struct stat st;
if (fstat(fd, &st) != 0) {
    close(fd);
    return 1;
}

if (st.st_size % NODE_SIZE != 0) {
    close(fd);
    return 1;
}

size_t total_nodes = st.st_size / NODE_SIZE;

struct FileCache cache;
cache.fd = fd;
cache.block_num = (size_t)(-1);
cache.buffer_size = 0;

if (total_nodes == 0) {
    printf("\n");
    close(fd);
    return 0;
}

traverse(0, &cache, total_nodes);

printf("\n");

close(fd);
return 0;
}
Выдает:
Partial solution
61 total tests runs, 30 passed, 31 failed.
Score gained: 0 (out of 100).
N Result Time (sec) Score
1 OK 0.006 0 (0)
2 OK 0.004 0 (0)
3 OK 0.004 0 (0)
4 OK 0.004 0 (0)
5 OK 0.004 0 (0)
6 OK 0.004 0 (0)
7 OK 0.004 0 (0)
8 OK 0.004 0 (0)
9 OK 0.004 0 (0)
10 OK 0.004 0 (0)
11 OK 0.004 0 (0)
12 OK 0.004 0 (0)
13 OK 0.004 0 (0)
14 OK 0.010 0 (0)
15 OK 0.007 0 (0)
16 OK 0.007 0 (0)
17 OK 0.009 0 (0)
18 OK 0.010 0 (0)
19 OK 0.010 0 (0)
20 OK 0.009 0 (0)
21 OK 0.008 0 (0)
22 OK 0.008 0 (0)
23 OK 0.007 0 (0)
24 OK 0.004 0 (0)
25 OK 0.004 0 (0)
26 OK 0.004 0 (0)
27 OK 0.004 0 (0)
28 OK 0.004 0 (0)
29 OK 0.004 0 (0)
30 OK 0.005 0 (0)
31 Run-time error 0.981 0 (0)
32 Run-time error 0.353 0 (0)
33 Run-time error 0.496 0 (0)
34 Time-limit exceeded >1.000 0 (0)
35 Time-limit exceeded >1.000 0 (0)
36 Time-limit exceeded >1.000 0 (0)
37 Time-limit exceeded >1.000 0 (0)
38 Time-limit exceeded >1.000 0 (0)
39 Time-limit exceeded >1.000 0 (0)
40 Run-time error 0.392 0 (0)
41 Run-time error 0.955 0 (0)
42 Run-time error 0.744 0 (0)
43 Run-time error 0.789 0 (0)
44 Time-limit exceeded >1.000 0 (0)
45 Run-time error 0.990 0 (0)
46 Time-limit exceeded >1.000 0 (0)
47 Run-time error 0.992 0 (0)
48 Run-time error 0.891 0 (0)
49 Run-time error 0.922 0 (0)
50 Run-time error 0.792 0 (0)
51 Run-time error 0.749 0 (0)
52 Time-limit exceeded >1.000 0 (0)
53 Run-time error 0.903 0 (0)
54 Time-limit exceeded >1.000 0 (0)
55 Run-time error 0.904 0 (0)
56 Time-limit exceeded >1.000 0 (0)
57 Time-limit exceeded >1.000 0 (0)
58 Time-limit exceeded >1.000 0 (0)
59 Time-limit exceeded >1.000 0 (0)
60 Time-limit exceeded >1.000 0 (0)
61 Wrong answer 0.004 0 (0)
В чем проблема?
Попробуй исправить
Вот задача, которую он должен решать:
Problem sm09-3: unix/files/binary-tree-2
В аргументах командной строки задается имя входного бинарного файла произвольного доступа. Бинарный файл рассматривается как массив структур:
struct Node
{
int32_t key;
int32_t left_idx;
int32_t right_idx;
};
Структура описывает вершину бинарного дерева поиска, где key – ключ поиска, а значения left_idx и right_idx – индексы в массиве соответственно левой и правой вершины. Корень дерева находится в элементе массива с индексом 0. Признаком отсутствия соответствующего поддерева в вершине является индекс, равный 0.
Числа в файле хранятся в естественном для x86 представлении (little-endian).
На стандартный поток вывода напечатайте ключи, размещенные в данном дереве, в порядке убывания.
Считывать содержимое всего файла в память целиком (хранить полное дерево в памяти) запрещается. Для чтения содержимого файла необходимо пользоваться низкоуровневым вводом-выводом (open/read/etc). Корректная работа на big-endian архитектуре не требуется. Не используйте низкоуровневые манипуляции с памятью (union, приведение типов указателей). Не используйте библиотечные функции преобразования.
Для вывода ключей можно использовать высокоуровневые потоки (stdout).
Не забывайте выводить '\n' в конце вывода.
В программе должна быть реализована проверка корректности чтения из файла. Минимизируйте число системных вызовов, необходимых для чтения одной записи из файла.
Например для этого файла надо вывести 9 8 7 6 5 4 3 2 1
Submit a solution
Language: gcc - GNU C 11.3.0