โปรแกรม C++ ค้นหาแบบอาศัย Locality of Reference

การค้นหาแบบอาศัย Locality of Reference ขึ้นอยู่กับรูปแบบการเข้าถึงหน่วยความจำ ข้อมูลจะถูกจัดสรรใหม่ ใช้วิธี Linear Search ในการค้นหาสมาชิก

อัลกอริทึม

เริ่มต้น
  int find(int *intarray, int n, int item)
  เริ่มต้น comparisons = 0
  สำหรับ i = 0 ถึง n-1
    เพิ่ม comparisons
    ถ้า (item == intarray[i])
      พิมพ์สมาชิกพร้อมดัชนี
      break
    ถ้า (i == n-1)
      พิมพ์ไม่พบสมาชิก
      คืนค่า -1
    จบถ้า
  จบลูป
  พิมพ์ Total comparisons
  สำหรับ j = i ถึง j > 0
    intarray[j] = intarray[j-1]
    intarray[0] = item
  คืนค่า 0
สิ้นสุด

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

// ฟังก์ชันค้นหาแบบ linear
int find(int *intarray, int n, int item) {
    int i;
    int comparisons = 0;
    // นำทางผ่านทุกสมาชิก
    for (i = 0; i < n; i++) {
        // นับจำนวนการเปรียบเทียบ
        comparisons++;
        // ถ้าพบ item ให้ break
        if (item == intarray[i]) {
            cout << "element found at:" << i << endl;
            break;
        }
        // ถ้าดัชนีถึงท้ายแล้ว แสดงว่าไม่มี item
        if (i == n-1) {
            cout << "\nThe element not found.";
            return -1;
        }
    }
    printf("Total comparisons made: %d", comparisons);
    // เลื่อนสมาชิกก่อน item ที่เจอ
    for (int j = i; j > 0; j--)
        intarray[j] = intarray[j-1];
    // วาง item ที่ค้นหาล่าสุดไว้ต้นอาร์เรย์
    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;
    // พิมพ์อาร์เรย์เริ่มต้น
    cout << "\nThe array is: ";
    for (i = 0; i < 20; i++)
        cout << intarray[i] << " ";
    up:
    cout << "\nEnter the Element to be searched: ";
    cin >> n;
    // พิมพ์อาร์เรย์หลังค้นหา
    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;
}

ผลลัพธ์

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