POLITECHNIKA WARSZAWSKA
POLITECHNIKA WARSZAWSKA
Instytut Automatyki i Robotyki
Instytut Automatyki i Robotyki
ZASADY PROGRAMOWANIA KOMPUTERÓW
ZASADY PROGRAMOWANIA KOMPUTERÓW
Język programowania: C/C++
Język programowania: C/C++
Środowisko programistyczne: C++Builder 6
Środowisko programistyczne: C++Builder 6
Wykład 10 . Tablice dynamiczne - c.d. Listy jednokierunkowe.
Wykład 10 . Tablice dynamiczne - c.d. Listy jednokierunkowe.
Tablice dwuwymiarowe w notacji wskaz
nikowej
Tablice dwuwymiarowe w notacji wskaz
nikowej
A[0][0]
zawartość
elementu tablicy
**A
Dynamiczna rezerwacja tablic dwuwymiarowych
Dynamiczna rezerwacja tablic dwuwymiarowych
int main( ) { // zarezerwujemy tablicę A typu double
double **A ; // A jest wskaz
nikiem do wskaz
nika
int w, k; // pierwszego elementu tablicy
cout << "ile wierszy i kolumn ? " << endl;
cin >> w >> k; // ma być w wierszy i k kolumn
A = new double *[w]; // rezerwujemy pamięć dla tablicy w wskaz
ników
// i adres pierwszego z nich zapamiętujemy jako A
for (int i = 0; i < w; i++) przydzielamy pamięć na kolejne tablice
A[i] = new double [k]; jednowymiarowe (wiersze tablicy dwuwymiar.)
i adresy ich wpisujemy do kolejnych elementów A[i]
...
A[i] [j] =0; // wykonujemy zwykłe działania na tablicy
...
for (int i = 0; i < w; i++) zwalniamy pamięć
delete [ ] A[i]; na kolejne tablice jednowymiarowe
delete [ ] A; // zwalniamy pamięć na tablicę wskaz
ników
...
return 0;
}
Tablice i arytmetyka wskaz
ników
Tablice i arytmetyka wskaz
ników
int T[n]; // tym razem tablica statyczna
*T=8; // równoważne T[0]=8;
*(T+1)=6; // równoważne T[1]=6;
T++; // ale tak nie wolno, bo tablica T jest statyczna
... // i jej nazwa zawsze przechowuje adres T[0]
int *wt; //dodatkowy wskaz
nik
wt=T; // czyli wt=&T[0];
wt++; // tak można; teraz wskaz
nik przesunął się do
Dodając i odejmując od
//następnego elementu tablicy
wskaz
ników liczby
cout << *wt; // wydrukuje się 6
naturalne możemy
bardzo szybko
int B[w] [k]; // tablice statyczne
przemieszczać się po
double **A ; // tablica dynamiczna
tablicy
**B=3; // równoważne B[0][0]=3;
*(*B+1)=7; // równoważne B[0][1]=7;
**(B+1)=4; // równoważne B[1][0]=4
... // tu trzeba przydzielić pamięć na tablicę A
**A=5; // równoważne A[0][0]=5;
*(*A+3)=4; // równoważne A[0][3]=4;
A++; // można nawet tak, ale to niebezpieczne
**A=12; // teraz to jest równoważne A[1][0]=12;
Tablice statyczne i dynamiczne jako parametry funkcji
Tablice statyczne i dynamiczne jako parametry funkcji
w obu przypadkach, mimo braku &, funkcja
using namespace std;
działa na oryginalnej tablicy będącej
const int w = 3; const int k = 4;
parametrem aktualnym funkcji (to pozwala
void czyt_stat (int X[ ][k]) {
tablicę zmienić, tzn. wczytać)
// wczytujemy dane do tablicy statycznej
...
int main( ) { const ...;
cin >> X[i][j];
int A[w] [k]; // tablica statyczna
}
int **B ; // tablica dynamiczna
void czyt_dyn (int **X) {
czyt_stat (A);
// wczytujemy dane do tablicy dynamicznej
druk_stat (A);
...
Uwaga: ten sposób podawania
...
parametrów często jest stosowany
cin >> X[i][j];
również do tablic statycznych
// wczytujemy rozmiary tablicy B
}
czyt_dyn (B);
void druk_stat (const int X[ ][k]) {
druk_dyn (B);
// drukujemy zawartość tablicy statycznej
...
...
return 0;
cout << X[i][j];
}
}
modyfikator const zabezpiecza przed zmianą
void druk_dyn (int **X) {
zawartości tablicy będącej parametrem
// drukujemy zawartość tablicy dynamicznej
aktualnym funkcji i warto go stosować
...
(ale nie działa on dla tablic dynamicznych
cout << X[i][j];
dwuwymiarowych jako parametrów funkcji)
}
Listy dowiązaniowe jednokierunkowe
Listy dowiązaniowe jednokierunkowe
Są przykładem struktur dynamicznych o dowolnej długości. Lista
jednokierunkowa zbudowana jest następująco z powiązanych ze
sobą elementów:
Elementy listy są rekordami, w których co najmniej jedno pole
zawiera wskaz
nik na rekord następny.
Zmienna glowa (nazwa może być dowolna) jest adresem początku
listy.
Stała NULL (typu wskaz
nikowego) oznacza adres pusty (żaden);
wskazuje, że dalej już nic nie ma (nie istnieje rekord następny).
Pamiętanie wskaz
nika ogon nie jest potrzebne (wiadomo, że ogon
jest tam, gdzie NULL), ale może być pożyteczne.
Różne typy list dowiązaniowych
Różne typy list dowiązaniowych
Lista dowiązaniowa jest
zestawem powiązanych ze sobą,
nieciągłych fragmentów
(zmiennych dynamicznych)
umieszczonych w różnych
obszarach pamięci wirtualnej
komputera - w przeciwieństwie
do tablic, które zajmują ciągły
obszar pamięci.
Użytkownik może przeglądać listę jednokierunkową jedynie w
jednym kierunku - od początku do końca, nie ma natomiast żadnej
możliwości, aby się cofnąć. Aby uniknąć tego ograniczenia,
można dodać drugie pole na wskaz
nik do elementu poprzedniego,
umożliwiając w ten sposób przeglądanie listy w obu kierunkach
(lista dwukierunkowa). Czasami stosuje się też połączenie
pierwszego elementu z ostatnim - uzyskuje się w ten sposób listę
cykliczną (jedno- lub dwukierunkową).
Aplet do operacji na liście jednokierunkowej
Aplet do operacji na liście jednokierunkowej
* Dodaj - dodawanie nowego elementu po wyróżnionym elemencie
* Dodaj po - dodawanie nowego elementu po wyróżnionym elemencie wraz
z przesunięciem wyróżnienia do następnego elementu (umożliwia
dodawanie elementów na końcu listy)
* Usuń - usuwanie elementu leżącego za wyróżnionym elementem
* Przesuń - przesunięcie wyróżnienia elementu do następnego elementu
* Powrót - powrót na początek listy
* Nowa - tworzenie nowej listy od początku.
Autor apletu (projekt i implementacja w Javie): Jakub Krzesłowski, gr. R41, listopad 2006.
Poruszanie się po liście
Poruszanie się po liście
struct Telement {
int dane;
Definicja struktury tworzącej listę
Telement *next;
};
Adres bieżącego elementu listy musi być wpisany w polu next
poprzedniego elementu listy. Wówczas z elementu do elementu
przesuwamy się za pomocą instrukcji:
adres=adres->next;
Drukowanie zawartości listy
Drukowanie zawartości listy
Drukowanie zawartości listy
// funkcja iteracyjna
void drukuj_liste_it (Telement *adres) {
while (adres !=NULL) { // dopóki to nie koniec listy
cout << adres->dane << " "; // wypisujemy zawartość elementu
adres = adres->next; // i przechodzimy do el. następnego
}
}
Funkcja drukuje zawartość listy zaczynającej się pod jakimś
adresem adres
// funkcja rekurencyjna
void drukuj_liste_rek (Telement *adres) {
if (adres != NULL) { // jeśli to nie koniec listy
cout << adres->dane << " "; // wypisujemy zawartość elementu
drukuj_liste_rek (adres ->next); // i funkcja wywołuje samą siebie
// dla następnego elementu
}
} UWAGA: zamiast
warunku (adres!=NULL)
zmieniając kolejność tych dwu instrukcji możemy listę
można napisać po prostu
wydrukować od końca
(adres), np. if (adres)
Schemat  tworzenie listy odwrotnej
Schemat  tworzenie listy odwrotnej
Początek
glowa
NULL
Pierwszy element
Funkcja wczytuje liczby całkowite aż do
aktualny glowa
napotkania zera i tworzy z nich listę w
kolejności odwrotnej do wczytywania.
NULL
liczba
dane
Adres początku utworzonej listy
zapamiętuje jako parametr glowa.
next
NULL
Kolejne elementy
aktualny glowa
liczba liczba liczba
dane
. . .
next
NULL
Tworzenie listy odwrotnej - przykład
Tworzenie listy odwrotnej - przykład
Funkcja wczytuje liczby całkowite aż do napotkania zera i tworzy z nich listę
w kolejności odwrotnej do wczytywania. Adres początku utworzonej listy
zapamiętuje jako parametr glowa
(dlatego musi być on przekazywany przez referencję).
void utworz_liste_odwrotna (Telement *&glowa) {
Telement *aktualny;
int liczba;
glowa = NULL; // na początku lista jest pusta
cout << "Wprowadz ciag liczb calkowitych zakonczony zerem \n";
cin >> liczba; // wczytujemy 1-szą liczbę
while (liczba!=0) { // dopóki nie wczytano zera
aktualny = new Telement; // przygotowujemy miejsce dla nowego elementu
aktualny->dane = liczba; // wpisujemy wczytaną liczbę do pola dane
aktualny->next = glowa; // element następny to ten, co przedtem był głową
glowa = aktualny; // element aktualny staje się teraz głową
cin >> liczba; // wczytujemy kolejną liczbę
}
}
kierunek dodawania elementów
Schemat - tworzenie listy prostej
Schemat - tworzenie listy prostej
glowa ogon
Początek
NULL NULL
Pierwszy element
glowa ogon
Funkcja wczytuje liczby całkowite aż do
napotkania zera i tworzy z nich listę w
NULL
liczba
dane
kolejności wczytywania. Adres
początku utworzonej listy zapamiętuje
next
jako parametr glowa.
NULL
Kolejne elementy
glowa
ogon aktualny
liczba
liczba liczba
dane
. . .
next
NULL NULL
Tworzenie listy prostej
Tworzenie listy prostej
Funkcja wczytuje liczby całkowite aż do
void utworz_liste (Telement *&glowa) {
napotkania zera i tworzy z nich listę w
Telement *aktualny, *ogon;
kolejności wczytywania. Adres początku
int liczba;
utworzonej listy zapamiętuje jako
aktualny = NULL;
parametr glowa.
glowa = NULL;
cout << "Wprowadz dane calkowite, 0 konczy wpisywanie\n";
cin >> liczba; // wczytujemy 1-szą liczbę
while (liczba !=0) { // dopóki nie wczytano zera
ogon = aktualny; // zapamiętujemy dotychczasowy koniec listy
aktualny = new Telement; // tworzymy miejsce dla nowego elementu
aktualny->dane = liczba; // zapisujemy do niego odczytane dane
aktualny->next = NULL; // i wpisujemy NULL
// bo teraz jest to nowy ogon listy
if (ogon == NULL) // jeśli nowy element to pierwszy element listy
glowa = aktualny; // to staje się on głową
else // a jeśli nie, to doczepiamy go do starego ogona:
ogon->next = aktualny;
cin >> liczba;
}
}
kierunek dodawania elementów
Szkielet całego programu - tworzenie i drukowanie listy
Szkielet całego programu - tworzenie i drukowanie listy
using namespace std;
struct Telement {
int dane;
Telement *next; // te nazwy nie mają znaczenia - mogą być dowolne
};
void utworz_liste (Telement *&glowa) { // parametr glowa jest przekazywany
// przez referencję
... // treść funkcji
}
void drukuj_liste (Telement *adres) { // parametr adres jest przekazywany
// przez wartość
... // treść funkcji
}
int main( ) {
Telement *glowa; // deklaracja wskaz
nika
utworz_liste (glowa); // glowa zmieni się po wywołaniu funkcji (i o to chodzi)
drukuj_liste (glowa); // a tu się nie zmieni (i dobrze !)
getchar();
return 0;
}
Wersja z funkcją zwracającą głowę
Wersja z funkcją zwracającą głowę
using namespace std;
struct Telement {
int dane;
Telement *next;
};
Telement *utworz_liste ( ) { // funkcja jest teraz typu wskaz
nikowego
Telement *glowa, *aktualny, ...; // glowa jest zmienną lokalną typu wskaz
nikowego
... // treść funkcji
return glowa;
}
void drukuj_liste (Telement *adres) {
... // treść funkcji
}
int main( ) {
Telement *glowa; // deklaracja wskaz
nika glowa
glowa = utworz_liste (); // zapamiętujemy glowę zwróconą przez funkcję
drukuj_liste (glowa); // i od niej zaczynamy drukowanie
getchar();
return 0;
}