Podstawy programowania. Wykład 11  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
Spis treści
11. Listy jednokierunkowe dowiązaniowe c. d. ....................................................................... 1
11.1 Usuwanie pierwszego elementu z listy .................................................................... 1
11.2 Usuwanie ostatniego elementu z listy ...................................................................... 1
11.3 Usuwanie wskazanego elementu z listy................................................................... 2
11.4 Implementacja stosu................................................................................................. 2
11.5 Implementacja kolejki FIFO. ................................................................................... 5
11.5.1 Przykład - implementacja kolejki na liście jednokierunkowej............................. 6
11.5.2 Przykład  implementacja kolejki ze wskaz
nikiem do końca .............................. 8
11. Listy jednokierunkowe dowiązaniowe c. d.
11.1 Usuwanie pierwszego elementu z listy
void UsunPierwszy (Lista **glowa) /* usuwa pierwszy element z
listy */
{
Lista *pom;
if (*glowa == NULL) /* lista pusta */
printf("******* lista pusta\n");
else
{
pom = *glowa;
*glowa = (*glowa)->nast;
free(pom); /* Mogę, bo przy dodawaniu przydzielałam
pamięć funkcją malloc */
}
}
11.2 Usuwanie ostatniego elementu z listy
void UsunOstatni (Lista **glowa) /* usuwa ostatni element z
listy */
{
Lista *pom, *poprz;
if (*glowa == NULL) /* lista pusta */
printf("lista pusta \n");
else
{
pom = *glowa;
while (pom->nast !=NULL)
{
poprz = pom;
1
Podstawy programowania. Wykład 11  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
pom = pom->nast;
}
/* teraz pom->nast == NULL */
free(pom);
poprz->nast = NULL;
}
}
11.3 Usuwanie wskazanego elementu z listy
void UsunWskazany (Lista **glowa, int N) /* usuwa z listy
element o wskazanym numerze */
{
Lista *pom, *poprz=NULL;
int k=0;
if (*glowa == NULL) /* lista pusta */
printf("***** lista pusta\n");
else
if (N<0)
printf("**** N ujemne\n");
else
{
pom = *glowa;
while (pom->nast !=NULL && k {
poprz = pom;
printf("elem======= %d\n",pom->co);
pom = pom->nast;
++k;
}
if (k==N && poprz!=NULL){
printf("elemk=N======= %d\n", pom->co);
poprz ->nast = pom ->nast;
free(pom);
}
else
if(k==N && poprz == NULL) /*usuwam pierwszy */
{
*glowa = pom -> nast;
free(pom);
}
}
}
11.4 Implementacja stosu.
Wstawiamy na początku, usuwamy pierwszy.
2
Podstawy programowania. Wykład 11  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
Operacje:
Push  włóż na stos;
Pop  zdejmij ze stosu;
Top  zwróć wierzchołek stosu
Empty  zwraca true, jeśli stos pusty
Przykład
#include
#include
#include
/* implementacja stosu na liscie jednokierunkowej */
typedef int Element;
typedef struct stos
{
Element poz;
struct stos *nast; /* wskaznik do nastepnego elementu listy */
} Stos;
void InicjujStos(Stos **st); /* inicjuje pusty stos wskazywany
przez st;*/
void Push(Stos **st, Element co); /* wklada na stos wskazany
element */
void Pop(Stos **st); /* zdejmuje ze stosu wierzchołek */
Element Top (Stos *st); /* pobiera wierzcholek */
short Empty(Stos *st); /* zwraca true jesli stos pusty */
int main()
{
const int ileLiczb = 10;
Stos *st;
3
Podstawy programowania. Wykład 11  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
int iSecret, i;
InicjujStos(&st);
/* inicjuj generacje liczb losowych */
srand ( time(NULL) );
for (i = 0; i iSecret = rand() % 100 + 1;
printf("wstawiam %d \n", iSecret);
Push(&st, iSecret);
}
while (!Empty(st)){
printf("** wierzcholek = %d\n", Top(st));
Pop (&st);
}
printf("****** Teraz stos pusty \n");
return 0;
}
void InicjujStos(Stos ** st)
/* inicjuje pusty stos st */
{
*st = NULL;
}
void Push(Stos **st, Element co) /* wkłada na stos wskazany
element */
{
Stos *pom;
Stos *nowy;
pom = *st;
/* pom wskazuje na wierzcholek stosu */
/* wypelniam nowy elem */
nowy = malloc(sizeof(Stos));
nowy -> poz = co;
/* wstawiam na poczatek stosu */
if (!Empty(*st))
nowy -> nast = pom;
else
nowy -> nast = NULL;
*st = nowy;
}
4
Podstawy programowania. Wykład 11  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
void Pop(Stos **st) /* zdejmuje ze stosu wierzcholek */
{
Stos *pom;
if (Empty(*st) )/* stos pusty */
printf( "***** stos pusty\n");
else
{
pom = *st;
*st = (*st)->nast;
free(pom);
}
}
Element Top (Stos *st) /* pobiera wierzcholek */
{
return (st->poz);
}
short Empty(Stos *st) /* zwraca true jesli stos pusty */
{
return(st==NULL);
}
11.5 Implementacja kolejki FIFO.
Wstawiamy na końcu, pobieramy z początku
Operacje:
Push  wstaw element na koniec kolejki
Pop  zdejmij pierwszy element z kolejki
Top  pobierz pierwszy element z kolejki
Empty  zwraca true, jeśli kolejka pusta
5
Podstawy programowania. Wykład 11  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
11.5.1 Przykład - implementacja kolejki na liście jednokierunkowej
#include
#include
#include
/* implementacja kolejki na liście jednokierunkowej */
typedef int Element;
typedef short bool;
typedef struct kolejka
{
Element poz;
struct kolejka *nast; /* wskaznik do nastepnego elementu listy
*/
} Kolejka;
void InicjujKolejka(Kolejka **kol); /* inicjuje pustą kolejke
wskazywaną przez kol; */
void Push(Kolejka **kol, Element co); /* wstawia wskazany
element do kolejki */
void Pop(Kolejka **kol); /* zdejmuje z kolejki wierzchołek */
Element Top (Kolejka *kol); /* pobiera wierzchołek */
bool Empty(Kolejka *kol); /* zwraca true jesli kolejka pusta
*/
int main()
{
const int ileLiczb = 10;
Kolejka *kol;
int iSecret, i;
InicjujKolejka(&kol);
/* inicjuj generacje liczb losowych */
srand ( time(NULL) );
for (i = 0; i iSecret = rand() % 100 + 1;
printf("wstawiam %d\n",iSecret);
Push(&kol, iSecret);
}
while (!Empty(kol)){
printf("** wierzcholek = %d\n", Top(kol));
Pop (&kol);
}
6
Podstawy programowania. Wykład 11  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
printf("****** Teraz Kolejka pusta \n");
return 0;
}
void InicjujKolejka(Kolejka **kol)
/* inicjuje pusty Kolejka st */
{
*kol = NULL;
}
void Push(Kolejka **kol, Element co) /* wkłada wstawia
wskazany element do kolejki */
{
Kolejka *pom;
Kolejka *nowy;
pom = *kol;
/* pom wskazuje na poczatek kolejki */
/* wypelniam nowy elem */
nowy = malloc(sizeof(Kolejka));
nowy -> poz = co;
nowy -> nast = NULL;
/* wstawiam na koniec kolejki */
if (!Empty(*kol))
while (pom -> nast != NULL) pom = pom -> nast;
/* pom wskazuje na ostatni element listy - kolejki */
/* wstawiam na koniec kolejki */
if (!Empty(*kol))
pom -> nast = nowy;
else
*kol = nowy;
}
void Pop(Kolejka **kol) /* zdejmuje z Kolejki wierzchołek */
{
Kolejka *pom;
if (Empty(*kol) )/*Kolejka pusta */
printf("***** pusta\n");
else
{
pom = *kol;
*kol = (*kol)->nast;
free(pom);
}
}
7
Podstawy programowania. Wykład 11  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
Element Top (Kolejka *kol) /* pobiera wierzchołek */
{
return (kol->poz);
}
short Empty(Kolejka *kol) /* zwraca true, jesli kolejka
wskazywana przez kol jest pusta */
{
return(kol==NULL);
}
11.5.2 Przykład  implementacja kolejki ze wskaz
nikiem do końca
#include
#include
#include
/* implementacja Kolejki na liście jednokierunkowej ze wsk.
końca */
typedef int Element;
typedef short bool;
typedef struct kolejka
{
Element poz;
struct kolejka *nast; /*wskaznik do nastepnego elementu listy
*/
} Kolejka;
void InicjujKolejka(Kolejka **kol, Kolejka **ogo); /* inicjuje
pustą kolejke wskazywany przez kol;*/
void Push(Kolejka **kol, Kolejka **ogo, Element co); /*
wstawia wskazany element do kolejki */
void Pop(Kolejka **kol); /* zdejmuje z kolejki wierzchołek */
Element Top (Kolejka *kol); /* pobiera wierzchołek */
bool Empty(Kolejka *kol); /* zwraca true jesli kolejka pusta
*/
int main()
{
const int ileLiczb = 10;
Kolejka *kol, *ogon;
int iSecret, i;
InicjujKolejka(&kol,&ogon);
8
Podstawy programowania. Wykład 11  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
/* inicjuj generacje liczb losowych */
srand ( time(NULL) );
for ( i = 0; i iSecret = rand() % 100 + 1;
printf("wstawiam %d\n", iSecret);
Push(&kol,&ogon, iSecret);
}
while (!Empty(kol)){
printf("***** wierzcholek = %d\n", Top(kol));
Pop (&kol);
}
printf("****** Teraz Kolejka pusta \n");
}
void InicjujKolejka(Kolejka **kol, Kolejka **ogo)
/* inicjuje pusty Kolejka st */
{
*kol = NULL;
*ogo = NULL;
}
void Push(Kolejka **kol, Kolejka **ogo, Element co) /* wkłada
wstawia wskazany element do kolejki */
{
Kolejka *pom;
Kolejka *nowy;
pom = *kol;
/* pom wskazuje na poczatek kolejki */
/* wypelniam nowy elem */
nowy = malloc(sizeof (Kolejka));
nowy -> poz = co;
nowy -> nast = NULL;
/* wstawiam na koniec kolejki *
/* if (!Empty(*kol)) */
/* while (pom -> nast != NULL) pom = pom -> nast; */
/* pom wskazuje na ostatni element listy */
/* wstawiam na koniec kolejki */
if (!Empty(*kol)){
(*ogo) -> nast = nowy;
*ogo = nowy;
}
9
Podstawy programowania. Wykład 11  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
else{
*kol = nowy;
*ogo =nowy;
}
}
void Pop(Kolejka **kol) /* zdejmuje z Kolejki wierzchołek */
{
Kolejka *pom;
if (Empty(*kol) )/* Kolejka pusta */
printf( "***** Kolejka pusta \n");
else
{
pom = *kol;
*kol = (*kol)->nast;
free(pom);
}
}
Element Top (Kolejka *kol) /* pobiera wierzcholek */
{
return (kol->poz);
}
bool Empty(Kolejka *kol) /* zwraca true jesli Kolejka pusty */
{
return(kol==NULL);
}
10