#include
#include
typedef int ElemType;
typedef struct node
{
    ElemType data;
    struct node *next;
}linkNode, *linklist;
/*
*功能:初始化链表
*返回值:链表首地址
*/
linklist initList()
{
    linklist head;
    head = (linklist)malloc(sizeof(linkNode));
    if(head == NULL)
        return NULL;
    head->next = NULL;
    return head;
}

/*
*功能:求链表长度(头结点不计算)
*参数:链表首地址
*返回值:链表结点数
*/
int length(linklist head)
{
    int len = 0;
    if(head == NULL)
        return 0;
    head = head->next;
    while(head != NULL)
    {
        ++len;
        head = head->next;
    }
    return len;
}
/*
*功能:判断两个结点的数据大小
*参数:两个结点的地址
*返回值:firstNode中数据大于secondNode中数据返回1
*firstNode中数据等于secondNode中数据返回0
*firstNode中数据小于secondNode中数据返回-1
*传递参数有问题时返回-2
*/
int nodeCompare(linklist firstNode, linklist secondNode)
{
    if(firstNode->data > secondNode->data)
        return 1;
    else if(firstNode->data == secondNode->data)
        return 0;
    else if(firstNode->data < secondNode->data)
        return -1;
    return -2;
}
/*
*功能:申请空间
*参数:结点(数据)
*返回值:指向结点的指针
*/
linklist makeNode(linkNode nodeData)
{
    linklist newNode;
    newNode = (linklist)malloc(sizeof(linkNode));
    if(newNode == NULL)
        return NULL;
    newNode->data = nodeData.data;
    return newNode;
}
/*
*功能:输出链表数据
*参数:链表首地址
*/
void printList(linklist head)
{
    if(head == NULL || head->next == NULL)
        return;
    head = head->next;
    printf("\nlinklist:\n");
    while(head != NULL)
    {
        printf("%d  ", head->data);
        head = head->next;
    }
    printf("\n");
}
/*
*功能:链表排序(带头结点)
*参数:链表首地址
*
*/
void listSort(linklist head)
{
    linklist pre, mid, tai;
    int i, j;
    int len = length(head);
    if(head == NULL || head->next == NULL)
        return;
    for(i = 0; i < len - 1; ++i)
    {
        pre = head;
        mid = head->next;
        tai = mid->next;
        for(j = 0; j < len - i - 1; ++j)
        {
            if(nodeCompare(mid, tai) == 1)
            {
                pre->next = mid->next;
                mid->next = tai->next;
                tai->next = mid;               
            }
            pre = pre->next;
            mid = pre->next;
            tai = mid->next;           
        }
    }
}
/*
*功能:在链表尾部插入结点
*参数:链表首地址,待插入结点地址
*/
void pushBack(linklist head, linklist insertNode)
{
    if(head == NULL)
        return;
    while(head->next != NULL)
    {
        head = head->next;
    }
    head->next = insertNode;
    insertNode->next = NULL;
}
/*
*功能:在链表头部插入结点
*参数:链表首地址,待插入结点地址
*/
void pushFront(linklist head, linklist insertNode)
{
    if(head == NULL)
        return;
    insertNode->next = head->next;
    head->next = insertNode;
}
/*
*功能:释放链表空间
*参数:链表首地址
*返回值:释放成功则返回NULL
*/
linklist freeList(linklist head)
{
    linklist p;
    p = head;
    while(p != NULL)
    {
        p = p->next;
        free(head);
        head = p;      
    }
    return head;
}
int main()
{
    linklist list, insertNode;
    linkNode newNode;
    int i;
    list = initList();
    for(i = 0; i < 5; ++i)
    {
        //newNode.data = i;
        scanf("%d", &newNode.data);
        insertNode = makeNode(newNode);      
        pushBack(list, insertNode);
    }
    printList(list);
    listSort(list);
    printList(list);
    freeList(list);
    return 0;
}