Temat:
Struktury danych
1. Przetwarzanie dynamicznych struktur danych
Przez pojęcie dynamicznych struktur danych rozumiemy proste i złożone struktury danych, którym pamięć może być przydzielana i zwalniana na żądanie w trakcie wykonywania programu.
Ze względu na organizację oraz sposoby dołączania, wstawiania i usuwania składników złożonych struktur dynamicznych, można wyróżnić:
stosy, w których wstawianie, usuwanie i dostęp są możliwe tylko na jednym końcu - wierzchołku stosu;
kolejki, w których można dołączyć składniki tylko na jednym końcu (koniec kolejki), a usunąć tylko na drugim końcu (początek kolejki);
listy, które charakteryzują się tym, że dla każdego składnika (poza pierwszym i ostatnim) określony jest jeden składnik poprzedni i jeden składnik następny (lista dwukierunkowa) lub tylko składnik poprzedni, lub tylko jeden składnik następny (są to listy jednokierunkowe), przy czym w dowolnym miejscu listy można dołączyć nowy składnik lub usunąć składnik istniejący;
drzewa, w których dla każdego składnika (poza pierwszym) określony jest jeden składnik poprzedni i dla każdego składnika (poza ostatnimi w strukturze) określonych jest n (n ≥ 2) składników następnych.
Z punktu widzenia tworzenia i przetwarzania tych struktur, tj. dołączania, usuwania i dostępu do składników, nie jest istotne, jakiego typu danymi są poszczególne składniki. Dlatego też skoncentrujemy uwagę przede wszystkim na prawidłowym ustaleniu powiązań pomiędzy składnikami i założymy, że omawiana struktura danych dynamicznych będzie służyć do przechowywania wartości typu int.
1.1. Stosy
Stos jest to struktura danych składająca się z liniowo uporządkowanych elementów, z których w danej chwili jest dostępny tylko element znajdujący się na wierzchołku stosu. Jest to jedyne miejsce, z którego można usunąć lub do którego można dołączyć nowy element.
Utwórzmy stos przechowujący liczby całkowite. Element stosu powinien być w tym przypadku strukturą składającą się z dwóch pól: pola przeznaczonego na liczbę całkowitą oraz pola przeznaczonego na wskaźnik i przechowującego adres elementu następnego na stosie (licząc od wierzchołku stosu).
Powyższe założenie wymaga zdefiniowania w programie następującego typu strukturalnego:
typedef struct El
{ int Liczba;
struct El * Wskaznik;
} ELEMENT;
ELEMENT * Wierzcholek;
Jeżeli element stosu przedstawimy jako , to organizacja stosu będzie następująca:
Poniżej przytoczono funkcje obsługi stosu.
void Na_Stos( int L )
/*****************************************************************************************/
/* Funkcja umożliwia dołączenie do aktualnego wierzchołka stosu */
/* nowego elementu L. Po dołączeniu elementu aktualizowany jest */
/* adres wierzchołka. Przed pierwszym wywołaniem procedury */
/* adres wierzchołka powinien być NULL, ponieważ stos jest pusty. */
/(****************************************************************************************/
{
ELEMENT *Biezacy ;
Biezacy = Wierzcholek;
Wierzcholek = new ELEMENT;
Wierzcholek->Liczba = L;
Wierzcholek->Wskaznik := Biezacy;
}
void Ze_Stosu( int &L )
/************************************************************************************ */
/* Funkcja umożliwia usunięcie elementu z wierzchołka stosu. */
/* Po usunięciu elementu powinien być aktualizowany adres */
/* wierzchołka stosu */
/*************************************************************************************/
{
ELEMENT *Biezacy ;
if ( Wierzcholek != NULL)
{ L = Wierzcholek->Liczba;
Biezacy = Wierzcholek->Wskaznik;
delete Wierzcholek;
Wierzcholek = Biezacy;
}
}
void Pisz_Stos_Od_Gory ( )
/****************************************************************************************/
/* Funkcja umożliwia wyświetlenie elementów stosu w kolejności */
/* od góry do dołu. Elementy zostaną wyświetlone w odwrotnej */
/* kolejności niż były wprowadzane. */
/****************************************************************************************/
{
ELEMENT * Biezacy ;
cout << ″Oto elementy stosu poczynając od wierzchołka: \n″;
cout << endl;
Biezacy = Wierzcholek;
if ( Wierzcholek != NULL )
do {
cout << Biezacy->Liczba;
Biezacy = Biezacy-> Wskaznik:
}
while (Biezacy != NULL );
else cout << ″Stos jest pusty″;
}
void Pisz_Stos_Od_Dolu ( )
/* Funkcja umożliwia wyświetlanie elementów stosu */
/* od dołu do góry */
{
ELEMENT * Biezacy, * Pom;
if ( Wierzcholek != NULL )
{
cout << ″ Oto elementy stosu w kolejności od dołu do góry:\n″;
cout << endl;
Pom = NULL;
do
{
Biezacy = Wierzcholek;
while ( Biezacy->Wskaznik != Pom)
Biezacy = Biezacy->Wskaznik;
cout << Biezacy->Liczba;
Pom = Biezacy
while ( Pom != Wierzcholek );
}
else cout << ″Stos jest pusty″;
}
Rozważmy teraz możliwość zastosowania stosu do rozwiązania zadania dotyczącego wystawienia ocen w postaci słownej ma podstawie liczby uzyskanych punktów. Stos w tym przypadku byłby zbudowany z elementów o następującej strukturze:
typedef struct El
{ char Nazwisko [30];
int Punkty;
struct El * Wskaznik;
} ELEMENT;
ELEMENT * Wierzcholek;
Należy jednak podkreślić, że wybrana struktura dynamiczna nie jest strukturą optymalną dla rozpatrywanego zagadnienia. Problem pojawia się już przy wyświetleniu elementów stosu - jeśli wyświetlać je w kolejności dostępu, tj. poczynając od wierzchołka w dół, to zostaną one wyświetlone w odwrotnej kolejności, niż były wprowadzone. Pojawi się również problem z sortowaniem np. wg nazwisk i dołączaniem nowych elementów z zachowaniem kolejności alfabetycznej.
1.2. Kolejki
Kolejka jest strukturą danych składającą się z liniowo uporządkowanych zbiorów składników, do której można dołączyć składnik tylko na końcu kolejki, a usunąć tylko na początku kolejki.
Powiązanie pomiędzy składnikami kolejki jest podobne, jak pomiędzy składnikami stosu. Poniższy rysunek ilustruje zasadę organizacji kolejki.
Usunięcie składnika z początku kolejki odbywa się w taki sam sposób, jak usunięcie składnika z wierzchołka stosu. Natomiast w celu dołączenia nowego składnika na końcu kolejki należy zmienić wskaźnik ostatniego składnika, tak aby wskazywał on na nowy składnik, a wskaźnikowi dołączanego elementu przypisać wartość NULL, ponieważ ostatni element kolejki nie wskazuje na żaden inny element.
Poniżej podano funkcje dołączania i usuwania elementów z kolejki.
void Do_Kolejki( int L )
{
ELEMENT * Biezacy;
Biezacy = Koniec;
Koniec = new ELEMENT;
Koniec->Liczba = L;
Koniec->Wskaznik = NULL;
if (Biezacy != NULL )
Biezacy->Wskaznik := Koniec;
}
void Z_Kolejki ( int &L )
{
ELEMENT * Biezacy;
if ( Poczatek != NULL )
{
L = Poczatek->Liczba;
Biezacy = Poczatek->Wskaznik;
delete Poczatek;
Poczatek = Biezacy;
}
else cout << ″Kolejka jest pusta\n″;
}
1.3. Listy
Rozróżniamy listy jednokierunkowe, dwukierunkowe i cykliczne. Rozpatrzmy najpierw organizację list jednokierunkowych.
Listy jednokierunkowe
Rozróżniamy listy jednokierunkowe o kierunku „do przodu” oraz listy jednokierunkowe o kierunku „do tyłu”. Organizacja listy jednokierunkowej jest podobna do organizacji stosu i kolejki, tzn. dla każdego składnika, poza ostatnim, jest określony następny (kierunek „do przodu”) lub dla każdego składnika, poza pierwszym, jest określony składnik poprzedni (kierunek „do tyłu”). Poniższe dwa rysunki ilustrują organizację list jednokierunkowych.
Listy dwukierunkowe
Listą dwukierunkową nazywamy liniowo uporządkowany zbiór składników, w którym dla każdego składnika, poza pierwszym i ostatnim, jest określony składnik poprzedni i następny. Dla ostatniego składnika listy dwukierunkowej jest określony składnik poprzedni, a dla pierwszego - następny. Składnik listy dwukierunkowej przechowującej liczby całkowite ma następującą budowę:
Organizacja listy dwukierunkowej przedstawia poniższy rysunek:
Każdy składnik listy dwukierunkowej posiada dwa wskaźniki: Wskaznik_1, który wskazuje składnik poprzedni, oraz Wskaznik_2, który wskazuje składnik następny.
Listy cykliczne
Lista cykliczna powstaje z listy jedno- lub dwukierunkowej przez powiązanie ostatniego składnika listy z jej pierwszym składnikiem. W wyniku takiego powiązania wyróżnione składniki przestają pełnić swoje funkcje. W liście cyklicznej żaden składnik nie jest wyróżniony.
Tworzenie listy cyklicznej, dołączanie do niej nowych elementów oraz ich usuwanie jest podobne do operacji wykonywanych na liście jedno- lub dwukierunkowej.
Na poniższym rysunku pokazano organizację dwukierunkowej listy cyklicznej.
2. Przetwarzanie list jednokierunkowych
Od wyboru właściwej w danym momencie struktury danych może zależeć wszystko: szybkość działania programu, możliwość jego łatwej modyfikacji, czytelność zapisu algorytmu i dobre samopoczucie programisty.
Każdy, kto poznał jakikolwiek język programowania, został niejako zmuszony do opanowania zasad posługiwania się tzw. typami podstawowymi: całkowitym, rzeczywistym, znakowym lub logicznym. Mogą one posłużyć jako elementy bazowe struktur, tablic, plików, które już zasługują na miano struktur danych, ale dość prymitywnych.
Prawdziwa przygoda rozpoczyna się dopiero, gdy dostajemy do ręki tzw. listy, drzewa binarne lub grafy. Wraz z nimi rozszerzają się znacznie możliwości rozwiązania programowego wielu ciekawych zagadnień.
2.1. Listy jednokierunkowe.
Lista jednokierunkowa jest oszczędną pamięciowo strukturą danych, pozwalających grupować dowolną, ograniczoną tylko dostępną pamięcią, liczbę elementów: liczb, znaków, struktur itd.
Jest to duża zaleta w porównaniu z tablicami, gdzie przydział dużego liniowego obszaru pamięci podczas wykonywania programu nie zawsze może zakończyć się sukcesem.
Do budowy listy jednokierunkowej wygodnie jest użyć dwa typy „komórek” pamięci. Pierwszy jest zwykłą strukturą natury informacyjnej, zawierającą dwa wskaźniki: do początku i do końca listy. Drugi typ komórek jest również strukturą, jednak ma on już charakter roboczy. Zawiera bowiem pole wartości i wskaźnik na następny element listy. Na poniższych rysunkach przedstawiono typy struktur używanych podczas programowania list oraz strukturę listy jednokierunkowej o kierunku „do przodu”.
W przykładzie dla uproszczenia operuje się wartościami typu całkowitego, co nie zmniejsza ogólności wywodu.
Jeśli lista jest pusta, to struktura informacyjna zawiera dwa wskaźniki NULL (składowe Glowa = NULL i Ogon = NULL).
Poniżej przytoczono tekst programu, który tworzy listę jednokierunkową o kierunku „do przodu” poprzez dołączanie kolejnych elementów na końcu listy, oraz umożliwia wyświetlenie na ekranie zawartości listy (patrz program PROG67.CPP):
/***************************************************************************************/
/* Program tworzy listę jednokierunkową bez sortowania elementów. */
/* Element roboczy listy przechowuje wartość typu całkowitego */
/* oraz wskaźnik na następny element. */
/* Utworzona lista jest ukierunkowana "do przodu". */
/* Program umożliwia również wyświetlenie kolejnych wartości */
/* całkowitych znajdujących się na liście. */
/***************************************************************************************/
#include <iostream.h>
#include <conio.h>
typedef struct El // struktura elementu roboczego
{ int Wartosc;
struct El *Nastepny; // wskaźnik do następnego elementu
} ELEMENT;
typedef struct // struktura elementu informacyjnego
{ ELEMENT *Glowa;
ELEMENT *Ogon;
} INFO;
int i,n, W;
INFO *Wsk_Info; // wskaźnik do elementu informacyjnego
void Do_Listy( int W);
void Pisz_Liste();
void Usun_Liste();
void main ()
{
clrscr();
cout << "Podaj długość listy: ";
cin >> n;
Wsk_Info = new INFO;
Wsk_Info->Glowa = NULL;
Wsk_Info->Ogon = NULL;
cout << "Wprowadź kolejne elementy listy:\n";
for (i=1; i <=n; i++)
{
cout << "el.";
cout.width(2);
cout << i << " = ";
cin >> W;
Do_Listy( W );
}
cout << "\nOto lista:\n " << endl;
Pisz_Liste();
Usun_Liste();
while ( !kbhit( ))
{ }
}
void Do_Listy(int W)
/* Funkcja dołącza nowy element do listy - na koniec listy */
{
ELEMENT *Nowy;
Nowy = new ELEMENT;
if (Wsk_Info->Glowa == NULL) // dołączenie nowego elementu
{ // do listy pustej
Wsk_Info->Glowa = Nowy;
Wsk_Info->Ogon = Wsk_Info->Glowa;
}
else // dołączenie nowego elementu
{ Wsk_Info->Ogon->Nastepny = Nowy; // na końcu listy niepustej
Wsk_Info->Ogon = Nowy;
}
Nowy->Wartosc = W;
Nowy->Nastepny = NULL;
}
void Pisz_Liste( )
/* Funkcja wyświetla elementy listy w kierunku od początku do końca */
{
ELEMENT *Biezacy;
int i = 0;
Biezacy = Wsk_Info->Glowa;
if (Wsk_Info->Glowa == NULL)
cout << "Lista jest pusta\n";
else while (Biezacy != NULL)
{
i++;
cout.width(2);
cout << i << ". " << Biezacy->Wartosc << endl;
Biezacy = Biezacy->Nastepny;
}
}
void Usun_Liste()
{
ELEMENT *Biezacy, *Usuniety;
Biezacy = Wsk_Info->Glowa;
if (Wsk_Info->Glowa == NULL)
cout << "Lista jest pusta";
else { while (Biezacy != NULL)
{
i++;
Usuniety = Biezacy;
Biezacy = Biezacy->Nastepny;
delete Usuniety;
}
if (Biezacy == NULL)
cout << "\nListę usunięto" << endl;
}
}
2.2. Lista jednokierunkowa posortowana
O wiele bardziej złożona jest funkcja dołączająca nowy element w takie miejsce, aby całość listy była widziana jako posortowana (np. niemalejąco). Ideę tworzenia takiej listy przedstawia poniższy rysunek, gdzie możemy zobaczyć sposób dołączenia liczby 7 do już istniejącej listy złożonej z elementów -21, 3 i 11.
Nowy element (narysowany jest w kolorze amarantowym) może zostać wstawiony na początek (a), koniec (b) listy, jak również gdzieś w środku (c). W każdym z tych przypadków w istniejącej liście trzeba znaleźć miejsce wstawienia, tzn. zapamiętać dwa wskaźniki: element, przed który mamy wstawić nowy i element, za którym mamy to zrobić. Do zapamiętania tych istotnych informacji posłużą nam zmienne Przed i Po. Następnie, gdy dowiemy się, gdzie jesteśmy, możemy dokonać wstawienia nowego elementu do listy. Sposób, w jaki tego dokonamy, zależy oczywiście od miejsca wstawienia i od tego, czy lista nie jest przypadkiem pusta.
Poniżej jest przedstawiony program, który tworzy posortowaną niemalejąco listę jednokierunkową o kierunku „do przodu” oraz wyświetla zawartość tej listy (patrz plik PROG68.CPP). W programie utworzono procedurę Do_Listy, która wstawia kolejny element we właściwym miejscu na liście. Pewne skomplikowanie tej procedury wynika z połączenia w niej poszukiwania miejsca wstawienia z samym dołączaniem elementu.
/****************************************************************************************/
/* Program tworzy listę jednokierunkową z sortowaniem elementów. */
/* Lista sortowana jest niemalejąco. */
/* Program umożliwia również wyświetlenie kolejnych elementów */
/* całkowitych znajdujących się na liście. */
/****************************************************************************************/
#include <iostream.h>
#include <conio.h>
typedef struct El // struktura elementu roboczego
{ int Wartosc;
struct El *Nastepny; // wskaźnik do następnego elementu
} ELEMENT;
typedef struct // struktura elementu informacyjnego
{ ELEMENT *Glowa;
ELEMENT *Ogon;
}INFO;
int i,n, W;
INFO *Wsk_Info; // wskaźnik do elementu informacyjnego
void Do_Listy( int W);
void Pisz_Liste();
void Usun_Liste();
void main ()
{
clrscr();
cout << "Podaj długość listy: ";
cin >> n;
Wsk_Info = new INFO;
Wsk_Info->Glowa = NULL;
Wsk_Info->Ogon = NULL;
cout << "Wprowadź kolejne elementy listy:\n";
for (i=1; i <=n; i++)
{
cout << "el.";
cout.width(2);
cout << i << " = ";
cin >> W;
Do_Listy(W);
}
cout << "\nOto lista posortowana:\n " << endl;
Pisz_Liste();
Usun_Liste();
while (!kbhit())
{ }
}
void Do_Listy(int W)
/* Funkcja dołącza nowy element we właściwym miejscu */
/* listy posortowanej. */
{
ELEMENT *Biezacy, *Nowy, *Przed, *Po; // Przed - adres poprzednika
// Po - adres następnika Biezacy
Nowy = new ELEMENT;
Biezacy = Wsk_Info->Glowa; // ustawienie się na początku listy
Przed = NULL;
Po = NULL;
Nowy->Wartosc = W;
// poszukiwanie miejsca wstawienia
if (Wsk_Info->Glowa == NULL) // lista jest pusta
{
Wsk_Info->Glowa = Nowy;
Wsk_Info->Ogon = Wsk_Info->Glowa;
Wsk_Info->Ogon->Nastepny = NULL;
}
else // lista nie jest pusta
{ do if (W > Biezacy->Wartosc)
{ Przed = Biezacy;
Po = Biezacy->Nastepny;
Biezacy = Po;
}
while ((W > Biezacy->Wartosc) && (Biezacy != NULL));
// wstawienie do listy
if (Biezacy == Wsk_Info->Glowa) // element jest mniejszy od pierwszego
{ Nowy->Nastepny = Wsk_Info->Glowa;
Wsk_Info->Glowa = Nowy;
}
else { if (Biezacy == NULL) // element jest większy od ostatniego
{ Wsk_Info->Ogon->Nastepny = Nowy;
Wsk_Info->Ogon = Nowy;
Wsk_Info->Ogon->Nastepny = NULL;
}
else // element jest w środku
{ Przed->Nastepny = Nowy;
Nowy->Nastepny = Po;
}
}
}
}
/*-----------------------------------------------------------------------------------------------*/
void Pisz_Liste()
/* Funkcja wyświetla elementy listy w kierunku od początku do końca */
{
ELEMENT *Biezacy;
int i = 0;
Biezacy = Wsk_Info->Glowa;
if (Wsk_Info->Glowa == NULL)
cout << "Lista jest pusta\n";
else while (Biezacy != NULL)
{
i++;
cout.width(2);
cout << i << ". " << Biezacy->Wartosc << endl;
Biezacy = Biezacy->Nastepny;
}
}
void Usun_Liste()
/* Funkcja usuwa listę z pamięci */
{
ELEMENT *Biezacy, *Usuniety;
Biezacy = Wsk_Info->Glowa;
if (Wsk_Info->Glowa == NULL)
cout << "Lista jest pusta";
else { while (Biezacy != NULL)
{
i++;
Usuniety = Biezacy;
Biezacy = Biezacy->Nastepny;
delete Usuniety;
}
if (Biezacy == NULL)
cout << "\nListę usunięto" << endl;
}
}
2.3. Wyszukiwanie zadanego elementu na liście
Kolejne ważne zadanie polega na odnalezieniu na liście pewnego elementu x. Zadanie nie należy do skomplikowanych. Wystarczy przejrzeć listę za pomocą zwykłej pętli while. Poniżej przytoczono treść funkcji przeszukującej Szukaj. Treść całego programu znajduje się w pliku PROG69.CPP.
/*****************************************************************************************/
/* Program tworzy listę jednokierunkową bez sortowania elementów. */
/* Element roboczy listy przechowuje wartość typu całkowitego */
/* oraz wskaźnik na następny element. */
/* Utworzona lista jest ukierunkowana "do przodu". */
/* Program umożliwia również wyświetlenie kolejnych elementów */
/* listy oraz odszukanie wskazanego elementu z listy. */
/****************************************************************************************/
#include <iostream.h>
#include <conio.h>
typedef struct El // struktura elementu roboczego
{ int Wartosc;
struct El *Nastepny; // wskaźnik do następnego elementu
} ELEMENT;
typedef struct // struktura elementu informacyjnego
{ ELEMENT *Glowa;
ELEMENT *Ogon;
} INFO;
int i,n, W, W1;
INFO * Wsk_Info; // wskaźnik do elementu informacyjnego
void Do_Listy( int W);
void Pisz_Liste();
void Szukaj( int W1);
/*-----------------------------------------------------------------------------------------------*/
void main ()
{
clrscr();
cout << "Podaj długość listy: ";
cin >> n;
Wsk_Info = new INFO;
Wsk_Info->Glowa = NULL;
Wsk_Info->Ogon = NULL;
cout << "Wprowadź kolejne elementy listy:\n";
for (i=1; i <=n; i++)
{
cout << "el.";
cout.width(2);
cout << i << " = ";
cin >> W;
Do_Listy(W);
}
cout << "\nOto lista:\n " << endl;
Pisz_Liste();
cout << "\nElement poszukiwany: ";
cin >> W1;
Szukaj(W1);
while (!kbhit())
{ }
}
/*-----------------------------------------------------------------------------------------------*/
void Do_Listy(int W)
/* Funkcja dołącza nowy element do listy - na koniec listy */
{
ELEMENT *Nowy;
Nowy = new ELEMENT;
if (Wsk_Info->Glowa == NULL) // dołączenie nowego elementu
{ // do listy pustej
Wsk_Info->Glowa = Nowy;
Wsk_Info->Ogon = Wsk_Info->Glowa;
}
else // dołączenie nowego elementu
{ Wsk_Info->Ogon->Nastepny = Nowy; // na końcu listy niepustej
Wsk_Info->Ogon = Nowy;
}
Nowy->Wartosc = W;
Nowy->Nastepny = NULL;
}
/*-----------------------------------------------------------------------------------------------*/
void Pisz_Liste()
/* Funkcja wyświetla elementy listy w kierunku od początku do końca */
{
ELEMENT *Biezacy;
int i = 0;
Biezacy = Wsk_Info->Glowa;
if (Wsk_Info->Glowa == NULL)
cout << "Lista jest pusta\n";
else while (Biezacy != NULL)
{
i++;
cout.width(2);
cout << i << ". " << Biezacy->Wartosc << endl;
Biezacy = Biezacy->Nastepny;
}
}
/*-----------------------------------------------------------------------------------------------*/
void Szukaj ( int W1 )
/* Funkcja wyszukuje wskazany element listy */
{
ELEMENT *Biezacy; // adres elementu bieżącego
int Znaleziono;
Znaleziono = 0;
Biezacy = Wsk_Info->Glowa;
if (Wsk_Info->Glowa == NULL) // lista jest pusta
cout << "Lista jest pusta\n";
else
{ do {
if (W1 == Biezacy->Wartosc) // element znaleziono
{ Znaleziono = 1;
cout << "Element " << W1 << " odnaleziono!\n";
}
else Biezacy = Biezacy->Nastepny;
}
while ((Znaleziono == 0) && (Biezacy != NULL));
if (Znaleziono == 0)
cout << "Brak elementu " << W1 << " na liście\n";
}
}
2.4. Usuwanie elementu z listy
Usuwanie elementu z listy, podobnie jak wstawianie elementu na właściwe miejsce listy posortowanej polega najpierw na lokalizacji elementu, a następnie na jego usunięciu, z którym wiąże się aktualizowanie powiązań pozostałych elementów listy.
Ideę usuwania elementu z listy przedstawia poniższy rysunek, gdzie możemy zobaczyć sposób usuwania liczby 7 z już istniejącej listy złożonej z elementów -21, 3, 7 i 11.
Sposób aktualizacji połączeń w wyniku usunięcia elementu z listy zależy od tego, czy usuwany element znajduje się na początku listy, na końcu, czy w środku listy. Poniżej przedstawiono funkcję usuwającą zadany element z listy. Odpowiedni program demonstracyjny znajduje się w pliku PROG70.CPP.
/***************************************************************************************/
/* Program tworzy listę jednokierunkową bez sortowania elementów. */
/* Element roboczy listy przechowuje wartość typu całkowitego */
/* oraz wskaźnik na następny element. */
/* Utworzona lista jest ukierunkowana "do przodu". */
/* Program umożliwia również wyświetlenie kolejnych elementów */
/* listy oraz usunięcie wskazanego elementu z listy. */
/***************************************************************************************/
#include <iostream.h>
#include <conio.h>
typedef struct El // struktura elementu roboczego
{ int Wartosc;
struct El *Nastepny; // wskaźnik do następnego elementu
} ELEMENT;
typedef struct // struktura elementu informacyjnego
{ ELEMENT *Glowa;
ELEMENT *Ogon;
}INFO;
int i,n, W, W1;
INFO *Wsk_Info; // wskaźnik do elementu informacyjnego
void Do_Listy( int W);
void Pisz_Liste();
void Usun_Z_Listy( int W1);
void main ()
{
clrscr();
cout << "Podaj długość listy: ";
cin >> n;
Wsk_Info = new INFO;
Wsk_Info->Glowa = NULL;
Wsk_Info->Ogon = NULL;
cout << "Wprowadź kolejne elementy listy:\n";
for (i=1; i <=n; i++)
{
cout << "el.";
cout.width(2);
cout << i << " = ";
cin >> W;
Do_Listy(W);
}
cout << "\nOto lista:\n " << endl;
Pisz_Liste();
cout << "\nElement poszukiwany: ";
cin >> W1;
Usun_Z_Listy(W1);
Pisz_Liste();
while (!kbhit())
{ }
}
/*-----------------------------------------------------------------------------------------------*/
void Do_Listy(int W)
/* Funkcja dołącza nowy element do listy - na koniec listy */
{
ELEMENT *Nowy;
Nowy = new ELEMENT;
if (Wsk_Info->Glowa == NULL) // dołączenie nowego elementu
{ // do listy pustej
Wsk_Info->Glowa = Nowy;
Wsk_Info->Ogon = Wsk_Info->Glowa;
}
else // dołączenie nowego elementu
{ Wsk_Info->Ogon->Nastepny = Nowy; // na końcu listy niepustej
Wsk_Info->Ogon = Nowy;
}
Nowy->Wartosc = W;
Nowy->Nastepny = NULL;
}
/*-----------------------------------------------------------------------------------------------*/
void Pisz_Liste()
/* Funkcja wyświetla elementy listy w kierunku od początku do końca */
{
ELEMENT *Biezacy;
int i = 0;
Biezacy = Wsk_Info->Glowa;
if (Wsk_Info->Glowa == NULL)
cout << "Lista jest pusta\n";
else while (Biezacy != NULL)
{
i++;
cout.width(2);
cout << i << ". " << Biezacy->Wartosc << endl;
Biezacy = Biezacy->Nastepny;
}
}
/*-----------------------------------------------------------------------------------------------*/
void Usun_Z_Listy ( int W1 )
/* Funkcja usuwa zadany element z listy */
{
ELEMENT *Biezacy, // adres elementu bieżącego
*Przed, // adres elementu poprzedzającego usuwany
*Po; // adres elementu następnego po usuwanym
int Usuniety;
Usuniety = 0; // lokalizacja elementu usuwanego
Biezacy = Wsk_Info->Glowa;
Przed = NULL;
Po = NULL;
if (Wsk_Info->Glowa == NULL) // lista jest pusta
cout << "Lista jest pusta\n";
else
{ do {
if (W1 == Biezacy->Wartosc) // element znaleziono
{ Usuniety = 1;
if (Biezacy == Wsk_Info->Glowa) //element jest na początku
{ Wsk_Info->Glowa = Wsk_Info->Glowa->Nastepny;
delete Biezacy;
}
else if (Biezacy == Wsk_Info->Ogon) //element jest
//na końcu
{ Przed->Nastepny = NULL;
delete Wsk_Info->Ogon;
Wsk_Info->Ogon = Przed;
}
else { Przed->Nastepny = Po; //element jest w środku
delete Biezacy;
} // element znaleziono
}
else { Przed = Biezacy; // elementu na razie nie znaleziono
Biezacy = Biezacy->Nastepny;
Po = Biezacy->Nastepny;
}
}
while ((Usuniety == 0) && (Biezacy != NULL)); //koniec szukania
if (Usuniety == 0)
cout << "Brak elementu " << W1 << " na liście\n";
else cout << "Element " << W1 << " został usunięty z listy\n";
}
}
/*-----------------------------------------------------------------------------------------------*/
12
Liczba
Wskaznik
wierzchołek stosu
Liczba
Wskaznik
Liczba
Wskaznik
Liczba
Wskaznik
Liczba
Wskaznik
Liczba
Wskaznik
Liczba
Wskaznik
dno stosu
element 1
element 2
element 3
element 4
element n-1
element n
NULL
Liczba
Wskaznik
Liczba
Wskaznik
Liczba
Wskaznik
Liczba
Wskaznik
Liczba
Wskaznik
element 1
element 2
element 3
element n-1
element n
NULL
początek kolejki
koniec kolejki
wejście
wyjście
Liczba
Wskaznik
Liczba
Wskaznik
Liczba
Wskaznik
Liczba
Wskaznik
Liczba
Wskaznik
element 1
element 2
element 3
element n-1
element n
NULL
początek listy
koniec listy
Lista jednokierunkowa o kierunku
„do przodu”
Liczba
Wskaznik
Liczba
Wskaznik
Liczba
Wskaznik
Liczba
Wskaznik
Liczba
Wskaznik
element 1
element 2
element 3
element n-1
element n
początek listy
koniec listy
NULL
Lista jednokierunkowa o kierunku
„do tyłu”
Liczba
Wskaznik_2
Wskaznik_1
Liczba
Wskaznik_2
Wskaznik_1
Liczba
Wskaznik_2
Wskaznik_1
Liczba
Wskaznik_2
Wskaznik_1
Liczba
Wskaznik_2
Wskaznik_1
Liczba
Wskaznik_2
Wskaznik_1
element 1
element 2
element 3
element n-1
element n
koniec listy
początek listy
NULL
NULL
Liczba
Wskaznik_2
Wskaznik_1
Liczba
Wskaznik_2
Wskaznik_1
Liczba
Wskaznik_2
Wskaznik_1
Liczba
Wskaznik_2
Wskaznik_1
Liczba
Wskaznik_2
Wskaznik_1
Glowa
Ogon
Wartosc
Nastepny
struktura informacyjna
struktura robocza
Glowa
Ogon
17
-123
4
NULL
-21
3
11
7
Przed
Po
NULL
a)
b)
c)
Po = NULL
Przed = NULL
-21
3
11
7
Przed
Po
Null