Podstawy Informatyki Wskazniki w języku C i C++ dr inż. Piotr Kaczmarek Piotr.Kaczmarek@put.poznan.pl http://pk.cie.put.poznan.pl/wyklady.php Organizacja pamięci Pamięć ma organizację komórka zmienna adres bajtową, liniową pamięci 1000 każdy bajt posiada swój 1001 0xcc 1002 indywidualny adres, który 0xdd 1003 a jest liczbą całkowitą 0xee 1004 0xff 1005 długość adresu wynosi 1006 obecnie 4 bajty (32bit) co 1007 1008 pozwala zaadresować do z 0x32 1009 4Gb pamięci 100A 100B zmienne przechowują dane w ........... kolejnych komórkach FF01 np. zmienna FF02 FF03 unsigned int a=0xffeeddcc FF04 char z='0'; Typy wskaznikowe zmienna typu wskaznikowego, komórka zmienna adres służy do przechowywania pamięci 1000 adresów innych zmiennych 1001 zmienna typu wskaznikowego, 0xcc 1002 0xdd przechowuje wartość 1003 a 0xee 1004 całkowitą, (4b), która jest 0xff 1005 adresem początku obszaru 1006 1007 pamięci w którym 1008 zlokalizowano dane z 0x32 1009 100A Przy deklaracji wskaznika, 100B zawsze trzeba określić ........... zmiennej jakiego typu będzie adres zmienn. int FF01 on dotyczył (typ* nazwa;) FF02 p1 np.: FF03 FF04 int* p1; FF05 Adres zm. float float* p2; FF06 p2 ........... char* p2; Operacje na wskaznikach Przypisanie adresu zmiennej komórka zmienna adres &a do wskaznika pamięci 1000 *p1 1001 unsigned int a=0xffeeddcc; 0xcc 1002 0xdd int* p1; 1003 a 0xee 1004 p1= &a; //adres początku 0xff 1005 1006 Zmiana wartości pod adresem 1007 1008 p1=&a wskazywanym z 0x32 1009 100A unsigned int a=0xffeeddcc; 100B int* p1; ........... p1= &a; adres zmienn. int FF01 *p1=2; //zmienna a=2 FF02 p1 1002 FF03 Uwagi: FF04 FF05 &zmianna odwołanie się do adresu zmiennej Adres zm. float FF06 *wskaznik odwołanie się do wartości p2 ........... przechowywanej pod wskazanym adresem Operacje na wskaznikach cd. Przypisanie adresu zmiennej komórka zmienna adres do wskaznika pamięci 1000 1001 char z='0'; 0xcc 1002 char* p2; 0xdd 1003 a p2= &z; 0xee 1004 *p2='a'; 0xff 1005 &z *p2 1006 1007 ile wynosi wartość: 1008 z 0x32 p2, &z, z,*p2 1009 100A 100B z 'a' p2=&z ........... *p2 'a' adres zmienn. int FF01 wartości p2 i &z są takie same (1009) FF02 p1 1002 FF03 Uwagi: FF04 FF05 &zmianna odwołanie się do adresu zmiennej 1009 FF06 *wskaznik odwołanie się do wartości p2 ........... przechowywanej pod wskazanym adresem Operacje na wskaznikach cd.. inkrementacja komórka zmienna adres pamięci char z='0'; 1000 char* p2; 1001 p2= &z; 0xcc 1002 *p2++; //inkrem. wartości 0xdd 1003 a p1++; 0xee 1004 ile wynosi wartość: 0xff 1005 p2, &z, z,*p2 *p2 1006 1007 z '1', *p2 '1' 1008 wartości p2 i &z są takie same (1009) z 0x32 ('0') 1009 p2++; 100A 100B p2++; inkrementacja adresu ........... p1++; adres zmienn. int FF01 ile wynosi wartość: FF02 p1 1002 FF03 p2, &z, z,*p2, p1 FF04 z '1', *p2 '1', FF05 &z bez zmian (1009) 1009 FF06 p2 100A (kolejny element char) p2 ........... p1 1006 (kolejny elemnet int) Operacje arytmetyczne na wskaznikach Operacje na wskaznikach mają inny komórka adres przebieg niż w zwykłej arytmetyce. pamięci 1000 Operacja dodawania lub odejmowania 1001 wsk+k 0xcc 1002 0xdd wsk-k 1003 a p1++; 0xee 1004 oznacza: przejdz o k elementów, stąd 0xff 1005 adres wynikowy zależy od rozmiaru 1006 1007 wskazywanej zmiennej: 1008 z 0x32 ('0') 1009 p2++; 100A int* p1=1002; 100B char* p2=1009; p2=p2+1;// adres wynosi 100A (char - 1b) ........... adres zmienn. int FF01 p1=p1+1;//adres wynosi 1006 (int - 4b) FF02 p1 1002 FF03 FF04 FF05 Uwaga: 1009 FF06 To o ile zmienia się wartość adresu p2 ........... determinowane jest przez typ wskaznika. Referencje Zmienne tworzona jako referencja komórka adres przechowuje wartość w tym *p1, pamięci *p2 1000 samym obszarze pamięci 1001 int a=1; 0x01 1002 a 0x00 int&b=a; // b jest referencją a 1003 0x00 1004 b int* p1, p2; 0x00 1005 p1=&a; 1006 1007 p2=&b; 1008 z 0x32 ('0') ile wynoszą wartości: 1009 100A p1,p2, &a, &b, p1,p2,a,b 100B p1,p2,&a,&b mają tą samą wartość (1002) ........... p1,p2,a,b mają wartość 1; adres zmienn. int FF01 FF02 p1 1002 FF03 FF04 FF05 1002 FF06 p2 ........... Wykorzystanie wskazników p1 int a=2, b=3; a 2 int* p1, p2; c p2 int& c=a; b 3 p1=&a; p2=&b; *p1=*p2; b++; p2=p1; *p2++; ile wynosi wartość: c++; a ,b, c, *p1, *p2 p1, p2, &a, &b, &c Wykorzystanie wskazników p1 int a=2, b=3; a 3 *p1 int* p1, p2; c p2 int& c=a; b 3 *p2 p1=&a; p2=&b; *p1=*p2; odwołanie się do wartości we wskazywanej komórce b++; p2=p1; *p2++; ile wynosi wartość: c++; a ,b, c, *p1, *p2 p1, p2, &a, &b, &c Wykorzystanie wskazników p1 int a=2, b=3; a 3 *p1 int* p1, p2; c p2 int& c=a; b 4 *p2 p1=&a; p2=&b; *p1=*p2; b++; p2=p1; *p2++; ile wynosi wartość: c++; a ,b, c, *p1, *p2 p1, p2, &a, &b, &c Wykorzystanie wskazników p1 int a=2, b=3; a 3 *p1 int* p1, p2; c p2 int& c=a; b 4 *p2 p1=&a; p2=&b; *p1=*p2; b++; przypisanie do p1 adresu p2 p2=p1; *p2++; ile wynosi wartość: c++; a ,b, c, *p1, *p2 p1, p2, &a, &b, &c Wykorzystanie wskazników p1 int a=2, b=3; a 5 *p1 int* p1, p2; c p2 int& c=a; b 4 *p2 p1=&a; p2=&b; *p1=*p2; b++; p2=p1; *p2++; ile wynosi wartość: c++; a ,b, c, *p1, *p2 p1, p2, &a, &b, &c Wykorzystanie wskazników p1 int a=2, b=3; a 3 *p1 int* p1, p2; c p2 int& c=a; b 4 *p2 p1=&a; p2=&b; *p1=*p2; b++; przypisanie do p1 adresu p2 p2=p1; *p2++; c++; Tablice i wskazniki float tab[5]; tablica jest ciągłym obszarem pamięci, w for(i=0;i<5;i++) którym kolejno umieszczone są wartości tab[i]=0.5*i; elementów zmienna tab jest wskaznikiem (typ float*) do pierwszego elementu tablicy nr stąd *tab, odwołuje się do wartości adres tabelementu elementu 0 k 0.0 0 natomiast tab+i, jest adresem i-tego k+6 *tab 1 0.5 elementu tablicy, a *(tab+i) odwołuje się k+12 *(tab+1) do wartości i-tego elementu tablicy. 2 1.0 k+18 3 1.5 stąd operacja : tab+4 k+24 2.0 tab[i] = 0.5*i; 4 jest tożsama operacji: *(tab+i) = 0.5*i; Wskazniki jako argument funkcji Zastosowanie wskazników pozwala na tworzenie funkcji przekazujących na zewnątrz więcej niż jedną wartość Przekazanie argumentów Przekazanie argumentów Przekazanie argumentów przez wartość przez wskaznik przez referencję void Zamien(int a,int b) void Zamien(int *a,int *b) void Zamien(int& a,int& b) { { { int t=a; int t=*a; int t=a; a=b; *a=*b; a=b; b=t; *b=t; b=t; } } } int main int main int main int main { { { { int x=2,y=3; int x=2,y=3; int x=2,y=3; int x=2,y=3; Zamien(x,y); Zamien(x,y); Zamien(&x,&y); Zamien(x,y); } } } } x,y nie zmieniają wartości x,y zmieniają swoje wartości Wskazniki jako argument funkcji Przekazując argument przez wartość (void Zamien(int a, int b)) przy każdym wywołaniu funkcji tworzone są lokalne zmienne a,b i przypisywana jest im wartość argumentów Czas wywołania funkcji oraz ilość pamięci rezerwowanej dla argumentów jest zależny od typu argumentu (musi zostać skopiowana pewna ilość bajtów z zmiennej przekazanej jako argument do zmiennej lokalnej) Przekazując argument jako wskaznik (void Zamien(int *a, int *b)) przy każdym wywołaniu funkcji tworzone są lokalnie zmienne wskaznikowe a i b i przypisywana jest im wartość adresów argumentów wejściowych (po 4 bajty na adres) Czas wywołania i ilość pamięci zajmowane przez argumenty funkcji jest więc niezależny od typu argumentów Wszystkie operacje modyfikujące wartość wskazywaną przez a lub b będą miały swoje odzwierciedlenie na zewnątrz funkcji Przekazanie argumentu przez referencję, działa tak jak przekazanie argumentu przez wskaznik, z tym że nie ma etapu kopiowania adresu (metoda ta jest najszybsza) Ochrona argumentów przed zmianami Przekazanie argumentów przez wskaznik lub referencję pozwala na zwiększenie szybkości wywoływania funkcji (szczególnie w przypadku argumentów o dużym rozmiarze) Może to jednak powodować że nastąpi zmiana argumentów przekazanych do funkcji (co nie zawsze jest pożądane) Zapewnić że argumenty nie zostaną zmodyfikowane przekazując je jako referencję do stałej void SzybkaFunkcja(const int& X) void SzybkaFunkcja(const int* X) { { int a=X; //ok int a=*X; //ok X=1;//błąd zmienna tylko do odczytu *X=1;//błąd zmienna tylko do odczytu } } Dynamiczny przydział pamięci Pamięć dla zmiennych i tablic deklarowanych w sposób pokazywany poprzednio jest przydzielona w chwili gdy program napotyka deklarację zmiennej: { float a; int tab[100]; char znak; ... } Rozmiar zmiennej (np. tablicy) musi być znany już w chwili uruchamiania programu. Konieczne jest więc deklarowanie tablic większych niże maksymalny rozmiar wprowadzony przez użytkownika. Zmienne automatyczne istnieją od momentu deklaracji do końca zasięgu ich widoczności. Program sam przydziela i zwalnia pamięć Dynamiczny przydział pamięci cd.. Pamięć może być również przydzielana komórka adres ręcznie przez użytkownika: pamięci przez zastosowanie operatora new. 1000 wsk; 1001 Składnia ma postać: 1002 typ* wsk = new typ; 1003 1004 float *wsk; 1005 wsk=new float; 1006 1007 *wsk = 6.0; 1008 1009 przydzielony blok nie ma stowarzyszonej 100A żadnej zmiennej automatycznej i istnieje 100B do czasu aż użytkownik uwolni ........... przydzieloną pamięć. Składnia ma adres zmienn. int FF01 postać: delete wskaznik; FF02 wsk 1002 FF03 FF04 delete wsk; FF05 FF06 ........... Przydział pamięci dla tablic w programie można uzależnić ilość przydzielanej pamięci od aktualnego zapotrzebowania. rezerwacja pamięci dla tablicy o N elementach ma postać: typ* wsk=new typ[N]; float *pTab; int N; cout<< Ile elementów chcesz wprowadzić? ; cin>>N; pTab=new float[N]; for(int i=0;i>pTab[i]; //lub cin>>*(pTab+i); Zwolnienie pamięci dla tablicy odbywa się za pomocą operatora delete[] delete[] pTab; Uwaga: delete pTab; //zwolnienie pamięci elementu 0 tablicy!!! Weryfikacji prawidłowego przydziału pamięci Sprawdzenie poprawności przydzielenia pamięci jest istotne szczególnie przy tworzeniu tablic o dużych rozmiarach. przy stosowaniu operatora new, jeśli można zarezerwować żądany przez użytkownika blok pamięci zwracany jest jego adres, w innym przypadku, operator new nie zwraca żadnej wartości Stąd można zastosować następującą procedurę sprawdzania: int N; float *pTab = null; cin>>N; pTab=new float[N]; if(pTab==null) { cout<< blad przydzialu ; exit(-1); } .... // pamięć przydzielona OK Przydział pamięci cd. Można stworzyć funkcje dedykowaną do przydziału pamięci, której zadaniem będzie sprawdzenie poprawności przydziału float* PrzydzielPamiec(int N) { float *pTab = null; cin>>N; pTab=new float[N]; if(pTab==null) { cout<< blad przydzialu ; exit(-1); } return pTab; } Użycie (wywołanie) będzie miało postać: int n; cin>>n; float* tab=PrzydzielPamiec(n); .... Grupowanie zmiennych Często pewien obiekt jest opisywany nie przez jedną zmienną, ale przez pewien zestaw w celu przechowania danych osoby w programie należy zdefiniować kilka zmiennych: char imie_nazwisko[25]; int wiek; char plec; aby dodaś kolejną osobę należy stworzyć kolejne zmienne char imie_nazwisko1[25]; int wiek1; char plec1; Struktury Struktury są typami umożliwiającymi grupowanie zmiennych. struct sNazwa { typ pole1; typ pole 2; typ pole 3; }; Struktura służąca do przechowywania danych osoby: struct sOsoba { char Imie_Nazwisko[25]; int wiek; char plec; }; Uwaga: definicja typu strukturalnego powinna znajdować się w pliku nagłówkowym Struktury - wykorzystanie Można zadeklarować zmienną typu strukturalnego sOsoba student; Do odwołania się do konkretnego pola struktury stosuje się operator '.' cout<< Wprowadz imię i nazwisko ; cin.getline(student.Imie_Nazwisko,25); cout<< Podaj wiek ; cin>>student.wiek; cout<< Podaj plec ; cin>>student.plec; Tablice struktur - wykorzystanie W celu przechowania wielu osób można zadeklarować tablicę: sOsoba studenci[50]; Do odwołania się do konkretnego pola struktury stosuje się operator '.' for(int i=0; i<50; i++) { cout<< Wprowadz imię i nazwisko ; cin.getline(studenci[i].Imie_Nazwisko,25); cout<< Podaj wiek ; cin>>studenci[i].wiek; cout<< Podaj plec ; cin>>studenci[i].plec; } Wskazniki do struktur Wskazników do struktur używa się tak jak innych wskazników do typów wbudowanych wsk sOsoba student1,student2; sOsoba* wsk; Imie_Nazwisko wsk = &student1; Student1 wiek plec Odwołanie do pól struktury (selektor Imie_Nazwisko Student2 '.') wiek plec *wsk.wiek=16; cin.getline(*wsk.Imie_Nazwisko,25); Bardziej poprawne odwołanie do pól struktury, dla wskazników (selektror ->) wsk->wiek=16; cin.getline(wsk->Imie_Nazwisko,25); Funkcje operujące na strukturach Zmienna typu strukturalnego może być przekazywana do funkcji tak jak zmienna wbudowana void Wyswietl(sOsoba* O) { cout<Imie_Nazwisko<<< wiek: <Wiek<<< plec: <plec<} Przekazanie adresu zmiennej pozwala przyspieszyć czas wykonywania funkcji (pola nie są kopiowane) sOsoba student; .... Wyswietl(&student); Przydział pamięci do struktur Przydział pamięci dla pojedynczej zmiennej strukturalnej, wygląda analogicznie jak dla typów wbudowanych sOsoba* wsk; wsk = new sOsoba; .... delete wsk; Przydział pamięci dla tablic struktur sOsoba* pOsoby; int N; cout<< ile osób chcesz wprowadzic ; cin>>N; pOsoby = new sOsoba[N]; .... delete[] pOsoby; Wady stosowania tablic struktur kopiowanie 2 elementów: Dodawanie/usuwanie elementów sOsoba o1,o2; stworzyć nową tablicę o właściwym ... rozmiarze, strcpy(o1.ImieNazwisko, przekopiować wszystkie elementy ze o2.imieNazwisko); o1.wiek=o2.wiek; starej tablicy do nowej o1.plec=o2.plec; (dodając/usuwając pewne elementy) usunąć starą tablicę Aby przestawić 2 elementy (np. przy sortowaniu) w tablicy należy zapamiętać pierwszy element w Uwaga: elemencie tymczasowym (skopiować struktury mogą wszystkie jego pola) zajmować dużo miejsca przypisać wartości pół 2 elementu do 1 w pamięci, stąd operacja elementu kopiowania elementów jest czasochłonna i może przypisać wartość elementu pochłaniać wiele zasobów tymczasowego do 2 elementu Listy dynamiczne Tablice wymagały przydzielenia ciągłego obszaru pamięci, stąd każda modyfikacja wiązała się z ingerencją w zawartość całej tablicy Zastosowanie struktur dynamicznych tj. Listy pozwala ominąć ten problem. Rozpatrzmy strukturę umożliwiającą zaimplementowanie wytworzenie listy dwukierunkowej: struct sOsoba { char Imie_Nazwisko[25]; int wiek; char plec; sOsoba* N;//nastepny element sOsoba* P;//poprzedni element }; Pola N i P przechowują adresy następnego i poprzedniego elementu listy. Wartość NULL tego pola oznacza, że nie istnieje następny (aktualny element jest ostatni) lub poprzedni element (aktualny element jest pierwszy. Dodawanie elementów do listy Załóżmy że zmienna sOsoba *root przechowuje adres pierwszego elementu listy sOsoba *root; root root = new sOsoba; osoba osoba N null root->N=null;//ostatni element P null root->P=null; //pierwszy element dodawanie kolejnego elementu d listy sOsoba* nowy=new sOsoba root nowy->P=root; osoba osoba root->N=nowy; N nowy->N=null; //ostatni element P null osoba nowy N null P Poszukiwanie ostatniego elementu na liście Ostatnim elementem na liście jest ten, którego pole N ma wartość null. Poniższa funkcja poszukuje ostatniego elementu na liście i zwraca jego adres. sOsoba* Ostatni(sOsoba* root) { sOsoba* aktualny=root; while(aktualny->N != null) { aktualny = aktualny->N; } return aktualny; } root osoba osoba osoba osoba osoba osoba osoba osoba N N N N null P P P null P Dodawanie elementu na końcu listy Aby dodać element na końcu listy należy odszukać element ostatni przydzielić pamięć dla nowego elementu zaktualizować pola N i P nowego i ostatniego elementu //dodawanie elementu sOsoba *koniec=Ostatni(root); sOsoba *nowy=new sOsoba; koniec->N=nowy; nowy->P=koniec; nowy->N=null; root osoba osoba osoba osoba osoba osoba osoba koniec N N N N null osoba null nowy P P P null P N P Przeszukiwanie listy Wyświetlić osoby, których wiek wynosi 28 lat; sOsoba* aktualny=root; int wiek =28; while(aktualny != null) // przechodzi do pierwszego do ostatniego elementu { if(aktualny->wiek==wiek) Wyswietl(aktualny)l aktualny = aktualny->N; } root osoba osoba osoba osoba osoba osoba osoba osoba N N N N osoba osoba null P P P null P N P Przestawianie 2 elementów sOsoba* E1;E2,Po,Na Aby przestawić 2 sąsiednie elementy należy ... określić adresy tych elementów E2=E1->N; zmienić wartości pól elementów poprzedzających Po=E1->P; Na=E2->N; i następujących Po->N=E2; E2->P=Po; osoba E2 Na->P=E1; N P E1->N=Na root E1->P=E2; osoba Po E2->N=E1; N P null osoba E1 N P osoba Na N P Usuwanie elementów z listy Aby usunąć element o adresie E1 sOsoba* E1;Po,Na Określić adresy elementów poprzedniego i ... następnego Po=E1->P; Zaktualizować pole N poprzednika tak by Na=E1->N; wskazywało adres elementu następnego Po->N=Na; Zaktualizować pole P el. następnego tak by Na->P=Po; wskazywało adres elementu poprzedniego uwolnić pamięć dla obiektu E1 delete E1; root osoba Po E1 osoba osoba osoba osoba Na N N N N osoba osoba null P P P null P N P