Chương trình C++ tìm kiếm dựa trên tính cục bộ tham chiếu

Tìm kiếm dựa trên tính cục bộ tham chiếu (locality of reference), phụ thuộc vào mẫu truy cập bộ nhớ, các phần tử dữ liệu được cấp phát lại.

Ở đây sử dụng phương pháp tìm kiếm tuyến tính để tìm một phần tử.

Thuật toán

Bắt đầu
  int find(int *intarray, int n, int item)
  khởi tạo comparisons = 0
  for i = 0 đến n-1
    Tăng comparisons
    if(item == intarray[i])
      In phần tử với chỉ số
      break
    if(i == n-1)
      In phần tử không tìm thấy
      trả về -1
  In Tổng so sánh
  For j = i đến i > 0
    intarray[j] = intarray[j-1]
    intarray[0] = item
  trả về 0
Kết thúc

Ví dụ

#include<iostream>
using namespace std;

// Hàm thực hiện tìm kiếm tuyến tính.
// Phương pháp này thực hiện tìm kiếm tuyến tính.
int find(int *intarray, int n, int item) {
  int i;
  int comparisons = 0;
  // duyệt qua tất cả phần tử
  for(i = 0; i < n; i++) {
    // đếm số lần so sánh
    comparisons++;
    // nếu tìm thấy, thoát vòng lặp
    if(item == intarray[i]) {
      cout << "element found at:" << i << endl;
      break;
    }
    // nếu chỉ số đến cuối mà không thấy.
    if(i == n-1) {
      cout << "\nThe element not found.";
      return -1;
    }
  }
  printf("Total comparisons made: %d", comparisons);
  // Dịch chuyển các phần tử trước phần tử khớp.
  for(int j = i; j > 0; j--)
    intarray[j] = intarray[j-1];
  // Đặt phần tử vừa tìm vào đầu mảng.
  intarray[0] = item;
  return 0;
}

int main() {
  int intarray[20] = {1,2,3,4,6,7,9,11,12,14,15,16,26,19,33,34,43,45,55,66};
  int i, n;
  char ch;
  // in mảng ban đầu.
  cout << "\nThe array is: ";
  for(i = 0; i < 20; i++)
    cout << intarray[i] << " ";
  up:
  cout << "\nEnter the Element to be searched: ";
  cin >> n;
  // In mảng sau khi cập nhật.
  if(find(intarray, 20, n) != -1) {
    cout << "\nThe array after searching is: ";
    for(i = 0; i < 20; i++)
      cout << intarray[i] << " ";
  }
  cout << "\n\nWant to search more.......yes/no(y/n)?";
  cin >> ch;
  if(ch == 'y' || ch == 'Y')
    goto up;
  return 0;
}

Kết quả

The array is: 1 2 3 4 6 7 9 11 12 14 15 16 26 19 33 34 43 45 55 66
Enter the Element to be searched: 26
element found at: 12
Total comparisons made: 13
The array after searching is: 26 1 2 3 4 6 7 9 11 12 14 15 16 19 33 34 43 45 55 66
Want to search more.......yes/no(y/n)? y
Enter the Element to be searched: 0
The element not found.
Want to search more.......yes/no(y/n)? n