头歌数据结构-单链表的排序操作

第1关单链表的冒泡排序算法300学习内容参考答案记录评论任务描述相关知识编程要求测试说明任务描述本关任务输入N个无序的整数建立一个无序链表利用冒泡排序算法将链表中的结点按照数值非降序排列。相关知识单链表结点类型定义如下typedef struct LNode // 结点类型定义{ElemType data; //数据域struct LNode *next; //指针域}LNode,*LinkList; // LinkList为结构指针类型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(i1; in; i ) //输入数组所有元素 { input(a[i]); } InitList(head); for(i1;in;i) //将数组元素插入到单链表head中 { ListInsert(head, i, a[i]); } BubbleSort(head); return 0; } /*****ElemType类型元素的基本操作*****/ void input(ElemType s) { cins; } void output(ElemType s) { couts ; } void swap(ElemType a,ElemType b) { ElemType t; ta; ab;bt; } /*****单链表的基本操作*****/ void InitList(LinkList L) { // 操作结果构造一个空的单链表L L(LinkList)malloc(sizeof(LNnode)); // 产生头结点并使L指向此头结点 if(!L) // 存储分配失败 return ; L-nextNULL; // 指针域为空 } 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 pL-next; while(p) { vi(p-data); pp-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;ii-next){ if(i-data i-next-data){ swap(i-data,i-next-data); } } t i; ListTraverse(L,output); } /********** End **********/ }第2关单链表的选择排序算法100学习内容参考答案记录评论任务描述相关知识编程要求测试说明任务描述本关任务输入N个无序的整数建立一个无序链表利用选择排序算法将链表中的结点按照数值非降序排列。相关知识单链表结点类型定义如下typedef struct LNode // 结点类型定义{ElemType data; //数据域struct LNode *next; //指针域}LNode,*LinkList; // LinkList为结构指针类型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(i1; in; i ) //输入数组所有元素 { input(a[i]); } InitList(head); for(i1;in;i) //将数组元素插入到单链表head中 { ListInsert(head, i, a[i]); } SelectedSort(head); return 0; } /*****ElemType类型元素的基本操作*****/ void input(ElemType s) { cins; } void output(ElemType s) { couts ; } void swap(ElemType a,ElemType b) { ElemType t; ta; ab;bt; } /*****单链表的基本操作*****/ void InitList(LinkList L) { // 操作结果构造一个空的单链表L L(LinkList)malloc(sizeof(LNnode)); // 产生头结点并使L指向此头结点 if(!L) // 存储分配失败 return ; L-nextNULL; // 指针域为空 } 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 pL-next; while(p) { vi(p-data); pp-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 **********/ }