Posortowana lista w sqrt(n)

Mamy posortowaną listę. Chcemy przy użyciu dodatkowej O(sqrt(n)) ilości pamięci umieć wstawiać i usuwać elementy z tej listy w czasie O(sqrt(n)).

Takie zadanie pojawiło się na pierwszej liście z AiSD. Większość rozwiązań tego zadania dzieliło listę na pierwiastek z n bloków o równej długości. Sprawiało to wiele problemów w sytuacjach w których należało zwiększyć liczbę bloków (jak to zrobić, aby zmieścić się w czasie O(sqrt(n))?). Moje rozwiązanie opierało się na nieco innym pomyśle, dzięki czemu cała struktura danych staje się bardzo prosta i elegancka.

Podzielmy listę (dwukierunkową) na bloki. Pierwszy blok będzie miał jeden element; drugi blok dwa elementy, trzeci trzy... i tak dalej. Przy czym dopuszczamy, aby ostatni blok był niepełny. To będzie nasz niezmiennik. Taka lista będzie miała k dodatkowych wskaźników (na początki bloków) i każdy z bloków będzie miał rozmiar nie większy niż k. Liczba elementów na takiej liście będzie równa 1 + 2 + 3 + ... + k = k(k+1) / 2 = n. Zatem jak widzimy k jest rzędu O(sqrt(n)).

Wstawianie elementu el wykonujemy w czterech prostych krokach:
- Szukamy do którego bloku musi trafić element el (O(k) operacji).
- Szukamy w które miejsce ma trafić element i umieszczamy go w tym miejscu (O(k)).
- Przywracamy niezmiennik listy. Robimy to w ten sposób, że wskaźniki do wszystkich bloków znajdujących się na prawo od wstawionego elementu przesuwamy o jeden element w lewo (O(k) operacji).
- Jeśli ostatni blok przekroczy dozwolony rozmiar, to tworzymy nowy blok (O(1)).
Wstawienie elementu prezentuje poniższy rysunek.
Usuwanie elementu w sposób analogiczny.

Wielopoziomowa Lista Liczb Całkowitych

Zadanie z kursu ANSI C brzmiało:

Wielopoziomową Listę Liczb Całkowitych (w skrócie WLLC) definiujemy jako skończony (w tym także pusty) ciąg, którego elementami są liczby całkowite lub WLLC. Jeśli lista zawiera tylko liczby to nazywamy ją jednopoziomową. Przykłady L1 = [3,1,5]; L2 = [2,[4,7],[]]; L3 = [[[3],[5,8],2],[1,5]]. Lista L1 jest jednopoziomowa. Zdefiniować moduł WLLC (tzn. podać zawartość plików wllc.c oraz wllc.h), w którym:
- Zdefiniowana jest funkcja WLLC merge(WLLC l1, WLLC l2), która zwraca listę powstałą z dołączenia listy l2 na końcu listy l1. Na przykład dołączenie listy L1 na końcu listy L2 powinno stworzyć listę [2,[4,7],[],3,1,5].
- Zdefiniowana jest funkcja WLLC flat(WLLC li), która tworzy nową listę jednopoziomową zawierającą wszystkie liczby z listy li z zachowaniem ich kolejności. Na przykład wywołanie flat(L3) powinno zwrócić listę [3,5,8,2,1,5].

Ja na tym kolokwium podszedłem do tego zadania bardzo rutynowo i stworzyłem strukturę, która wyglądała mniej więcej tak:

struct WLLCnode
{
  bool  isWLLC;    // True jeśli element jest listą WLLC
  int   intvalue;  // Wartość liczbowa
  WLLC* WLLCvalue; // Wartość listowa
  WLLC* next;      // Wskaźnik na następny element
};
typedef WLLCnode* WLLC;

Po czym występowały definicje funkcji. Trochę się zamotałem z tymi wskaźnikami,

"Dać programiście wskaźniki to tak jakby dać małpie karabin maszynowy" Piotr Chrząstowski-Wachtel

pokreśliłem pół kartki ale ostatecznie coś wyszło i o dziwo okazało się poprawne. Nie mam zamiaru odtwarzać tego rozwiązania, ale wierzcie mi - było straszne :D. Natomiast Maciek zaczął to zadanie tak:

typedef char* WLLC;

i wszystkie funkcje pisze się miło i przyjemnie. Bardzo spodobało mi się to rozwiązanie. Z moją pomocą udało się zmniejszyć złożoność obu funkcji do liniowych i zmniejszyć rozmiar tych funkcji do kilku linijek.

Pierwsza funkcja jest bardzo prosta, aż niema co w niej opisywać. Rezerwujemy pamięć, kopiujemy pierwszą listę, kopiujemy drugą listę, wstawiamy przecinek w odpowiednie miejsce. Osobno rozważamy przypadki gdy lista jest pusta.

WLLC merge(WLLC a, WLLC b)
{
  int lena = strlen(a);
  int lenb = strlen(b);
  WLLC answer = malloc((lena + lenb) * sizeof(char));
  
  // Jeśli lista a jest pusta - zwróć listę b
  if (lena == 2)
    return strcpy(answer, b);

  // Analogicznie
  if (lenb == 2)
    return strcpy(answer, a);
  
  strcpy(answer, a);
  strcpy(answer + lena, b + 1);
  answer[lena - 1] = ',';

  return answer;
}

Z funkcją flat na początku były kłopoty. Maciek strasznie zakręcił... ale rozwiązanie jest dość proste:

WLLC flat(WLLC a)
{
  int  j = 1;
  bool inint = false;
  WLLC answer = malloc(strlen(a) * sizeof(char));
  
  answer[0] = '[';
  for (int i = 0; a[i] != '\0'; i++)
  {
    if (('0' <= a[i] && a[i] <= '9') || a[i] == '-')
    {
      answer[j++] = a[i];
      inint = true;
    }
    else
    {
      if (inint) answer[j++] = ',';
      inint = false;
    }
  }
  if (j == 1) j++;
  answer[j-1] = ']';
  answer[j]   = '\0';
  
  return answer;
}

Iterator i przebiega listę, którą chcemy spłaszczyć. Iterator j przebiega naszą listę wynikową. Jeśli na danej nam liście znajduje się cyfra - to ją przepisujemy. Jeśli nie, to sprawdzamy czy nowy znak zakończył nam jakąś liczbę (służy nam do tego zmienna "inint"). Jeśli zakończył to stawiamy przecinek. Na końcu zamykamy nawias i zwracamy wynik. Warunek if na samym końcu zapewnia nas, że zwrócimy poprawny wynik także dla listy pustej. Przykład użycia:

  WLLC L0 = "[]";
  WLLC L1 = "[3,1,5]";
  WLLC L2 = "[2,[4,7],[]]";
  WLLC L3 = "[[[3],[5,8],2],[1,5]]";
  
  printf("%s\n", merge(L2, L1));
  printf("%s\n", flat(L3));