Opole, dn. 18 maja 2004

Laboratorium Algorytmów i Struktur Danych

Temat:

Listy dwukierunkowe

Autor: Dawid Najgiebauer

Informatyka, sem. II, grupa lab. 11

Prowadzący: dr inż. Jan Sadecki

1. Temat

Utworzyć 7 dowolnych funkcji pracujących na liście dwukierunkowej.

2. Podjęte zagadnienia

W ramach tematu zadania program obsługujący listy dwukierunkowe został wzbogacony o następujące funkcje:

1. Wstawiania nowego elementu na dowolną pozycję w liście.

2. Usuwania elementów, których pole data mieści się w zadanym przedziale liczbowym.

3. Wyszukiwanie i zliczanie ilości elementów o zadanej wartości.

4. Odwracanie kolejności elementów listy poprzez zmianę wartości pól danych.

5. Zliczanie liczby elementów w liście.

6. Sortowanie listy poprzez sortowanie wartości pól danych (sortowanie metodą bąbelkową).

7. Usuwanie listy.

3. Specyfikacja wewnętrzna funkcji

1. Wstawianie

lista_element *insert(lista_element *start, int pos, int data);

Parametry funkcji: start - wskaźnik na pierwszy element listy pos - pozycja, za którą ma nastąpić wstawienie nowego elementu (0 - na początek listy; wartość większa od liczby elementów - na koniec listy) data - wartość nowego wstawianego elementu Wartości zwracane: Wskaźnik na początek listy po wstawieniu elementu.

2. Usuwanie o zadanym zakresie

lista_element *deleterange(lista_element *start, int from, int to);

Parametry funkcji: start - wskaźnik na pierwszy element listy from - dolna wartość graniczna, wobec której elementy o wartości pola data większej bądź równej będą usuwane. to - górna wartość graniczna, wobec której elementy o wartości pola data mniejszej bądź równej będą usuwane. Oba warunki muszą być spełnione równocześnie, aby element został usunięty z listy. Wartości zwracane: Wskaźnik na początek listy po wykonaniu się funkcji.

3. Wyszukiwanie

int search(lista_element *start, int data);

Parametry funkcji: start - wskaźnik na pierwszy element listy data - wartość wyszukiwana. Wartości zwracane: Ilość wystąpień szukanego elementu (0 - szukany element nie występuje w liście).

4. Odwracanie kolejności

void transposition(lista_element *start);

Parametry funkcji: start - wskaźnik na pierwszy element listy Wartości zwracane: Brak

5. Zliczanie elementów

int count(lista_element *start);

Parametry funkcji: start - wskaźnik na pierwszy element listy Wartości zwracane: Liczba elementów w liście

6. Sortowanie

void sort(lista_element *start);

Parametry funkcji: start - wskaźnik na pierwszy element listy Wartości zwracane: Brak

7. Usuwanie listy

void deleteall(lista_element *start);

Parametry funkcji: start - wskaźnik na pierwszy element listy Wartości zwracane: Brak

4. Implementacje funkcji

1. Wstawianie

lista_element *insert(lista_element *start, int pos, int data)

{

lista_element *pom=start;

lista_element *nowy=new lista_element;

nowy->data=data;

if (pos==0)

{

nowy->next=start;

nowy->prev=NULL;

start->prev=nowy;

start=nowy;

}

else

{

for(int p=1;p<pos && pom->next->next!=NULL;p++)

pom=pom->next;

nowy->prev=pom;

nowy->next=pom->next;

pom->next=nowy;

if (nowy->next!=NULL)

nowy->next->prev=nowy;

}

return start;

}

2. Usuwanie o zadanym zakresie

lista_element *deleterange(lista_element *start, int from, int to)

{

lista_element *wsk;

lista_element *pom;

for(wsk=start;wsk->next!=NULL;)

{

pom=wsk->next;

if (wsk->data>=from && wsk->data<=to)

{

if(wsk->prev!=NULL)

wsk->prev->next=wsk->next;

else //usuniemy start

start=wsk->next;

if(wsk->next!=NULL)

wsk->next->prev=wsk->prev;

delete wsk;

}

wsk=pom;

}

return start;

}

3. Wyszukiwanie

int search(lista_element *start, int data)

{

lista_element *wsk;

int res=0;

for(wsk=start;wsk!=NULL;wsk=wsk->next)

if (wsk->data==data)

res++;

return res;

}

4. Odwracanie kolejności

void transposition(lista_element *start)

{

lista_element *left=start;

lista_element *right;

for(right=start;right->next->next!=NULL;right=right->next);

for(;left!=right && right->next!=left;left=left->next,right=right->prev)

{

int tmp;

tmp=left->data;

left->data=right->data;

right->data=tmp;

}

}

5. Zliczanie elementów

int count(lista_element *start)

{

lista_element *wsk;

int res=0;

for (wsk=start;wsk->next->next!=NULL;wsk=wsk->next)

res++;

return res;

}

6. Sortowanie

void sort(lista_element *start)

{

lista_element *i;

lista_element *stop;

lista_element *ostzam;

for(stop=NULL;stop!=start;stop=ostzam)

{

ostzam=start;

for(i=start;i!=stop && i->next->next!=NULL;i=i->next)

{

if (i->data > i->next->data)

{

ostzam=i;

int tmp=i->data;

i->data=i->next->data;

i->next->data=tmp;

}

}

}

}

7. Usuwanie listy

void deleteall(lista_element *start)

{

for(start=start->next;start->next!=NULL;start=start->next)

delete start->prev;

delete start;

}

8 Dawid Najgiebauer

Implementacje funkcji 7

Temat 3

---