Как я могу прочитать текстовый файл матрицы в связанный список в C, используя указатели?

Question

Мне нужно прочитать текстовый файл букв, используя списки связанных матриц, где каждая буква должна иметь 8 указателей вокруг нее.

Вот что мне нужно сделать: введите описание изображения здесь

Текстовый файл такой:

JDCPCPXOAA
ZXVOVXFRVV
NDLEIRBIEA
YTRQOMOIIO
FZZAPXERTQ
XAUEOEOOTO
PORTUOAZLZ
CZNOQUPUOP

В моем коде я могу читать только буквы в первой строке.

Может ли кто-нибудь мне помочь?

typedef struct letter           ///estrutura para cada letra da sopa
{
    char *lname;
    struct letter *pnext;
}LETTER;

typedef struct soup         ///estrutura para a sopa de letras
{
    int lin;
    int col;
    LETTER *pfirst;
}SOUP;

void read_soup_txt(SOUP *pcs,char *fn,int lin,int col)
{
  FILE *fp;
  fp=fopen(fn,"r");
  char c;
  if(fp!=NULL)
  {
    pcs->lin=lin;
    pcs->col=col;
    LETTER *current=malloc(sizeof(LETTER)),*previous;
    pcs->pfirst=current;

    for(int i=0;i<pcs->lin;i++)     ///linhas
    {
      for(int j=0;j<pcs->col;j++)     ///colunas
      {
        fscanf(fp,"%c",&c);                     ///le o char
        current->lname=malloc(sizeof(char));       ///aloca espaço para o char
        strcpy(current->lname,&c);              ///copia o char para a estrutura
        previous=current;

        if(i==pcs->lin-1)
        {
            current=NULL;
        }
        else
            current=malloc(sizeof(LETTER));
        previous->pnext=current;
      }
    }
  }
  else
    printf("Erro ao abrir arquivo!");
  fclose(fp);
}

Answer 1

каждая буква должна иметь 8 указателей вокруг нее.

Это означает, что ваша структура письма должна выглядеть примерно так:

struct letter {
    struct letter  *up_left;
    struct letter  *up;
    struct letter  *up_right;
    struct letter  *left;
    struct letter  *right;
    struct letter  *down_left;
    struct letter  *down;
    struct letter  *down_right;
    int             letter;
};

Тебе не нужен суп из писем. Поскольку вы читаете символы по порядку, вы можете читать их непосредственно в график. Хитрость заключается в том, что вам нужно сохранить один struct letter указатель на верхнюю левую букву на графике; один struct letter указатель на первую букву в каждой строке; и один struct letter указатель для каждой новой добавляемой буквы.

Вот логика в псевдокоде :

Function ReadGraph(input):

    Let  topleft  = NULL     # Top left letter in the graph
    Let  leftmost = NULL     # Leftmost letter in current line
    Let  previous = NULL     # Previous letter in current line
    Let  current  = NULL     # Current letter
    Let  letter = ''

    Do:
        Read next letter from input
    While (letter is not a letter nor EOF)
    If letter is EOF:
        # No letters at all in the input, so no graph either.
        Return NULL
    End If

    topleft = new struct letter (letter)
    leftmost = topleft
    current = topleft

    # Row loop. First letter is already in current.
    Loop:

        # Loop over letters in the current line
        Loop:
            Read new letter from input
            If letter is EOF, or newline:
                Break
            End If

            previous = current
            current = new struct letter

            current->left = previous
            previous->right = current

            If current->left->up is not NULL:
                current->up_left = current->left->up
                current->up_left->down_right = current

                If current->up_left->right is not NULL:
                    current->up = current->up_left->right
                    current->up->down = current

                    If current->up->right is not NULL:
                        current->up_right = current->up->right
                        current->up_right->down_left = current
                    End If
                End If
            End If

        End Loop

        If letter is not EOF:
            While (letter is not EOF) and (letter is not a letter):
                Read new letter from input
            End While
        End If
        If letter is EOF:
            Break
        End If

        # We have a first letter on a new line.
        current = new letter structure

        current->up = leftmost
        leftmost->down = current

        If current->up->right is not NULL:
            current->up_right = current->up->right
            current->up_right->down_left = current
        End If

        leftmost = current

    End Loop

    Return topleft
End Function

Обратите внимание, как первый символ во входном потоке обрабатывается по-разному (в самом начале), и как первый символ в каждой последующей строке обрабатывается по-разному (ближе к концу функции). Это может показаться странным с точки зрения логики или структуры, но выполнение этого таким образом делает код простым.

Также обратите внимание, как устроены двунаправленные ссылки. Поскольку мы читаем сверху вниз, слева направо, мы устанавливаем связь сначала слева, затем вверх-влево, затем вверх, затем вверх-вправо; с обратной ссылкой сразу после прямой ссылки.

Требуется немного подумать, чтобы понять, почему это работает. Рассмотрим:

  up_left │  up  │   up_right
──────────┼──────┼───────────
     left │ curr │      right
──────────┼──────┼───────────
down_left │ down │ down_right

Когда мы создаем curr, мы знаем, существует ли left или нет, потому что мы обрабатываем первую букву в каждой строке отдельно.

Если curr->left не NULL, а curr->left->up не NULL, мы знаем, что была предыдущая строка, и мы можем указать curr->up_left, чтобы указать на нее. ->down_right должно указывать на curr, конечно, чтобы ссылки были согласованными.

Если curr->up_left не NULL, а curr->up_left->right не NULL, мы знаем, что в предыдущей строке была буква в том же столбце. Мы можем установить curr->up для указания на него, а ->down для указания на curr.

Если curr->up не NULL, а curr->up->right не NULL, мы знаем, что в предыдущей строке была буква в следующем столбце. Мы можем установить curr->up_right для указания на него, а ->down_left для указания на curr.

Теперь, поскольку мы читаем каждую строку слева направо, все столбцы в каждой строке заполняются до самого правого столбца. Если вы продолжите использовать вышеуказанную логику, вы обнаружите, что вторая строка заполняет остальные ссылки от букв первой строки до букв второй строки и т. Д.

Это также означает, что если входной файл содержит специальный символ, скажем, '*' для небуквенного узла, вы должны создавать их при построении графа, так же, как они были обычными буквами, чтобы обеспечить вышеуказанную логику связывания работы.

После того, как весь граф будет прочитан, вы можете удалить эти не буквенные узлы из графика, один за другим. Чтобы удалить узел, сначала установите обратные ссылки на него (из соседних букв) на NULL, затем free() it.

Я лично «отравляю» структуру перед free() ее введением, устанавливая для letter известное невозможное значение (WEOF для широкого конца ввода) и все ссылки на NULL, так что если какой-то другой код использует структуру после того, как он был освобожден (что будет использовать после свободной ошибки ), например, потому что он как-то кэшировал указатель, его легче обнаружить.

(Когда вы free() указываете, библиотека C обычно не возвращает ее немедленно операционной системе или не очищает ее; обычно динамически выделенная область просто добавляется во внутреннюю свободную кучу, так что в будущем выделение может просто повторно использовать эту память. К сожалению, это означает, что если вы не «отравляете» освобожденные структуры, иногда они все равно могут быть доступны впоследствии. Такие ошибки использования после освобождения очень раздражают, и это определенно стоит «ненужной работы» отравления структур, просто чтобы помочь отладить их.)

Для облегчения отравления, а также для облегчения его устранения, если в какой-то момент оказывается ненужным замедление, лучше всего использовать вспомогательные функции для создания и уничтожения структур:

static inline struct letter *new_letter(const int letter)
{
    struct letter *one;

    one = malloc(sizeof *one);
    if (!one) {
        fprintf(stderr, "new_letter(): Out of memory.\n");
        exit(EXIT_FAILURE);
    }

    one->up_left    = NULL;
    one->up         = NULL;
    one->up_right   = NULL;
    one->left       = NULL;
    one->right      = NULL;
    one->down_left  = NULL;
    one->down       = NULL;
    one->down_right = NULL;

    one->letter = letter;

    return one;
}

static inline void free_letter(struct letter *one)
{
    if (one) {
        one->up_left    = NULL;
        one->up         = NULL;
        one->up_right   = NULL;
        one->left       = NULL;
        one->right      = NULL;
        one->down_left  = NULL;
        one->down       = NULL;
        one->down_right = NULL;
        one->letter     = EOF;
        free(one);
    }
}

Я обычно включаю эти функции в заголовочный файл, который определяет struct letter;поскольку тогда они представляют собой крошечные макроподобные функции, я отмечаю их static inline, говоря компилятору C, что они должны быть доступны только в одном модуле компиляции и что ему не нужно генерировать функции и вызывать эти функции,но может встроенный код, куда бы они ни вызывались.

---

Лично я написал и проверил приведенный выше псевдокод, используя

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

struct letter {
    struct letter  *chain;  /* Internal chain of all known letters */

    struct letter  *up_left;
    struct letter  *up;
    struct letter  *up_right;
    struct letter  *left;
    struct letter  *right;
    struct letter  *down_left;
    struct letter  *down;
    struct letter  *down_right;

    wint_t          letter;
};

static struct letter *all_letters = NULL;

struct letter *new_letter(wint_t letter)
{
    struct letter *one;

    one = malloc(sizeof *one);
    if (!one) {
        fprintf(stderr, "new_letter(): Out of memory.\n");
        exit(EXIT_FAILURE);
    }

    one->letter = letter;

    one->chain = all_letters;
    all_letters = one;

    one->up_left    = NULL;
    one->up         = NULL;
    one->up_right   = NULL;
    one->left       = NULL;
    one->right      = NULL;
    one->down_left  = NULL;
    one->down       = NULL;
    one->down_right = NULL;

    return one;
}

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

    if (!setlocale(LC_ALL, ""))
        fprintf(stderr, "Warning: Current locale is not supported by your C library.\n");
    if (fwide(stdin, 1) < 1)
        fprintf(stderr, "Warning: Wide standard input is not supported by your C library for current locale.\n");
    if (fwide(stdout, 1) < 1)
        fprintf(stderr, "Warning: Wide standard output is not supported by your C library for current locale.\n");

в начале вашего main() и использовать широкие функции ввода / вывода (fwprintf(), fgetwc() и т. Д.), Предполагая, что выиметь стандартную среду C.(Очевидно, у некоторых пользователей Windows есть проблемы с поддержкой UTF-8 в Windows. Пожаловаться на Microsoft; вышеупомянутое поведение соответствует стандарту C.)

Член chain используется, чтобы связать все созданные буквы вединый связанный список, так что мы можем использовать функцию (ниже) для рисования всего графика на языке Graphviz Dot.( Graphviz доступен для всех операционных систем и, на мой взгляд, является отличным инструментом при разработке или отладке кода, использующего связанные списки или графики.) Утилита circo, кажется, неплохо рисует такиеГрафики тоже.

int letter_graph(FILE *out)
{
    struct letter  *one;

    /* Sanity check. */
    if (!out || ferror(out))
        return -1;

    /* Wide output. */
    if (fwide(out) < 1)
        return -1;

    fwprintf(out, L"digraph {\n");
    for (one = all_letters; one != NULL; one = one->chain) {
        fwprintf(out, L"    \"%p\" [ label=\"%lc\" ];\n",
                      (void *)one, one->letter);
        if (one->up_left)
            fwprintf(out, L"    \"%p\" -> \"%p\" [ label=\"↖\" ];\n",
                          (void *)one, (void *)(one->up_left));
        if (one->up)
            fwprintf(out, L"    \"%p\" -> \"%p\" [ label=\"↑\" ];\n",
                          (void *)one, (void *)(one->up));
        if (one->up_right)
            fwprintf(out, L"    \"%p\" -> \"%p\" [ label=\"↗\" ];\n",
                          (void *)one, (void *)(one->up_right));
        if (one->left)
            fwprintf(out, L"    \"%p\" -> \"%p\" [ label=\"←\" ];\n",
                          (void *)one, (void *)(one->left));
        if (one->right)
            fwprintf(out, L"    \"%p\" -> \"%p\" [ label=\"→\" ];\n",
                          (void *)one, (void *)(one->right));
        if (one->down_left)
            fwprintf(out, L"    \"%p\" -> \"%p\" [ label=\"↙\" ];\n",
                          (void *)one, (void *)(one->down_left));
        if (one->down)
            fwprintf(out, L"    \"%p\" -> \"%p\" [ label=\"↓\" ];\n",
                          (void *)one, (void *)(one->down));
        if (one->down_right)
            fwprintf(out, L"    \"%p\" -> \"%p\" [ label=\"↘\" ];\n",
                         (void *)one, (void *)(one->down_right));
    }
    fwprintf(out, L"}\n");

    return 0;
}

Если входной файл

ABC
DEF
GHI

, то точка описания графика будет

digraph {
    "0x1c542f0" [ label="I" ];
    "0x1c542f0" -> "0x1c54170" [ label="↖" ];
    "0x1c542f0" -> "0x1c541d0" [ label="↑" ];
    "0x1c542f0" -> "0x1c54290" [ label="←" ];
    "0x1c54290" [ label="H" ];
    "0x1c54290" -> "0x1c54110" [ label="↖" ];
    "0x1c54290" -> "0x1c54170" [ label="↑" ];
    "0x1c54290" -> "0x1c541d0" [ label="↗" ];
    "0x1c54290" -> "0x1c54230" [ label="←" ];
    "0x1c54290" -> "0x1c542f0" [ label="→" ];
    "0x1c54230" [ label="G" ];
    "0x1c54230" -> "0x1c54110" [ label="↑" ];
    "0x1c54230" -> "0x1c54170" [ label="↗" ];
    "0x1c54230" -> "0x1c54290" [ label="→" ];
    "0x1c541d0" [ label="F" ];
    "0x1c541d0" -> "0x1c54050" [ label="↖" ];
    "0x1c541d0" -> "0x1c540b0" [ label="↑" ];
    "0x1c541d0" -> "0x1c54170" [ label="←" ];
    "0x1c541d0" -> "0x1c54290" [ label="↙" ];
    "0x1c541d0" -> "0x1c542f0" [ label="↓" ];
    "0x1c54170" [ label="E" ];
    "0x1c54170" -> "0x1c53ff0" [ label="↖" ];
    "0x1c54170" -> "0x1c54050" [ label="↑" ];
    "0x1c54170" -> "0x1c540b0" [ label="↗" ];
    "0x1c54170" -> "0x1c54110" [ label="←" ];
    "0x1c54170" -> "0x1c541d0" [ label="→" ];
    "0x1c54170" -> "0x1c54230" [ label="↙" ];
    "0x1c54170" -> "0x1c54290" [ label="↓" ];
    "0x1c54170" -> "0x1c542f0" [ label="↘" ];
    "0x1c54110" [ label="D" ];
    "0x1c54110" -> "0x1c53ff0" [ label="↑" ];
    "0x1c54110" -> "0x1c54050" [ label="↗" ];
    "0x1c54110" -> "0x1c54170" [ label="→" ];
    "0x1c54110" -> "0x1c54230" [ label="↓" ];
    "0x1c54110" -> "0x1c54290" [ label="↘" ];
    "0x1c540b0" [ label="C" ];
    "0x1c540b0" -> "0x1c54050" [ label="←" ];
    "0x1c540b0" -> "0x1c54170" [ label="↙" ];
    "0x1c540b0" -> "0x1c541d0" [ label="↓" ];
    "0x1c54050" [ label="B" ];
    "0x1c54050" -> "0x1c53ff0" [ label="←" ];
    "0x1c54050" -> "0x1c540b0" [ label="→" ];
    "0x1c54050" -> "0x1c54110" [ label="↙" ];
    "0x1c54050" -> "0x1c54170" [ label="↓" ];
    "0x1c54050" -> "0x1c541d0" [ label="↘" ];
    "0x1c53ff0" [ label="A" ];
    "0x1c53ff0" -> "0x1c54050" [ label="→" ];
    "0x1c53ff0" -> "0x1c54110" [ label="↓" ];
    "0x1c53ff0" -> "0x1c54170" [ label="↘" ];
}

(Это в обратном порядке, потому чтоЯ вставляю каждое новое письмо в начале связанного списка).circo рисует следующий график из этого:

Во время разработки я также проверяю, является ли связь согласованной:

    for (one = all_letters; one != NULL; one = one->chain) {

        if (one->up_left && one->up_left->down_right != one)
            fprintf(stderr, "'%c'->up_left is broken!\n", one->letter);
        if (one->up && one->up->down != one)
            fprintf(stderr, "'%c'->up is broken!\n", one->letter);
        if (one->up_right && one->up_right->down_left != one)
            fprintf(stderr, "'%c'->up_right is broken!\n", one->letter);
        if (one->left && one->left->right != one)
            fprintf(stderr, "'%c'->left is broken!\n", one->letter);
        if (one->right && one->right->left != one)
            fprintf(stderr, "'%c'->right is broken!\n", one->letter);
        if (one->down_left && one->down_left->up_right != one)
            fprintf(stderr, "'%c'->down_left is broken!\n", one->letter);
        if (one->down && one->down->up != one)
            fprintf(stderr, "'%c'->down is broken!\n", one->letter);
        if (one->down_right && one->down_right->up_left != one)
            fprintf(stderr, "'%c'->down_right is broken!\n", one->letter);
    }

По согласованной связи,Я имею в виду, что если a->left == b, то b->right == a.Конечно, проверка не может определить, является ли a->left или b->right неправильным;он может только определить, соответствуют ли они или нет.