首页 > 代码库 > 链表版冒泡排序

链表版冒泡排序

2024-11-21 00:46:39   202人阅读

　　基本原理就是尾插法建立链表（当然，也可以用头插法建立链表），重点是冒泡排序法中的两层for循环的参数设置，设置两个链表指针p、q：

　　第一个用来指向头结点后一个(p = head ->next)(p还有个作用就是排序的步骤数)，第二个用来指向头结点后一个的后一个(q = p -> next)，每次内层循环q指针往后移一个结点，然后和第一个节点存储的数据相比较，完成交换，直到第一次排序完毕为止，整个过程中，p指针一直指向的是第一个数。第二次，p就指向后一个节点，q指向p所指向的节点的后一个节点，然后同前面的操作一样，依次类推。其实实际上就像用指针做冒泡排序时一样。

　　用图形可视化来描述这个过程肯定更能清晰一些，这里用五个数(5、4、3、2、1)来做例子（图中p、q 是链表指针）：

技术分享

 

　　综上所述，我们可以写出冒泡排序代码：

typedef struct sortLinkList
{
    int data;
    struct sortLinkList * next;
}sortLinkList;

/*
 *****************************
 * 初始条件:已创建链表sortLinkList
 * 设置两个链表指针 sortLinkList *p, *q
 * int s; s用做完成数据交换的容器
 *****************************
 */
for(p = head -> next; p != NULL; p = p -> next)
      for(q = p -> next; q != NULL; q = q -> next)
           if((p -> data) > (q -> data))
               s = q -> data, q -> data = http://www.mamicode.com/p -> data, p -> data = s;

　　实在不会的小伙伴请看这里

　　完整代码：

技术分享 
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define N 100

typedef int Element;

typedef struct sortLinkList
{
    Element data;
    struct sortLinkList * next;
}sortLinkList;

sortLinkList * head, * tail, * current;

int main()
{
    int i;
    sortLinkList * p, * q;
    Element swap;

    head = (sortLinkList *)malloc(sizeof(sortLinkList));
    tail = head;
    srand(time(0));
    for(i = 0; i < N; i++)
    {
        current = (sortLinkList *)malloc(sizeof(sortLinkList));
        current -> data = http://www.mamicode.com/rand()%N*20 + 1;
        tail-> next = current;
        tail = current;
    }

    tail -> next = NULL;

    for(p = head -> next; p != NULL; p = p -> next)
        for(q = p -> next; q != NULL; q = q -> next)
            if((p -> data) > (q -> data))
                swap = q -> data, q -> data = http://www.mamicode.com/p -> data, p -> data = swap;

    p = head -> next;
    while(p)
    {
        printf("%d ",p -> data);
        p = p -> next;
    }
    putchar(‘\n‘);

    return 0;
}
sortLinkList

 

链表版冒泡排序


联系
我们