[数据结构与算法]1. 使用c++实现单链表(模板编程)包括析构函数尾插法和头插法

• 因为vs中,涉及到模板类的时候不能分文件编写,而是将定义和声明都写到一个文件中,这个文件约定俗成,后缀名为.hpp
• 所有用new创建的元素,都要在析构函数中,释放掉对应的内存空间,否则会造成内存泄漏
• LinkedList.hpp

#pragma once
#include<iostream>
using namespace std;

//节点类
template<class DateType>
class Node
{
public:
	Node<DateType>* next;
	DateType date;
	Node(DateType date);
	Node();
};
//单链表类
template<class DateType>
class LinkedList
{
private:
	Node<DateType>* head;
	int size = 0;
public:
	LinkedList();//构造函数
	~LinkedList();//析构函数
	bool isEmpty();//判空函数
	void PushFront(Node<DateType>* node);//头插法
	void PushBack(Node<DateType>* node);//尾插法
	void printList();//输出链表
	Node<DateType>* PopBack();//取出尾部元素
	Node<DateType>* PopFront();//取出首部元素
	int getSize();//获得长度
};


//节点的无参构造函数
template<class DateType>
Node<DateType>::Node() {}
//节点的有参构造函数
template<class DateType>
Node<DateType>::Node(DateType date)
{
	this->date = date;
}


//链表的构造函数
template<class DateType>
LinkedList<DateType>::LinkedList()
{
	head = new Node<DateType>();
	head->next = NULL;
	head->date = 0;
}
//链表的析构函数,只要是new出来的元素,都要清除内存空间
template<class DateType>
LinkedList<DateType>::~LinkedList()
{
	cout << "------------析构函数调用------------" << endl;
	Node<DateType>* temp = head->next;
	while (temp != NULL)
	{
		Node<DateType>* del = temp;
		temp = temp->next;
		cout << del->date << "内存被释放" << endl;
		delete del;
	}
	delete head;
	cout << "头结点内存被释放" << endl;
	cout << "------------析构函数完成------------" << endl;
}
//判空
template<class DateType>
bool LinkedList<DateType>::isEmpty()
{
	return this->size == 0 ? true : false;
}
//头插法
template<class DateType>
void LinkedList<DateType>::PushFront(Node<DateType>* node)
{
	node->next = head->next;
	head->next = node;
	size++;
}
//尾插法
template<class DateType>
void LinkedList<DateType>::PushBack(Node<DateType>* node)
{
	Node<DateType>* temp = head;
	while (temp->next != NULL)
	{
		temp = temp->next;
	}
	temp->next = node;
	size++;
}
//遍历链表
template<class DateType>
void LinkedList<DateType>::printList()
{
	Node<DateType>* temp = head;
	for (int i = 0; i < size; i++)
	{
		cout << i + 1 << " : " << temp->next->date << endl;
		temp = temp->next;
	}
}
template<class DateType>
Node<DateType>* LinkedList<DateType>::PopBack()
{
	if (!this->isEmpty())
	{
		Node<DateType>* temp = head;
		for (int i = 0; i < this->size - 1; i++)
		{
			temp = temp->next;
		}
		Node<DateType>* temp2 = temp->next;
		temp->next = NULL;
		size--;
		return temp2;
	}
	else
	{
		cout << "链表为空" << endl;
		return 0;
	}
}
template<class DateType>
Node<DateType>* LinkedList<DateType>::PopFront()
{
	if (!this->isEmpty())
	{
		Node<DateType>* node = head->next;
		head->next = head->next->next;
		size--;//一定要记住改变size
		return node;
	}
	else
	{
		cout << "链表是空的" << endl;
		return 0;
	}
	
}
template<class DateType>
int LinkedList<DateType>::getSize()
{
	return size;
}

• 主方法 main.cpp

#include "LinkedList.hpp"
using namespace std;
int main()
{
	LinkedList<int> list;
	list.PushFront(new Node<int>(1));
	list.PushFront(new Node<int>(2));
	list.PushFront(new Node<int>(3));
	list.PushFront(new Node<int>(4));
	list.PushFront(new Node<int>(5));
	cout << list.getSize() << endl;
	cout << list.isEmpty() << endl;
	list.PushBack(new Node<int>(6));
	list.PushBack(new Node<int>(7));
	list.PushBack(new Node<int>(8));
	list.PushBack(new Node<int>(9));
	list.PushBack(new Node<int>(10));
	Node<int>* node = list.PopFront();
	cout << "首元素是 : " << node->date << endl;
	node = list.PopBack();
	cout << "尾元素是 : " << node->date << endl;
 	list.printList();
	
	return 0;
}