C++实现双向链表

实现双向链表的基本 *** 作：创建列表功能，插入功能，删除功能，顺序输出，逆序输出，判断回文串功能
第一个代码是问题代码，要想直接看正确的请翻至最下

#include  
#include
using namespace std;
class ListNode
{
public:
	char data;
	ListNode* prev;
	ListNode* next;
	ListNode()
	{
		data = '0';
		prev = nullptr;
		next = nullptr;
	}
	ListNode(int x)
	{
		data = x;
		prev = nullptr;
		next = nullptr;
	}
};
class DoubleLinkedList
{
public:
	void InsertElement(int, char);
	void CreatList(const char*);
	void SequentialPrint(void);
	void ReversePrint(void);
	void DeleteElement(int);
	DoubleLinkedList()
	{
		head = new ListNode;
		tail = new ListNode;
		length = 0;
		head->data = '0';
		head->next = tail;
		head->prev = nullptr;
		tail->data = '0';
		tail->prev = head;
		tail->next = nullptr;
	}
	ListNode* head;
	ListNode* tail;
private:
	int length = 0;
};
void DoubleLinkedList::InsertElement(int position, char element)
{
	if (position <1 || position>length + 1)
	{
		return;
	}
	ListNode* p = head;
	for (int i = 1; i < position; i++)
	{
		p = p->next;
	}
	ListNode* q = p->next;
	ListNode* tmp = new ListNode(element);
	length++;
	tmp->prev = p;
	p->next = tmp;
	tmp->next = q;
	q->prev = tmp;
}
void DoubleLinkedList::CreatList(const char* str)
{
	int x_len = strlen(str);
	for (int i = 0; i < x_len; i++)
	{
		this->InsertElement(i + 1, str[i]);
	}
}
void DoubleLinkedList::SequentialPrint()
{
	if (length == 0)
	{
		return;
	}
	ListNode* p = head->next;
	while (p->next)
	{
		cout << p->data;
		p = p->next;
	}
	cout << endl;
}
void DoubleLinkedList::ReversePrint()
{
	if (length == 0)
	{
		return;
	}
	ListNode* p = tail->prev;
	while (p->prev)
	{
		cout << p->data;
		p = p->prev;
	}
	cout << endl;
}
void DoubleLinkedList::DeleteElement(int location)
{
	if (location > length || location < 1)
	{
		return;
	}
	ListNode* p = head;
	if (location == length)
	{
		for (int i = 1; i < location; i++)
		{
			p = p->next;
		}
		ListNode* q = p->next;
		delete q;
		length--;
		p->next = this->tail;
		this->tail = p;
	}
	else
	{
		for (int i = 1; i < location; i++)
		{
			p = p->next;
		}
		ListNode* q1 = p->next;
		ListNode* q2 = p->next->next;
		delete q1;
		length--;
		p->next = q2;
		q2->prev = p;
	}
}
bool Judge_HUIWEN(DoubleLinkedList x)
{
	ListNode* p = x.head;
	ListNode* q = x.tail;
	while (true)
	{
		if ((p == q) || (p->prev == q))return 1;
		if (p->data != q->data)return 0;
		p = p->next;
		q = q->prev;
	}
}
int main() {
	DoubleLinkedList obj;
	char temp[105] = {};
	cin >> temp;
	obj.CreatList(temp);
	if (Judge_HUIWEN(obj))
	{
		obj.SequentialPrint();
		cout << "True" << endl;
	}
	else
	{
		obj.SequentialPrint();
		cout << "False" << endl;
	}
	system("pause");
	return 0;
}

主函数测试：

int main() {
	DoubleLinkedList obj;
	char temp[105] = {};
	cin >> temp;
	obj.CreatList(temp);
	if (Judge_HUIWEN(obj))
	{
		obj.SequentialPrint();
		cout << "True" << endl;
	}
	else
	{
		obj.SequentialPrint();
		cout << "False" << endl;
	}
	while (true)
	{
		int x;
		cin >> x;
		obj.DeleteElement(x);
		obj.SequentialPrint();
	}
	system("pause");
	return 0;
}

输出结果：

这串代码看似没有问题，实则隐含着严重的内存泄漏问题，聪明的你不难发现，ListNode动态分配出的内存在析构函数中没有回收！于是我慌张的在DoubleLinkedList类中添加了析构函数

~DoubleLinkedList()
	{
		ListNode* p = nullptr;
		while (head)
		{
			p = head;
			head = head->next;
			delete p;
		};
	}

但是在编译的时候却一直报错：

这就又回到了我们老生常谈的问题：深拷贝与浅拷贝
程序中判断回文函数bool Judge_HUIWEN(DoubleLinkedList x) 写在类外，DoubleLinkedList x在传参过程中触发浅拷贝，其实这倒没有太大问题，问题是当该函数结束时，临时变量x会背析构函数析构掉head和tail，这导致在下一次访问时没有办法找到head和tail，引发问题
解决方案：
1.把判断回文函数写在类内
2.重写拷贝构造函数，进行深拷贝
由于本人较懒，且方法2的实现在我之前的文章中讲过，故采用第一种方案

下面是正确的代码

#include  
#include
using namespace std;
class ListNode
{
public:
	char data;
	ListNode* prev;
	ListNode* next;
	ListNode()
	{
		data = '0';
		prev = nullptr;
		next = nullptr;
	}
	ListNode(int x)
	{
		data = x;
		prev = nullptr;
		next = nullptr;
	}
};
class DoubleLinkedList
{
public:
	void InsertElement(int, char);//插入功能
	void CreatList(const char*);//创建列表功能
	void SequentialPrint(void);//顺序输出
	void ReversePrint(void);//逆序输出
	void DeleteElement(int);//删除功能
	bool Judge_HUIWEN(void);//判断回文
	DoubleLinkedList()
	{
		head = new ListNode;
		tail = new ListNode;
		length = 0;
		head->data = '0';
		head->next = tail;
		head->prev = nullptr;
		tail->data = '0';
		tail->prev = head;
		tail->next = nullptr;
	}
	~DoubleLinkedList()
	{
		ListNode* p = nullptr;
		while (head)
		{
			p = head;
			head = head->next;
			delete p;
		};
	}
	ListNode* head;
	ListNode* tail;
private:
	int length = 0;
};
void DoubleLinkedList::InsertElement(int position, char element)
{
	if (position <1 || position>length + 1)
	{
		return;
	}
	ListNode* p = head;
	for (int i = 1; i < position; i++)
	{
		p = p->next;
	}
	ListNode* q = p->next;
	ListNode* tmp = new ListNode(element);
	length++;
	tmp->prev = p;
	p->next = tmp;
	tmp->next = q;
	q->prev = tmp;
}
void DoubleLinkedList::CreatList(const char* str)
{
	int x_len = strlen(str);
	for (int i = 0; i < x_len; i++)
	{
		this->InsertElement(i + 1, str[i]);
	}
}
void DoubleLinkedList::SequentialPrint()
{
	if (length == 0)
	{
		return;
	}
	ListNode* p = head->next;
	while (p->next)
	{
		cout << p->data;
		p = p->next;
	}
	cout << endl;
}
void DoubleLinkedList::ReversePrint()
{
	if (length == 0)
	{
		return;
	}
	ListNode* p = tail->prev;
	while (p->prev)
	{
		cout << p->data;
		p = p->prev;
	}
	cout << endl;
}
void DoubleLinkedList::DeleteElement(int location)
{
	if (location > length || location < 1)
	{
		return;
	}
	ListNode* p = head;
	if (location == length)
	{
		for (int i = 1; i < location; i++)
		{
			p = p->next;
		}
		ListNode* q = p->next;
		delete q;
		length--;
		p->next = this->tail;
		this->tail = p;
	}
	else
	{
		for (int i = 1; i < location; i++)
		{
			p = p->next;
		}
		ListNode* q1 = p->next;
		ListNode* q2 = p->next->next;
		delete q1;
		length--;
		p->next = q2;
		q2->prev = p;
	}
}
bool DoubleLinkedList::Judge_HUIWEN()
{
	ListNode* p = head;
	ListNode* q = tail;
	while (true)
	{
		if ((p == q) || (p->prev == q))return 1;
		if (p->data != q->data)return 0;
		p = p->next;
		q = q->prev;
	}
}
int main() {
	DoubleLinkedList obj;
	char temp[105] = {};
	cin >> temp;
	obj.CreatList(temp);
	if (obj.Judge_HUIWEN())
	{
		obj.SequentialPrint();
		cout << "True" << endl;
	}
	else
	{
		obj.SequentialPrint();
		cout << "False" << endl;
	}
	while (true)
	{
		int x;
		cin >> x;
		obj.DeleteElement(x);
		obj.SequentialPrint();
	}
	system("pause");
	return 0;
}

成功解决！