Miről lesz ma szó?
A PROGAMOZÁS ALAPJAI 1 8. előadás Vitéz András egyetemi adjunktus BME Híradástechnikai Tanszék
[email protected] 2012. március 27.
Dinamikus adatszerkezetek • Önhivatkozó struktúra • Egyirányban láncolt lista – keresés, beszúrás, törlés – strázsák használata • Verem • Várakozási sor • Prioritásos sor • Két irányban láncolt lista • Több kulcs szerint rendezett lista • Fésűs lista • Memória gazdálkodás A programozás alapjai 1 8. előadás
Dinamikus adatszerkezetek Dinamikus adatszerkezetek: Adott építőelemekből, adott szabályok szerint felépített, de nem rögzített méretű adatszerkezetek. A tényleges méret futás közben alakul ki. A méret és a szerkezet is megváltoztatható.
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Önhivatkozó struktúrák
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Dinamikus adatszerkezetek Megvalósításához szükséges: önhivatkozó struktúra olyan összetett adattípus, amely összetevőként tartalmaz olyan mutatót, amely saját típusára képes mutatni.
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Önhivatkozó struktúrák
Struktúra deklaráció alakja:
Önhivatkozó struktúra deklaráció alakja:
struct [<struktúra címke>] {
struct <struktúra címke> { [<struktúra tag deklarációk>] struct <struktúra címke> *
; [<struktúra tag deklarációk>] } [<struktúra változó azonosítók>] ;
<struktúra tag deklarációk> }
[<struktúra változó azonosítók>] ; A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
1
Önhivatkozó struktúrák Példa:
Önhivatkozó struktúrák Példa:
struct elem1 {
typedef struct kamu {
int adat; struct elem1 * kovetkezo; } e1,*e2; struct elem1 e3,*e4;
A programozás alapjai 1 8. előadás
int adat; struct kamu * kovetkezo; } elem2; elem2 e5,*e6;
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Önhivatkozó struktúrák Példa:
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista Egyirányban láncolt lista:
typedef struct k { int adat; struct k * kovetkezo; } listelem,*listptr; listelem e7,e8; listptr p1,p2;
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista Egyirányban láncolt lista:
Hogy kezelni tudjuk, két mutatóra van szükségünk:
head
spot
Az egyik az adatszerkezet elejét jelzi, A másik az éppen feldolgozott elemre mutat. A listát ez a két mutató testesíti meg.
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
next
A programozás alapjai 1 8. előadás
next
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
2
Egyirányban láncolt lista
Egyirányban láncolt lista A beszúráshoz egy segédmutató kell.
Hogy a tárolt adatokat vissza tudjuk keresni, rendezni kell (vagy eleve rendezetten felépíteni)
head
Kézenfekvő megoldás: közvetlen beszúrásos rendezés.
A programozás alapjai 1 8. előadás
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista
temp
spot
next
next
next
A programozás alapjai 1 8. előadás
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista
Beszúrni csak az aktuális elem mögé lehet!
Beszúrni csak az aktuális elem mögé lehet! temp->next=spot->next;
head
temp
spot
next
next
next
next
A programozás alapjai 1 8. előadás
head
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista
temp
spot
next
next
next
next
A programozás alapjai 1 8. előadás
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista
Beszúrni csak az aktuális elem mögé lehet!
Beszúrni csak az aktuális elem mögé lehet!
temp->next=spot->next; head
temp
spot
next
A programozás alapjai 1 8. előadás
next
next
next
next
spot->next=temp; head
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
temp
spot
next
A programozás alapjai 1 8. előadás
next
next
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
3
Egyirányban láncolt lista
Egyirányban láncolt lista
Beszúrni csak az aktuális elem mögé lehet!
Beszúrni csak az aktuális elem mögé lehet!
spot->next=temp; head
temp
spot
next
A programozás alapjai 1 8. előadás
next
next
next
head
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista
next
spot
next
next
A programozás alapjai 1 8. előadás
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista Ez a módszer hibás!
A beszúrás helyét lineáris kereséssel találhatjuk meg:
Nem lehet beszúrni az első elem elé, és az utolsó elem után.
A legelső elemtől kiindulva megkeressük az első olyan elemet, amely után következő elem kulcsa nagyobb a beszúrni kívánténál.
Ezek esetleges szükségességét minden esetben külön meg kell vizsgálni.
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista
Ez körülményes, ezért nem így járunk el.
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista Egyirányban láncolt lista strázsával:
Helyette: Mindkét végén kiegészítjük a listát egy-egy elemmel. Egy olyannal, amelynek kulcsa kisebb minden elvileg tárolható eleménél, és egy olyannal, amelynek kulcsa nagyobb minden elvileg tárolható eleménél.
head
spot
next
«
next
next
next
next
»
Ezeket az elemeket strázsának (sentinel) nevezzük. A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
4
Egyirányban láncolt lista
Egyirányban láncolt lista
Az üres lista ezek szerint:
Elemet törölni is csak az aktuális elem mögül lehet!
spot
head
head
next
«
A programozás alapjai 1 8. előadás
next
next
«
next
»
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista
next
«
A programozás alapjai 1 8. előadás
next
next
next
»
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista Elemet törölni is csak az aktuális elem mögül lehet! head
next
next
next
spot
next
spot
«
Elemet törölni is csak az aktuális elem mögül lehet! head
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Elemet törölni is csak az aktuális elem mögül lehet! spot->next=spot->next->next; head
A programozás alapjai 1 8. előadás
next
»
A programozás alapjai 1 8. előadás
spot
next
next
Egyirányban láncolt lista
Elemet törölni is csak az aktuális elem mögül lehet! spot->next=spot->next->next;
next
next
«
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
next
next
next
»
Egyirányban láncolt lista
head
spot
next
next
»
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
next
«
A programozás alapjai 1 8. előadás
spot
next
next
next
»
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
5
Egyirányban láncolt lista Adat beszúrása a listába
Egyirányban láncolt lista Adat beszúrása a listába „cserével”
typedef struct{... key_t key; ...}data; typedef struct x{data d; struct x *next;}le,*lp; insert(data newdata,lp head){ lp spot=head,temp=malloc(sizeof (le)); if(!temp)return 0; temp->d=newdata; while(spot->next->d.keynext; temp->next=spot->next; spot->next=temp; return 1; }
typedef struct{... key_t key; ...}data; typedef struct x{data d; struct x *next;}le,*lp; insert_x(data newdata,lp head){ lp spot=head,temp=malloc(sizeof (le)); if(!temp)return 0; while(spot->d.keynext; temp->next=spot->next; spot->next=temp; temp->d=spot->d; spot->d=newdata; return 1; }
Csak akkor, ha külső hivatkozások nem mutatnak a listára! A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista
Adott kulcsú adat törlése a listából
Adott kulcsú adat törlése a listából „cserével”
typedef struct{... key_t key; ...}data; typedef struct x{data d; struct x *next;}le,*lp; delete(key_t k,lp head){ lp temp,spot=head; while((k!=spot->next->d.key)&& (k<spot->next->d.key))spot=spot->next; if(k>spot->next->d.key)return 0; temp=spot->next; spot->next=spot->next->next; free(temp); return 1; }
typedef struct{... key_t key; ...}data; typedef struct x{data d; struct x *next;}le,*lp; delete_x(key_t k,lp head){ lp spot=head; while((k!=spot->d.key)&&(k<spot->d.key)) spot=spot->next; if(k>spot->d.key)return 0; spot->d=spot->next->d; temp=spot->next; spot->next=spot->next->next; free(temp); return 1; }
Csak akkor, ha külső hivatkozások nem mutatnak a listára! A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista
Listák különleges alkalmazásai: verem (stack) (LIFO), várakozási sor (queue) (FIFO) prioritásos sor (priority queue)
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Verem
Verem (Last In First Out): Elemet mindig csak a lista elejére szúrunk be; mindig csak a lista elejéről veszünk ki.
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
6
Verem
Verem Beszúrás a verembe:
A vermet egyetlen mutató testesíti meg.
head
Beszúrni üres verembe is ugyanúgy lehet. Törölni az utolsó elemet is ugyanúgy lehet. Strázsákra sincs szükség.
A programozás alapjai 1 8. előadás
temp
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Verem
next
next
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Beszúrás a verembe: temp->next=head;
head
temp->next=head; head
temp
temp
next
next
next
next
A programozás alapjai 1 8. előadás
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Verem
next
next
next
next
A programozás alapjai 1 8. előadás
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Verem
Beszúrás a verembe:
Beszúrás a verembe: head=temp;
head
head=temp; head
temp
A programozás alapjai 1 8. előadás
next
Verem
Beszúrás a verembe:
next
next
temp
next
next
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
next
A programozás alapjai 1 8. előadás
next
next
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
7
Verem
Verem
Beszúrás a verembe:
Beszúrás üres verembe:
head
head
temp
next
next
next
next
A programozás alapjai 1 8. előadás
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Verem
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Verem
Beszúrás üres verembe:
Beszúrás üres verembe: temp->next=head;
head
temp->next=head; head
temp
temp
next
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Verem
next
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Verem
Beszúrás üres verembe:
Beszúrás üres verembe: head=temp;
head
head
temp
A programozás alapjai 1 8. előadás
head=temp;
temp
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
A programozás alapjai 1 8. előadás
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
8
Verem
Verem
Beszúrás üres verembe:
Elem törlése a veremből: head
head
next
next
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Verem
next
A programozás alapjai 1 8. előadás
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Elem törlése a veremből: head=head->next;
head
next
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Verem
next
next
A programozás alapjai 1 8. előadás
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Verem
Elem törlése a veremből:
Elem törlése a veremből: head
head
A programozás alapjai 1 8. előadás
head=head->next; head
A programozás alapjai 1 8. előadás
next
next
Verem
Elem törlése a veremből:
next
next
next
next
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
A programozás alapjai 1 8. előadás
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
9
Verem
Verem
Az utolsó elem törlése a veremből:
Az utolsó elem törlése a veremből: head=head->next;
head
head
next
A programozás alapjai 1 8. előadás
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Verem
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Verem
Az utolsó elem törlése a veremből:
Az utolsó elem törlése a veremből:
head=head->next; head
head
next
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Verem
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Egyirányban láncolt lista
Adat berakása a verembe
Adat elővétele a veremből
typedef struct{... key_t key; ...}data; typedef struct x{data d; struct x *next;}le,*lp; lp push(data newdata,lp*stack){ lp temp=malloc(sizeof (le)); if(!temp)return 0; temp->d=newdata; temp->next=*stack; *stack=temp; return*stack; }
typedef struct{... key_t key; ...}data; typedef struct x{data d; struct x *next;}le,*lp; data pop(lp*stack){ data dd;lp temp; temp=*stack; dd=temp->d; *stack=temp->next; free(temp); return dd; }
A megváltozott címet adjuk vissza!
A kiolvasott adatot adjuk vissza!
VIGYÁZAT! lp*stack kétszeres indirekció!
VIGYÁZAT! lp*stack kétszeres indirekció!
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
10
Várakozási sor
Várakozási sor A várakozási sort két mutató testesíti meg. Az egyik az első elemre mutat; a másik pedig az utolsóra.
Várakozási sor (First In First Out): Elemet mindig csak a lista végére szúrunk be; mindig csak a lista elejéről veszünk ki.
Beszúrni az utolsó elem mögé lehet. Egy strázsa elég az elejére, így mindig lesz utolsó elem, akkor is, ha a sor üres. Törölni mindig a strázsa utáni elemet kell.
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
Üres várakozási sor: head
tail
next
next
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
Várakozási sor: head
A programozás alapjai 1 8. előadás
next
next
tail
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
Beszúrás várakozási sorba:
Beszúrás várakozási sorba: temp->next=0;
head
head
tail
temp
next
A programozás alapjai 1 8. előadás
next
next
tail
temp
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
next
A programozás alapjai 1 8. előadás
next
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
11
Várakozási sor
Várakozási sor
Beszúrás várakozási sorba:
Beszúrás várakozási sorba: temp->next=0;
head
temp
next
next
tail->next=temp; head
tail
A programozás alapjai 1 8. előadás
next
tail
temp
next
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
A programozás alapjai 1 8. előadás
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
Beszúrás várakozási sorba:
Beszúrás várakozási sorba: tail->next=temp;
head
tail=temp; head
tail
temp
next
next
A programozás alapjai 1 8. előadás
next
next
tail
temp
next
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
A programozás alapjai 1 8. előadás
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
Beszúrás várakozási sorba:
Beszúrás várakozási sorba: tail=temp;
head
head
tail
temp
next
A programozás alapjai 1 8. előadás
next
next
tail
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
next
next
A programozás alapjai 1 8. előadás
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
12
Várakozási sor
Várakozási sor
Beszúrás üres várakozási sorba:
Beszúrás üres várakozási sorba: temp->next=0;
head
head
tail
temp
tail
temp
next
next
next
next
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
Beszúrás üres várakozási sorba:
Beszúrás üres várakozási sorba:
temp->next=0; head
tail->next=temp; head
tail
temp
tail
temp
next
next
next
next
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
Beszúrás üres várakozási sorba:
Beszúrás üres várakozási sorba:
tail->next=temp; head
temp
tail
temp
next
next
A programozás alapjai 1 8. előadás
tail=temp; head
tail
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
13
Várakozási sor
Várakozási sor
Beszúrás üres várakozási sorba:
Beszúrás üres várakozási sorba: tail=temp;
head
head
tail
temp
tail
next
next
next
next
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
Elem törlése várakozási sorból:
Elem törlése várakozási sorból: head->next=head->next->next;
head
head
tail
next
next
next
A programozás alapjai 1 8. előadás
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
tail
next
next
A programozás alapjai 1 8. előadás
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
Elem törlése várakozási sorból:
Elem törlése várakozási sorból:
head->next=head->next->next; head
head
tail
next
A programozás alapjai 1 8. előadás
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
tail
next
A programozás alapjai 1 8. előadás
next
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
14
Várakozási sor
Várakozási sor
Elem törlése várakozási sorból: head
Utolsó elem törlése várakozási sorból:
tail
head
next
next
A programozás alapjai 1 8. előadás
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
tail
next
next
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
Utolsó elem törlése várakozási sorból:
Utolsó elem törlése várakozási sorból:
head->next=head->next->next; head
head->next=head->next->next; head
tail
next
next
A programozás alapjai 1 8. előadás
tail
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Várakozási sor
Utolsó elem törlése várakozási sorból:
Utolsó elem törlése várakozási sorból: if(!(head->next))tail=head;
head
next
!
A programozás alapjai 1 8. előadás
head
tail
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
!
A programozás alapjai 1 8. előadás
tail
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
15
Várakozási sor
Várakozási sor
Utolsó elem törlése várakozási sorból:
Utolsó elem törlése várakozási sorból:
if(!(head->next))tail=head; head
head
tail
next
next
A programozás alapjai 1 8. előadás
tail
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Prioritásos sor
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Prioritásos sor
Prioritásos sor:
Prioritásos sor: Elemet mindig csak a magasabb prioritású vagy megegyező prioritású de régebben várakozó elemek mögé szúrunk be;
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Prioritásos sor
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Prioritásos sor
Prioritásos sor: Elemet mindig csak a magasabb prioritású vagy megegyező prioritású de régebben várakozó elemek mögé szúrunk be; mindig csak a lista elejéről veszünk ki.
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Megvalósítható a lista első változatával. Mivel beszúrásra a legelején és a legvégén is sor kerülhet, kell mindkét strázsa.
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
16
Prioritásos sor
Prioritásos sor
Beszúrás prioritásos sorba: head
temp
spot
next
next
next
Beszúrás prioritásos sorba:
next
A programozás alapjai 1 8. előadás
head
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Prioritásos sor
temp
spot
next
A programozás alapjai 1 8. előadás
next
next
next
A programozás alapjai 1 8. előadás
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Beszúrás prioritásos sorba:
next
next
next
next
Prioritásos sor
Beszúrás prioritásos sorba: head
temp
spot
head
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
next
spot
next
next
next
A programozás alapjai 1 8. előadás
next
next
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Két irányban láncolt lista
Két irányban láncolt lista
Ez NEM fa, de nagyon gyakran használjuk!
Ez NEM fa, de nagyon gyakran használjuk! Két irányban láncolt lista strázsával:
head
prev
next
«
A programozás alapjai 1 8. előadás
head
tail
spot
prev
next
prev
next
prev
next
prev
next
»
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
prev
tail
spot
next
«
A programozás alapjai 1 8. előadás
prev
next
prev
next
prev
next
prev
next
»
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
17
Két irányban láncolt lista
Két irányban láncolt lista
Ez NEM fa, de nagyon gyakran használjuk! Két irányban láncolt lista strázsával:
Ez NEM fa, de nagyon gyakran használjuk! Két irányban láncolt lista strázsával:
head
prev
next
head
tail
spot
prev
next
prev
next
prev
next
prev
«
next
»
Rekurzívan rendezhető gyorsrendezéssel! A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Több kulcs szerint rendezett lista A lista szerkezet lehetővé teszi, hogy egy lista egyidejűleg több szempont szerint is rendezett legyen. Például az iskolaorvos a gyerekeket testsúly szerint csökkenő, testmagasság szerint növekvő sorban tárolhatja. Ilyenkor minden kulcshoz tartozik egy-egy mutató. Ezeket célszerűen adatvektorba foglalhatjuk. A vektor indexelése történhet felsorolt típussal.
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Fésűs lista
prev
tail
spot
prev
next
next
prev
next
prev
next
prev
«
next
»
Cserénél vigyázni kell a mutatók átállításának sorrendjére! A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Több kulcs szerint rendezett lista Listaelem több kulcs szerinti láncoláshoz: #define N … struct multisort { [<struktúra tag deklarációk>] struct multisort * next[N]; [<struktúra tag deklarációk>] } [<struktúra változó azonosítók>] ; A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Fésűs lista Példa: A földrajztanár az osztály névsorához hozzárendeli a kapott osztályzatokat.
A listaelem tagjai között gyakran tárolunk olyan mutatót, amelyen egy másik lista lóg.
9.c
A „fésű” lelógó fogai általában egy másik adattípushoz tartoznak. AAAA
Balogh Buda
Kiss Döme
felelet
3
témazáró
4
felelet
5
Rák Emil
röpdolgozat 2 felelet
4
ZZZZ
témazáró
5
felelet
5
röpdolgozat 5
röpdolgozat 4 A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
18
Fésűs lista
Memóriagazdálkodás
typedef enum{ felelet, ropdolgozat, temazaro }jegy_t; typedef struct x{ jegy_tipus miert; short osztalyzat; struct x *kovetkezo_jegy; }jegy,*jegy_mutato; typedef struct y{ char nev[48]; jegy_mutato jegyek; struct y *kovetkezo tanulo; }tanulo,*tanulo_mutato; typedef struct { char osztaly_neve[4]; tanulo_mutato tanulok; }osztaly; A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Memóriagazdálkodás #define N 64 typedef struct{... key_t key; ...}data; typedef struct x{data d; struct x *next;}le,*lp; lp spare; /* !!! globális változó !!! */ lp getnew(){ lp temp; if(!spare){ int i; spare=calloc(N,sizeof(le)); if(!spare) return 0; for(i=0;inext; return temp; } A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
A lista elemeit nem célszerű egyenként kérni, mert a nyilvántartáshoz szükséges információ minden egyes elemnél tárolási igényként jelentkezik. Egyszerre kérünk egy nagyobb csomagot, és a kapott tömböt verem szervezésű listává láncoljuk. Az új elem iránti igényeket ebből szolgáljuk ki. Ha elfogy, kérünk még. Ha menet közben visszaadnánk egy elemet, akkor ebbe a tartalék listába tesszük. Ha egy adatelemnek több mutatója is van, csak az egyiket használjuk a láncoláshoz. A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
Memóriagazdálkodás #define N 64 typedef struct{... key_t key; ...}data; typedef struct x{data d; struct x *next;}le,*lp; lp spare; /* !!! globális változó !!! */ void hang_up(lp temp){ temp->next=spare; spare=temp; }
A programozás alapjai 1 8. előadás
© Vitéz András, Dr. Zsóka Zoltán, Híradástechnikai Tanszék Budapesti Műszaki és Gazdaságtudományi Egyetem
19
