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

发布时间:2024年01月04日

?前言:此文章是介绍线性表中单链表的实现,参考视频数据结构与算法——第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;
}

文章来源:https://blog.csdn.net/angelxiaolei/article/details/135313963
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。