1 Algorytmy i struktury danychstruktury rekurencyjne tablice, listy, stosy, kolejki 1
2 Tablica – struktura o swobodnym dostępieC/C++ const int MAX = 12; int i, Data[MAX] = {1,7,2,4,8,11,7,2}; Pseudokod Data = [1,7,2,4,8,11,7,2,0,0,0,0] # de facto w Pythonie nazywa się to lista i = 1 Data[i] = 5 Data[5] = 5 Data[i+2] = 5 1 7 5 2 4 8 5 11 7 2 5
3 Jeszcze o pseudokodzietablica (lista w Pythonie) indeksowane są od 0 sprawdzanie długości możliwe jest funkcją len tablice można konkatenować t1 = t2+t3 iterowanie for element in A : ..... do definiowania zakresów służy funkcja range range(1,10) zwraca zakres 1,2,3,4,5,6,7,8,9 range(1,9,4)zwraca zakres 1, 5 range(5,3)zwraca zakres [] range(5,3,-1)zwraca zakres [5, 4] dopuszczalne jest konkatenowanie zakresów np [1,2,3] + [5,7]
4 Tablica – podstawowe operacjeStruktura o dostępie swobodnym Operacje Zapis - (1) : A[i] = newValue Odczyt - (1): value = A[i] if value == A[i] Przeszukiwanie - O(n) lub O(log n) w zależności od uporządkowania for e in A : ... for i in range(0,len(a)): if A[i] == s: ... element = find(A,pattern)
5 Tablica – dodatkowe operacjeWstawianie - O(n) – n = liczba elementów przed for i in range(n-1, k, -1) : A[i+1] = A[i] A[k] = newElement Zmiana rozmiaru - (n): C/C++: Resize(A, newSize) { tmp = alokuj_nowa_tablice kopiuj_elementy_z_A_do_nowej_tablicy zwolnij_A return tmp }
6 Tablica wskaźników xxx xxx yyy yyy zzz zzz aaa bbb ccc aaa ddd eee bbbC/C++ ELEMENT Array[MAX]; ELEMENT *Array[MAX]; xxx xxx yyy zzz aaa bbb ccc ddd eee yyy zzz aaa bbb NULL ccc NULL NULL NULL ddd eee W jęz. Python, .Net, Java obiekty klas mają charakter wkaźników
7 Zamiana elementów xxx xxx yyy yyy yyy zzz zzz zzz aaa bbb ccc aaa dddeee bbb NULL ccc NULL NULL NULL ddd eee !! Uwaga należy wyzerować nieużywane komórki
8 UWAGA Musimy mieć na co pokazywać, można alokować pojedyncze elementy lub skorzystać z dodatkowej tablicy xxx ELEMENT Array[...]; C/C++: Element *Array[MAX]; for (i.... ) A[i] = new Element; yyy zzz aaa for (....) Array[i] = &tab[j]; bbb ccc NULL ddd NULL eee NULL NULL ELEMENT tab[?];
9 Rekurencja danych Pseudokod: class SLNODE : C/C++ C/C++ - inaczejtypedef int DATA; typedef struct SLNODE { DATA data; SLNODE *next; } *PSLNODE; SLNODE OneElement; C/C++ - inaczej typedef int DATA; struct SLNODE; typedef SLNODE * PSLNODE; struct NODE { DATA data; PSLNODE next; } OneElement; Pseudokod: class SLNODE : data = None next = None
10 Lista jednostronnie wiązanadata next cccccccc Root data next AAAA data next dddddddd data next bbbb data next xxxxxxxx
11 Lista jednostronnie wiązanaclass NODE : data = None next = None def PrintList (list): tmp = list while tmp != None: print tmp.data tmp = tmp.next def ListLen(list): cnt = 0 tmp = list while tmp != None : cnt = cnt tmp = tmp.next return cnt
12 Lista jednostronnie wiązanadef AddHead(list, newNode): newNode.next = list return newNode def AddTail(list, newNode): newNode.next = None if list == None : return newNode else : tmp = list while tmp.next != None : tmp = tmp.next tmp.next = node return list Użycie: newNode = Node() newNode.data = "abc" list = AddTail(list,newNode)
13 Lista jednostronnie wiązanadef GetHead (list): if list==None : return None else : return list def GetTail(list): if list==None : return None else: tmp = list while tmp.next!=None: tmp = tmp.next return tmp Użycie: lastNode = GetEnd(list)
14 Lista jednostronnie wiązanadef RemoveHead(list): if list== None : return None else : return list.next def RemoveTail(list): if list==None : return None elif list.next==None : return None else: tmp = list while tmp.next.next!=None: tmp = tmp.next tmp.next = None return list Użycie: list = RemoveHead(list)
15 Lista jednostronnie wiązana- usuwanie elementudata next cccccccc Root data next AAAA data next dddddddd data next bbbb data next xxxxxxxx
16 Lista jednostronnie wiązana- dodawanie elementudata next cccccccc Root data next AAAA data next dddddddd data next bbbb data next xxxxxxxx
17 Lista jednostronnie wiązanadef FindNode(lista,dataPattern): tmp = list while tmp != None: if tmp.data == dataPattern : return tmp return None def GetAt(lista,pos): #funkcja zwraca element na pozycji pos liczac od 0 #jesli nie ma tyulu elementow zwraca None tmp = list while tmp != None: if pos == 0 : return tmp pos = pos - 1 return None
18 Lista jednostronnie wiązanadef InsertAfter(node, newNode): newNode.next = node.next node.next = newNode def DeleteAfter(node): node.next = node.next.next #InsertBefore i DeleteNode – wymagaja #modyfikacji wezla wczesniejszego
19 Lista jednostronnie wiązanadef InsertBeforeNode(lista,newNode,dataPattern): if list==None : return list elif list.next==None : if list.data!=dataPattern: return list else: newNode.next = list return newNode else: tmp = list while tmp.next != None: if tmp.next.data == datPattern : newNode = tmp.next tmp.next = newNode break return list
20 Lista jednostronnie wiązanadef DeleteNode(list,dataPattern): if list== None : return list elif list.next== None : if list.data!=dataPattern: return list else: return list.next else: tmp = list while tmp.next != None : if tmp.next.data == datPattern : tmp.next = tmp.next.next break return list
21 Lista dwustronnie wiązanadata next CCCCCCCC prev Root data next Aaaa prev data next XXXXXXXX prev bbbb data next BBBBBBB prev
22 Lista dwustronnie wiązanaclass DLNODE : data = None next = None prev = None Identyczne będą funkcje: PrintList(list) ListLen(list) GetHead(list) GetTail(list) FindNode(list,dataPattern)
23 Lista dwustronnie wiązanadef AddHead(list, newNode): newNode.prev = None newNode.next = list if list!= None : list.prev = newNode return newNode def AddTail(list, newNode): tail = GetTail(list) newNode.prev = tail if tail== None : return newNode tail.next = newNode return tail Użycie: newNode = DLNODE() newNode.data = "ABC" list = AddTail(list,newNode)
24 Lista dwustronnie wiązana usuwanie elementudata next CCCCCCCC prev Root data next Aaaa prev data next XXXXXXXX prev bbbb data next BBBBBBB prev
25 Lista dwustronnie wiązana wstawianie elementudata next CCCCCCCC prev Root data next Aaaa prev data next XXXXXXXX prev bbbb data next BBBBBBB prev
26 Lista dwustronnie wiązanadef InsertAfter(node, newNode): if node==None: return newNode.next = node.next newNode.prev = node if node.next!=None : node.next.prev = newNode node.next = newNode
27 Lista dwustronnie wiązanadef InsertBeforeNode (list, node, newNode): if node==None : return list newNode.next = node newNode.prev = node.prev node.pev = newNode if newNode.prev==None : # i.e. list = node return newNode newNode.prev.next = newNode return list Użycie: node = FindNode(list, whatToFind) list = InsertBefore(list, node, newNode)
28 Lista dwustronnie wiązanadef DeleteAfter(node): node.next = node.next.next if node.next != None : node.next.prev = node def DeleteNode(list, node): tmp = node.next if node.next!= None : node.next.prev = node .prev if node.prev == None : #i.e. list == node return node.next node.prev.next = node.next return list Użycie: node = FindNode(list, whatToFind) DeleteAfter(node) list = DeleteBefore(list, node)
29 Lista dwustronnie wiązanadef InsertAfter(node, newNode): newNode.next = node.next newNode.prev = node if node.next!= None : node.next.prev = newNode node.next = newNode def DeleteAfter(node): node.next = node.next.next if node.next != None : node.next.prev = node
30 Lista - struktura o dostępie sekwencyjnymOperacje: Przeszukiwanie - O(n) (zależy ? od uporządkowania) Wstawianie na poczatek - (1) Usuwanie z poczatku - (1) Zapis na i-ta pozycję - O(n) : GetAt+InsertAfter Odczyt - O(n): GetAt(list,i-1) Wstawianie na koniec (n) ?? Usuwanie z końca (n) ??
31 Stos - Last In First Out Przykład zastosowania np. DFS zzz zzz ttt Popxxx Push yyy zzz aaa bbb ccc ddd eee
32 Kolejka - First In First Outzzz Przykład zastosowania np. BFS ttt Put zzz ttt xxx yyy zzz aaa bbb ccc ddd Get eee eee
33 Tablicowa realizacja stosuCnt=0 def Push(Element): if Cnt
34 Tablicowa realizacja kolejkiELEMENT Array[MAX]; Problem: ograniczona pojemność stosu wędrujące elementy Realizacja realokacji elementów po osiągnięciu końca buforu śledzenie początku i końca (skomplikowane) – tzw. bufor cykliczny aaa 1 aaa 1 aaa bbb bbb 2 long Cnt long First
35 Listowa realizacja stosu/kolejkiPUSH/PUT -> AddHead() = (1) POP -> GetHead() + DeleteHead() = (1) GET -> GetTail() + DeleteTail() = O(n) def Push(stack, data): node = NODE() node.data = data return AddHead(stack, data)
36 Listowa realizacja kolejki/stosudef Pop(stack): ret = GetHead(stack) if ret==None: ERROR "Stos jest pusty" else: return (DeleteHead(stack), ret.data) def Get(stack): ret = GetTail(stack) if ret==None : ERROR "Stos jest pusty" else: return (DeleteTail(stack), ret.data) Użycie: stack,value = pop(stack)
37 Listowa realizacja kolejki w czasie stałymdef Put(startList, endList, dataNode): node = DLNODE() node.data = dataNode if startList==None : node.next = None node.prev = None return (node, node) else: node.prev = None node.next = startList startList.prev = node return (node, endList) Użycie: start,end = Put(start,end,"abc")
38 Listowa realizacja kolejki w czasie stałymdef Get(startList, endList): if startList==None : ERROR "Lista jest pusta" elif startList==endList: return (None, None, startList.data) else: ret = endList newEnd = endList.prev newEnd.next = None return (startList, newEnd, ret.data) Użycie: start,end,value = Get(start,end)
39 Lista cykliczna (jednostronna)Root Aaaa data next pWrite CCCCCCCC data next XXXXXXXX bbbb data next pRead BBBBBBB data next
40 Lista cykliczna (dwustronna)Root data next Aaaa prev pWrite data next CCCCCCCC prev data next XXXXXXXX prev bbbb pRead data next BBBBBBB prev
41 Lista cykliczna Ostatni element pokazuje na pierwszyW przypadku cyklicznej l. dwukierunkowej – również pierwszy na ostatni Wstaw, usuń analogicznie do listy zwykłej Szukanie – należy zapamiętać początek poszukiwań aby wiedzieć kiedy je zakończyć
42 Struktury wskaźnikowe bez wskaźnikówint arrOfPtrs[MAXPTR]; ELEMENT elements[MAXEL]; xxx yyy zzz aaa bbb ccc ddd eee 1 3 -1 -1 -1 -1 -1 int ptr; 3
43 Przykład użycia stosu odwiedzanie pomieszczen – DFSdef VisitRooms(start): stack = None stack = Push(stack, start) while (stack!= None) : stack,current = Pop(stack) neighbours = GetNeighbourhood(current) for room in neighbours : if not Already_Visited(room): stack = Push (stack, room) odwiedzanie pomieszczen BFS: Push -> Put Pop -> Get
44 Odwrotna Notacja PolskaRozwinięcie notacji zaproponowanej przez Jana Łukasiewicza Pozwala wykonywać obliczenia bez nawiasów, bez potrzeby stosowania prorytetów a+b*c przedstawiane jest jako a b c * + a+b*c-7 przedstawiane jest jako a b c * + 7 - b*c-(d+e)*4 przedstawiane jest jako b c * d e + 4 * -
45 ONP - obliczenia def ONPCalc(onp):"Funkcja oblicza wyniki wyrazenia w ONP Obslugiwane są operatory 2 argumentowe. Przyklad 3 4 * 2 +" stack = None while onp!= None : item = DajKolejnyElementWyrażenia(onp) if JestOperandem(item): stack = Push(stack,item) else: stack, op1 = Pop(stack) stack, op2 = Pop(stack) result = WykonajObliczenia(op, arg1, arg2) stack = push(stack, result) stack,result = Pop(stack) return result
46 ONP - obliczenia Obliczenia: weź element wyrażeniajeżeli to operand połóż go na stosie jezeli to operator zdejmij ze stosu odpowiednią liczbę operandów, wykonaj obliczenia i odłóż wynik na stos wynik znajduje sie na górze stosu
47 ONP – przykład obliczeńWejście Bieżący Stos po b. operacji 2, 3, *, 5, +, 7, * 3, *, 5, +, 7, * 2 *, 5, +, 7, * 3 2,3 5, +, 7, * * 6 +, 7, * 5 6, 5 7, * + 11 7 11, 7 77
48 ONP - konwersja Konwersja: Pobierz kolejny element wyrazeniaJesli jest to operand przepisz na wyjście Jeśli jest to operator ")" zdejmij se stosu wszystkie operatory aż do nawiasu otwierającego Jeśli jest to operator "(" połóż go na stosie Jeśli to inny niż nawiasy zdejmij se stosu wszystkie operatory o priorytecie wyższym lub równym do bieżącego i połóż bieżacy operator na stosie Po przetworzeniu wyrażenia przepisz stos na wyjście
49 def ONPConv(expression): stack = None onp = None while expressiondef ONPConv(expression): stack = None onp = None while expression!= None : item = DajKolejnyElementWyrażenia(expression) if JestOperandem(item) : onp = onp + [item] elif item == "(" : stack = push(stack,item) elif item == ")" : while (stack!= None): stack,item = Pop(stack) if item=="(": break else : onp = onp + [item] else: priority = DajPriorytet(item) while (stack!= None): top = GetHead(stack).data if top=="(": break if DajPriorytet(top)>priority: break result = Put result + [top] stack = RemoveHead(stack) stack = Push(stack,item) while stack!= None : stack, item = Pop(stack) onp = onp + [item] return onp ONP - konwersja
50 ONP – przykład konwersjiWejście Wyjście Stos b*c-(d+e)*4 *c-(d+e)*4 b c-(d+e)*4 * -(d+e)*4 b c (d+e)*4 b c * - d+e)*4 - ( +e)*4 b c * d )*4 - ( + * 4 b c * d e 4 b c * d e + - * b c * d e + 4 b c * d e + 4 * b c * d e + 4 * -