笔记
2024-07-30 13:10:39
发布于：上海
21阅读
0回复
0点赞
这里什么都没有
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
#include <bits/stdc++.h>
using namespace std;
struct node { //链表中的一个节点
int data; //节点本身数据信息
node *next; //指向下一个节点
};
node *head, *tail; //头指针、尾指针
void print_lst() {
node *step = head; //再找一个指针指向遍历的起点
while (step) { //当节点不为空时，持续遍历链表
cout << step->data << ' '; //访问节点信息
step = step->next; //指向下一个节点
}
}
void append_data(int x) {
if (tail == NULL) { //当尾结点（链表）为空时
head = tail = new node; //头尾结点都为空，申请新的空间
} else { //当链表不为空的时候
node *new_node = new node; //创建新的节点，申请空间
tail->next = new_node; //将新的节点连接到链表尾部
tail = new_node; // 更新尾指针
}
tail->data = x; //存储数据
tail->next = NULL; //尾结点next为空
}
void insert_node(node *p, int d) { //在p的后面之为d的节点
node *new_node = new node; //创建新节点，申请空间
new_node->data = d; //存储数据
new_node->next = p->next; //新节点的next，指向p的下一个节点
p->next = new_node; //p的next指向新节点
}
void del_data(int d) { //删除链表当中值为d的节点
node *step = head; //再找一个指针指向链表的起点
if (step == NULL) return ; //链表为空时，无法删除，直接结束
if (step->data == d) { // 当头节点需要被删除时
head = head->next; //更新头指针的指向
delete step; //释放空间
} else {
while (step->next) {
//当下一个节点不为空时，持续遍历
if (step->next->data == d) { //找到要删除的节点时
node *del = step->next; //del指向要删除的节点
if (tail == del) //删除的是尾结点
tail = step; //跟新尾指针的指向
step->next = step->next->next; //更新小箭头指向
delete del; //释放空间
break; //删除完成
}
step = step->next; //step指向下一个节点
}
}
}
int main () {
head = tail = NULL;
append_data(3);
append_data(3);
append_data(0);
append_data(9);
print_lst();
cout << endl;
node *step = head;
while (step) {
if (step->data == 3) {
insert_node(step, 5);
step = step->next;
}
step = step->next;
}
print_lst();
cout << endl;
del_data(5);
print_lst();
cout << endl;
return 0;
}
没记完
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
node *next, *prev;//指向上/下一个节点
};
node *head, *tail;
void print_lst() {//同单项链表
node *step = head;
while (step) {
cout << step->data << ' ';
step = step->next;
}
}
void print_lst_re() {//倒序输出链表
node *step = tail;//倒序遍历，从尾结点开始
while (step) {
cout << step->data << " ";
step = step->prev;//指向上一个节点
}
}
void append_data(int x) {//在链表尾部插入值为k的节点
if (tail == NULL) {//链表为空
head = tail = new node;
tail->data = x;
tail->prev = NULL;//此时链表只有一个节点 ，prev指向NULL
tail->next = NULL;//next也指向NULL
} else {//链表不为空
node *new_node = new node;//创建新节点，申请空间
new_node->data = x;
new_node->next = tail->next;//新节点的next指向为空
new_node->prev = tail;//新节点的prev指向tall
tail->next = new_node;//tail的next指向新节点
tail = new_node;//更新尾指针的指向
}
}
void insert_node(node *p, int d) {//在p的后面插入为d的节点
node *new_node = new node;//创建新节点，申请空间
new_node->data = d;//给新节点赋值
new_node->next = p->next;//新节点的next指向p的next
p->next = new_node;//p的next指向
new_node->prev = p;//新节点的prev指向节点p
if (p == tail)//如果p是尾结点
tail = new_node;//更新尾指针
else//p不是尾结点
new_node->next->prev = new_node;//新节点next(p节点原来的next)的prev指向新节点
}
void del_data(int d) {//删除链表中，值为d的第一个节点
node *step = head;
if (step == NULL) return ;//如果链表为空，持续遍历
while (step!=NULL) {//当step不为空时，直接结束
if (step->data == d) {//当找到值
if (step == head) {//要删除的为头结点
head = head->next;//更新头指针的指向
if (head == NULL) {//如果删除后链表为空
tail = NULL;//将尾指针也设置为NULL
} else {//如果删除后链表为不空
head->prev = NULL;//将头指针的prev指向NULL
}
delete step;//释放空间
} else if (step == tail) {//要删除的为尾结点
tail = tail->prev;//更新尾指针
if (tail == NULL) {//
head = NULL;//
} else {//
tail->next = NULL;//
}
delete step;//
} else {
step->prev->next = step->next;
step->next->prev = step->prev;
delete step;
}
break;
}
step = step->next;//
}
}
int main () {
head = tail = NULL;//初始时，链表为空，头尾指针指向NULL
append_data(1);
append_data(2);
append_data(3);
append_data(4);
print_lst();
cout << endl;
print_lst_re();
cout << endl;
node *step = head;
while (step) {
if (step->data == 3) {
insert_node(step, 5);
step = step->next;
}
step = step->next;
}
print_lst();
cout << endl;
print_lst_re();
cout << endl;
del_data(4);
print_lst();
cout << endl;
print_lst_re();
cout << endl;
return 0;
}
有帮助，赞一个