线性表——单链表(C++)

?前言：此文章是介绍线性表中单链表的实现，参考视频数据结构与算法——第3周01--2.5线性表的链式表示和实现1--链表概念_哔哩哔哩_bilibili

视频里面实现基本是c语言和c++混合，此文章将视频中代码所有用c++进行重写，里面涉及到许多c++知识，如果还没有这方面知识，可以查阅对应博客后，再进行阅读！?

---

目录

链表的特性：?

1 数据准备

2 初始化单链表

3 销毁单链表

4 清空链表

5 获取链表长度

6 获取指定位置单链表的数据

7 获取指定数据单链表的位置

8 在指定位置插入数据

9 删除指定位置的元素

10 创建固定长度的单链表

11 打印单链表所有数据

12 主程序测试

整个代码

---

链表的特性：?

	链表
存储空间	动态分配，不会出现空间闲置或者溢出
存储密度	存储密度小于1，要借助指针域来表示元素之间的逻辑关系
存取元素	顺序存取，访问某位置的元素的时间复杂度为O(n)
插入、删除	不需要移动元素，只需要改变指针位置，继而改变结点之间的链接关系。时间复杂度O(1)
适用情况	1.长度变化较大 2.频繁的插入和删除

1 数据准备

#include <iostream>
#include <string>

using namespace std;

class Stuedents
{
public:
	string _mane;
	string _num;
	int _score;
	Stuedents();//初始化
	bool operator==(Stuedents& s);//运算符重载
	friend istream& operator>>(istream &is, Stuedents& s);
	friend ostream& operator<<(ostream &os, Stuedents& s);
};

Stuedents::Stuedents()
{
	_mane = "";
	_num = "";
	int _score = 0;
}
//运算符重载
bool Stuedents::operator==(Stuedents& s)
{
	if (_mane == s._mane &&  _num == s._num && _score == s._score)
	{
		return true;
	}
	else
	{
		return false;
	}
}
istream& operator>>(istream &is, Stuedents& s)
{
	cout << "name：";
	is >> s._mane;
	cout << "num：";
	is >> s._num;
	cout << "score：";
	is >> s._score;	
	return is;
}
ostream& operator<<(ostream &os, Stuedents& s)
{
	cout << "name：" << s._mane 
		<< " num：" << s._num 
		<< " score：" << s._score << endl;
	return os;
}

typedef Stuedents ElemType;

class Lnode
{
public:
	ElemType data;//结点的数据域
	Lnode* next;//结点的指针域
private:

};

class LinkList :public Lnode
{
public:
	Lnode* head;//头结点
	LinkList();//初始化单链表
	~LinkList();//销毁单链表
	bool ListIsEmpty();//判断链表是否为空
	void ListClear();//清空链表
	int ListLength();//获取链表长度
	bool ListGetElem(int i, ElemType &e);//获取指定位置单链表的数据
	bool ListLocateElem(int& i, ElemType &e);//获取指定数据单链表的位置
	bool ListInsertElem(int i, ElemType &e);//在指定位置插入数据
	bool ListDelete(int i);//删除指定位置的元素
	void ListCreate(int i);//头插法：创建固定长度的单链表
	void ListCreate(int i,int);//尾插法：创建固定长度的单链表
	void ListPrint();//打印单链表所有数据
};

2 初始化单链表

//初始化单链表
LinkList::LinkList()
{
	head = new Lnode;
	head->next = nullptr;//头结点置空
}

3 销毁单链表

//销毁单链表
LinkList::~LinkList()
{
	Lnode *p;
	while (head != nullptr)
	{
		p = head;
		head = p->next;
		delete p;
	}
}

4 清空链表

//清空链表
void LinkList::ListClear()
{
	Lnode *p, *q;
	p = head->next;
	while (p != nullptr)//一直循环到表尾
	{
		q = p->next;
		delete p;
		p = q;
	}
	head->next = nullptr;//头结点指针域置空
}

5 获取链表长度

//获取链表长度
int LinkList::ListLength()
{
	Lnode *p;
	p = head->next;
	int length = 0;

	while (p != nullptr)
	{
		length++;
		p = p->next;
	}
	return length;
}	

6 获取指定位置单链表的数据

//获取指定位置单链表的数据
bool LinkList::ListGetElem(int i, ElemType &e)
{
	Lnode *p;
	p = head->next;
	int temp = 1;
	while (p != nullptr && temp <= i)
	{
		if (temp == i)
		{
			e = p->data;
			return true;
		}
		p = p->next;
		temp++;
	}
	return false;
}

7 获取指定数据单链表的位置

//获取指定数据单链表的位置
bool LinkList::ListLocateElem(int& i, ElemType &e)
{
	Lnode *p;
	p = head->next;
	int temp = 1;
	while (p != nullptr)
	{
		if (e == p->data)
		{
			i = temp;
			return true;
		}
		temp++;
		p = p->next;
	}
	return false;
}

8 在指定位置插入数据

//在指定位置插入数据
bool LinkList::ListInsertElem(int i, ElemType &e)
{
	Lnode *p;
	p = head->next;
	int temp = 1;
	while (p != nullptr)
	{
		if (temp == i)
		{
			break;
		}
		temp++;
		p = p->next;
	}
	if (temp >= i)//找到数据位置,插入新数据
	{
		Lnode *q = new Lnode;
		q->data = e;
		q->next = p->next;
		p->next = q;
		return true;
	}
	else
	{
		return false;
	}
}

9 删除指定位置的元素

//删除指定位置的元素
bool LinkList::ListDelete(int i)
{
	Lnode *p,*q;
	p = head->next;
	int temp = 1;
	while (p != nullptr)
	{
		if (temp == i)
		{
			break;
		}
		temp++;
		p = p->next;
	}
	if (temp >= i)//找到数据位置，删除数据
	{
		q = p->next;
		p->next = q->next;
		delete q;
		return true;
	}
	else
	{
		return false;
	}
}

10 创建固定长度的单链表

void LinkList::ListCreate(int i)
{
	Lnode *p,*q;
	p = head;
	int temp = 1;
	while (temp <= i)
	{
		q = new Lnode;
		cin >> q->data;
		q->next = p->next;//插入到表头
		p->next = q;
		temp++;
	}
}
//尾插法：创建固定长度的单链表
void LinkList::ListCreate(int i, int)
{
	Lnode *p, *q;
	p = head;
	int temp = 1;
	while (temp <= i)
	{
		q = new Lnode;
		cin >> q->data;
		q->next = nullptr;
		p->next = q;//插入到表尾
		p = q;//p指向新的尾节点
		temp++;
		system("cls");
	}
}

11 打印单链表所有数据

//打印单链表所有数据
void  LinkList::ListPrint()
{
	Lnode *p;
	p = head->next;
	while (p != nullptr)
	{
		cout << p->data;
		p = p->next;
	}
}

12 主程序测试

void Show_Menu()
{
	cout << "****************************************************" << endl;
	cout << "1: ListCreate  2: ListDelete   3: ListInsertElem" << endl;
	cout << "4: ListLength  5: ListGetElem  6: ListPrint" << endl;
	cout << "****************************************************" << endl;
}

int main()
{
	LinkList L;
	
	//测试区域
	ElemType E,E1;
	E._mane = "张三";
	E._num = "11";
	E._score = 88;
	int num = 1;
	while (true)
	{
		//进行菜单显示
		Show_Menu();
		int select = 0;
		cout << "请输入你想操作功能的编号： ";
		cin >> select;
		switch (select)
		{
		case 0: //退出管理程序
			cout << "欢迎下次使用！" << endl;
			cout << endl;
			return 0;
		case 1:
			L.ListCreate(2);
			break;
		case 2:
			L.ListDelete(1);
			break;
		case 3:
			L.ListInsertElem(1, E);
			break;
		case 4:
			cout<<L.ListLength()<<endl;
			break;
		case 5:
			L.ListGetElem(num, E1);
			cout << E1 << endl;
			break;
		case 6:
			L.ListPrint();
			break;
		default://输入错误
			cout << endl;
			cout << "输入错误，请输入正确的功能编号!!!" << endl;
			cout << endl;
			break;
		}
		system("pause");
		system("cls");
	}
	system("pause");
	return 0;
}

整个代码

//2 单链表
#include <iostream>
#include <string>

using namespace std;

class Stuedents
{
public:
	string _mane;
	string _num;
	int _score;
	Stuedents();//初始化
	bool operator==(Stuedents& s);//运算符重载
	friend istream& operator>>(istream &is, Stuedents& s);
	friend ostream& operator<<(ostream &os, Stuedents& s);
};

Stuedents::Stuedents()
{
	_mane = "";
	_num = "";
	int _score = 0;
}
//运算符重载
bool Stuedents::operator==(Stuedents& s)
{
	if (_mane == s._mane &&  _num == s._num && _score == s._score)
	{
		return true;
	}
	else
	{
		return false;
	}
}
istream& operator>>(istream &is, Stuedents& s)
{
	cout << "name：";
	is >> s._mane;
	cout << "num：";
	is >> s._num;
	cout << "score：";
	is >> s._score;	
	return is;
}
ostream& operator<<(ostream &os, Stuedents& s)
{
	cout << "name：" << s._mane 
		<< " num：" << s._num 
		<< " score：" << s._score << endl;
	return os;
}

typedef Stuedents ElemType;

class Lnode
{
public:
	ElemType data;//结点的数据域
	Lnode* next;//结点的指针域
private:

};

class LinkList :public Lnode
{
public:
	Lnode* head;//头结点
	LinkList();//初始化单链表
	~LinkList();//销毁单链表
	bool ListIsEmpty();//判断链表是否为空
	void ListClear();//清空链表
	int ListLength();//获取链表长度
	bool ListGetElem(int i, ElemType &e);//获取指定位置单链表的数据
	bool ListLocateElem(int& i, ElemType &e);//获取指定数据单链表的位置
	bool ListInsertElem(int i, ElemType &e);//在指定位置插入数据
	bool ListDelete(int i);//删除指定位置的元素
	void ListCreate(int i);//头插法：创建固定长度的单链表
	void ListCreate(int i,int);//尾插法：创建固定长度的单链表
	void ListPrint();//打印单链表所有数据
};
//初始化单链表
LinkList::LinkList()
{
	head = new Lnode;
	head->next = nullptr;//头结点置空
}
//销毁单链表
LinkList::~LinkList()
{
	Lnode *p;
	while (head != nullptr)
	{
		p = head;
		head = p->next;
		delete p;
	}
}
//判断链表是否为空
bool LinkList::ListIsEmpty()
{
	if (head->next == nullptr)
	{
		return true;
	}
	else
	{
		return false;
	}
}
//清空链表
void LinkList::ListClear()
{
	Lnode *p, *q;
	p = head->next;
	while (p != nullptr)//一直循环到表尾
	{
		q = p->next;
		delete p;
		p = q;
	}
	head->next = nullptr;//头结点指针域置空
}
//获取链表长度
int LinkList::ListLength()
{
	Lnode *p;
	p = head->next;
	int length = 0;

	while (p != nullptr)
	{
		length++;
		p = p->next;
	}
	return length;
}

//获取指定位置单链表的数据
bool LinkList::ListGetElem(int i, ElemType &e)
{
	Lnode *p;
	p = head->next;
	int temp = 1;
	while (p != nullptr && temp <= i)
	{
		if (temp == i)
		{
			e = p->data;
			return true;
		}
		p = p->next;
		temp++;
	}
	return false;
}

//获取指定数据单链表的位置
bool LinkList::ListLocateElem(int& i, ElemType &e)
{
	Lnode *p;
	p = head->next;
	int temp = 1;
	while (p != nullptr)
	{
		if (e == p->data)
		{
			i = temp;
			return true;
		}
		temp++;
		p = p->next;
	}
	return false;
}

//在指定位置插入数据
bool LinkList::ListInsertElem(int i, ElemType &e)
{
	Lnode *p;
	p = head->next;
	int temp = 1;
	while (p != nullptr)
	{
		if (temp == i)
		{
			break;
		}
		temp++;
		p = p->next;
	}
	if (temp >= i)//找到数据位置,插入新数据
	{
		Lnode *q = new Lnode;
		q->data = e;
		q->next = p->next;
		p->next = q;
		return true;
	}
	else
	{
		return false;
	}
}

//删除指定位置的元素
bool LinkList::ListDelete(int i)
{
	Lnode *p,*q;
	p = head->next;
	int temp = 1;
	while (p != nullptr)
	{
		if (temp == i)
		{
			break;
		}
		temp++;
		p = p->next;
	}
	if (temp >= i)//找到数据位置，删除数据
	{
		q = p->next;
		p->next = q->next;
		delete q;
		return true;
	}
	else
	{
		return false;
	}
}
//头插法：创建固定长度的单链表
void LinkList::ListCreate(int i)
{
	Lnode *p,*q;
	p = head;
	int temp = 1;
	while (temp <= i)
	{
		q = new Lnode;
		cin >> q->data;
		q->next = p->next;//插入到表头
		p->next = q;
		temp++;
	}
}
//尾插法：创建固定长度的单链表
void LinkList::ListCreate(int i, int)
{
	Lnode *p, *q;
	p = head;
	int temp = 1;
	while (temp <= i)
	{
		q = new Lnode;
		cin >> q->data;
		q->next = nullptr;
		p->next = q;//插入到表尾
		p = q;//p指向新的尾节点
		temp++;
		system("cls");
	}
}

//打印单链表所有数据
void  LinkList::ListPrint()
{
	Lnode *p;
	p = head->next;
	while (p != nullptr)
	{
		cout << p->data;
		p = p->next;
	}
}
//bool ListIsEmpty();//判断链表是否为空
//void ListClear();//清空链表
//int ListLength();//获取链表长度
//bool ListGetElem(int i, ElemType &e);//获取指定位置单链表的数据
//bool ListLocateElem(int& i, ElemType &e);//获取指定数据单链表的位置
//bool ListInsertElem(int i, ElemType &e);//在指定位置插入数据
//bool ListDelete(int i);//删除指定位置的元素
//void ListCreate(int i);//头插法：创建固定长度的单链表
//void ListCreate(int i, int);//尾插法：创建固定长度的单链表
//void ListPrint();//打印单链表所有数据
void Show_Menu()
{
	cout << "****************************************************" << endl;
	cout << "1: ListCreate  2: ListDelete   3: ListInsertElem" << endl;
	cout << "4: ListLength  5: ListGetElem  6: ListPrint" << endl;
	cout << "****************************************************" << endl;
}

int main()
{
	LinkList L;
	
	//测试区域
	ElemType E,E1;
	E._mane = "张三";
	E._num = "11";
	E._score = 88;
	int num = 1;
	while (true)
	{
		//进行菜单显示
		Show_Menu();
		int select = 0;
		cout << "请输入你想操作功能的编号： ";
		cin >> select;
		switch (select)
		{
		case 0: //退出管理程序
			cout << "欢迎下次使用！" << endl;
			cout << endl;
			return 0;
		case 1:
			L.ListCreate(2);
			break;
		case 2:
			L.ListDelete(1);
			break;
		case 3:
			L.ListInsertElem(1, E);
			break;
		case 4:
			cout<<L.ListLength()<<endl;
			break;
		case 5:
			L.ListGetElem(num, E1);
			cout << E1 << endl;
			break;
		case 6:
			L.ListPrint();
			break;
		default://输入错误
			cout << endl;
			cout << "输入错误，请输入正确的功能编号!!!" << endl;
			cout << endl;
			break;
		}
		system("pause");
		system("cls");
	}
	system("pause");
	return 0;
}