sun.c

十字链表

#include<stdio.h>
#include<malloc.h>
#define Max 50
typedef struct node
{
	int num[Max];
	int len;
	struct node *dp;
	struct node *rp;
}NODETYPE;

typedef struct
{
	int unit;
	NODETYPE *p;
}NUMTYPE;

NUMTYPE NUM[10];

void Order()
{
	int i;
	for(i=0;i<10;i++)
	{
		NUM[i].unit=i;
		NUM[i].p=NULL;
	}
}

void Changeorder(NODETYPE *s)
{
	int temp,i;
	for(i=0;i<s->len/2;i++)
	{
		temp=s->num[i];
		s->num[i]=s->num[s->len-i-1];
        s->num[s->len-i-1]=temp;
	}
}


NODETYPE *Sort(NODETYPE *s,int n)
{
	int i,j;
    NODETYPE *p,*q;
	for(i=0;i<n;i++)
	{
		for(p=s;p!=NULL;p=p->rp)
		{
			if(p->len<i+1) 
				p->num[i]=0;
			if(NUM[p->num[i]].p==NULL)
				NUM[p->num[i]].p=p;
			else
			{
				q=NUM[p->num[i]].p;
				while(q->dp!=NULL)
					q=q->dp;
				q->dp=p;
				q=q->dp;
			}
		}
		s=NULL;
		for(j=0;j<10;j++)
		{
			q=NUM[j].p;
			if(q!=NULL&&s==NULL)
			{
				s=q;
				p=s;
				q=q->dp;
				p->dp=NULL;//把dp置空，以备下次分配时正常使用
			}
			else if(q==NULL)
				continue;
			while(q!=NULL)
			{
				p->rp=q;
				p=p->rp;
				q=q->dp;
				p->dp=NULL;
			}
			NUM[j].p=NULL;//重新把数字数组的指针置空
		}
        p->rp=NULL;//否则形成死循环
	}
	return s;
}

main()
{
	NODETYPE *head,*p,*point;
	char c;
	int i,max=0;
	Order();
	printf("Please enter the nodes :\n");
	point=(NODETYPE *)malloc(sizeof(NODETYPE));
	point->len=0;
	head=point;
	p=head;
	while(c=getchar())
	{
		if('0'<=c&&c<='9')
			point->num[point->len++]=c-48;
		else
		{
			max=(max>point->len)?max:point->len;
			point->dp=NULL;
			Changeorder(point);
            if(c=='\n')
			{
				point->rp=NULL;
				break;
			}
		    point=(NODETYPE *)malloc(sizeof(NODETYPE));
			point->len=0;
			p->rp=point;
			p=p->rp;
		}
		
	}
	head=Sort(head,max);
	printf("Numbers in correct order is:\n");
	for(p=head;p!=NULL;p=p->rp)
	{
		for(i=p->len-1;i>=0;i--)
			printf("%d",p->num[i]);
		printf("  ");
	}
}


//getchar()接收scanf的回车\n ？？