数据结构c++实现——线性表

通过vector实现一个简单的线性表

#include <iostream>
#include <cstring>

template <typename Type> class Vector {
private:
    int size, length;
    Type *data;
public:
    Vector(int input_size) {
        size = input_size;
        length = 0;
        data = new Type[size];  // 指向一段连续的Type类型的空间
    }
    ~Vector() {
        delete[] data;
    }
};
int main() {
    Vector<int> a(100);
    return 0;
}

实现插入元素的函数:

bool insert(int loc, Type value);

#include <iostream>
#include <cstring>
using std::cout;
using std::endl;
template <typename Type> class Vector {
private:
    int size, length;
    Type *data;
public:
    Vector(int input_size) {
        size = input_size;
        length = 0;
        data = new Type[size];
    }
    ~Vector() {
        delete[] data;
    }
    bool insert(int loc, Type value) {  // 实现插入元素到指定位置的函数
        if (loc < 0 || loc > length) {
            return false;
        }
        if (length >= size) {
            return false;
        }
        for (int i = length; i > loc; --i) {
            data[i] = data[i - 1];
        }
        data[loc] = value;
        length++;
        return true;
    }
};
int main() {
    Vector<int> a(2);
    cout << a.insert(1, 0) << endl;
    cout << a.insert(0, 1) << endl;
    cout << a.insert(2, 1) << endl;
    cout << a.insert(1, 2) << endl;
    cout << a.insert(0, 3) << endl;
    return 0;
}

添加扩容函数 : void expand();

#include <iostream>
#include <cstring>
using std::cout;
using std::endl;
template <typename Type> class Vector {
private:
    int size, length;
    Type *data;
public:
    Vector(int input_size) {
        size = input_size;
        length = 0;
        data = new Type[size];
    }
    ~Vector() {
        delete[] data;
    }
    bool insert(int loc, Type value) {
        if (loc < 0 || loc > length) {
            return false;
        }
        if (length >= size) {
            // return false;
            expand();  // 调用扩容函数
        }
        for (int i = length; i > loc; --i) {
            data[i] = data[i - 1];
        }
        data[loc] = value;
        length++;
        return true;
    }
    // 请在下面实现扩容方法 expand
    void expand() {
        Type * old_data = data;  // 指向data空间首地址
        size = size * 2;
        data = new Type[size];
        for(int i=0; i < length; i++) {
            data[i] = old_data[i];
        }
        delete[] old_data;

    }
};
int main() {
    Vector<int> a(2);
    cout << a.insert(1, 0) << endl;
    cout << a.insert(0, 1) << endl;
    cout << a.insert(2, 1) << endl;
    cout << a.insert(1, 2) << endl;
    cout << a.insert(0, 3) << endl;
    return 0;
}

注意g++的编译语法是:

g++ -o [编译后的执行文件][空格][源文件]

原文链接: https://www.cnblogs.com/huangZ-H/p/12247780.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/326370

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

数据结构c++实现——线性表

相关推荐