Home dungnv » gdtctdlgt » mctdlgt » các hàm trong danh sách liên kết đơn

các hàm trong danh sách liên kết đơn

Saturday, January 24, 2015
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();
}
Chia sẻ bài viết ^^
Other post

All comments [ 0 ]


Your comments