Struktur data dan algoritma berkaitan dalam C++

C++ ialah bahasa pengaturcaraan yang digunakan secara meluas yang menyokong pelbagai struktur data dan algoritma. Struktur data ialah kaedah menyimpan dan menyusun data, manakala algoritma ialah kaedah memanipulasi data pada struktur data. Bagi setiap masalah, adalah sangat penting untuk memilih struktur data dan algoritma yang sesuai. Dalam artikel ini, kami akan memperkenalkan beberapa struktur dan algoritma data yang biasa digunakan, serta pelaksanaannya dalam C++.

1. Tatasusunan

Tatasusunan ialah struktur data ringkas Ia adalah pengumpulan data yang terdiri daripada unsur-unsur yang sama. Dalam C++, kita boleh menggunakan tatasusunan untuk mewakili struktur data bersaiz tetap, seperti piksel imej atau peta dalam permainan. Berikut ialah contoh mengisytiharkan dan memulakan tatasusunan:

int arr[5]; // 定义一个包含5个整数的数组
arr[0] = 1; // 初始化第一个数组元素
arr[1] = 2; // 初始化第二个数组元素
arr[2] = 3; // 初始化第三个数组元素
arr[3] = 4; // 初始化第四个数组元素
arr[4] = 5; // 初始化第五个数组元素

2. Senarai terpaut

Senarai terpaut ialah satu lagi struktur data yang biasa digunakan, yang terdiri daripada nod. Setiap nod mengandungi nilai dan penunjuk ke nod seterusnya. Senarai terpaut boleh digunakan untuk mewakili struktur data bersaiz dinamik. Berikut ialah contoh menggunakan senarai terpaut untuk melaksanakan tindanan:

class Node {
public:
    int data;
    Node* next;
};
 
class Stack {
public:
    Stack() {
        head = NULL;
    }
    void push(int data) {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->next = head;
        head = newNode;
    }
    void pop() {
        if (head != NULL) {
            Node* temp = head;
            head = head->next;
            delete(temp);
        }
    }
private:
    Node* head;
};

3. Pokok

Pohon ialah struktur data yang sangat fleksibel yang terdiri daripada nod, setiap nod mengandungi nilai dan penunjuk kepada anaknya. Pokok boleh digunakan untuk mewakili struktur hierarki, seperti sistem fail atau struktur organisasi korporat. Berikut ialah contoh penggunaan pokok untuk melaksanakan rekursi:

class Node {
public:
    int data;
    Node* left;
    Node* right;
};

void inOrderTraversal(Node* node) {
    if (node == NULL) return;
    inOrderTraversal(node->left);
    cout << node->data << " ";
    inOrderTraversal(node->right);
}

int main() {
    Node* root = new Node();
    root->data = 1;
    root->left = new Node();
    root->left->data = 2;
    root->right = new Node();
    root->right->data = 3;
    inOrderTraversal(root);
    return 0;
}

IV Graf

Graf ialah struktur data yang mewakili objek diskret dan perhubungan antara mereka. Graf terdiri daripada nod dan tepi di antara mereka. Terdapat banyak algoritma untuk graf, seperti algoritma Dijkstra dan algoritma pokok rentang minimum. Berikut ialah contoh penggunaan matriks bersebelahan untuk mewakili graf tidak berarah:

const int MAX_V = 100;
int cost[MAX_V][MAX_V]; // 边的权重
int d[MAX_V]; // 从源节点到各个节点的最短路径长度
bool used[MAX_V]; // 是否已使用节点

int V, E; // V表示图的节点数，E表示图的边数

void dijkstra(int s) {
    fill(d, d + V, INF);
    fill(used, used + V, false);
    d[s] = 0;
    while (true) {
        int v = -1;
        for (int u = 0; u < V; u++) {
            if (!used[u] && (v == -1 || d[u] < d[v])) {
                v = u;
            }
        }
        if (v == -1) break;
        used[v] = true;
        for (int u = 0; u < V; u++) {
            d[u] = min(d[u], d[v] + cost[v][u]);
        }
    }
}

int main() {
    // 处理输入
    dijkstra(0);
    // 输出结果
    return 0;
}

Melalui contoh ini, kita dapat melihat kefleksibelan dan kuasa struktur data dan algoritma dalam C++. Jenis struktur data dan algoritma yang berbeza mempunyai aplikasi yang baik dalam masalah yang berbeza. Dalam pengaturcaraan sebenar, kita harus memberi perhatian kepada memilih struktur data dan algoritma yang sesuai untuk mencapai kod yang lebih cekap dan boleh dipercayai.

Atas ialah kandungan terperinci Struktur data dan algoritma berkaitan dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!