第1关：单链表的冒泡排序算法

300

• 学习内容
• 参考答案
• 记录
• 评论

• 任务描述
• 相关知识
• 编程要求
• 测试说明

任务描述

本关任务：输入N个无序的整数，建立一个无序链表，利用冒泡排序算法将链表中的结点按照数值非降序排列。

相关知识

单链表结点类型定义如下：

1. typedef struct LNode // 结点类型定义
2. {
3. ElemType data; //数据域
4. struct LNode *next; //指针域
5. }LNode,*LinkList; // LinkList为结构指针类型
6. typedef int ElemType;

ElemType类型为int型 。

单链表冒泡排序思想：设置两个指针，一个是当前指针，一个是尾指针，当前的指针指向头节点，将尾指针指向最后一个节点，在当前的指针不等于尾指针时是一次循环，第一次将当前一个节点的值与下一个节点的值相比较，直到下一个节点和尾指针相等（即为空），结束本次循环，最后当前的指针赋给尾指针，当前指针重新指向头结点，再两两相比较，把最大（或最小）的数放在最后。

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成单链表的选择排序算法，，并输出每一次排序后的结果，具体要求如下：

• 函数 BubbleSort() 用冒泡法将带头结点的单链表排成一个有序的单链表

测试说明

平台会对你编写的代码进行测试：

测试输入：1029 62 73 90 46 43 38 76 52 93

输入说明： 第一行为n，表示n个整数。 第二行为n个整数。

预期输出：29 62 73 90 46 43 38 76 52 9329 62 73 46 43 38 76 52 90 9329 62 46 43 38 73 52 76 90 9329 46 43 38 62 52 73 76 90 9329 43 38 46 52 62 73 76 90 9329 38 43 46 52 62 73 76 90 9329 38 43 46 52 62 73 76 90 9329 38 43 46 52 62 73 76 90 9329 38 43 46 52 62 73 76 90 93

开始你的任务吧，祝你成功！

#include <stdlib.h> #include <stdio.h> #include <iostream> using namespace std; /* 定义ElemType为int类型 */ typedef int ElemType; void input(ElemType &s); void output(ElemType s); void swap(ElemType &a,ElemType &b); /* 单链表类型定义 */ typedef struct LNnode { ElemType data; struct LNnode *next; }LNnode,*LinkList; void InitList(LinkList &L); int ListInsert(LinkList &L,int i,int e) ; void ListTraverse(LinkList L,void(*vi)(ElemType)); void BubbleSort(LinkList L); int main() { LinkList head; //定义一个LinkList 型的变量head ElemType a[100 ]; int n,i; scanf("%d",&n); for(i=1; i<=n; i++ ) //输入数组所有元素 { input(a[i]); } InitList(head); for(i=1;i<=n;i++) //将数组元素插入到单链表head中 { ListInsert(head, i, a[i]); } BubbleSort(head); return 0; } /*****ElemType类型元素的基本操作*****/ void input(ElemType &s) { cin>>s; } void output(ElemType s) { cout<<s<<" "; } void swap(ElemType &a,ElemType &b) { ElemType t; t=a; a=b;b=t; } /*****单链表的基本操作*****/ void InitList(LinkList &L) { // 操作结果：构造一个空的单链表L L=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点 if(!L) // 存储分配失败 return ; L->next=NULL; // 指针域为空 } int ListInsert(LinkList &L,int i,int e) { // 在带头结点的单链线性表L的第i个元素之前插入元素e LinkList p,s; p = L; int j = 0; while (p && j < i-1) { // 寻找第i-1个结点 p = p->next; ++j; } if (!p || j > i-1) return 0; // i小于1或者大于表长 s = (LinkList)malloc(sizeof(LNnode)); // 生成新结点 s->data = e; s->next = p->next; // 插入L中 p->next = s; return 1; } void ListTraverse(LinkList L,void(*vi)(ElemType)) { // 初始条件：单链表L已存在。 //操作结果：依次对L的每个数据元素调用函数vi() LinkList p=L->next; while(p) { vi(p->data); p=p->next; } printf("\n"); } void BubbleSort(LinkList L) //单链表的冒泡排序算法 { //用冒泡法将带头结点的单链表排成一个有序的单链表 /********** Begin **********/ LinkList i = L->next; LinkList t = nullptr; ElemType max ; for(LinkList p = L->next;p->next != nullptr;p = p->next){ for(i = L->next;i->next != t && i->next;i=i->next){ if(i->data > i->next->data){ swap(i->data,i->next->data); } } t = i; ListTraverse(L,output); } /********** End **********/ }

第2关：单链表的选择排序算法

100

• 学习内容
• 参考答案
• 记录
• 评论

• 任务描述
• 相关知识
• 编程要求
• 测试说明

任务描述

本关任务：输入N个无序的整数，建立一个无序链表，利用选择排序算法将链表中的结点按照数值非降序排列。

相关知识

单链表结点类型定义如下：

1. typedef struct LNode // 结点类型定义
2. {
3. ElemType data; //数据域
4. struct LNode *next; //指针域
5. }LNode,*LinkList; // LinkList为结构指针类型
6. typedef int ElemType;

ElemType类型为int型 。

单链表选择排序算法思想：在要排序的单链表中，选出一个数据值最小的结点，将这个结点的数据与第一个结点的数据交换；然后在剩下的单链表当中再找值最小的结点与第二个位置结点的数据交换，如此循环到倒数第二个位置结点的数据和最后一个结点数据比较为止。

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成单链表的选择排序算法，，并输出每一次排序后的结果，具体要求如下：

• 函数 SelectedSort( ) 用选择排序算法将带头结点的单链表排成一个有序的单链表

测试说明

平台会对你编写的代码进行测试：

测试输入：1088 84 23 85 32 34 80 52 91 77

预期输出：23 84 88 85 32 34 80 52 91 7723 32 88 85 84 34 80 52 91 7723 32 34 85 84 88 80 52 91 7723 32 34 52 84 88 80 85 91 7723 32 34 52 77 88 80 85 91 8423 32 34 52 77 80 88 85 91 8423 32 34 52 77 80 84 85 91 8823 32 34 52 77 80 84 85 91 8823 32 34 52 77 80 84 85 88 9123 32 34 52 77 80 84 85 88 91

提示： 如果有10个整数，要求输出每趟选择排序共9趟的结果。

开始你的任务吧，祝你成功！

#include <stdlib.h> #include <stdio.h> #include <iostream> using namespace std; /* 定义ElemType为int类型 */ typedef int ElemType; void input(ElemType &s); void output(ElemType s); void swap(ElemType &a,ElemType &b); /* 单链表类型定义 */ typedef struct LNnode { ElemType data; struct LNnode *next; }LNnode,*LinkList; void InitList(LinkList &L); int ListInsert(LinkList &L,int i,int e) ; void ListTraverse(LinkList L,void(*vi)(ElemType)); void SelectedSort(LinkList L); //单链表的选择排序算法 int main() { LinkList head; //定义一个LinkList 型的变量head ElemType a[100 ]; int n,i; scanf("%d",&n); for(i=1; i<=n; i++ ) //输入数组所有元素 { input(a[i]); } InitList(head); for(i=1;i<=n;i++) //将数组元素插入到单链表head中 { ListInsert(head, i, a[i]); } SelectedSort(head); return 0; } /*****ElemType类型元素的基本操作*****/ void input(ElemType &s) { cin>>s; } void output(ElemType s) { cout<<s<<" "; } void swap(ElemType &a,ElemType &b) { ElemType t; t=a; a=b;b=t; } /*****单链表的基本操作*****/ void InitList(LinkList &L) { // 操作结果：构造一个空的单链表L L=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点 if(!L) // 存储分配失败 return ; L->next=NULL; // 指针域为空 } int ListInsert(LinkList &L,int i,int e) { // 在带头结点的单链线性表L的第i个元素之前插入元素e LinkList p,s; p = L; int j = 0; while (p && j < i-1) { // 寻找第i-1个结点 p = p->next; ++j; } if (!p || j > i-1) return 0; // i小于1或者大于表长 s = (LinkList)malloc(sizeof(LNnode)); // 生成新结点 s->data = e; s->next = p->next; // 插入L中 p->next = s; return 1; } void ListTraverse(LinkList L,void(*vi)(ElemType)) { // 初始条件：单链表L已存在。 //操作结果：依次对L的每个数据元素调用函数vi() LinkList p=L->next; while(p) { vi(p->data); p=p->next; } printf("\n"); } void SelectedSort(LinkList L) { //用选择排序算法将带头结点的单链表排成一个有序的单链表 /********** Begin **********/ LinkList i = nullptr; for (LinkList p = L->next; p; p = p->next) { LinkList t = p; for (i = p->next; i; i = i->next) { if (t->data > i->data) { t = i; } } swap(t->data,p->data); ListTraverse(L,output); } /********** End **********/ }