orderlist.h

该程序主要完成集合运算方面的一些内容

typedef int ElemType;

typedef struct NodeType{
ElemType data;
NodeType *next;
}NodeType, *LinkType;                  // 结点类型和指针类型

typedef struct{
LinkType head,tail;         // 分别指向有序链表的头结点和尾结点
int size;                   // 链表当前的长度
int curpos;                 // 当前被操作的元素在有序表中的位置
LinkType current;           // 当前指针，指向链表中第 curpos 个元素
}OrderedList;                   // 有序链表类型

status InitList(OrderedList &L)
{
// 构造一个带头结点的空的有序链表L，并返回TRUE
// 若分配空间失败，则令L.head为NULL，并返回FALSE
   L.head = new NodeType;
   if(!L.head) return FALSE;
   L.head->data = 0;                // 头结点的数据域暂虚设元素为0
   L.head->next = NULL;
   L.current = L.tail = L.head;
   L.curpos = L.size = 0;
   return TRUE;
} //InitList

void DestroyList(OrderedList &L)
{
// 销毁链表 
	LinkType p;
  while (L.head->next){
	   p = L.head->next;
	   L.head->next = p->next;
	   delete p;
  }//while
 delete L.head;
}//DestroyList

ElemType GetElem(OrderedList L, int i )
{
// 若1≤i≤ListLength(L)，则返回L中第 i 个元素，否则返回MAXINT
// MAXINT为予设常量，其值大于有序表中所有元素
  if ((i<1)||(i>L.size))
     return MAXINT;
  if (i == L.curpos)
     return L.current->data;
  if (i < L.curpos) {
     L.curpos = 0;  L.current = L.head;
  }
  else {
     L.curpos++;   L.current = L.current->next;
  }
  while ( L.curpos < i ) {
     L.curpos++;  L.current = L.current->next;
  }
  return L.current->data;
}//GetElem

int LocatePos(OrderedList &L, ElemType e) 
{
// 若有序表L中已存在值和e相同的元素，则返回它在有序表中的序号；
// 否则返回 0，此时 L.current 指示插入位置，即插在它之后
	
	if (!L.head) return 0;           // 有序表不存在
	if ( e==L.current->data ) return L.curpos;
	
	if ( e<L.current->data){
		L.current = L.head; 
		L.curpos = 0;
	}	
	if (L.head->next&&e==L.head->next->data) return 1;
	while ( L.current->next &&(e>L.current->next->data)){
		
		L.current = L.current->next;  
		L.curpos++; 
	}
	if ( (!L.current->next) || ( e < L.current->next->data ) ) return 0;
	else  return L.curpos;
}//LocatePos

void InsertElem(OrderedList &L, ElemType e ) 
{
// 若有序表L中不存在其值和 e 相同的元素，则按有序关系插入之，
// 否则空操作。插入之后，当前指针指向新插入的结点
	LinkType s;
	if (!LocatePos (L, e)) {
		s = new NodeType;   s->data = e;
		s->next = L.current->next; 
		L.current->next = s;
		if ( L.tail == L.current ) L.tail = s;
		L.current = s; 
		L.curpos++; 
		L.size++;
	}//if
}//InsertElem

void DeleteElem(OrderedList &L,  int i ) 
{
 // 若1≤i≤ListLength(L)，则删除有序表L中第 i 个数据元素，否则空操作
	int pre;
	LinkType q;
	if ((i>=1) && (i<=L.size)) {
     pre = GetElem(L, i-1);
     q = L.current->next;
     L.current->next = q->next;     // 删除第 i 个元素
     if ( L.tail == q )
        L.tail = L.current;
     delete q;                      // 释放结点空间
     L.size--;
  }//if
}//DeleteElem

void output(LinkType p)
{                                     
   // 作为被visit导入的指针函数
	   cout<<p->data<<",";
}// output

void ListTraverse(OrderedList &L, void(*visit)(LinkType))
{
   // 依次对L的每个结点元素调用函数visit( )
	LinkType p;
   if (L.head){
p = L.head->next;
      while(p) { visit(p); p = p->next;}
   }
}//ListTraverse