链表经典例题

D.基础数据结构——单链表（2）(链表)

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 192 (72 users)

Total Accepted: 82 (67 users)

Special Judge: No

Description

1997-1998 年欧洲西南亚洲区预赛之后，举办了一场隆重的聚会。主办方发明了一个特殊的方式去挑选那些自愿去洗脏碟子的参赛选手。先让那些选手一个挨着一个的排成一条队。每个选手都获得一个编号，那些编号是从2开始的，第一个的编号是2 ，第二个人的编号是3，第三个人的编号是4，以此类推。

第一个选手将被问到他的编号（编号为2）。他将不用去清洗了，直接参加聚会，但是他身后的所站的位置是2的倍数的人必须去厨房（那些人的编号分别为4， 6， 8 等等）。然后在那队伍中的下一个选手必须报数。他回答3，他可以离开去参加聚会，但是在他身后的每个是三的倍数的选手将会被选上（那些人的编号分别为9,15,21等等）。下一个被选上的人的编号是5，并且将可以离开去参加聚会，但是在他身后并且站的位置是5的倍数的人将会被选上去清洗碟子（那些人的编号分别为19,35,49等等）.下一个被选上的人的编号是7，并且将可以离开去参加聚会，但是在他身后并且站的位置是7的倍数的人将会被选上去清洗碟子，以此类推。

让我们称那些没有被选上去洗碟子的那些选手的编号为幸运数字。继续这个挑选的方式，那些幸运的数字是2， 3， 5， 7， 11 ， 13， 17等等的递增序列。为下一次的聚会寻找幸运数字！

Input

本题有多组测试数据，每组测试数据包含一个整数n，1<=n<=3000。

Output

对于每组测试数据输出一个数字，代表对应的幸运号码。

Sample Input

Sample Output

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define status int
#define int int
typedef struct lnode{
   int date;
   struct lnode *next;
}node,*linklist;
void init(linklist &l){
   linklist p=(linklist)malloc(sizeof(lnode));
   p->next=NULL;
   l=p;
}
int main(){
      linklist l1,l2;
      init(l1);
      init(l2);
      linklist head=l1;
      linklist p=l1;
      for(int i=2;i<=35000;i++){
          linklist s=(linklist)malloc(sizeof(lnode));
            s->date=i;
            s->next=p->next;
             p->next=s;
             p=s;
      }
        int flag=0;
        linklist top;
        while(l1->next!=NULL){
           int tmp=l1->next->date;
           top=l1->next;
           cnt++;
           while(1){
              for(int i=1;i<tmp;i++){
                     if(top->next==NULL){
                       flag=1;
                       break;
                     }
                      top=top->next;
              }
              if(flag){
                  flag=0;
                 break;
                 }
               else{
                    if(top->next==NULL)
                    break;
                    else{
                        linklist q=top->next;
                        top->next=q->next;
                        free(q);
                    }
               }
           }
           l1=l1->next;
        }
       int t;
    while(scanf("%d",&t)!=EOF){
        linklist ans=head;
        while(t){
           t--;
           ans=ans->next;
        }
        printf("%d
",ans->date);
    }

    return 0;
}

/*
#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *next;
};
int main()
{
    struct node *head = NULL;
    struct node *p, *q;
     //创建单链表。
    p = (struct node *)malloc(sizeof(struct node));
    p->data = 0;
    head = p;

    for(int i = 2; i <= 35000; i++){
        q = (struct node *)malloc(sizeof(struct node));
        q->data = i;
        p->next = q;
        p = q;
    }
    p->next = NULL;
      //创建完毕。
    struct node *point = head;
    struct node *top;
    int ans = 0;
          //遍历链表。
    while(point->next != NULL)
    {
        int tmp = point->next->data;
        top = point->next;
        while(1)
        {
            for(int i = 0; i < tmp-1; i++)
            {
                if(top->next == NULL)
                {
                    ans = 1;
                    break;
                }
                top = top->next;
            }
            if(ans)
            {
                ans = 0;
                break;
            }
            else
            {
                if(top->next == NULL)
                {
                    break;
                }
                else
                {
//删除操作。
                    q = top->next;
                    top->next = q->next;
                    free(q);
                }
            }
        }
        point = point->next;
    }

    int n;
    while(scanf("%d", &n) != EOF)
    {
        struct node *point = head;

        for(int i = 0; i < n; i++)
        {
            point = point->next;
        }
        printf("%d
", point->data);
    }
    return 0;
}
*/