C++实现数据结构——单链表

2020年8月7日 周五 天气晴 【不悲叹过去，不荒废现在，不惧怕未来】

---

---

1. 引言

用C++实现了简单的单链表类，功能包括插入、删除、查找相关元素，分离链表等操作。代码是用VS2019实现的，每个函数的功能都添加了一定注释，完整工程放在了我的github上，有需要的也可以自取。

github地址：https://github.com/March225/Data-structure-implemented-by-Cpp

---

2. 主文件——main.cpp

/**
 *  @Copyright (C) 2020 March. All rights reserved.
 *  @license   GNU General Public License (GPL)
 *  @author	   March
 *  @email	   [e-mail]
 *  @file	   main.cpp
 *  @brief	   单链表的C++实现主文件
 *  @version   1.0
 *  @date	   2020-08-07
 */

#include "stdafx.h"
#include "linklist.h"

int main()
{
	FILE* stream1;
	ios::sync_with_stdio(false); // 让c风格的输入输出流和c++的输入输出流分开,使cin读入的更快
	freopen_s(&stream1, "10_1.in", "r", stdin); // 直接从文档中读取待输入的数据


	// 下面展示的是按照元素值的奇偶性分解单链表的功能，实现函数为 SplitLinkListByParityOfVal()
	LinkList* L1 = new LinkList();
	int len;
	cin >> len;
	L1->CreateLinkListByInsertAtEnd(len);
	L1->PrintLinkList();

	LinkList* L1_odd = new LinkList();
	LinkList* L1_even = new LinkList();

	L1->SplitLinkListByParityOfVal(L1_odd, L1_even); // 实现分离
	L1_odd->PrintLinkList(); // 打印奇数部分链表
	L1_even->PrintLinkList(); // 打印偶数部分链表

	L1->PrintLinkList(); // 打印原链表（由于原链表已经分解，因此打印出来为空）

	delete L1;
	delete L1_odd;
	delete L1_even;

	return 0;
}

3. 单链表类.h文件——linklist.h

#pragma once
/**
 * @brief 创建一个单链表类
 */

class LinkList
{
public:
	LinkList();
	~LinkList();

	int GetLength(); // 返回单链表的长度
	bool GetElemByPosition(int pos, ElemType& val); // 根据位置返回单链表的元素
	bool CreateLinkListByInsertAtEnd(int len); // 尾插法创建单链表
	bool CreateLinkListByInsertAtBeg(int len); // 头插法创建单链表
	bool InsertElemBeforePosition(int pos, ElemType val); // 在第pos个结点前插入值为val的结点
	bool FindElemByValue(int& pos, ElemType val); // 返回单链表中值为val的元素位置
	bool DeleteElemByPosition(int pos); // 根据位置删除单链表的元素
	bool InsertElemInOrder(ElemType val); // 在一个有序单链表中插入元素,并保证链表还是有序的
	bool SplitLinkListByParityOfVal(LinkList*& l_odd, LinkList*& l_even); // 根据元素的奇偶性分离单链表
	void PrintLinkList(); // 打印单链表的长度和元素

private:
	ListNode* head_; // 单链表的哑结点
	int length_; // 单链表的长度
};

4. 单链表类.cpp文件——linklist.cpp

#include "stdafx.h"
#include "linklist.h"

// 构造函数，初始化单链表
LinkList::LinkList() :head_(nullptr), length_(0)
{
	cout << this << "单链表已被初始化！" << endl;
}

// 析构函数，销毁单链表
LinkList::~LinkList()
{
	while (head_)
	{
		ListNode* cur = head_;
		head_ = head_->next;
		delete cur;
	}
	cout << this << "单链表已被销毁！" << endl;
}

// 返回单链表的长度
int LinkList::GetLength()
{
	return length_;
}

// 根据位置返回单链表的元素
bool LinkList::GetElemByPosition(int pos, ElemType& val)
{
	if (head_ == nullptr) {
		cout << "单链表为空，获取元素失败！" << endl;
		return false;
	}
	else if (pos <= 0 || pos > length_) {
		cout << "位置 " << setw(2) << pos << " 有误！" << "获取元素失败!" << endl;
		return false;
	}
	else {
		ListNode* cur = head_;
		while (cur)
		{
			if (--pos == 0) {
				val = cur->val;
				return true;
			}
			cur = cur->next;
		}
		cout << "未知原因，获取元素失败！" << endl;
		return false;
	}
}

// 尾插法创建单链表
bool LinkList::CreateLinkListByInsertAtEnd(int len)
{
	ListNode* dummy_node = new ListNode(0), * cur = dummy_node;
	for (int i = 0; i < len; ++i)
	{
		ElemType num;
		cin >> num;
		ListNode* new_node = new ListNode(num);
		cur->next = new_node;
		cur = cur->next;
		++length_;
	}
	head_ = dummy_node->next;
	return true;
}

// 头插法创建单链表
bool LinkList::CreateLinkListByInsertAtBeg(int len)
{
	ListNode* cur = nullptr;
	for (int i = 0; i < len; ++i)
	{
		ElemType num;
		cin >> num;
		ListNode* new_node = new ListNode(num);
		new_node->next = cur;
		cur = new_node;
		++length_;
	}
	head_ = cur;
	return true;
}

// 在第pos个结点前插入值为val的结点
bool LinkList::InsertElemBeforePosition(int pos, ElemType val)
{
	if (head_ == nullptr) {
		cout << "单链表为空，插入元素失败！" << endl;
		return false;
	}
	else if (pos <= 0 || pos > length_) {
		cout << "位置 " << setw(2) << pos << " 有误！" << "插入元素失败!" << endl;
		return false;
	}
	else {
		ListNode* dummy_node = new ListNode(0), * cur = dummy_node;
		dummy_node->next = head_;
		while (cur->next) {
			if (--pos == 0) {
				ListNode* tmp = cur->next;
				cur->next = new ListNode(val);
				cur->next->next = tmp;

				head_ = dummy_node->next;
				++length_;
				return true;
			}
			cur = cur->next;
		}
		cout << "未知原因，插入元素失败！" << endl;
		return false;
	}
}

// 返回单链表中值为val的元素位置
bool LinkList::FindElemByValue(int& pos, ElemType val)
{
	if (head_ == nullptr) {
		cout << "单链表为空，查找元素失败！" << endl;
		return false;
	}

	ListNode* cur = head_;
	int cnt = 1;
	while (cur) {
		if (cur->val == val) {
			pos = cnt;
			return true;
		}
		++cnt;
		cur = cur->next;
	}
	cout << "没有查找到值为 " << val << " 的元素！" << endl;
	return false;
}

// 根据位置删除单链表的元素
bool LinkList::DeleteElemByPosition(int pos)
{
	if (head_ == nullptr) {
		cout << "单链表为空，删除元素失败！" << endl;
		return false;
	}
	else if (pos <= 0 || pos > length_) {
		cout << "位置 " << setw(2) << pos << " 有误！" << "删除元素失败!" << endl;
		return false;
	}
	else {
		ListNode* dummy_node = new ListNode(0), * cur = dummy_node;
		dummy_node->next = head_;
		while (cur->next) {
			if (--pos == 0) {
				ListNode* tmp = cur->next;
				cur->next = cur->next->next;
				delete tmp;

				head_ = dummy_node->next;
				--length_;
				return true;
			}
			cur = cur->next;
		}
		cout << "未知原因，删除元素失败！" << endl;
		return false;
	}
}

// 在一个有序单链表中插入元素,并保证链表还是有序的
bool LinkList::InsertElemInOrder(ElemType val)
{
	if (!head_) {
		head_ = new ListNode(val);
		++length_;
		return true;
	}

	ListNode* dummy_node = new ListNode(0);
	dummy_node->next = head_;
	ListNode* pre = dummy_node;
	while (pre->next) {
		if (val <= pre->next->val) {
			ListNode* tmp = pre->next;
			pre->next = new ListNode(val);
			pre->next->next = tmp;
			break;
		}
		else {
			if (!pre->next->next) {
				ListNode* cur = pre->next;
				cur->next = new ListNode(val);
				cur->next->next = nullptr;
				break;
			}
			else
				pre = pre->next;
		}
	}
	head_ = dummy_node->next;
	++length_;
	return true;
}

// 根据元素的奇偶性分离单链表
bool LinkList::SplitLinkListByParityOfVal(LinkList*& l_odd, LinkList*& l_even)
{
	ListNode* cur = head_;
	ListNode* dummy_node_odd = new ListNode(0), * dummy_node_even = new ListNode(0);
	ListNode* cur_odd = dummy_node_odd, * cur_even = dummy_node_even;

	while (cur) {
		if (cur->val % 2 == 1) {
			cur_odd->next = cur;
			cur = cur->next;
			cur_odd->next->next = nullptr;
			cur_odd = cur_odd->next;
			++l_odd->length_;
		}
		else {
			cur_even->next = cur;
			cur = cur->next;
			cur_even->next->next = nullptr;
			cur_even = cur_even->next;
			++l_even->length_;
		}
		
	}
	l_odd->head_ = dummy_node_odd->next;
	l_even->head_ = dummy_node_even->next;
	head_ = nullptr;
	length_ = 0;
	return true;
}

// 打印单链表的长度和元素
void LinkList::PrintLinkList()
{
	ListNode* cur = head_;
	cout << "单链表长度：" << length_ << endl;
	cout << "单链表元素：";
	while (cur)
	{
		cout << cur->val << "->";
		cur = cur->next;
	}

	cout << "nullptr" << endl << endl;
}

5. 预编译头文件——stdafx.h

#pragma once
// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
//

#if !defined(AFX_STDAFX_H__D36E9D40_3BCB_4A85_9D48_AC876E7A2942__INCLUDED_)
#define AFX_STDAFX_H__D36E9D40_3BCB_4A85_9D48_AC876E7A2942__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <bits/stdc++.h> // 万能的头文件,可能需要手动加入include文件夹中

typedef int ElemType; // 使链表的数据类型ElemType为int

/**
 * @brief 定义单链表的结点
 */
struct ListNode {
	ElemType val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
};

using namespace std;

#endif // !defined(AFX_STDAFX_H__D36E9D40_3BCB_4A85_9D48_AC876E7A2942__INCLUDED_)

---

参考文献

https://www.cnblogs.com/25th-engineer/p/9937678.html

本文地址：https://blog.csdn.net/m0_37433111/article/details/107864737