首页 > 代码库 > 用链表写的冒泡排序理解

用链表写的冒泡排序理解

这是一位师弟问的问题,一段用链表写的冒泡排序。

技术分享

 

[1] 为什么要多用一个空的表头?

这是由链表结构造成的,如果要交换p1和p2两个节点,则需要p1的前趋的指针,举例,设原链表为{3,2,1}如果我们要交换3和2,由于3是表头节点,所以需要一个指向3的指针节点,因此这里我们设置了一个空的头节点p1,第一个元素的位置实际上在head->next上。

[2] 释放指针方式解读

 

delete p;p=NULL;

技术分享

技术分享

最后要释放掉这个空的头节点,先保存下这个地址p1=head,实际表的地址指回原来的位置(head=head->next),然后释放p1的指针,释放指针实际就是让p1不要指向head。如果你直接head’=head->next,虽然我们不知道原来的head在哪里了,但是它仍然是指向现在的head‘的,这就是所谓的野指针,这就涉及到指针的知识了,学生党写写程序没关系,但是放到项目里面,就非常不好了。关于这个在指针学习系列里面我再仔细写写。
[3] 总结

    熟悉用数组写的冒泡,用算法的思路去思考这个问题,或者写个简单的序列手动模拟程序排序的过程或者让程序输出来排序的过程,便于理解。

用链表写的冒泡排序理解