-2

Preciso fazer um trabalho na linguagem C onde a entrada é a quantidade de vértices de um grafo na primeira linha e para cada vértice é listado os nós adjacentes de cada vértice em cada linha, separando cada vértice Adjacente por “;”. E a última linha especifica o tipo de representação dos grafos desejado pelo usuário, que pode ser: 1: coleção de listas de adjacências ou 2: matriz de adjacências.

Exemplos:

8

a: b;

b: c; e; f;

c: d; g;

d: c; h;

e: a; f;

f: g;

g: f; h;

h: h;

2

ou

9

undershorts: pants; shoes;

pants: belt; shoes;

belt: jacket;

shirt: belt; tie;

tie: jacket;

jacket:

socks: shoes;

shoes:

watch:

1

Eu já tenho funções para adicionar vértices e arestas ao meu grafo, mas estou com dificuldade para ler essa entrada e armazenar o conteúdo dela em variáveis que eu possa usar nas funções, minhas principais dificuldades são:

1-Como separar o que é um novo vértice do que é uma nova aresta. Imagino que eu precise comparar o último caractere da string com ':' ou ';', mas como eu identifico esse último caractere se as entradas possuem tamanhos diferentes?

2-Como fazer um laço que leia todos esses vértices e arestas, mas pare antes da última linha que indica o tipo de representação do grafo ou então sirva também para tratar essa linha?

1
  • 1 - Leia de byte em byte. cria um buffer, e vai escrevendo nele até achar um : ou ; e então ja tem a resposta pra tudo aquilo que está no buffer. 2 - A primeira vez que ler é o quantidade de linhas seguintes que irá ler, dpoeis de ler toda as linhas (Que você ja sabe a quantidade, foi informado antes), só voltar a ler o numero (e que ao ler, volta a ler as linhas, como no mencionei antes).
    – Inkeliz
    22/05/2022 às 20:13

1 Resposta 1

-2

Como separar o que é um novo vértice do que é uma nova aresta. Imagino que eu precise comparar o último caractere da string com ':' ou ';', mas como eu identifico esse último caractere se as entradas possuem tamanhos diferentes?

A julgar pelos arquivos que mostrou o vértice é o primeiro campo de cada linha e as arestas vem a seguir. Sabe que terminou a lista de arestas quando a linha acaba

Como fazer um laço que leia todos esses vértices e arestas, mas pare antes da última linha que indica o tipo de representação do grafo ou então sirva também para tratar essa linha?

A primeira linha do arquivo não diz exatamente isso? São 2+n linhas onde a primeira linha diz o valor de n. Seu primeiro exemplo tem 10 linhas para 8 vértices. O segundo tem 11 linhas...

Exemplos em C

Duas maneiras comuns de fazer isso em C:

  • usar scanf() que foi escrita para consumir esse tipo de dado
  • usar uma maquina de estados e ler letra a letra.

[1] usando scanf()

As arestas vem linha a linha, e os delimitadores podem ser : ou ; ou um '\n' então para scanf() se pode usar

    char mascara[] = "%[^\n;:]%c";

como especificadores para consumir os dados: o primeiro especificador %[^\n;:] consome o campo e o segundo consome o caracter que encerrou o campo. Nada mais. Lembrando que o ^ na primeira posição inverte a condição, de modo a aceitar tudo exceto os 3 símbolos que vem a seguir.

2 problemas:

  • seria mais simples garantir que as linhas não terminem por ; e apenas com '\n' para não ter que tratar os dois casos
  • espaços em branco no arquivo são um inferno e vão parar dentro das strings

Deixei as duas opções nos arquivos para testar, como pode ver acima.

[1] o exemplo usando scanf()

main.c

#include <stdio.h>
#include <string.h>

void trim(char*);

int  main(int argc, char** argv)
{
    const char* tipo[] = {
        "matriz de adjacencia", "listas de adjacencia"};
    char mascara[] = "%[^\n;:]%c";
    char campo[4096], delim[4];
    int  n = 0;
    int campos = 0;
    delim[0]           = 'x';
    const char* padrao = "f2.txt";
    char arquivo[132];
    strcpy(arquivo, padrao);
    if (argc > 1) strcpy(arquivo, argv[1]);
    FILE* ent = fopen(padrao, "r");
    char* p = fgets(campo, sizeof(campo), ent);
    if (p == NULL)
    { 
        fclose(ent);
        return - 1;
    }
    int n_vert = atoi(campo);
    if (n_vert <= 0)
    {
        fclose(ent);
        return -2;
    }
    printf("%d Vertices\n\nArestas:\n", n_vert);
    while (n_vert>0)
    {
        n = fscanf(ent,mascara,campo,delim);
        if (n < 1)
        {
            fgetc(ent);
            --n_vert;
            continue;
        }
        trim(campo);
        switch (delim[0])
        {
            case '\n':
                // terminou uma linha
                printf("  [%s]", campo);
                --n_vert;
                break;
            case ':':
                // novo label
                printf("\n\t[%s]:  ", campo);
                break;
            case ';':
                // nova aresta
                printf("\t[%s]", campo);
                break;
            default:
                // algo errado
                printf(
                    "\nErro! Delimitador = %d\n", delim[0]);
                break;
        };  // switch()
        campos += 1;
    };
    p = fgets(campo, sizeof(campo), ent);
    if (p == NULL)
    {
        fclose(ent);
        return -3;
    }
    n_vert = atoi(campo);
    if (n_vert <= 0)
    {
        fclose(ent);
        return -4;
    }
    printf("\n\nRepresentacao: %s\n", tipo[n_vert!=2]);
    fclose(ent);
    return 0;
};

void trim(char* str)
{   // elimina os espacos de str
    size_t n = strlen(str);
    size_t br = 0;
    char*  pin = str;
    char*  pout = str;
    while (*pin != 0)
    {   if (*pin == ' ') br++;
        else
        {   if (pin != pout) *pout = *pin;
            ++pout;
        }
        ++pin;
    };
    *(str + n - br) = 0;
    return;
};

[2] exemplo usando uma máquina de estados

Aqui não precisa de trim() porque a própria máquina pode eliminar os espaços. A lógica é a mesma e os estados são auto-explicativos: procura os vértices, depois as arestas até terminar

o código do segundo exemplo

// os estados da maquina
#define ARE_ 3
#define ERR_ 2
#define PRE_ 1
// o fim de linha
#define EOL '\n'

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

int main(int argc, char** argv)
{
    char        st_    = PRE_; // o esado
    const char* tipo[] = {
        "matriz de adjacencia", "listas de adjacencia"};
    char        campo[512];
    const char* padrao = "f2.txt";
    char        arquivo[132];
    // trata o parametro nome do arquivo
    strcpy(arquivo, padrao);
    if (argc > 1) strcpy(arquivo, argv[1]);
    FILE* ent = fopen(arquivo, "r");
    char* p   = fgets(campo, sizeof(campo), ent);
    if (p == NULL)
    {
        fclose(ent);
        return -1;
    }
    // identifica o n. de vertices
    int n_vert = atoi(campo);
    if (n_vert <= 0)
    {
        fclose(ent);
        return -2;
    }
    printf("%d Vertices\n\nArestas:\n", n_vert);
    // tenta ler os vertices e arestas
    int c = fgetc(ent);
    if (feof(ent))
    {
        fclose(ent);
        return -3;  // arquivo vazio
    }
    while (n_vert > 0)
    {
        switch (st_)
        {
            case ARE_: // lendo arestas
                switch (c)
                {
                    case ':':
                        st_ = ERR_;
                        break;
                    case ' ':
                    case '\t':
                        break;
                    case ';':
                        *p = 0;  // termina string
                        // nova aresta
                        printf("\t[%s]", campo);
                        p = campo;  // reinicia
                        break;
                    case EOL:    // fim da linha
                        *p = 0;  // termina string
                        if (p[0] != 0)
                            printf("\t[%s]\n", campo);
                        p   = campo;  // reinicia
                        st_ = PRE_;
                        n_vert -= 1; // achou mais um
                        break;

                    default:
                        *p++ = (char)c;
                        break;
                }
                break;

            case PRE_:
                switch (c)
                {
                    case ':':
                        *p = 0;  // termina string
                        // novo label
                        printf("\n\t[%s]:  ", campo);
                        st_ = ARE_;   // busca arestas
                        p   = campo;  // reset
                        break;
                    case ' ':
                    case '\t':
                        break;
                    case ';':
                        st_ = ERR_;
                        break;
                    default:
                        *p++ = (char)c;
                        break;
                }
                break;
            case ERR_:
                fprintf(
                    stderr, "\n\tErro no arquivo %s\n",
                    arquivo);
                fclose(ent);
                return -4;
                break;
            default:
                break;
        };  // switch()
        c = fgetc(ent);
        if ((feof(ent)) && (n_vert != 0))
        {
            fprintf(
                stderr, "\n\tErro no arquivo %s\n",
                arquivo);
            fclose(ent);
            return -4;
        }
    };  // while()
    // sai do loop com o criterio lido
    // 1 = listas de adjacencia
    printf("\n\nRepresentacao: %s\n", tipo[(c=='1')]);
    fclose(ent);
    return 0;
};

A saída dos dois programas é, claro, a mesma

Os programas esperam o nome do arquivo como parâmetro. Na falta deles um valor padrão é assumido.

Considere os arquivos

f1.txt

8
a:b;
b:  c ;e ;f 
c:d;g;
d:c;h
e:a;f;
f:g
g:f;h;
h:h
2

f2.txt

9
undershorts: pants; shoes;
pants: belt; shoes;
belt: jacket;
shirt: belt; tie;
tie: jacket;
jacket:
socks: shoes;
shoes:
watch:
1

saída dos 2 programas


PS C:\so> .\teste f1.txt
8 Vertices

Arestas:

        [a]:    [b]
        [b]:    [c]     [e]  [f]
        [c]:    [d]     [g]
        [d]:    [c]  [h]
        [e]:    [a]     [f]
        [f]:    [g]
        [g]:    [f]     [h]
        [h]:    [h]

Representacao: matriz de adjacencia
PS C:\so> .\teste f2.txt
9 Vertices

Arestas:

        [undershorts]:          [pants] [shoes]
        [pants]:        [belt]  [shoes]
        [belt]:         [jacket]
        [shirt]:        [belt]  [tie]
        [tie]:          [jacket]
        [jacket]:
        [socks]:        [shoes]
        [shoes]:
        [watch]:

Representacao: listas de adjacencia

e deve servir como exemplo para casos como esse. A função trim() existe para remover eventuais espaços DENTRO dos campos no arquivo, como é o caso do exemplo que o autor postou. Sem isso as arestas poderiam ter nomes diferentes a cada vez, em existindo espaços no arquivo de entrada. Um inferno. O exemplo aceita campos terminados por ; ou por '\n'.

usando isso em um programa

Ao invés de mostrar os vértices e arestas como o exemplo apenas insira os valores na lista de vértices e as arestas na matriz ou nas listas conforme o caso. É claro que seria mais esperto se a opção que define como vai armazenar as arestas viesse antes da leitura... Do modo como está vai precisar de algo intermediário.

4
  • Ah o SO pt... Então uma resposta que discute o problema, mostra como tratar os dados e tem exemplos em C com a saída anexada é então inútil... E aquela recomendação do próprio SO para que se comente como uma resposta inútil como a que escrevi se torne razoável ao menos, no nível que o site merece?
    – arfneto
    24/05/2022 às 15:50
  • Obrigada pela resposta, não foi inútil e me ajudou a resolver meu problema, infelizmente entrei aqui recentemente e não tenho reputação o suficiente para dar upvote
    – Laura PS
    25/05/2022 às 13:40
  • :) bom que ajudou em algo. Comentei apenas porque em geral assim que eu escrevo algo vem 1 ou 2 desses votos e comecei a comentar ao final. É algo pessoal, não deve ter a ver com as respostas em si. E agora eu copio esse comentário de uma questão para outra
    – arfneto
    25/05/2022 às 13:55
  • Então 2 usuários acharam inútil o que eu escrevi, apesar do autor da pergunta dizer que tal resposta foi útil e de ter 2 exemplos completos e uma discussão do problema. Preciso melhorar ;) as respostas
    – arfneto
    13/06/2022 às 18:51

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .