链表插入(线性表)

2020年1月17日 773点热度 0人点赞 0条评论

链表插入(线性表)

时间: 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 

提示:

参考答案:

解锁文章

没有看到答案?微信扫描二维码可免费解锁文章

微信扫描二维码解锁

使用微信扫描二维码打开广告页面后可以立即关闭,再刷新此页面即可正常浏览此文章

所跳转广告均由第三方提供,并不代表本站观点!

已经扫描此二维码?点此立即跳转

code

这个人很懒,什么都没留下

文章评论