Algorytmy i struktury danych

Sortowanie przez wstawianie- algorytm rozpoczyna się od porównania dwóch pierwszych elementów sortowanej tablicy tab, którymi są tab[0] i tab[1] , jeśli nie są one ustawione we właściwej kolejności, to następuje zamiana miejsc. Następnie jest rozważany trzeci element tab[2], jeśli jest mniejszy niż tab[0] i tab[1] to te dwa elementy są przesuwane o jedna pozycję w prawo tab [0] umieszczamy na pozycji ,1, tab[1] na poz. 2, a tab[2] na poz. 0. Jeśli element tab[2] jest mniejszy niż tab[1] ale większy niż tab[0] to tab[1] wędruje na pozycję 2, jego miejsce zajmuje tab[2]. Jeśli tab[2] jest większy od tab[0] i tab[1] to pozostaje na swojej pozycji.

Sortowanie bąbelkowe- tablica jest przeglądana od dołu do góry, a dwa sąsiednie elementy są zamieniane, jeśli są w złej kolejności. Najpierw są porównywane elementy tab[n] i tab[n-1] i zamieniane miejscami, jeżeli tab[n]
Tablicę przegląda się ponownie porównując sąsiednie elementy i zamieniając je miejscami miejscami miarę potrzeby, ale tym razem ostatnie porównanie dotyczy elementów tab[2] i tab[1], najmniejszy element jest już, bowiem na właściwym miejscu poz.- 0. Procedura trwa aż do ostatniego przebiegu, w którym porównywane są tylko elementy tab[n] i tab[n-1] i ewentualnie zamieniane.
Sortowanie Quick sort (szybkie)- początkowa tablica jest podzielona na dwie podtablice. Pierwsza podtablica zawiera wszystkie elementy równe lub mniejsze niż element rozdzielający. Druga podtablica zawiera elementy równe lub większe niż element rozdzielający. Wybierane są dwa nowe elementy rozdzielające. Tworzą się cztery podtablice. Proces podziału jest kontynuowany dopóki nie dojdzie do utworzenia podtablic jednoelementowych, których już nie trzeba sortowałaby podzielić tablice należy znaleźć elem rozdzielający i przejrzeć tablice w celu umieszczenia jej elementów we właściwych podtablicach jedną z najprostszych metod jest przyjęcie za element rozdzielający pierwszy element tablicy, można też wybrać element leżący w środku tablicy. Teraz następuje przejrzenie elementów tablicy i porównanie z wybranym elementem rozdzielającym. Wykorzystujemy tu dwa indeksy tablicy: lower i upper- pierwsza i ostatnia pozycja w tablicy. Lower przesuwa się w prawo dopóki nie natrafi na element nie mniejszy po czym przychodzi kolej na upper, który wędruje w lewo dopóki nie spotka elementu nie większego niż oś. Elementy tab[lower] i tab[upper] sa teraz zamieniane miejscami. Następnie indeks lower jest zwiększany a upper zmniejszany w drugim przebiegu pętli while są zamieniane miejscami elementy tab[lower] i tab[upper] po czym przesuwają się kolejno indeksy a następnie w trzecim przebiegu pętli while zwiększa się jedynie indeks lower. Kończy się proces podziału dla całej tablicy a teraz procedura Quicksort wywołuje samą siebie dla otrzymanych w wyniku tego podziału dwóch podtablic. Cały proces powtarza się dla wszystkich podziałów rozważane tablice są coraz mniejsze aż wreszcie nie ma czego dzielić.

Sortowanie przez scalanie- problem, związany z algorytmem sortowania szybkiego polega na trudności w kontrolowaniu proceu podziału. Strategią algorytmy „sortowania przez scalanie” jest najbardziej jak to możliwe uprościć operację podziału a skoncentrować się na łączeniu dwóch podzielonych tablic. Algorytm sortowania przez scalanie należy do kategorii algorytmów opartych na zasadzie dziel i zwyciężaj. Umożliwia połączenie dwóch uporządkowanych połówek w jedną posortowaną tablicę. Połówki te trzeba jednak wcześniej posortować co osiąga się scalając z kolei ich posortowane połówki. Proces dzielenia tablicy na połowy kończy się kiedy tablica ma mniej niż dwa elementy. Algorytm ma charakter rekurencyjny.

Lista jednokierunkowa- jest oszczędną pamięciowo strukturą danych pozwalającą grupować dowolną- ograniczoną tylko ilością dostępnej pamięci- liczbę elementów.: liczb, znaków, rekordów. Do budowy listy jednokierunkowej używane są dwa typy komórek pamięci. Pierwszy typ jest zwykłym rekordem natury informacyjnej zawierającym dwa wskaźniki do początku i do końca listy. Drugi typ komórek jest również rekordem lecz ma już on charakter roboczy. Zawiera bowiem pole wartości i wskaźnik na następny element listy. Pola głowa ogon i następny są wskaźnikami, natomiast wartość może być czymkolwiek: liczbą, znakiem, rekordem.
Jeżeli lista jest pusta to struktura informacyjna zawiera dwa wskaźniki null. Null nie równa się zero jest to pewien adres, na który żadna zmienna nie wskazuje. Pierwszy element listy jest złożony z jego własnej wartości oraz ze wskaźnika na drugi el. listy. Drugi zawiera własne pole informacyjne i wskaźnik na trzeci element listy. Miejsce zakończenia listy zaznaczamy przez wartość null.




Dołączanie elementów do listy jednokierunkowej- podczas dokładania nowego elementu możliwe są dwa podejścia: 1). Albo będziemy traktować listę jak „worek” do gromadzenia danych nieuporządkowanych albo 2). Nowe elementy dokładane będą w liście we właściwym porządku. Działanie funkcji dorzuć: w przypadku listy pustej oba pola struktury informacyjnej są inicjowane wskaźnikiem na nowo powstały element. W przeciwnym wypadku nowy element zostaje podpięty do końca stając się ogonem listy. Możliwe jest dokładanie nowego rekordu przez pierwszy element listy stawałby się on wówczas automatycznie głową listy i musiałby zostać zapamiętany przez program.
Bardziej złożona jest funkcja dołączająca nowy element w takie miejsce aby całość lity była posortowana
Nowy element może zostać wstawiony na początek, koniec, lub w środku listy. Trzeba znaleźć miejsce wstawienia tzn. zapamiętać dwa wskaźniki: element, przed którym mama wstawić nową komórkę i element, za którym mama to zrobić. Do zapamiętania tych informacji wybieramy dwie zmienne np. przed i po. Następnie, gdy dowiemy się gdzie jesteśmy możemy dokonać wstawienia nowego elementu do listy. Sposób zależy od miejsca wstawienia i od tego czy lista przypadkiem nie jest jeszcze pusta. Skomplikowanie funkcji, która dokłada element do listy wynika z połączenia w niej rozszukiwania miejsca wstawienia z samym dołączeniem elementu. Można te czynności rozbić na dwie osobne funkcje. Istnieją trzy przypadki „współrzędnych” współrzędnych nowego elementu a). przed=NULLb). Po=NULL c). przed po=NULL. W zależności od ich wystąpienia zmieni się sposób dołączenia elementu do listy.
Do usuwania ostatniego elementu z listy używamy operatora dekrementacji. Funkcja, która się za nim ukrywa jest relatywnie prosta: jeśli na liście jest tylko jeden element to modyfikacji ulega zarówno pole głowa jaki ogon struktury informacyjnej oba te pola po uprzednim usunięciu jedynego elementu listy zostano zainicjowane wartością NULL. Trudniejszy jest przypadek gdy lista zawiera więcej niż jeden element. Należy wówczas odszukać przedostatni jej element aby móc odpowiednio zmodyfikować wskaźnik ogon struktury informacyjnej. Znajomość przedostatniego elementu listy umożliwia nam łatwe usunięcie ostatniego elementu listy.
Stos- jest liniową strukturą danych dostępnych do zapisywania i odczytywania tylko jednego końca (tzw. wierzchołka) Nowe elementy są dokładane na wierzch stosu i zdejmowane z wierzchu. Ostatni element położony na stosie będzie pierwszym z niego zdjętym. Stos jest nazywany strukturą LIFO (last In first out)
Operacja na stosie- initialize- powoduje opróżnienie stosu, empty- sprawdzenie czy stos jest pusty , full- czy stos jest zapełniony, push- umieszczenie elementu na stosie, pop- zdjęcie najwyższego elementu ze stosu. Ciąg operacji pusch i pop:

Po wykonaniu operacji push (X) element x sam staje się nowym wierzchołkiem przykrywającym poprzedni. Jedynym bezpośrednio dostępnym elementem stosu jest wierzchołek.
Kolejki- kolejka to lista oczekujących zwiększająca się przez dodawanie elementów na jej końcu, a malejąca przez wyjmowanie elementów z początku. Kolejka jest struktur, której wykorzystywane są oba końce jeden do wstawiania nowych elementów, elementów drugi do ich usuwania. Ostatni element musi poczekać aż wszystkie elementy poprzedzające go w kolejce zostaną usunięte. Nazywa się to strukturą FIFO (first In first out).
Operacja na kolejce- initialize- powoduje opróżnienie kolejki, empty- sprawdzenie czy kolejka jest pusta, full sprawdzenie czy kolejka jest zapełniona, enq- powoduje umieszczenie elementu na końcu kolejki, deq- usunięcie pierwszego elementu. Jedną z możliwych implementacji kolejki jest tablica. Elementy dostawia się na końcu ale usuwa się je z początku zwalniając komórki tablicy. Komórki te używa się do wstawiania nowych elementów co, powoduje że koniec kolejki może znaleźć się na początku tablicy. Kolejka jest pełna jeśli pierwszy element poprzedza bezpośrednio element ostatni w kierunku przeciwnym do ruchu wskazówek zegara.
Kolejka priorytetowa- elementy są usuwane według ich priorytetu oraz bieżącej pozycji w kolejce. Operacje wykonywane na kolejkach priorytetowych polegają na zwykłym wstawianiu nowego elementu i usuwania największego elementu. Mogą one być reprezentowane przez dwa typy list. Dla pierwszego typu list elementy są umieszczone w kolejności ich wstawiania a dla drugiego typu list porządek zachowuje się umieszczając nowy element na pozycji odpowiadającej jego priorytetowi. Realizacją kolejek priorytetowych jest użycie struktury danych zwanej stertą.
Sterta- to takie drzewo binarne, w którym jest zachowana hierarchia elementów tzn. każdy element nadrzędny ma wartość większą niż jego elementy podrzędne



Liniowy porządek wypełniania drzewa sugeruje sposób jego składowania w tablicy: wierzchołek=1. wartość każdego węzła jest większa od wartości węzłów jego dwóch potomków. Można bez problemu nowy element dopisać na koniec tablicy (zburzy nam to panujący ład) następnie przywrócić z powrotem tablicy właściwości sterty.
Dlaczego sterta umożliwia łatwe tworzenie kolejek priorytetowych – priorytetowych kolejka priorytetowych pierwszym obsługiwanym jest element, który ma największa wartość. W przypadku list i zwykłych tablic problemem byłoby znalezienie największego elementu w stercie z założenia największy element znajduje się w komórce tablicy o nr 1.
Wstawianie nowego elementu do sterty- elementy są zawsze dokładane na koniec ale potem trzeba wywołać procedurę Do góry, która przywróci stercie zachwiany porządek, lub po usunięciu największego elementu w tablicy robi się dziura ostatni element tablicy wstawiamy na miejsce korzenia i wywołujemy procedurę Na dół- która skoryguje stertę, której porządek miałby być zachwiany.
Procedura Na dół- zmiana wartości w korzeniu mogła zburzyć ład zarówno w lewym jak i w prawym jego potomku. Nowy korzeń należy przy pomocy zamiany z większym z jego potomków przesiać w dół drzewa aż do momentu znalezienia właściwego dla niego miejsca.
Drzewo- jest to taka organizacja danych, w których 1). Jest 1 element główny 2). Każdy element poza głównym ma jeden element nadrzędny i może mieć wiele elementów podrzędnych 3). Może być wiele (dowolna ilość) poziomów hierarchii 4). Usuwając dowolny element jednocześnie usuwamy wszystkie elementy podrzędne.
Drzewa binarne- struktury podobne do list jednokierunkowych wzbogacone o jeden wymiar. Drzewo, w którym każdy element ma jeden element nadrzędny i co najwyżej 2 elementy podrzędne. Każdy z elementów tej struktury może zawierać wskazanie na dwa inne elementy: lewy i prawy. Podstawowa komórka służąca do konstrukcji drzewa binarnego w miejsce jednego wskaźnika następny ma dwa wskaźniki o nazwach lewy i prawy . są one wskaźnikami do lewej i prawej gałęzi drzewa binarnego.
Drzewa binarne i wyrażenia arytmetyczne- zastosowanie drzew binarnych do reprezentowania wyrażeń arytmetycznych:
Dowolne wyrażenie arytmetyczne może być zapisane w kilku odmiennych postaciach związanych z położeniem operatorów: przed swoimi ………. Po nich i pomiędzy nimi.
Uniwersalna struktura słownikowa- jest strukturą która automatycznie zapewnia kompresję danych już w pamięci komputera nie ograniczając dostępu do zapamiętanych informacji. Idea USS opiera się na obserwacji. Wiele słów posiada te same rdzenie (przedrostki) różniąc się jedynie końcówkami (przyrostkami). Jest to deklaracja typu rekurencyjnego, którego elementem jest tablica wskaźników do tego typu.
Grafy- są to struktury danych. Grafem nazywamy parę (X, T) gdzie X oznacza zbiór tzw. Węzłów (wierzchołków) a T jest zespołem krawędzi. Garf jest skierowany jeśli krawędziom został przypisany jakiś kierunek (symbol, strzałka) biorąc pod uwagę dwa węzły grafu x, y połączone krawędzią to węzeł x jest węzłem początkowym a węzeł y końcowym.