使用c++写一个链表排序
时间: 2023-03-10 10:32:11 浏览: 132
我可以给你一个简单的例子:使用C语言写一个链表排序:#include <stdio.h>
#include <stdlib.h>
// 定义一个结构体,包含链表的值和下一个节点的指针
struct node
{
int data;
struct node *next;
};
// 创建链表
struct node *createList(int n)
{
struct node *head = NULL, *p = NULL;
int i;
for (i=0; i<n; i++)
{
// 分配内存空间
struct node *temp =
(struct node *)malloc(sizeof(struct node));
int x;
printf("输入第 %d 个元素的值:", i+1);
scanf("%d", &x);
temp->data = x;
temp->next = NULL;
// 如果是第一个节点,则设置head指针
if (i==0)
{
head = temp;
p = head;
}
else
{
// 否则把新节点接到链表末尾
p->next = temp;
p = temp;
}
}
return head;
}
// 使用选择排序对链表进行排序
struct node *selectionSort(struct node *head)
{
struct node *p, *q, *r, *s, *temp;
// 将头指针置为NULL
r = NULL;
while (head != NULL)
{
// 将最小的值的地址保存到p中
for (p=head, q=head; q!=NULL; q=q->next)
{
if (q->data < p->data)
p = q;
}
// 从链表中删除最小的节点
for (q=head, s=NULL; q!=p; s=q, q=q->next);
if (s == NULL)
head = p->next;
else
s->next = p->next;
// 把最小值插入到新的链表中
p->next = NULL;
if (r == NULL)
r = p;
else
{
for (temp=r; temp->next!=NULL; temp=temp->next);
temp->next = p;
}
}
return r;
}
// 输出链表中的元素
void printList(struct node *head)
{
while (head != NULL)
{
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
// 主函数
int main()
{
int n;
printf("输入链表的元素个数:");
scanf("%d", &n);
// 创建一个新的链表
struct node *head = createList(n);
printf("排序前:");
printList(head);
// 使用选择排序对链表进行排序
head = selectionSort(head);
printf("排序后:");
printList(head);
return 0;
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)