dynamiczne dodawanie komórek do tabeli

Hej,

Przy dynamicznym tworzeniu tabeli możemy utworzyć tabelę o rozmiarze, który jest zmienną. Ja mam jednak potrzebę dodawać w określonym momencie kolejną kolumnę - nie wiem ile ich będzie aż do zakończenia pracy programu. Konkretnie kwestia jest taka:

Mam dowolny ciąg znaków wczytywany z klawiatury. Potrzebuję tabelę dwuwymiarową, która będzie przechowywać liczbę konkretnych znaków. Np. dla ciągu: abacdabd będzie wyglądać tak:

a|b|c|d|
3|2|1|2|

Chcę sprawdzać każdy znak po kolei - jeśli już się pojawił to tylko zwiększać liczbę, jeśli nie, to dodawać nową kolumnę. Wydaje mi się, że w ten sposób będzie to najbardziej optymalne i pamięciowo i czasowo.

Pytanie zatem brzmi: po pierwsze czy mam rację co do wydajności, a po drugie: jak to zrobić? ;)

Dziękuję z góry za pomoc!
Mal

Coś znalazłam dlatego doprecyzuje swoje pytanie. Znalazłam funkcje calloc i realloc. Ale nie do końca rozumiem jak się ich używa. Czy to mogłoby być coś w tym stylu:

tab = calloc (1, sizeof(char));
if(znak sie nie powtarza)
    realloc(tab, sizeof(char));

Jestem dość początkująca, dlatego zanim uda mi się napisać ten kod tak, żeby go sprawdzić, to Wy zapewne po pierwszym rzucie oka będziecie w stanie powiedzieć czy to w ogóle ma szanse powodzenia ;)

Dziękuję Wam z góry jeszcze raz.
Mal

Rozmiar tablicy trzeba trzymać osobno, a ten realloc musiałby dostać jako rozmiar sizeof(char) * nowy_rozmiar.

Przy okazji, sizeof(char) ma gwarantowaną wartość 1.

Dla lepszej wydajności zazwyczaj nie zwiększa się tablicy o jeden element, tylko aż dwukrotnie — za to tylko wtedy, gdy brakuje już miejsca. Wtedy musisz trzymać dwa „rozmiary”: ilość elemetów w tablicy, i rozmiar zaalokowanej tablicy.
Gdy brakuje miejsca, realokujesz tablicę by była dwa razy większa niż dotychczas.

Możesz też zacząć od jakiegoś rozmiaru alokowanego na początku większego niż 1 element (na przykład 16).

Dziękuję ślicznie.

Chciałam dodać punkcik, ale jestem niezarejestrowana. Obiecuję ten błąd naprawić. Dziękuję jeszcze raz za wskazówki.

Pozdrawiam
Mal

No cóż, jednak nie poszło tak prosto jak myślałam. Więc zwracam się z prośbą jeszcze raz. Zadanie jest cały czas to samo. Na razie postanowiłam robić to jeszcze "komórka po komórce" - optymalizacją zajmę się jak już zrozumiem jak to powinno działać.

Deklaruję dwie tablice:

char* znaki;		//tablica ze znakami
	znaki = (char*) calloc(1, 1);
	int* il;			//tabela okreslajaca liczbe konkretnych znakow
	il = (int*) calloc(1, sizeof(int));
	wtab = 0;           //wielkosc tablic - 1 

W funkcji dopisz() sprawdzam, czy dany znak x już jest w tabeli - jeśli tak, to zwiększam jego liczbę, jeśli nie - to chcę dodać komórkę i tam go zapisać:

void dopisz(char x, char* tabzn, int* ilezn)
{

	bool temp = false;
	for (int i = 0; i<wtab+1; i++)
	{
		if (tabzn[i] == x)
		{
			ilezn[i]++;
			temp = true;
			break;
		}
	}
	if (temp == false)
	{
		wtab++;
		realloc(tabzn, wtab*sizeof(char));
		realloc(ilezn, wtab*sizeof(int));
		tabzn[wtab] = x;
		ilezn[wtab] = 1;
	}

}

Przy drugim przejściu pętli for na drugim realloc wywala mi błąd Windows has triggered a breakpoint in file.exe. This may be due to a corruption of the heap, and indicates a bug in file.exe or any of the DLLs it has loaded.

Możecie mi podpowiedzieć co robię nie tak?

Pozdrawiam,
Mal

wtab = 0; //wielkosc tablic - 1

dlaczego "-1"? z tego wynika twój dalszy błąd. zrób tak, żeby to była rzeczywista wielkość tablicy, a nie jakieś „minus jeden”.

struck literki_i_cyferki{
    unsigned int iLiczbaLiterek;
    unsigned char cZnakLiterki;
} *tablicaZnaczkow

na poczatku mozna zalozyc że ( bedzie to zajmowac, u mnie przynajmniej, 480 bajtow , noo i miejsce na wskaznik :] )

tablicaZnacznikow = (literki_i_cyferki ) malloc( 24sizeof( literki_i_cyferki));
24 bo mozna zalozyc ze pojawi sie caly alfabet :]
34 jezeli dodali bysmy cyfry :]

i odwolywal sie poprzez kod ascii danego znaku
np. od 65 mamy A, czyli jezeli

int iSize = 24;
int iIndeksDoOstatniegoElementuTablicy = iSize; // to bedzie pokazyawc gdzie ejst ostatni element zajety

int numerLiterki;
if ( ((unsigned int ) znak > 65 ) && ( (unsigned int ) znak < 89 ){ // 24  + 65, ale nie wiem czy na bank to bedzie 89 bo nie wiem ile znakow jest w tablicy ascii 
         numerLiterki = ((unsigned int ) - 65 ) ; // dla literki a bedzie to 0 dla b= 1 dla , c = 2 itd.
         tablicaZnacznikow[ numerLiterki].iLiczbaLiterek++;   
        }
else if ((unsigned int ) znak > 97 ) &&& (( unsigned int ) znak < 121 ) {// zakresy dla malych znakow;
         numerLiterki = ((unsigned int) - 97 );
         tablicaZnacznikow[ numerLiterki].iLiczbaLiterek++;
}

i tak samo dla liczb.

natomiast dopiero jezeli pojawi sie cos czego nie ma w tablicy to dodac .... 5 elementow do tablicy i do tego dopisac i szukac ponad zakresem tablicy :]

idac dalej

else {
     if( iSize < iIndeksDoOstatniegoElementuTablicy ){
               iSize = iSize + 5;     // mowimy ze bedzie teraz wieksza tablica ( cala tablica zajete i nie zajete komorki )
               numerLiterki = realloc( numerLiterki , iSize * sizeof( literki_i_cyferki ) ;   // 
    }
     for( int iLicznikTablicy = 24 ; iLicznikTablicy < iIndeksDoOstatniegoElementuTablicy ; iLicznikTablicy++){   // lecimy od 24 bo pomija sie wtedy znaki alfabetu ktore znamy 
             if ( tablicaZnacznikow[ iLiczniktablicy].cZnakLiterki == znak ){
                          tablicaZnacznikow[ iLiczniktablicy].iLiczbaLiterek++;
                        break;       
                        }
             if ( iLicznikTablicy + 1 < iIndeksDoOstatniegoElementuTablicy) // dochodzimy do wniosku ze jednak znaku nie ma ejszcze w tablicy i trzeba go dodac.
                  tablicaZnacznikow[ iLicznikTablicy + 1].cZnakLiterki = znak;
                  tablicaZnacznikow[ iLicznikTablicy +1].iLiczbaLiterek++;
}
   

no i tak ze wszsytkimi znakami :]

indeksy
iIndeksDoOstatniegoElementuTablicy
oraz
iLicznikTablicy i iSize
moga sie troche rozjezdzac ( o 1 wartosc , zdaza mi sie tak napisac cos czasem, ... )

wazne
pamietaj ze za kazdym razem kiedy allokujesz pamiec mowisz systemowi ze bedziesz jej uzywac :].
jezeli nadpiszesz sobie wskaznik do zaalokowanej pamieci
wskaznik = malloc ( rozmiar );
to stracisz moliwosc dostepu do pamieci ( sie to memory leak nazywa );
dopiero po zamknieciu programu pamiec moze zostac zwrocona do systemu ( chociaz pewnie mozliwe jest zeby nie zostala zwrocona :] ).

wiec pamietaj zeby stosowac free :]
czyli
free( wskaznik_do_juz_nie_potrzebnej_pamieci);

[edit 1] dodanie info o free();
[edit 2] literowka :]
[edit 3] znazniki cpp
[edit 4] ten koment
[edit 5] znaniki dla struktury
[edit 6 ] przepraszam za literowki, wszedlem na forum na chwile zeby zobaczyc czy ktos odpowiedzial na mojego posta ( no i od razu zajrzalem do tematu ), a jako ze istnieje skoczone prawdopodobienstwo ze posiadasz pewne kraglosci na klatce piesiowej postanowilem sie podlizac i strzelic odpowiedz.
[edit 7] urozmaicenie tematu o odrobinę dorbiu
[edit 8] nie wiem czemu na podgladzie kurczak dziala, a na forum sie nie wyswietla ;/

Temat był dawno, ja miałam sporo zajęć ale wróciłam :P No i piszę tu mało merytorycznego posta, bo mi się głupio zrobiło, że Wy tacy pomocni jesteście, a ja tu nie zajrzałam i nie podziękowałam. Tak więc:

Dzięki wszystkim za odpowiedzi i podpowiedzi, wcielę w życie i zobaczę co wyjdzie. Pewnie też jeszcze nie raz tu zajrzę zresztą. Rozwiązanie ze strukturą mi się podoba, ale w ramach treningu wrzucę to od razu w klasę. Kurczak jest bomba, dzięki za życzenia - z tym, że to nie na zalkę. Studia już skończyłam, teraz sama kodzę odrobinkę coby się dokształcić :P Za podlizywanie się dziękuję równie gorąco co za pomoc :)

Dziękuję jeszcze raz i do "poczytania" znowu zapewne.

Mal