Algoritma carian dan contoh aplikasi dalam C++

Cari algoritma dan contoh aplikasi dalam C++

Dalam C++, algoritma carian merujuk kepada algoritma yang mencari elemen khusus dalam set data. Ia adalah salah satu algoritma yang paling asas dan biasa digunakan dalam program komputer dan digunakan secara meluas dalam pelbagai masalah praktikal. Artikel ini akan memperkenalkan beberapa algoritma carian yang biasa digunakan dalam C++ dan memberikan contoh aplikasi yang sepadan untuk membantu pembaca memahami dan menguasai algoritma ini dengan lebih baik.

1. Algoritma carian linear

Algoritma carian linear (juga dipanggil algoritma carian berjujukan) ialah algoritma carian yang paling mudah dan asas. Idea asasnya ialah membandingkan satu demi satu bermula dari elemen pertama data sehingga elemen sasaran ditemui. Berikut ialah kod untuk melaksanakan carian linear dalam C++:

int linearSearch(int arr[], int n, int x)
{
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == x)
        {
            return i;   // 找到目标元素返回其下标
        }
    }
    return -1;  // 未找到目标元素返回 -1
}

Kerumitan masa bagi algoritma carian linear ialah O(n), dengan n mewakili saiz data, iaitu bilangan elemen dalam data. Jika elemen yang ditemui kebetulan berada di kedudukan terakhir dalam data, maka carian linear perlu merentasi keseluruhan data untuk mencari elemen sasaran, dan kerumitan masa akan mencapai O(n) dalam kes yang paling teruk. Oleh itu, algoritma carian linear tidak cekap apabila saiz data adalah besar.

2. Algoritma carian binari

Algoritma carian binari (juga dipanggil algoritma carian separuh) ialah algoritma carian yang cekap. Ia memerlukan data mestilah teratur, dan mengurangkan skop carian sebanyak separuh dalam setiap carian, dan akhirnya menemui elemen sasaran. Berikut ialah kod untuk melaksanakan carian binari dalam C++:

int binarySearch(int arr[], int n, int x)
{
    int left = 0, right = n - 1, mid;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (arr[mid] == x)
        {
            return mid;   // 找到目标元素返回其下标
        }
        else if (arr[mid] > x)
        {
            right = mid - 1;   // 目标元素在左边区域
        }
        else
        {
            left = mid + 1;   // 目标元素在右边区域
        }
    }
    return -1;  // 未找到目标元素返回 -1
}

Kerumitan masa bagi algoritma carian binari ialah O(log n), di mana n mewakili saiz data, iaitu bilangan elemen dalam data. Algoritma carian binari mengambil kesempatan daripada ciri-ciri data tersusun Setiap carian boleh mengurangkan separuh julat carian untuk mencari elemen sasaran dengan cepat. Walau bagaimanapun, apabila data tidak diisih, ia perlu diisih sebelum carian binari boleh digunakan, yang akan menambah kerumitan masa tambahan.

3. Algoritma carian hash

Algoritma carian hash (juga dipanggil algoritma carian hash) ialah algoritma yang menggunakan fungsi hash untuk mencari dengan pantas. Ia cepat mencari elemen sasaran dengan memetakan elemen data ke kedudukan tetap (iaitu, nilai cincang). Berikut ialah kod untuk melaksanakan carian cincang dalam C++:

const int MAX_SIZE = 10007;   // 哈希表的最大长度

struct Node
{
    int key, value;   // 哈希表中存放的元素
    Node* next;   // 指向下一个节点的指针
};

class HashTable
{
private:
    Node* table[MAX_SIZE];   // 哈希表的数组
    int hashFunc(int key) { return key % MAX_SIZE; }   // 哈希函数

public:
    HashTable() { memset(table, 0, sizeof(table)); }   // 初始化哈希表

    void insert(int key, int value)   // 将元素插入哈希表
    {
        int pos = hashFunc(key);
        Node* p = new Node();
        p->key = key;
        p->value = value;
        p->next = table[pos];
        table[pos] = p;
    }

    int search(int key)   // 在哈希表中查找元素
    {
        int pos = hashFunc(key);
        Node* p = table[pos];
        while (p != NULL)
        {
            if (p->key == key)
            {
                return p->value;   // 找到目标元素返回其值
            }
            p = p->next;
        }
        return -1;  // 未找到目标元素返回 -1
    }
};

Kerumitan masa algoritma carian cincang ialah O(1), yang tidak dipengaruhi oleh saiz data dan sangat cekap. Walau bagaimanapun, terdapat banyak faktor yang perlu dipertimbangkan dalam reka bentuk fungsi cincang Jika fungsi cincang tidak baik, ia boleh menyebabkan konflik cincang, sekali gus menjejaskan kecekapan carian.

4. Contoh aplikasi algoritma carian

Selain daripada tiga algoritma carian di atas, terdapat banyak algoritma carian lain dalam C++, seperti carian interpolasi, carian Fibonacci, dll. Contoh aplikasi mudah diberikan di bawah untuk menunjukkan aplikasi algoritma carian dalam masalah praktikal.

Diberi tatasusunan dan nilai sasaran, cari jumlah dua nombor dalam tatasusunan yang sama dengan nilai sasaran dan kembalikan subskrip bagi dua nombor itu. Berikut ialah kod untuk melaksanakan fungsi ini dalam C++:

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> umap;
    int size = nums.size();
    for (int i = 0; i < size; i++)
    {
        int complement = target - nums[i];
        if (umap.find(complement) != umap.end())
        {
            return { umap[complement], i };
        }
        umap[nums[i]] = i;
    }
    return {};
}

Algoritma ini menggunakan idea carian hash Semasa proses merentasi tatasusunan, ia mencari dalam jadual cincang sama ada terdapat elemen yang menambah pada semasa. elemen kepada nilai sasaran Jika ia wujud, indeksnya dikembalikan.

Ringkasan

Artikel ini memperkenalkan tiga algoritma carian yang biasa digunakan dalam C++: algoritma carian linear, algoritma carian binari dan algoritma carian cincang, dan memberikan contoh aplikasi yang sepadan. Memahami kelebihan, kelemahan dan aplikasi praktikal algoritma carian ini boleh membantu kami menggunakannya dengan lebih baik dalam pengaturcaraan dan meningkatkan kecekapan dan kualiti program.

Atas ialah kandungan terperinci Algoritma carian dan contoh aplikasi dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!