C++實現(xiàn)動態(tài)線性表

更新時間：2020年05月25日 10:14:54 作者：-yyqx-

這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)動態(tài)線性表，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下

之前在學(xué)習(xí)c語言的時候用c語言實現(xiàn)了動態(tài)線性表?，F(xiàn)在再使用c++實現(xiàn)一下動態(tài)線性表。

相關(guān)數(shù)據(jù)結(jié)構(gòu)方面就不多說了。在之前的博客里也有。下面就直接來實現(xiàn)吧。

這里使用指針來遍歷數(shù)組，這樣在算size，capacity的時候，直接用指針相減的方式就可以得到元素個數(shù)，以及容量。

Vector.h

#include <iostream>
#include<assert.h>
#include<stdio.h>
#include<string.h>
//用typedef定義int為存儲類型，想更改直接更改這一句即可。
typedef int DataType;

class Vector
{
public:
  //構(gòu)造函數(shù)。
  Vector()
  {
    _first = new DataType[3];
    _finish = _first;
    _endofstorage = _first + 3;
  }
  //拷貝構(gòu)造
  Vector(const Vector& v)
  {
    _first = new DataType[v.Size()];
    memmove(_first, v._first, v.Size()*sizeof(DataType));
    _finish = _first + v.Size() ;
    _endofstorage = _finish ;
  }
  //賦值運(yùn)算符的重載
  Vector& operator=(Vector v);
  //析構(gòu)函數(shù)
  ~Vector()
  {
    delete[] _first;
  }
  //順序表的有效長度
  size_t Size() const
  {
    return _finish - _first ;
  }
  //順序表的容量
  size_t Capacity() const
  {
    return _endofstorage - _first ;
  }
  //擴(kuò)容順序表
  void Expand(size_t n);
  //尾插
  void PushBack(DataType x);
  //截取容量
  void Reserve(size_t n);
  //尾刪
  void PopBack();
  //任意位置插入
  void Insert(size_t pos, DataType x);
  //任意位置刪除
  void Erase(size_t pos);
  //查找元素
  size_t Find(DataType x);
  //打印當(dāng)前順序表
  void Print();
private:
  //指向第一個元素的指針
  DataType* _first;
  //指向最后一個有效元素的下一個位置
  DataType* _finish;
  //順序表容量的下一個位置
  DataType* _endofstorage;
};

Vector.cpp

#include"Vector_List1.h"

  //賦值運(yùn)算符的重載可以使用傳值的方式進(jìn)行
  //在傳值的時候默認(rèn)調(diào)用了拷貝構(gòu)造函數(shù)，進(jìn)行了深拷貝
  //而當(dāng)前這個傳入的v就是我們想要的賦值之后的結(jié)果
  //將當(dāng)前的順序表與順序表v一交換，就可以不用再自己實現(xiàn)深拷貝
  Vector& Vector::operator=(Vector v)
  {
    size_t size = v.Size();
    DataType *tmp = v._first;
    v._first = _first;
    _first = tmp;
    _finish = _first + size;
    _endofstorage = _finish;
    return *this;
  }
  void Vector::Expand(size_t n)
  {
    DataType *tmp = new DataType[n];
    size_t size = Size();
    memmove(tmp, _first, Size()*sizeof(DataType));
    delete[] _first;
    _first = tmp;
    _finish = _first + size;
    _endofstorage = _first + n;
  }
  void Vector::PushBack(DataType x)
  {
    if (_finish > _endofstorage)
      Expand(2 * Capacity());
    *_finish = x;
    _finish++;
  }
  void Vector::PopBack()
  {
    assert(_first < _finish);
    _finish--;
  }
  void Vector::Insert(size_t pos, DataType x)
  {
    assert(pos<Size());
    if(_finish >= _endofstorage)
      Expand(2*Capacity());
    memmove(_first+pos+1,_first+pos,Size()-pos+1);
    *(_first+pos) = x;
  }
  void Vector::Erase(size_t pos)
  {
    assert(pos<Size());
    memmove(_first+pos,_first+pos+1,(Size()-pos-1)*sizeof(DataType));
    _finish--;
  }
  size_t Vector::Find(DataType x)
  {
    DataType *tmp = _first;
    while(tmp != _finish)
    {
      if(*tmp == x)
        return tmp-_first;
      else
        tmp++;
    }
    return -1;
  }
  //截取n個字符
  void Vector::Reserve(size_t n)
  {
    //如果n<capacity,則什么都不做，將其容量降為size與n之間的最大值
    //會改變capacity,不會改變size，若n>capacity擴(kuò)容，
    if(n<Capacity())
    {
      _endofstorage = _first + ( n > Size() ? n : Size());
      return;
    }
    else if(n>Capacity())
    {
      Expand(n);
      return;
    }
    else
      return;
  }   
  void Vector::Print()
  {
    DataType *tmp = _first;
    while (tmp != _finish)
    {
      printf("%d ", *tmp);
      tmp++;
    }
    printf("\n");
  }
int main()
{
  Vector v;
  Vector v1(v);
  v.PushBack(1);
  v.PushBack(2);
  v.PushBack(3);
  v.PushBack(4);
  v.PushBack(5);
  v.PushBack(6);
  v.Print();
  v1 = v;
  v1.Print();
  v1.Erase(2);
  v1.Print();
  size_t ret = v1.Find(3);
  printf("%lu\n",ret);
  ret = v1.Find(2);
  printf("%lu\n",ret);
  ret = v1.Find(5);
  printf("%lu\n",ret);
  v1.Reserve(3);
  v1.Print();
  return 0;
}

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: