Matrius esparses (2): transposició

Tal com vam veure al problema Matrius esparses (1): conversió, una
matriu esparsa només emmagatzema els elements no nuls. Els tipus usats
(definits a matrius.hh) són els mateixos:

    struct Casella {
        int pos;    // índex de columna
        int valor;  // valor de l'element
    };

    struct MatriuEsparsa {
        int ncols;                   // nombre de columnes
        vector<list<Casella>> files; // files de la matriu esparsa
    };

La transposada d’una matriu n × m és la matriu m × n que s’obté
intercanviant files i columnes: l’element a la posició (i, j) de
l’original passa a la posició (j, i) de la transposada.

Fes la funció següent:

    /**
     * @brief Calcula la transposada d'una MatriuEsparsa.
     *
     * @param S MatriuEsparsa de S.files.size() files i S.ncols columnes.
     *
     * @pre S és una MatriuEsparsa vàlida. Les posicions de les caselles van de 0 a S.ncols-1.
     * @post Retorna una nova MatriuEsparsa T amb T.ncols == S.files.size() i
     *       T.files.size() == S.ncols, on T.files[j] conté les caselles
     *       {i, S.files[i][j].valor} de S, ordenades per columna ascendentment.
     */
    MatriuEsparsa matriu_esparsa_transposa(const MatriuEsparsa& S);

Observació

Els fitxers públics (icona del gatet) contenen:

  ------------ ----------------------------------------------------
  main.cc      el programa principal, amb la entrada/sortida feta
  matrius.hh   els tipus Casella i MatriuEsparsa
  Makefile     per compilar amb make còmodament
  .vscode      carpeta per compilar i depurar amb VSCode
  ------------ ----------------------------------------------------

Cal enviar únicament la implementació de la funció
matriu_esparsa_transposa, incloent-hi l’include de matrius.hh. No cal
enviar el main.

Entrada

La primera línia conté dos enters n i m (0 ≤ n, m ≤ 1000), el nombre de
files i columnes de la matriu esparsa d’entrada. A continuació hi ha n
línies, cadascuna amb les caselles no nul·les de la fila com a parelles
(col,val) separades per espais, seguides d’un punt .. Les files sense
elements no nuls es representen com ..

Sortida

La matriu esparsa transposada en el mateix format que l’entrada: la
primera línia conté les dimensions m × n de la transposada, seguida de m
línies amb les caselles no nul·les de cada fila, seguides d’un punt ..

Informació del problema

Autoria: Pau Fernández

Generació: 2026-02-25T09:47:57.694Z

© Jutge.org, 2006–2026.
https://jutge.org
