C++ のデータ構造と関連アルゴリズム

C は、さまざまなデータ構造とアルゴリズムをサポートする、広く使用されているプログラミング言語です。データ構造はデータを保存および整理する方法であり、アルゴリズムはデータ構造上のデータを操作する方法です。問題ごとに、適切なデータ構造とアルゴリズムを選択することが非常に重要です。この記事では、一般的に使用されるデータ構造とアルゴリズム、およびそれらの C での実装を紹介します。

1. 配列

配列は単純なデータ構造であり、同じ型の要素で構成されるデータの集合です。 C では、配列を使用して、画像ピクセルやゲーム内のマップなどの固定サイズのデータ​​構造を表すことができます。以下は、配列の宣言と初期化の例です。

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

2. リンク リスト

リンク リストは、よく使用されるもう 1 つのデータ構造であり、ノードで構成されます。各ノードには値と次のノードへのポインタが含まれています。リンク リストを使用すると、動的にサイズ変更されるデータ構造を表すことができます。以下は、リンク リストを使用してスタックを実装する例です:

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. ツリー

ツリーはノードで構成される非常に柔軟なデータ構造です。各ノードには値と値が含まれています。子供のポインタ。ツリーを使用して、ファイル システムや企業の組織構造などの階層構造を表すことができます。以下は、ツリーを使用して再帰を実装する例です:

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;
}

4. グラフ

グラフは、個別のオブジェクトとそれらの間の関係を表すデータ構造です。グラフはノードとノード間のエッジで構成されます。ダイクストラのアルゴリズムや最小スパニング ツリー アルゴリズムなど、グラフのアルゴリズムは多数あります。以下は、隣接行列を使用して無向グラフを表現する例です。

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;
}

これらの例を通じて、C のデータ構造とアルゴリズムの柔軟性と能力がわかります。さまざまなタイプのデータ構造とアルゴリズムは、さまざまな問題に適しています。実際のプログラミングでは、より効率的で信頼性の高いコードを実現するために、適切なデータ構造とアルゴリズムの選択に注意を払う必要があります。

以上がC++ のデータ構造と関連アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。