线性表和带头结点的双向循环链表

程序员文章站 2024-03-21 19:29:04

...

1.0 带头节点的双链表的操作的函数：

Node(const DataType& data = DataType()) 
: _pNext(NULL) 
, _pPre(NULL) 
, _data(data) 
{} 
}; 


class List 
{ 
public: 
List() 
: _pHead(NULL) 
{} 

List(const DataType* array, size_t size)； 
List(const List& L); 
List& operator=(const List& s); 
~List()； 

void PushBack(const DataType& data)； 
void PopBack()； 
void PushFront(const DataType& data); 
void PopFront(); 

// 返回插入的新节点 
Node* Insert(Node* pos, DataType data); 
// 返回删除节点的下一个位置	
Node* Erase(Node* pos); 
size_t Size()const; 
bool Empty()const；

带头节点的双链表的操作：

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <string.h>
#include <assert.h>
using namespace std;
//2. 以C++的方式实现双向循环链表
typedef int DataType;
struct Node
{
	struct Node* _pNext;
	struct Node* _pPre;
	DataType _data;

	Node(const DataType& data = DataType())
		: _pNext(NULL)
		, _pPre(NULL)
		, _data(data)
	{}
};
class List
{
public:
	List()
		:_pHead(NULL)
	{}
	List(const DataType* array, size_t size)
	{
		for (size_t i = 0; i < size; i++)
			PushBack(array[i]);
	}
    List(const List& list)//拷贝构造函数
	{
			if (list._pHead == NULL)
				return;
			else
			{
				Node* pcur = list._pHead->_pNext;
				while (pcur!= list._pHead)
				{
					this->PushBack(pcur->_data);
					pcur = pcur->_pNext;
				}
			}
		}
	friend ostream& operator<<(ostream& _cout, const List& list)//输出运算符的重载
	{
		Node* pcur = list._pHead->_pNext;
		if (pcur == NULL)//空链表
			_cout << "空链表";
		else
		{
			while (pcur != list._pHead)
			{
				_cout << pcur->_data << "-";
				pcur = pcur->_pNext;
			}
			_cout << "循环";
		}
		return _cout;
	}
	List& operator=(const List& s)
	{
		if (this != NULL)
			this->~List();
		if (this != &s)
		{
			Node* pcur = s._pHead->_pNext;
			while (pcur != s._pHead)
			{
				this->PushBack(pcur->_data);
				pcur = pcur->_pNext;
			}
		}
		return *this;
	}
	~List()
	{
		Node* pcur = _pHead;
		if (pcur == NULL)//空
			return;
		_pHead->_pPre->_pNext = NULL;//将循环链表的尾节点next置空
		Node* temp = NULL;
		while (pcur)
		{
			temp = pcur;
			pcur = pcur->_pNext;
			delete temp;
		}
		_pHead = NULL;
	}
	void PushBack(const DataType data)//尾插
	{
		if (NULL == _pHead)//空链表
		{
			_pHead = new Node;
			Node* newnode = new Node(data);
			_pHead->_pNext = newnode;
			newnode->_pPre = _pHead;
			_pHead->_pPre = newnode;
			newnode->_pNext = _pHead;
		}
		else 
		{
			Node* pcur = _pHead;
			pcur = pcur->_pPre;  //尾节点
			Node* pNewNode = new Node(data);//创建节点
			pcur->_pNext = pNewNode;
			pNewNode->_pPre = pcur;
			pNewNode->_pNext = _pHead;
			_pHead->_pPre = pNewNode;
		}
	}
	void PopBack()
	{
		if (NULL == _pHead)
			return;
		else
		{
			Node* _pTail = _pHead->_pPre;
			_pTail->_pPre->_pNext = _pHead;
			_pHead->_pPre = _pTail->_pPre;
			delete _pTail;
			_pTail = NULL;
		}
	}
	void PushFront(const DataType& data)
	{
		if (NULL == _pHead)//空链表
		{
			_pHead = new Node;
			Node* newnode = new Node(data);
			_pHead->_pNext = newnode;
			newnode->_pPre = _pHead;
			_pHead->_pPre = newnode;
			newnode->_pNext = _pHead;
		}
		else
		{
			Node*newnode = new Node(data);
			_pHead->_pNext->_pPre = newnode;
			newnode->_pNext = _pHead->_pNext;
			_pHead->_pNext = newnode;
			newnode->_pPre = _pHead;
		}
	}
	void PopFront()
	{
		if (NULL == _pHead)
			return;
		else
		{
			Node* _pDel=_pHead->_pNext;
			_pDel->_pNext->_pPre = _pHead;
			_pHead->_pNext = _pDel->_pNext;
			delete _pDel;
			_pDel = NULL;
		}
	}
	Node* Find(DataType data)//查找，没找到返回空
	{
		Node* pcur = _pHead->_pNext;
		if (pcur == NULL)
			return NULL;
		while (pcur!= _pHead)
		{
			if (pcur->_data == data)
				return pcur;
			pcur = pcur->_pNext;
		}
		return NULL;
	}
	// 返回插入的新节点 
	Node* Insert(Node* pos, DataType data)  //在pos前插入
	{
	        assert(pos);
			Node* newnode = new Node(data);
			pos->_pPre->_pNext = newnode;
			newnode->_pPre=pos->_pPre;
			newnode->_pNext = pos;
			pos->_pPre = newnode;
			return newnode;
	}
	// 返回删除节点的下一个位置	;
	Node* Erase(Node* pos)
	{
		   assert(pos);
		   Node* temp = pos->_pNext;
			Node* pre=pos->_pPre;
			pos->_pNext->_pPre = pre;
			pre->_pNext = pos->_pNext;
			delete pos;
			pos = NULL;
			return temp;
	}
	size_t Size()const
	{
		size_t count = 0;
		Node* _pCur = _pHead->_pNext;
		while (_pCur != _pHead)
		{
			count++;
			_pCur = _pCur->_pNext;
		}
		return count;
	}
	bool Empty()const
	{
		return NULL == _pHead;
	}
private:
	Node* _pHead;
};
void TestList1()
{
	int a[] = { 1, 2, 3, 4, 5, 6 };
	List l(a, 6);
	l.PushBack(7);
	l.PopBack();
	l.PushFront(0);
	l.PopFront();
	l.Insert(l.Find(6)->_pNext, 7);
	l.Erase(l.Find(7));
	cout << l.Size() << endl;
	cout <<l<< endl;
}
int main()
{
	TestList1();
	system("pause");
	return 0;
}

结果：

线性表和带头结点的双向循环链表

2.0 C++封装的顺序表的具体函数：

SeqList()
: _pData(new DataType[3])
, _capacity(3)
, _size(0)
{}

SeqList(DataType* array, size_t size)
: _pData(new DataType[size])
, _capacity(size)
, _size(size)
{
	for (size_t i = 0; i < size; ++i)
		_pData[i] = array[i];
}

SeqList(const SeqList& s);
SeqList& operator=(const SeqList& s);
~SeqList();
void PushBack(const DataType& data);
void PopBack();
// 参数检测 
void Insert(size_t pos, DataType data);
void Erase(size_t pos);
size_t Size()const;
size_t Capacity()const;
bool Empty()const;
// 将顺序表中的元素改成newSize 
void ReSize(size_t newSize, DataType data = DataType());
DataType& operator[](size_t index);
const DataType& operator[](size_t index)const;
// 获取顺序表中第一个元素 
DataType& Front();
const DataType& Front()const;
// 获取顺序表中最后一个元素 
DataType& Back();
const DataType& Back()const;
void Clear()
{ 
	_size = 0;
}
void CheckCapacity();
friend ostream& operator<<(ostream& _cout, const SeqList& s);

C++封装的顺序表方法的内容：

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <string.h>
#include <assert.h>
using namespace std;
typedef int DataType;
class SeqList
{
public:
	SeqList()
		: _pData(new DataType[3])
		, _capacity(3)
		, _size(0)
	{}

	SeqList(DataType* array, size_t size)
		: _pData(new DataType[size])
		, _capacity(size)
		, _size(size)
	{
		for (size_t i = 0; i < size; ++i)
			_pData[i] = array[i];
	}

	SeqList(const SeqList& s){
		_pData = new DataType[s._size];
		_capacity = s._size;
		_size = s._size;

		for (size_t i = 0; i < s._size; ++i)
			_pData[i] = s._pData[i];
	}
	SeqList& operator=(const SeqList& s){
		for (size_t i = 0; i < _size; i++)
			_pData[i] = s._pData[i];
	}
	~SeqList(){
		if (_pData)
		{
			delete[] _pData;
			_pData = NULL;
			_capacity = 0;
			_size = 0;
		}
	}
	void PushBack(const DataType& data){
		CheckCapacity();
		_pData[_size++] = data;
	}
	void ReSize(size_t newSize, DataType data = DataType())
	{
		if (newSize > _size)
		{
			CheckCapacity();
			size_t i = 0;
			for (i = _size; i<newSize; i++)
			{
				_pData[i] = data;
			}
		}
		else
		{
			_size = newSize;
		}
	}
	void PopBack(){
		assert(_size);
		--_size;
	}
	void Insert(size_t pos, DataType data){
		if (pos > _size)
			return;
		CheckCapacity();
		for (int i = _size - 1; i >= pos; --i)
			_pData[i + 1] = _pData[i];

		_pData[pos] = data;
		++_size;
	}
	void Erase(size_t pos){
		if (pos >= _size)
			return;
		// 搬移元素
		for (size_t i = pos; i < _size - 1; ++i)
			_pData[i] = _pData[i + 1];
		--_size;
	}
	size_t Size()const{
		return _size;
	}
	size_t Capacity()const{
		return _capacity;
	}
	bool Empty()const
	{
		return 0 == _size;
	}
	DataType& operator[](size_t index)
	{
		assert(index < _size);
		return _pData[index];
	}
	const DataType& operator[](size_t index)const{
		assert(index < _size);
		return _pData[index];
	}
	DataType& Front(){
		return _pData[0];
	}
	const DataType& Front()const{
		return _pData[0];
	}
	DataType& Back(){
		return _pData[_size - 1];
	}
	const DataType& Back()const{
		return _pData[_size - 1];
	}
	void CheckCapacity(){
		if (_size==_capacity)
		{
			DataType* temp = new DataType[2 * _size + 3];
			if (_pData)
			{
				for (size_t i = 0; i <_size; ++i)//效率低
					temp[i] = _pData[i];
				delete[] _pData;
			}
			_pData = temp;
			_size=2 * _size + 3;
			_capacity = _size;
		}
	}
	friend ostream& operator<<(ostream& _cout, const SeqList& l);
    void Clear(){
			_size = 0;
    }
private:
	DataType* _pData;
	size_t _capacity;    // 最大元素的个数
	size_t _size;        // 有效元素的个数
};
ostream& operator<<(ostream& _cout, const SeqList& l)
{
	size_t count=0;
	for (size_t i = 0; i < l._size; i++)
	{
		cout << l._pData[i] << "-";
		count++;
		if(count % 5 == 0)  //每行输出五个元素
		{
			cout << endl;
		}
	}
	_cout <<" _capacity:" << l._capacity << " _size:  " << l._size;
	return _cout;
}
void TestSeqList()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	SeqList s1(array, sizeof(array) / sizeof(array[0]));
	SeqList s2(s1);
	s2.ReSize(15, 2);
	cout <<s2<< endl;
}
int main()
{
	TestSeqList();
	system("pause");
	return 0;
}

结果：

线性表和带头结点的双向循环链表

上一篇： Hibernate Jar/Doc下载地址博客分类： db hibernatejardocdownload

下一篇： Java学习笔记——多态

线性表和带头结点的双向循环链表

带头双向循环链表的增删查改

带头循环双向链表的增删查改

C语言--带头双向循环链表的基本操作实现

数据结构(带头结点的双向循环链表的相关操作)

用模板实现顺序表和带头结点的双向循环链表

数据结构——带头结点的双向链表

数据结构：带头结点双向链表的实现（考研）

C语言带有头结点的循环双链表的实现和相关操作。

带头结点循环双向链表 c语言实现

数据结构之带头结点带环的双向链表

线性表和带头结点的双向循环链表

带头双向循环链表的增删查改

带头循环双向链表的增删查改

C语言--带头双向循环链表的基本操作实现

数据结构(带头结点的双向循环链表的相关操作)

用模板实现顺序表和带头结点的双向循环链表

数据结构——带头结点的双向链表

数据结构：带头结点双向链表的实现（考研）

C语言 带有头结点的循环双链表的实现和相关操作。

带头结点循环双向链表 c语言实现

数据结构之带头结点带环的双向链表

C语言带有头结点的循环双链表的实现和相关操作。