Chinaunix首页 | 论坛 | 博客
  • 博客访问: 525261
  • 博文数量: 118
  • 博客积分: 10028
  • 博客等级: 上将
  • 技术积分: 1820
  • 用 户 组: 普通用户
  • 注册时间: 2007-11-07 18:46
文章分类

全部博文(118)

文章存档

2009年(12)

2008年(106)

我的朋友

分类: C/C++

2008-12-27 21:37:20


题目:
    以及n个人(编号1...n),围坐一张圆桌。从编号为K的人开始数到m的人出列;他的下一个人为头开始数,依次重复下去,知道所有人都出列。

INPUT:
     n m k
OUTPUT:
     出列顺序

思路:
    1、先构造有n个节点的循环链表
    2、找到K的位置
    3、数数

代码:

#include <stdio.h>
#include <stdlib.h>

struct node{
    int key;
    struct node *next;
};
typedef struct node Node;

void print_list(Node *head)
{
    Node *p=head;
    if(NULL == head){
        printf("there is no node!\n");
        return;
    }

    do{
        printf("%d ",p->key);
        p=p->next;
    }while(p != head);
    printf("\n");
}

void do_count(Node *list,int m,int k)
{
    Node *p=list;
    Node *pk=list;
    int i=0;

    while(1){//find k people

        if(i == k){
            pk=p; //pk point to k
            break;
        }
        p=p->next;
        i++;
    }
    //printf("%d\n",pk->key);
    while(pk != pk->next){
        i=0;
        while(1){
            if(i == m-1){
                printf("%d ",pk->next->key);
                p=pk->next;
                pk->next=pk->next->next;
                free(p);
                p=NULL;
                pk=pk->next;
                break;
            }
            pk=pk->next;
            i++;
        }
    }
    printf("%d ",pk->key);
    printf("\n");
    free(pk);
}

Node *create_list(Node **head,int n)
{
    Node *temp;
    int i;

    temp=(Node *)malloc(sizeof(Node));
    temp->key=1;
    temp->next=temp;
    *head=temp;
    for(i=n;i>1;i--){
        temp=(Node *)malloc(sizeof(Node));
        if(NULL == temp){
            printf("Malloc error!\n");
            exit(1);
        }
        temp->key=i;
        temp->next=(*head)->next;
        (*head)->next=temp;
    }
    return *head;
}

int main(int argc,char **argv)
{
    Node *head=NULL;
    int n=7,m=5,k=2;

    if(0 == m){
        printf("m cannt be zero!\n");
        exit(1);
    }
    head=create_list(&head,n);
    print_list(head);
    do_count(head,m,k);
    return 0;
}

阅读(939) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~