排序(线性表)

排序(线性表)

时间: 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",&current->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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注