c语言不带头结点的循环链表joseph问题
1、以下是不带头结点的循环链表算法
*/
#include <stdio.h>
#include <stdlib.h>
typedef int data_t;
typedef struct node
{
data_t data;
struct node *next;
}listnode, *linklist;
2、/*创建一个不带头节点的循环链表*/
listnode* CreatCycleList(int num)
{
int i = 2;
listnode *head = NULL, *q = NULL, *p = NULL;
head = (listnode*)malloc(sizeof(listnode));
head->data = 1;
head->next = NULL;
p = head;
while(i <= num)
{
q = (listnode*www.gzlij.com)malloc(sizeof(listnode));
q->data = i;
q->next = NULL;
p->next = q;
p = q;
i++;
}
p->next = head;
return head;
}
listnode* Joseph(listnode *head, int start, int killNum)
{
int i;
listnode *p, *q; //p遍历链表，q指向待宰的人
p = head;
3、/* 找位置,p最后停在开始报数的前一个人处*/
if(start == 1)
{
while(p->next != head)
{
p = p->next;
}
}
else
{
for(i = 1; i < start-1; i++)
{
p = p->next;
}
}
4、/* 开杀*/
while(p != p->next)
{
for(i = 1; i < killNum; i++)
{
p = p->next;
}
q = p->next;
p->next = q->next;
printf("%d,",q->data);
free(q);
q = NULL;
}
return p;
}
void Display(listnode *head)
{
listnode *p = head;
while(p->next != head)
{
printf("%d,",p->data);
p = p->next;
}
printf("%d\n",p->data);
}
int main(int argc, char *argv[])
{
listnode *head = CreatCycleList(5);
Display(head);
listnode *p = Joseph(head, 8, 3);
printf("%d\n",p->data);
return 0;
}