dungnvcác hàm trong danh sách liên kết đơn
1:17 PM |
các hàm trong danh sách liên kết đơn.
chú ý: chỗ khai báo int x; bôi vàng. do khai ở hàm phía trên nên không đưa vào 1 số hàm phía dưới tránh trùng nhau trong bài này. Nếu dùng hàm đơn lẻ mới sử dụng.
dowload file *.cpp
https://drive.google.com/file/d/0BydNUbu7zbP2T2FLOXIzM213UlE/view?usp=sharing
dowload file word
https://drive.google.com/file/d/0BydNUbu7zbP2WmxnLW03WFdlMHc/view?usp=sharing
#include <stdio.h>
#include <conio.h>
typedef struct node
{
int info;
node
*link;
};
// ham xem danh sach lien
ket.
void xem(node *f)
{
node
*p=f;
while(p!=NULL)
{
printf("%5d",p->info);
p=p->link;
}
}
//Nhap danh sach lien ket
don LIFO.
node *nhaplifo(node *f,int n)
{
node
*p;
for(int
i=0;i<n;i++)
{
p=new(node);
printf("\nNhap phan tu:
");
scanf("%d",&p->info);
p->link=f;
f=p;
}
return f;
}
//nhap danh sach lien ket
don FIFO.
node *nhapfifo(node *f,node *l,int n)
{
node
*p;
for(int
i=0;i<n;i++)
{
p=new(node);
printf("\nNhap phan tu:
");
scanf("%d",&p->info);
if(f==NULL)
{
f=p;
l=p;
}
else
{
l->link=p;
l=p;
}
}
return f;
}
//ham sap xep day theo thu
tu tang dan (khong giam).
void sapxeptang(node *f)
{
node
*p1=f,*p2;
while(p1->link!=NULL)
{
p2=p1->link;
while(p2!=NULL)
{
if(p1->info>p2->info)
{
int tg=p1->info;
p1->info=p2->info;
p2->info=tg;
}
p2=p2->link;
}
p1=p1->link;
}
}
//ham sap xep theo thu tu
giam gian(khong tang)
void sapxepgiam(node *f)
{
node
*p1=f,*p2;
while(p1->link!=NULL)
{
p2=p1->link;
while(p2!=NULL)
{
if(p1->info<p2->info)
{
int tg=p1->info;
p1->info=p2->info;
p2->info=tg;
}
p2=p2->link;
}
p1=p1->link;
}
}
//tim kiem so x co xuat
hien trong danh sach hay khong.
// khong thay thi tra ve
NULL.
// thay thi tra ve dia chi
dau tien chua x.
node *timkiem1(node *f,int x)
{
node
*p=f;
while(p!=NULL && p->info!=x) p=p->link;
return p;
}
//tim kiem so x co xuat
hien trong danh sach hay khong.
// khong thay thi tra ve 0.
// tim thay thi tra 1.
int timkiem2(node *f,int x)
{
node
*p=f;
while(p!=NULL && p->info!=x) p=p->link;
if (p!=NULL) return
1;
return 0;
}
//dem so phan tu cua dslk;
//ham tra ve kieu nguyen so
phan tu.
int demspt(node *f)
{
int d=0;
node
*p=f;
while(p!=NULL)
{
d++;
p=p->link;
}
return d;
}
//ddem so phan tu chan
trong ds lk.
//Ham tra ve so phan tu
chan.
int demchan(node *f)
{
int d=0;
node
*p=f;
while(p!=NULL)
{
if (p->info%2==0) d++;
p=p->link;
}
return d;
}
//ddem so phan tu le trong
ds lk.
//ham tra ve so phan tu le.
int demle(node *f)
{
int d=0;
node
*p=f;
while(p!=NULL)
{
if (p->info%2!=0) d++;
p=p->link;
}
return d;
}
//dem so phan tu lon hon x.
//ham tra ve so phan tu lon
hon x.
int dem(node *f,int x)
{
int d=0;
node
*p=f;
while(p!=NULL)
{
if(p->info>x) d++;
p=p->link;
}
return d;
}
// tong cac phan tu trong
dslk.
//ham tra ve tong cac phan
tu.
int sum(node *f)
{
int s=0;
node
*p=f;
while(p!=NULL)
{
s+=p->info;
p=p->link;
}
return s;
}
//tong cacs phan tu chan
trong dslk;
//ham tra ve tong cac phan
tu chan.
int tongchan(node *f)
{
int t=0;
node
*p=f;
while(p!=NULL)
{
if(p->info%2==0) t+=p->info;
p=p->link;
}
return t;
}
//tong cac phan tu le trong
dslk
//ham tra ve tong cac phan
tu le.
int tongle(node *f)
{
int t=0;
node
*p=f;
while(p!=NULL)
{
if(p->info%2!=0) t+=p->info;
p=p->link;
}
return t;
}
//tong cac phan tu lon hon
x trong dslk
//ham tra ve tong phan tu
lon hon x.
int tong(node *f,int x)
{
int t=0;
node
*p=f;
while(p!=NULL)
{
if(p->info>x) t+=p->info;
p=p->link;
}
return t;
}
//them 1 phan tu vao dau
dslk .
node *themdau(node *f)
{
node
*x;
x=new(node);
printf("\nNhap phan tu can them vao dau : ");
scanf("%d",&x->info);
x->link=f;
return x;
}
//them mot phan tu vao cuoi
dslk.
node *themcuoi(node *f)
{
node
*x;
x=new(node);
printf("\nNhap phan tu can them vao cuoi : ");
scanf("%d",&x->info);
x->link=NULL;
if (f==NULL) return
x;//neu danh sach rong thi x la phan tu dau tien.
node
*p=f;
while(p->link!=NULL) p=p->link;// du con tro p chay den cuoi danh sach
p->link=x;
return f;
}
//them mot phan tu vao vi
tri thu 2 cua dslk.
void them2(node *f)
{
if (f==NULL) return;//danh sach rong thi khong thuc hien.
node
*x;
x=new(node);
printf("\nNhap phan tu can them vao sau vi tri thu nhat :
");
scanf("%d",&x->info);
x->link=f->link;
f->link=x;
}
// them mot phan tu chen
vao vi tri thu k.
node *themk(node *f,int k)
{
node
*x,*p=f;
int d=0;
x=new(node);
printf("\nNhap gia tri phan tu can them: ");
scanf("%d",&x->info);
if(k==1)
{
x->link=f;
return x;
}
while(p!=NULL)
{
d++;
if (d==(k-1)) break;
p=p->link;
}
x->link=p->link;
p->link=x;
return f;
}
//them mot phan tu vao sao
cho khong lam thay doi sap xep tang dan cua day.
node *them(node *f)
{
node
*x,*p=f;
x=new(node);
printf("\nNhap phan tu can them vao : ");
scanf("%d",&x->info);
while((p->link!=NULL)&&(p->link->info
< x->info)) p=p->link;
if (p==f)
{
x->link=p;
return x;
}
x->link=p->link;
p->link=x;
return f;
}
//xoa mot phan tu dau tien.
node *xoadau(node *f)
{
if (f==NULL) return
f;// ds ronf khong xoa duoc.
node
*p=f;
f=p->link;
delete(p);
return f;
}
//xoa mot phan tu cuoi
cung.
node *xoacuoi(node *f)
{
if (f==NULL) return
f;// neu ds rong khong xoa duoc.
if (f->link==NULL)// neu
danh sach chi 1 phan tu
{
delete(f);
return NULL;
}
node
*p=f;
while(p->link->link!=NULL) p=p->link;
delete(p->link);
p->link=NULL;
return f;
}
// xoa phan tu thu k.
node *xoak(node *f)
{
node
*p=f,*q;
int d=1,k;
printf("\nNhap phan tu thu k can xoa: ");
scanf("%d",&k);
if (f==NULL&&k>0) return
f;// neu ds rong khong xoa duoc. va k>0
if (k==1)
{
delete(f);
return NULL;
}
while(p!=NULL)
{
q=p;
p=p->link;
d++;
if(d==k)
{
q->link=p->link;
delete(p);
return f;
}
}
printf("\nGia tri k khong hop le : ");
return f;
}
//xoa nhung phan tu co gia
tri co dinh.
node *xoa(node *f)
{
node
*p=f;
int x;
printf("\nNhap gia tri phan tu can loai bo khoi dslk: ");
scanf("%d",&x);
while (p->info==x&&p!=NULL)
{
f=xoadau(f);
p=f;
}
while(p->link!=NULL)
{
if(p->link->info==x)
{
node
*tg=p->link;
p->link=p->link->link;
delete(tg);
}
else
p=p->link;
}
return f;
}
// dao nguoc dslk.
node *Reverse(node *l)
{
node *p=l,*tg1,*tg2=NULL;
while (p!=NULL)
{
tg1=p;
p=p->link;
tg1->link=tg2;
tg2=tg1;
}
return tg1;
}
int main()
{
node
*f=NULL;
int n;
//nhap dslk lifo.
printf("\nNhap so phan tu cua dslk : ");
scanf("%d",&n);
f=nhaplifo(f,n);
// ket thuc .
/*
node *f=NULL,l=NULL;
int n;
//nhap dslk fifo.
printf("\nNhap so phan tu cua dslk : ");
scanf("%d",&n);
f=nhapfifo(f,l,n);
// ket thuc .
*/
// xem danh sach lien ket.
printf("\nDanh sach vua nhap : ");
xem(f);
//ket thuc.
// sap xep tang.
printf("\nDanh sach sau khi sap xep tang :
");
sapxeptang(f);
xem(f);
// ket thuc
// sap xep giam
printf("\nDanh sach sau khi sap xep giam :
");
sapxepgiam(f);
xem(f);
// ket thuc.
// tim kiem 1.
// khong thay thi tra ve NULL.
// thay thi tra ve dia chi dau tien chua x.
int x;
printf("\nNhap phan tu can tim kiem :
");
scanf("%d",&x);
if (timkiem1(f,x)!=NULL) printf("\nTim thay %d trong danh sach lien ket",x);
else printf("\nKhong
tim thay %d trong danh sach lien ket. ",x);
// ket thuc.
// tim kiem 2.
// khong thay thi tra ve 0.
// tim thay thi tra 1.
//int x;
printf("\nNhap phan tu can tim kiem :
");
scanf("%d",&x);
if (timkiem2(f,x)) printf("\nTim
thay %d trong danh sach lien ket",x);
else printf("\nKhong
tim thay %d trong danh sach lien ket. ",x);
// ket thuc.
// dem so phan tu trong ds
printf("\nSo phan tu trong danh sach : %d ",demspt(f));
// ket thuc.
// dem so phan tu chan trong ds
printf("\nSo phan tu chan trong danh sach : %d ",demchan(f));
// ket thuc.
// dem so phan tu le trong ds
printf("\nSo phan tu le trong danh sach : %d ",demle(f));
// ket thuc.
//dem so phan tu lon hon x.
//int x;
printf("\ndem so phan tu lon hon x.");
printf("\nNhap x =
");
scanf("%d",&x);
printf("\nSo phan tu lon hon %d trong ds la : %d
",x,dem(f,x));
//ket thuc.
// tong cac phan tu chan trong dslk.
printf("\nTong cac phan tu chan trong dslk la : %d
",tongchan(f));
//ket thuc.
// tong cac phan tu le trong dslk.
printf("\nTong cac phan tu le trong dslk la : %d
",tongle(f));
//ket thuc.
//tong cac phan tu lon hon x trong dslk.
//int x;
printf("\ntong cac phan tu lon hon x trong dslk.");
printf("\nNhap x =
");
scanf("%d",&x);
printf("\nTong cac phan tu lon hon %d trong dslk la : %d
",x,tong(f,x));
//ket thuc.
//them dau.
f=themdau(f);
printf("\nDanh sach sau khi them dau : ");
xem(f);
//ket thuc.
//them cuoi.
f=themcuoi(f);
printf("\nDanh sach sau khi them cuoi : ");
xem(f);
//ket thuc.
//them mot phan tu vao vi tri thu 2 cua dslk.
them2(f);
printf("\nDanh sach sau khi them vao phan tu thu 2 : ");
xem(f);
// ket thuc.
// them mot phan tu chen vao vi tri thu k.
int k;
printf("\nNhap vi tri can chen vao: ");
scanf("%d",&k);
f=themk(f,k);
printf("\nDanh sach sau khi them vi tri thu %d ",k);
xem(f);
// ket thuc.
//them mot phan tu vao sao cho khong lam thay doi sap xep
tang dan cua day.
printf("\nthem mot phan tu vao sao cho khong lam thay doi
sap xep tang dan cua day.");
sapxeptang(f);
printf("\nDanh sach sau khi sap xep tang : ");
xem(f);
f=them(f);
printf("\nDanh sach sau khi them ");
xem(f);
// ket thuc.
//xoa 1 phan tu dau dslk.
f=xoadau(f);
printf("\nDanh sach sau khi xoa dau la : ");
xem(f);
//ket thuc
//xoa 1 phan tu cuoi dslk;
f=xoacuoi(f);
printf("\nDanh sach sau khi xoa cuoi ");
xem(f);
//ket thuc.
// xoa phan tu thu k.
printf("\n xoa phan
tu thu k.");
f=xoak(f);
printf("\nDanh sach sau khi xoa ");
xem(f);
//ket thuc.
//xoa nhung phan tu co gia tri co dinh.
printf("\nxoa nhung phan tu co gia tri co dinh. ");
f=xoa(f);
printf("\nDanh sach sau khi xoa ");
xem(f);
//ket thuc.
//dao nguoc dslk
printf("\nDanh sach lien ket sau khi dao nguoc");
f=Reverse(f);
xem(f);
//ket thuc
getch();
}
Previous Article
.jpg)
