C++使用单向循环链表解决
需要实现节点的插入和删除
——我为++做实事
1 、节点定义:
struct node
{
int number; // 表示序号
node *next;
};
2 、节点的插入:
为每个节点(人)发放生死序号:index
考虑链表为空和不为空的情况
void insert_Node(node *&head, int index)
{
node *newNode = new node;
// 如果链表为空
if (head == nullptr)
{
newNode->number = index;
newNode->next = newNode; // next指针指向自己
head = newNode; // 把自己设为头节点
}
else
{
newNode->number = index;
newNode->next = head; // next指针指向头节点
node *N = find_tail(head);
N->next = newNode; // 尾节点的next指向自己
}
}
3 、删除节点的操作:
当我们删除链表中的节点时,一般只需要修改附近节点的 next 指针即可,不过此题使用了 new 来分配空间,所以还需要 delete 掉节点,防止内存泄漏。如果用数组模拟链表就不用考虑真的“删除”节点这个问题。
3 .1 有以下几种情况:
如果是头节点
是否有且只有头节点
除了头节点还有其他节点
如果不是头节点
3.2 需要注意释放内存
delete node
代码:
void del_Node(node *&head, node *victim)
{
if (victim == head) // 如果删除的是头节点
{
node *tail = find_tail(head);
if (head == tail) // 链表只有一个节点
{
delete head; // 释放内存
head = nullptr; // 设置为空
}
else // 除了头节点还有其他节点
{
head = head->next; // 修改头节点
tail->next = head; // 尾节点指向新的头节点
delete victim; // 释放内存
}
}
else // 删的不是头节点
{
node *before_victim = head;
while (before_victim->next != victim)
before_victim = before_victim->next;
before_victim->next = victim->next; // 删除 victim,修改前面节点的next指针
delete victim; // 释放内存
}
}
4. Main 函数
一定要初始化头节点为空,作为链表的一个标志
代码逻辑:
为 30 个人发号码牌
循环 15 次,每次丢出去一个人(好残忍)
每次从当前的人这里,往前走 8 步,找到 victim
删除 victim
指针移动到这个 victim 下一位,下次循环就从这人开始,继续走 8 步……
代码:
int main()
{
node *head = nullptr; // 一定要初始化头节点为空
for (int i = 1; i <= 30; i++)
insert_Node(head, i);
int all_people = 30, half_people = all_people / 2;
node *victim = head;
while (half_people--)
{
for (int i = 0; i < 8; i++)
victim = victim->next;
cout << victim->number << " ";
node *next_vic = victim->next;
del_Node(head, victim);
victim = next_vic;
cout << endl;
// print(head);
}
return 0;
}
最后是些无关紧要的辅助函数
1、find_tail 函数
// 返回链表最后一个节点的指针
node *find_tail(node *head)
{
node *N = head;
while (N->next != head) // find尾节点
{
N = N->next;
}
return N;
}
2、打印链表函数(debug 用可删)
// 打印当前剩下的所有人
void print(node *head)
{
node *c = head;
if (c == nullptr)
return; // 空链表处理
do
{
cout << c->number << " ";
c = c->next;
} while (c != head); // 打印直到头节点
cout << endl;
}
小韩碎碎念 —有些 bug 值得注意:
1、对于链表的修改,包括插入和删除,传进函数一定要用 &
,引用传递,否则只会在函数内部修改,不会对原始链表有任何影响。
2、关于 while 和 do-while 的一个 bug:
源代码:
void print(node * head)
{
node *c = head;
while(c->next != head)
cout << c->number << " ";
}
问题:
print
函数的逻辑问题: print
函数缺少打印链表最后一个节点的代码,因为它只循环到 c->next != head
,而没有打印尾节点。因此,你会错过打印最后一个节点
改成 do-while 循环后的代码:
void print(node * head)
{
node *c = head;
if (c == nullptr)
return; // 空链表处理
do
{
cout << c->number << " ";
c = c->next;
} while (c != head); // 打印直到头节点
cout << endl;
}
标签:node,head,游戏,victim,next,链表,死者,约瑟夫,节点
From: https://www.cnblogs.com/yuxiyuxi/p/18534827