Dynamiczna tablica dwuwymiarowa i rekurencja

Odpowiedz Nowy wątek
2011-10-15 11:54
0

Witam,
mam taki problem: chcę napisać program, który by mi tworzył dwuwymiarową tablicę n*n i uzupełniał ją po kolei "po spirali", tzn. dla n = 4 ma być takie coś:

 1  2  3  4
12 13 14  5
11 16 15  6
10  9  8  7

Wiem oczywiście, że można to zrobić na miliard sposobów, ale ja chcę to akurat (w ramach ćwiczenia języka) zrobić rekurencyjnie, poprzez manipulację wskaźnikami.
Naskrobałem takie cuś:

#include <iostream>

using namespace std;

void
fill_matrix(int _index, int _max, int _size, int** _matrix) {
    int i = 0, j = 0;

    if (_index + 1 == _max) {
        _matrix[0][0] = _index + 1;
        return;
    }

    for (; i < _size - 1; i++)
        _matrix[0][i] = ++_index;
    for (; j < _size - 1; j++)
        _matrix[j][i] = ++_index;
    for (; i > 0; i--)
        _matrix[j][i] = ++_index;
    for (; j > 0; j--)
        _matrix[j][0] = ++_index;

    if (_index < _max)
        fill_matrix(_index, _max, _size - 2, &(&_matrix[1])[1]);
}

int **
create_matrix(int _n) {
    int** tablica = new int*[_n];
    for (int i = 0; i < _n; i++)
        tablica[i] = new int[_n];

    fill_matrix(0, _n * _n, _n, tablica);

    return tablica;
}

void
remove_matrix(int** _matrix, int _n) {
    for (int i = 0; i < _n; i++)
        delete[] _matrix[i];
    delete[] _matrix;
}

int
main() {
    const int n = 4;
    int** tablica = create_matrix(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << (tablica[i][j] < 10 ? " " : "") << tablica[i][j] << " ";
        cout << endl;
    }

    remove_matrix(tablica, n);

    return 0;
}

Widzicie mój zamysł - każde kolejne wywołanie rekurencji ma dostawać tablicę o jeden rząd i jeden wiersz mniejszą. Tyle, że zamiast tego dostaję tablicę mniejszą o dwa wiersze i zero rzędów. W skrócie, dostaję takie coś:

 1  2  3  4 
12  0  0  5 
13 14  0  6 
16 15  8  7 

Jak temu zaradzić? Jak dostać wskaźnik int** na pozycję [1][1]?

Z góry dziękuję za odpowiedź i pozdrawiam.

edytowany 1x, ostatnio: Garrappachc, 2011-10-15 11:54

Pozostało 580 znaków

2011-10-15 13:00
0

nie da się tak, zrób to na indeksach a nie na wskaźnikach:
void fill_matrix(int** matrix, int start_index, int xa, int xb, int ya, int yb);

i wywołaj:
fill_matrix(matrix,0,0,szerokosc,0,wysokosc);

zauwaz ze xb i yb pokazują zawsze element tablicy oddalony o 1 dalej (dużo łatwiej napisać kod)

EDIT:
ewentualnie możesz zrobić inną strukturę tablicy: jako rząd uznaj pierwszą kolumnę wraz z pierwszym wierszem, a jako kolumnę tablicę wierszy o coraz mniejszym rozmiarze (zmniejszającym się o 2)


░█░█░█░█░█░█░█░█░█░█░█░
edytowany 1x, ostatnio: krwq, 2011-10-15 13:02

Pozostało 580 znaków

2011-10-15 13:27
0

A dlaczego się nie da tak? Gdzieś widziałem kod obliczania wyznacznika macierzy, rekurencyjnie, właśnie w ten sposób. Chciałem uniknąć właśnie podawania po kolei indeksów startowych przy każdym wywołaniu.

Pozostało 580 znaków

2011-10-15 14:00
0

nie da się dlatego, że matrix** jest tablicą wskaźników na pierwsze elementy kolumn, co oznacza że musiałbyś skopiować całą tablicę tych wskaźników i przesunąć te wskaźniki o 1, co jest bezsensowne. Lepiej zapisać offset względem wskaźnika do pierwszego elementu czyli indeks.


░█░█░█░█░█░█░█░█░█░█░█░
Nie wiem, o co Ci chodzi? Program, który napisałem działa poprawnie dla indeksów jak i dla przesuwania wskaźnika. - MJay 2011-10-17 16:24
zobacz post niżej - krwq 2011-10-17 20:12

Pozostało 580 znaków

2011-10-15 14:06
1

Oczywiście, że można tylko należy samemu zarządzać pamięcią. Jest to bardzo eleganckie programowanie, aczkolwiek trzeba wszystko przewidywać. Napisałem przykładowy program który pomoże Ci to zrozumieć:

#include <iostream>
using namespace std;

int main()
{
    int *zarezerwowany_obszar = new int[16];

    int **tab = new(zarezerwowany_obszar) int*[4];

    for(int i = 0; i < 4; ++i)
        tab[i] = new(zarezerwowany_obszar + i * 4) int[4];

    for(int i = 0; i < 4; ++i)
        for(int j = 0; j < 4; ++j)
            cout << &tab[i][j] << "\n";

    cout << "\n";

    for(int i = 0; i < 16; ++i)
        cout << (tab + i) << "\n";

    getchar();
    delete [] zarezerwowany_obszar;
    return 0;
}

Gdy się nie wie, co się robi, to dzieją się takie rzeczy, że się nie wie, co się dzieje ;-)

Pozostało 580 znaków

2011-10-15 19:40
0

Dobra jest, trochę z tym pokombinowałem i działa :)
Dzięki @Mjay za podpowiedź ;)

Pozostało 580 znaków

2011-10-17 20:12
0

To co napisał MJay nie ma prawa działać - odkomentuj sobie zerowanie tablicy - wraz z wyzerowaniem elementów wyzerują się również wskaźniki i wyskoczy piękny AV

#include <iostream>
using namespace std;

int main()
{
  int *zarezerwowany_obszar = new int[16];

  int **tab = new(zarezerwowany_obszar) int*[4];

  for(int i = 0; i < 4; ++i)
    tab[i] = new(zarezerwowany_obszar + i * 4) int[4];

  for(int i = 0; i < 4; ++i)
    for(int j = 0; j < 4; ++j)
      cout << &tab[i][j] << " = " << tab[i][j] << "\n";

  cout << "\n";

  /* zerujemy tablice */
  /*for(int i = 0; i < 4; ++i)
    for(int j = 0; j < 4; ++j)
      tab[i][j] = 0;

  cout << "\n";*/

  for(int i = 0; i < 4; ++i)
    for(int j = 0; j < 4; ++j)
      cout << &tab[i][j] << " = " << tab[i][j] << "\n";

  cout << "\n";

  for(int i = 0; i < 16; ++i)
    cout << (tab + i) << " = " << *(tab + i) << "\n";

  getchar();
  delete [] zarezerwowany_obszar;
  return 0;
}

░█░█░█░█░█░█░█░█░█░█░█░
edytowany 1x, ostatnio: krwq, 2011-10-17 22:38

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0