[数据结构与算法]单链表（C++版）

数据结构

单链表操作案例

??关于单链表的一些描述可以参考数据结构-第二章（5）-链式存储结构和数据结构-第二章（6）-单链表基本操作的实现

一、制作界面

//界面制作
void showMenu()
{
	std::cout << "***********************************" << endl;
	std::cout << "*****  [0]-----退出链表-----*******" << endl;
	std::cout << "*****  [1]----创建单链表----*******" << endl;
	std::cout << "*****  [2]----链表的判空----*******" << endl;
	std::cout << "*****  [3]----求链表长度----*******" << endl;
	std::cout << "*****  [4]----对链表取值----*******" << endl;
	std::cout << "*****  [5]----链表的查找----*******" << endl;
	std::cout << "*****  [6]----链表的插入----*******" << endl;
	std::cout << "*****  [7]----链表的删除----*******" << endl;
	std::cout << "*****  [8]----对链表清空----*******" << endl;
	std::cout << "*****  [9]----对链表销毁----*******" << endl;
	std::cout << "*****  [10]---单链表的合并--*******" << endl;
	std::cout << "***********************************" << endl;
}

二、链表类型定义

typedef struct Lnode//声明结点的类型和指向结点的指针类型
{
	ElemType data;//结点的数据域
	struct Lnode* next;//结点的指针域,next中存的是地址,指向Lnode这个类型的指针
}Listnode, * Linklist;//linklist为指向结构体Lnode的指针类型,里面存了个地址（Lnode变量的地址）

三、创建链表

头插法：

void head_insert(Linklist& L)
{
	int n;
	std::cout << "请输入单链表元素个数：";
	std::cin >> n;

	for (int i = n; i > 0; --i)
	{
		Listnode* p = new Listnode;
		std::cin >> p->data;
		p->next = L->next;//插入到表头
		L->next = p;
	}
}

尾插法：

void tail_insert(Linklist& L)
{
	int n;
	std::cout << "请输入单链表元素个数：";
	std::cin >> n;

	Listnode* r = L;//尾指针r指向头结点
	for (int i = 0; i < n; i++)
	{
		Listnode* p = new Listnode;
		std::cin >> p->data;
		p->next = NULL;
		r->next = p;//插入到表尾
		r = p;//r指向新的尾结点
	}
}

创建单链表

void CreatList(Linklist& L)
{
	//1、生成新结点作为头结点
	L = new Listnode;
	//2、头结点的指针域next置空
	L->next = NULL;
	std::cout << "单链表已初始化，请创建单链表" << std::endl;
	std::cout << "输入1为选择头插法建立单链表，输入2为选择尾插法建立单链表" << std::endl;
	int select;
	std::cin >> select;

	if (select == 1)
	{
		head_insert(L);
	}
	else if (select == 2)
	{
		tail_insert(L);
	}
	else
	{
		std::cout << "你的输入有误，请重新输入！" << std::endl;
	}
	
}//CreatList

四、单链表判空

简单写法：

??这种写法在没创建单链表的条件下会报错!

void ListEmpty(Linklist& L)
{
	if (L->next)//非空
	{
		std::cout << "这不是一个空链表" << endl;
	}
	else
	{
		std::cout << "这是一个空链表" << endl;
	}
}

完善写法：

void ListEmpty(Linklist& L)
{
	if (L == NULL)
	{
		std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;
		return;
	}

	if (L->next) std::cout << "这不是一个空链表" << endl;
	else std::cout << "这是一个空链表" << endl;
}

五、求链表长度

void ListLength(Linklist& L)
{
	/*Linklist p;
	p = L;*/
	Listnode* p = L;
	if (p == NULL)
	{
		std::cout << "链表不存在，请尝试选择1创建单链表" <<std::endl;
		return;
	}
	int i = 0;
	while (p)
	{
		p = p->next;
		i++;
	}
	std::cout << "单链表表长为：" << i - 1 << std::endl;
}//ListLength

六、对链表取值

??和上面不同的是，后面的形参类型为指针，但意思其实一样。

void GetElem(Listnode* L)
{
	Listnode* p;
	ElemType e;
	int i;
	if (L == NULL)
	{
		std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;
		return;
	}
	std::cout << "请输入你要取出单链表元素的位置：";
	std::cin >> i;
	p = L->next; //变量初始化，p指向第一个节点
	int j = 1;
	while (p && j < i)
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)
	{
		std::cout << "链表中不存在第" << i << "个节点，请重新输入！" << std::endl;//链表中不存在第i个节点
		return;
	}
	e = p->data; //取到第i个元素
	std::cout << "取出的元素为:" << e << std::endl;
}//GetElem

七、单链表的查找

	void LocateElem(Listnode* L)
	{
		Listnode* p;
		ElemType e;
		int i = 0;
		if (L == NULL)
		{
			std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;
			return;
		}
		p = L;
		std::cout << "请输入要查找的元素：";
		std::cin >> e;
		while (p && p->data != e)
		{
			i++;
			p = p->next;
		}

		if (p) std::cout << "所找元素的位置为：" << i << std::endl; 
		else std::cout << "所找的元素不存在，请重新选择！" << std::endl; 
	}//LocateElem

八、单链表的插入

void ListInsert(Listnode* L)
{
	//在单链表L的第i个结点前插入值为e的新结点
	Listnode* p, *s, *q;
	int i, j;
	ElemType e;
	if (L == NULL)
	{
		std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;
		return;
	}
	p = L; j = 0;
	std::cout << "请输入插入节点的位置及插入的元素：";
	std::cin >> i >> e;

	while (p && j < i - 1)
	{ //查找第i- 1个节点，并令指针p指向该节点
		p = p->next; ++j;
	}//while
	if (!p || j > i - 1)
	{
		std::cout << "参数不合法，i小于1或者大于表长加1" << std::endl; 
		return;
	}
	s = new Listnode;
	if (!s) exit(1); //存储空间失败
	s->data = e; //创建新元素节点
	s->next = p->next; p->next = s; //修改指针
	std::cout << "插入后的单链表：";
	q = L->next;
	while (q)
	{
		std::cout << q->data << ' ';
		q = q->next;
	}
	std::cout << std::endl;
}//ListInsert

九、单链表的删除

void ListDelete(Listnode* L)
{
	//删除单链表L的第i个元素元素，输出删除元素后的顺序表
	Listnode *p, *q, *r;
	int i, j;
	if (L == NULL)
	{
		std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;
		return;
	}
	std::cout << "请输入删除节点的位置：";
	std::cin >> i;
	p = L; j = 0;
	while (p->next && j < i - 1)
	{ //寻找第i个节点，并令指针p指向其前驱
		p = p->next; ++j;
	}//while
	if (!(p->next) || j > i - 1)
	{
		std::cout << "删除位置不合法"; //删除位置不合法
		return;
	}
	q = p->next; p->next = q->next; //修改指针
	delete(q); //释放节点空间
	std::cout << "删除后的单链表：";
	r = L->next;
	while (r)
	{
		std::cout << r->data << ' ';
		r = r->next;
	}
	std::cout << std::endl;
}//ListDelete

十、清空单链表

void ClearList(Listnode* L)
{
	if (L == NULL)
	{
		std::cout << "链表不存在" << std::endl;
		return;
	}
	Listnode* p, * q;
	p = L->next;
	while (p)
	{
		q = p -> next;
		delete p;
		p = q;
	}
	L->next = NULL;
	std::cout << "单链表已清空" << std::endl;
}

十一、销毁单链表

void DestroyList(Listnode* L)
{
	if (L == NULL)
	{
		std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;
		return;
	}
	Listnode* p;
	while (L)
	{
		p = L;
		L = L->next;
		delete p;
	}//while
	L = NULL; 
	std::cout << "链表已销毁" << std::endl;
}//DestroyList

十二、合并单链表

void MergeList()
{
	//按值排序的单链表La,Lb,归并为Lc后也按值排序
	Linklist La, Lb, Lc, pa, pb, pc, ra, rb, q;
	int m, n, j;
	std::cout << "请输入单链表La元素个数：";
	std::cin >> m;
	La = new Listnode;
	ra = La;
	if (!La) exit(0); //存储空间分配失败
	std::cout << "请输入单链表La的元素：";
	for (j = 0; j < m; j++)
	{
		pa = new Listnode; //生成新节点
		std::cin >> pa->data; //输入元素值
		ra->next = pa; ra = pa; //插入到表头
	}
	ra->next = NULL;
	std::cout << "请输入单链表Lb元素个数：";
	std::cin >> n;
	Lb = new Listnode;
	rb = Lb;
	if (!Lb) exit(0); //存储空间分配失败
	std::cout << "请输入单链表Lb的元素：";
	for (j = 0; j < n; j++)
	{
		pb = new Listnode; //生成新节点
		std::cin >> pb->data; //输入元素值
		rb->next = pb; rb = pb; //插入到表头
	}
	rb->next = NULL;
	pa = La->next; pb = Lb->next; Lc = pc = La; q = Lc->next;
	while (pa && pb)
	{
		if (pa->data <= pb->data)
		{
			pc->next = pa; pc = pa; pa = pa->next;
		}
		else
		{
			pc->next = pb; pc = pb; pb = pb->next;
		}
	}
	pc->next = pa ? pa : pb;

	delete Lb; //释放Lb头节点
	j = 0;
	std::cout << "合并后的单链表为：";
	while (j < m + n)
	{
		std::cout << q->data << ' ';
		q = q->next;
		j++;
	}
	std::cout << std::endl;
}//MergeList

完整版

#include<iostream>
#include<string>
#include <stdlib.h>
using namespace std;
//界面制作
void showMenu()
{
	std::cout << "***********************************" << endl;
	std::cout << "*****  [0]-----退出链表-----*******" << endl;
	std::cout << "*****  [1]----创建单链表----*******" << endl;
	std::cout << "*****  [2]----链表的判空----*******" << endl;
	std::cout << "*****  [3]----求链表长度----*******" << endl;
	std::cout << "*****  [4]----对链表取值----*******" << endl;
	std::cout << "*****  [5]----链表的查找----*******" << endl;
	std::cout << "*****  [6]----链表的插入----*******" << endl;
	std::cout << "*****  [7]----链表的删除----*******" << endl;
	std::cout << "*****  [8]----对链表清空----*******" << endl;
	std::cout << "*****  [9]----对链表销毁----*******" << endl;
	std::cout << "*****  [10]---单链表的合并--*******" << endl;
	std::cout << "***********************************" << endl;
}


typedef int ElemType;

typedef struct Lnode//声明结点的类型和指向结点的指针类型
{
	ElemType data;//结点的数据域
	struct Lnode* next;//结点的指针域,next中存的是地址,指向Lnode这个类型的指针
}Listnode, * Linklist;//linklist为指向结构体Lnode的指针类型,里面存了个地址（Lnode变量的地址）

void CreatList(Linklist& L);
void ListEmpty(Linklist& L);
void ListLength(Linklist& L); 
void GetElem(Listnode* L);
void LocateElem(Listnode* L);
void ListInsert(Listnode* L);
void ListDelete(Listnode* L);
void ClearList(Listnode* L);
void DestroyList(Listnode* L);
void MergeList();

int main(void)
{
	Linklist L;
	L = NULL;
	int select;
	
	while (true)
	{
		showMenu();
		std::cout << "请输入您的选择：";
		std::cin >> select;
		switch (select)
		{
		case 0:
			std::cout << "已退出系统" << std::endl;
			break;
		case 1: 
			CreatList(L);
			break;
		case 2: 
			ListEmpty(L);
			break;
		case 3:
			ListLength(L);
			break;
		case 4:
			GetElem(L);//取值
			break;
		case 5:
			LocateElem(L);
			break;
		case 6:
			ListInsert(L);
			break;
		case 7:
			ListDelete(L);
			break;
		case 8:
			ClearList(L);
			break;
		case 9:
			DestroyList(L);
			break;
		case 10:
			MergeList();
			break;
		default:
			std::cout << "无效选项!" << std::endl; 
			system("pause");
		}

	}	

}


void head_insert(Linklist& L)
{
	int n;
	std::cout << "请输入单链表元素个数：";
	std::cin >> n;

	for (int i = n; i > 0; --i)
	{
		Listnode* p = new Listnode;
		std::cin >> p->data;
		p->next = L->next;//插入到表头
		L->next = p;
	}
}
void tail_insert(Linklist& L)
{
	int n;
	std::cout << "请输入单链表元素个数：";
	std::cin >> n;

	Listnode* r = L;//尾指针r指向头结点
	for (int i = 0; i < n; i++)
	{
		Listnode* p = new Listnode;
		std::cin >> p->data;
		p->next = NULL;
		r->next = p;//插入到表尾
		r = p;//r指向新的尾结点
	}
}

void CreatList(Linklist& L)
{
	//1、生成新结点作为头结点
	L = new Listnode;
	//2、头结点的指针域next置空
	L->next = NULL;
	std::cout << "单链表已初始化，请创建单链表" << std::endl;
	std::cout << "输入1为选择头插法建立单链表，输入2为选择尾插法建立单链表" << std::endl;
	int select;
	std::cin >> select;

	if (select == 1)
	{
		head_insert(L);
	}
	else if (select == 2)
	{
		tail_insert(L);
	}
	else
	{
		std::cout << "你的输入有误，请重新输入！" << std::endl;
	}

}//CreatList


void ListEmpty(Linklist& L)
{
	if (L == NULL)
	{
		std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;
		return;
	}

	if (L->next) std::cout << "这不是一个空链表" << endl;
	else std::cout << "这是一个空链表" << endl;
}


void ListLength(Linklist& L)
{
	Listnode* p = L;
	if (p == NULL)
	{
		std::cout << "链表不存在，请尝试选择1创建单链表" <<std::endl;
		return;
	}
	int i = 0;
	while (p)
	{
		p = p->next;
		i++;
	}
	std::cout << "单链表表长为：" << i - 1 << std::endl;
}//ListLength

void GetElem(Listnode* L)
{
	Listnode* p;
	ElemType e;
	int i;
	if (L == NULL)
	{
		std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;
		return;
	}
	std::cout << "请输入你要取出单链表元素的位置：";
	std::cin >> i;
	p = L->next; 
	int j = 1;
	while (p && j < i)
	{ 
		p = p->next;
		++j;
	}
	if (!p || j > i)
	{
		std::cout << "链表中不存在第" << i << "个节点，请重新输入！" << std::endl;
		return;
	}
	e = p->data; 
	std::cout << "取出的元素为:" << e << std::endl;
}//GetElem


	void LocateElem(Listnode* L)
	{
		Listnode* p;
		ElemType e;
		int i = 0;
		if (L == NULL)
		{
			std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;
			return;
		}
		p = L;
		std::cout << "请输入要查找的元素：";
		std::cin >> e;
		while (p && p->data != e)
		{
			i++;
			p = p->next;
		}

		if (p) std::cout << "所找元素的位置为：" << i << std::endl; 
		else std::cout << "所找的元素不存在，请重新选择！" << std::endl; 
	}//LocateElem

void ListInsert(Listnode* L)
{
	Listnode* p, *s, *q;
	int i, j;
	ElemType e;
	if (L == NULL)
	{
		std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;
		return;
	}
	p = L; j = 0;
	std::cout << "请输入插入节点的位置及插入的元素：";
	std::cin >> i >> e;

	while (p && j < i - 1)
	{ 
		p = p->next; ++j;
	}
	if (!p || j > i - 1)
	{
		std::cout << "参数不合法，i小于1或者大于表长加1" << std::endl; 
		return;
	}
	s = new Listnode;
	if (!s) exit(1); //存储空间失败
	s->data = e; //创建新元素节点
	s->next = p->next; p->next = s; //修改指针
	std::cout << "插入后的单链表：";
	q = L->next;
	while (q)
	{
		std::cout << q->data << ' ';
		q = q->next;
	}
	std::cout << std::endl;
}//ListInsert

void ListDelete(Listnode* L)
{
	//删除单链表L的第i个元素元素，输出删除元素后的顺序表
	Listnode *p, *q, *r;
	int i, j;
	if (L == NULL)
	{
		std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;
		return;
	}
	std::cout << "请输入删除节点的位置：";
	std::cin >> i;
	p = L; j = 0;
	while (p->next && j < i - 1)
	{ //寻找第i个节点，并令指针p指向其前驱
		p = p->next; ++j;
	}
	if (!(p->next) || j > i - 1)
	{
		std::cout << "删除位置不合法"; //删除位置不合法
		return;
	}
	q = p->next; p->next = q->next; //修改指针
	delete(q); //释放节点空间
	std::cout << "删除后的单链表：";
	r = L->next;
	while (r)
	{
		std::cout << r->data << ' ';
		r = r->next;
	}
	std::cout << std::endl;
}//ListDelete

void ClearList(Listnode* L)
{
	if (L == NULL)
	{
		std::cout << "链表不存在" << std::endl;
		return;
	}
	Listnode* p, * q;
	p = L->next;
	while (p)
	{
		q = p -> next;
		delete p;
		p = q;
	}
	L->next = NULL;
	std::cout << "单链表已清空" << std::endl;
}



void DestroyList(Listnode* L)
{
	if (L == NULL)
	{
		std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;
		return;
	}
	//销毁以L为头指针的单链表，释放链表中所有节点的空间
	Listnode* p;
	while (L)
	{
		p = L;
		L = L->next;
		delete p;
	}
	L = NULL; 
	std::cout << "链表已销毁" << std::endl;
}//DestroyList


void MergeList()
{
	Linklist La, Lb, Lc, pa, pb, pc, ra, rb, q;
	int m, n, j;
	std::cout << "请输入单链表La元素个数：";
	std::cin >> m;
	La = new Listnode;
	ra = La;
	if (!La) exit(0); //存储空间分配失败
	std::cout << "请输入单链表La的元素：";
	for (j = 0; j < m; j++)
	{
		pa = new Listnode; //生成新节点
		std::cin >> pa->data; //输入元素值
		ra->next = pa; ra = pa; //插入到表头
	}
	ra->next = NULL;
	std::cout << "请输入单链表Lb元素个数：";
	std::cin >> n;
	Lb = new Listnode;
	rb = Lb;
	if (!Lb) exit(0); //存储空间分配失败
	std::cout << "请输入单链表Lb的元素：";
	for (j = 0; j < n; j++)
	{
		pb = new Listnode; //生成新节点
		std::cin >> pb->data; //输入元素值
		rb->next = pb; rb = pb; //插入到表头
	}
	rb->next = NULL;
	pa = La->next; pb = Lb->next; Lc = pc = La; q = Lc->next;
	while (pa && pb) 
	{
		if (pa->data <= pb->data)
		{
			pc->next = pa; pc = pa; pa = pa->next;
		}
		else
		{
			pc->next = pb; pc = pb; pb = pb->next;
		}
	}
	pc->next = pa ? pa : pb;

	delete Lb; 
	j = 0;
	std::cout << "合并后的单链表为：";
	while (j < m + n)
	{
		std::cout << q->data << ' ';
		q = q->next;
		j++;
	}
	std::cout << std::endl;
}//MergeList

总结

期待大家和我交流，留言或者私信，一起学习，一起进步！