C++封装顺序表和带头结点的双向循环链表

C语言中写过了顺序表和带头结点的双向循环链表，这里就不对具体的逻辑进行探究了。

顺序表：

Vector.h:

#ifndef __VECTOR_H__
#define __VECTOR_H__

#define NULL 0

typedef int DataType;

class Vector
{
public:
	Vector()//在构造函数中，到底要不要开辟内存空间？
		//这里必须开辟，全部置空，不正确，在判空，开辟内存时出错
		:_first(new DataType[3])//NULL
		, _finish(_first)		//NULL
		, _endofstorage(_first+3)//NULL
	{}
	Vector(const Vector& v);
	//Vector& operator=(const Vector& v);
	Vector& operator=(Vector v);            //这里进行传值方便调用构造函数，写出现代写法
	~Vector();
	size_t Size() const;			//最好将size和capacity函数 定义为内联函数
	size_t Capacity()const;
	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;              //记录容量
};

void TestVector();

#endif	//__VECTOR_H__

Vector.cpp:

#define _CRT_SECURE_NO_WARNINGS 1
#include <string.h>
#include <assert.h>
#include <iostream>

using namespace std;

#include "Vector.h"

Vector::Vector(const Vector& v)
{
	_first = v._first;
	_finish = v._finish;
	_endofstorage = _endofstorage;
}

//Vector& Vector::operator=(const Vector& v)	//不考虑写时拷贝
//{
//	if (_first != v._first)
//	{
//		//先处理this
//		delete[]_first;
//		_first = new DataType[v.Size()];	//这里开辟size个防止内存的浪费		
//		//再赋值
//		memcpy(_first, v._first, sizeof(DataType)* Size());
//		_finish = v._finish;
//		_endofstorage = v._finish;
//	}
//	return *this;
//}

Vector& Vector::operator=(Vector v)	//现代写法
{	
	if (_first != v._first)
	{
		swap(_first, v._first);
		swap(_finish,  v._finish);
		swap(_endofstorage, v._endofstorage);
	}
	return *this;
}

size_t Vector::Size()const
{
	return _finish - _first;
}
size_t Vector::Capacity()const
{
	return _endofstorage - _first;
}
void Vector::Expand(size_t n)
{
	int size = Size();
	DataType *tmp = new DataType[n];
	
	memcpy(tmp, _first, sizeof(DataType)* Size());
	delete[]_first;
	_first = tmp;
	_finish = _first + size;
	_endofstorage = _first + n;
}
void Vector::PushBack(DataType x)
{
	if (_finish == _endofstorage)
	{
		Expand(Capacity() * 2);
	}
	*_finish = x;
	_finish++;
}
void Vector::Reserve(size_t n)
{
	if (n > Capacity())
	{
		Expand(n);
	}
}

void Vector::PopBack()
{
	if (_finish == _first)//顺序表空
	{
		return;
	}
	else
	{
		_finish--;
	}
}

void Vector::Insert(size_t pos, DataType x)
{
	assert(_first + pos - 1<= _finish);
	//增容？
	if (_finish == _endofstorage)
	{
		Expand(Capacity() * 2);
	}
	//搬移
	int i = 0;
	for (i = Size(); i >= (int)pos - 1; --i)     //这里应注意pos是size_t类型，需要强转
	{
		*(_first + i + 1) = *(_first + i);     //first[i+1]  = first[i]
	}
	*(_first + pos - 1) = x;
	_finish++;
}

void Vector::Erase(size_t pos)
{
	assert(_first + pos - 1 <= _finish);
	if (_finish == _first)
	{
		return;
	}
	size_t i = 0;
	for (i = pos - 1; i < Size(); i++)
	{
		*(_first + i) = *(_first + i + 1);
	}
	_finish--;
}

size_t Vector::Find(DataType x)
{
	size_t i = 0;
	for (; i < Size(); i++)
	{
		if (*(_first + i) == x)
		{
			return i;
		}
	}
	return -1;
}

Vector::~Vector()
{
	delete[]_first;
	_first = _finish = _endofstorage = NULL;     //析构完成，指针置空
}

void Vector::Print()
{
	size_t i = 0;
	for (; i < Size(); i++)
	{
		cout << *(_first + i)<<" ";
	}
}


void TestVector()
{
	Vector v;
	v.PushBack(1);       //起始位置下标为1
	v.PushBack(2);
	v.PushBack(3);
	v.PushBack(4);
	v.PopBack();
	v.Insert(1, 0);
	v.Print();
	cout << endl;
	cout << "size = " << v.Size() << endl;
	v.Erase(1);
	v.Print();
	cout << endl;
	cout<<"size = "<<v.Size()<<endl;

	cout << v.Find(2) + 1 << endl;
}

SList.h:

#ifndef __SLIST__H_
#define __SLIST__H_

typedef int DataType;
#define NULL 0

struct ListNode
{
	ListNode* _next;
	ListNode* _prev;
	DataType _data;

	ListNode(DataType x)                //在结构体中的构造函数对节点进行初始化
		:_data(x)
		, _next(NULL)
		, _prev(NULL)
	{}
};

class List
{
	typedef ListNode Node;
public:
	List()
		:_head(new Node(DataType()))    //对头结点进行初始化
	{
		_head->_next = _head;
		_head->_prev = _head;
	}

	List(const List& l);
	List& operator=(List l);
	~List();

	void PushBack(DataType x);
	void PushFront(DataType x);
	void PopBack();
	void PopFront();
	Node* Find(DataType x);
	void Insert(Node* pos, DataType x);
	void Erase(Node* pos);

	void Print();
private:
	Node* _head;
};

void TestList();

#endif //__SLIST__H_

SList.cpp:

#define _CRT_SECURE_NO_WARNINGS 1
#include <assert.h>
#include <iostream>

#include "SList.h"

using namespace std;

List::List(const List& l)
:_head(new ListNode(DataType()))
{
	_head->_next = _head;
	_head->_prev = _head;

	Node* pCur = l._head->_next;
	while (pCur != l._head)
	{
		PushBack(pCur->_data);
		pCur = pCur->_next;
	}
}

List& List::operator=(List l)
{
	swap(_head, l._head);
	
	return *this;
}

void List::PushBack(DataType x)
{
	//Node *Tail = _head->_prev;
	//Node *NewNode = new ListNode(DataType(x));
	//
	//NewNode->_prev = Tail;
	//NewNode->_next = _head;
	//_head->_prev = NewNode;;
	//Tail->_next = NewNode;
	Insert(_head, x);
}
void List::PushFront(DataType x)
{
	Insert(_head->_next, x);
}

void List::PopBack()
{
	Erase(_head->_prev);
}

void List::PopFront()
{
	Erase(_head->_next);
}



void List::Insert(Node* pos, DataType x)
{
	//assert(pos);
	Node* NewNode = new ListNode(DataType(x));
	Node* prev = pos->_prev;

	//prev  newnode  pos
	NewNode->_next = pos;
	NewNode->_prev = prev;
	prev->_next = NewNode;
	pos->_prev = NewNode;
}

void List::Erase(Node* pos)
{
	assert(pos != _head);
	//prev  pos  pos->next
	Node* prev = pos->_prev;
	Node* next = pos->_next;
	
	delete pos;
	prev->_next = next;
	next->_prev = prev;
}

List::Node* List::Find(DataType x)
{
	Node* pCur = _head->_next;
	while (pCur != _head)
	{
		if (x == pCur->_data)
		{
			return pCur;
		}
		pCur = pCur->_next;
	}
	return NULL;
}

void List::Print()
{
	Node* pCur = _head->_next;
	while (pCur != _head)
	{
		cout << pCur->_data << " ";
		pCur = pCur->_next;
	}
	cout << endl;
}

List:: ~List()
{
	Node* pCur = _head->_next;
	while (pCur != _head)
	{
		Node *next = pCur->_next;
		delete pCur;
		pCur = next;
	}
	delete _head;
	_head = NULL;
}


void TestList()
{
	List l;
	l.PushBack(1);
	l.PushBack(2);
	l.PushBack(3);
	l.PushBack(4);
	l.PushBack(5);
	l.PopFront();
	l.Print();
}