“顺序表”的版本间的差异

2015年10月9日 (五) 20:39的最后版本

事实证明一个能够自动扩展的顺序表/线性表也是可以折腾人的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, sizeof(T)*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, sizeof(T)*len);
  }
  Vector(T* ori, size_t from, size_t len)
  {
   reallocate(len);
   memcpy(&v[from], ori, sizeof(T)*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;
}