C/Napisy - własna implementacja

Własna implementacja

Ponieważ tablice znaków mają ograniczenia, możemy zaimplementować łańcuch typu linked list.

Typ danych

Typ zdefiniujemy jako klasę.

typedef struct _string
{
    /* aktualny znak */
    char c;
    /* następny znak */
    struct _string *next;
} *string;

Zauważmy, że łańcuch automatycznie oznaczamy jako wskaźnik. W ten sposób zabezpieczamy się przed kopiowaniami.

Metody

Na początek zajmiemy się wypisywaniem łańcucha:

typedef struct _string
{
    FILE *(*wypisz)(FILE*); /* wskaźnik na metodę */
} *string;
FILE *wypisz_str(FILE *strum) /* metoda */
{
   string wsk = str;
   for(;wsk != NULL;wsk = wsk->next) /* pętla po znakach */
   fputc(strum, wsk->c); /* wypisz znak */
}

Teraz zajmijmy się przypisaniem:

typedef struct _string
{   char c;
    struct _string *next;
    FILE *(*wypisz)(FILE*);
    void (*wpisz)(const char*);
} *string;
static string str;
void wpisz_do_str(const char *new_string)
{
    for(;new_string && *new_string;++new_string)
    {
       string new_char = create_string("");
       new_char->c = *new_string;
       new_char->next = NULL;
       str->next = new_char;
    }
}

Dla uproszczenia zapisu skorzystaliśmy z konstruktora klasy string. Tego jeszcze nie mamy, więc czas na niego:

/* konstruktor */
string create_string(const char *initial)
{
    string new_string = malloc(sizeof *new_string);
    new_string->wypisz = wypisz_str; /* ustawienie wskaźników na metody */
    new_string->wpisz = wpisz_do_str;
    for(;initial && *initial;++initial) /* inicjalizacja */
    {
       struct _string new_char;
       new_char->c = *new_string;
       new_char->next = NULL;
       tmp->next = new_char;
     }
    str = new_string; /* ustawienie adresu ostatniego napisu */
    return new_string;
}
/* deskruktor */
void free_string(string *s)
{
   if(*s == NULL)return;
   if((*s)->next)free_string(s->next);
   free(*s);
   str = NULL;
}

Porównywanie

int porownaj_str(string porownywany)
{
    int is_equal;
    string wsk = str;
    for(;wsk != NULL;wsk = wsk->next)
       for(;porownywany != NULL;porownywany = porownywany->next)
          if(wsk->c == porownywany->c)
             is_equal = 1;
          else
             is_equal = 0;
     return is_equal;
}

Konwersje

Pora na konwersje. Można je zaimplementować analogicznie do sprintf i sscanf.

Jak komputer przechowuje w pamięci listę znaków?

W pamięci komputera najpierw stoi "głowa" łańcucha (pierwszy znak).

Sytuacja taka jest przedstawiona poniżej (łańcuch "Hello"):

0x0329adf9382     c     'H'
0x0329adf9382     next  0x0329adf9383
0x0329adf9383     c     'e'
0x0329adf9383     next  0x0329adf9384
0x0329adf9384     c     'l'
0x0329adf9384     next  0x0329adf9385
0x0329adf9385     c     'l'
0x0329adf9385     next  0x0329adf9386
0x0329adf9386     c     'o'
0x0329adf9386     next  0x00000000

Na samym końcu stoi "ogon" (ostatni znak).

Ideą listy znaków jest to, że może się rozszerzać, bez specyfikowania żadnego wymiaru "na sztywno". Inną jej cechą jest to, iż nie możemy jej indeksować.