#include<iostream.h>  

#include<conio.h>

struct sn  

{  

int Item;  

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

};

struct ds  

{  

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

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

int count; //so phan tu cua mang  

};

void nhap(ds* tro_ds);  

void hienthi(ds* tro_ds);  

void bosung(ds* tro_ds,int X,int k);  

void xoa(ds* tro_ds,int k);  

void xoasoam(ds* tro_ds);  

void sapxep(ds* tro_ds);  

int them_sort(ds* tro_ds,int X);  

void infor(ds* tro_ds);

void main()  

{  

ds* tro_ds= new ds; //bat dau tro  

tro_ds->infor= new sn;  

tro_ds->count= 0; //khoi tao danh sach  

tro_ds->sort=0;  

int X, k;

clrscr();  

nhap(tro_ds);  

clrscr();  

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

hienthi(tro_ds);  

//bo sung  

clrscr();  

cout<<"nhap gia tri bo sung va vi tri can bo sung";  

cin>>X>>k;  

bosung(tro_ds,X,k);  

cout<<"

danh sach moi:";  

hienthi(tro_ds);  

//xoa  

clrscr();

cout<<"

hap vi tri xoa :"; cin>>k;  

xoa(tro_ds,k);  

cout<<"

ket qua: ";  

hienthi(tro_ds);  

//xoa so am  

clrscr();

xoasoam(tro_ds);  

cout<<"sau khi xoa so am:

";  

hienthi(tro_ds);  

//sap xep tang

clrscr();

sapxep(tro_ds);  

tro_ds->sort=1;  

cout<<"

Ket qua sap xep:";  

hienthi(tro_ds);  

}

void nhap(ds* tro_ds)  

{  

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

int n;  

int i= 1;  

cin>>n;

cout<<"

Nhap danh sach: "<<endl;  

sn* tg= tro_ds->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)  

{  

tro_ds->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* tro_ds)  

{  

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

cout<<"(gom "<<tro_ds->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* tro_ds,int X,int k)  

{  

sn* tg= tro_ds->infor;  

sn* p= new sn;  

p->Item= X;

if(k== 1)  

{  

p->next= tro_ds->infor;  

tro_ds->infor= p;  

tro_ds->count++;  

}  

else  

if(k>tro_ds->count+1) cout<<"Vi tri nay nam ngoai mang, danh sach dang co "<<tro_ds->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;  

tro_ds->count++;  

}

}  

void xoa(ds* tro_ds,int k)  

{  

sn* tg= tro_ds->infor;

if(k== 1)  

{  

tro_ds->infor= tg->next;  

delete(tg);  

tro_ds->count--;  

}  

else  

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

else  

{  

int i= 1;  

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

{  

tg= tg->next;  

i++;  

}

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

tro_ds->count--;  

///delete(tg);  

}  

}

void xoasoam(ds* tro_ds)  

{  

sn* tg= tro_ds->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;  

tro_ds->infor= tg->next;  

tg= tg->next;  

tro_ds->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; tro_ds->count--; } //tim so duong tiep theo

tg->next= tgnext;  

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

}  

}

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

{  

sn* tg= tro_ds->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* tro_ds,int X) ///sap xep tang dan  

{  

sn* tg= tro_ds->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;  

tro_ds->infor= p;  

tro_ds->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;  

return 1;  

}  

}

void infor(ds* tro_ds)  

{  

int am= 0;  

int duong= 0;  

sn* tg= tro_ds->infor;

while(tg->next!= NULL)  

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

else duong++;

cout<<"

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

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

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

}