-----[L]--- Bài tập C++ Chương 2 - Số Nguyên

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

//=====================================
//khai bao prototype
void NhapDS (int a[], int n);
void XuatDS (int a[], int n);
void Them1PT (int a[], int *n, int vt, int x);
void Xoa1PT (int a[], int *n, int vt);

//======================================
//Cac Prototype O Phia Duoi Se Khac Nhau Trong Tung Bai Tap
int  LinearSearch (int a[], int n, int x);
int  BinarySearch (int a[], int n, int x );

void HoanVi (int *x, int *y);
void InsertionSort (int a[], int n);
void SelectionSort (int a[], int n);
void InterchangeSort (int a[], int n);
void BubbleSort (int a[], int n);

void QuickSort (int a[], int l, int r);

//...........
//=====================================
//Chuong trinh Chinh

void main()
{
   clrscr();
   int a[20], x;
   int n, chon, kt, vt;
   char ht[20], ms[10], ch;
   printf("\n\tNhap SPTu : ");
   scanf ("%d", &n);
   printf("\n\tNhap Cac Phan Tu !");
   NhapDS (a, n);  //Goi Ham
   do
   {
      clrscr();
      printf("\n\n\tBAI TAP CHUONG HAI !");
      printf("\n\t1  : Nhap DS Moi !");
      printf("\n\t2  : Xuat Danh Sach !");
      printf("\n\t3  : Them 1 Phan Tu vao DS !");
      printf("\n\t4  : Xoa 1 Phan Tu Trong DS !");
      printf("\n\t5  : Tim Kiem bang Phuong Phap Tuyen Tinh !");
      printf("\n\t6  : Tim Kiem bang PP Nhi Phan !");
      printf("\n\t7  : Sap Xep DS bang PPhap InsertionSort Dua Vao Ten !");
      printf("\n\t8  : Sap Xep DS bang PPhap SelectionSort Dua Vao Ma So !");
      printf("\n\t9  : Sap Xep DS bang PPhap InterchangeSort Dua Vao Diem CTDL !");
      printf("\n\t10 : Sap Xep DS bang PPhap BubbleSort Dua Vao Diem TB !");
      printf("\n\t11 : Sap Xep DS bang PPhap QuickSort Dua Vao Diem CSDL !");
      printf("\n\t12 : Hieu Chinh Noi Dung 1 Phan Tu !");
      printf("\n\t13 : Danh Sach Nhung SVien Dat !");
      printf("\n\t14 : Danh Sach Nhung SVien Khong Dat !");
      printf("\n\t15 : Xuat Danh Sach Dang BTHuong !");
      printf("\n\t.....!");
      printf("\n\t0  : THOAT KHOI CHUONG TRINH !");
      printf("\n\tBan Chon Chuc Nang Nao ? ");
      scanf ("%d", &chon);
      switch(chon)
      {
         case 1:
         {
            clrscr();
            printf("\n\tNhap SPTu : ");
            scanf ("%d", &n);
            printf("\n\tNhap Cac Phan Tu !");
            NhapDS (a, n);
            break;
         }
         case 2:
         {
            clrscr();
            printf("\n\tDanh Sach Hien Tai la !\n\t");
            XuatDS (a, n);
            getch();
            break;
         }
         case 3:
         {
            clrscr();
            printf("\n\tThem 1 PTu vao DS !");
            printf("\n\tDanh Sach Truoc Khi Them  !");
            XuatDS (a, n);
            do
            {
               printf("\n\tNhap Vi Tri Can Them (0 - > %d): ", n);
               scanf ("%d", &vt);
            }while (vt < 0 || vt > n);
            printf("\n\tNhap Noi Dung Can Them X : ");
            scanf ("%d", &x);
            Them1PT (a, &n, vt, x);
            printf("\n\tDanh Sach Sau Khi Them  !");
            XuatDS (a, n);
            getch();
            break;
         }
         case 4:
         {
            clrscr();
            printf("\n\tXoa 1 PTu Trong DS !");
            printf("\n\tDanh Sach Truoc Khi Xoa  !");
            XuatDS (a, n);
            do
            {
               printf("\n\tNhap Vi Tri Can Xoa (0 - > %d): ", n - 1);
               scanf ("%d", &vt);
            }while (vt < 0 || vt >= n);
            Xoa1PT (a, &n, vt);
            printf("\n\tDanh Sach Sau Khi Xoa  !");
            XuatDS (a, n);
            getch();
            break;
         }
         case 5:
         {
            clrscr();
            printf("\n\tTim Kiem Bang Phuong Phap Tuyen Tinh !");
            printf("\n\tDanh Sach Hien tai La !\n");
            XuatDS (a, n);
            printf("\n\tNhap Noi Dung Can Tim X : ");
            scanf ("%d", &x);
            kt = LinearSearch(a, n, x);
            if (kt == -1)
               printf("\n\tKhong Tim Thay Phan Tu co Noi Dung %d trong DS !");
            else
               printf("\n\tTim Thay Phan Tu co Noi Dung %d trong DS Tai vi Tri %d !", x, kt);
            getch();
            break;
         }
         case 6:
         {
            clrscr();
            printf("\n\tTim Kiem Bang Phuong Phap Nhi Phan  !");
            printf("\n\tDanh Sach Hien Tai La !\n");
            SelectionSort (a, n);
            XuatDS (a, n);
            printf("\n\tNhap Noi Dung Can Tim X : ");
            scanf ("%d", &x);
            kt = BinarySearch(a, n, x);
            if (kt == -1)
               printf("\n\tKhong Tim Thay Phan Tu co Noi Dung %d trong DS !");
            else
               printf("\n\tTim Thay Phan Tu co Noi Dung %d trong DS Tai vi Tri %d !", x, kt);
            getch();
            break;
         }
         case 7:
         {
            clrscr();
            printf("\n\tSX Bang PPhap Chen Truc Tiep !\n");
            printf("\n\tDanh Sach Truoc Khi SX !\n");
            XuatDS (a, n);
            InsertionSort (a, n);
            printf("\n\tDanh Sach Sau Khi SX !\n");
            XuatDS (a, n);
            getch();
            break;
         }
         case 8:
         {
            clrscr();
            printf("\n\tSX Bang PPhap Chon Truc Tiep !\n");
            printf("\n\tDanh Sach Truoc Khi SX !\n");
            XuatDS (a, n);
            SelectionSort (a, n);
            printf("\n\tDanh Sach Sau Khi SX !\n");
            XuatDS (a, n);
            getch();
            break;
         }
         case 9:
         {
            clrscr();
            printf("\n\tSX Bang PPhap Doi Cho Truc Tiep !\n");
            printf("\n\tDanh Sach Truoc Khi SX !\n");
            XuatDS (a, n);
            InterchangeSort (a, n);
            printf("\n\tDanh Sach Sau Khi SX !\n");
            XuatDS (a, n);
            getch();
            break;
         }
         case 10:
         {
            clrscr();
            printf("\n\tSX Bang PPhap Noi Bot !\n");
            printf("\n\tDanh Sach Truoc Khi SX !\n");
            XuatDS (a, n);
            BubbleSort (a, n);
            printf("\n\tDanh Sach Sau Khi SX !\n");
            XuatDS (a, n);
            getch();
            break;
         }
         case 11:
         {
            clrscr();
            printf("\n\tSX Bang PPhap Phan Hoach  !\n");
            printf("\n\tDanh Sach Truoc Khi SX !\n");
            XuatDS (a, n);
            QuickSort (a, 0, n - 1);
            printf("\n\tDanh Sach Sau Khi SX !\n");
            XuatDS (a, n);
            getch();
            break;
         }
      }//KT Switch
   }while (chon > 0);
   getch();
}//KT CTChinh

//CD Cac prototype o tren
//=====================================
//=====================================
//Tac Vu Nay Tuong Tu Cho Cac bai Tap Khac Ve Cau Truc
void NhapDS (int a[], int n)
{
   for (int i = 0; i < n; i++)
   {
      printf("\n\tNhap PTu Thu %d : ", i+1);
      scanf("%d", &a[i]);
   }
}
//Tac Vu Nay Tuong Tu Cho Cac bai Tap Khac Ve Cau Truc
//Dang Nay Xuat DS Dang Binh Thuong
void XuatDS (int a[], int n)
{
   for (int i = 0; i < n; i++)
      printf("%7d", a[i]);
}
//=====================================
//Tac Vu Nay Tuong Tu Cho Cac bai Tap Khac Ve Cau Truc
void Them1PT (int a[],  int *n, int vt , int x)
{
   int i;
   if ((vt < 0) || (vt > *n))
      printf("\n\tvi Tri Them Khong Hop le !");
   else
   {
      //Doi Cac Phan Tu Tu Cuoi Den VTThem Len 1 VTri
      for (i = *n; i > vt; i--)
         a[i] = a[i - 1];
      //KT Qua Trinh Doi
      a[vt] = x;
      *n = *n + 1;   //Tang SPTu len 1 DV
   }
}

//=====================================
//Tac Vu Nay Tuong Tu Cho Cac bai Tap Khac Ve Cau Truc
void Xoa1PT (int a[], int *n , int vt)
{
   int i;
   if ((vt < 0) || (vt >= *n))
      printf("\n\tVi Tri Xoa Khong Hop le !");
   else
   {
      //Doi Cac Phan Tu Tu vt + 1 Den Cuoi Xuong 1VT
      for (i = vt + 1; i < *n; i++)
         a[i - 1] = a[i];
      //KT Qua Trinh Doi
      *n = *n - 1;   //Giam SPTu len 1 DV
   }
}
//=====================================
int  LinearSearch (int a[], int n, int x)
{
   int i = 0;
   while ((i < n) && (a[i] != x))
      i++;
   if (i < n)
      return i;
   return -1;
}

//====================================
int  BinarySearch (int a[], int n, int x )
{
   int l, r, mid;
   l = 0;
   r = n - 1;
   do
   {
      mid = (l + r) / 2;
      if (a[mid] == x)
         return mid;
      if (a[mid] > x)
         r = mid - 1;
      else
         l = mid + 1;
   }while (l <= r);
   return -1;
}
//=====================================
void SelectionSort (int a[], int n)
{
   int i, vtmin, j;
   for (i = 0; i < n - 1; i++)
   {
      vtmin = i;
      for (j = i + 1; j < n; j++)
         if (a[vtmin] > a[j])
            vtmin = j;
      if (vtmin != i)
         HoanVi (&a[vtmin], &a[i]);
   }
}
//=====================================
void InsertionSort (int a[], int n)
{
   int i, j, pos;
   int x;
   for (i = 1; i < n; i++)
   {
      x = a[i];
      pos = i - 1;
      while ((i >= 0) && (a[pos] > x))
      {
         a[pos + 1] = a[pos];
         pos --;
      }
      a[pos + 1] = x;
   }
}
//=====================================
void InterchangeSort (int a[], int n)
{
   int i, j;
   for (i = 0; i < n - 1; i++)
      for (j = i + 1; j < n; j++)
         if (a[i] > a[j])
            HoanVi (&a[i], &a[j]);
}
//=====================================
void BubbleSort (int a[], int n)
{
   int i, j;
   for (i = 0; i < n - 1; i++)
      for (j = n - 1; j > i; j--)
         if (a[j - 1] > a[j])
            HoanVi (&a[j - 1], &a[j]);
}
//=====================================
void QuickSort (int a[], int l, int r)
{
   int i, j, x;
   i = l;
   j = r;
   x = a[(l + r) / 2];
   do
   {
      while (a[i] < x)
         i++;
      while (a[j] > x)
         j--;
      if (i <= j)
      {
         HoanVi (&a[i], &a[j]);
         i ++;
         j --;
      }
   }while (i < j);
   if (l < j)
      QuickSort (a, l, j);
   if (i < r)
      QuickSort (a, i, r);
}
//=====================================
void HoanVi (int *x, int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}