c语言动态顺序表（c++顺序表的实现）

vector是连续存储结构，支持随机的高效的随机和在尾部进行插入、删除操作，其它位置的插入、删除操作相对来说效率较低。

vector相当于一个数组，但它的数组空间大小需要写一程序来实现。

它的内存分配原理大概可分为下面几步：

1）首先分配一块内存空间进行存储；
2）当所需存储的数据超过分配的空间时，再重新分配一块空间；
3）将旧元素复制到新空间；
4）释放旧空间。

c语言动态顺序表（c++顺序表的实现）

实现代码如下：

vector.h

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 #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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #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; }