链表插入(线性表)

链表插入(线性表)

时间: 1ms        内存:128M

描述:

本题只需要提交填写部分的代码
(线性表)已知一单向链表,从第二个结点至表尾递增有序,(设a1<x<an)如下图(“第二个结点至表尾”指a1..an )。试编写程序,将第一个结点删除并插入表中适当位置,使整个链表递增有序。
代码:

#include <iostream>
using namespace std;
struct Node
{
    int data;
    Node *next;
};
Node *createlist(Node *head,int n)       //建立链表
{
    Node *previous;    //前驱结点
    Node *current;     //当前结点
    if(n<1)
    {
        return NULL;    //建立空链表
    }
    previous=head=new Node;   //建立首结点
    cin>>head->data;      //输入数据
    while(--n)
    {
        current=new Node;      //建立新结点
        cin>>current->data;      //输入数据
        previous->next=current;     //将新结点挂在表尾    
        previous=current;
    }
    previous->next=NULL;     //置表尾结束标志
    return head;       //返回首结点指针
}
Node *insertsortlist(Node *head)
{
    Node *previous;     //前驱结点
    Node *current;      //当前结点
    Node *key;         //记录首结点
    /* 特殊情况处理 链表为空或只有一个结点或初始升序*/
    if(head==NULL||head->next==NULL||head->data<=head->next->data)  
        return head;
    previous=key=head;    //记录插入结点
    current=head->next;    //当前结点
    head=current;        //首结点后移
    /* 查找第一个比key大的结点 */
    while(current!=NULL&&current->data<=key->data)
    {    
        previous=current;        //记录前驱结点
        current=current->next;    //当前结点后移
    }
    
    if(current==NULL)           //链表结点均不大于首结点
    {                    
        previous->next= key;    //将插入结点挂在表尾
        key->next = NULL;
    }
    else                        //将key插入在previous和next之间
    {    
        /*
        请在该部分填写缺少的代码
        */
    }
    return head;
}
void output(Node *head)
{
    Node *current=head;
    while(current!=NULL)
    {
        cout<<current->data<<" ";
        current=current->next;
    }
}
int main()
{
    int n;
    Node *head=NULL;
    cin>>n;
    head=createlist(head,n);
    if(head==NULL)
        return 0;
    head=insertsortlist(head);
    output(head);
    return 0;
}

输入:

输入长度n:7

输入数据:4 1 2 3 6 8 9

输出:

1 2 3 4 6 8 9

示例输入:

5
11 7 8 9 10

示例输出:

7 8 9 10 11 

提示:

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


#include <iostream>
using namespace std;
struct Node
{
    int data;
    Node *next;
};
Node *createlist(Node *head,int n)       //建立链表
{
    Node *previous;    //前驱结点
    Node *current;     //当前结点
    if(n<1)
    {
        return NULL;    //建立空链表
    }
    previous=head=new Node;   //建立首结点
    cin>>head->data;      //输入数据
    while(--n)
    {
        current=new Node;      //建立新结点
        cin>>current->data;      //输入数据
        previous->next=current;     //将新结点挂在表尾    
        previous=current;
    }
    previous->next=NULL;     //置表尾结束标志
    return head;       //返回首结点指针
}
Node *insertsortlist(Node *head)
{
	Node *previous;     //前驱结点
	Node *current;      //当前结点
	Node *key;         //记录首结点
	/* 特殊情况处理 链表为空或只有一个结点或初始升序*/
	if(head==NULL||head->next==NULL||head->data<=head->next->data)   
		return head;
	previous=key=head;	//记录插入结点
	current=head->next;	//当前结点
	head=current;		//首结点后移
	/* 查找第一个比key大的结点 */
	while(current!=NULL&&current->data<=key->data)
	{	
		previous=current;		//记录前驱结点
		current=current->next;	//当前结点后移
	}
	
	if(current==NULL)           //链表结点均不大于首结点
	{					
		previous->next= key;	//将插入结点挂在表尾
		key->next = NULL;
	}
	else                        //将key插入在previous和next之间
	{head=previous->next;
	}
	return head;
}
void output(Node *head)
{
    Node *current=head;
    while(current!=NULL)
    {
        cout<<current->data<<" ";
        current=current->next;
    }
}
int main()
{
    int n;
    Node *head=NULL;
    cin>>n;
    head=createlist(head,n);
    if(head==NULL)
        return 0;
    head=insertsortlist(head);
    output(head);
    return 0;
}

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

#include<iostream>
#include<stdlib.h>
using namespace std;
struct a
{int b;};
int cmp(const void*a,const void*b)
{return *(int*)a-*(int*)b;}
int main()
{
	int n,i,a[100];
	cin>>n;
	for(i=0;i<n;i++)
		cin>>a[i];
    qsort(a,n,sizeof(int),cmp);
		for(i=0;i<n;i++)
    cout<<a[i]<<" ";
		return 0;
}

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

点赞

发表评论

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