lista liniowa
#include <iostream>
#include <time.h>
using namespace std;
class lista{
private:
lista **head;
lista *newNode;
lista *pomoc;
public:
int key;
lista *next;
int data;
lista()
{
head=new lista*;
*head=NULL;
}
//interfejs
lista& dodajWezel(int);
lista& dodajWiele();
lista* wyszukaj(int);
lista& usun(int);
lista& wyswietl();
};
lista& lista::dodajWezel(int key)
{
lista *poprzednik;
newNode=new lista;
newNode->key=key;
newNode->next=NULL;
newNode->data=rand();
poprzednik=NULL;
pomoc=*head;
if(!pomoc) //lista pusta
{
*head=newNode;
return *this;
}
if(pomoc->key==key) // dublowanie wezlow
{
cout<<"Wezel o podanym kluczu juz istnieje\n\n";
return *this;
}
while(pomoc)
{
if(pomoc->key<key)
{
poprzednik=pomoc;
pomoc=poprzednik->next;
if(pomoc!=NULL && pomoc->key==key) //dublowanie wezlow
{
cout<<"Wezel o podanym kluczu juz istnieje\n\n";
return *this;
}
}
else
{
if(!poprzednik) //pierwszy element
{
*head=newNode;
newNode->next=pomoc;
return *this;
}
poprzednik->next=newNode;
newNode->next=pomoc;
return *this;
}
}
poprzednik->next=newNode;
return *this;
}
lista& lista::wyswietl()
{
int i(1);
pomoc=*head;
while(pomoc)
{
cout<<"\nWezel "<<i<<"\n\n\tKlucz: "<<pomoc->key<<"\tDane : "<<pomoc->data;
pomoc=pomoc->next;
i++;
}
cout<<"\n\n";
return *this;
}
lista& lista::dodajWiele()
{
int rozmiar,i,j,*tabkey,key;
srand(time(0));
cout<<"podaj liczbe wezlow: ";
cin>>rozmiar;
tabkey=new int [rozmiar];
for(i=0; i<rozmiar; i++)
{
key=rand();
for(j=0; j<i; j++)
{
if(tabkey[j]==key)
{
key=rand();
j=-1;
}
}
tabkey[i]=key;
}
for(i=1; i<=rozmiar; i++)
{
dodajWezel(tabkey[i-1]);
}
return *this;
}
lista& lista::usun(int key)
{
lista *pomoc,*poprzednik;
pomoc=*head;
if(pomoc->key==key)
{
*head=pomoc->next;
delete[] pomoc;
return *this;
}
poprzednik=pomoc;
pomoc=pomoc->next;
while(pomoc)
{
if(pomoc->key==key)
{
poprzednik->next=pomoc->next;
delete[] pomoc;
return *this;
}
poprzednik=pomoc;
pomoc=pomoc->next;
}
cout<<"Brak zadanego elementu\n\n";
return this;
}
lista lista::wyszukaj(int key)
{
lista* pomoc;
pomoc=*head;
while(pomoc)
{
if(pomoc->key==key)
{
cout<<"Znaleziono wezel "<<key<<"\n\n";
return pomoc;
}
pomoc=pomoc->next;
}
cout<<"Nie znaleziono wezla o podanym kluczu\n\n";
return NULL;
}
void main()
{
lista slownik,*a;
slownik.dodajWezel(12).dodajWezel(13).dodajWezel(4).wyswietl().usun(10).wyswietl();
system("pause");
}
lisata cykliczna
#include <iostream>
#include <time.h>
using namespace std;
class lista{
private:
lista *tail;
lista **head;
lista *newNode;
lista *pomoc;
public:
int key;
lista *next;
int data;
lista()
{
head=new lista*;
*head=NULL;
}
//interfejs
lista& dodajWezel(int);
lista& dodajWiele();
lista* wyszukaj(int);
lista& usun(int);
lista& wyswietl();
};
lista& lista::dodajWezel(int key)
{
lista *poprzednik;
int wartownik(1);
newNode=new lista;
newNode->key=key;
newNode->next=*head;
newNode->data=rand();
poprzednik=NULL;
pomoc=*head;
if(!pomoc) //lista pusta
{
*head=newNode;
newNode->next=*head;
tail=newNode;
return *this;
}
if(pomoc->key==key) // dublowanie wezlow
{
cout<<"Wezel o podanym kluczu juz istnieje\n\n";
return *this;
}
while(wartownik)
{
if(pomoc->key<key)
{
poprzednik=pomoc;
pomoc=poprzednik->next;
if(pomoc==*head) wartownik=0;
if(pomoc!=NULL && pomoc->key==key) //dublowanie wezlow
{
cout<<"Wezel o podanym kluczu juz istnieje\n\n";
return *this;
}
}
else
{
if(!poprzednik) //pierwszy element
{
*head=newNode;
newNode->next=pomoc;
tail->next=*head;
return *this;
}
poprzednik->next=newNode;
newNode->next=pomoc;
return *this;
}
}
poprzednik->next=newNode;
tail=newNode;
return *this;
}
lista& lista::wyswietl()
{
int i(1);
pomoc=*head;
while(1)
{
cout<<"\nWezel "<<i<<"\n\n\tKlucz: "<<pomoc->key<<"\tDane: "<<pomoc->data;
pomoc=pomoc->next;
if(pomoc==*head) break;
i++;
}
cout<<"\n\n";
return *this;
}
lista& lista::dodajWiele()
{
int rozmiar,i,j,*tabkey,key;
cout<<"podaj liczbe wezlow: ";
cin>>rozmiar;
tabkey=new int [rozmiar];
for(i=0; i<rozmiar; i++)
{
key=rand();
for(j=0; j<i; j++)
{
if(tabkey[j]==key)
{
key=rand();
j=-1;
}
}
tabkey[i]=key;
}
for(i=1; i<=rozmiar; i++)
{
dodajWezel(tabkey[i-1]);
}
return *this;
}
lista& lista::usun(int key)
{
lista *pomoc,*poprzednik;
pomoc=*head;
if(pomoc->key==key)
{
*head=pomoc->next;
tail->next=*head;
delete[] pomoc;
return *this;
}
poprzednik=pomoc;
pomoc=pomoc->next;
while(pomoc)
{
if(pomoc->key==key)
{
if(pomoc->next==*head) tail=poprzednik;
poprzednik->next=pomoc->next;
delete[] pomoc;
return *this;
}
poprzednik=pomoc;
pomoc=pomoc->next;
}
cout<<"Brak zadanego elementu\n\n";
return *this;
}
lista* lista::wyszukaj(int key)
{
lista* pomoc;
pomoc=*head;
while(pomoc)
{
if(pomoc->key==key)
{
cout<<"Znaleziono wezel "<<key<<"\n\n";
return pomoc;
}
pomoc=pomoc->next;
if(pomoc==*head) break;
}
cout<<"Nie znaleziono wezla o podanym kluczu\n\n";
return NULL;
}
void main()
{
lista slownik;
slownik.dodajWiele().wyswietl();
system("pause");
}
lista 2kierunkowa
#include <iostream>
#include <time.h>
using namespace std;
class lista{
private:
lista **head;
lista *tail;
lista *newNode;
lista *pomoc;
public:
int key;
lista *next;
lista *previous;
int data;
lista()
{
head=new lista*;
*head=NULL;
}
//interfejs
lista& dodajWezel(int);
lista& dodajWiele();
lista* wyszukaj(int);
lista& usun(int);
lista& wyswietl();
lista& wyswietltyl();
};
lista& lista::dodajWezel(int key)
{
lista *poprzednik;
newNode=new lista;
newNode->key=key;
newNode->next=NULL;
newNode->previous=NULL;
newNode->data=rand();
poprzednik=NULL;
pomoc=*head;
if(!pomoc) //lista pusta
{
*head=newNode;
tail=newNode;
newNode->previous=NULL;
return *this;
}
if(pomoc->key==key) // dublowanie wezlow
{
cout<<"Wezel o podanym kluczu juz istnieje\n\n";
return *this;
}
while(pomoc)
{
if(pomoc->key<key)
{
poprzednik=pomoc;
pomoc=poprzednik->next;
if(pomoc!=NULL && pomoc->key==key) //dublowanie wezlow
{
cout<<"Wezel o podanym kluczu juz istnieje\n\n";
return *this;
}
}
else
{
if(!poprzednik) //pierwszy element
{
*head=newNode;
newNode->next=pomoc;
pomoc->previous=newNode;
newNode->previous=NULL;
return *this;
}
poprzednik->next=newNode;
newNode->next=pomoc;
pomoc->previous=newNode;
newNode->previous=poprzednik;
return *this;
}
}
poprzednik->next=newNode;
tail=newNode;
newNode->previous=poprzednik;
return *this;
}
lista& lista::wyswietl()
{
int i(1);
pomoc=*head;
while(pomoc)
{
cout<<"\nWezel "<<i<<"\n\n\tKlucz: "<<pomoc->key<<"\tDane : "<<pomoc->data<<"\t"<<pomoc<<" "<<pomoc->next<<" "<<pomoc->previous;
pomoc=pomoc->next;
i++;
}
if(i==1) cout<<"Lista jest pusta\n\n";
cout<<"\n\n";
return *this;
}
lista& lista::wyswietltyl()
{
int i(1);
pomoc=tail;
while(pomoc)
{
cout<<"Wezel "<<i<<"\n\n\t"<<"Klucz: "<<pomoc->key<<"\tDane: "<<pomoc->data<<"\n";
pomoc=pomoc->previous;
i++;
}
cout<<"\n\n";
return *this;
}
lista& lista::dodajWiele()
{
int rozmiar,i,j,*tabkey,key;
srand(time(0));
cout<<"podaj liczbe wezlow: ";
cin>>rozmiar;
tabkey=new int [rozmiar];
for(i=0; i<rozmiar; i++)
{
key=rand();
for(j=0; j<i; j++)
{
if(tabkey[j]==key)
{
key=rand();
j=-1;
}
}
tabkey[i]=key;
}
for(i=1; i<=rozmiar; i++)
{
dodajWezel(tabkey[i-1]);
}
return *this;
}
lista& lista::usun(int key)
{
lista *pomoc,*poprzednik;
pomoc=*head;
if(pomoc->key==key)
{
*head=pomoc->next;
pomoc->next->previous=NULL;
delete[] pomoc;
return *this;
}
poprzednik=pomoc;
pomoc=pomoc->next;
while(pomoc)
{
if(pomoc->key==key)
{
poprzednik->next=pomoc->next;
if(pomoc->next!=NULL) pomoc->next->previous=poprzednik;
delete[] pomoc;
return *this;
}
poprzednik=pomoc;
pomoc=pomoc->next;
}
cout<<"Brak zadanego elementu\n\n";
return this;
}
lista lista::wyszukaj(int key)
{
lista* pomoc;
pomoc=*head;
while(pomoc)
{
if(pomoc->key==key)
{
cout<<"Znaleziono wezel "<<key<<"\n\n";
return pomoc;
}
pomoc=pomoc->next;
}
cout<<"Nie znaleziono wezla o podanym kluczu\n\n";
return NULL;
}
void main()
{
lista slownik,*a;
slownik.dodajWezel(1).dodajWezel(2).dodajWezel(3).dodajWiele().wyswietl().wyswietltyl();
system("pause");
}