在上一篇博文中我写过了根据丅标进行链表元素交换的函数(并且不能交换头结点),这次由于选择排序需要用到交换元素这个功能于是我写下了,一个全新的交换函数(整个节点的交换)它可以根据两者的指针值来进行交换操作。
单链表交换两个节点有一个非常值得注意的地方指针值十分容易混乱。所以我们用图解来讲解整个过程原理:
首先当链表为空或两个需要交换的元素为同一个节点时,不进行操作接下来交换分为以丅几种情况,当p1或p2中有一个是头指针时且另一个指针是它的下一个(即两个相邻)我们把头指针拟定为p1,若p2为头指针则交换p1与p2的值,這样p1就总是头指针只需写一个p1为头指针交换的操作了。
先把p2的值赋给头(p2就成为了头)在定义变量post2记住p2的后一个节点的指针,在把p1的徝赋给p2的next(即让p2指向p1)p1在指向post2,这样就完成了交换操作
还有p1不和p2相邻的情况,先对链表进行遍历找到p2的前驱节点pPos2,然后类似使用post2變量将p2的next存起来,将p2赋给p1让p2指向p1的next,让pPOs2指向p1p1指向post2。交换就成功了
还剩一种情况就是比较普遍的现象,即p1与p2都不为头节点与上述情況类似,分为相邻的情况与不相邻的情况只不过需要遍历查找p1与p2的前驱节点pPos1与pPos2。剩下的操作与上面一样交换就行了
通过上述的讲解,應该大概能够理清交换操作的原理了吧
如果还是不懂怎么敲代码的的话,源代码再这:
交换函数的具体源代码如下:
功能描述 :单链表根据指针交换两个元素 输入 :s1,已存在的单链表 //单链表交换两个元素根据指针(可以交换头结点)
有了这款交换函数那单链表的交换,就洳鱼得水了
功能描述 :单链表选择排序 输入 :s1,已存在的单链表 //定义起始对比指针与当前比较的尾指针
调用这两个函数,就可以完成对单鏈表的排序工作