Chinaunix首页 | 论坛 | 博客
  • 博客访问: 119417
  • 博文数量: 61
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 230
  • 用 户 组: 普通用户
  • 注册时间: 2014-04-26 11:35
个人简介

实践Linux的理论

文章存档

2015年(1)

2014年(60)

我的朋友

分类: C/C++

2014-04-29 15:48:08

 相比较线性表的排序而言,链表排序的内容稍微麻烦一点。一方面,你要考虑数据插入的步骤;另外一方面你也要对指针有所顾虑。要是有一步的内容错了,那么操作系统会马上给你弹出一个exception。就链表的特殊性而言,适合于链表的排序有哪些呢?
    (1)插入排序    (适合)
    (2)冒泡排序    (适合)
    (3)希尔排序    (适合)
    (4)选择排序    (适合)
    (5)快速排序    (不适合)
    (6)合并排序    (不适合)
    (7)基数排序     (不适合)
    (8)堆排序         (不适合)
    其实,一般来说。如果涉及到数据之间的相对关系调配,那么只适合线性排序;如果只是数据内容之间的相互交换,那么这种排序方法也比较适合链表的排序。快速排序、合并排序、堆排序都涉及到了中间值的选取问题,所以不大适合链表排序。
    为了说明链表排序是怎么进行的,我们可以利用插入排序作为示例,描述链表是怎么进行插入排序的。
    a)首先遍历节点,一边是排序好的节点,一边是待排序的节点
[cpp] view plaincopy
void sort_for_link_node(NODE** ppNode)  
{  
    NODE* prev;  
    NODE* curr;  
  
    if(NULL == ppNode || NULL == *ppNode)  
        return;  
  
    curr = (*ppNode) ->next;  
    (*ppNode) ->next = NULL;  
  
    while(curr){  
        prev = curr;  
        curr = curr->next;  
        insert_for_sort_operation(ppNode, prev);  
    }  
  
    return;  
}  


    b)对于待插入的节点,选择合适的位置插入即可
[cpp] view plaincopy
void insert_for_sort_operation(NODE** ppNode, NODE* pNode)  
{  
    NODE* prev;  
    NODE* cur;  
  
    /* 在第一个数据之前插入pNode */  
    if(pNode->data < (*ppNode)->data){  
        pNode->next = *ppNode;  
        *ppNode = pNode;  
        return;  
    }  
  
    cur = *ppNode;  
    while(cur){  
        if(pNode->data < cur->data)  
            break;  
  
        prev = cur;  
        cur = cur->next;  
    }  
  
    pNode->next = prev->next;  
    prev->next = pNode;  
    return;  
}  
阅读(759) | 评论(0) | 转发(0) |
0

上一篇:链表逆转

下一篇:块驱动范例1

给主人留下些什么吧!~~