M个人,1到N报数出列问题

来源： 编程中国 作者： 若水   2008-05-12/19:31

软件频道 编程学院 C/C++/VC 实例解析 正文

• 问题
• 个人
•  
• int
• "
• next
• 节点

/*************************************************************/
/*       M个人围成一圈,从1至N开始顺序循环报数                */
/*       每数到N的人出列,输出该数值,直至全部输出             */
/*************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

/* 循环链表结构 */
typedef struct Node{
    int data;
    struct Node *next;
}*LinkList;

/* 利用单向循环链表找到符合条件的节点,输出节点值并删除该节点 */
int CreateList(LinkList &L,int m); /* 将m个人1到m编号依次插入循环链表L中 */
int GetNode(LinkList &L,int n); /* 依次删除输出链表中符合要求的节点 */

int CreateList(LinkList &L,int m)
{
    int i=1;
    LinkList tmp,p;
    /* 给链表头指针分配内存 */
    L=(LinkList)malloc(sizeof(struct Node));    
    if(L==NULL)
    {
        printf("动态分配内存失败!");
        return -1;
    }
    p=L;
    for(i=1;i<=m;i++) /* 依次为节点分配内存,插入链表 */
    {
        tmp=(LinkList)malloc(sizeof(struct Node));
        if(tmp==NULL)
        {
            printf("动态分配内存失败!");
            return -1;
        }
        /* 将节点tmp插入链表 */
        tmp->data=i;
        p->next=tmp;
        p=tmp;
    }
    tmp->next=L->next; /* 最后一个节点next指针指向第一个节点 */
    return 0;
}

int GetNode(LinkList &L,int n)
{
    LinkList p,s;
    int i=0;
    p=L->next; /* p指向第一个节点 */
    while(p->next!=p) /* 链表中只有一个节点时终止 */
    {
        i++;
        if(i==n-1) /* 找到报数n的节点,输出节点值并删除节点,计数器i归位 */
        {
            s=p->next;
            p->next=p->next->next;
            printf("%d ",s->data);
            i=0;
            free(s);
        }
        p=p->next;
    }
    printf("%d ",p->data); /* 输出最后一个节点,并释放其内存 */
    free(p);
    free(L); /* 释放头节点内存 */
    return 0;
}

int main()
{
    int m,n;
    LinkList L;

    printf("Enter the total number of the person[m]:"); /* 总人数 */
    scanf("%d",&m);
    printf("Enter the number of get out[n]:");
    scanf("%d",&n);
    CreateList(L,m);
    printf("The out queue is:\n");
    GetNode(L,n);

    getch();
    return 0;
}