#include <string>
#include <iostream>
using namespace std;

 struct student {

			int fn;

			string name;

			student* next;

	  } *group = NULL, *last = NULL; 


	  void add()

	  {

			student* s=new student;

			cout<<"Fakulteten nomer=";

			cin>>s->fn;

			cout<<"Ime=";

			cin>>s->name;

			s->next=NULL;

			if(!group)

				  group=last=s;

			else

				  last->next=s;

			last=s;

	  }  

	  void list()


	  {

			student* s=group;

			while(s)

			{

				  cout<<"#"<<s->fn<<" - "<<s->name<<"\n";

				  s=s->next;

			}

	  } 

	  void search() {

			student* s=group;

			int search;

			cout<<"Vavedete fakulteten nomer za tarsene=";

			cin>>search;

			while(s)

			{

				  if(search==s->fn)

				  {

						cout<<"Namereno #"<<s->fn<<" - "<<s->name<<"\n";

						break;

				  }

				  s=s->next;

			}

	  } 

		void sort() {

		   student *lst, *tmp = group, *prev, *potentialprev = group;

		   int idx, idx2, n = 0;

		   student* s=group;

		   while(s)

			{

				   n++;

				  s=s->next;

			}

			for (idx=0; idx<n-1; idx++) 

			  {

				for (idx2=0,lst=group; 

					 lst && lst->next && (idx2<=n-1-idx);

					 idx2++)

				{

				  if (!idx2)

				  {

					prev = lst;

				  }


				  if (lst->next->fn < lst->fn) 

				  {  

					tmp = (lst->next?lst->next->next:0);


					if (!idx2 && (prev == group))

					{

					  group = lst->next;

					}

					potentialprev = lst->next;

					prev->next = lst->next;

					lst->next->next = lst;

					lst->next = tmp;

					prev = potentialprev;

				  }

				  else

				  {

					lst = lst->next;

					if(idx2)

					{

					  prev = prev->next;

					}

				  }	 

				} 

			  }

			  list();

	  }

	  void del() {

			student* s=group, *prev=group;

			int search;

			cout<<"Vavedete fakulteten nomer za iztrivane=";

			cin>>search;

			while(s) {

				  if(search==s->fn) {

						prev->next=s->next;

						if(s==last) last=prev;

						if(s==group) group=s->next;

						delete s;


						break; 

						}

			   prev=s;

			   s=s->next; 

			}


	  } 

	  int main(int argc, char* argv[])

	  {

			int choice;

			do {

				  cout<<"\n =============================================";

				  cout<<"\n1.Dobavi\n2.Pokaji\n3.Tarsi\n";

				  cout<<"4.Iztriy\n5.Sortiray\n6.Exit\n";

				  cout<<"\n =============================================";

				  cout<<"\nIzberete:";

				  cin>>choice;

				  switch(choice) {

					  case 1: add(); break;

					  case 2: list(); break;

					  case 3: search(); break;

					  case 4: del(); break;

					  case 5: sort(); break;

				  }

	  } while(choice!=6);


	  return 0;


	}