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

typedef struct time
{
    char year[5];
    char month[3];
    char day[3];
    struct time *next;
}Node;

Node *createLList(int );
Node *sortLList(Node *);
void print(Node *);

int main()
{
int n; 
Node *head,*newhead;
printf("请输入结点个数:\n"); 
scanf("%d",&n);
head=createLList(n);
print(head);
newhead=sortLList(head);
print(newhead);
}

Node *createLList(int n)
{
  Node *head,*p,*q;
  //char ch;
  if(n==0)
  {                                         //创建链表 
     printf("创建链表失败\n");
     return NULL;
  }
  head=(Node *)malloc(sizeof(Node));
  p=head;
  for(int t=1;t<=n-1;t++)
  {
    printf("请输入年/月/日:\n"); 
	scanf("%s%s%s",p->year,p->month,p->day);
    q=(Node *)malloc(sizeof(Node));
    p->next=q;
    p=p->next;
  }
    printf("请输入年/月/日:\n"); 
	scanf("%s%s%s",p->year,p->month,p->day);
    p->next=NULL;
    return head;
}

    
Node *sortLList(Node *head)               //链表排序 
{
	Node *first,*tail,*p,*p_max,*max;
	first=NULL;
	while(head!=NULL)
	{
		for(p=head,max=head;p->next!=NULL;p=p->next)
		{
			 if((p->next->year>max->year)||(p->next->year==max->year&&p->next->month>max->month)
			    ||(p->next->year==max->year&&p->next->month==max->month&&p->next->day>max->day))
			   {
			      p_max=p;
			      max=p->next;
			   }
		}
		
	    if(first==NULL)
	    {
	    	first=max;
	    	tail=max;
	    }
	    else
	    {
	    	tail->next=max;
	    	tail=max;
	    }
	    if(max==head)
	    {
	        head=head->next;
	    }
	    else
	    {
		   p_max->next=max->next;
	    }
	}
	  
	    
	     if (first!=NULL) 
        {
           tail->next=NULL; 
        }
        head=first;
        return head;
}

	      
void print(Node *head)
{ 
    Node *p;
    p=head;
    while(p->next!=NULL)
    {
       printf("%4s%4s%4s\n",p->year,p->month,p->day);
	   p=p->next;
    }
       printf("%4s%4s%4s\n",p->year,p->month,p->day);
}