链表的冒泡排序,该怎么处理

链表的冒泡排序

C/C++ code


struct Node
{
    int age; 
    struct Node * pNext;
};

对比的是age，进行升序排(冒泡排序），交换的是每个结点而不是结点中的数据域。代码应该怎样实现啊。最好在讲一下算法和伪代码

------解决方案--------------------

C/C++ code


#include <stdio.h>
#include <malloc.h>

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
*/
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;
}

int main()
{
    linklist list, insertNode;
    linkNode newNode;
    int i;
    list = initList();

    for(i = 0; i < 10; ++i)
    {
        newNode.data = 10 - i;
        insertNode = makeNode(newNode);        
        pushBack(list, insertNode);
    }

    printList(list);
    listSort(list);
    printList(list);
    return 0;
}

链表的冒泡排序,该怎么处理

相关推荐