数据结构-单链表

大家好：
衷心希望各位点赞。
您的问题请留在评论区，我会及时回答。

单链表的定义

// 链表的定义
typedef struct _LinkNode
{
	ElemType data; // 数据域
	struct _LinkNode* next; // 指针域
}* LinkList, LinkNode; // LinkList：头指针、LinkNode：链表节点

单链表的初始化

bool initList(LinkList& L)
{
	L = new LinkNode; // 生成新节点作为头节点，用头指针L指向头节点

	if (L == NULL) return false; // 生成节点失败

	L->next = NULL; // 头节点指针域置为空

	L->data = 0; // 头节点数据映射链表长度

	return true;
}

代码示范：

#include <iostream>
#include <Windows.h>

using namespace std;

typedef int ElemType;

// 链表的定义
typedef struct _LinkNode
{
	ElemType data; // 数据域
	struct _LinkNode* next; // 指针域
}* LinkList, LinkNode; // LinkList：头指针、LinkNode：链表节点

// 构造一个空的单链表
// 生成头节点
bool initList(LinkList& L)
{
	L = new LinkNode; // 生成新节点作为头节点，用头指针L指向头节点

	if (L == NULL) return false; // 生成节点失败

	L->next = NULL; // 头节点指针域置为空

	L->data = 0; // 头节点数据映射链表长度

	return true;
}

int main(void)
{
	LinkList L;
	initList(L); // 初始化链表
	
	system("pause");
	return 0;
}

单链表的打印

// 打印链表
void listPrint(const LinkList& L)
{
	LinkList p = L->next;

	if (p == NULL) return ; // 链表为空

	cout << "链表长度：" << L->data << " 链表元素：";
	while (p != NULL)
	{
		cout << p->data << "  ";
		p = p->next;
	}
	cout << endl;
}

单链表的插入——头插法

// 插入节点
// 头插法
bool listInsert_front(LinkList& L, LinkNode* node)
{
	if (L == NULL || node == NULL ) return false;

	node->next = L->next; // 新节点的指针域指向头结点的后继节点
	L->next = node; // 头结点的指针域指向新节点
	L->data++; // 链表的节点数加一
	return true;
}

代码示范：

#include <iostream>
#include <Windows.h>

using namespace std;

typedef int ElemType;

// 链表的定义
typedef struct _LinkNode
{
	ElemType data; // 数据域
	struct _LinkNode* next; // 指针域
}* LinkList, LinkNode;

// 构造一个空的单链表
// 生成头节点
bool initList(LinkList& L);

// 插入节点
// 头插法
bool listInsert_front(LinkList& L, LinkNode* node);

// 打印链表
void listPrint(const LinkList& L);

int main(void)
{
	LinkList L;
	initList(L); // 初始化链表

	for (int i = 0; i < 10; i++)
	{
		LinkNode* node = new LinkNode; // 创建节点
		node->data = i + 1; // 给新节点的数据域赋值
		listInsert_front(L, node); // 头插法给单链表插入新节点
	}

	listPrint(L);

	system("pause");
	return 0;
}

bool initList(LinkList& L)
{
	L = new LinkNode; // 生成新节点作为头节点，用头指针L指向头节点

	if (L == NULL) return false; // 生成节点失败

	L->next = NULL; // 头节点指针域置为空

	L->data = 0; // 头节点数据映射链表长度

	return true;
}

bool listInsert_front(LinkList& L, LinkNode* node)
{
	if (L == NULL || node == NULL ) return false;

	node->next = L->next; // 新节点的指针域指向头结点的后继节点
	L->next = node; // 头结点的指针域指向新节点
	L->data++; // 链表的节点数加一
	return true;
}

void listPrint(const LinkList& L)
{
	LinkList p = L->next;

	if (p == NULL) return ; // 链表为空

	cout << "链表长度：" << L->data << " 链表元素：";
	while (p != NULL)
	{
		cout << p->data << "  ";
		p = p->next;
	}
	cout << endl;
}

运行截图：

单链表的插入——尾插法

// 插入节点
// 尾插法
bool listInsert_back(LinkList& L, LinkNode* node)
{
	if (L == NULL || node == NULL) return false;

	LinkList p = L;

	// 指针p移动到表尾元素
	while (p->next != NULL)
	{
		p = p->next;
	}

	node->next = p->next;

	p->next = node;

	L->data++; // 链表元素个数加一

	return true;
}

代码示范：

#include <iostream>
#include <Windows.h>

using namespace std;

typedef int ElemType;

// 链表的定义
typedef struct _LinkNode
{
	ElemType data; // 数据域
	struct _LinkNode* next; // 指针域
}* LinkList, LinkNode;

// 构造一个空的单链表
// 生成头节点
bool initList(LinkList& L);

// 插入节点
// 头插法
bool listInsert_front(LinkList& L, LinkNode* node);

// 插入节点
// 尾插法
bool listInsert_back(LinkList& L, LinkNode* node);

// 打印链表
void listPrint(const LinkList& L);

int main(void)
{
	LinkList L;
	initList(L); // 初始化链表

	for (int i = 0; i < 10; i++)
	{
		LinkNode* node = new LinkNode; // 创建节点
		node->data = i + 1; // 给新节点的数据域赋值
		listInsert_back(L, node); // 尾插法给单链表插入新节点
	}

	listPrint(L);

	system("pause");
	return 0;
}

bool initList(LinkList& L)
{
	L = new LinkNode; // 生成新节点作为头节点，用头指针L指向头节点

	if (L == NULL) return false; // 生成节点失败

	L->next = NULL; // 头节点指针域置为空

	L->data = 0; // 头节点数据映射链表长度

	return true;
}

bool listInsert_front(LinkList& L, LinkNode* node)
{
	if (L == NULL || node == NULL ) return false;

	node->next = L->next; // 新节点的指针域指向头结点的后继节点
	L->next = node; // 头结点的指针域指向新节点
	L->data++; // 链表的节点数加一
	return true;
}

bool listInsert_back(LinkList& L, LinkNode* node)
{
	if (L == NULL || node == NULL) return false;

	LinkList p = L;

	// 指针p移动到表尾元素
	while (p->next != NULL)
	{
		p = p->next;
	}

	node->next = p->next;

	p->next = node;

	L->data++; // 链表元素个数加一

	return true;
}

void listPrint(const LinkList& L)
{
	LinkList p = L->next;

	if (p == NULL) return ; // 链表为空

	cout << "链表长度：" << L->data << " 链表元素：";
	while (p != NULL)
	{
		cout << p->data << "  ";
		p = p->next;
	}
	cout << endl;
}

运行截图：

单链表的插入——在指定位置插入元素

// 插入节点
bool ListInsert(LinkList& L, int pos, ElemType elem)
{
	int i = 0;
	LinkList p, s;
	p = L;
	i = 1;
	while (p != NULL && i < pos)
	{
		// 寻找第i个节点
		p = p->next;
		i++;
	}
	if (p == NULL || i > pos)return false;

	s = new LinkNode;
	s->data = elem;
	s->next = p->next;
	p->next = s;

	L->data++;

	return true;
}

代码示范：

#include <iostream>
#include <Windows.h>

using namespace std;

typedef int ElemType;

// 链表的定义
typedef struct _LinkNode
{
	ElemType data; // 数据域
	struct _LinkNode* next; // 指针域
}* LinkList, LinkNode;

// 构造一个空的单链表
// 生成头节点
bool initList(LinkList& L);

// 插入节点
// 头插法
bool listInsert_front(LinkList& L, LinkNode* node);

// 插入节点
// 尾插法
bool listInsert_back(LinkList& L, LinkNode* node);

// 插入节点
bool ListInsert(LinkList& L, int pos, ElemType elem);

// 打印链表
void listPrint(const LinkList& L);

int main(void)
{
	LinkList L;
	initList(L); // 初始化链表

	for (int i = 0; i < 5; i++)
	{
		LinkNode* node = new LinkNode; // 创建节点
		node->data = i + 1; // 给新节点的数据域赋值
		listInsert_back(L, node); // 尾插法给单链表插入新节点
	}

	listPrint(L);
	cout << endl;

	cout << "在第3个位置插入值为10的元素：" << endl;;

	ListInsert(L, 3, 10);

	listPrint(L);

	system("pause");
	return 0;
}

bool initList(LinkList& L)
{
	L = new LinkNode; // 生成新节点作为头节点，用头指针L指向头节点

	if (L == NULL) return false; // 生成节点失败

	L->next = NULL; // 头节点指针域置为空

	L->data = 0; // 头节点数据映射链表长度

	return true;
}

bool listInsert_front(LinkList& L, LinkNode* node)
{
	if (L == NULL || node == NULL ) return false;

	node->next = L->next; // 新节点的指针域指向头结点的后继节点
	L->next = node; // 头结点的指针域指向新节点
	L->data++; // 链表的节点数加一
	return true;
}

bool listInsert_back(LinkList& L, LinkNode* node)
{
	if (L == NULL || node == NULL) return false;

	LinkList p = L;

	// 指针p移动到表尾元素
	while (p->next != NULL)
	{
		p = p->next;
	}

	node->next = p->next;

	p->next = node;

	L->data++; // 链表元素个数加一

	return true;
}

bool ListInsert(LinkList& L, int pos, ElemType elem)
{
	int i = 0;
	LinkList p, s;
	p = L;
	i = 1;
	while (p != NULL && i < pos)
	{
		// 寻找第i个节点
		p = p->next;
		i++;
	}
	if (p == NULL || i > pos)return false;

	s = new LinkNode;
	s->data = elem;
	s->next = p->next;
	p->next = s;

	L->data++;

	return true;
}

void listPrint(const LinkList& L)
{
	LinkList p = L->next;

	if (p == NULL) return ; // 链表为空

	cout << "链表长度：" << L->data << " 链表元素：";
	while (p != NULL)
	{
		cout << p->data << "  ";
		p = p->next;
	}
	cout << endl;
}

运行截图：

单链表的删除

// 单链表的删除
// 删除L的第pos个元素，并用elem返回其值，L的长度减1
bool ListDelete(LinkList& L, int pos, ElemType* elem)
{
	int i;
	LinkList p, q;
	p = L;
	i = 1;
	while (p->next != NULL && i < pos)
	{
		p = p->next;
		i++;
	}

	if (p->next == NULL || i > pos)
	{
		return false;
	}

	q = p->next;
	p->next = q->next;
	*elem = q->data;
	delete q;

	L->data--;
	return true;
}

代码示范：

#include <iostream>
#include <Windows.h>

using namespace std;

typedef int ElemType;

// 链表的定义
typedef struct _LinkNode
{
	ElemType data; // 数据域
	struct _LinkNode* next; // 指针域
}* LinkList, LinkNode;

// 构造一个空的单链表
// 生成头节点
bool initList(LinkList& L);

// 插入节点
// 头插法
bool listInsert_front(LinkList& L, LinkNode* node);

// 插入节点
// 尾插法
bool listInsert_back(LinkList& L, LinkNode* node);

// 插入节点
bool ListInsert(LinkList& L, int pos, ElemType elem);

// 单链表的删除
// 删除L的第pos个元素，并用elem返回其值，L的长度减1
bool ListDelete(LinkList& L, int pos, ElemType* elem);

// 打印链表
void listPrint(const LinkList& L);

int main(void)
{
	LinkList L;
	initList(L); // 初始化链表

	for (int i = 0; i < 5; i++)
	{
		LinkNode* node = new LinkNode; // 创建节点
		node->data = i + 1; // 给新节点的数据域赋值
		listInsert_back(L, node); // 尾插法给单链表插入新节点
	}

	listPrint(L);
	cout << endl;

	cout << "删除在第3个位置的元素：" << endl;;

	ElemType e;
	ListDelete(L, 3, &e);

	cout << "删除的元素为：" << e << endl;

	listPrint(L);

	system("pause");
	return 0;
}

bool initList(LinkList& L)
{
	L = new LinkNode; // 生成新节点作为头节点，用头指针L指向头节点

	if (L == NULL) return false; // 生成节点失败

	L->next = NULL; // 头节点指针域置为空

	L->data = 0; // 头节点数据映射链表长度

	return true;
}

bool listInsert_front(LinkList& L, LinkNode* node)
{
	if (L == NULL || node == NULL ) return false;

	node->next = L->next; // 新节点的指针域指向头结点的后继节点
	L->next = node; // 头结点的指针域指向新节点
	L->data++; // 链表的节点数加一
	return true;
}

bool listInsert_back(LinkList& L, LinkNode* node)
{
	if (L == NULL || node == NULL) return false;

	LinkList p = L;

	// 指针p移动到表尾元素
	while (p->next != NULL)
	{
		p = p->next;
	}

	node->next = p->next;

	p->next = node;

	L->data++; // 链表元素个数加一

	return true;
}

bool ListInsert(LinkList& L, int pos, ElemType elem)
{
	int i = 0;
	LinkList p, s;
	p = L;
	i = 1;
	while (p != NULL && i < pos)
	{
		// 寻找第i个节点
		p = p->next;
		i++;
	}
	if (p == NULL || i > pos)return false;

	s = new LinkNode;
	s->data = elem;
	s->next = p->next;
	p->next = s;

	L->data++;

	return true;
}

bool ListDelete(LinkList& L, int pos, ElemType* elem)
{
	int i;
	LinkList p, q;
	p = L;
	i = 1;
	while (p->next != NULL && i < pos)
	{
		p = p->next;
		i++;
	}

	if (p->next == NULL || i > pos)
	{
		return false;
	}

	q = p->next;
	p->next = q->next;
	*elem = q->data;
	delete q;

	L->data--;
	return true;

}

void listPrint(const LinkList& L)
{
	LinkList p = L->next;

	if (p == NULL) return ; // 链表为空

	cout << "链表长度：" << L->data << " 链表元素：";
	while (p != NULL)
	{
		cout << p->data << "  ";
		p = p->next;
	}
	cout << endl;
}

运行截图：