排序(线性表)
时间： 1ms 内存：128M
描述：
（线性表）已知不带头结点的线性链表node，链表中结点构造为（data、next），其中data为数据域，next为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。#include <stdio.h>
#include <stdlib.h> //对应malloc函数
struct Node
{
int data;
struct Node *next;
};
struct Node *creat(struct Node *head) //尾插建表
{
int n,i;
struct Node *current=NULL,*previous=NULL;
head=NULL;
scanf("%d",&n);
for(i=1; i<=n; i++)
{
current=(struct Node*)malloc(sizeof(struct Node));
scanf("%d",¤t->data);
current->next=NULL;
if(i==1)
head=current; //链表头
else
previous->next=current;
previous=current;
}
return head;
}
struct Node *sort(struct Node *head) //插入排序
{
struct Node *unsorted,*previous,*current,*sorted,*inserted;
if(head==NULL)
return NULL;
unsorted=head->next; //剩余未排序链表
head->next=NULL; //摘下首结点
sorted=head; //已排序链表
while(unsorted!=NULL) //还有未排序结点
{
inserted=unsorted; //当前插入结点
unsorted=unsorted->next;
current=sorted;
while((current!=NULL)&&(current->data<inserted->data))
{
previous=current;
current=current->next;
}
if(current==sorted) //插入到链表的头部
sorted=inserted;
else
/**************/添加代码
/**************/
}
return sorted;
}
void destroy(struct Node *head)
{
struct Node *p;
while(head!=NULL)
{
p=head->next;
delete(head);
head=p;
}
}
int main()
{
struct Node *head=NULL;
head=creat(head);
head=sort(head);
while(head!=NULL)
{
printf("%d ",head->data);
head=head->next;
}
destroy(head);
return 0;
}
输入：
输入链表长度：5
输入数据：10 22 9 8 6
输出：
6 8 9 10 22
示例输入：
7
11 3 8 9 44 26 55示例输出：
3 8 9 11 26 44 55 提示：
参考答案（内存最优[752]）：
#include"stdio.h"
#include"stdlib.h"
int n,i;
struct node{
int date;
struct node *next;
};
struct node *creat(struct node *head)
{
struct node *p1=NULL,*p2=NULL;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
p1=(struct node*)malloc(sizeof(struct node));
scanf("%d",&p1->date);
p1->next=NULL;
if(i==1)
head=p1;
else
p2->next=p1;
p2=p1;
}
return head;
}
struct node *sort(struct node *head)
{
struct node *first,*p,*q,*t;
first=head->next;
head->next=NULL;
while(first!=NULL)
{
for(t=first,q=head;((q!=NULL)&&(q->date<t->date));p=q,q=q->next);
first=first->next;
if(q==head)
head=t;
else
p->next=t;
t->next=q;
}
return head;
}
int main(){
struct node *head=NULL,*temp;
head=creat(head);
temp=sort(head);
while(temp)
{
printf("%d ",temp->date);
temp=temp->next;
}
return 0;
}
参考答案（时间最优[0]）：
#include"stdio.h"
#include"stdlib.h"
int n,i;
struct node{
int date;
struct node *next;
};
struct node *creat(struct node *head)
{
struct node *p1=NULL,*p2=NULL;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
p1=(struct node*)malloc(sizeof(struct node));
scanf("%d",&p1->date);
p1->next=NULL;
if(i==1)
head=p1;
else
p2->next=p1;
p2=p1;
}
return head;
}
struct node *sort(struct node *head)
{
struct node *first,*p,*q,*t;
first=head->next;
head->next=NULL;
while(first!=NULL)
{
for(t=first,q=head;((q!=NULL)&&(q->date<t->date));p=q,q=q->next);
first=first->next;
if(q==head)
head=t;
else
p->next=t;
t->next=q;
}
return head;
}
int main(){
struct node *head=NULL,*temp;
head=creat(head);
temp=sort(head);
while(temp)
{
printf("%d ",temp->date);
temp=temp->next;
}
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。