当前位置:   article > 正文

数据结构——单链表基本操作实现 (c++)_c++单链表

c++单链表

单链表定义

单链表链式存储结构的特点是:用一组任意的存储单元存储线性表的数据元素(这里存储单元可以是连续的,也可以是不连续的),为了表示每个数据元素a与其直接后继数据元素之间的逻辑关系,除了存储信息本身外还要存储一个指示其直接后继的信息(地址).
这两部分信息组成数据元素a的存储映像称为结点,它包括两个域:存储信息的称为数据域,存储直接后继存储地址的域称为指针域,指针域中存储的信息称作指针.

单链表表示

可以参考下图:
在这里插入图片描述

三个需要理解的概念:

头指针:头指针是指向链表中第一个结点的指针。若链表设有头结点,则头指针所指结点为线性表的头节点;若链表没设头结点,则头指针所指结点为线性表的首元结点。

头结点:头结点是在首元结点之前附设的一个结点,该头结点指针域指向首元结点。头结点的数据域可以不存储任何信息,也可存储信息,设定头结点的目的是使链表中第一个数据(首元结点)的操作与其他数据元素的操作相同,无需进行特殊处理。

首元结点:首元结点是指链表中存储第一个数据元素a的结点。如上图所示的A。

代码实现

1.单链表存储结构和初始化操作

//单链表存储结构
struct LinkedList {
	int data;	//结点数据域(以下我用int型数据类型)
	LinkedList* next;	//结点指针域
};

//初始化操作(创建头节点)
void InitList(LinkedList*& L) {	//这里的 *& 表示对指针的引用
	L = new LinkedList;	//生成一个头节点,用头指针 L 指向头节点
	L->next = NULL;		//头指针置空(目的是为了不指向什么奇奇怪怪的地方,也为了方便对单链表基本操作实现)
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

1.单链表存储结构包括两个方面:一是该存储节点的数据域,二是该存储节点的指针域(用来指向直接后继结点的).
2. 初始化的目的时为了生成一个头结点,上面代码InitList中的形参为指针的引用类型(*&)是对指针的一个引用操作。那么为什么这个地方要用引用指针?用指针不也行吗?肯定不行,这里简单表示为p1(形参) = p2(实参),若用指针作为形参接收实参,在开辟空间 L = new LinkedList; 时,实际接收这个新开辟的空间的指针是p1而不是p2,总的来说就是我们想初始化的是实参,开辟的空间要作用于实参上就必须得用指针的引用类型.

2.前插法

//前插法(在头节点后插入 n 个结点)
void CreateList_H(LinkedList*& L, int n = 1) {	
//n 表示前插的结点数量,这里默认设置为 1
	if (n < 1){	//若传入的n小于1,出现错误
		cout << "ERROR" << endl;
		exit(0);
	}
	//逆位序插入结点
	for (int i = 0; i < n; i++) {
		LinkedList* p = new LinkedList;	//创建新结点
		cin >> p->data;
		
		//具体插入操作
		p->next = L->next; 	
		L->next = p;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

下图是单链表(c、d、e)前插过程,因为每次插入都在头结点后,所以为逆位序插入,插入顺序为e、d、c.
在这里插入图片描述

3.后插法

//后插法
void CreateList_R(LinkedList*& L, int n = 1) {
	LinkedList* r = L->next;	//创建指向尾部的指针
	while (r->next) {	//让尾指针指向链表尾部
		r = r->next;
	}
	if (n < 1) {	//若传入的n小于1,出现错误
		cout << "ERROR" << endl;
		exit(0);	//跳出程序
	}		
	for (int i = 0; i < n; i++) {
		LinkedList* p = new LinkedList;
		cin >> p->data;
		
		//具体插入操作
		p->next =r->next;
		r->next = p;
		r = p;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

下图是单链表(a、b、c)后插过程,实现该过程需要一个尾指针 r 来指向链表尾部.

4.取值、查找和显示

//取值
void GetElem(LinkedList*& L, int i, int& e) {	
//在带头节点的单链表 L 中根据序号 i 获取元素的值,用 e 返回该值
	LinkedList* p = L->next;
	int j = 1;
	while (p && j < i) {	//p不为空 && j < i
		p = p->next;
		j++;
	}
	if (!p || j > i) {	//p为空 || i小于1
		cout << "ERROR" << endl;
		exit(0);	//跳出程序
	}
	e = p->data;	//该函数形参为引用类型,所以这里的 e 改变实参也会改变
}

//查找
LinkedList* LocateElem(LinkedList*& L, int e) {	
//在带头结点的单链表 L 中查找值为 e 的元素并返回该结点地址
	LinkedList* p = L;
	while (p && p->data != e) {	//p不为空 && p数据域不等于e
		p = p->next;
	}
	return p;	//返回指针p,因为该函数返回值类型为 LinkedList* 类型
}

//显示
void ShowList(LinkedList*& L) {
	LinkedList* p = L->next;
	while (p){	//p为空时循环结束
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

5.插入(指定插入)

//插入
void ListInsert(LinkedList*& L, int i, int e) {	
//在带头节点的单链表 L 中第 i 个位置插入值为 e 的新结点
	LinkedList* p = L;
	int j = 1;	//用j来记录指针p向后移次数
	while (p && j < i) {	//p不为空 && j记录次数小于i
		p = p->next;
		j++;
	}
	if (!p || j > i) {	//p为空 || i大于1
		cout << "ERROR" << endl;
		exit(0);	//跳出程序
	}	
	LinkedList* s = new LinkedList;
	
	//具体插入操作
	s->data = e;
	s->next = p->next;
	p->next = s;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

可以参考下图:
在这里插入图片描述

6.删除

//删除
void ListDelete(LinkedList*& L, int i) {	
//在带头节点的单链表 L 中,删除第 i 个结点
	LinkedList* p = L;
	int j = 1;	//用j来记录指针p向后移次数
	while (p->next && j < i) {	//p->next不为空 && j<i
		p = p->next;
		j++;
	}
	if (!p->next || j > i) {	//p->next为空 || i大于1
		cout << "ERROR" << endl;
		exit(0);
	}
	
	//具体删除操作
	LinkedList* q = p->next;
	p->next = q->next;
	delete q;	//释放该段结点空间
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

代码源文件

下面是上诉代码集合 和 main函数测试:

#include <iostream>
using namespace std;

//单链表存储结构
struct LinkedList {
	int data;	
	LinkedList* next;	
};

//初始化操作(创建头节点)
void InitList(LinkedList*& L) {	
	L = new LinkedList;	
	L->next = NULL;		
}

//前插法(在头节点后插入 n 个结点)
void CreateList_H(LinkedList*& L, int n = 1) {	
	if (n < 1){	
		cout << "ERROR" << endl;
		exit(0);
	}
	//逆位序插入结点
	for (int i = 0; i < n; i++) {
		LinkedList* p = new LinkedList;
		cin >> p->data;
		p->next = L->next; 
		L->next = p;
	}
}

//后插法
void CreateList_R(LinkedList*& L, int n = 1) {
	LinkedList* r = L->next;	
	while (r->next) {	
		r = r->next;
	}
	if (n < 1) {	
		cout << "ERROR" << endl;
		exit(0);	
	}		
	for (int i = 0; i < n; i++) {
		LinkedList* p = new LinkedList;
		cin >> p->data;
		p->next =r->next;
		r->next = p;
		r = p;
	}
}

//取值
void GetElem(LinkedList*& L, int i, int& e) {	
	LinkedList* p = L->next;
	int j = 1;
	while (p && j < i) {	
		p = p->next;
		j++;
	}
	if (!p || j > i) {	
		cout << "ERROR" << endl;
		exit(0);
	}
	e = p->data;	
}

//查找
LinkedList* LocateElem(LinkedList*& L, int e) {	
	LinkedList* p = L;
	while (p && p->data != e) {	
		p = p->next;
	}
	return p;	
}

//插入
void ListInsert(LinkedList*& L, int i, int e) {	
	LinkedList* p = L;
	int j = 1;
	while (p && j < i) {	
		p = p->next;
		j++;
	}
	if (!p || j > i) {
		cout << "ERROR" << endl;
		exit(0);
	}
	LinkedList* s = new LinkedList;
	s->data = e;
	s->next = p->next;
	p->next = s;
}

//删除
void ListDelete(LinkedList*& L, int i) {	
	LinkedList* p = L;
	int j = 1;
	while (p->next && j < i) {
		p = p->next;
		j++;
	}
	if (!p->next || j > i) {
		cout << "ERROR" << endl;
		exit(0);
	}
	LinkedList* q = p->next;
	p->next = q->next;
	delete q;	
}

//显示
void ShowList(LinkedList*& L) {
	LinkedList* p = L->next;
	while (p){	
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}


int main() {
	//创建头指针
	LinkedList* L;

	//初始化(创建头节点,让头指针和头节点关联)
	InitList(L);

	cout << "前插:" << endl;
	CreateList_H(L, 2);
	ShowList(L);

	cout << "后插:" << endl;
	CreateList_R(L, 3);
	ShowList(L);
	
	cout << "插入元素:" << endl;
	ListInsert(L, 3, 9);
	ShowList(L);

	cout << "删除元素:" << endl;
	ListDelete(L, 2);
	ShowList(L);


	system("pause");
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146

下面是运行截图:

请添加图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/422835?site
推荐阅读
相关标签
  

闽ICP备14008679号