int main(void)
{
	ElemType site[11] = { 'a', 'n', 'o', 't', 'h', 'e', 'r', 'h', 'o', 'm', 'e' };
	LinkList *Link, *LinkR;
	ElemType e;

	CreateListF(Link, site, 11);
	CreateListR(LinkR, site, 11);
	DispList(Link);
	DispList(LinkR);
	DestroyList(LinkR);
	if (ListEmpty(Link))
	{
		printf("List is empty\n");
	}
	else
	{
		printf("List isn't empty\n");
	}
	printf("ListLength: %d\n", ListLength(Link));
	GetElem(Link, ListLength(Link), e);
	ListInsert(Link, 2, e);
	DispList(Link);
	ListDelete(Link, 3, e);
	DispList(Link);
	printf("The location of 'o' is %d\n", LocateElem(Link, 'o'));
	DestroyList(Link);

	return 0;
}

// 9. 求两个单链表相交的第一个节点
ListNode * ListFirstCrossNodeOf2List(ListNode * head1, ListNode * head2)
{
	if(head1 == NULL || head2 == NULL) return NULL;
	if(!ListIsCrossed(head1, head2)) return NULL;

	int len1 = ListLength(head1);
	int len2 = ListLength(head2);
	ListNode * p = head1;
	ListNode * q = head2;
	if(len1 > len2) {
		int m = len1 - len2;
		while(m > 0) {
			p = p->next;
			m--;
		}
	} else {
		int n = len2 - len1;
		while(n > 0) {
			q = q->next;
			n--;
		}
	}

	while(p != q) {
		p = p->next;
		q = q->next;
	}

	return p;
}

/**************************************************
函数功能:获取链表某一位置处的值
参数1:链表头指针
参数2:待获取元素的位置
参数3(Output):返回元素
参数4:函数指针，指出为数据赋值的方式
返回值:无
说明:
头文件: <assert.h>
        <stdlib.h>
		<stdio.h>
作者: Lee.C
完成时间:2015-05-10
修改时间:2016-05-04
修改说明:代码重构
**************************************************/
void GetLinkListItem(const LinkList L, size_t n, LinkListItem *e, void (*Assgin)(LinkListItem *dst, const LinkListItem *src))
{
	assert(L);
	assert(L->next);
	assert(n >= 1 && n <= ListLength(L));
	
	/*******************************************
	 * current : 指向链表待获取处的节点，
	             初始值为指向链表第一个元素的指针
	 * currentPos : 待获取处的节点位置，从第1个节点算起
	*******************************************/
	LNode *current = L->next;
	size_t currentPos = 1;

	while(current && currentPos < n)
	{
		current = current->next;
		currentPos++;
	}

	if(!current || currentPos > n)
	{
		fputs("Call GetItem() ERROR !\n", stdout);
		fprintf(stdout, "The List`s length is %lu,the get location %lu is overflow\n", ListLength(L), n);
		exit(EXIT_FAILURE);
	}

	Assgin(e, &current->data);
}

/* 链表删除 */
Status DeleteNode(LinkList &L, int i) {
    LinkList p = (LinkList) malloc (sizeof(LNode));
    LinkList q = (LinkList) malloc (sizeof(LNode));
    if(i <= 0 || i > ListLength(L)) return ERROR;
    int j = 0;

    if (i == 1) {
        q = L;    
        L = L->next;
    } else if (i == ListLength(L) + 1) {
        for (p = L; p->next->next != NULL; p = p->next)
            q = p->next->next;
        p->next = NULL;
    } else {
        p = L;
        while (p->next && j < i - 2) {
            p = p->next; ++j;
        }
        if (!p->next || j > i - 1) return ERROR;

        q = p->next;
        p->next = q->next;
    }
    free(q);

    return OK;
}

/*
 * 给定两个单链表，找出两个链表的公共节点
 * 思路：由于每个单链表节点只有一个next域，所以从第一个公共节点开始往后，链表都是重合的
 * 先遍历两个链表，得到链表的长度，并求出长度差，在长链表上先遍历长度之差个节点之后，再
 * 同步遍历两个链表，直到找到相同的节点，或者一直到链表结束
 * 时间复杂度O(len1 + len2)
 */
void search_common(LinkList La, LinkList Lb)
{
    int len1 = ListLength(La);
    int len2 = ListLength(Lb);
    int dist;
    LinkList longlist, shortlist;

    if ( len1 > len2 )
    {
        longlist = La->next;
        shortlist = Lb->next;
        dist = len1 - len2;
    }
    else
    {
        longlist = Lb->next;
        shortlist = La->next;
        dist = len2 - len1;
    }

    while ( dist-- )
        longlist = longlist->next;
    while ( longlist )
    {
        if ( longlist == shortlist )
            ListTraverse(longlist, print);
        else
        {
            longlist = longlist->next;
            shortlist = shortlist->next;
        }
    }
}

 void MergeList(SqList La,SqList Lb,SqList &Lc) // 算法2.2
 { // 已知线性表La和Lb中的数据元素按值非递减排列。
   // 归并La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列
   int i=1,j=1,k=0;
   int La_len,Lb_len;
   ElemType ai,bj;
   InitList(Lc); // 创建空表Lc
   La_len=ListLength(La);
   Lb_len=ListLength(Lb);
   while(i<=La_len&&j<=Lb_len) // 表La和表Lb均非空
   {
     GetElem(La,i,ai);
     GetElem(Lb,j,bj);
     if(ai<=bj)
     {
       ListInsert(Lc,++k,ai);
       ++i;
     }
     else
     {
       ListInsert(Lc,++k,bj);
       ++j;
     }
   } // 以下两个while循环只会有一个被执行
   while(i<=La_len) // 表La非空且表Lb空
   {
     GetElem(La,i++,ai);
     ListInsert(Lc,++k,ai);
   }
   while(j<=Lb_len) // 表Lb非空且表La空
   {
     GetElem(Lb,j++,bj);
     ListInsert(Lc,++k,bj);
   }
 }

int main(int argc, char *argv[])
{
	DataType a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9,};
	DataType b[] = {10, 11, 12, 13, 14, 15};
	DataType e;

	CirList A;	/* 声明循环链表A和B */
	CirList B;
	p_CirList C = NULL;

	InitList(&A);	/* 初始化 */
	InitList(&B);
	C = &A;

	/* 插入元素 */
	Insert_Elem(&A, a, sizeof(a) / sizeof(DataType));
	Insert_Elem(&B, b, sizeof(b) / sizeof(DataType));

	printf("循环链表A中有%d个元素\n", ListLength(A));
	ListTraverse(A, Show_Elem);
	
	putchar('\n');

	printf("循环链表B中有%d个元素\n", ListLength(B));
	ListTraverse(B, Show_Elem);

	puts("\n\n");

	if (GetElem(&A, 8, &e))
		printf("循环链表A第8个元素是%4d\n", e);
	
	if (GetElem(&B, 5, &e))
		printf("循环链表B第5个元素是%4d\n", e);
	putchar('\n');

	printf("删除链表B最后一个元素\n");
	ListDelete(&B, 6, &e);
	ListTraverse(B, Show_Elem);

	putchar('\n');

	C = Merge(&A, &B);	/* 合并 */
	
	printf("合并后的链表有%d个元素\n", ListLength(*C));
	ListTraverse(*C, Show_Elem);	

	putchar('\n');
	
	if (GetElem(C, 14, &e))
		printf("合并后的链表第14个元素是%4d\n", e);

	ClearList(&A);
	ClearList(&B);
	
	putchar('\n');
	
	exit(EXIT_SUCCESS);
}

status GetElem(SqList *L, int i, ElemType e)
{
	if(ListLength(L)==0 || i>ListLength(L) || i<1) {
		return ERROR;
	}
	*e = L.data[i-1];
	
	return OK;
}

Term wdbg(Term t, Term ind)
	{
	t=CompoundArg1(t);
	t=GetAtomProperty(t,PROP_TYPE);
	t=CompoundArg1(t);
	printf("%d terms %d inds\n",ListLength(CompoundArg1(t)),
			ListLength(CompoundArg2(t)));
	return 0;
	}

int main(int argc, const char * argv[]) {
    int a[10] = {1,3,9,8,4,2,5,0,7.6};
    int b[4] = {2,2,3};
    int c[4] = {1,3,3,4};
    SeqList list;//这个怎么直接全部赋值

    fillList(&list, a, 10);
    
    printf("获取位置:%d\n",Locate(list, 2));//按内容查找
    
    printf("插入:%s\n",InsList(&list,2,10)==1?"OK":"ERROR");//插入
    
    int delement;
    printf("删除：%s,删除的元素：%d\n",DelList(&list,3,&delement)==1?"ok":"ERROR",delement);//删除
    
    
    SeqList list1,list2,list3;
    
    fillList(&list1,b,3);
    fillList(&list2,c,4);
    
    mergeList(&list1,&list2,&list3);//合并两个非递减有序线性表
    printf("合并后的list：%d\n",list3.elem[7]);
    
    printf("---------%s---------\n","链表");
    
    //----------链表-------
    
    LinkList L;
    InitList(&L);
    
    //CreateFromHead(L);
    CreateFormTail(&L);
    
    Node *p = Get(L, 2);
    printf("链表的第2个节点：%c\n",p->data);
    
    
    Node *pp = Located(L,'2');
    printf("key是2的节点：%c\n",pp->data);
    
    printf("链表的长度是：%d\n",ListLength(L));
    
    InseList(L,1,'5');
    printf("插入后的链表长度：%d,首节点：%c\n",ListLength(L),Get(L, 1)->data);
    
    char tem;
    DellList(L,1,&tem);
    printf("链表长度%d,删除链表元素:%c\n",ListLength(L),tem);
    
    LinkList Lb = L;
    printf("合并后的长度%d\n",ListLength(MergeLinkList(L,Lb)));
    return 0;
}

void Union(List &La, List Lb) {  // 算法2.1
  // 将所有在线性表Lb中但不在La中的数据元素插入到La中
  int La_len,Lb_len,i;
  ElemType e;
  La_len = ListLength(La);          // 求线性表的长度  
  Lb_len = ListLength(Lb);
  for (i=1; i<=Lb_len; i++) {
    GetElem(Lb, i, e);              // 取Lb中第i个数据元素赋给e
    if (!LocateElem(La, e, equal))  // La中不存在和e相同的数据元素
      ListInsert(La, ++La_len, e);  // 插入
  }
} // union

void unionL(SqList *La,SqList Lb)
{
	ElemType e;
	int La_len=ListLength(*La);
	int Lb_len=ListLength(Lb);
	for (int i=1;i<=Lb_len;i++)
	{
		GetElem(Lb,i,&e);
		if (!LocateElem(*La,e))
			ListInsert(La,++La_len,e);
	}
}

void GetPowerSet(int i, List A, List &B) {  // 算法6.15
   // 线性表A表示集合A，线性表B表示幂集ρ(A)的一个元素。
   // 局部量k为进入函数时表B的当前长度。
   // 第一次调用本函数时，B为空表，i＝1。
   ElemType x;
   int k;
   if (i > ListLength(A)) Output(B); // 输出当前B值，即ρ(A)的一个元素
   else { 
      GetElem(A, i, x);        k = ListLength(B);
      ListInsert(B, k+1, x);   GetPowerSet(i+1, A, B);
      ListDelete(B, k+1, x);   GetPowerSet(i+1, A, B);
   }
} // GetPowerSet

void unionL(SqList *La, SqList Lb) /* union Lb to La */
{				
    int La_len, Lb_len, i;
    ElemType e;
    La_len = ListLength(*La);
    Lb_len = ListLength(Lb);

    for (i = 1; i <= Lb_len; ++i) {
	GetElem(Lb, i, &e);
	if (!LocateElem(*La, e))
	    ListInsert(La, ++La_len, e);
    }
    
}

static void alg1_fix_w1(Term w)
	{
	List wi;
	List l1,l2,al;
	
	if(is_empty_list(CompoundArg2(w)))
		return;
	
	wi=NewList();
	l1=CompoundArg1(w);
	while(!is_empty_list(ListTail(l1)))
		{
		wi=AppendLast(wi,CompoundArg2(ListFirst(l1)));
		l1=ListTail(l1);
		}
	al=CompoundArg2(w);
	
	if(!is_empty_list(wi))
	while(!is_empty_list(al))
		{
		Term a1;
		List wia;
		a1=ListFirst(al);
		wia=NewList();
		l1=CompoundArg2(a1);
		while(!is_empty_list(l1))
			{
			wia=AppendLast(wia,CompoundArg2(ListFirst(l1)));
			l1=ListTail(l1);
			}
		if(ListLength(wi)!=ListLength(wia))
			{
			puts("Internal error a1fw");
			longjmp(alg1_jmp_buf,1);
			}
		l1=wi;
		l2=wia;
		while(!is_empty_list(l1))
			{
			rename_ind(a1,ListFirst(l2),ListFirst(l1));
			l1=ListTail(l1);
			l2=ListTail(l2);
			}
		FreeAtomic(wia);
		al=ListTail(al);
		}
	FreeAtomic(wi);		
	
	}

void union_func(SqList *La, SqList Lb)
{
	int La_length, Lb_length, i;

	ElemType e;
	La_length = ListLength(*La);
	Lb_length = ListLength(Lb);
	
	for( i=1; i <= Lb_length; i++) {
		GetElem(Lb, i, &e);
		if( !LocateElem(*La, e) ) {
			ListInsert(La, ++La_length, e);
		}
	}
}

static Term finda2(List pl, int del)
{
	int pli, ii;
	List l;
	pli=ListLength(pl);
	mmmpos=0;
	for(ii=0;ii<LagrHashSize;ii++)
	{
	
		for(l=lagr_hash[ii];l;l=ListTail(l))
		{
			List cpl=CompoundArg1(ListFirst(l));
			List vpl=0;
			List ll1,ll2;
			int pos=1;

			if(cpl==0 || ListLength(cpl)!=pli)
				continue;
			for(ll1=cpl;ll1;ll1=ListTail(ll1),pos++)
			{
				Atom a,prp;
				a=CompoundArg1(ListFirst(ll1));
				prp=GetAtomProperty(a,PROP_TYPE);
				if(is_compound(prp)&&CompoundName(prp)==OPR_FIELD &&
					CompoundArg2(prp)==NewInteger(4))
					a=CompoundArg1(prp);
				if(a==mmm)
					mmmpos=pos;
				vpl=AppendLast(vpl,a);
			}
				
			vpl=SortedList(vpl, acmp);

			for(ll1=pl,ll2=vpl;ll1;ll1=ListTail(ll1),ll2=ListTail(ll2))
				if(ListFirst(ll1)!=ListFirst(ll2))
					break;
			if(is_empty_list(ll1))
				break;
		}
	if(l)
		break;
	}
	
	if(l && del)
		lagr_hash[ii]=CutFromList(lagr_hash[ii],l);
	
	return l;
}

int main()
{
    StaticLinkList L;
    Status i;
    i=InitList(L);
    printf("初始化L后：L.length=%d\n",ListLength(L));

    i=ListInsert(L,1,'F');
    i=ListInsert(L,1,'E');
    i=ListInsert(L,1,'D');
    i=ListInsert(L,1,'B');
    i=ListInsert(L,1,'A');

    printf("在L的表头依次插入FEDBA后：\nL.data=");
    ListTraverse(L);

    i=ListInsert(L,3,'C');
    printf("\n在L的“B”与“D”之间插入“C”后：\nL.data=");
    ListTraverse(L);

    i=ListDelete(L,1);
    printf("\n在L的删除“A”后：\nL.data=");
    ListTraverse(L);

    printf("\n");

    return 0;
}

void main()
{
	DLinkList *h;
	ElemType e;
	printf("(1)初始化循环双链表h\n");
	InitList(h);
	printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");
	ListInsert(h,1,'a');
	ListInsert(h,2,'b');
	ListInsert(h,3,'c');
	ListInsert(h,4,'d');
	ListInsert(h,5,'e');
	printf("(3)输出循环双链表h:");
	DispList(h);
	printf("(4)循环双链表h长度=%d\n",ListLength(h));
	printf("(5)循环双链表h为%s\n",(ListEmpty(h)?"空":"非空"));
	GetElem(h,3,e);
	printf("(6)循环双链表h的第3个元素=%c\n",e);
	printf("(7)元素a的位置=%d\n",LocateElem(h,'a'));
	printf("(8)在第4个元素位置上插入f元素\n");
	ListInsert(h,4,'f');
	printf("(9)输出循环双链表h:");
	DispList(h);
	printf("(10)删除h的第3个元素\n");
    	ListDelete(h,3,e);
	printf("(11)输出循环双链表h:");
	DispList(h);
	printf("(12)释放循环双链表h\n");
	DestroyList(h);
}

void main()
{
	SqList *L;
	ElemType e;
	printf("(1)初始化顺序表L\n");
	InitList(L);
	printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");
	ListInsert(L,1,'a');
	ListInsert(L,2,'b');
	ListInsert(L,3,'c');
	ListInsert(L,4,'d');
	ListInsert(L,5,'e');
	printf("(3)输出顺序表L:");
	DispList(L);
	printf("(4)顺序表L长度=%d\n",ListLength(L));
	printf("(5)顺序表L为%s\n",(ListEmpty(L)?"空":"非空"));
	GetElem(L,3,e);
	printf("(6)顺序表L的第3个元素=%c\n",e);
	printf("(7)元素a的位置=%d\n",LocateElem(L,'a'));
	printf("(8)在第4个元素位置上插入f元素\n");
	ListInsert(L,4,'f');
	printf("(9)输出顺序表L:");
	DispList(L);
	printf("(10)删除L的第3个元素\n");
    	ListDelete(L,3,e);
	printf("(11)输出顺序表L:");
	DispList(L);
	printf("(12)释放顺序表L\n");
	DestroyList(L);
}