之前在学习c语言的时候用c语言实现了动态线性表。现在再使用c++实现一下动态线性表。
相关数据结构方面就不多说了。在之前的博客里也有。下面就直接来实现吧。
这里使用指针来遍历数组，这样在算size，capacity的时候，直接用指针相减的方式就可以得到元素个数，以及容量。
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
|
#include <iostream>#include<assert.h>#include<stdio.h>#include<string.h>//用typedef定义int为存储类型，想更改直接更改这一句即可。typedef int DataType;class Vector{public: //构造函数。 Vector() { _first = new DataType[3]; _finish = _first; _endofstorage = _first + 3; } //拷贝构造 Vector(const Vector& v) { _first = new DataType[v.Size()]; memmove(_first, v._first, v.Size()*sizeof(DataType)); _finish = _first + v.Size() ; _endofstorage = _finish ; } //赋值运算符的重载 Vector& operator=(Vector v); //析构函数 ~Vector() { delete[] _first; } //顺序表的有效长度 size_t Size() const { return _finish - _first ; } //顺序表的容量 size_t Capacity() const { return _endofstorage - _first ; } //扩容顺序表 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); //打印当前顺序表 void Print();private: //指向第一个元素的指针 DataType* _first; //指向最后一个有效元素的下一个位置 DataType* _finish; //顺序表容量的下一个位置 DataType* _endofstorage;}; |
Vector.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
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
|
#include"Vector_List1.h" //赋值运算符的重载可以使用传值的方式进行 //在传值的时候默认调用了拷贝构造函数，进行了深拷贝 //而当前这个传入的v就是我们想要的赋值之后的结果 //将当前的顺序表与顺序表v一交换，就可以不用再自己实现深拷贝 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扩容， 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;} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/weixin_40331034/article/details/80002990
