数据结构-单链表(c++)超全超详细

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
一、单链表是什么？
二、单链表上基本操作的实现
- 1.定义单链表
- 2.单链表初始化
- 3.头插法
- 4.尾插法
- 5.任意位置插入
- 6.按位取值
- 7.按值取位
- 8.删除结点
- 9.打印链表
- 10.销毁链表
三、完整代码(功能过多，建议注释一部分使用)
总结

前言

顺序表可以随时存取表中的任意一个元素，它的存储位置可以用一个简单直观的公式表示，但插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用地址的连续存储单元，即不要求逻辑上相邻元素在物理地址上也相邻，它通过“链”建立起数据元素之间的逻辑关系，因此插入和删除元素操作不需要移动元素，而只需要修改指针，但也会失去顺序表可随机存取的优点

提示：以下是本篇文章正文内容，下面案例可供参考

一、单链表是什么？

**线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。**为了建立数据元素之间的线性关系，对每个链表结点，出存放元素自身信息外，还需要存放一个指向其后继的指针。

二、单链表上基本操作的实现 1.定义单链表

代码如下（示例）：

typedef struct _linkNode {

	int data; //结点的数据域

	struct _linkNode* next;//结点的指针域

}linkNode, linklist;

2.单链表初始化

代码如下（示例）：

bool InitList(linklist* &L) {

	L = new linkNode;

	if (!L) return false;//生成结点失败

	L->next = NULL;
	
	return true;
}

3.头插法

代码如下（示例）：

bool ListInsert_front(linklist* &L, linkNode* node) {

	if (!L || !node) return false;

	node->next = L->next;
	L->next = node;

}

4.尾插法

代码如下（示例）：

bool ListInsert_back(linklist* &L, linkNode* node) {

	linkNode* last = NULL;
	if (!L || !node) return false;
	last = L;
	while (last->next) {
		last = last->next;
	}
	node->next = NULL;
	last->next = node;
	return true;
}

5.任意位置插入

代码如下（示例）：

bool ListInsert(linklist* &L,int i,int e) {

	if (!L)return false;

	int j = 0;
	linklist* p, * s;
	p = L;

	while (p&&jnext;
		j++;
	}

	if (!p || j > i - 1) {
		return false;
	}

	s = new linkNode;//生成新结点
	s->data = e;
	s->next = p->next;
	p->next = s;
}

6.按位取值

代码如下（示例）：

bool link_GetElem(linklist*& L, int i, int& e) {

	//在带头节点的单链表L中查找第i个元素
	//用e记录L中第i个元素的值
	int index;
	linklist* p;
	if (!L || !L->next) return false;

	p = L->next;
	index = 1;
	while (p && index < i) {//链表向后扫描，直到p指向第i个元素或者p为空
		p = p->next;
		index++;
	}
	if (!p || index > i) return false;//i值不合法，i>n或i<=0;

	e = p->data;
	return true;
}

7.按值取位

代码如下（示例）：

bool linklist_FindElement(linklist* L,int e,int& index) {

	//在带头结点的单链表L中查找值为e的元素位置
	linklist* p;
	p = L->next;
	index = 1;

	if (!L || !L->next) {
		index = -1;
		return false;
	}

	while (p&&p->data!=e) {
		p = p->next;
		index++;
	}

	if (!p) {
		index = -1;
		return false;//查找结点不存在
	}

	return true;
}

8.删除结点

代码如下（示例）：

bool linklistDelete(linklist* L, int i) {

	linklist* p,*q;
	p = L;
	int index = 0;

	if (!L || !L->next) return false;

	while ((p->next) && (index < i - 1)) {
		index++;
		p = p->next;
	}

	if (!p->next || index > i - 1) return false;

	q = p->next;		//临时保存被删结点的地址以备释放空间
	p->next = q->next;	//改变删除结点前驱结点的指针域
	delete q;			//释放被删除结点的空间

	return true;
}

9.打印链表

代码如下（示例）：

void linkPrint(linklist* &L) {

	linkNode* p = NULL;
	if (!L) { cout << "此链表为空"<next;

	while (p) {
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

10.销毁链表

代码如下（示例）：

void linklistDestroy(linklist*& L) {
	
	linklist* p=L;
	cout << "销毁链表" << endl;
	
	while (p) {
		L = L->next; //L指向下一个结点
		delete p;   //删除当前结点
		p = L;     //p移向下一个结点
	}

}

三、完整代码(功能过多，建议注释一部分使用)

代码如下（示例）：

#include
using namespace std;

typedef struct _linkNode {

	int data; //结点的数据域

	struct _linkNode* next;//结点的指针域

}linkNode, linklist;


bool InitList(linklist* &L) {

	L = new linkNode;

	if (!L) return false;//生成结点失败

	L->next = NULL;
	
	return true;
}


//前插法
bool ListInsert_front(linklist* &L, linkNode* node) {

	if (!L || !node) return false;

	node->next = L->next;
	L->next = node;

}


//尾插法
bool ListInsert_back(linklist* &L, linkNode* node) {

	linkNode* last = NULL;
	if (!L || !node) return false;
	last = L;
	while (last->next) {
		last = last->next;
	}
	node->next = NULL;
	last->next = node;
	return true;
}


//任意位置插入
bool ListInsert(linklist* &L,int i,int e) {

	if (!L)return false;

	int j = 0;
	linklist* p, * s;
	p = L;

	while (p&&jnext;
		j++;
	}

	if (!p || j > i - 1) {
		return false;
	}

	s = new linkNode;//生成新结点
	s->data = e;
	s->next = p->next;
	p->next = s;
}


//单链表按位置取值
bool link_GetElem(linklist*& L, int i, int& e) {

	//在带头节点的单链表L中查找第i个元素
	//用e记录L中第i个元素的值
	int index;
	linklist* p;
	if (!L || !L->next) return false;

	p = L->next;
	index = 1;
	while (p && index < i) {//链表向后扫描，直到p指向第i个元素或者p为空
		p = p->next;
		index++;
	}
	if (!p || index > i) return false;//i值不合法，i>n或i<=0;

	e = p->data;
	return true;
}


//单链表按值查找
bool linklist_FindElement(linklist* L,int e,int& index) {

	//在带头结点的单链表L中查找值为e的元素位置
	linklist* p;
	p = L->next;
	index = 1;

	if (!L || !L->next) {
		index = -1;
		return false;
	}

	while (p&&p->data!=e) {
		p = p->next;
		index++;
	}

	if (!p) {
		index = -1;
		return false;//查找结点不存在
	}

	return true;
}


//单链表的删除
bool linklistDelete(linklist* L, int i) {

	linklist* p,*q;
	p = L;
	int index = 0;

	if (!L || !L->next) return false;

	while ((p->next) && (index < i - 1)) {
		index++;
		p = p->next;
	}

	if (!p->next || index > i - 1) return false;

	q = p->next;		//临时保存被删结点的地址以备释放空间
	p->next = q->next;	//改变删除结点前驱结点的指针域
	delete q;			//释放被删除结点的空间

	return true;
}


//单链表打印
void linkPrint(linklist* &L) {

	linkNode* p = NULL;
	if (!L) { cout << "此链表为空"<next;

	while (p) {
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}


//销毁单链表
void linklistDestroy(linklist*& L) {
	
	linklist* p=L;
	cout << "销毁链表" << endl;
	
	while (p) {
		L = L->next; //L指向下一个结点
		delete p;   //删除当前结点
		p = L;     //p移向下一个结点
	}

}



int main() {
	int n;
	linklist* L=NULL;
	linklist* s = NULL;


	//1.初始化一个空的链表
	InitList(L);


	//2.使用前插法插入数据
	cout << "前插法创建单链表" << endl;
	cout << "请输入插入的个数n:";
	cin >> n;

	while (n > 0) {
		s = new linkNode;//生成新结点s
		cin >> s->data;
		ListInsert_front(L, s);
		n--;
	}


	//3.使用尾插法插入数据
	cout << "尾插法创建单链表" << endl;
	cout << "请输入插入的个数n:";
	cin >> n;

	while (n > 0) {
		s = new linkNode;//生成新结点s
		cin >> s->data;
		ListInsert_back(L, s);
		n--;
	}
	

	//4.单链表的输出
	linkPrint(L);


	//5.任意位置插入元素
	for (int j = 0; j < 3; j++) {
		int i, x;
		cout << "请输入插入元素的位置及值：";
		cin >> i >> x;
		if (ListInsert(L, i, x)) {
			cout << "插入成功" << endl;
		}
		else {
			cout << "插入失败" << endl;
		}
		linkPrint(L);
	}


	//6.单链表取值
	int element;  
	cout << "请输入你要获取值的位置" ;
	cin >> n;
	if (link_GetElem(L, n, element)) {
		cout << "第" << n << "元素的值为：" << element << endl;
	}
	else {
		cout << "第" <> n;
	if (linklist_FindElement(L, n, index)){
		cout<<"你查询值为"<> n;
	if (linklistDelete(L, n)) {
		cout << "删除第" << n << "元素成功!" << endl;
		linkPrint(L);
	}
	else {
		cout << "删除第" << n << "元素失败!" << endl;
	}


	//9.销毁单链表
	linklistDestroy(L);


	system("pause");
	return 0;
}

总结以上就是今天要讲的内容，本文介绍了单链表的创建等一系列操作，本人小白，如有错误，欢迎大佬们指点出来。

数据结构-单链表(c++)超全超详细

C/C++/C#相关栏目本月热门文章