数据结构 事实证明一个能够自动扩展的顺序表也是可以折腾人的0u0
CloudLunar
#include<iostream>#include<cstdlib>#include<cstring>#include<cmath>namespace cus { template<typename T> class Vector { T* v; size_t length; size_t cap; void rearrange(size_t logLen) { size_t newLen =( 1 << logLen); if (newLen > cap) { T* from = v; T* to = static_cast<T*>(malloc(sizeof(T)*newLen)); memcpy(to, from, length); free(v); v = to; } cap = newLen; } void reallocate(size_t n) { rearrange(1+ static_cast<int>(log2(n))); } public: Vector() :v(nullptr), length(0), cap(0) {} Vector(T* ori, size_t len) { reallocate(len); memcpy(v, ori, len); } Vector(T* ori, size_t from, size_t len) { reallocate(len); memcpy(&v[from], ori, len); } void resize(size_t n) { reallocate(n); for (int i = length;i < n;++i) { v[i] = 0; } length = n; } void push_back(const T &x) { if (length + 1 >= cap)reallocate(length + 1); v[length++] = x; } friend std::ostream& operator <<(std::ostream& os,Vector a) { for (unsigned i = 0;i < a.size();++i) { os << a[i] << " "; } return os; } inline size_t size() const { return length; } inline size_t capacity() const { return cap; } bool empty() const { return size() == 0; } T& at(size_t index) { if (index >= length)return v[0]; return v[index]; } T& operator [](size_t index) { if (index >= length)return v[0]; return v[index]; } T* find(const T &x) const { for (unsigned i = 0;i < length;++i) { if (v[i] == x) { return &v[i]; } } return nullptr; } size_t find_index(const T &x) const { auto rtn = find(x); if (rtn == nullptr)return static_cast<size_t>(-1); return x; } T* insert(const T* pos,const T& x) { if (length + 1 >= cap)reallocate(length + 1); size_t id = pos - v; if (id >= length)return nullptr; for (auto i =id;i < length;++i) { v[i+1] = v[i]; } ++length; v[id] = x; return &v[id]; } T* insert(size_t index, const T& x) { return insert(v + index, x); } T* erase(const T* pos) { size_t id = pos - v; if (id >= length)return nullptr; --length; for (unsigned i = id;i < length;++i) { v[i] = v[i+1]; } return &v[id]; } T* erase(size_t index) { return erase(v + index); } ~Vector() { if (v == nullptr)return; free(v); } };}int main(){ cus::Vector<int> s; while(1) { int a; std::cin>>a; s.push_back(a); std::cout<<s.size()<<" "<<s.capacity()<<std::endl; } std::cout<<"（1）初始化顺序表L；"<<std::endl; cus::Vector<char> L; std::cout<<"（2）依次采用尾插法插入a, b, c, d, e元素；"<<std::endl; char a, b, c, d, e; std::cin >> a >> b >> c >> d >> e; L.push_back(a); L.push_back(b); L.push_back(c); L.push_back(d); L.push_back(e); std::cout<<"（3）输出顺序表L；"<<std::endl; std::cout << L << std::endl; std::cout<<"（4）输出顺序表L长度；"<<std::endl; std::cout << "size:" << L.size() << std::endl; std::cout<<"（5）判断顺序表L是否为空；"<<std::endl; std::cout << "isEmpty:" << L.empty() << std::endl; std::cout<<"（6）输出顺序表L的第3个元素；"<<std::endl; std::cout << L << std::endl; std::cout << "3rd:" << L[2] << std::endl; std::cout<<"（7）输出元素'a'的位置；"<<std::endl; std::cout << "a is at:" << L.find_index('a') << std::endl; std::cout<<"（8）在第4个元素位置上插入'f'元素；"<<std::endl; L.insert(3, 'f'); std::cout<<"（9）输出顺序表L；"<<std::endl; std::cout << L << std::endl; std::cout<<"（10）删除L的第3个元素；"<<std::endl; L.erase(2); std::cout<<"（11）输出顺序表L；"<<std::endl; std::cout << L << std::endl; std::cout<<"（12）释放顺序表L。"<<std::endl; system("pause"); return 0;}