linklist.h

数据结构

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 ERRORMESSAGE(char *s)                 
{
   cout<<s<<endl;
   exit(1);
} //ERRORMESSAGE

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;
		}
}

int 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;
	}    		
}

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

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

int 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;
}

int 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


int 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;
}