数据结构-单链表(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&&j<i-1)//查找位置为i-1的结点，p指向该结点
{
p = p->next;
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 << "此链表为空"<<endl; return; }
p = L->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<iostream>
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&&j<i-1)//查找位置为i-1的结点，p指向该结点
{
p = p->next;
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 << "此链表为空"<<endl; return; }
p = L->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<< "个元素的值获取失败！" << endl;
}
//7.单链表按值查找
int index = 0;
cout << "输入你要查询值的位置：";
cin >> n;
if (Linklist_FindElement(L, n, index)){
cout<<"你查询值为"<<n<<"的位置为"<<index<<endl;
}
else {
cout << "你查询值为" << n << "的位置为" << index << endl;
}
//8.单链表的删除元素
cout << "请输入你要删除第几个元素:";
cin >> n;
if (LinklistDelete(L, n)) {
cout << "删除第" << n << "元素成功!" << endl;
LinkPrint(L);
}
else {
cout << "删除第" << n << "元素失败!" << endl;
}
//9.销毁单链表
LinklistDestroy(L);
system("pause");
return 0;
}
总结
以上就是今天要讲的内容，本文介绍了单链表的创建等一系列操作，本人小白，如有错误，欢迎大佬们指点出来。
华为开发者空间，是为全球开发者打造的专属开发空间，汇聚了华为优质开发资源及工具，致力于让每一位开发者拥有一台云主机，基于华为根生态开发、创新。
更多推荐
32
1- 0
已为社区贡献2条内容
所有评论(0)