创建一单向链表,并使用复杂度为O(nlg(n))的排序算法对该单向链表进行由小到大排序。
来源:百度知道 编辑:UC知道 时间:2024/09/28 13:56:34
帮个忙!急用!
占个地TvT... 我想说这个10分总归有点太便宜了TvT....
我先琢磨去|||
写注释去...
--
#include <stdio.h>
#include <stdlib.h>
struct s_node
{
int i;
s_node *next;
};
s_node * create_list(int in_n)
{
s_node *head = 0, *p;
head = new s_node;
head->i = rand();
p = head;
for (int i = 1; i < in_n; i++)
{
s_node *n = new s_node;
n->i = rand();
p->next = n;
p = n;
}
return head;
}
s_node _end_node = {0x7FFFFFFF}; // 用来标记排序时子链表的结尾
s_node * sort_list(s_node **in_list, int in_n) // 对给定链表的前n个节点排序,返回第n+1个节点
{
if (in_n == 2) // 链表有两个元素的时候,判断是否交换顺序,并截断
{
s_node *a = *in_list;
s_node *b = a->next;
s_node *r = b->next;
if (a->i > b->i)
{
*in_list = b;
b->next = a;
a-