linktable.~cpp

一个高速缓冲类（缓冲池）

#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;
  //根据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);     
}