C++算法之链表排序
发布时间:2020-12-16 07:44:47 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 相比较线性表的排序而言,链表排序的内容稍微麻烦一点。一方面,你要考虑数据插入的步骤;另外一方面你也要对指针有所顾虑。要是有一步的内容错了,那
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考
相比较线性表的排序而言,链表排序的内容稍微麻烦一点。一方面,你要考虑数据插入的步骤;另外一方面你也要对指针有所顾虑。要是有一步的内容错了,那么操作系统会马上给你弹出一个exception。就链表的特殊性而言,适合于链表的排序有哪些呢?
(1)插入排序 (适合) (2)冒泡排序 (适合) (3)希尔排序 (适合) (4)选择排序 (适合) (5)快速排序 (不适合) (6)合并排序 (不适合) (7)基数排序 (不适合) (8)堆排序 (不适合) 其实,一般来说。如果涉及到数据之间的相对关系调配,那么只适合线性排序;如果只是数据内容之间的相互交换,那么这种排序方法也比较适合链表的排序。快速排序、合并排序、堆排序都涉及到了中间值的选取问题,所以不大适合链表排序。 为了说明链表排序是怎么进行的,我们可以利用插入排序作为示例,描述链表是怎么进行插入排序的。 ????a)首先遍历节点,一边是排序好的节点,一边是待排序的节点 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)对于待插入的节点,选择合适的位置插入即可 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; } 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |