节点插入(线性表)

节点插入(线性表)

时间: 1ms        内存:128M

描述:

有一个有序单链表(从小到大排序),表头指针为head,编写一个函数向该单链表中插入一个元素为x的结点,使插入后该链表仍然有序。

输入:

输入长度n:5

输入数据:1 6 8 9 10

输入插入数据:7

输出:

输出:1 6 7 8 9 10

示例输入:

4
1 2 3 4
6

示例输出:

1 2 3 4 6 

提示:

参考答案(内存最优[748]):

#include <stdio.h>
#include <stdlib.h>
typedef struct shu
{
	int date ;
	struct shu *link;
}S;
S *creat(int n)
{
	S *p,*q,*head;
	head=p=q=malloc(sizeof(S));
	scanf("%d",&p->date);
	while(--n)
	{
		p=malloc(sizeof(S));
		scanf("%d",&p->date);
		q->link=p;
		q=p;
	}
	q->link=NULL;
	return head;
}
void play(S *h)
{
	S *p,*min,*t,*head,x;
	scanf("%d",&x.date);
	for(p=h;p!=NULL;p=p->link)
		if(x.date<p->date)
			break;
		else
			min=p;
	if(p==h)
	{
		head=&x;
		head->link=h;
	}
	else
	{
		head=h;
		if(p==NULL)
		{
			min->link=&x;
			x.link=NULL;
		}
		else
		{
			x.link=min->link;
			min->link=&x;
		}
	}
	for(p=head;p!=NULL;p=p->link)
		printf("%d ",p->date);
}
int main()
{
	int n;
	S *head;
	scanf("%d",&n);
	head=creat(n);
	play(head);
	return 0;
}

参考答案(时间最优[0]):

#include <stdio.h>
#include <stdlib.h>
typedef struct shu
{
	int date ;
	struct shu *link;
}S;
S *creat(int n)
{
	S *p,*q,*head;
	head=p=q=malloc(sizeof(S));
	scanf("%d",&p->date);
	while(--n)
	{
		p=malloc(sizeof(S));
		scanf("%d",&p->date);
		q->link=p;
		q=p;
	}
	q->link=NULL;
	return head;
}
void play(S *h)
{
	S *p,*min,*t,*head,x;
	scanf("%d",&x.date);
	for(p=h;p!=NULL;p=p->link)
		if(x.date<p->date)
			break;
		else
			min=p;
	if(p==h)
	{
		head=&x;
		head->link=h;
	}
	else
	{
		head=h;
		if(p==NULL)
		{
			min->link=&x;
			x.link=NULL;
		}
		else
		{
			x.link=min->link;
			min->link=&x;
		}
	}
	for(p=head;p!=NULL;p=p->link)
		printf("%d ",p->date);
}
int main()
{
	int n;
	S *head;
	scanf("%d",&n);
	head=creat(n);
	play(head);
	return 0;
}

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

点赞

发表评论

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