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

//-----------------------------------
typedef int dataType;
//-----------------------------------

// 定义数据节点
struct node
{
	dataType data; // 数据域
	struct node *next; // 指针域，存放(指向)下一个节点的地址
};
//-----------------------------------

// 定义头节点
struct headNode
{
	struct node *first; // 指向第一个数据节点
	struct node *last; // 指向最后一个数据节点
	int nodeNumber; // 记录链表节点数
};
//---------------------------------
// 尾插
void tailAdd(struct node *pnew,struct headNode *head)
{
	head->last->next=pnew;
	head->last=pnew;
}
//---------------------------------
// 头插
void headAdd(struct node *pnew,struct headNode *head)
{
	pnew->next=head->first;
	head->first=pnew;
}
//---------------------------------
struct headNode *create_list()
{
	// 创建头节点
	struct headNode *head = malloc(sizeof(struct headNode));
	if(head == NULL)
	{
		perror("create headNode failed");
		return NULL;
	}
	head->first = NULL;
	head->last = NULL;
	head->nodeNumber = 0;
	
	dataType data;
	
	while(1)
	{
		scanf("%d",&data);
		if(data == 0)// 链表生成
			break;
		
		// 创建新节点
		struct node *pnew = malloc(sizeof(struct node));
		if(pnew == NULL)
		{
			perror("create newnode failed");
			return NULL;
		}	
		pnew->data = data;
		pnew->next = NULL;
		
		//将新节点插入到链表
		if(head->first == NULL)//从无到有
		{
			head->first = pnew;
			head->last = pnew;
		}
		else // 从少到多
		{
			// 尾插法
			tailAdd(pnew,head);
			
			// 头插法
			//headAdd(pnew,head);
			
		}
		
		// 更新节点数
		head->nodeNumber++;
		
		// 将链表设计为单向循环链表
		if(head->nodeNumber != 0)
		{
			head->last->next = head->first;
		}
		
	}
	
	return head;
}

//------------------------------
// 将add_node修改为适用于循环链表
struct headNode *add_node(struct headNode *head,dataType newdata,dataType data)
{
	// 判断链表是否为空
	if(head->first == NULL)
		return NULL;
	
	// 创建新节点
	struct node *pnew = malloc(sizeof(struct node));
	if(pnew == NULL)
	{
		perror("create new node failed:");
		return NULL;
	}
	// 初始化新节点
	pnew->data = newdata;
	pnew->next = NULL;
	
	// 定义指针p遍历链表
	struct node *p = head->first;
	// 定义指针pre指向p的前一个节点
	struct node *pre = NULL;
	
	// 开始遍历链表查找对应的节
	int n = head->nodeNumber;
	while(n--) // while(n;n-1)// 先判断n是否为真，然后再减一      while(--n) // while(n-1,n)
	{
		// 找到了,停止遍历
		if(p->data == data)
		{
			break;
		}
		else // 继续找
		{
			pre = p;
			p = p->next;
		}
		printf("__%d__\n",n);
	}
	// 找不到节点
	if(n == -1) //尾插
	{
		tailAdd(pnew,head);
	}
	else
	{
		// 找打的是首节点
		if(p == head->first)
		{
			// 头插法
			headAdd(pnew,head);
		}
		else // 中间插
		{
			pre->next = pnew;
			pnew->next = p;
		}
	}
	// 链表节点加一
	head->nodeNumber++;
	
	if(head->nodeNumber != 0)
	{
		head->last->next = head->first;
	}
	
	return head;
}

/*
	del_node : 将head指向的链表中删除所有对应的data数据所对应的节点
*/
struct headNode *del_node(struct headNode *head,dataType data)
{
	// 遍历指针
	struct node *p = head->first;
	// 指向p的前一个节点
	struct node *pre = NULL;
	int n = head->nodeNumber;
	while(n--)
	{
		if(p->data == data)// 找到需要删除的节点
		{
			// 链表节点减一
			head->nodeNumber--;
			
			if(p == head->first)// 需要删除的数据为首节点数据
			{
				head->first = head->first->next;
				p->next = NULL; // 断开链表
				free(p); // 释放空间
				p = head->first;//p重新指向新的首节点
			}
			else //删除的数据不是首节点
			{
				pre->next = p->next;
				p->next = NULL; // 断开链表
				free(p); // 释放堆空间
				p = pre->next; 
			}
		}
		else // 没有找到对应的节点，继续往下找
		{
			pre = p;
			p = p->next;
		}
	}
	
	return head;
}

struct headNode *sort_list()
{
	// 创建头节点
	struct headNode *head = malloc(sizeof(struct headNode));
	if(head == NULL)
	{
		perror("create headNode failed");
		return NULL;
	}
	head->first = NULL;
	head->last = NULL;
	head->nodeNumber = 0;
	
	// 用于存放数据的数据
	dataType data;
	// 循环创建节点,将节点插入到链表
	while(1)
	{
		// 输入数据
		scanf("%d",&data);
		// 链表创建完成
		if(data == 0)
			break;
		
		// 创建新节点
		struct node *pnew = malloc(sizeof(struct node));
		if(pnew == NULL)
		{
			perror("create new node failed:");
			return NULL;
		}
		// 初始化新节点里面的数据
		pnew->data = data;
		pnew->next = NULL;
		
		//如果链表为NULL
		if(head->first == NULL)
		{
			head->first = pnew;
			head->last  = pnew;
		}
		else // 链表不为空
		{
			// 定义遍历指针p指向链表的首节点，用于遍历链表
			struct node *p = head->first;
			// 定义一个指针pre指向p的前一个节点
			struct node *pre = NULL;
			int n = head->nodeNumber;
			
			while(n--)
			{
				// 如果找到对应的节点
				if(p->data > pnew->data)
				{
					break;
				}
				else // 找不到，继续找
				{
					pre = p;
					p = p->next;
				}
			}
			
			// 如果找不到对应的数据
			// 将数据插入到链表的末尾
			if(n == -1)
			{
				head->last->next = pnew;
				head->last = pnew;
			}
			else // 找到了对应的数据
			{
				// 如果找到的是首节点
				if(p == head->first) // 头插法
				{
					pnew->next = head->first;
					head->first = pnew;
				}
				else// 中间插
				{
					pre->next = pnew;
					pnew->next = p;
				}
			}	
		}
		// 添加完一个节点
		head->nodeNumber++;
		
		// 将链表设计为循环链表
		if(head->nodeNumber != 0)
		{
			head->last->next = head->first;
		}
	}
	
	return head;
}

//------------------------------
// 打印链表节
void show_list(struct headNode *head)
{
	/* for(struct node *p = head->first;p != NULL;p = p->next)
	{
		printf("%d  ",p->data);
	} */
	// 如果链表为空结束
	if(head->first == NULL)
		return ;
	
	int n = head->nodeNumber;
	struct node *p = head->first;
	while(n--)
	{
		printf("%d  ",p->data);
		p = p->next;
	}
	
	printf("\n");
	printf("此链表的节点数据数为%d个\n",head->nodeNumber);
}

int main()
{
	// 创建新链表
	//struct headNode *head = create_list();
	
	//head = add_node(head,8,3);

	//  删除节点
	//head = del_node(head,3);
	
	// 排序
	struct headNode *head  = sort_list();
	
	//打印链表
	show_list(head);
	return 0;
}