|
文章目录
链表①简单strcut版的链表②使用构造函数初始化结点的链表1. 约瑟夫问题解法——链表
2. 队列安排题解——链表
链表
C++关于链表
①简单strcut版的链表
#include
using namespace std;
struct ListNode
{
double value;
ListNode* next;
};
int main()
{
ListNode* head = nullptr; //头结点
// 头结点的初始化
head = new ListNode;
head->value = 0;
head->next = nullptr;
// 尾插法
ListNode* tmp = head;
for (int i = 1; i
ListNode* newPtr = new ListNode;
newPtr->value = i;
head->next = newPtr;
newPtr->next = tmp;
tmp = head->next;
}
// 遍历链表
tmp = head;
while (tmp != nullptr) {
cout
cout
cout
cout next = newPtr;
break;
}
tmp = tmp->next;
}
// 再遍历链表输出
tmp = head;
while (tmp != nullptr) {
cout
value = value1; next = next1;
}
};
int main()
{
ListNode* numberList = new ListNode(0); //尾结点及初始化
// 创建链表（本质是头插法）
for (int i = 1; i
cout
int n, m;
cin >> n >> m;
ListNode* head = nullptr; //头结点
// 头结点的初始化
head = new ListNode;
head->value = 0;
head->next = nullptr;
// 尾插法
ListNode* tmp = head;
for (int i = 1; i
// 遍历链表，删除所有序号为m的倍数的结点
tmp = head;
while (tmp->next != nullptr) {
if (num % m == 0) {
cout value next->next;
num = 0; // 重新开始报数
}
else {
tmp = tmp->next;
}
num++;
}
tmp = head;
}
return 0;
}
2. 队列安排
题目描述
一个学校里老师要将班上
N
N
N 个同学排成一列，同学被编号为
1
∼
N
1\sim N
1∼N，他采取如下的方法：
先将
1
1
1 号同学安排进队列，这时队列中只有他一个人；
2
−
N
2-N
2−N 号同学依次入列，编号为
i
i
i 的同学入列方式为：老师指定编号为
i
i
i 的同学站在编号为
1
∼
(
i
−
1
)
1\sim(i-1)
1∼(i−1) 中某位同学（即之前已经入列的同学）的左边或右边； 从队列中去掉
M
(
M
<
N
)
M(M
int k, p;
scanf("%d%d", &k, &p);
if (p == 0)
{
pos[i] = queList.insert(pos[k], i); //left
}
else
{
auto nextIter = next(pos[k]);
pos[i] = queList.insert(nextIter, i); //right
}
}
int M;
scanf("%d", &M);
for (int x, i = 1; i
queList.erase(pos[x]);
}
erased[x] = true;
}
}
int main()
{
scanf("%d", &N);
buildQueue();
bool first = true;
for (int x: queList)
{
if (!first)
putchar(' ');
first = false;
printf("%d", x);
}
putchar('\n');
return 0;
}
|