小 (换行) |
小 (修改细节) |
||
第2行: | 第2行: | ||
事实证明一个能够自动扩展的顺序表也是可以折腾人的0u0 | 事实证明一个能够自动扩展的顺序表也是可以折腾人的0u0 | ||
<pre> | <pre> | ||
+ | //编译时请加入参数 --std=c++11 | ||
#include<iostream> | #include<iostream> | ||
#include<cstdlib> | #include<cstdlib> | ||
第142行: | 第143行: | ||
int main() | int main() | ||
{ | { | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
std::cout<<"(1)初始化顺序表L;"<<std::endl; | std::cout<<"(1)初始化顺序表L;"<<std::endl; | ||
cus::Vector<char> L; | cus::Vector<char> L; |
事实证明一个能够自动扩展的顺序表也是可以折腾人的0u0
//编译时请加入参数 --std=c++11 #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() { 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; }