`
xitong
  • 浏览: 6158391 次
文章分类
社区版块
存档分类
最新评论

单链表的冒泡排序

 
阅读更多

起因

今天利用空余时间在九度做ACM的时候,需要对单链表进行排序,由于单链表不是随机存取结构,所以我不建议用快速排序,因此采用了冒泡排序!

带头节点的尾插法构建单链表

//初始化带头节点的链表
struct lnode *head, *s, *r, *p;
head = malloc(sizeof(struct lnode));
r = head;
for(i = 0; i < n; i ++)
{
	scanf("%d", &d);
	s = malloc(sizeof(struct lnode));
	s -> data = d;
	r -> next = s;
	r = s;
}
r -> next = NULL;

冒泡排序——单链表

/**
 * Description:单链表的冒泡排序
 */
void BubbleSort(struct lnode *head)
{
	struct lnode *f, *p, *x, *y;
	f = NULL;
	//判断是否只有一个元素或者没有元素
	if(head -> next == NULL || head -> next -> next == NULL)
	{
		return;
	}
	while(f != head->next->next)
	{
		//外层是N - 1次循环,升序
		for(p = head; p -> next -> next != f; p = p -> next)
		{
			if(p -> next -> data > p -> next -> next ->data)
			{
				x = p -> next;
				y = p -> next -> next;
				p -> next = y;
				x -> next = y -> next;
				y -> next = x;
			}
		}
		f = p -> next;
	}
}

九度ACM遍历链表

题目描述:

建立一个升序链表并遍历输出。

输入:

输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。

输出:

可能有多组测试数据,对于每组数据,
将n个整数建立升序链表,之后遍历链表并输出。

样例输入:
4
3 5 7 9
样例输出:
3 5 7 9

AC代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct lnode
{
	int data;
	struct lnode *next;
};

void BubbleSort(struct lnode * head);
int main()
{
	int n, i, d;

	while(scanf("%d", &n) != EOF)
	{
		//初始化带头节点的链表
		struct lnode *head, *s, *r, *p;
		head = malloc(sizeof(struct lnode));
		r = head;
		for(i = 0; i < n; i ++)
		{
			scanf("%d", &d);
			s = malloc(sizeof(struct lnode));
			s -> data = d;
			r -> next = s;
			r = s;
		}
		r -> next = NULL;
		
		//冒泡排序
		BubbleSort(head);

		//打印输出
		for(p = head -> next; p != NULL; p = p -> next)
		{
			if(p -> next == NULL)
			{
				printf("%d\n", p -> data);
			}else
			{
				printf("%d ", p -> data);
			}
		}
	}

	return 0;
}

/**
 * Description:单链表的冒泡排序
 */
void BubbleSort(struct lnode *head)
{
	struct lnode *f, *p, *x, *y;
	f = NULL;
	//判断是否只有一个元素或者没有元素
	if(head -> next == NULL || head -> next -> next == NULL)
	{
		return;
	}
	while(f != head->next->next)
	{
		for(p = head; p -> next -> next != f; p = p -> next)
		{
			if(p -> next -> data > p -> next -> next ->data)
			{
				x = p -> next;
				y = p -> next -> next;
				p -> next = y;
				x -> next = y -> next;
				y -> next = x;
			}
		}
		f = p -> next;
	}
}









分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics