/*****链式表的类定义和实现*****/
#include <iostream>
using namespace std;
#define LEN 50

class Linklist
{
public:
Linklist* next;
Linklist()
{
next=NULL;
}
int data;
void Push(Linklist** refhead,int data);//添加节点
void Insert(Linklist* head,Linklist* pio);//插入节点
void Display(Linklist* head);//显示链表
int Length(Linklist* head);//统计节点数目
Linklist* Find(Linklist* head,int data);//查找节点地址
void Delete(Linklist* head,int data);//删除节点
void Sort(Linklist* head,int mark);//对链表排序mark>0为升序
};
Linklist* head=new Linklist;
//插入一个元素到合适的位置
void Linklist::Insert(Linklist* head,Linklist* pio)
{
Linklist *cur,*bef;
cur=bef=head;
while(cur != NULL)
{ if(cur->data >= pio->data)
break;
else
{bef=cur;
cur=cur->next;
}
}
if(cur==head)
{ pio->next=head;
head=pio;
}
else
{
bef->next=pio;
pio->next=cur;
}
}
//返回要寻找的数据的内存地址
Linklist* Linklist::Find(Linklist* head,int data)
{
bool bo=true;
Linklist* cur;
cur=head;
while(cur != NULL)
{
if(cur->data==data){
bo=false;
break;}
cur=cur->next;
}
if(bo==true){
cout<<"It is no have the Linklist!"<<endl;
return NULL;
}
return cur;
}
//计算链表的长度
int Linklist::Length(Linklist* head)
{
int count=0;
Linklist* cur;
cur=head;
while(cur != NULL)
{
cur=cur->next;
count++;
}
return count;
}
//建立新结点
void Linklist::Push(Linklist** refhead,int data)
{
Linklist* newLinklist=new Linklist;
newLinklist->data=data;
newLinklist->next=*refhead;
*refhead=newLinklist;
}
//对链表遍历
void Linklist::Display(Linklist* head)
{
Linklist *temp=new Linklist;
temp=head;
if(temp==NULL)
cout<<"The Linklist is empty!"<<endl;
else
{
while(temp!=NULL)
{
cout<<temp->data<<"\t";
temp=temp->next;
}
cout<<endl;
}
}
//删除链表中数据和data相等的元素
void Linklist::Delete(Linklist* head,int data)
{
Linklist *cur,*bef;
cur=bef=head;
while(cur != NULL)
{
if(cur->data==data)
break;
else
{
bef=cur;
cur=cur->next;
}
}
if(cur==head)
{
cur->next=head;
delete cur;
}
else
{
bef->next=cur->next;
delete cur;
}
}

//对链表进行有序的排序，mark>0时升序mark>=0时降序
void Linklist::Sort(Linklist* head,int mark)
{
    int a[LEN+1];
    int k,t;
    Linklist* cur;
    cur=head->next;
    for(k=0;cur!=NULL;k++,cur=cur->next)
        a[k]=cur->data;
    for(int i=0;i<k;i++){
        for(int j=0;j<k-i;j++)
        {
            if((mark>0 && a[j]>a[j+1]) || (mark<=0 && a[j]<a[j+1]))
            {
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
    }
    cur=head->next;
    for(int l=0;l<k;l++,cur=cur->next)
        cur->data=a[l];
    return;
}