数据结构实验之链表八：Farey序列

你的名字 2022-05-16 07:10 77阅读 0赞

Problem Description  
Farey序列是一个这样的序列：其第一级序列定义为（0/1，1/1），这一序列扩展到第二级形成序列（0/1，1/2，1/1），扩展到第三极形成序列（0/1，1/3，1/2，2/3，1/1），扩展到第四级则形成序列（0/1，1/4，1/3，1/2，2/3，3/4，1/1）。以后在每一级n，如果上一级的任何两个相邻分数a/c与b/d满足（c+d）<=n，就将一个新的分数(a+b)/(c+d)插入在两个分数之间。对于给定的n值，依次输出其第n级序列所包含的每一个分数。

Input  
输入一个整数n(0

#include <stdio.h>
    #include <stdlib.h>
    
    struct node
    {
        int data1;
        int data2;
        struct node *next;
    };
    
    struct node *creat()
    {
        struct node *head,*tail,*p;
        head=(struct node *)malloc(sizeof(struct node));
        head->next=NULL;
        tail=head;
        p=(struct node*)malloc(sizeof(struct node));
        p->data1=0;p->data2=1;
        p->next =NULL;
        tail->next=p;
        tail=p;
        p=(struct node*)malloc(sizeof(struct node));
        p->data1=1;p->data2=1;
        tail->next=p;
        p->next=NULL;
        tail=p;
        return head;
    }
    
     struct node *creat2(struct node *head,int n)
     {
        struct node *p,*q,*t;
        int i;
        for(i=2;i<=n;i++)
        {
            p=head->next;
            q=p->next;
            while(q)
            {
                if(p->data2+q->data2<=i)
                {
                    t=(struct node *)malloc(sizeof(struct node));
                    t->data1=p->data1+q->data1;
                    t->data2=p->data2+q->data2;
                    t->next=NULL;
                    t->next=p->next;
                    p->next=t;
                }
                p=q;
                q=q->next;
            }
        }
        return head;
    
     }
     void print(struct node *head)
     {
         struct node *p;
         p=head->next;
         int sum=0;
         while(p)
         {
             printf("%d/%d",p->data1,p->data2);
             sum++;
             if(sum%10==0)
             {
                 printf("\n");
             }
             else
             {
                 printf("\t");
             }
             p=p->next;
         }
     }
    int main()
    {
        int n;
        struct node *head;
        scanf("%d",&n);
        head=creat();
        if(n==1)
        {
          print(head);
        }
        else
        {
            head=creat2(head,n);
            print(head);
        }
    
        return 0;
    }