Uczę się z książki: Algorytmy, struktury danych i techniki programowania. Wydanie V i jest tam przykład listy.
lista.h
// definicje pomocniczych typ�w danych
enum szukanie {PORAZKA=0, SUKCES=1};
typedef struct rob{
int wartosc;
struct rob *nastepny; // wska�nik do
}ELEMENT; // nast�pnego elementu
class LISTA{ // pocz�tek deklaracji klasy LISTA
public:
// nag��wki:
friend LISTA& operator +(LISTA&, LISTA&); // sumuje dwie listy
friend void fuzja(LISTA &x, LISTA &y); // realizacja poza klas�, jako funkcja zaprzyja�niona!
void wypisz(); // wypisuje zawarto�� listy
int szukaj(int x); // szuka elementu x na li�cie
void naKoniec(int x); // dorzuca bez sortowania
void dodSort(int x); // dorzuca z sortowaniem
LISTA& operator --(int); // usuwa ostatni element listy, przedefiniowany operator --, parametr 'int' jest sztuczny, informuje
// kompilator o tym, �e jest to operator "przyrostkowy"
// kilka prostych metod:
bool pusta(){ // czy lista co� zawiera?
return (inf.glowa==NULL);
}
void zeruj(){ // zeruje list� bez wykonywania "delete"
inf.glowa=inf.ogon=NULL;
}
LISTA(){ // konstruktor
inf.glowa=inf.ogon=NULL;
}
~LISTA(){ // destruktor, kt�ry u�ywa przedefiniowanego wcze�niej operatora --
while (!pusta()) (*this)--;
}
private:
typedef struct{ // definicja struktury informacyjnej, kt�ta zapewni dost�p do listy
ELEMENT *glowa;
ELEMENT *ogon;
}INFO;
INFO inf; // deklacja zmiennej zawiewraj�cej struktur� informacyjn�
}; //koniec deklaracji klasy LISTA
lista.cpp
#include <iostream>
#include "lista.h"
using namespace std;
void LISTA::naKoniec(int x){ // do��czamy rekord na koniec listy
// bez sortowania
ELEMENT *q=new ELEMENT;
q->wartosc=x;
q->nastepny=NULL;
if (pusta()) // lista pusta?
inf.glowa=inf.ogon=q;
else{ // co� jest w liscie
(inf.ogon)->nastepny=q;
inf.ogon=q;
}
}
// -------------------------------------------------------
LISTA& LISTA::operator --(int)
{
if (inf.glowa==inf.ogon){ // jeden element (lub lista pusta)
delete inf.glowa;
inf.glowa=inf.ogon=NULL;
} else{
ELEMENT *temp=inf.glowa;
while ((temp->nastepny) != inf.ogon) // szukamy przedostatniego
temp=temp->nastepny; // elementu listy...
inf.ogon=temp;
delete temp->nastepny; // ... i usuwamy go
temp->nastepny=NULL;
}
return (*this); // zwracamy zmodyfikowany obiekt
}
// -------------------------------------------------------
void LISTA::dodSort(int x){ // do��czamy rekord na w�a�ciwe miejsce z sortowaniem
ELEMENT *q=new ELEMENT; // tworzymy nowy element listy
q->wartosc=x;
// Poszukiwanie w�asciwej pozycji na wstawienie elementu
if (pusta()){
inf.glowa=inf.ogon=q;
q->nastepny=NULL;
}
else{ //szukamy miejsca na wstawienie
ELEMENT *przed=NULL,*po=inf.glowa;
enum {SZUKAJ,ZAKONCZ} stan=SZUKAJ; // zmienna wyliczeniowa
while ((stan==SZUKAJ) && (po!=NULL))
if (po->wartosc>=x)
stan=ZAKONCZ; // znale�li�my w�a�ciwe miejsce!
else{ // przemieszczamy si� w poszukiwaniach w�a�ciwego miejsca
przed=po; // wska�niki "przed" i "po"
po=po->nastepny;// zapami�taj� miejsce wstawiania
}
if (przed==NULL){ // wstawiamy na pocz�tek listy
inf.glowa=q;
q->nastepny=po;
} else
if (po==NULL){// wstawiamy na koniec listy
inf.ogon->nastepny=q;
q->nastepny=NULL;
inf.ogon=q;
}else{ // wstawiamy gdzie� w �rodku
przed->nastepny=q;
q->nastepny=po;
}
}
}
// -------------------------------------------------------
LISTA& operator +(LISTA &x, LISTA &y){
LISTA *temp=new LISTA;
ELEMENT *q1=(x.inf).glowa; // wska�niki robocze
ELEMENT *q2=(y.inf).glowa;
while (q1 != NULL){ // przekopiowanie listy x do temp
temp->dodSort(q1->wartosc);
q1=q1->nastepny;
}
while (q2 != NULL){ // przekopiowanie listy y do temp
temp->dodSort(q2->wartosc);
q2=q2->nastepny;
}
return (*temp);
}
// ------------------------------------------------------
ELEMENT *sortuj(ELEMENT *a, ELEMENT *b){
if (a==NULL)
return b;
if (b==NULL)
return a;
if (a->wartosc<=b->wartosc)
{
a->nastepny=sortuj(a->nastepny,b);
return a;
}else
{
b->nastepny=sortuj(b->nastepny,a);
return b;
}
}
// ------------------------------------------------------
// Uwaga: zauwa�, �e funkcja fuzja jest zaprzyja�niona z klas� LISTA i dlatego realizujemy j� poza cia�em klasy
void fuzja(LISTA &x, LISTA &y){ // a i b musz� by� posortowane
ELEMENT *a=x.inf.glowa, *b=y.inf.glowa;
ELEMENT *wynik=sortuj(a,b);
x.inf.glowa=wynik;
if(x.inf.ogon->wartosc <= y.inf.ogon->wartosc)
x.inf.ogon=y.inf.ogon;
else
x.inf.ogon=x.inf.ogon;
y.zeruj();
}
// -------------------------------------------------------
void LISTA::wypisz(){
ELEMENT *q=inf.glowa;
if (pusta())
cout << "(lista pusta)";
else
while (q != NULL){
cout << q->wartosc << " ";
q=q->nastepny;
}
cout << endl;
}
// -------------------------------------------------------
int LISTA::szukaj(int x){
ELEMENT *q=inf.glowa;
while (q != NULL){
if (q->wartosc==x)
return SUKCES;
q=q->nastepny;
}
return PORAZKA;
}
// -------------------------------------------------------
int main(){
LISTA l1,l2;
const int n=6;
int tab1[n]={2, 5, -11, 4, 14, 12}; // ka�dy element tablicy zostanie wstawiony do listy
cout << "\nL1 = ";
for (int i=0; i<n; l1.dodSort(tab1[i++]));
l1.wypisz();
int tab2[n]={9,6,77,1,7,4};
cout << "L2 = ";
for (int i=0; i<n; l2.dodSort(tab2[i++]));
l2.wypisz();
cout << "Efekt poszukiwan liczby 14 w liscie l1: " << l1.szukaj(14) << endl;
cout << "Efekt poszukiwan liczby 0 w liscie l1: " << l1.szukaj(0) << endl;
cout << "Oto lista bedaca suma dwoch poprzednich\nL3 = ";
LISTA l3=l1+l2;
l3.wypisz();
cout << "Listy L1 i L2 pozostaly bez zmian:\nL1 = ";
l1.wypisz();
cout << "L2 = ";
l2.wypisz();
cout << "Lista L1 bez dwoch ostatnich elementow:\nL1 = ";
(l1--)--.wypisz();
cout << "Efekt fuzji L1 z L2:\n";
fuzja(l1,l2);
cout << "L1 = ";
l1.wypisz();
cout << "L2 = ";
l2.wypisz();
l1.dodSort(80);l1.dodSort(8);
cout << "Dorzucamy do L1 liczby 80 i 8\nL1 = ";
l1.wypisz();
}
Według mnie ten kawełk kodu w funkcji fuzja jest niepotrzebny:
if(x.inf.ogon->wartosc <= y.inf.ogon->wartosc)
x.inf.ogon=y.inf.ogon;
else
x.inf.ogon=x.inf.ogon;
Po jego usunięciu wszystko działa, więc czy mam racje że jest niepotrzebny?