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