CTDL: Tìm Kiếm

Bài toán 1. Tìm kiếm và mô phỏng tiến trình thực hiện thuật toán tìm kiếm tuyến tính và tìm kiếm nhị phân.
Yêu cầu:
               + Tạo mảng A gồm các số tự động phát sinh trong một giới hạn mà bạn chọn.
               + Xuất mảng A để biết tình trạng dữ liệu hiện tại.
               + Thực hiện quá trình tìm kiếm giá trị X và cho ra kết quả.
Bài toán 2. Tiến hành ứng dụng thuật toán tìm kiếm vào dữ liệu có cấu trúc
Yêu cầu:
               + Xây dựng cấu trúc sinh viên với các thông tin: MSSV, HoTen, Diem
               + Các hàm thao tác trên danh sách sinh viên như : nhập, xuất
               + Tìm kiếm một sinh viên có MSSV là 0394876 và in ra các thông tin chi tiết của sinh viên đó
Thông tin về hàm trong C:

void gotoxy(int x, int y); Hàm gotoxy có nghĩa là dời con trỏ về tọa độ thứ x,y nào đó trên màn hình.
void delay(long milisec); Hàm delay là ngừng chương trình trong 1/1000 giây.
Cả hai hàm này nằm trong thư viện conio.h nhưng trong Visual C++ thì chỉ có thể dùng hàm Sleep để thế cho delay còn gotoxy thì có thể điều chỉnh lại bằng cách sử dụng đoạn code dưới đây.
Hàm gotoxy tạm thời có thể tự định nghĩa như sau:

Code:

#include "windows.h"
void gotoxy(int x,int y)
{ HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE) ;
COORD position = {x,y} ; SetConsoleCursorPosition(hStdout,position ) ;
}
Định nghĩa xong thì dùng y như là gotoxy của thư viện conio.h.

Một số source code tham khảo:
Thuật toán tìm kiếm nhị phân tìm phần tử x trong mảng a.
int binarysearch(int a[], int x)  // x là giá trị cần tìm trong mảng a
{
    int left , right , mid;
    left = 0;
    right = n-1;  // n là số phần tử mảng a
    while (left <= right)
    {          mid = (left + right) / 2;
        if (a[mid] < x)
            left = mid +1;
        else
        {    if (a[mid] > x)
                right = mid - 1;
            else
                return mid;
        }
    }
    return -1;
}

Hàm khởi tạo mảng A với N phần tử.
void initArray(int* A, int N)
{
      for (int i=0; i<N; i++)
            A[i] = rand() % 100;
}

Hàm in tạo mảng A với N phần tử ra màn hình tại tọa độ (XY, YY).
void printArray(int* A, int N)
{
      textcolor(3);
      gotoxy(XX-5, YY);
      cprintf("A = [");
      for (int i=0; i<N; i++)
      {
            gotoxy(XX + i* 4, YY);
            cprintf("%3d ", A[i]);
      }
      cprintf("]");
      gotoxy(1, YY);
}

CODE chương trình minh họa thuật toán tìm kiếm tuyến tính
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <mem.h>
#include <dos.h>
#include <graphics.h>

int XX = 10, YY = 10;

void initArray(int* A, int N)
{
      for (int i=0; i<N; i++)
            A[i] = rand() % 100;
}

void printArray(int* A, int N)
{
      textcolor(3);
      gotoxy(XX-5, YY);
      cprintf("A = [");
      for (int i=0; i<N; i++)
      {
            gotoxy(XX + i* 4, YY);
            cprintf("%3d ", A[i]);
      }
      cprintf("]");
      gotoxy(1, YY);
}

void printLineSearch(int* A, int N, int X)
{
      for (int i=0; i<N; i++)
      {
            for (int j=0; j<4; j++)
            {
                  delay(100);
                  textcolor(2);
                  gotoxy(XX+(i-1)*4+j, YY+2);
                  cprintf(" %3d ?", X);
            }

            if (A[i] == X)
            {
                  textcolor(4 + BLINK);
                  gotoxy(XX+(i-1)*4+j, YY);
                  cprintf("%3d ", A[i]);
                  gotoxy(XX, YY + 4);
                  cprintf("ANS: Found");
                  gotoxy(XX-3, YY);
                  return;
            }
            else
            {
                  textcolor(4 + BLINK);
                  gotoxy(XX+(i-1)*4+j, YY);
                  cprintf("%3d ", A[i]);
            }

            gotoxy(XX-3, YY);
            delay(1000);

            textcolor(6);
            gotoxy(XX+(i-1)*4+j, YY);
            cprintf("%3d ", A[i]);
      }

      textcolor(4 + BLINK);
      gotoxy(XX-4, YY + 4);
      cprintf("ANS: Not Found");
      gotoxy(XX-3, YY);
}

void sort(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])
                  {
                        int t = A[i];
                        A[i] = A[j];
                        A[j] = t;
                  }
            }
      }

}
void printBinarySearch(int* A, int N, int X)
{
      int l = 0;
      int r = N-1;
      while (l<=r)
      {
            int m = (l+r) / 2;
            if (A[m] < X)
                  l = m;
            if (A[m] > X)
                  r = m;
            if (A[m] == X)
            {
                  textcolor(4 + BLINK);
                  gotoxy(XX+(m-1)*4+4, YY);
                  cprintf("%3d ", A[m]);
                  gotoxy(XX, YY + 4);
                  cprintf("ANS: Found");
                  gotoxy(XX-3, YY);
                  return;
            }
      }
}

void main()
{
      int A[100], N =15;

      clrscr();

      initArray(A, N);
      printArray(A, N);

      printLineSearch(A, N, A[11]);

      sort(A, N);
      printBinarySearch(A, N, A[10]);

      getch();
}