• Đăng Nhập
heo_kimcuong
 

Bài tập về danh sách liên kết đơn

01/09/2010 22:34  |  109 lượt xem

9. BT DSLK ĐƠN:
#include<conio.h>
#include<iostream.h>
struct Node{
                             int Info;
                             Node *Next;
                 };
//viet ham tao 1 node P
Node *TaoNode(int X)
{
          Node *P;
          P=new Node;
          P->Info=X;
          P->Next=NULL;
          return P;
}
//viet ham chen 1 node vao dau danh sach
void ChenNodeDau(Node *&first,Node *P)
{
          if(first==NULL)        first=P;
          else
          {
                   P->Next=first;
                   first=P;
          }
}
//viet ham tao 1 dslk theo kieu chen dau
void TaoDSLK(Node *&first)
{
          Node *P;
          first=NULL;
          int n,X;
          cout<<"Nhap n:";     cin>>n;
          for(int i=1;i<=n;i++)
          {
                   cout<<"nSo "<<i<<":";     cin>>X;
                   P=TaoNode(X);
                   ChenNodeDau(first,P);
          }
}
//viet ham xuat dslk
void XuatDSLK(Node *first)
{
          Node *P=first;
          while(P!=NULL)
          {
                   if(P==first)             cout<<P->Info;
                   else              cout<<"->"<<P->Info;
                   P=P->Next;
          }
}
//viet ham chen 1 node P vao cuoi dslk
void ChenNodeCuoi(Node *&first,Node *P)
{
          if(first==NULL)        first=P;
          else
          {
                   Node *Q=first;
                   while(Q->Next!=NULL)        Q=Q->Next;
                   Q->Next=P;
          }
}
//viet ham tim node Q trong dslk khi nhap vao vi tri k bat ky
Node *TimQ(Node *first,int k)
{
          Node *Q=first;
          int i=1;
          while(i<k&&Q!=NULL)
          {
                   Q=Q->Next;            i++;
          }
          if(k<=0)       return NULL;
          else              return Q;
}
//viet ham chen 1 node P vao truoc node Q trong dslk
void ChenPTruocQ(Node *&first,Node *P,Node *Q)
{
          if(Q==NULL)            cout<<"khong chen";
          else
                   if(Q==first)             ChenNodeDau(first,P);
                   else
                   {
                             Node *R=first;
                             while(R->Next!=Q)             R=R->Next;
                             R->Next=P;           
                             P->Next=Q;
                   }
}
//xuat ra mh cac gia tri le trong dslk
void XuatGiaTriLe(Node *first)
{
          Node *P=first;
          while(P!=NULL)
          {
                   if(P->Info%2!=0)     cout<<P->Info<<"t";
                   P=P->Next;
          }
}
//kiem tra ds co chua so chan khong
int KTChan(Node *first)
{
          Node *P=first;
          while(P!=NULL)
          {
                   if(P->Info%2==0)    return 1;
                   else              P=P->Next;
          }
          return 0;
}
//dem trong dslk co bao nhieu gia tri chan
int DemGiaTriChan(Node *first)
{
          Node *P=first;
          int Dem=0;
          while(P!=NULL)
          {
                   if(P->Info%2==0)             Dem++;
                   P=P->Next;
          }
          return Dem;
}
//tinh tong cac gia tri chia het cho 2 va 5 trong dslk
int TongChiaHetCho2Va5(Node *first)
{
          Node *P=first;
          int S=0;
          while(P!=NULL)
          {
                   if(P->Info%10==0)            S=S+P->Info;
                   P=P->Next;
          }
          return S;
}
//tinh tbc cac so nguyen to trong dslk
int KiemTraSoNguyenTo(int X)
{
          int i;
          if(X==1)       return 0;
          else
          {
                   for(i=2;i<=X-1;i++)
                             if(X%i==0)             return 0;
          }
          return 1;
}
float TinhTBC1(Node *first)
{
          int S=0,D=0;
          Node *P=first;
          while(P!=NULL)
          {
                   if(KiemTraSoNguyenTo(P->Info)==1)
                   {
                             S=S+P->Info;
                             D++;
                   }
                   P=P->Next;
          }
          return 1.0*S/D;
}
//tinh TBC cac so chan trong ds
float TinhTBC2(Node *first)
{
          int S=0,D=0;
          Node *P=first;
          while(P!=NULL)
          {
                   if(P->Info%2==0)
                   {
                             D++;
                             S=S+P->Info;
                   }
                   P=P->Next;
          }
          return 1.0*S/D;
}
//in ra gia tri cuoi cung
void InNodeCuoi(Node *first)
{
          Node *P=first;
          while(P->Next!=NULL)                  P=P->Next;
          cout<<P->Info;
}
//kiem tra node ke cuoi cua dslk la chan hay le
int KiemTraNodeKeCuoi(Node *first)
{
          Node *P=first;
          while(P->Next!=NULL)                  P=P->Next;
          Node *Q=first;
          while(Q->Next!=P)             Q=Q->Next;
          if(Q->Info%2==0)             return 0;
          else              return 1;
}
//kiem tra node cuoi chan hay le
int KTNodeCuoi(Node *first)
{
          Node *P=first;
          while(P!=NULL)
          {
                   P=P->Next;
                   if(P->Info%2==0)    return 0;
                   else              return 1;
          }
}
//dem xem ds co bao nhieu node
int Dem(Node *first)
{
          int Dem=0;
          Node *P=first;
          while(P!=NULL)
          {
                   Dem++;
                   P=P->Next;
          }
          return Dem;
}
//tim g/t X co trong dslk hay ko, neu co thi tra ve node do, neu ko co thi tra ve NULL
Node *TimX(Node *first,int X)
{
          Node *Q=first;
          while(Q!=NULL)
          {
                   if(Q->Info==X)        return Q;
                   Q=Q->Next;
         }
          return NULL;
}
//dem xem trong ds co bao nhieu gia tri X
int DemX(Node *first,int X)
{
          Node *P=first;                   int D=0;
          while(P!=NULL)
          {
                   if(P->Info==X)        D++;
                   P=P->Next;
          }
          return D;
}
//xuat ra mh noi dung cua node thu k trong ds
void XuatK(Node *first,int K)
{
          int d=1;
          Node *Q=first;
          if(K==1)       cout<<first->Info;
          else
                   do{
                             d++;
                             Q=Q->Next;
                        }while(d<K&&Q!=NULL);
          if(Q==NULL)            cout<<"nko co node thu k trong ds";
          else              cout<<Q->Info;
}
//tim tong lon nhat cua 2 pt lien tiep trong ds
int Max1(Node *first)
{
          Node *P=first,*Q;
          int S,Max=-32768;
          while(P->Next!=NULL)
          {
                   Q=P->Next;
                   S=P->Info+Q->Info;
                   if(Max<S)               Max=S;
                   P=P->Next;
          }
          return Max;
}
//tim tong cua 2 pt lon nhat trong ds
int Max2(Node *first)
{
          Node *P=first,*Q;
          int S,Max=-32768;
          while(P->Next!=NULL)
          {
                   Q=P->Next;
                   while(Q!=NULL)
                   {
                             S=P->Info+Q->Info;
                             if(Max<S)               Max=S;
                             Q=Q->Next;
                   }
                   P=P->Next;
          }
          return Max;
}
//xoa node dau trong dslk
void XoaDau(Node *&first)
{
          if(first!=NULL)
          {
                   Node *P=first;
                   first=P->Next;
                   delete(P);
          }
          else              cout<<"nds rong ko xoa";
}
//xoa node cuoi trong dslk
void XoaCuoi(Node *first)
{
          if(first!=NULL)
          {
                   if(first->Next==NULL)        XoaDau(first);
                   else
                   {
                             Node *P=first;
                             while(P->Next!=NULL)        P=P->Next;
                             Node *Q=first;
                             while(Q->Next!=P)             Q=Q->Next;
                             Q->Next=NULL;
                             delete(P);
                   }
          }
          else              cout<<"nds rong, ko xoa";
}
//xoa 1 node Q cho truoc trong dslk
void XoaNodeQ(Node *&first,Node *Q)
{
          if(first!=NULL)
          {
                   if(Q==NULL)            cout<<"ko xoa";
                   else
                   {
                             Node *R=first;
                             while(R->Next!=Q)             R=R->Next;
                             R->Next=Q->Next;
                             delete(Q);
                   }
          }
}
//viet ham xoa khoi dslk cac phan tu la so nguyen le
void XoaLe(Node *&first)
{
          Node *Q=first;
          while(Q!=NULL)
                   if(Q->Info%2!=0)
                   {
                             Node *P;
                             P=Q->Next;
                             XoaNodeQ(first,Q);
                             Q=P;
                   }
                   else              Q=Q->Next;
}
//dao 2 node dau cho nhau
void Dao1(Node *&first)
{
          Node *P,*Q,*R;
          P=first;
          Q=P->Next;
          R=Q->Next;
          P->Next=R;
          Q->Next=P;
          first=Q;
          XuatDSLK(first);
}
//dao 2 node cuoi cho nhau
void Dao2(Node *&first)
{
          Node *P,*Q,*R;
          P=first;
          while(P->Next!=NULL)        P=P->Next;
          Q=first;
          while(Q->Next!=P)             Q=Q->Next;
          R=first;
          while(R->Next!=Q)             R=R->Next;
          P->Next=Q;
          R->Next=P;
          Q->Next=NULL;
          XuatDSLK(first);
}
//dao node dau va cuoi cho nhau
void Dao3(Node *&first)
{
          Node *P,*Q,*R,*S;
          P=first;
          Q=P->Next;
          S=first;
          while(S->Next!=NULL)        S=S->Next;
          R=first;
          while(R->Next!=S)             R=R->Next;
          S->Next=Q;
          R->Next=P;
          first=S;
          P->Next=NULL;
          XuatDSLK(first);
}
//kiem tra ds co tang dan hay khong
int KTTang(Node *first)
{
          Node *P=first,*Q;
          while(P->Next!=NULL)
          {
                   Q=P->Next;
                   if(P->Info>Q->Info)           return 0;
                   P=P->Next;
          }
          return 1;
}
//viet ham sap xep dslk
void SapXep(Node *first)
{
          Node *P=first,*Q;
          while(P->Next!=NULL)
          {
                   Q=P->Next;
                   while(Q!=NULL)
                   {
                             if(P->Info>Q->Info)
                             {
                                       int t=P->Info;
                                       P->Info=Q->Info;
                                       Q->Info=t;
                             }
                             Q=Q->Next;
                   }
                   P=P->Next;
          }
}
//viet ham dao nguoc dslk
void DaoNguoc(Node *&first)
{
          Node *P=first,*first1;
          first1=NULL;
          while(P!=NULL)
          {
                   first=first->Next;
                   P->Next=NULL;
                   ChenNodeDau(first1,P);
                   P=first;
          }
          first=first1;
}
void main()
{
          clrscr();
          int X1,K,X2,Y,L;
          Node *first,*P1,*P2,*Q;
          TaoDSLK(first); XuatDSLK(first);
          cout<<"nviet ham chen 1 node P vao cuoi dslk";
          cout<<"nnhap gia tri cua nut can chen:"; cin>>X1;
          P1=TaoNode(X1);
          ChenNodeCuoi(first,P1); XuatDSLK(first);
          cout<<"nviet ham chen 1 node P truoc node Q";
          cout<<"nnhap vi tri can chen:"; cin>>K;
          Q=TimQ(first,K);
          cout<<"nnhap gia tri cua nut can chen:"; cin>>X2;
          P2=TaoNode(X2);
          ChenPTruocQ(first,P2,Q); XuatDSLK(first);
          cout<<"nxuat cac gia tri le trong mang ra mh:";
          XuatGiaTriLe(first);
          cout<<"nkiem tra ds co chua so chan khong";
          if(KTChan(first)==1)          cout<<"nds co chua so chan";
          else              cout<<"nds ko chua so chan";
          cout<<"nso gia tri chan trong dslk la:"<<DemGiaTriChan(first);
          cout<<"ntong pt chia het cho 2 va 5 ="<<TongChiaHetCho2Va5(first);
          cout<<"nTBC cac so nguyen to trong dslk="<<TinhTBC1(first);
          cout<<"nTBC cac so chan trong dslk="<<TinhTBC2(first);
          cout<<"nin ra gia tri cuoi cung:";
          InNodeCuoi(first);
          cout<<"nkiem tra node ke cuoi cua dslk la chan hay le:";
          if(KiemTraNodeKeCuoi(first)==1)             cout<<"nnode ke cuoi la so le";
          else              cout<<"nnode ke cuoi la so chan";
          cout<<"nkiem tra node cuoi cua dslk la chan hay le:";
          if(KTNodeCuoi(first)==1)              cout<<"nnode cuoi la so le";
          else              cout<<"nnode cuoi la so chan";
          cout<<"nso node co trong ds la:"<<Dem(first);
          cout<<"ntim xem g/t X co trong dslk ko";
          cout<<"nnhap gia can tim:"; cin>>Y;
          cout<<TimX(first,Y);
          cout<<"ndem xem trong dslk co bao nhieu g/t X:"<<DemX(first,Y);
          cout<<"nxuat ra mh noi dung cua node thu K trong ds la:";
          cout<<"nnhap vi tri muon xem:"; cin>>L;
          XuatK(first,K);
          cout<<"ntong lon nhat cua 2 pt lien tiep trong ds:"<<Max1(first);
          cout<<"ntong cua 2 pt lon nhat trong ds:"<<Max2(first);
          cout<<"nxoa node dau ds:";
          XoaDau(first); XuatDSLK(first);
          cout<<"nxoa node cuoi ds:";
          XoaCuoi(first); XuatDSLK(first);
          cout<<"nxoa 1 node Q cho truoc trong dslk";
          XoaNodeQ(first,Q); XuatDSLK(first);
          cout<<"nviet ham xoa khoi dslk cac phan tu la so nguyen le";
          XoaLe(first); XuatDSLK(first);
          cout<<"ndao 2 node dau cho nhau:";
          Dao1(first);
          cout<<"ndao 2 node cuoi cho nhau:";
          Dao2(first);
          cout<<"ndao node dau va cuoi cho nhau:";
          Dao3(first);
          if(KTTang(first)==1)           cout<<"nds tang dan";
          else              cout<<"nds ko tang dan";
          cout<<"nsap xep dslk";
          SapXep(first); XuatDSLK(first);
          cout<<"ndao nguoc dslk";
          DaoNguoc(first); XuatDSLK(first);
          getch();
}
10. BT DSLK ĐƠN NỐI VÒNG:
#include<conio.h>
#include<iostream.h>
struct Node{
                            int Info;
                            Node *Next;
                };
//tao 1 node moi
Node *TaoNode(int X)
{
          Node *P;
          P=new Node;
          P->Info=X;
          P->Next=P;
          return P;
}
//chen 1 node vao dau dslk
void ChenNodeDau(Node *&first,Node *P)
{
          if(first!=NULL)
          {
                   Node *R=first;
                   while(R->Next!=first)         R=R->Next;
                   R->Next=P;
                   P->Next=first;
          }
          first=P;
}
//tao dslk
void TaoDSLK(Node *&first)
{
          Node *P;
          first=NULL;
          int n,X;
          cout<<"Nhap n:";              cin>>n;
          for(int i=1;i<=n;i++)
          {
                   cout<<"nSo "<<i<<":";              cin>>X;
                   P=TaoNode(X);
                   ChenNodeDau(first,P);
          }
}
//xuat dslk
void XuatDSLK(Node *first)
{
          Node *P=first;
          do{
                   cout<<P->Info<<"t";
                   P=P->Next;
              }while(P!=first);
}
//chen 1 node vao cuoi dslk
void ChenNodeCuoi(Node *&first,Node *P)
{
          if(first==NULL)        first=P;
          else
          {
                   Node *R=first;
                   while(R->Next!=first)         R=R->Next;
                   R->Next=P;
                   P->Next=first;
          }
}
//tim node Q co trong dslk hay ko
Node *TimQ(Node *first,int k)
{
          Node *Q=first;
          int d=1;
          if(k==1)                 return first;
          else
          {
                   do{
                             d++;            Q=Q->Next;
                       }while(d<k&&Q!=first);
                   if(Q==first)             return NULL;
                   else                      return Q;
          }
}
//viet ham chen P truoc Q
void ChenPTruocQ(Node *&first,Node *P,Node *Q)
{
          if(Q==NULL)            cout<<"ko chen";
          else
                   if(Q==first)             ChenNodeDau(first,P);
                   else
                   {
                             Node *R=first;
                             while(R->Next!=Q)             R=R->Next;
                             R->Next=P;
                             P->Next=Q;
                   }
}
//xoa node dau
void XoaDau(Node *&first)
{
          if(first->Next!=first)
          {
                   Node *R=first;
                   while(R->Next!=first)         R=R->Next;
                   R->Next=first->Next;
                   delete(first);
                   first=R->Next;
          }
          else
          {
                   delete(first);
                   first=NULL;
          }
}
//xoa node cuoi
void XoaCuoi(Node *first)
{
          if(first->Next!=first)
          {
                   Node *P=first;
                   while(P->Next->Next!=first)          P=P->Next;
                   delete(P->Next);
                   P->Next=first;
          }
          else
          {
                   delete(first);
                   first=NULL;
          }
}
//xoa node Q
void XoaNodeQ(Node *&first,Node *Q)
{
          if(first!=NULL)
          {
                   if(Q==first)             XoaDau(first);
                   else
                   {
                             Node *R=first;
                             while(R->Next!=Q)             R=R->Next;
                             R->Next=Q->Next;
                             delete(Q);
                   }
          }
}
//tim gia tri x trong dslk
Node *TimX(Node *first,int X)
{
          Node *Q=first;
          do{
                   if(Q->Info==X)                  return Q;
                   Q=Q->Next;
              }while(Q!=first);
          return NULL;
}
//sap xep dslk tang dan
void SapXep(Node *first)
{
          Node *P=first,*Q;
          while(P->Next!=first)
          {
                   Q=P->Next;
                   while(Q!=first)
                   {
                             if(P->Info>Q->Info)
                             {
                                       int t=P->Info;
                                       P->Info=Q->Info;
                                       Q->Info=t;
                             }
                             Q=Q->Next;
                   }
                   P=P->Next;
          }
}
void main()
{
          clrscr();
          Node *first,*P1,*Q,*P2;
          int X1,K,X2,Y;
          TaoDSLK(first); XuatDSLK(first);
          cout<<"nviet ham chen 1 node P vao cuoi dslk";
          cout<<"nnhap gia tri cua nut can chen:"; cin>>X1;
          P1=TaoNode(X1);
          ChenNodeCuoi(first,P1); XuatDSLK(first);
          cout<<"nviet ham chen 1 node P truoc node Q";
          cout<<"nnhap vi tri can chen:"; cin>>K;
          Q=TimQ(first,K);
          cout<<"nnhap gia tri cua nut can chen:"; cin>>X2;
          P2=TaoNode(X2);
          ChenPTruocQ(first,P2,Q); XuatDSLK(first);
          cout<<"nxoa node dau ds:";
          XoaDau(first); XuatDSLK(first);
          cout<<"nxoa node cuoi ds:";
          XoaCuoi(first); XuatDSLK(first);
          cout<<"nxoa 1 node Q cho truoc trong dslk";
          XoaNodeQ(first,Q); XuatDSLK(first);
          cout<<"ntim xem g/t X co trong dslk ko";
          cout<<"nnhap gia can tim:"; cin>>Y;
          cout<<TimX(first,Y);
          cout<<"nsap xep dslk";
          SapXep(first); XuatDSLK(first);
          getch();
}

Công Nghệ & Xe

1 / 3

Bình luận  

Viết bình luận

Bài mới

1 / 3

Mời Kết Bạn

Gởi lời mời kết bạn đến

Gửi