#include<iostream.h>  

#include<conio.h>  

#include<process.h>

struct sn  

{  

int Item;  

sn* next; //con tro toi phan tu tiep theo  

};

struct ds  

{  

bool sort; //danh sach da xap xep hay chua  

sn* infor; //phan tu dau tien cua danh sach  

int count; //so phan tu cua mang  

};

int Menu(bool sort);  

void nhap(ds* pds);  

void hienthi(ds* pds);  

void boxung(ds* pds,int X,int k);  

void xoa(ds* pds,int k);  

void xoasoam(ds* pds);  

void sapxep(ds* pds);  

int boxungsort(ds* pds,int X);  

void infor(ds* pds);

void main()  

{  

ds* pds= new ds; //con tro toi danh sach  

pds->infor= new sn; //cap phat vung nho cho phan tu dau tien cua mang  

pds->count= 0; //khoi tao so phan tu bang 0  

pds->sort= false;  

int X, k;

clrscr();  

nhap(pds);  

clrscr();  

cout<<"Danh sach da nhap: "<<endl;  

hienthi(pds);  

cout<<"

Nhan mot phim bat ki de tiep tuc...";  

getch();  

while(1)  

{  

switch(Menu(pds->sort))  

{  

clrscr();  

cout<<"

Danh sach (truoc): ("<<pds->count<<" phan tu):

";  

hienthi(pds);  

cout<<endl<<endl;  

case 0:  

exit(0);  

case 1:  

cout<<endl;  

nhap(pds);  

clrscr();  

break;  

case 2:  

clrscr();  

cout<<endl<<endl;  

break;  

case 3:  

clrscr();  

cout<<"Danh sach truoc khi sap xep: "<<endl;  

hienthi(pds);  

sapxep(pds);  

pds->sort= true;  

cout<<"

Ket qua cua qua trinh sap xep:";  

break;  

case 4:  

clrscr();  

cout<<" Thao tac xoa mot phan tu: "<<endl<<endl;  

cout<<"Danh sach truoc khi xoa bo: "<<endl;  

hienthi(pds);  

cout<<"

Vao vi tri phan tu muon xoa: "; cin>>k;  

xoa(pds,k);  

cout<<"

Ket qua sau khi xoa phan tu o vi tri "<<k<<":

";  

break;  

case 5:  

clrscr();  

cout<<"Thao tac xoa cac so am: "<<endl<<endl;  

cout<<"Danh sach truoc khi xoa: "<<endl;  

hienthi(pds);  

xoasoam(pds);  

cout<<"

Ket qua sau qua trinh xoa cac phan tu am:

";  

break;  

case 6:  

clrscr();  

cout<<"Thao tac bo xung mot phan tu va mot vi tri: "<<endl<<endl;  

cout<<"Danh sach hien thoi: "<<endl;  

hienthi(pds);  

cout<<"

Bo xung X vao vi tri k: [X, k]= ";  

cin>>X>>k;  

boxung(pds,X,k);  

cout<<"

Danh sach sau khi bo xung "<<X<<" vao vi tri "<<k<<": "<<endl;  

break;  

case 7:  

clrscr();  

cout<<"Danh sach truoc: "<<endl;  

hienthi(pds);  

cout<<"

Danh sach sau khi bo xung "<<X<<":"<<endl;  

boxungsort(pds,X);  

break;  

case 8:  

clrscr();  

cout<<"Thong tin sanh sach:"<<endl<<endl;  

infor(pds);  

}

hienthi(pds);  

cout<<"

Nham mot phim bat ki de tiep tuc..."<<endl;  

getch();  

}  

}

void nhap(ds* pds)  

{  

cout<<"Nhap vao so phan tu du tinh se nhap: ";  

int n;  

int i= 1;  

cin>>n;

cout<<"

Nhap danh sach: "<<endl;  

sn* tg= pds->infor; //tao con tro toi thong tin cua phan tu va tro vao phan tu dau tien cua danh sach  

while(i<= n)  

{  

cout<<"

Phan tu thu "<<i<<": ";  

cin>>tg->Item;  

if(tg->Item!= -1)  

{  

pds->count++; //tang so phan tu cua ds len 1  

tg->next= new sn; //cap phat vung nho cho phan tu tiep theo  

tg= tg->next; //tg tro toi phan tu tiep theo trong ds  

tg->next= NULL;  

i++;  

}  

else //truong hop nhap vao -1  

{  

//tg->next= NULL;//no la diem ket thuc, do do ko chua phan tu nao sau do nua  

break; //thoat vong while  

}  

}  

}

void hienthi(ds* pds)  

{  

sn* tg= pds->infor; //tg tro toi phan tu dau tien trong danh sach  

cout<<"(gom "<<pds->count<<" phan tu)."<<endl;  

while(tg->next!= NULL)//phan tu chot mang co gia tri next=NULL  

{  

cout<<tg->Item<<" ";  

tg= tg->next;  

}  

}

void boxung(ds* pds,int X,int k)  

{  

sn* tg= pds->infor;  

sn* p= new sn;  

p->Item= X;

if(k== 1)  

{  

p->next= pds->infor;  

pds->infor= p;  

pds->count++;  

}  

else  

if(k>pds->count+1) cout<<"Vi tri nay nam ngoai mang, danh sach dang co "<<pds->count<<" phan tu."<<endl;  

else  

{  

int i= 1;  

while(tg->next!= NULL && i<k-1)  

{  

tg= tg->next;  

i++;  

}  

p->next= tg->next;  

tg->next= p;  

pds->count++;  

}  

}  

void xoa(ds* pds,int k)  

{  

sn* tg= pds->infor;

if(k== 1)  

{  

pds->infor= tg->next;  

delete(tg);  

pds->count--;  

}  

else  

if(k<1 || k> pds->count) cout<<"Vi tri nay nam ngoai mang, danh sach dang co "<<pds->count<<" phan tu."<<endl;  

else  

{  

int i= 1;  

while(tg->next!= NULL && i<k-1)  

{  

tg= tg->next;  

i++;  

}  

tg->next= tg->next->next;  

pds->count--;  

///delete(tg);  

}  

}

void xoasoam(ds* pds)  

{  

sn* tg= pds->infor;  

sn* tgnext= tg->next;

while(tg->Item< 0 && tg->next!= NULL) //xoa lien tiep cac phan tu am o dau danh sach  

{  

cout<<"Lap 1"<<endl;  

pds->infor= tg->next;  

tg= tg->next;  

pds->count--;  

}

///toi day, tg tro toi phan tu duong dau tien trong day

while(tg->next!= NULL)  

{  

tgnext= tg->next;  

//cout<<"Lap 2"<<endl;  

while(tgnext->Item< 0 && tgnext->next!= NULL) {tgnext= tgnext->next; pds->count--; } //tim so duong tiep theo

tg->next= tgnext;  

tg= tg->next; //tg tro vao phan tu duong tiep theo  

}  

}

void sapxep(ds* pds) ///sap xep tang dan bang phuong phap select sort;  

{  

sn* tg= pds->infor; //phan tu hien tai  

sn* tg_chay; //tim kiem nho nhat  

sn* min;  

while(tg->next!= NULL)  

{  

tg_chay= tg;  

min= tg_chay;  

while(tg_chay->next!= NULL)  

{  

if(tg_chay->Item< min->Item) min= tg_chay;  

tg_chay= tg_chay->next;  

}  

//////doi cho  

int trung_gian= tg->Item;  

tg->Item= min->Item;  

min->Item= trung_gian;  

tg= tg->next;  

}  

}

int boxungsort(ds* pds,int X) ///sap xep tang dan  

{  

sn* tg= pds->infor;  

sn* pre_tg= NULL; //phan tu truoc tg  

sn* p= new sn; //phan tu moi

p->Item= X;

if(tg->Item> X)  

{  

p->next= tg;  

pds->infor= p;  

pds->count++;  

return 0; //bo xung thanh cong  

}  

else  

{  

pre_tg= tg;  

tg->next;  

}  

while(tg->next!= NULL && tg->Item<X)  

{  

pre_tg= tg;  

tg= tg->next;  

}  

if(tg->next== NULL) return 0;  

else  

{  

pre_tg->next= p;  

p->next= tg;  

}  

}

void infor(ds* pds)  

{  

int am= 0;  

int duong= 0;  

sn* tg= pds->infor;

while(tg->next!= NULL)  

if(tg->Item<0) am++;  

else duong++;  

cout<<"

So phan tu cua danh sach: "<<pds->count<<endl;  

cout<<"So gia phan tu am: "<<am<<endl;  

cout<<"So gia tri duong: "<<duong<<endl;  

}

int Menu(bool sort)  

{  

lap:  

clrscr();  

cout<<endl<<endl;  

textcolor(2);  

cout<<"Lua chon cac thao tac:"<<endl<<endl;  

cout<<" 1. Nhap hoac nhap lai danh sach hoan toan moi."<<endl;  

cout<<" 2. Hien thi."<<endl;  

cout<<" 3. Sap xep."<<endl;  

cout<<" 4. Xoa mot phan tu."<<endl;  

cout<<" 5. Xoa cac so am."<<endl;  

cout<<" 6. Bo xung."<<endl;  

cout<<" 7. Thong tin mang hien tai."<<endl;  

cout<<" 8. Thoat."<<endl;  

textcolor(0);  

char ch= getch();  

if(ch>='0'&&ch<='8')  

switch(ch)  

{  

case '6':  

if(sort== true)  

{  

cout<<"

Mang da duoc sap xep!"<<endl;  

cout<<"Nhan 'Y' de chen vao mang co sap xep, phim bat ki de chen binh thuong.";  

char ch= getch();  

if(ch=='Y' || ch=='y')  

{  

clrscr();  

return 7;  

}  

}  

else return 6;  

break;  

case '7':  

return 8;  

default:  

return ((int)ch-48); ///ki tu so '1' co ma ASCII la 31  

}  

else goto lap;  

return 0;  

}