Contoh penggunaan C++ untuk menyelesaikan masalah struktur data

Dengan perkembangan berterusan sains komputer, struktur data telah menjadi satu bidang yang penting. Dalam pengaturcaraan komputer, struktur data adalah sangat penting kerana ia adalah cara data disimpan dan diuruskan. Struktur data yang sempurna boleh meningkatkan kecekapan dan kebolehskalaan program. Dalam artikel ini, kami akan meneroka cara menyelesaikan masalah struktur data menggunakan C++.

1. Tindanan

Timbunan ialah struktur data biasa. Dalam timbunan, data boleh ditambah atau dialih keluar, tetapi mereka mesti mengikut prinsip 'Last In First Out' (LIFO). Ia adalah sangat mudah untuk menggunakan ciri LIFO timbunan untuk menyelesaikan masalah. Dalam C++, tindanan boleh dilaksanakan menggunakan bekas tindanan dalam perpustakaan STL.

Contoh berikut boleh memberi anda pemahaman yang lebih baik tentang cara menggunakan tindanan dalam C++:

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> myStack;

    myStack.push(1);
    myStack.push(2);
    myStack.push(3);

    while (!myStack.empty()) {
        cout << myStack.top() << " ";
        myStack.pop();
    }

    return 0;
}

Dalam contoh di atas, kami telah mencipta tindanan kosong dan menggunakan fungsi tolak untuk menolak nombor 1, 2 dan 3 ke dalam timbunan. Akhir sekali, kami menggunakan gelung sementara untuk memunculkan dan mengeluarkan elemen daripada timbunan. Kelebihan menggunakan tindanan ialah kodnya ringkas, cepat dan mudah difahami.

2. Baris gilir

Barisan ialah satu lagi struktur data biasa. Baris gilir juga boleh menambah dan mengalih keluar elemen, tetapi mereka mesti menggunakan prinsip 'Masuk Dahulu Keluar' (FIFO). Baris gilir amat sesuai untuk tugasan yang memerlukan elemen diproses secara berurutan. Juga dalam C++, baris gilir boleh dilaksanakan menggunakan bekas baris gilir dalam perpustakaan STL.

Contoh berikut boleh memberi anda pemahaman yang lebih baik tentang cara menggunakan baris gilir dalam C++:

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> myQueue;

    myQueue.push(1);
    myQueue.push(2);
    myQueue.push(3);

    while (!myQueue.empty()) {
        cout << myQueue.front() << " ";
        myQueue.pop();
    }

    return 0;
}

Dalam contoh ini, kami mencipta baris gilir kosong dan menggunakan fungsi tolak untuk menolak nombor 1, 2 dan 3 ke dalam baris gilir. Begitu juga, kami menggunakan gelung sementara untuk mengalih keluar dan mengeluarkan elemen dalam baris gilir.

3. Senarai Terpaut

Senarai terpaut ialah struktur data yang terdiri daripada satu siri nod, setiap nod mengandungi elemen data dan penunjuk ke nod seterusnya. Senarai terpaut ialah struktur data biasa yang mempunyai kelebihan untuk memasukkan dan memadam elemen dengan cekap. Dalam C++, anda boleh menggunakan senarai terpaut tersuai untuk melaksanakan senarai terpaut.

Contoh berikut menunjukkan cara untuk melaksanakan senarai terpaut dalam C++:

#include <iostream>

using namespace std;

struct Node {
    int data;
    Node* next;
};

class LinkedList {
    private:
        Node* head;

    public:
        LinkedList() {
            head = NULL;
        }

        void insert(int value) {
            Node* newNode = new Node;
            newNode->data = value;
            newNode->next = head;
            head = newNode;
        }

        void remove(int value) {
            if (head == NULL) {
                return;
            }

            Node* current = head;
            Node* previous = NULL;

            while (current->data != value && current != NULL) {
                previous = current;
                current = current->next;
            }

            if (current == NULL) {
                return;
            }

            if (previous == NULL) {
                head = current->next;
            } else {
                previous->next = current->next;
            }

            delete current;
        }

        void print() {
            Node* current = head;

            while (current != NULL) {
                cout << current->data << " ";
                current = current->next;
            }

            cout << endl;
        }
};

int main() {
    LinkedList myList;

    myList.insert(1);
    myList.insert(2);
    myList.insert(3);

    myList.print();

    myList.remove(2);

    myList.print();

    return 0;
}

Dalam contoh ini, kita mula-mula mencipta struktur Nod, yang mengandungi pembolehubah int dan penunjuk ke nod seterusnya. Kemudian kami menggunakan kelas untuk melaksanakan LinkedList. Dalam kelas LinkedList, kami mentakrifkan fungsi untuk memasukkan, memadam dan mencetak senarai terpaut. Dalam fungsi utama, kami mencipta LinkedList dan memasukkan nombor 1, 2 dan 3 ke dalam senarai terpaut. Kemudian kami memanggil fungsi keluarkan untuk memadam nombor 2 daripada senarai terpaut dan mencetak hasil akhir.

4. Pepohon binari

Pepohon perduaan ialah struktur data Setiap nod mempunyai paling banyak dua subpohon, masing-masing dipanggil subpohon kiri dan subpohon kanan. Pokok binari digunakan secara meluas dalam mencari dan menyusun. Dalam C++, anda boleh menggunakan struktur pokok binari tersuai untuk melaksanakan pokok binari.

Contoh berikut menunjukkan cara menggunakan pepohon binari tersuai dalam C++:

#include <iostream>

using namespace std;

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
};

class BinaryTree {
    private:
        TreeNode* root;

    public:
        BinaryTree() {
            root = NULL;
        }

        void insert(int value) {
            if (root == NULL) {
                root = new TreeNode;
                root->value = value;
                root->left = NULL;
                root->right = NULL;
                return;
            }

            TreeNode* current = root;

            while (true) {
                if (value < current->value) {
                    if (current->left == NULL) {
                        current->left = new TreeNode;
                        current->left->value = value;
                        current->left->left = NULL;
                        current->left->right = NULL;
                        break;
                    } else {
                        current = current->left;
                    }
                } else {
                    if (current->right == NULL) {
                        current->right = new TreeNode;
                        current->right->value = value;
                        current->right->left = NULL;
                        current->right->right = NULL;
                        break;
                    } else {
                        current = current->right;
                    }
                }
            }
        }

        void printInorder() {
            printInorder(root);
        }

        void printInorder(TreeNode* node) {
            if (node == NULL) {
                return;
            }

            printInorder(node->left);
            cout << node->value << " ";
            printInorder(node->right);
        }
};

int main() {
    BinaryTree myTree;

    myTree.insert(15);
    myTree.insert(10);
    myTree.insert(20);
    myTree.insert(8);
    myTree.insert(12);
    myTree.insert(17);
    myTree.insert(25);

    myTree.printInorder(); // 8 10 12 15 17 20 25

    return 0;
}

Dalam contoh ini, kami mentakrifkan struktur TreeNode yang mengandungi pembolehubah int dan penuding ke subpokok kiri dan kanan. Kemudian, kami melaksanakan BinaryTree menggunakan kelas dan menentukan fungsi sisipan dan cetakan. Dalam fungsi utama, kami mencipta BinaryTree dan memasukkan nombor 15, 10, 20, 8, 12, 17 dan 25 ke dalam pokok. Kemudian kami memanggil fungsi printInorder untuk mencetak nilai semua nod dalam pokok binari.

Ringkasan:

Dalam artikel ini, kami meneroka cara menyelesaikan masalah struktur data menggunakan C++. Kami memperkenalkan tindanan, baris gilir, senarai terpaut dan pepohon binari dan memberikan contoh cara melaksanakannya dalam C++. Struktur data ini boleh digunakan untuk kedua-dua masalah pengaturcaraan mudah dan tugasan algoritma dan sains komputer yang lebih kompleks. Kebiasaan dengan struktur data ini adalah penting untuk menjadi seorang saintis komputer yang berjaya.

Atas ialah kandungan terperinci Contoh penggunaan C++ untuk menyelesaikan masalah struktur data. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!