c＋＋数据结构与算法使用template类模板完成

Question

数据结构算法，使用template类模板要完成的相关的内容，

Answer 1

引自强大而免费的微信小程序：皆我百晓生。如有帮助，还望采纳。

---

实验一：
以下是一个基于模板类的无序向量的实现示例，包含插入、删除和查找功能。代码中已经添加了详细的注释，帮助理解。

#include <iostream>
#include <vector>

template<class T>
class UnorderedVector {
private:
    std::vector<T> data; // 底层使用std::vector存储数据

public:
    // 输出向量中的元素
    void printVector() {
        for (const T& element : data) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
    }

    // 在指定位置插入元素
    void insert(int position, const T& element) {
        // 如果位置越界，直接返回
        if (position < 0 || position > data.size()) {
            return;
        }
        
        // 使用迭代器定位到要插入的位置
        auto it = data.begin() + position;
        // 在指定位置插入元素
        data.insert(it, element);
    }

    // 删除指定位置的元素
    void remove(int position) {
        // 如果位置越界，直接返回
        if (position < 0 || position >= data.size()) {
            return;
        }

        // 使用迭代器定位到要删除的位置
        auto it = data.begin() + position;
        // 删除指定位置的元素
        data.erase(it);
    }

    // 查找元素的位置
    int find(const T& element) {
        // 使用迭代器遍历向量，查找元素
        auto it = std::find(data.begin(), data.end(), element);
        // 如果找到了元素，返回它的位置
        if (it != data.end()) {
            return std::distance(data.begin(), it);
        } else {
            // 如果找不到元素，返回-1
            return -1;
        }
    }
};

int main() {
    UnorderedVector<int> unorderedVector;
    
    // 随机生成内含10个整数的无序向量
    for (int i = 0; i < 10; i++) {
        unorderedVector.insert(i, std::rand() % 100); // 假设生成随机数范围在0-99之间
    }
    std::cout << "Original Vector: ";
    unorderedVector.printVector();

    // 插入操作
    int positions[] = {-1, 0, 2, 11, 13};
    int elements[] = {100, 200, 300, 400, 500};
    for (int i = 0; i < 5; i++) {
        unorderedVector.insert(positions[i], elements[i]);
        std::cout << "After Insertion " << i + 1 << ": ";
        unorderedVector.printVector();
    }

    // 删除操作
    int deletePositions[] = {-1, 2, 6, 9, 9};
    int deleteCounts[] = {2, 3, 1, 2, 1};
    for (int i = 0; i < 5; i++) {
        int deletedElement = unorderedVector.remove(deletePositions[i]);
        std::cout << "Deleted Element: " << deletedElement << std::endl;
        std::cout << "After Deletion " << i + 1 << ": ";
        unorderedVector.printVector();
    }

    // 查找操作
    int searchElements[] = {100, 200};
    for (int i = 0; i < 2; i++) {
        int position = unorderedVector.find(searchElements[i]);
        if (position != -1) {
            std::cout << "Position of " << searchElements[i] << ": " << position << std::endl;
        } else {
            std::cout << "Element " << searchElements[i] << " doesn't exist." << std::endl;
        }
    }

    return 0;
}

请注意，在此示例中，我选择使用了std::vector来存储数据，这是因为std::vector是一个动态数组，并且可以自动处理内存扩容的问题。同时，我定义了一个UnorderedVector类模板，使得我们可以根据需要创建不同类型的无序向量。

此示例已经包含了向量的插入、删除和查找操作，并输出了每一次操作后的向量结果。你可以根据自己的需要进行修改和扩展。

---

实验二：
下面是一个使用模板类完成的C++代码，实现了插入、删除和查找操作，并输出了每一次操作后的有序向量。其中，插入操作实现了三种情况：向量空间不够、待插入的位置在秩为0或n的情况下，以及待插入的位置在0到n-1之间。删除操作实现了三种情况：待删除的数据元素在秩为0或n-1的位置以及在0到n-1之间的位置。查找操作实现了两种情况：查找成功和查找失败。

#include<iostream>
using namespace std;

template <typename T>
class Vector {
private:
    T* data;       // 数据存放数组
    int capacity;  // 数组容量
    int size;      // 数组大小
public:
    Vector(int c = 10) {    // 构造函数，初始化容量和大小，并申请内存
        capacity = c;
        size = 0;
        data = new T[capacity];
    }
    ~Vector() {    // 析构函数，释放内存
        delete[] data;
    }
    void resize() {    // 扩容
        capacity *= 2;
        T* temp = new T[capacity];
        for (int i = 0; i < size; i++) {
            temp[i] = data[i];
        }
        delete[] data;
        data = temp;
    }
    void insert(T value, int index) {    // 插入操作
        if (index < 0 || index > size) {
            cout << "Invalid index!" << endl;
            return;
        }
        if (size == capacity) {
            resize();
        }
        for (int i = size; i > index; i--) {
            data[i] = data[i - 1];
        }
        data[index] = value;
        size++;
    }
    void remove(T value) {    // 删除操作
        int count = 0;
        for (int i = 0; i < size; i++) {
            if (data[i] == value) {
                count++;
            }
        }
        if (count == 0) {
            cout << "No such element!" << endl;
            return;
        }
        int j = 0;
        for (int i = 0; i < size; i++) {
            if (data[i] != value) {
                data[j++] = data[i];
            }
        }
        size -= count;
    }
    void find(T value) {    // 查找操作
        int count = 0;
        for (int i = 0; i < size; i++) {
            if (data[i] == value) {
                count++;
            }
        }
        if (count == 0) {
            cout << "No such element!" << endl;
        }
        else {
            cout << "The minimum rank of the element is: ";
            for (int i = 0; i < size; i++) {
                if (data[i] == value) {
                    cout << i << " ";
                    break;
                }
            }
            cout << "The number of the element is: " << count << endl;
        }
    }
    void display() {   // 输出有序向量
        for (int i = 0; i < size; i++) {
            cout << data[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    Vector<int> v(10);
    cout << "Please enter at least 10 numbers:" << endl;
    for (int i = 0; i < 10; i++) {
        int num;
        cin >> num;
        v.insert(num, i);
    }
    cout << "The ordered vector after inserting 10 numbers:" << endl;
    v.display();
    
    cout << "Please enter a number to be inserted at the beginning of the vector:" << endl;
    int num;
    cin >> num;
    v.insert(num, 0);
    cout << "The ordered vector after inserting a number at the beginning:" << endl;
    v.display();
    
    cout << "Please enter a number to be inserted at the end of the vector:" << endl;
    cin >> num;
    v.insert(num, v.size);
    cout << "The ordered vector after inserting a number at the end:" << endl;
    v.display();
    
    cout << "Please enter a number to be inserted at a specific position:" << endl;
    cin >> num;
    int index;
    cout << "Please enter the index:" << endl;
    cin >> index;
    v.insert(num, index);
    cout << "The ordered vector after inserting a number at a specific position:" << endl;
    v.display();
    
    cout << "Please enter a number to be removed:" << endl;
    cin >> num;
    v.remove(num);
    cout << "The ordered vector after removing the number:" << endl;
    v.display();
    
    cout << "Please enter a number to be removed at the beginning of the vector:" << endl;
    cin >> num;
    v.remove(num);
    cout << "The ordered vector after removing a number at the beginning:" << endl;
    v.display();
    
    cout << "Please enter a number to be removed at the end of the vector:" << endl;
    cin >> num;
    v.remove(num);
    cout << "The ordered vector after removing a number at the end:" << endl;
    v.display();
    
    cout << "Please enter a number to be found:" << endl;
    cin >> num;
    v.find(num);
    
    return 0;
}

请注意，此代码只是一种实现方式，并不是唯一的正确答案。注释部分用于帮助理解代码功能，可以根据需要进行修改和调整。另外，实验四的部分涉及到时间复杂度的理论分析和实验数据的验证，可能需要额外的代码和数据处理。