linklist.h

理发馆问题。基于vc的模拟试验.包括试验设计文稿。

//--------------------出错信息处理函数--------------------------------------------
void ERRORMESSAGE(char *s)                 
{
   cout<<s<<"，程序将自动退出！"<<endl;
   exit(1);
}

typedef struct{
	int OccurTime;     //事件发生时刻
	int NType;         //事件状态
}ElemType,Event;       //如果NType==0表示顾客还未被分配到理发，此时Occurtime表示顾客到达时间
                       //如果NType==1表示顾客已开始理发，此时Occurtime表示顾客离去时间

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("初始化链表失败");
	else
	{
		L.head=L.tail=L.current;
	    L.len=0;
		}
}

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

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

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

//--------------------判断链表是否为空---------------------------------------
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;
}

//--------------------删除链表第一个元素，存储到e中--------------------------
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;
    else 
	{  L.current=L.current->next;
	   return OK;
	}
}

//--------------------改变当前指针指向第i个结点------------------------------
status LocatePos(LinkList &L,int 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;
}

//--------------------以e返回L中第i个元素值----------------------------------
status GetElem(LinkList L,int i,ElemType &e)
{
	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;
}

//--------------------按照OccurTime大小顺序插入元素值------------------------
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;
}

//--------------------列举元素值--------------------------------------------
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; 
}