C++ 中循环链表和约瑟夫环

2024-02-19 15:20:06 291

循环链表和约瑟夫环

循环链表的实现

单链表只有向后结点，当单链表的尾链表不指向NULL，而是指向头结点时候，形成了一个环，成为单循环链表，简称循环链表。当它是空表，向后结点就只想了自己，这也是它与单链表的主要差异，判断node->next是否等于head。

代码实现分为四部分：

初始化
插入
删除
定位寻找

代码实现：

voidListInit(Node*pNode){
intitem;
Node*temp,*target;
cout<<"输入0完成初始化"<>item;
if(!item)
return;
if(!(pNode)){//当空表的时候，head==NULL
pNode=newNode;
if(!(pNode))
exit(0);//未成功申请
pNode->data=item;
pNode->next=pNode;
}
else{
//
for(target=pNode;target->next!=pNode;target=target->next)
;
temp=newNode;
if(!(temp))
exit(0);
temp->data=item;
temp->next=pNode;
target->next=temp;
}
}
}
voidListInsert(Node*pNode,inti){//参数是首节点和插入位置
Node*temp;
Node*target;
intitem;
cout<<"输入您要插入的值:"<>item;
if(i==1){
temp=newNode;
if(!temp)
exit(0);
temp->data=item;
for(target=pNode;target->next!=pNode;target=target->next)
;
temp->next=pNode;
target->next=temp;
pNode=temp;
}
else{
target=pNode;
for(intj=1;jnext;
temp=newNode;
if(!temp)
exit(0);
temp->data=item;
temp->next=target->next;
target->next=temp;
}
}
voidListDelete(Node*pNode,inti){
Node*target,*temp;
if(i==1){
for(target=pNode;target->next!=pNode;target=target->next)
;
temp=pNode;//保存一下要删除的首节点,一会便于释放
pNode=pNode->next;
target->next=pNode;
deletetemp;
}
else{
target=pNode;
for(intj=1;jnext;
temp=target->next;//要释放的node
target->next=target->next->next;
deletetemp;
}
}
intListSearch(Node*pNode,intelem){//查询并返回结点所在的位置
Node*target;
inti=1;
for(target=pNode;target->data!=elem&&target->next!=pNode;++i)
target=target->next;
if(target->next==pNode&&target->data!=elem)
return0;
elsereturni;
}

约瑟夫问题

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。这类问题用循环列表的思想刚好能解决。

注意：编写代码的时候，注意报数为m=1的时候特殊情况

#include
#include
usingnamespacestd;
typedefstructNode{
intdata;
Node*next;
};

Node*Create(intn){
Node*p=NULL,*head;
head=newNode;
if(!head)
exit(0);
p=head;//p是当前指针
intitem=1;
if(n){
inti=1;
Node*temp;
while(i<=n){
temp=newNode;
if(!temp)
exit(0);
temp->data=i++;
p->next=temp;
p=temp;
}
p->next=head->next;
}
deletehead;
returnp->next;
}
voidJoseph(intn,intm){
//n为总人数，m为数到第m个的退出
m=n%m;

Node*start=Create(n);

if(m){//如果取余数后的m!=0，说明m!=1
while(start->next!=start){
Node*temp=newNode;
if(!temp)
exit(0);
for(inti=0;inext;
temp=start->next;
start->next=start->next->next;
start=start->next;
cout<data<<"";
deletetemp;
}
}
else{
for(inti=0;idata<<"";
temp=start;
start=start->next;
deletetemp;
}
}
cout<data<
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

C++ 中循环链表和约瑟夫环

热门推荐

随机推荐