约瑟夫环C实现

费德 2016/10/13 22:03 537 次

#include<stdio.h>
#include <stdlib.h>
#define M_INIT 20
#define N 7

typedef struct node//节点存放一个数据和指向下一个节点的指针
{
    int data;//编号
    int password;//密码值
    struct node* pnext;
} Node;

Node *link_create()//创建n个节点的循环链表
{
    //先创建第1个节点
    Node *p,*q,*head;
    int i ;
    int arr[N+1] = {0,3,1,7,2,4,8,4};
    p = (Node *)malloc(sizeof(Node));
    head = p;
    p->password = arr[1];
    p->data = 1;

    for(i = 2;i<=N;i++)//再创建剩余节点
    {
        q = (Node *)malloc(sizeof(Node));
        q->data = i;
        q->password = arr[i];
        p->pnext = q;
        p = q;
    }
    p->pnext = head;//最后一个节点指向头部，形成循环链表
    return head;
}

void link_process(Node *head)
{
    int i;
    int m = M_INIT;
    int data = 0;
    Node *p = head,*tmp1;
    //循环控制输出
    while(p->pnext != p)
    {
        for(i=1;i<m;i++)
        {
            tmp1 = p;
            p = p->pnext;
        }

        printf("%d ",p->data);
        tmp1->pnext= p->pnext;
        m = p->password;
        data = p->data;
        free(p);
        p = tmp1->pnext;
    }
    printf("%d ",p->data);
    free(p);
}

int main()
{
    Node *head = link_create();
    link_process(head);
    system("pause");
    return 0;
}