查看顺序表的源代码 ←顺序表

[[分类::数据结构]]
事实证明一个能够自动扩展的顺序表也是可以折腾人的0u0
<pre>
#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;}</pre>