Cấu trúc dữ liệu và Giải thuật

Lượt truy cập:

1/ Các thuật toán Tìm kiếm và Sắp xếp:

2/ Danh sách liên kết

3/ Cây nhị phân

 1/ Tìm kiếm và Sắp xếp:

//CAC THUAT TOAN TIM KIEM VA SAP XEP:

#include<stdio.h>

#include<conio.h>

#include<math.h>

#include<stdlib.h>

int nNumHV=0;

int nNumSS=0;

 

void nhap(int a[], int &n)

 {

   for(int i=0; i<n; i++)

      {

            printf("\n Nhap phan tu A[%d] = ",i);

            scanf("%d",&a[i]);

      }

 }

 

 

void xuat(int a[], int &n)

 {

   for(int i=0; i<n; i++)

   printf("%5d", a[i]);

 }

 

void swap(int &a, int &b)

 {

  int c=a;a=b; b=c;

 }

 

 

//A : CAC THUAT TOAN TIM KIEM:

//-1: TIM TUYEN TINH:

 

int TimTuyenTinh( int a[],int n, int x)

 {

   int i=0;

   while( (i<n) && (a[i]!=x) )

   i++;

   if(i==n) return 0 ; //Khong tim thay/

   else return 1;     //Tim thay/

 }

// Tot nhat: 1, Xau nhat : n, Trung binh (n+1)/2, Pt :O(N).

 

 

 

//-2 : TIM NHI PHAN (chi ap dung cho day so da xap xep) :

int TimNhiPhan (int a[], int n, int x)

 {

   int left=0, right=n-1, mid;

   do

     {

         mid=(left+right)/2;

         if( a[mid]==x) return 1; //Tim thay x/.

         else

                 {

                      if(a[mid]<x) left=mid+1;

                      else         right=mid-1;

                  }

      }

     while(left<=right)  ;

     return 0;

 }

//Tot nhat 1, xau nhat: log2(n), trung binh log2(n/2), phuc tap O(log2(n) ).

 

//-1: DOI CHO TRUC TIEP -Xep giam dan:

void interchangesort(int a[], int &n)

 {

    for(int i=0; i<n-1; i++)

      {

                 for(int j=i+1; j<n; j++)

                 if(a[i]>a[j])

                 swap(a[i], a[j]);

      }

 }

//Tot nhat: so lan ss: n(n-1)/2, so lan hoan vi 0;

//Xau nhat: so lan ss: n(n-1)/2, so lan hoan vi n(n-1)/2 .

 

 

//-2 : CHON TRUC TIEP -Xep giam dan :

void selectionsort(int a[], int n)

 {

   for( int i=0;i<n-1;i++)

      {

                 int min=i;

                 for(int j=i+1;j<n;j++)

                     {

                              if( a[j] < a[min] )

                              min=j;   //Luu vi tri phan tu hien tai nho nhat/.

                             swap( a[min], a[j] );

                     }

      }

 }

//Tot nhat :so lan ss: n(n-1)/2, so phep gan 0.

//Xau nhat :so lan ss: n(n-1)/2, so phep gan 3n(n-1)/2.

 

 

//-3: NOI BOT : Xep tang dan:

void bubblesort(int a[], int n)

 {

   for( int i=0; i<n; i++)

     {

       for(int j=n-1; j>i; j--)

       if(a[j]<a[j-1] )

       swap( a[j], a[j-1] ) ;

     }

 }

//Tot nhat: so lan ss: n(n-1)/2, so lan hoan vi 0.

//Xau nhat: so lan ss: n(n-1)/2, so lan hoan vi n(n-1)/2.

 

//-4 : SHAKER SORT -Xep tang dan:

void shakersort(int a[], int n)

 {

   int left=0, right=n-1, k=n-1,i,j;

    while(left<right)

            {

               for(j=right; j>left; j--)

               if(a[j]<a[j-1])

                        {

                           swap(a[j-1], a[j]);

                           k=j;

                        }

             left=k;

             for(j=left;j<right; j++)

             if( a[j] > a[j+1] )

                   {

                         swap(a[j], a[j+1] )        ;

                          k=j;

                   }

             right=k;

            }

 }

 

//5-CHEN TRUC TIEP :

void insertionsort(int a[], int n)

 {

   int pos, i;

   int x; //Luu gia tri a[i], tranh bi ghi de khi doi cho cac phan tu/.

   for( i=1; i<n;  i++)

     {

       x=a[i];

       pos=i-1;

       while( (pos >=0 ) && (a[pos]> x) )

                   {

                            a[pos+1]=a[pos];

                            pos--;

                   }

                a[pos+1]=x;

     }

 }

 

//6-CHEN NHI PHAN :

void BinInsertionSort(int a[], int n)

 {

  int l, r, m ,i;

  int x; //Luu gia tri a[i] /.

  for(  i=1; i<n; i++)

     {

       x=a[i];

       l=1;  r=i-1;

       while(i<=r)  //Tim vi tri chen x:

                   {

                              m=(l+r)/2;

                             if(x<a[m]  )  r=m-1;

                             else l=m+1;

                           }

       for( int j=i-1; j>=l; j--)

       a[j+1]=a[j];

       a[l]=x;

    }

 }

 

 //-7: SHELL SORT:

//Viet ham tinh mangH bang cong thuc h[i]=( h[i+1]*2) +1;

void createH (int n, int h[], int &k)

 {

    int i;

    k=int (log(n)/log(2) ) ;

    h[k]=1;

    for(i=k-1;i>=0;i--)

    h[i]=(h[i+1]*2+1) ;

    k++;

 }

 

 

 

void shellsort(int a[], int n, int h[], int k)

 {

   int step, i,j, x, len;

   createH(n,h,k);

   for(step=0; step<k; step++)

     {

        len=h[step];

        for(i=len; i<n; i++)

              {

                         x=a[i];

                         j=i-len;

                         while( (x<a[j] ) &&(j>=0) )

                              {

                                 a[j+len]=a[j];

                                 j=j-len;

 

                              }

                          a[j+len]=x;

              }

      }

 }

 

//-8: HEAP SORT:

 

void Hoanvi(int &x,int &y)

{

            int tam;

            tam=x;

            x=y;

            y=tam;

            nNumHV++;

}

 

//hieu chinh day a[l]-> a[r] thanh heap

void shift(int a[],int l,int r)

{

            int x,i,j;

            i=l;

            j=2*i+1;

            x=a[i];

            while(j<=r)

                  {

                         if(j<r)

                            {

                                     nNumSS++;

                                     if(a[j]<a[j+1]) //tim phan tu lon nhat a[j] va a[j+1]

                                                j++; //luu chi so cua phan tu nho nhat trong hai phan tu

                              }

                       

                       

                        if(a[j]<=x) return;

                        else

                             {

                                    a[i]=a[j];

                                    a[j]=x;

                                    i=j;

                                    j=2*i+1;

                                    x=a[i];

                                    nNumHV++;

                              }

                       

            }

}

 

//Dieu chinh day ban dau thanh Heap

void CreateHeap(int a[],int n)

{

             int l;

             l=n/2-1;

             while(l>=0)

             {

                         nNumSS++;

                        shift(a,l,n-1);

                        l=l-1;

             }

}

 

 

//thuat toan Heapsort

void HeapSort(int a[],int n)

{

            int r;

            CreateHeap(a,n);

            r=n-1;

            while(r>0)

            {

                        nNumSS+=2;

                        Hoanvi(a[0],a[r]);//a[0] la root

                        r--;//

                        if(r>0)

                                    shift(a,0,r);

            }

}

//Do phuc tap : 0(nlog2(n) )

 

//THUAT TOAN QUICK SORT:

void QuickSort(int a[], int left, int right)

 {         int        i, j, x;

            x = a[(left+right)/2];

            i = left; j = right;

            while(i < j)

                 {

                       while(a[i] < x) i++;

                       while(a[j] > x) j--;

                       if(i <= j)

                            {

                                       swap(a[i],a[j]);

                                      i++ ; j--;

                             }

                }

            if(left<j)

                        QuickSort(a, left, j);

            if(i<right)

                        QuickSort(a, i, right);

 }

 

//Tot nhat : do phuc tap nlog(n)

//xau nhat :n*n

//Trung binh : nlog(n)

 

void main()

{

  clrscr();

  int a[100], n, m, h[10], k;

  printf("\n Nhap n: ");

  scanf("%d", &n);

  nhap(a,n);

  printf("\n Mang vua nhap la :  \n ");

  xuat(a,n);

 // printf("\n Xap xep Shell Sort : \n")   ;

 // shellsort(a,n,h,k);

  printf("\n Sap xep qs :  \n");

  QuickSort(a,0,n-1);

  xuat(a,n);

  printf("\n Nhap phan tu can tim kiem :");

  scanf("%d", &m);

 int c= TimNhiPhan(a,n,m)  ;

 if(c==1) printf("\n Tim thay.");

 else printf("\n Tim khong thay. ");

 

  getch();

}

 2/ Danh sách liên kết:

//Bài tập về viết danh sách liên kết quản lý sinh viên:

#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>

typedef struct date
 {
   int day;
   int month;
   int year;
 }date;

typedef struct sinhvien
  {
    char ten[10];
    char ms[10];
    float dtb;
    struct date ngaysinh;
  }sv;

typedef struct tagnode
 {
   sinhvien info;
   struct tagnode *pnext;
 }node;

typedef struct
 {
   node *phead;
   node *ptail;

 }list;

node *createnode(sv x)
{
  node *p;
  p=new node;
  if(p==NULL)
    {
      printf("\n Khong du bo nho/");
      exit(1);
    }

  p->info=x; //gan du lieu cho node/
  p->pnext=NULL;
  return p;
 }

void createlist(list &l)
 {
   l.phead=NULL;
   l.ptail=NULL;
 }

void addhead(list &l, node *p)
 {
   if(l.phead==NULL)
    {
     l.phead=p;
     l.ptail=l.phead;
    }
   else
     {
       p->pnext=l.phead;
       l.phead=p;
     }
 }

void printlist(list l)
 {
   node *p;
   p=l.phead;
   while(p!=NULL)
    {
      printf("\n%s    %d/%d/%d     %s    %0.2f\n ", p->info.ten, p->info.ngaysinh.day, p->info.ngaysinh.month,
                             p->info.ngaysinh.year, p->info.ms, p->info.dtb);
      p=p->pnext;
    }
 }

node *searchnode(list &l)
 {
  char x[10];
  printf("\n Nhap ten sv can tim: " );
  gets(x);
  node *p;
  p=l.phead;
  while(p!=NULL && strcmp(p->info.ten, x)!=0)
  p=p->pnext;
  return p;
 }

void swap(sv &a, sv &b)
 {
  sv   c=a ;
  a=b;
  b=c;
 }
void swap1(float &a, float &b)
 {
  float c=a; a=b;b=c;
 }

void sortbyname(list &l)
 {
   node *a, *b, *min;
   a=l.phead;
   while(a!=l.ptail)
    {
      min=a;
      b=a->pnext;
      while(b!=NULL)
        {
          int kq=strcmp(b->info.ten, min->info.ten);
          if(kq<0)
          min=b;
          b=b->pnext;
        }
       swap1(a->info.dtb, min->info.dtb);
       a=a->pnext;
    }
 }

void sortbydiem(list &l)
 {
   node *a, *b, *min;
   min=a;
   a=l.phead;
   while(a!=NULL)
    {
      min=a;
      b=a->pnext;
      while(b!=NULL)
       {
         if(b->info.dtb < a->info.dtb)
         min=b;
         b=b->pnext;
       }
      swap1(min->info.dtb, a->info.dtb);
      a=a->pnext;
    }
 }

void removelist(list&l)
 {
   node *p;
   while(l.phead==NULL)
    {
      p=l.phead;
      l.phead=p->pnext;
      delete p;
    }
 }


void main()
 {
   node *p;
   list l;
   sv s;
   float diem;
   int d, m, y;
   createlist(l);
   do
    {
      printf("\n Nhap ten: ");
      fflush(stdin);
      gets(s.ten);
      if(strlen(s.ten)>0)
       {
         printf("\n Nhap ma so: ");
         gets(s.ms);
         printf("\n Nhap ngay thang nam sinh: dd/mm/yyyy ");
         scanf("%d %d %d", &d, &m, &y);

         s.ngaysinh.day=d;
         s.ngaysinh.month=m;
         s.ngaysinh.year=y;
         printf("\n Nhap diem trung binh: ");
         scanf("%f", &diem);
         s.dtb=diem;
         p=createnode(s);
         addhead(l, p);
       }
    }
   while(strlen(s.ten)>0);
   printf("\n DANH SACH VUA NHAP LA: \n");
  printlist(l);
  printf("\n SAP XEP THEO TEN:  \n\n");
  sortbyname(l);
  printlist(l);
 // printf("\n SAP XEP THEO DIEM: \n\n");
 // sortbydiem(l);
 // printlist(l);
  node *a=searchnode(l);
  if(p==NULL)
  printf("\n Khong tim thay ten can tim: \n");
  else printf("\n Ket qua: \nTen: %s \nMa so: %s \nNgay Thang nam sinh: %d/%d/%d  \nDiem trung binh: %0.2f",
                a->info.ten, a->info.ms, a->info.ngaysinh.day, a->info.ngaysinh.month, a->info.ngaysinh.year, a->info.dtb);

  printf("\n XOA HET CAC PHAN TU: ");
  char xoa, xoa1;
  printf("\n Neu ban muon xoa het cac phan tu, nhap x: ");
  xoa=getch();
  putch(xoa);
  if(xoa='x')
  printf("\n  Nhap Ok de xoa, C de thoat:");
  xoa1=getch();
  putch(xoa1);
  if(xoa1='ok')
   {
    printf("\n Dang xoa...\n xong!");
    removelist(l)  ;
   }
  else if(xoa1='c') printf("\n Huy lenh xoa, bam Enter de thoat.");


  getch();
 }
3/ Cây nhị phân:

//CAY NHI PHAN: NHAP VA TINH TOAN/
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>

typedef struct tagtnode
 {
   int  key;
   struct tagtnode        *pleft;
   struct tagtnode       *pright;

 }tnode;
 typedef tnode            *tree;

 void creattree(tree &t)
  {
   t=NULL;
  }

 int insertnode (tree &t, int  x)
   {
     if (t)
       {
         if (t->key ==x)  return 0;
         if(t->key>x)     return insertnode (t->pleft ,x);
         else             return insertnode(t->pright, x) ;

       }
      t=new tnode;
      if (t==NULL) return -1;
      t->key =x;
      t->pleft=t->pright=NULL;
     return 1;
    }

void NLR (tree root ) //Duyet truoc
 {
  if (root!=NULL)
    {
      printf ("%5d", root->key);
      NLR (root->pleft);//Goi de quy ham NRL
      NLR(root->pright);
    }
 }

void LNR (tree root )//Duyet giua
    {
      if (root!=NULL)
       {
         LNR (root->pleft ) ;
         printf("%5d",root->key);
         LNR (root->pright)  ;

      }
    }

void LRN( tree root) //Duyet sau
 {
    if (root != NULL)
       {
          LRN (root->pleft );
          LRN (root->pright);
          printf("%5d",root-> key );

       }
 }
tnode  * searchnode(tree root, int x)
{
  tnode *p=root;
  while(p!=NULL)
      {
        if(x==p->key) return p;
        else
        if(x<p->key)  p=p->pleft;
        else p=p->pright;
      }
     return NULL;
}

//DEM SO NUT LA CUA CAY :
int demnutla(tnode *root)
{
 if(root==NULL)
    return 0;
 else
    if(root->pleft!=NULL ||root->pright!=NULL)
       return demnutla(root->pleft)+ demnutla(root->pright);
    else
    return 1;
}

//TINH CHIEU CAO CUA CAY:
int highttree(tree &t)
{
  int l=1;
  int r=1;
  if(t==NULL) return 0;
  if(t->pleft!=NULL) l=l+highttree(t->pleft);
  if(t->pright!=NULL) r=r+highttree(t->pright);
  return (l>r) ?l:r  ;
}
//XOA PHAN TU CO KHOA X :
void replace(tree &p, tree &t)
{
 if(t->pleft!=NULL)  replace(p, t->pleft);
 else
   {
     p->key=t->key;
     p=t;
     t=t->pright;
   }

}
void deletenodex(tree &t, int x)
{
 if(t!=NULL)
   {
    if( t->key<x )  deletenodex( t->pright, x  );
    else
     {
       if(t->key>x ) deletenodex(t->pleft, x);
       else //Tim thay node co truong du lieu =x/
          {
             tnode *p;
             p=t;
             if(t->pleft==NULL) t=t->pright;
             else
               {
                 if(t->pright==NULL) t=t->pleft;
                 else  replace(p, t->pright); //Tim ben cay con phai/
               }
             delete p;
          }
     }
   }
  else printf("\n Khong tim thay phan tu can xoa.");
}
//HAM CHINH:

void main ()
{

// NHAP VA IN RA :
  clrscr();
  tree  t=NULL;
  int x;
  do
    {
      printf("\n Nhap x: ") ;
     scanf("%d" ,&x);
      if (x!=0)
       insertnode (t,x);
    }
   while (x!=0);
     printf("\n\n Duyet truoc NLR  :   \n\n");
     NLR (t);
     printf("\n\n Duyet giua  LNR  :   \n\n");
     LNR (t);
     printf("\n\n Duyet sau   LRN  :   \n\n");
     LRN(t);

//DEM SO NUT LA :

printf("\n So nut la la %d ", demnutla(t) );

//TINH CHIEU CAO :

printf("\n chieu cao cay la &d ", highttree(t) );

//TIM KIEM :
int n;
printf("\n Nhap phan tu can tim :");
scanf("%d", &n);
searchnode(t,n);
if(searchnode(t, n)==NULL)  printf("\n Tim khong thay.");
else  printf("\n Tim thay. " );


//XOA PHA TU :
int m;
printf("\n Nhap phan tu can xoa: ");
scanf("%d", &m);
deletenodex(t, m);
printf("\n Deleting...\n Finish! \n View Node Left Right:  \n");
NLR(t);
getch();
}