Aisd W03 I 4

Algorytmy i struktury danych Wykład 2

 Podstawy struktur danych  Dynamiczne struktury danych  Implementacja dynamicznych struktur danych w języku C

Definicja struktury danych Definicja Strukturą danych nazywamy trójkę uporządkowaną S=(D, R, e), gdzie: 

D – oznacza zbiór danych elementarnych di, i = 1,..,d



R={rwe, N} – jest zbiorem dwóch relacji określonych na rwe ⊂ e × Ddanych: strukturze

N ⊂ D× D

– relacja wejścia do struktury danych S, – relacja następstwa (porządkująca) strukturę

S, 

e – jest elementem wejściowym do struktury danych S (nie jest to dana wchodząca w skład struktury danych S).

Algorytmy i struktury danych

2

Zbiór danych elementarnych D

■

■

■

Zbiór danych elementarnych jest skończony i dla wygody operowania oznaczeniami jego elementów poszczególne dane są indeksowane od wartości 1 w kierunku wartości większych. Przykład: D = d , d , d , d , d

{

1

2

3

4

5

}

Liczność zbioru danych elementarnych wynosi 5, czyli d=5

Algorytmy i struktury danych

3

Dane elementarne - zmienne programowe ■

Dane elementarna di są pojęciem abstrakcyjnym, rozumianym jako tzw. „nazwana wartość”. Jest ona określana jako uporządkowana dwójka elementów:

d i = ni , wi

■

■

, gdzie:

◆

ni – nazwa danej,

◆

wi – aktualna wartość danej z określonej dziedziny wartości.

Zmienna programowa jest pojęciem związanym z realizacją danej w konkretnym środowisku programistycznym. Posiada zdefiniowaną etykietę (nazwę zmiennej), wraz z określeniem dziedziny wartości, którą może przyjmować dana reprezentowana przez zmienną

Algorytmy i struktury danych

4

Relacja rwe – wskazanie korzenia struktury S ■

■

Relacja rwe ⊂ e × D , jest opisywana poprzez zbiór (jednolub wieloelementowy) par uporządkowanych elementów, z których pierwszym jest zawsze element wejściowy e, natomiast drugim elementem jest jedna z danych elementarnych ze zbioru D. Element di „uczestniczący” w relacji rWE nazywamy korzeniem struktury danych S. Struktura musi mieć zdefiniowany co najmniej jeden korzeń.

Przykład: Jeśli struktura S posiada dwa korzenie: d2 oraz d5, to

rwe = { e, d2 , e, d5

Algorytmy i struktury danych

}

5

Relacja N – ustalenie porządku struktury S ■

■

Relacja następstwa N opisuje wzajemne uporządkowanie elementów w strukturze danych S. Porządek struktury opisujemy w postaci zestawów par uporządkowanych elementów. Przykładowy porządek pięcioelementowej struktury danych S:

N = { d 2 , d1 , d1 , d 3 , d1 , d 4 , d 3 , d 4 , d 5 , d 3 poprzednik

Algorytmy i struktury danych

}

następnik

6

Model grafowy struktury danych ■

Aby łatwiej zobrazować strukturę danych i w ten sposób lepiej ją zrozumieć, można zbudować dla niej model grafowy. W modelu tym: ◆ węzły (wierzchołki) oznaczają poszczególne dane elementarne, ◆ łuki (strzałki) służą do odwzorowania następstw poszczególnych danych elementarnych w strukturze S.

korzeń Przykład: Model grafowy dla opisywanej do tej pory struktury S: e d5

d3

d2

korzeń Algorytmy i struktury danych

d1

liść

D = { d1 , d 2 , d 3 , d 4 , d 5 } rwe = { e, d 2 , e, d 5

d4

}

N = { d 2 , d1 , d1 , d 3 , d1 , d 4 , d 3 , d 4 , d 5 , d 3

} 7

Statyczna a dynamiczna struktura danych Statyczna struktura danych: ◆ Posiada z góry ustalony rozmiar (bez możliwości jego zmiany); ◆ Jej deklaracja poprzedza uruchomienie głównej procedury programu; ◆ Liczba zmiennych o typie statycznych musi być z góry znana; ◆ Pamięć jest przydzielana na początku, a zwalniana po zakończeniu programu;

Algorytmy i struktury danych

8

Statyczna a dynamiczna struktura danych Dynamiczną strukturę danych odróżnia sposób przydziału pamięci operacyjnej: ◆ wielkość wymaganej pamięci dla struktury danych nie musi być znana przed uruchomieniem programu; ◆ przydział pamięci następuje dynamicznie w czasie realizacji programu; ◆ po wykonaniu zadań struktury danych powinny być usunięte a przydzielona pamięć dynamicznie zwolniona; ◆ zalety tego podejścia: ✦

✦

◆

możliwość dynamicznego tworzenia struktur danych o różnych „kształtach” i rozmiarach; „brak” ograniczeń na wielkość struktury;

wada: złożone operacje dodawania i usuwania elementów struktury;

Algorytmy i struktury danych

9

Zmienne i typy wskaźnikowe – przypomnienie

■

■

Utworzenie struktury dynamicznej możliwe jest poprzez zastosowanie wskaźników. Czy potrafimy odróżnić pojęcie i właściwości: ◆ zmiennej, ◆ wskaźnika, ◆ adresu, ◆ referencji?

Algorytmy i struktury danych

10

Wskaźniki - podstawy  Wskaźnik to zmienna przechowująca adres pamięci. pamięci  Ten adres to lokalizacja innej zmiennej w pamięci.  Jeśli jedna zmienna zawiera adres innej zmiennej, to mówi się, że ta pierwsza zmienna to wskaźnik do drugiej zmiennej.

Wskaźnik Adres

Algorytmy i struktury danych

Zmienna Wartość

11

Wskaźniki - podstawy

 Deklaracja wskaźnika: typ *nazwa;  Przykłady: int *wsk1; char *wsk2;

Algorytmy i struktury danych

12

Operatory wskaźnikowe: * oraz &

 Jednoargumentowy operator & zwraca adres w pamięci. Operacja: m = &count; umieszcza w zmiennej m adres zmiennej count.  Załóżmy, że zmienna count zajmuje komórkę pamięci o adresie 2000. Załóżmy, też że jej wartość to 100. Tak więc w wyniku powyższego przypisania zmienna m będzie miała wartość 2000. „m otrzymuje adres zmiennej count” Algorytmy i struktury danych

13

 Jednoargumentowy operator * zwraca wartość zmiennej, znajdującej się pod adresem następującym po operatorze.  Jeśli zmienna m zawiera adres zmiennej count to: q = *m; umieszcza wartość zmiennej count w zmiennej q.  Tak więc zmienna q będzie miała wartość 100, gdyż 100 znajduje się pod adresem 2000, który jest adresem zapisanym w m. „q otrzymuje wartość, znajdującą się pod adresem m” Algorytmy i struktury danych

14

Wskaźniki - podstawy

Przykład #include <stdio.h> int main(void) { int *p, q; q = 100; /* przypisanie do q wartości 100 */ p = &q; /* przypisanie do p adresu q */ printf("%d", *p); /* wyświetlenie wartości q z użyciem wskaźnika */ return 0; }

Algorytmy i struktury danych

15

Wskaźniki - podstawy

Przykład #include <stdio.h> int main(void) { int *p, q; p = &q; /* pobranie adresu q */ *p = 100; /* przypisanie wartości q z wykorzystaniem wskaźnika */ printf(„wartośćią q jest %d", q); return 0; }

Algorytmy i struktury danych

16

Wskaźniki - podstawy

 Przykład niepoprawnego wykorzystania wskaźnika int main(void) { int *p; *p = 10;

/* niepoprawnie - p jeszcze na nic nie wskazuje */

}

Algorytmy i struktury danych

17

Wskaźniki - podstawy  Oprócz operatorów * i & istnieją tylko cztery inne operatory, które można stosować ze wskaźnikami: +, ++, -, --.  Operator ++ zwiększa adres, na który wskazuje wskaźnik o jedną długość typu wskaźnika; np. jeżeli p zawiera adres 200 do liczby całkowitej (o długości 2 bajtów), to instrukcja p++ powoduje, że p będzie miało adres 202, tzn. 200+(1*2). Równoważnie można to zapisać: p+=1;  Jeżeli mamy: int *p; p=p+200; to p będzie wskazywało na 200. liczbę całkowitą występująca za liczbą wskazywaną poprzednio.  Podobnie działają operatory odejmowania. Algorytmy i struktury danych

18

Wskaźniki - podstawy  Aby otrzymać wartość o jeden większą od wskazywanej przez wskaźnik, należy posłużyć się konstrukcją: (*p)++; (Jeżeli założymy, że p wskazuje na adres 200, pod którym znajduje się liczba 100 typu int, to po wykonaniu ww. instrukcji p wskazuje na liczbę 101 nadal pod adresem 200).  UWAGA! Instrukcja: *p++; powoduje zwiększenia wskaźnika p o 1 (a nie wartości obiektu, na który wskazuje!!!), tzn. p wskazuje na adres 202 (zakładamy, że liczba typu int zajmuje 2 bajty).  Dzieje się tak dlatego, że operator * ma wyższy priorytet niż ++. Algorytmy i struktury danych

19

Rzutowanie typów  Aby rzutować zmienną t typu T na inny typ S, poprzedzamy t nazwą typu S ujętą w nawias.  Przykład float f; f=100.2; printf(„%d, (int) f); /*wyświetlenie f jako liczby całkowitej */

Algorytmy i struktury danych

20

Rzutowanie typów  Ta sama zasada dotyczy rzutowania wskaźników  Załóżmy, że mamy: int *iptr; float *fptr;  Aby przypisać wskaźnik do liczby całkowitej iptr wskaźnikowi do liczby zmiennoprzecinkowej fptr, piszemy: fptr=(float *) iptr;

Algorytmy i struktury danych

21

Wskaźniki i tablice  Niech: int sample[10];  Można utworzyć wskaźnik do pierwszego elementu, używając nazwy sample  Poniższy fragment programu przypisuje zmiennej p adres pierwszego elementu tablicy sample: int *p; int sample[10]; p = sample;  Równoważne są odwołania: sample[i] oraz *(sample+i)

Algorytmy i struktury danych

22

Wskaźniki i tablice  Nazwa tablicy bez indeksu jest wskaźnikiem do początku tablicy. Przeanalizuj poniższy przykład #include <stdio.h> int main(void) { int a[10] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; int *p; p = a; /* przypisanie p adresu początkowego tablicy a */ /* wypisanie pierwszych trzech elementu tablicy a z użyciem p */

printf("%d %d %d\n", *p, *(p+1), *(p+2)); /* to samo z wykorzystaniem a */ printf("%d %d %d", a[0], a[1], a[2]); return 0;} Algorytmy i struktury danych

23

Wskaźniki i tablice Zadanie Jaka wartość zostanie wypisana na ekranie? int temp[5] = {10, 19, 23, 8, 9}; int *p; p = temp; printf("%d", *(p+3));

Odpowiedź: 8 Algorytmy i struktury danych

24

Wskaźniki i tablice Zadanie Napisać program wczytujący ciąg znaków. Program powinien odszukać pierwszą spację w ciągu, a następnie wyświetlić pozostałą część napisu występującą za nią. Wykorzystać zmienne wskaźnikowe.

Algorytmy i struktury danych

25

#include <stdio.h> int main(void) { char str[80], *p; printf(„Wprowadź ciąg znaków: "); gets(str); p = str; /* Dopóki nie natrafimy na koniec napisu lub spację, zwiększamy p aby pobrać następny znak */ while(*p && *p!=' ') p++; p++; printf(p); Uruchom program return 0;} Algorytmy i struktury danych

26

Wskaźniki wielokrotne  Możliwe jest, aby wskaźnik wskazywał na inny wskaźnik (tzw. wielokrotne odwołanie niejawne).

Wskaźnik do wskaźnika Adres

Wskaźnik Adres

Zmienna Wartość

 Aby zadeklarować wskaźnik do wskaźnika, należy przed nazwą wskaźnika umieścić dodatkową gwiazdkę: char **mp;

Algorytmy i struktury danych

27

Wskaźniki wielokrotne Aby dostać się do wartości wskazywanej niejawnie przez wskaźnik do wskaźnika, należy zastosować operator * dwukrotnie: char **mp, *p, ch; p=&ch; // pobranie adresu ch mp=&p; // pobranie adresu p /* przypisanie ch wartości A z wykorzystaniem wielokrotnego odwołania niejawnego */ **mp=‘A’;

Algorytmy i struktury danych

28

Arytmetyka wskaźników – przypomnienie Przeanalizuj i wyjaśnij poniższy kod: int x=1, y, z[10]; int *ip, *iq; ip = &x; y = *ip; *ip = 0; *ip += 1; y = *ip+2; ip = &z[0]; iq = ip;

Algorytmy i struktury danych

/* ip wskazuje na x /* y = 1 /* x przypisano 0 /* x zwiększone o 1 /* y = 3 /* ip wskazuje na z[0] /* iq wskazuje na z[0]

*/ */ */ */ */ */ */

29

Arytmetyka wskaźników – przypomnienie ■

■

■

■

Przykład operacji dla typu prostego: ◆ int *p; ◆ p += 2; p = (adres wskazywany przez p) + (2 * rozmiar obiektu wskazywanego przez p); np. dla p równego 3000 i rozmiaru 4 (dla int): ◆ 3000 + 2 * 4 = 3008;

pa Przykład dla tablicy: ◆ int a[4]; ◆ int *pa; ◆ pa = a; /* lub pa=&a[0]; */ ✦ ✦ ✦

pa ++; pa =+ 2; pa --;

Algorytmy i struktury danych

3000

3004

3008

3012

a[0] a[1] a[2] a[3]

/*pa wskazuje na a[1] */ /*pa wskazuje na a[3] */ /*pa wskazuje na a[2] */

30

Dynamiczne zarządzanie pamięcią operacyjną Dynamiczny przydział pamięci (alokacja): ◆

malloc() /* z biblioteki stdlib.h */

◆

Prototyp funkcji: ✦

void *malloc(size_t liczba_bajtów);

◆

‘void’ pozwala na wskazanie danych dowolnego typu;

◆

argumentem funkcji jest rozmiar przydzielanej pamięci;

◆

funkcja zwraca wskaźnik na pierwszy bajt przydzielonego obszaru pamięci

◆

pamięć przydzielana jest z obszaru zwanego stertą (kopcem);

◆

sizeof() – funkcja do określenia wielkości pamięci: ✦

sizeof(int) – zwróci rozmiar pamięci potrzebny dla przechowania danych typu int;

sizeof(struct typ_struktury) – zwróci rozmiar pamięci potrzebny dla przechowania danych typu zadeklarowanego jako typ_struktury; Algorytmy i struktury danych ✦

31

Dynamiczne zarządzanie pamięcią – polecenia Przykład użycia funkcji malloc() i sizeof(): ◆

(1)

int x=1, y; y = sizeof (int); lub

y = sizeof x; (2) struct node { rekursywna char dane; deklaracja struct node *nextPtr ; struktury }; struct node *newPtr; newPtr = (struct node *)malloc(sizeof(struct node)); newPtr

? dane

Algorytmy i struktury danych

nextPtr 32

Dynamiczne zarządzanie pamięcią – polecenia ■

Dynamiczne zwolnienie pamięci: ◆

■

free()

/* z biblioteki stdlib.h */

Przykład: struct node *newPtr; newPtr = (struct node *)malloc(sizeof(struct node)); … /* operacje na danych struktury node*/ … free (newPtr);

Algorytmy i struktury danych

33

Dynamiczne zarządzanie pamięcią – polecenia

■

W języku C++ : ◆ do alokacji pamięci można używać polecenia new, np. struct node *robPtr; robPtr=new struct node; ◆ do zwalniania pamięci można używać polecenia delete, np. delete robPtr;

Algorytmy i struktury danych

34

Algorytmy i struktury danych Wykład 3

 Liniowe struktury danych (listy)  Rodzaje struktur liniowych  Implementacja list  Podstawowe operacje na listach jednokierunkowych

Liniowe struktury danych

Wyróżniamy cztery rodzaje list:  jednokierunkowe listy niecykliczne,  dwukierunkowe listy niecykliczne,  jednokierunkowe listy cykliczne (pierścienie jednokierunkowe),  dwukierunkowe listy cykliczne (pierścienie dwukierunkowe).

Algorytmy i struktury danych

36

Jednokierunkowe listy niecykliczne ■

Model grafowy listy jednokierunkowej:

e d1

Algorytmy i struktury danych

d2

d3

dn

37

Dwukierunkowe listy niecykliczne Model grafowy listy dwukierunkowej:

■

e d1

Algorytmy i struktury danych

d2

d3

dn

38

Pierścień jednokierunkowy Model grafowy pierścienia jednokierunkowego:

■

e d1

Algorytmy i struktury danych

d2

d3

dn

39

Pierścienie dwukierunkowe ■

Model grafowy pierścienia dwukierunkowego:

e

d2 d1

d3

dn

Algorytmy i struktury danych

40

Podstawowe operacje na listach

1. 2. 3. 4. 5.

Wyszukiwanie elementu na liście Dołączanie elementu do listy Usuwanie elementu z listy Przestawianie elementów na liście Porządkowanie (sortowanie) listy

Algorytmy i struktury danych

41

Dynamiczne realizacje struktur listowych  Element listy zawiera: ◆ Dane elementarne, ◆ Odwzorowanie relacji następstwa – informacja o dowiązaniu do innych elementów; startPtr

Głowa (head)

Ogon (tail)

NULL

dane

Algorytmy i struktury danych

wskaźnik na następny element

42

Dynamiczne realizacje struktur listowych  Deklaracja elementu listy: struct Node { char dane; struct Node *next; }; typedef struct Node *NodePtr;

dane elementarne

dowiązanie do kolejnego elementu

/* typ wskaźnikowy do struktury ‘Node’ */

Algorytmy i struktury danych

43

Wyszukiwanie elementu na liście Algorytm wyszukania elementu na liście jednokierunkowej: ◆

Cel: ✦

◆

◆

Wyszukanie elementu na liście;

Dane wejściowe: ✦

Wskaźnik na pierwszy element listy;

✦

Kryterium poszukiwania, np. wartość danej elementarnej;

Uwagi: ✦

W skrajnym przypadku należy przejrzeć wszystkie elementy (złożoność O(n));

Algorytmy i struktury danych

44

Algorytm wyszukiwania elementu na liście jednokierunkowej 2. Rozpocznij wyszukiwanie od pierwszego elementu listy; 3. Dopóki nie osiągnięto końca listy oraz szukana wartość jest różna od wartości aktualnego elementu przemieść się do następnego elementu listy; 4. Zwróć wskaźnik na znaleziony (aktualny) element;

startPtr

A Algorytmy i struktury danych

B

C

D 45

Algorytm wyszukiwania elementu na liście jednokierunkowej

Node *Find (NodePtr *startPtr, char nazwa) { NodePtr currPtr = *startPtr;

/* adres na pierwszy

element listy */

while ((currPtr != NULL) && (currPtr -> dane != nazwa)) currPtr = currPtr -> next; return currPtr; }

Algorytmy i struktury danych

46

Dynamiczne realizacje struktur listowych

■

Przykład: Node *element = Find (startPtr, ‘C’);

prevPtr

Wartość szukana: C

NULL

newPtrcurrPtr: startPtr currPtr -> dane: A

C

currPtr currPtr startPtr Algorytmy i struktury danych

A

B

D C

NULL NULL

D NULL 47

Dynamiczne realizacje struktur listowych

■

Przykład (cd): Node *element = Find (startPtr, ‘C’);

prevPtr currPtr startPtr Algorytmy i struktury danych

Nazwa szukana: C

NULL

newPtrcurrPtr: currPtr -> next currPtr -> dane: B

C

currPtr

A

B

D C

NULL NULL

D NULL 48

Dynamiczne realizacje struktur listowych

■

Przykład (cd.) Node *element = Find (startPtr, ‘C’);

prevPtr

Nazwa szukana: C

NULL

currPtr startPtr Algorytmy i struktury danych

newPtrcurrPtr: currPtr -> next currPtr -> dane: C

C

currPtr

A

B

D C

NULL NULL

D NULL 49

Algorytm dołączania elementu do uporządkowanej listy jednokierunkowej ◆

Cel: ✦

◆

Dodanie nowego elementu do listy uporządkowanej;

Dane wejściowe: ✦

Wskaźnik na pierwszy element listy;

✦

Dane do wstawienia na listę;

C

startPtr Algorytmy i struktury danych

A

B

D 50

Algorytm dołączania elementu do uporządkowanej listy jednokierunkowej 1. Utwórz element i ustal dane elementarne 2. Znajdź miejsce wstawienia elementu na listę ✦ Zainicjuj currPtr na początek listy a prevPtr na NULL; ✦ Dopóki currPtr jest różny od NULL i wartość wstawiana jest większa od currPtr->dane: • Ustaw prevPtr na currPtr; • Przesuń currPtr na następny element listy; 3. Wstaw element na listę: ✦ Wstaw element jako pierwszy na liście: • Ustaw pole next elementu wstawianego na pierwszy element listy; • Ustaw wskaźnik do listy na element wstawiony;

lub ✦

Wstaw element we wskazane miejsce w liście: • Ustaw pole next elementu prevPtr na element wstawiany; • Ustaw pole next elementu wstawianego na element currPtr;

Algorytmy i struktury danych

51

1. Utwórz element i ustal dane elementarne

int insert (NodePtr *startPtr, char nazwa) { struct Node *newPtr, *currPtr, *prevPtr; int retcode; /* Utwórz element Node */ newPtr = (struct Node *)malloc(sizeof(Node));

prevPtr

newPtr

currPtr startPtr Algorytmy i struktury danych

A

B

D

NULL 52

1. Utwórz element i ustal dane elementarne (cd.) if (newPtr == NULL) /* weryfikacja przydzielonej pamięci*/ return 1; else { /* Ustal dane elementarne w Node */ newPtr -> dane = nazwa; newPtr -> next = NULL; /* Zainicjowanie wskaźników pomocniczych */ currPtr = startPtr; /* ustaw wskaźnik na głowę listy */ prevPtr = NULL;

prevPtr

NULL

newPtr

C

currPtr startPtr Algorytmy i struktury danych

A

B

D

NULL NULL 53

2. Znajdź miejsce wstawienia elementu na listę Dopóki currPtr jest różny od NULL oraz dane elementu wstawianego są ‘większe’ od currPtr->dane: • Ustaw prevPtr na currPtr; • Przesuń currPtr na następny element listy; … /* Znajdź miejsce wstawienia */ while ((currPtr != NULL) && (nazwa > currPtr>dane)) { prevPtr = currPtr; currPtr = currPtr -> next; }

prevPtr startPtr Algorytmy i struktury danych

A

newPtr currPtr

B

C D

N ULL NULL 54

3. Wstaw element na listę if (prevPtr == NULL) /* Wstaw element jako pierwszy w liście */ { newPtr -> next = *startPtr; *startPtr = newPtr; }

prevPtr

NULL

newPtr currPtr

currPtr

startPtr

A C

Algorytmy i struktury danych

newPtr

C B A

D B

NULL NULL

D NULL 55

3. Wstaw element na listę (cd.) /* Wstaw element w miejsce między prevPtr a currPtr */ else { newPtr->next = currPtr; prevPtr->next = newPtr; } } return 0; }

prevPtr currPtr

startPtr startPtr Algorytmy i struktury danych

NULL prevPtr prevPtr

AA

newPtr newPtr

currPtr newPtr

BB

CC currPtr DD C

NULL NULL NULL

D NULL NULL 56

Algorytm dołączania elementu do listy jednokierunkowej – pełny kod int insert (NodePtr *startPtr, char nazwa) { struct Node *newPtr, *currPtr, *prevPtr; int retcode=1; /* Utwórz element Node */ newPtr = (struct Node *)malloc(sizeof(Node)); if (newPtr == NULL) /* weryfikacja przydzielonej pamięci*/ return 1; else { /* Ustal dane elementarne w Node */ newPtr -> dane = nazwa; newPtr -> next = NULL; /* Zainicjowanie wskaźników pomocniczych */ currPtr = startPtr; /* ustaw wskaźnik na głowę listy */ prevPtr = NULL; while ((currPtr != NULL) && (nazwa > currPtr->dane)) { prevPtr = currPtr; currPtr = currPtr -> next; } if (prevPtr == NULL) /* Wstaw element jako pierwszy w liście */ { newPtr -> next = *startPtr; *startPtr = newPtr; }

} }

else /* Wstaw element w miejsce między prevPtr a currPtr */ { newPtr->next = currPtr; prevPtr->next = newPtr; } return 0;

Algorytmy i struktury danych

57

Dołączanie elementu do uporządkowanej listy dwukierunkowej Uwagi: ◆

każdy element posiada dodatkowe pole (wskaźnik) prev, który dla pierwszego elementu listy jest równe NULL;

◆

lista może być przeglądana w obydwu kierunkach;

◆

często pamięta się dowiązania do pierwszego i ostatniego elementu;

◆

należy zawsze uaktualniać dowiązania w obydwu kierunkach;

Czy potrafisz dostosować zaprezentowany algorytm do list dwukierunkowych? Algorytmy i struktury danych

58

Dołączanie elementu do uporządkowanej listy jednokierunkowej cyklicznej Uwagi: ◆

brak dowiązań wskazujących na NULL;

◆

w liście jednoelementowej dowiązania wskazują na ten sam element;

◆

aby uniknąć pętli nieskończonej podczas przeglądania listy, można zastosować ‘wartownika – dowiązanie do pierwszego elementu (umownego);

Czy potrafisz dostosować zaprezentowany algorytm do list cyklicznych?

Algorytmy i struktury danych

59

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej ◆

Cel: ✦

◆

Usunięcie elementu z listy;

Dane wejściowe: ✦

Wskaźnik na pierwszy element listy startPtr;

✦

Opis usuwanego elementu, np. wartość danej elementarnej;

Algorytmy i struktury danych

60

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej

startPtr Przed usunięciem:

A

B

C

startPtr Po usunięciu: Algorytmy i struktury danych

A

B

C 61

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej 1. Jeżeli dane są zgodne z danymi pierwszego elementu listy ✦

Usuń pierwszy element listy;

2. Znajdź element do usunięcia na liście; 3. Jeżeli nie znaleziono elementu, generuj komunikat; 4. Usuń znaleziony element z listy;

Algorytmy i struktury danych

62

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej ■

Jeżeli dane są zgodne z danymi pierwszego elementu listy ■ Usuń pierwszy element listy;

int delete (NodePtr *startPtr, char nazwa) { Node *prevPtr, *currPtr, *tempPtr; if (*startPtr == NULL) /* Lista pusta */ return 1; else { if (nazwa == (*startPtr)->dane) /* Usuń pierwszy element listy */ { tempPtr = *startPtr; *startPtr = (*startPtr)->next; free (tempPtr);

Algorytmy i struktury danych

63

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej ... ◆

Znajdź na liście element do usunięcia:

… else { /* znajdź w liście element do usunięcia */ prevPtr = *startPtr; /* początek listy */ currPtr = (*startPtr)->next; /* drugi element*/ while (currPtr != NULL && currPtr -> dane != nazwa) { prevPtr = currPtr; currPtr = currPtr -> next; } Algorytmy i struktury danych

64

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej ... ◆

Znajdź element do usunięcia w liście: ✦ ✦

Jeżeli nie znaleziono elementu, generuj komunikat; Usuń znaleziony element;

… if (currPtr == NULL) return 1; /* element nie został znaleziony */ else { /* Usuń znaleziony element */ tempPtr = currPtr; prevPtr->next = currPtr->next; free (tempPtr); } } }

return 0; } Algorytmy i struktury danych

65

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej – pełny kod int delete (NodePtr *startPtr, char nazwa) { Node *prevPtr, *currPtr, *tempPtr; if (*startPtr == NULL) /* Lista pusta */ return 1; else { if (nazwa == (*startPtr)->dane) /* Usuń pierwszy element listy */ { tempPtr = *startPtr; *startPtr = (*startPtr)->next; free (tempPtr); } else { /* znajdź w liście element do usunięcia */ prevPtr = *startPtr; /* początek listy */ currPtr = (*startPtr)->next; /* drugi element*/

}

} } return 0;

Algorytmy i struktury danych

while (currPtr != NULL && currPtr -> dane != nazwa) { prevPtr = currPtr; currPtr = currPtr -> next; } if (currPtr == NULL) return 1; /* element nie został znaleziony */ else { /* Usuń znaleziony element */ tempPtr = currPtr; prevPtr->next = currPtr->next; free (tempPtr); }

66

Algorytmy i struktury danych

67