起因
今天利用空余时间在九度做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;
}
}
分享到:
相关推荐
数据结构,单链表冒泡法排序数据结构,C++实现,可输入式程序
java冒泡排序集锦方法!所有的方法都有!很不错的!希望对大家有帮助哈哈!
冒泡排序C语言实现 冒泡排序C语言实现 冒泡排序C语言实现
vs2010环境c++实现冒泡排序 这个地方return的必须是全局变量或者是引用参数传递过来的变量;否则,得不到;;“采用引用返回方式时,返回的不能是函数中的局部变量,这时返回的局部变量地址已经失效
单向链表实现倒置,冒泡排序,插入排序,快速排序,在linux下的gcc实现
大二实验作业 顺序表,单链表,顺序表应用,冒泡排序,折半查找 写在一个form窗口
使用c#语言编写的winform程序,实现顺序表、单链表、顺序栈、冒泡排序、折半查找 源代码和程序展示: 顺序表:https://blog.csdn.net/HAIIAKU/article/details/119302855 单链表:...
利用冒泡法排序,是一种经典的排序法,两重FOR循环
对数据结构不是很熟,用c++实现的单链表反转,冒泡和选择排序,有问题的话请批评指正
关于单链表的快速排序 堆排序和冒泡排序,基于指针的交换,对理解指针偶帮助
C语言实现键盘输入数据构建链表后冒泡排序,工程在VS2005下编译通过并运行无误。
1、链表排序 [问题描述] 建立一个...设计要求:利用随机函数产生10个样本,每个样本有20000随机整数,利用直接插入排序、希尔排序,冒泡排序、快速排序、选择排序、堆排序,归并排序,基数排序八种排序方法进行排序
链表创建、排序操作
通过冒泡排序进行单链表的有序插入,并将这两个有序单链表合并成一个有序单链表,使用两个单链表的原有空间进行合并,将生成的有序单链表输出显示
这个头文件实现了链表有关的基本操作,包括:发现链表是否有环、求环入口及环长度、求两个链表是否相交、反转链表、还有各种排序操作,基于链表的插入排序,冒泡排序、选择排序、合并排序、快速排序
文档包括带表头单链表的实现,双链表的操作,双链表的冒泡排序,不带表头的单链表,双向链表、链表节点的排序
冒泡排序、快速排序、归并排序,向链表中添加和删除数据
整理一下之前的作业,说不定会帮上别人 如果其中选做题没有源码或没有运行截图,那是因为作者也未完成,请见谅 一、查找与排序实验(1)——查找 ... 改进冒泡排序 题目3. 以单链表为存储结构的简单选择排序
Java实现单链表的增删改查以及选择、冒泡、反转排序等功能的实现!