Pisownia
Temat: [C++] Tworzenie tablicy dwuwymiarowej (komentarz)

----------------------------------------------



Post dotyczy tego posta w CUO.



W po?cie jest napisane, ?e przy korzystaniu z metody z alokacj? ci?g?ego obszaru pami?ci trudniej jest tworzy? tablice dwuwymiarowe o nietypowych kszta?tach. Wbrew pozorom w wi?kszo?ci przypadków tak nie jest. Je?eli mamy kod alokuj?cy wiersze ró?nej d?ugo?ci metod? alokacji ka?dego wiersza oddzielnie, to bez problemu zwykle mo?na to prze?o?y? bezpo?rednio na wersj? z pojedyncz? alokacj?. Schemat jest prosty. Rozmiar wymaganego obszaru ci?g?ego jest równy sumie d?ugo?ci wszystkich wierszy. Oprócz tego musimy wiedzie?, gdzie zaczyna si? ka?dy z wierszy w zaalokowanym obszarze. Nietrudno si? domy?li?, ?e przesuni?cie jest sum? d?ugo?ci wszystkich poprzednich wierszy.



Dla osób lubi?cych wzorki:

Przy za?o?eniu, ?e jest n oraz s(i) oznacza rozmiar i-tego wiersza:

Rozmiar alokowanego obszaru

[tex:bc00a4de92]size=\sum_{i=1}^n{s(i)}[/tex:bc00a4de92]

Przesuni?cie dla k-tego wiersza

[tex:bc00a4de92]offset(k)=\sum_{i=1}^k{s(i)}[/tex:bc00a4de92]

Przek?adaj?c te wzorki bezpo?rednio na kod: Oczywi?cie jest to niewydajne (linia 8: ci?g?e przeliczanie tego samego) i mo?na to zapisa? przynajmniej tak: W wi?kszo?ci przypadków mo?na (nawet wypada) napisa? to optymalniej, zast?puj?c wyra?enie s[n] lub sum? s[n] innymi, prostszymi wyra?eniami. Np. dla tablicy prostok?tnej suma s[n] to po prostu iloczyn d?ugo?ci wiersza i indeksu aktualnego wiersza: Dla tablicy trójk?tnej s[i] mo?na zast?pi? po prostu i. D?ugo?ci wierszy tworz? ci?g arytmetyczny, wi?c nietrudno równie? zauwa?y?, jak policzy? sum? d?ugo?ci wierszy. Itd.

Dodaj do słownika