#include<iostream.h>
#include<stdlib.h>
#include"linktable.h"
 
//初始化單鏈表
void LINKTABLE::InitList(LNode*& HL)
{
    HL=NULL;  
}
 
//清空單鏈表
void LINKTABLE::ClearList(LNode*& HL)
{
       LNode *cp, *np;  
       cp=HL;  
       while(cp!=NULL)  
       {
              np=cp->next;  
              delete cp;  
              cp=np;  
       }
       HL=NULL;  
}
 
//求單鏈表長度
int LINKTABLE::ListSize(LNode* HL)
{
       LNode* p=HL;
       int i=0;
       while(p!=NULL) {
              i++;
              p=p->next;
       }
       return i;
}
 
//檢查線性表是否為空
bool LINKTABLE::ListEmpty(LNode* HL)
{
       return (HL==NULL);
}
 
//返回單鏈表中指定序號的結點值
ElemType LINKTABLE::GetElem(LNode* HL, int pos)
{
       if(pos<1) {
              cerr<<"pos is out range!"<<endl;
              return -1;
       }
       LNode* p=HL;
       int i=0;
       while(p!=NULL) {
              i++;
              if(i==pos) break;
              p=p->next;
       }
       if(p!=NULL)
              return p->data;
       else {
              cerr<<"pos is out range!"<<endl;
              return -1;
       }
}
 
//遍歷單鏈表
void LINKTABLE::TraverseList(LNode* HL)
{
       LNode* p=HL;
       while(p!=NULL) {
              cout<<p->data<<" ";
              p=p->next;
       }
       cout<<endl;
}
 
//從單鏈表中查找元素
bool LINKTABLE::FindList(LNode* HL, ElemType& item)
{
       LNode* p=HL;
       while(p!=NULL) 
              if(p->data==item) {
                     item=p->data;
                     return true;
              }
              else
                     p=p->next;
       return false;
}
 
//更新單鏈表中的給定元素
bool LINKTABLE::UpdateList(LNode* HL, const ElemType& item)
{
       LNode* p=HL;
       while(p!=NULL)  //查找元素 
              if(p->data==item)
                  break;
        else
                     p=p->next;
       if(p==NULL) 
              return false;
       else {  //更新元素
              p->data=item;
              return true;
       }
}
 
//向單鏈表插入元素
//mark>0 向表頭插入結點；mark<0 向表尾插入結點 其他自由插入
void LINKTABLE::InsertList(LNode*& HL, const ElemType& item, int mark)
{
  //建立一個值為item的新結點
       LNode* newptr;
       newptr=new LNode;  
       newptr->data=item;  
  //向表頭插入結點
    if(mark>0) {  
              newptr->next=HL; HL=newptr;
       }
  //向表尾插入結點
       else if(mark<0) {  
                  if(HL==NULL) {newptr->next=NULL; HL=newptr;}
                  else {
                         LNode* p=HL;
                      while(p->next!=NULL)  
                             p=p->next;
                      p->next=newptr; newptr->next=NULL;
                     }
       }
  //插入到合適位置
       else { 
           LNode* cp;  
           LNode* ap;  
        ap=NULL; cp=HL;
              while(cp!=NULL) {
                  if(item<cp->data) break;
            else {ap=cp; cp=cp->next;}
              }
           if(ap==NULL) {newptr->next=HL; HL=newptr;}
           else {newptr->next=cp; ap->next=newptr;}
       }
}
 
//從單鏈表中刪除元素
//mark >0 刪除表頭結點; mark <0 刪除表尾結點 其他為刪除值為item結點
bool LINKTABLE::DeleteList(LNode*& HL, ElemType& item, int mark)
{
       if(HL==NULL) return false;
  //刪除表頭結點
       if(mark>0) {
              LNode* p=HL;
              item=HL->data;
           HL=HL->next;
           delete p;
           return true;
       }
  //刪除表尾結點
       else if(mark<0) {
                     LNode *cp=HL, *ap=NULL;
                     while(cp->next!=NULL) {
                            ap=cp; cp=cp->next;
                     }
               if(ap==NULL) HL=NULL;
                     else ap->next=cp->next; 
                     item=cp->data;
                     delete cp;
                     return true;
       }
  //刪除值為item結點
       else {
           LNode *cp=HL, *ap=NULL;
           while(cp!=NULL)
                  if(cp->data==item) break;
            else {ap=cp; cp=cp->next;}
           if(cp==NULL) return false;
              else {
            if(ap==NULL) HL=HL->next;
               else ap->next=cp->next;
            item=cp->data;
                     delete cp;
               return true;
              }
       }
}
//對單鏈表進行有序輸出
void LINKTABLE::OrderOutputList(LNode* HL, int mark)
{
       if(HL==NULL) {cout<<"鏈表為空!"<<endl; return;}
  //建立新的單鏈有序表的表頭結點
       LNode* head=new LNode;  //head為新建有序表的表頭指針
       head->data=HL->data; head->next=NULL;
  //根據(jù)HL單鏈表生成head單鏈有序表
       for(LNode* p=HL->next; p; p=p->next) {
              LNode* q=new LNode;
              q->data=p->data;
              LNode *cp=head, *ap=NULL;
         //為向head單鏈表插入q結點而順序查找合適位置
              while(cp) {
                     if(mark==1) {
                            if(q->data<cp->data) break;
                            else {ap=cp; cp=cp->next;}
                     }
                     else {
                            if(q->data>cp->data) break;
                            else {ap=cp; cp=cp->next;}
                     }
              }
         //把q結點插入head有序單鏈表中
              if(ap==NULL) {q->next=head; head=q;}
              else {
                     q->next=cp; ap->next=q;
              }
       }
  //遍歷head有序單鏈表
    TraverseList(head);  
  //清除head有序單鏈表
    ClearList(head);     
}