// 1.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
// deklaracja typu elementu listy
//-------------------------------
struct TlistElement
{
TlistElement * next;
int key;
};
// deklaracja typu klasy listy jednokierunkowej
//---------------------------------------------
class TsingleList
{
private:
TlistElement * front, * back;
int counter;
public:
// konstruktor
//------------
TsingleList()
{
front = back = NULL;
counter = 0;
}
// destruktor
//-----------
//~TsingleList()
//{
// TlistElement * p;
//
// while(front)
// {
// p = front->next;
// delete front;
// front = p;
// }
//}
// Zwraca długość listy
//---------------------
int size()
{
return counter;
}
// Dodaje element na początku listy i zwraca jego adres
//-----------------------------------------------------
TlistElement * push_front(TlistElement * p)
{
p->next = front;
front = p;
if(!back) back = front;
counter++;
return front;
}
// Dodaje element na końcu listy i zwraca jego adres
//--------------------------------------------------
TlistElement * push_back(TlistElement * p)
{
if(back) back->next = p;
p->next = NULL;
back = p;
if(!front) front = back;
counter++;
return back;
}
// Dodaje element p1 za elementem p2 i zwraca adres p1
//----------------------------------------------------
TlistElement * insert(TlistElement * p1, TlistElement * p2)
{
p1->next = p2->next;
p2->next = p1;
if(!(p1->next)) back = p1;
counter++;
return p1;
}
//--------------------------------------------------------------
TlistElement * insert2(TlistElement * p1, int n)
{if (n!=1){
TlistElement *p2;
p2 = index(n-1);
p1->next = p2->next;
p2->next = p1;
if(!(p1->next)) back = p2;
counter++;
return p1;}
else
push_front(p1);
}
// Usuwa element z początku listy i zwraca adres usuniętego elementu
//------------------------------------------------------------------
TlistElement * pop_front()
{
TlistElement * p;
if(front)
{
p = front;
front = front->next;
if(!front) back = NULL;
counter--;
return p;
}
else return NULL;
}
// Usuwa element z końca listy i zwraca adres usuniętego elementu
//---------------------------------------------------------------
TlistElement * pop_back()
{
TlistElement * p;
if(back)
{
p = back;
if(p == front) front = back = NULL;
else
{
back = front;
while(back->next != p) back = back->next;
back->next = NULL;
}
counter--;
return p;
}
else return NULL;
}
// usuwa z listy element p i zwraca adres usuniętego elementu
TlistElement * erase(TlistElement * p)
{
TlistElement * p1;
if(p == front) return pop_front();
else
{
p1 = front;
while(p1->next != p) p1 = p1->next;
p1->next = p->next;
if(!(p1->next)) back = p1;
counter--;
return p;
}
}
// zwraca n-ty element listy. Jeśli lista posiada mniej niż n elementów,
// zwraca NULL. Elementy numerujemy od 1.
//----------------------------------------------------------------------
TlistElement * index(unsigned n)
{
TlistElement * p;
if((!n) || (n > counter)) return NULL;
else if(n == counter) return back;
else
{
p = front;
while(--n) p = p->next;
return p;
}
}
//Szukanie danego klucza
//-----------------------
void search(int b)
{ int flaga=0;
TlistElement *bb;
bb=front;
while(bb)
{
if(bb->key==b)
flaga=1;
bb=bb->next;
}
if(flaga==1) cout<<"jest"<<endl;
else cout<<"nie ma"<<endl;
}
// wyświetla kolejno klucze wszystkich elementów listy
//----------------------------------------------------
void showKeys()
{
TlistElement * p;
if(!front) cout << "Lista jest pusta." << endl;
else
{
p = front;
while(p)
{
cout << p->key << " ";
p = p->next;
}
cout << endl;
}
}
};
//************************************************************************
//** Przykładowa aplikacja testująca utworzoną klasę TsingleList **
//************************************************************************
int _tmain(int argc, _TCHAR* argv[])
{
TsingleList sl;
TlistElement * p;
int i;
cout << "(A) : "; sl.showKeys();
// tworzymy pięć elementów dodając je kolejna na początek listy
for(i = 1; i <= 5; i++)
{
p = new TlistElement;
p->key = i;
sl.push_front(p);
}
cout << "(B) : "; sl.showKeys();
// tworzymy pięć elementów dodając je kolejna na koniec listy
for(i = 1; i <= 5; i++)
{
p = new TlistElement;
p->key = i;
sl.push_back(p);
}
cout << "(C) : "; sl.showKeys();
// usuwamy pierwszy element listy
sl.pop_front();
cout << "(D) : "; sl.showKeys();
// usuwamy ostatni element listy
sl.pop_back();
cout << "(E) : "; sl.showKeys();
// usuwamy trzeci element z listy moze byc wybrany!!!!
delete sl.erase(sl.index(3));
cout << "(F) : "; sl.showKeys();
//// usuwamy przedostatni element z listy
//
// delete sl.erase(sl.index(sl.size() - 1));
//
// cout << "(G) : "; sl.showKeys();
//Za czwartym elementem listy wstawiamy nowy element z kluczem 9
p = new TlistElement;
p->key = 9;
sl.insert(p,sl.index(4));
cout << "(H) : "; sl.showKeys();
p = new TlistElement;
p->key = 1;
sl.insert2(p,1);
cout<<"(H2) : "; sl.showKeys();
//szukanie elementu
sl.search(5);
// usuwamy wszystkie elementy z listy
while(sl.size()) sl.pop_front();
cout << "(I) : "; sl.showKeys();
cout << endl << endl;
system("PAUSE");
}