C++實(shí)現(xiàn)動(dòng)態(tài)順序表（vector）

更新時(shí)間：2020年05月25日 10:44:35 作者：get_it_started

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

vector是連續(xù)存儲(chǔ)結(jié)構(gòu)，支持隨機(jī)的高效的隨機(jī)和在尾部進(jìn)行插入、刪除操作，其它位置的插入、刪除操作相對(duì)來說效率較低。

vector相當(dāng)于一個(gè)數(shù)組，但它的數(shù)組空間大小需要寫一程序來實(shí)現(xiàn)。

它的內(nèi)存分配原理大概可分為下面幾步：

1）首先分配一塊內(nèi)存空間進(jìn)行存儲(chǔ)；
2）當(dāng)所需存儲(chǔ)的數(shù)據(jù)超過分配的空間時(shí)，再重新分配一塊空間；
3）將舊元素復(fù)制到新空間；
4）釋放舊空間。

實(shí)現(xiàn)代碼如下：

vector.h

#pragma once

#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<iostream>
using namespace std;

typedef int DataType;

class Vector
{
public:
 Vector()
  :_first(NULL),
  _finish(NULL),
  _endofstorage(NULL)
 {}

 Vector(const Vector& v){
  if (v.Size() > 0){
   _first = new DataType(v.Size());
   memcpy(_first, v._first, sizeof (DataType)*v.Size());
  }
  if (_first > 0){
   _finish = _first + v.Size();
   _endofstorage = _first + v.Size();
  }
  _first = _finish = _endofstorage = NULL;
 }

 Vector& operator=(const Vector& v){
  if (this != &v){
   /*swap(_first, v._first);
   swap(_finish, v._finish);
   swap(_endofstorage, v._endofstorage);*/

   DataType* tmp = new DataType(v.Size());
   memcpy(tmp, _first, sizeof(DataType)*v.Size());
   delete _first;
   _first = tmp;
   _finish = _first + v.Size();
   _endofstorage = _first + v.Size();
  }
  return *this;
 }

 ~Vector(){
  delete[] _first;
  _first = _finish = _endofstorage = NULL;
 }

 void Print(){
  DataType* cur = _first;
  while (cur != _first){
   cout << "*cur" << endl;
   cur++;
  }
  cout << endl;
 }

 size_t Size() const{
  return _finish - _first;
 }

 size_t Capacity() const{
  return _endofstorage - _first;
 }

 void Expand(size_t n){
  if (n > Capacity()){
   DataType* tmp = new DataType(n);
   size_t size = Size();
   memcpy(tmp, _first, sizeof(DataType)*size);
   delete[] _first;
   _first = tmp;
   _finish = _first + size;
   _endofstorage = _first + n;
  }
 }

 void PushBack(DataType x){
  if (_finish == _endofstorage){
   size_t capacity = Capacity() > 0 ? Capacity() * 2 : 3;
   Expand(capacity);
   /*if (Capacity() == 0){
    Expand(3);
   }
   else{
    Expand(Capacity() * 2);
   }*/
  }
  *_finish = x;
  ++_finish;
 }

 void PopBack(){
  assert(_finish > _first);
  --_finish;
 }

 void Reserve(size_t n){
  if (n > Capacity()){
   Expand(n);
  }
 }

 void Insert(size_t pos, DataType x){
  assert(pos < Size());
  if (_finish = _endofstorage){
   size_t capacity = Capacity() > 0 ? Capacity() * 2 : 3;
   Expand(capacity);
  }
  int tmp = Size() - 1;
  while (tmp >= (int)pos){
   _first[tmp + 1] = _first[tmp];
   --tmp;
  }
  _first[pos] = x;
  ++_finish;
 }

 void Erase(size_t pos){
  assert(pos < Size());
  size_t cur = pos;
  while (cur < Size()-1){
   _first[cur] = _first[cur] + 1;
   ++cur; 
  }
  --_finish;
 }

 size_t Find(DataType x){
  DataType *cur = _first;
  while (cur != _finish){
   if (*cur == x){
    return cur - _first;
   }
   ++cur;
  }
  return -1;
 }
private:
 DataType* _first;
 DataType* _finish;
 DataType* _endofstorage;
};

test.cpp

#include"vector.h"

void Tset(){
 Vector v;
 v.PushBack(1);
 v.PushBack(2);
 v.PushBack(3);
 v.PushBack(4);
 v.PopBack();
 v.Print();

 size_t pos = v.Find(1);
 printf("pos->data:expcet 1,axtual %lu", pos);

 Vector v1;
 v1.Insert(1, 0);
 v1.Print();

 Vector v2;
 v2.Erase(3);
 v2.Print();
}

int main(){
 Tset();
 return 0;
}

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

您可能感興趣的文章: