YTU2211链表插入(线性表)-阿南达文事网

YTU 2211 链表插入(线性表)

风华是一指流砂，苍老是一段年华。

题目描述

本题只需要提交填写部分的代码

（线性表）已知一单向链表，从第二个结点至表尾递增有序，（设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

样例输入

copy

5
11 7 8 9 10

样例输出

7 8 9 10 11

previous->next=key;key->next=current;