//面对对象风格的单链表排序.

//现在的主要问题是，排序的列表中不能出现0，原因是与NULL冲突.
#include <iostream>
using namespace std;

const long int MAX = 2147483647;   //长整形的最大值,即 (2^31)-1，在当前编译器中，int和long int都是4字节32位

typedef class LNode//重命名struct LNode为LNode 
{
private:
    long int data;
    LNode *next;//在结构体中可以直接使用新名字LNode 
public:
    void CreateLinklist(LNode*& head);
    void printLinklist(LNode* p);
    void CopyLinklist(LNode*& head, LNode* b);
    void sort(LNode*& headA, LNode* p);
}LNode;

void LNode::CreateLinklist(LNode*& head)
{
    cout << "请输入数字创建链表，以9999结束。\n";
    head = new LNode;
    head->next = nullptr;
    LNode* flag;
    flag = head;
    long int t;
    cin >> t;
    while (t != 9999)
    {
        flag->data = t;
        flag->next = new LNode;    //new会返回一个地址
        flag = flag->next;
        cin >> t;
    }
    flag->next = nullptr;
    flag = head;
}

void LNode::printLinklist(LNode *p)
{
    if (p->data == NULL)
        cout << "链表为空。\n";
    else
    {
        cout << "链表的结构为:\n";
        while (p->next != nullptr)
        {
            cout << p->data;
            p = p->next;
            if (p->next != nullptr)
                cout << " -> ";
        }
    }
}

void LNode::CopyLinklist(LNode *&head, LNode *b)
{
    head = new LNode;
    head->next = nullptr;
    LNode* flag;
    flag = head;
    while (b->next != nullptr)
    {
        flag->data = b->data;
        flag->next = new LNode;
        flag = flag->next;
        b = b->next;
    }
    flag->next = nullptr;
    flag = head;
}


void LNode::sort(LNode *&headA, LNode *p)
{
    LNode* copy;
    copy->CopyLinklist(copy, p);
    headA = new LNode;
    headA->next = nullptr;
    LNode* flagA;
    LNode* flagB;
    LNode* flagC;
    flagA = headA;
    flagB = copy;
    flagC = copy;
    long int g;
    int num = 0;
    while (copy->next != nullptr)
    {
        copy = copy->next;
        num++;
    }
    cout<<"该排序链表共有"<<num<<"个结点。\n";
    copy = flagB;
    g = copy->data;
    if (num == 0)
        cout << "该排序链表为空！";
    else
    {
        while (num > 0)
        {
            while (copy->next != nullptr)
            {
                if (g > copy->data && copy->data != NULL)
                {
                    g = copy->data;
                    flagC = copy;
                }
                copy = copy->next;
            }
            flagC->data = MAX;    //将当前最小值设为一个原链表绝对不可能达到的极大值
            flagA->data = g;
            flagA->next = new LNode;
            flagA = flagA->next;
            flagA->next = nullptr;
            copy = flagB;
            g = MAX;
            num--;
        }
        flagA = headA;
    }
}

int main()
{
    LNode* LA;
    LA->CreateLinklist(LA);
    printf("\n");
    LA->printLinklist(LA);
    printf("\n");
    printf("\n");
    LNode* LB;
    LB->sort(LB, LA);
    printf("\n");
    LB->printLinklist(LB);
    return 0;
}