//BT CTDL so 1
//Nguyen Le Hoang Chuong - 0650080089
//Lop: 06_ÐHCNTT3
#include <iostream.h>
#include<string>
#include<cstdlib>
#include<ctime>
using namespace std;
struct sinhvien
{
	string ten89;
	int stt89;
};
struct	Node
{
sinhvien data89;  
Node *pNext89;
};
typedef struct Node NODE;
struct List
{
Node* pHead89;
Node* pTail89;
};
typedef struct List LIST;
void Init89(List &l)
{
l.pHead89 = l.pTail89 = NULL;
}
NODE* GetNODE89(sinhvien x) 
{
	NODE *p = new NODE;
	if(p == NULL)
	{
		return NULL;
	}
	p->data89 = x;
	p->pNext89 = NULL;
	return p;
}
void nhapt(sinhvien &sv)
{
		fflush(stdin);
		cout<<"Nhap ten sv:";	
		getline(std::cin,sv.ten89);
		cout<<"\tNhap stt cua sv:";
		cin>>sv.stt89;
}
int sosanh(int a,int b)
{
	if (a==b) return 1;
	return 0;
}
void themdauds89(List &l)
{
	sinhvien sv;
	nhapt(sv);
	Node*p=GetNODE89(sv);
	if (l.pHead89 == NULL)
	{
	l.pHead89 = l.pTail89 = p;
	}
	else
	{
	p->pNext89 = l.pHead89;  
	l.pHead89 = p;
	}
}
void themcuoids89(List &l)
{
	sinhvien sv;
	nhapt(sv);
	Node*p=GetNODE89(sv);
	if (l.pHead89 == NULL)
	{
	l.pHead89 = l.pTail89 = p;
	}
	else
	{
	l.pTail89->pNext89 = p;
	l.pTail89 = p ;
	}
}

void themgiua89(List&l,Node*p,int a)
{
	int dem=2;
	sinhvien sv;
	p=l.pHead89;
	
	while (p!=NULL)
	{ if (dem==a) 
	  {
	  	cout<<"Nhap du lieu sinh vien duoc them:\n";
	  	nhapt(sv);
	  	Node*r=GetNODE89(sv);
	  	r->pNext89=p->pNext89;
	  	p->pNext89=r;
	  	return ;
	  }
	  p=p->pNext89;
	  dem++;
	}
	if (dem<=a) cout<<"Khong the them\n";
}
int xoadauds89(List &l)
{
	if (l.pHead89 == NULL)
		return 0;
	Node* p=l.pHead89;  
	l.pHead89 = p->pNext89;
	if (l.pHead89 == NULL)	
		l.pTail89=NULL; 
	delete p;
	return 1;
}

void xoagiua89(List&l,Node*p,int a)
{
	p=l.pHead89;
	int dem=2;
	if (a==1)
	{
		Node*r=p;
		p=p->pNext89;
	}
	else
	{
	while (p!=NULL)
	{
		if (dem==a)
		{
			Node*r=p->pNext89;
			p->pNext89=r->pNext89;
		    delete p;
		}
		dem++;
		p=p->pNext89;
	}
	}
}
void xoacuoids89(List &l)
{
	NODE *p;
	for(NODE *k = l.pHead89; k != NULL; k = k ->pNext89)
	{
		if(k == l.pTail89)
		{
			l.pTail89 = p;
			l.pTail89 ->pNext89 = NULL;
			delete k;
			return;
		}
		p = k;
	}
}
void timkiem89(List&l,Node*p)
{
	p=l.pHead89;
	int tim;
	cout<<"nhap stt ban can tim:";
	cin>>tim;
	while (p!=NULL)
	{
		if (sosanh(tim,p->data89.stt89)==1)
		cout<<"Ten sinh vien ban can tim la: "<<p->data89.ten89<<endl;
		p=p->pNext89;
	}
}
void hoanvi89(int &a,int &b)                // ham hoan vi


 {
     int t=a; 
     a=b; 
     b=t; 
  }
void sapxeptang89(List l)          // ham sap xep tang 

{ 

 Node *i,*j; 

 for(i=l.pHead89;i!=l.pTail89;i=i->pNext89) 

         for(j=i->pNext89;j!=NULL;j=j->pNext89)

   if(i->data89.stt89>j->data89.stt89) 

    hoanvi89(j->data89.stt89,i->data89.stt89); 

}
void dauvao89(LIST &l,int n)
{
	sinhvien sv;
	Init89(l); 
	for(int i = 1; i <= n; i++)
	{
		themcuoids89(l);
	}
}
void daura89(LIST &l)
{
	for(NODE *p = l.pHead89; p != NULL; p = p ->pNext89)
	{
		cout<<p->data89.ten89<<"\t"<<p->data89.stt89<<endl;
	}
}
int main(int argc, char *argv[])
{
	LIST l;
	Node *p;
	int n;
	cout<<"Ban muon nhap thong tin bao nhieu sv: ";
	cin>>n;
	dauvao89(l,n);
	cout<<"Danh sach ban da nhap la:\n";
	daura89(l);
	int x;  
	cout<<"Them vao dau ds 1 sv: \n";   
	themdauds89(l);
	daura89(l);
	int vt,gt;
	cout<<"Nhap vi tri ban muon them 1 sv phia truoc= ";
	cin>>vt;
	themgiua89(l,p,vt);
	daura89(l);
	int y;
	cout<<"Them vao cuoi ds 1 phan tu= \n";  
	themcuoids89(l);
	daura89(l);
	cout<<"Xoa phan tu dau danh sach:\n";
	xoadauds89(l);
	daura89(l);
	int r;
	cout<<"Chon vi tri can xoa o giua ds: ";
	cin>>r;
	cout<<"Xoa phan tu o giua danh sach:\n";
	xoagiua89(l,p,r);
	daura89(l);
	cout<<"Xoa phan tu o cuoi danh sach\n";
	xoacuoids89(l);
	daura89(l);
	cout<<"Sap xep danh sach sv tang dan:\n";
	sapxeptang89(l);
	daura89(l);
	timkiem89(l,p);
	return 0;
}