Data structures and related algorithms in C++

C is a widely used programming language that supports a variety of data structures and algorithms. Data structures are methods of storing and organizing data, while algorithms are methods of manipulating data on data structures. For each problem, it is very important to choose the appropriate data structure and algorithm. In this article, we will introduce some commonly used data structures and algorithms, as well as their implementation in C.

1. Array

An array is a simple data structure. It is a data collection composed of elements of the same type. In C, we can use arrays to represent fixed-size data structures, such as image pixels or maps in a game. The following is an example of declaring and initializing an array:

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

2. Linked list

Linked list is another commonly used data structure, which is composed of nodes. Each node contains a value and a pointer to the next node. Linked lists can be used to represent dynamically sized data structures. The following is an example of using a linked list to implement a stack:

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. Tree

A tree is a very flexible data structure that consists of nodes. Each node contains a value and points to it. Child's pointer. Trees can be used to represent hierarchical structures, such as file systems or corporate organizational structures. The following is an example of using trees to implement recursion:

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. Graph

A graph is a data structure that represents discrete objects and the relationships between them. A graph consists of nodes and the edges between them. There are many algorithms for graphs, such as Dijkstra's algorithm and minimum spanning tree algorithm. The following are examples of using adjacency matrices to represent undirected graphs:

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

Through these examples, we can see the flexibility and power of data structures and algorithms in C. Different types of data structures and algorithms have good applications in different problems. In actual programming, we should pay attention to choosing appropriate data structures and algorithms to achieve more efficient and reliable code.

The above is the detailed content of Data structures and related algorithms in C++. For more information, please follow other related articles on the PHP Chinese website!