kiem tra cau truc du lieu.txt nguyenanhque
#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;
}
Bạn đang đọc truyện trên: Truyen247.Pro