UCZELNIA WARSZAWSKA
Kierunek INFORMATYKA I EKONOMETRIA
Programowanie komputerów
r.a. 2007/2008
Prowadzący: dr hab. in\
. Kazimierz Worwa, prof. UW MSC
Lokalizacja plików do wykładów
http://members.lycos.co.uk/pkjw84/kw/
logowanie:
nazwa u\
ytkownika 2007/2008
hasło kw
2
Programowanie komputerów
Wykład 5: Wskaz
nikowe typy danych
Dokończenie wykładu 4: podstawowe algorytmy sortowania
podstawy typów wskaz
nikowych
operatory wskaz
nikowe
wskaz
niki a typy tablicowe i napisy
3
Programowanie komputerów
Metody sortowania wewnętrznego
Podstawowe algorytmy sortowania
Sortowanie przez wstawianie (ang. insertion sort)
Sortowanie przez wybieranie (selekcję) (ang. selection sort)
Sortowanie przez zamianę (bąbelkowe) (ang. exchange sort, bubble sort)
Efektywne algorytmy sortowania
Sortowanie przez kopcowanie (ang. heap sort)
Sortowanie metodą malejących przyrostów (Shella)
Sortowanie szybkie (ang. quicksort)
Sortowanie przez scalanie (ang. merge sort)
Klucze
44 55 12 42 94 18 06 67
początkowe
4
Programowanie komputerów
Sortowanie przez wstawianie
Klucze
44 55 12 42 94 18 06 67
początkowe
K
i = 2
44 55 12 42 94 18 06 67
r
o
k i = 3
12 44 55 42 94 18 06 67
i
i = 4
12 42 44 55 94 18 06 67
a
l
i = 5
g 12 42 44 55 94 18 06 67
o
r
12 18 42 44 55 94 06 67
i = 6
y
t
i = 7
06 12 18 42 44 55 94 67
m
u
i = 8
06 12 18 42 44 55 67 94
5
Programowanie komputerów
Idea algorytmu sortowania przez wstawianie
void InsertionSort (int tab[ ], int n)
{
for ( i=1; i{
przesuń wszystkie elementy tab[j] większe od tab[i] o jedną pozycję;
umieść tab[i] w odpowiednim miejscu;
}
}
6
Programowanie komputerów
Przykładowy algorytm sortowania przez wstawianie
void InsertionSort (int tab[ ], int n)
{
for ( int i=1, j; i{
int temp=tab[i];
for (j=i; j>0 && temptab[j]= tab[j-1];
tab[j]=temp;
}
}
Program 4.9
7
Programowanie komputerów
Sortowanie przez wybieranie
Klucze
K 44 55 12 42 94 18 06 67
początkowe
r
o
i = 2
06 55 12 42 94 18 44 67
k
i
i = 3
06 12 55 42 94 18 44 67
a
l
i = 4
g 06 12 18 42 94 55 44 67
o
r
i = 5
06 12 18 42 44 55 94 67
y
t
m
i = 6
06 12 18 42 44 55 67 94
u
8
Programowanie komputerów
Idea algorytmu sortowania przez wybieranie
void SelectionSort (int tab[ ], int n)
{
for (i=0; i{
wybierz najmniejszy element spośród tab[i], ..., tab[n-1];
zamień wybrany element z tab[i];
}
}
9
Programowanie komputerów
Przykładowy algorytm sortowania przez wybieranie
void SelectionSort (int tab[ ], int n)
{
int i, least, j;
for ( i=0; i{
for (j=i+1, least=i; jif (tab[j] < tab[least])
least=j;
// zamiana (tab[least], tab[i]);
int temp= tab[least];
tab[least] = tab[i];
tab[i ]=temp;
}
Program 4.10
}
10
Programowanie komputerów
Przykładowy algorytm sortowania przez wybieranie
void SelectionSort (int tab[ ], int n)
???
{
for (int i=0, least, j; i{
for (j=i+1, least=i; jif (tab[j] < tab[least])
least=j;
// zamiana (tab[least], tab[i]);
int temp= tab[least];
tab[least] = tab[i];
tab[i ]=temp;
}
}
11
Programowanie komputerów
Sortowanie przez zamianę (bąbelkowe)
K r o k i a l g o r y t m u
Klucze
i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8
początkowe
44 06 06 06 06 06 06 06
55 44 12 12 12 12 12 12
12 55 44 18 18 18 18 18
42 12 55 44 42 42 42 42
94 42 18 55 44 44 44 44
18 94 42 42 55 55 55 55
06 18 94 67 67 67 67 67
67 67 67 94 94 94 94 94
12
Programowanie komputerów
Idea algorytmu sortowania przez zamianę
void BubbleSort (int tab[ ], int n)
{
for (i=0; ifor (j=n-1; j>i; j--)
jeśli kolejność elementów j oraz j-1 jest
niewłaściwa, zamień je miejscami;
}
13
Programowanie komputerów
Przykładowy algorytm sortowania przez zamianę
void BubbleSort (int tab[ ], int n)
{
for (int i=0; ifor (int j=n- --)
-1; j>i; j--
- --
- --
if (tab[j]-1])
-
-
{
// zamiana (tab[j -
-1] , tab[j ])
-
-
int temp= tab[j -
-1];
-
-
tab[j -
-1] = tab[j ];
-
-
tab[j ]=temp;
}
}
Program 4.11
14
Programowanie komputerów
Podstawy typów wskaz
nikowych
Zmienna typu wskaz
nikowego (wskaz
nik) jest zmienną przechowującą
adres do innego obiektu (zmiennej) w pamięci operacyjnej
Wskaz
niki mają określoną specjalną arytmetykę wskaz
ników, dzięki
którym mo\
na w stosunkowo łatwy sposób operować na adresach w
pamięci operacyjnej
Wskaz
nik Zmienna
Adres Wartość
15
Programowanie komputerów
Wskaz
niki - podstawy
Deklaracja wskaz
nika:
typ *nazwa;
Przykłady:
int *wsk1;
char *wsk2;
16
Programowanie komputerów
Operatory wskaz
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
W wyniku powy\
szego przypisania zmienna m będzie miała wartość
2000, tzn. zmienna m otrzymuje adres zmiennej count
17
Programowanie komputerów
Operatory wskaz
nikowe: * oraz &
Jednoargumentowy operator * zwraca wartość zmiennej,
znajdującej się pod adresem następującym po operatorze
Jeśli zmienna m zawiera adres zmiennej count to instrukcja
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
18
Programowanie komputerów
Wskaz
niki - podstawy
Zadanie
Napisać program wypisujący na ekranie liczbę 100 z u\
yciem
wskaz
nika na liczbę typu int.
19
Programowanie komputerów
Wskaz
niki - podstawy
Sposób 1
#include
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 wskaz
nika */
return 0;
}
20
Programowanie komputerów
Wskaz
niki - podstawy
Sposób 2
#include
int main(void)
{
int *p, q;
p = &q; /* pobranie adresu q */
*p = 100; /* przypisanie wartości q z wykorzystaniem wskaz
nika */
printf( wartośćią q jest %d", q);
return 0;
}
21
Programowanie komputerów
Wskaz
niki - podstawy
Przykład niepoprawnego wykorzystania wskaz
nika
int main(void)
{
int *p;
/* niepoprawnie - p jeszcze na nic nie wskazuje! */
*p = 10;
}
22
Programowanie komputerów
Wskaz
niki - podstawy
Oprócz operatorów * i & istnieją tylko cztery inne operatory,
które mo\
na stosować ze wskaz
nikami: +, ++, -, --.
Operator ++ zwiększa adres, na który wskazuje wskaz
nik o jedną długość
typu wskaz
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.
23
Programowanie komputerów
Wskaz
niki - podstawy
Aby otrzymać wartość o jeden większą od wskazywanej przez wskaz
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 wskaz
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).
24
Programowanie komputerów
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 */
25
Programowanie komputerów
Rzutowanie typów
Ta sama zasada dotyczy rzutowania wskaz
ników
Załó\
my, \
e mamy:
int *iptr;
float *fptr;
Aby przypisać wskaz
nik do liczby całkowitej iptr wskaz
nikowi do liczby
zmiennoprzecinkowej fptr, piszemy:
fptr=(float *) iptr;
26
Programowanie komputerów
Wskaz
niki a typy tablicowe
Język C w sposób wyjątkowy uto\
samia wskaz
niki i tablice
W wyniku deklaracji zmiennej tablicowej, środowisko języka C
tworzy wskaz
nik na początek tej tablicy. Miejsca na pozostałe
elementy tablicy są zajmowane w zale\
ności od rozmiaru tablicy.
Tablica zajmuje spójny obszar pamięci operacyjnej
Tak więc do tablic mo\
emy odnosić się w sposób tradycyjny, tzn.
przy pomocy nazwy zmiennej z indeksem tablicy: tab[i] lub
stosując arytmetykę wskaz
ników
Takie traktowanie tablic jest szczególnie przydatne dla tzw. tablic
otwartych i łańcuchów znaków - bez wstępnego określenia ich
długości. Środowisko języka C jest w stanie na bie\
ąco reagować
na aktualne potrzeby programisty w tym zakresie
Takich cech nie ma większość innych języków programowania
27
Programowanie komputerów
Wskaz
niki i tablice
Niech:
int sample[10];
Mo\
na utworzyć wskaz
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ą równie\
odwołania:
sample[i] oraz *(sample+i)
28
Programowanie komputerów
Wskaz
niki i tablice
Nazwa tablicy bez indeksu jest wskaz
nikiem do początku
tablicy. Przeanalizuj poni\
szy przykład
#include
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;}
29
Programowanie komputerów
Wskaz
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));
Odpowiedz
: 8
30
Programowanie komputerów
Wskaz
niki i tablice
Zadanie
Napisać program wczytujący napis jako łańcuch znaków.
Program powinien odszukać pierwszy ciąg spacji w łańcuchu,
a następnie wyświetlić pozostałą część napisu.
Wykorzystać zmienne wskaz
nikowe.
31
Programowanie komputerów
#include
int main(void)
{
char str[80], *p;
printf( Wprowadz
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++;
while(*p && *p==' ') p++;
printf(p);
Program 5.1
return 0;}
32
Programowanie komputerów
Wskaz
niki wielokrotne
Mo\
liwe jest, aby wskaz
nik wskazywał na inny wskaz
nik
(tzw. wielokrotne odwołanie niejawne).
Wskaz
nik Wskaz
nik
Zmienna
do wskaz
nika
Adres Wartość
Adres
Aby zadeklarować wskaz
nik do wskaz
nika, nale\
y przed
nazwą wskaz
nika umieścić dodatkową gwiazdkę:
char **mp;
char **mp;
33
Programowanie komputerów
Wskaz
niki wielokrotne
Aby dostać się do wartości wskazywanej niejawnie przez
wskaz
nik do wskaz
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 ;
34
Programowanie komputerów
Arytmetyka wskaz
ników
Przeanalizuj i wyjaśnij poni\
szy kod:
int x=1, y, z[10];
int *ip, *iq;
ip = &x; /* ip wskazuje na x */
y = *ip;
/* y = 1 */
*ip = 0; /* x przypisano 0 */
*ip += 1;
/* x zwiększone o 1 */
y = *ip+2; /* y = 3 */
ip = &z[0];
/* ip wskazuje na z[0] */
iq = ip;
/* iq wskazuje na z[0] */
35
Programowanie komputerów
Arytmetyka wskaz
ników
Przykład operacji dla typu prostego:
int *px;
px += 2;
px = (adres wskazywany przez px) + (2 * rozmiar obiektu
wskazywanego przez px);
np. dla px równego 3000 i rozmiaru 4 (dla int):
3000 + 2 * 4 = 3008;
3000 3004 3008 3012
pa
Przykład dla tablicy:
a[0] a[1] a[2] a[3]
int a[4];
int *pa;
pa = a; /* lub pa=&a[0]; */
/*pa wskazuje na a[1] */
pa ++;
/*pa wskazuje na a[3] */
pa =+ 2;
/*pa wskazuje na a[2] */
pa --;
36
Programowanie komputerów
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 wskaz
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;
37
Programowanie komputerów
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 nextPtr
38
Programowanie komputerów
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);
39
Programowanie komputerów
Wskaz
niki a napisy - zadania
Zrealizować implementację rozwiązań dla czterech poni\
szych
zadań, wykorzystując wskaz
niki do napisów:
Wczytaj z klawiatury napis o niezdefiniowanej długości i
wypisz go na ekranie w kolejności od końca do początku
wczytanego napisu
Wczytaj z klawiatury napis o niezdefiniowanej długości i
wypisz go na ekranie zamieniając wszystkie jego znaki na
du\
e litery
Wczytaj z klawiatury dwa napisy i daj odpowiedz
, czy są
one identyczne
Skopiuj napis1 do zmiennej napis2 przechodząc po
pojedynczych znakach i nie zapominając o dodaniu na
koniec napisu wynikowego znaku null, czyli:  \0 .
40
Programowanie komputerów
41
Programowanie komputerów