之前在学习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