当前位置：首页 > news >正文

【C语言】约瑟夫环，循环链表实现

news 来源：原创 2024/9/20 8:14:55

更新一下，昨天的代码有点问题，没有考虑到头结点的影响，我的方法是：

在进行步数位移的时候判断标记点，如果走到了头结点，就在循环里面立即往后再位移一次，把头结点跳过；同时在后面删除元素的时候，再次判断位移点有不有走到头结点，如果走到了的话，就直接再往后移动一位，这样就成功跳过头结点了

单独拎出来约瑟夫环实现代码，函数封装


//约瑟夫
int link_yue(NodePtr L, int flag) {if (L == NULL || flag <= 0 || link_empty(L)) {printf("输入的参数有误或链表为空。\n");return -1;}NodePtr prev = L; NodePtr curr = L->next; while (L->len > 1) { for (int count = 0; count < flag-1; count++) {prev = curr; curr = curr->next; if(curr == L)              //在这里加入了一个if判断条件，判断在位移的时候有不有经过头节点，经过就跳过{prev = curr;curr = curr->next;}}printf("删除节点的值为: %d\n", curr->data); prev->next = curr->next; NodePtr temp = curr; curr = curr->next; if(curr == L)                 //在这里再加入了一个if判断条件，这个是用来判断删除之后节点有不有走到头结点，走到头结点，就跳过这个节点，跳过的方法是继续往后位移一位就行{prev = curr;curr = curr->next;}L->len--; free(temp); }// 输出最后剩下的节点数据printf("最后剩下的节点数据是：%d\n", curr->data);return 0;
}

以下为源码，分文件编译

1、循环链表实现约瑟夫环，每次经过特定步数删除一个元素

//looplist.h
#ifndef LOOPLIST_H
#define LOOPLIST_H
#include<stdio.h>
#include<string.h>
#include<stdlib.h>typedef int datatype;typedef struct Node
{union {int len;datatype data;};struct Node *next;
}Node,*NodePtr;//创建循环链表
NodePtr link_create();//判空
int link_empty(NodePtr L);//链表申请空间封装节点
NodePtr apply_node(datatype e);//按位置进行查找
NodePtr list_search_pos(NodePtr L, int pos);//头插
int link_insert_tail(NodePtr L,datatype e);//遍历链表
int link_show(NodePtr L);//约瑟夫
int link_yue(NodePtr L,int flag);
#endif

//looplist.c
#include"looplist.h"//创建循环链表
NodePtr link_create()
{NodePtr L = (NodePtr)malloc(sizeof(Node));if(NULL == L){printf("链表创建失败\n");return NULL;}L->len = 0;L->next = L;printf("创建链表成功\n");return L;
}//判空
int link_empty(NodePtr L)
{return L->next == L;
}//链表申请空间封装节点
NodePtr apply_node(datatype e)
{//堆区申请一个节点的空间NodePtr p = (NodePtr)malloc(sizeof(Node));if(NULL == p){printf("申请失败\n");return NULL;}//给节点赋值p->data = e;p->next = NULL;return p;
}//按位置进行查找
NodePtr list_search_pos(NodePtr L, int pos)
{if(NULL == L || pos < 0 || pos > L->len){printf("查找失败\n");return NULL;}NodePtr q = L;for (int  i = 0; i < pos; i++){q = q->next;}return q;
}//尾插
int link_insert_tail(NodePtr L,datatype e)
{   if(NULL == L){printf("插入失败\n");return -1;}NodePtr q = list_search_pos(L,L->len);NodePtr p = apply_node(e);p->next = q->next;q->next = p;L->len++;printf("插入成功\n");return 0;
}//遍历链表
int link_show(NodePtr L)
{if(NULL == L || link_empty(L)){printf("遍历失败\n");return -1;}NodePtr q = L->next;while(q != L){printf("%d\t",q->data);q = q->next;}printf("\n");
}//约瑟夫
int link_yue(NodePtr L, int flag) {if (L == NULL || flag <= 0 || link_empty(L)) {printf("输入的参数有误或链表为空。\n");return -1;}NodePtr prev = L; NodePtr curr = L->next; while (L->len > 1) { for (int count = 0; count < flag-1; count++) {prev = curr; curr = curr->next; if(curr == L)              //在这里加入了一个if判断条件，判断在位移的时候有不有经过头节点，经过就跳过{prev = curr;curr = curr->next;}}printf("删除节点的值为: %d\n", curr->data); prev->next = curr->next; NodePtr temp = curr; curr = curr->next; if(curr == L)                 //在这里再加入了一个if判断条件，这个是用来判断删除之后节点有不有走到头结点，走到头结点，就跳过这个节点，跳过的方法是继续往后位移一位就行{prev = curr;curr = curr->next;}L->len--; free(temp); }// 输出最后剩下的节点数据printf("最后剩下的节点数据是：%d\n", curr->data);return 0;
}

//main.c
#include"looplist.h"
int main(int argc, char const *argv[])
{NodePtr L = link_create();int flag = 0,n = 0,sum = 0;printf("请输入你想输入的个数:");scanf("%d",&n);//循环插入值for(int i = 0;i < n;i++){printf("请输入第%d个值:",i+1);scanf("%d",&sum);link_insert_tail(L,sum);}printf("当前链表中的元素为:");link_show(L);printf("请输入你想走多少步移除一个数:");scanf("%d",&flag);getchar();//调用约瑟夫环函数link_yue(L,flag);return 0;
}

输出结果如下: