linklist.h

数据结构基本算法实现 用C++实现理发馆防真功能

/************************* 出错信息处理函数定义 ***********************/
 
void ERRORMESSAGE(char *s)                 
{
   cout<<s<<endl;
   exit(1);
} //ERRORMESSAGE


/****************************** 各种类型定义 **************************/
 	
typedef struct{
	int OccurTime;//事件发生时刻
	int NType;
}ElemType,Event;

typedef struct LNode{ //结点类型
	ElemType data;
	struct LNode *next;
}*Link,*Position;

typedef struct {    //链表类型
	Link head,tail;
	int len;
	Link current;
}LinkList;

void visit(Link p)
{   
    cout<<p->data.OccurTime<<",";
	cout<<p->data.NType<<" ";
}
void InitList(LinkList &L)
{ //建立一个空的单链表
	L.current=new LNode;
	L.current->next=NULL;
	if(!L.current) ERRORMESSAGE("OVERFLOW");
	else
	{
		L.head=L.tail=L.current;
	    L.len=0;
		}
}

status MakeNode(Link &p,ElemType e)
{ //分配由p指向的值为e的结点，并返回OK，若分配失败返回ERROR
	p=new LNode;
	if(!p) return ERROR;
	else
	{   p->data.OccurTime=e.OccurTime;
	    p->data.NType=e.NType;
		p->next=NULL;
	    return OK;
	}    		
}

status FreeNode(Link &p)
{ //释放p所指结点
	delete p;
	return OK;
}
 
void DestroyList(LinkList &L) //销毁单链表L
   { Link p,q;
     p=L.head;
     while(p){
	  q=p;
	  p=p->next;
	  FreeNode(q);
     }
    L.head=NULL;
   }//destroyList_L

int ListLength(LinkList L)
{  //求表长
	int i=L.len;
	return i;
} //ListLength

status ListEmpty(LinkList L)
{  //判断链表是否为空
	if(ListLength(L)==0) return OK;
	 else return ERROR;
}

void ClearList(LinkList &L)
{Link p;
 while(L.head->next){
 	p=L.head->next;L.head->next=p->next;
    FreeNode(p);}
 L.len=0;
 L.current=L.tail=L.head;
}//clearlist

status DelFirst(LinkList &L,ElemType &e)
{Link p;
 if (L.head->next==NULL) return ERROR;
 p=L.head->next;
 e.OccurTime=p->data.OccurTime;
 e.NType=p->data.NType;
 L.head->next=p->next;
 if(L.current==p) L.current=L.head->next;
 if(L.tail==p) L.tail=L.head;
 delete(p);
 L.len--;
 return OK;
}


ElemType GetCurElem(LinkList L)
{  //返回当前指针的数据元素
	ElemType e;
	e=L.current->data;
	return e;
}

status SetCurElem(LinkList &L,ElemType e)
{  //更新当前指针的数据元素
	L.current->data=e;
	return OK;
}

status Prior(LinkList &L)
{  //改变当前指针指向其前驱
	Link p;
	p=L.head;
	if(p==L.current||!L.current) return ERROR;//若当前指针指向头结点，返回ERROR
	while(p->next!=L.current)  p=p->next;
	L.current=p;
	return OK;
}	

status Next(LinkList &L)
{  //改变当前指针指向其后继
	if(!L.current) return ERROR;//L.current为空
    else 
	{  L.current=L.current->next;
	   return OK;
	}
}//next

status LocatePos(LinkList &L,int i)
{  //改变当前指针指向第i个结点                     
	int k=0;
	Link p=L.head;
	if (i>L.len||i<0) return ERROR;
	//i值不合理，当i等于零时L.current指向头结点
	while(k!=i) {p=p->next;k++;}
    L.current=p;
	return OK;
}//Locatepos

status GetElem(LinkList L,int i,ElemType &e)
{  //以e返回L中第i个元素值
	LocatePos(L,i);
	e=GetCurElem(L);
    return OK;
}

status InsAfter(LinkList &L,ElemType e)
{ //若当前指针在链表中，则将数据元素e插入表L中当前指针所指结点之后，
  //并返回OK，否则返回ERROR         
    Link s;
	if(!L.current) return ERROR;
	if(!MakeNode(s,e)) return ERROR;
	s->next=L.current->next;
	L.current->next=s;
	if(L.tail==L.current) L.tail=s;
	L.current=s;
	L.len++;
	return OK;
}

status OrderInsert(LinkList &L,ElemType e)
{ Link p,r,q;
  if(!MakeNode(p,e)) return ERROR;
  q=L.head;
  r=q->next;
  while(r&&(p->data.OccurTime>r->data.OccurTime)) {q=r;r=r->next;}
  if(!r) {
	  L.tail->next=p;
      if(L.current==L.tail) L.current=p;
	  L.tail=p;
  }
  else{p->next=r;
       q->next=p;
       L.current=p;
  }
  L.len++;
  return OK;
}

status DelAfter(LinkList &L,ElemType &e)
{  //若当前指针及其后继在链表中，则删除表L中当前指针所指结点之后的结点，
	//并返回OK，否则返回ERROR 
	Link q;
	if(!(L.current&&L.current->next)) return ERROR;
	q=L.current->next;
	L.current->next=q->next;
	if(L.tail==q) L.tail=L.current;
	e=q->data;
	L.current=L.current->next;
	FreeNode(q);
	L.len--;
	return OK;
}//DelAfter

status ListTraverse(LinkList L,void(*visit)(Link))
{
	if(!L.head->next)return ERROR;
	L.current=L.head->next;
	while(L.current){
		(*visit)(L.current);
		L.current=L.current->next;
	}
	cout<<endl;
	return OK; 
}