输入一组数，构建有序链表 （C语言实现）

要求说明

输入一组数，构建有序链表。

整体思路

用数组保存这组数，每次都去找最小值，把最小值构建结点并使用头插法插入到单链表中。 然后将该值删掉(为简便起见，把值弄成MAX)。

这里使用的是类直接插入的排序方法。

代码实现

#include <stdio.h> #include <stdlib.h> #define MAX 1000000 // 单链表结构体定义 typedef struct node { int val; struct node *next; } node; // 顺序打印链表 void printNode(node* L) { while(L->next!=NULL) { L = L->next; printf("%d ",L->val); } } int main() { int n,i,j; //因为要求有序，所以每次都去数组中找最小的值 int min=MAX; int min_index = -1; int arr[100]; scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d",&arr[i]); } // 表头结点head 和 需要插入的结点s node *head,*s; // 生成表头结点，表头结点不存放数据 head = (node*)malloc(sizeof(node)); head->next = NULL; for(i=0; i<n; i++) { for(j=0; j<n; j++) { if(min>arr[j]) { min = arr[j]; min_index = j; } } // 头插法构建单链表 s = (node*)malloc(sizeof(node)); s->val = min; s->next = head->next; head->next = s; // 初始化最小值标识 arr[min_index] =MAX; min = MAX; } // 输出单链表 printNode(head); return 0; }

运行结果

由于我们每次都是找最小值，故是从小到大的顺序插入。

而我们使用的是头插法，故最终结果从大到小。

所以如果想要让最终的单链表从小到大，每次都找最大值即可。

10 1 9 5 4 3 2 1 5 8 6 9 8 6 5 5 4 3 2 1 1