当前位置：网站首页>双向链表的各种操作
双向链表的各种操作
2022-08-09 10:59:00 【誰能久伴不乏】
双向链表的各种操作
运行环境:VS2022 X64
#include <iostream>
#include <Windows.h>
using namespace std;
//双向链表的结构体定义
typedef struct _LinkNode {
int data; //数据域
struct _LinkNode* next; //指向下一个节点的指针域
struct _LinkNode* prev; //指向上一个节点的指针域
}LinkList, LinkNode;
//初始化双向链表
bool DbInit_List(LinkList*& L) {
//构造一个空的双向链表
L = new LinkNode; //生成新结点作为头结点，用头指针 L 指向头结点
if (!L) {
cout << "头结点生成失败!" << endl; return false; }
L->next = NULL;
L->prev = NULL;
L->data = -1;
return true;
}
//双向链表前插法
bool DbListInster_front(LinkList*& L, LinkNode* node) {
if (!L || !node) {
return false; }
//只有头结点
if (L->next == NULL) {
node->next = NULL;
node->prev = L; //插入节点的前置指针域指向头结点
L->next = node; //头节点的后置指针域指向插入的节点
}
else {
L->next->prev = node; //把插入节点的后一个节点的前置节点指向自己
node->next = L->next; //把插入的节点的后置指针域指向下一个节点
node->prev = L; //把自己的前置指针指向上一个节点
L->next = node; //把前一个节点的的后置指针,指向自己
}
return true;
}
//双向链表尾插法
bool DbListInster_back(LinkList*& L, LinkNode* node) {
if (!L || !node) {
return false; }
LinkNode* last = NULL; //用于遍历链表
last = L;
while (last->next) last = last->next; //遍历链表,找到尾部
node->next = NULL; //把自己的后置指针,置为空,因为是尾插法,后面没得节点
node->prev = last; //把自己的前置指针域指向上一个节点
last->next = node; //把前一个节点的后置指针域指向自己
return true;
}
//双链表任意位置插入
bool DbLink_Inster(LinkList*& L, int i, int &e) {
//i是插入的位置,e是插入的数据
if (!L || !L->next) {
return false; }
if (i < 1) {
cout << "插入的位置不能小于1!" << endl; return false; }
int j = NULL;
LinkList* p = NULL, * s = NULL;
p = L;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j != i) {
cout << "节点不存在!" << endl; return false; }
s = new LinkNode;
s->data = e;
s->next = p; //把插入节点的后置指针域指向,后面一个节点
s->prev = p->prev; //把插入节点的前置指针域指向,前一个节点
/* p->prev->next = s; //把前一个节点的后置指针域指向自己 p->prev = s; //把后面一个节点的前置指针域指向自己 bug记录: 这里如果这样写就会出现错误 p->prev = s; p->prev->next = s; 因为先把p->prev改成了s 导致p->prev->next = s;的时候,p->prev 已经被修改过了,就是访问自己了 所以要注意修改的先后顺序 */
p->prev->next = s; //把前一个节点的后置指针域指向自己
p->prev = s; //把后面一个节点的前置指针域指向自己
return true;
}
//双向链表的遍历
void DbLink_print(LinkList*& L) {
LinkNode* p = NULL;
if (!L) {
cout << "链表为空!" << endl; return; }
p = L;
cout << "正序打印:";
while (p->next) {
cout << p->next->data << " ";
p = p->next;
}
cout << endl;
cout << "逆序打印:";
while (p!=L) {
cout << p->data << " ";
p = p->prev;
}
cout << endl;
}
//双向链表获取元素
bool DbLink_GetElem(LinkList*& L, int i, int& e) {
//i查询的节点,e查询节点的数据域
if (!L || !L->next) {
return false; }
int index = NULL;
LinkList* p = NULL;
p = L->next; //头结点的后一个节点
index = 1; //这里随着头结点+1
while (p && index < i) {
p = p->next;
index++;
}
if (!p || index > i) {
return false; }
e = p->data;
return true;
}
//双链表删除节点
bool DbLink_Delete(LinkList*& L, int i) {
//i被删的位置
LinkList* p = NULL;
int index = NULL;
if (!L || !L->next) {
cout << "双向链表为空!" << endl; return false; }
if (i < 1) {
cout << "不能删除头结点!" << endl; return false; }
p = L;
while (p && index < i) {
p = p->next;
index++;
}
if (!p) {
return false; }
p->prev->next = p->next; //把被删除节点前一个节点的后置指针域指向被删除节点的后一个节点
if (p->next) {
//如果p不是最后一个节点
p->next->prev = p->prev; //把被删除节点的后一个节点的前置指针域指向,被删除节点的前一个节点
}
delete p;
return true;
}
//双链表按数据域查找
bool Link_FindElem(LinkList*& L, int& i) {
//查找的数据
if (!L || i == -1) {
return false; }
LinkList* p = NULL;
p = L;
while (p->next) {
if (p->data == i) {
return true;
}
p = p->next;
}
return false;
}
bool ListAmend(LinkList*& L, int i, int j) {
//i查找的位置 j需要修改的数据
if (!L || !L->next) {
return false; }
if (i < 1) {
cout << "不能查询比1小的节点!" << endl;
return false;
}
LinkNode* p = L;
int index = NULL;
while (p->next && index<i) {
p = p->next;
index++;
}
p->data = j;
return true;
}
//双向链表的销毁
void DbLink_Destroy(LinkList*& L) {
LinkNode* p = L; //定义临时节点 p 指向头节点
cout << "销毁链表!" << endl;
while (p) {
L = L->next; //L 指向下一个节点
cout << "删除元素:" << p->data << endl;
delete p; //删除当前节点
p = L; //p 移向下一个节点
}
}
void ListInstrt_back1(LinkList*& L) {
int e = NULL;
LinkList* s2 = NULL;
cout << "请输入需要插入的个数(尾插法):";
cin >> e;
while (e > 0) {
s2 = new LinkNode;
cout << "请输入数据:";
cin >> s2->data;
if (DbListInster_back(L, s2)) {
cout << "插入成功!!" << endl;
e--;
}
else {
cout << "插入失败!!" << endl;
return;
}
}
DbLink_print(L);
}
void ListInstrt_front1(LinkList*& L) {
LinkList* s2 = NULL;
int e = NULL;
cout << "请输入需要插入的个数(前插法):";
cin >> e;
while (e > 0) {
s2 = new LinkNode;
cout << "请输入数据:";
cin >> s2->data;
if (DbListInster_front(L, s2)) {
cout << "插入成功!!" << endl;
e--;
}
else {
cout << "插入失败!!" << endl;
return;
}
}
DbLink_print(L);
}
void LinkInsert1(LinkList*& L) {
int e = NULL;
int b = NULL;
cout << "请输入插入的个数:";
cin >> b;
while (b > 0) {
int a = NULL;
e = NULL;
cout << "当前数据:" << endl;
DbLink_print(L);
cout << "请输插入的位置和数据(空格隔开):";
cin >> a >> e;
if (DbLink_Inster(L, a, e)) {
cout << "插入成功!!" << endl;
DbLink_print(L);
b--;
}
else {
cout << "插入失败!!" << endl;
return;
}
}
}
void Link_GetElem1(LinkList*& L) {
int i = NULL;
int e1 = NULL;
while (true) {
cout << "请输入需要查询的节点(按0退出):";
cin >> i;
if (i == 0) {
break; }
if (DbLink_GetElem(L, i, e1)) {
cout << "节点的数据域值是:" << e1 << endl;
}
else {
cout << "该值不存在" << endl;
}
}
}
void Link_FindElem1(LinkList*& L) {
while (true) {
int i = NULL;
cout << "请输入需要查询的值(输入0结束):";
cin >> i;
if (i == 0) {
break; }
if (Link_FindElem(L, i)) {
cout << "查找的:" << i << "存在!" << endl;
}
else {
cout << "查找的:" << i << "不存在!" << endl;
}
}
}
void ListAmend(LinkList*& L) {
while (true) {
int x = NULL;
int y = NULL;
cout << "请输入需要修改数据的节点,以及修改的数据(空格隔开,按 0 空格 0 回车结束):";
cin >> x >> y;
if (x == 0) {
break; }
if (ListAmend(L, x, y)) {
cout << "修改成功!!" << endl;
DbLink_print(L);
}
else {
cout << "修改失败!!" << endl;
return;
}
}
}
void LinkDelete1(LinkList*& L) {
while (true) {
int a = NULL;
cout << "请输入需要删除的节点(按0结束):";
cin >> a;
if (a == 0) {
break; }
if (DbLink_Delete(L, a)) {
cout << "删除成功!!" << endl;
DbLink_print(L);
}
else {
cout << "删除失败!!" << endl;
}
}
}
void function() {
LinkList* s1; //头结点
DbInit_List(s1); //初始化一个空的双向链表
while (true) {
int x = NULL;
string str[]{
" 双向链表 \n"
"1.插入数据(尾插法) \n"
"2.插入数据(前插法) \n"
"3.任意位置插入数据 \n"
"4.按节点查询数据 \n"
"5.查询数据是否存在 \n"
"6.修改任意节点的数据 \n"
"7.查看链表中的数据 \n"
"8.删除任意节点 \n"
"9.销毁链表 \n"
"10.退出 \n"
};
cout << *str << endl;
cout << "请输入需要执行的操作:";
cin >> x;
if (x <= 0 || x > 11) {
cout << "条件不成立!!" << endl; return; }
switch (x) {
case 1:
ListInstrt_back1(s1);
system("pause");
break;
case 2:
ListInstrt_front1(s1);
system("pause");
break;
case 3:
LinkInsert1(s1);
system("pause");
break;
case 4:
Link_GetElem1(s1);
system("pause");
break;
case 5:
Link_FindElem1(s1);
system("pause");
break;
case 6:
ListAmend(s1);
system("pause");
break;
case 7:
cout << "链表中的所有数据" << endl;
DbLink_print(s1);
system("pause");
break;
case 8:
LinkDelete1(s1);
system("pause");
break;
case 9:
cout << "销毁链表后,就无法进行任何对链表的操作!!" << endl;
DbLink_Destroy(s1);
system("pause");
break;
case 10:
exit(0);
break;
default:
break;
}
system("cls");
}
}
int main(void) {
function();
return 0;
}
边栏推荐
- Preparation for gold three silver four: how to successfully get an Ali offer (experience + interview questions + how to prepare)
- faster-rcnn learn
- 微信小程序——天气查询
- MATLAB中如何把cftool拟合的函数输出到命令行（解决如何导出拟合后的曲线数据）
- AQS同步组件-ForkJoin、BlockingQueue阻塞队列解析和用例
- b站up主：空狐公子 --矩阵求导（分母布局）课程笔记
- Shell script combat (2nd edition) / People's Posts and Telecommunications Press Script 1 Find programs in the PATH
- 山东招远通报星童幼儿园食品安全问题最新调查情况
- 研发需求的验收标准应该怎么写？ | 敏捷实践
- AQS同步组件-FutureTask解析和用例
猜你喜欢
![[Original] Usage of @PrePersist and @PreUpdate in JPA](/img/a0/5aebdef4a12fe55b4782b69e39b817.png)
随机推荐
golang源代码阅读，sync系列-Pool
Multi-merchant mall system function disassembly 26 lectures - platform-side distribution settings
1008 Elevator (20分)
乘积量化（PQ）
PoseNet: A Convolutional Network for Real-Time 6-DOF Camera Relocalization论文阅读
华为VRRP+MSTP联动接口检测实验案例
一键完成物联网产品注册，快速体验在线调试设备
threejs+shader 曲线点运动,飞线运动
支付宝小程序的接入
jvm-类加载系统
leetcode-搜索旋转排序数组-33
FreeRTOS列表和列表项源码分析
Official explanation, detailed explanation and example of torch.cat() function
WebSocket
Error: Cannot find module ‘./application‘
golang runtime Caller、Callers、CallersFrames、FuncForPC、Stack作用
MySQL查询性能优化七种武器之索引潜水
使用pip成功安装某个库，但pycharm中找不到，此问题的解决方案
【VIBE: Video Inference for Human Body Pose and Shape Estimation】论文阅读
tensorflow和numpy对应的版本,报FutureWarning: Passing (type, 1) or ‘1type‘ as a synonym of type is deprecate