若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

2211: 链表插入(线性表)

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,391

题目描述

本题只需要提交填写部分的代码
(线性表)已知一单向链表,从第二个结点至表尾递增有序,(设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 

参考代码

#include<stdio.h>
int main() 
{
    int n,i,j,a[80],t;
    scanf("%d",&n);
    for (i=0;i<n;i++)
            scanf("%d",&a[i]);
    for (i=0;i<n;i++)
            for (j=i+1;j<n;j++) 
    {
        if(a[i]>a[j]) 
        {
            t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    for (i=0;i<n;i++)
                printf("%d ",a[i]);
    return 0;
}

解析

暂无

hustoj

发表评论 取消回复

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

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

原站点 Skip Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist