编程：有序的链表

编程：有序的链表

时间： 1ms        内存：128M

描述：

链表是一种最常用的线性结构数据的表示方式。下面的程序中，给出了结点类和链表类的声明。请将程序补充完整，使输入一个负数之后，前面输入的非负数可以呈升序输出。请在begin到end中间写上需要的代码，并提交这部分程序。
#include<iostream>
using namespace std;
class Node
{
private:
    int data;
    Node *next;
public:
    Node(int n)
    {
        data=n;
        next=NULL;
    }
    void setNext(Node *n);
    int getData();
    Node *getNext();
};
class List
{
private:
    Node *head;
public:
    List()
    {
        head=NULL;
    }
    void insertlist(Node *s);
    void outputlist();
    ~List();
};
//**********************begin***************************

//*****************end********************
int main()
{
    List A;
    int n;
    cin>>n;
    while(n>0)
    {
        A.insertlist(new Node(n));
        cin>>n;
    }
    A.outputlist();
    return 0;
}

输入：

若干非负数，以一个负数结束

输出：

链表中所有结点元素的值，按升序排列。

示例输入：

6 2 4 1 8 9 11 67 12 -1

示例输出：

1 2 4 6 8 9 11 12 67

提示：

参考答案（内存最优[1092]）：

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


    return 0;
}

参考答案（时间最优[0]）：

#include<iostream>
using namespace std;
class Node
{
private:
    int data;
    Node *next;
public:
    Node(int n)
    {
        data=n;
        next=NULL;
    }
    void setNext(Node *n);
    int getData();
    Node *getNext();
};
class List
{
private:
    Node *head;
public:
    List()
    {
        head=NULL;
    }
    void insertlist(Node *s);
    void outputlist();
    ~List();
};void Node::setNext(Node *n)
{
    next=n;
}
int Node::getData()
{
    return data;
}
Node *Node::getNext()
{
    return next;
}

void List::insertlist(Node *s)  //插入一个值为a结点
{
    Node *p, *q;
    p=head;
    if(head==NULL)    //若是空表，使a作为第一个结点
        head=s;
    else if(p->getData() > s->getData())  //若s是第一个结点
    {
        s->setNext(p);
        head=s;
    }
    else
    {
        while(p->getData() < s->getData() && p->getNext()!=NULL)   //查找结点a
        {
            q=p;
            p=p->getNext();
        }
        if(p->getData() >= s->getData())     //若有比结点a大的点，插入到q后
        {
            q->setNext(s);
            s->setNext(p);
        }
        else                    //结点a作为最后的点；
        {
            p->setNext(s);
        }
    }
}

void List::outputlist()
{
    Node *p = head;
    while(p!=NULL)
    {
        cout<<p->getData()<<" ";
        p=p->getNext();
    }
    cout<<endl;
    return;
}

List::~List()
{
    Node *p = head, *q;
    while(p!=NULL)
    {
        q=p;
        p=p->getNext();
        delete q;
    }
}
//*****************end********************
int main()
{
    List A;
    int n;
    cin>>n;
    while(n>0)
    {
        A.insertlist(new Node(n));
        cin>>n;
    }
    A.outputlist();
    return 0;
}

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