使用C++实现高效数据结构和算法

一、C++中的STL

C++中的STL（Standard Template Library）是一个高效的数据结构和算法库。它包含了众多的数据结构，例如vector、set、map等等；同时也包含了一些常见的算法，例如排序算法、查找算法等等。它的高效性来自于使用模板实现，因此它可以在编译时期进行类型检查，并生成优化后的代码。

下面以vector为例，展示如何使用STL中的数据结构。

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(3);
    vec.push_back(2);

    cout << "vector: ";
    for (auto i:vec)
        cout << i << " ";
    cout << endl;

    return 0;
}

以上代码中定义了一个vector\ ，并向其中依次添加了1、3、2三个元素。最后使用迭代器遍历输出vector中的元素。使用STL的代码简洁、高效。

二、自定义数据结构

除了STL中提供的数据结构，我们也可以自定义数据结构来满足特定的需求。以下是实现链表的代码示例。

#include <iostream>

using namespace std;

// 链表节点的结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 链表类
class LinkedList {
public:
    LinkedList() {
        head = NULL;
    }

    // 在链表头部插入节点
    void addAtHead(int val) {
        ListNode *node = new ListNode(val);
        node->next = head;
        head = node;
    }

    // 在链表尾部插入节点
    void addAtTail(int val) {
        ListNode *node = new ListNode(val);
        if (!head) {
            head = node;
            return;
        }

        ListNode *tail = head;
        while (tail->next) {
            tail = tail->next;
        }
        tail->next = node;
    }

    // 在指定位置插入节点
    void addAtIndex(int index, int val) {
        if (index <= 0) {
            return addAtHead(val);
        }

        ListNode *node = new ListNode(val);
        ListNode *cur = head;
        while (--index && cur) {
            cur = cur->next;
        }
        if (!cur) {
            return;
        }

        node->next = cur->next;
        cur->next = node;
    }

    // 删除指定位置的节点
    void deleteAtIndex(int index) {
        if (index < 0) {
            return;
        }

        if (!index) {
            head = head->next;
            return;
        }

        ListNode *cur = head;
        while (--index && cur) {
            cur = cur->next;
        }
        if (!cur->next) {
            return;
        }

        cur->next = cur->next->next;
    }

    // 获取指定位置的节点的值
    int get(int index) {
        if (index < 0) {
            return -1;
        }

        ListNode *cur = head;
        while (index-- && cur) {
            cur = cur->next;
        }
        if (!cur) {
            return -1;
        }

        return cur->val;
    }

private:
    ListNode *head;
};

int main() {
    LinkedList list;
    list.addAtHead(1);
    list.addAtTail(3);
    list.addAtIndex(1, 2);
    list.deleteAtIndex(1);

    cout << list.get(1) << endl; // 输出3

    return 0;
}

以上代码中定义了一个LinkedList类，实现了链表节点的添加、删除、查找等操作。链表是一种基础的数据结构，在一些场景下可以提供比STL更高效的实现。

三、算法实现

在实现算法时，我们需要深入理解算法思路，并使用高效的数据结构加以实现。以下是LeetCode问题“两数相加”的代码实现。

#include <iostream>

using namespace std;

// 链表节点的结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = NULL;
        ListNode *tail = NULL;
        int carry = 0;

        while (l1 || l2 || carry) {
            int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
            carry = sum / 10;
            sum %= 10;

            if (!head) {
                head = tail = new ListNode(sum);
            } else {
                tail = tail->next = new ListNode(sum);
            }

            if (l1) {
                l1 = l1->next;
            }
            if (l2) {
                l2 = l2->next;
            }
        }

        return head;
    }
};

int main() {
    Solution solution;
    ListNode *l1 = new ListNode(2);
    l1->next = new ListNode(4);
    l1->next->next = new ListNode(3);

    ListNode *l2 = new ListNode(5);
    l2->next = new ListNode(6);
    l2->next->next = new ListNode(4);

    ListNode *result = solution.addTwoNumbers(l1, l2);

    while (result) {
        cout << result->val << " ";
        result = result->next;
    }
    cout << endl; // 输出7 0 8

    return 0;
}

以上代码实现了两个链表的相加操作。算法思路简单，但需要使用高效的链表数据结构实现。

四、总结

C++提供了丰富的数据结构和算法库，包括STL和自定义数据结构等；同时也提供了高效的模板实现，可以大大缩短开发时间。在实际开发中，要深入理解算法思路，并根据场景选择恰当的数据结构，以实现最优的代码。