C语言—链表的排序

一时失言乱红尘 2022-07-11 08:27 147阅读 0赞

#  链表的排序 #

许多人认为链表排序是这里面最难得，因为大家脑海里面对于前面插入，删除的

方法已经熟悉了，可能最容易想到的就是从结点和结点之间的联系入手，确实最

常用的就是把链表的“链”打断再重新排，再有就是重新创建一个一模一样的链

表，然后把排序出来的从大到小依次写进去，但是这些方法都是从外边的大结构

上入手，但是可以想办法从结构体内的元素入手，只是交换元素，链表结构框架

不会改变。仔细想想突然觉得还行哈。。。

现在我们想想我们知道的排序，都有什么排序?选择排序，冒泡排序。。。。。

今天我们就用冒泡排序，把最大的通过循环冒泡到顶端。

现在不妨写一下冒泡排序的程序。

for (i = 0; i < 10;i++)
    	for (k = 9 - i; k>0; k--)
    	{
    		if (arrg[k] < arrg[k - 1])
    		{
    			j = arrg[ k ];
    			arrg[k] = arrg[k - 1];
    			arrg[k - 1] = j;
    		}
    	}

`这是我以前写的排序数组的程序，现在我们里面交换的是结构体的元素，所以我们`

`用的是指针，`

point *pi, *pj, *pt, t;
    	for (pi = head.next; pi;pi=pi->next)
    	for (pj = pi->next; pj; pj = pj->next)
    	if (pi->rows > pj->rows)
    	{
    		t = *pi;
    		*pi = *pj;
    		*pj = t;

}

现在里面的元素已经交换了，但是你也把链表之间的关系破坏了，你要把它的指向

给它还原回去，所以我们添加一步。

for (pi = head.next; pi;pi=pi->next)
    	for (pj = pi->next; pj; pj = pj->next)
    	if (pi->rows > pj->rows)
    	{
    		t = *pi;
    		*pi = *pj;
    		*pj = t;
    
    		pt = pi->next;
    		pi->next = pj->next;
    		pj->next = pt;
    	}

现在程序就大功告成了，相对于重新排布结构体的指向，能简单很多，也能好理解好多。

# 程序实现 #

void *ordering(point head)
    {
    	 point *pi, *pj, *pt, t;
    	for (pi = head.next; pi;pi=pi->next)
    	for (pj = pi->next; pj; pj = pj->next)
    	if (pi->rows > pj->rows)
    	{
    		t = *pi;
    		*pi = *pj;
    		*pj = t;
    
    		pt = pi->next;
    		pi->next = pj->next;
    		pj->next = pt;
    	} 
    
    return pi;}