学习笔记------数据结构(C语言版) 扩展的线性单链表及归并

//Function realization.cpp

#include"predefined.h"
#include"ExtenLinkedList.h"
Status MakeNode_E(Link *p,ElemType e)
//分配由p指向的值为e的结点，并返回OK；
//若分配失败，则返回ERROE。
{
	(*p)=(Link)malloc(sizeof(LNode));
	if(!(*p)) exit(OVERFLOW);
	(**p).data=e;
	(**p).next=NULL;
	return OK;
}

void FreeNode_E(Link *p)
//释放p所指的结点。
{
	free(*p);
	*p=NULL;
}

Status InitList_E(LinkList *L)
//构造一个空的线性链表L。
{
	Link p;
	p=(Link)malloc(sizeof(LNode));
	if(!p) exit(OVERFLOW);
	(*p).next=NULL;
	(*p).data=0;
	(*L).head=(*L).tail=p;
	(*L).len=0;
	return OK;
}

Status DestroyList_E(LinkList *L)
//销毁线性链表L，L不再存在。
{
	Link p,q;  
	p=(*L).head;  
    while(p)  
    {  
        q=p;
  		p=(*p).next;
		free(q); 
    }
	(*L).head=(*L).tail=NULL;
	(*L).len=0;
    return OK;
}

Status ClearList_E(LinkList *L)
//将线性链表L重置为空表，并释放原链表的结点空间。
{
	Link p,q;
	p=(*(*L).head).next;
	while(p)
	{
		q=p;
		p=(*p).next;
		free(q);
	}
	(*(*L).head).next=NULL;
	(*L).len=0;
	(*L).tail=(*L).head;
	return OK;
}

Status InsFirst_E(LinkList *L,Link h,Link s)
//已知h指向线性链表的头结点,将s所指结点插入在第一个结点之前。
{
	(*s).next=(*h).next;
	(*h).next=s;
	(*L).len++;
	if((*L).tail==h) (*L).tail=s;
	return OK;
}

Status DelFirst_E(LinkList *L,Link h,Link *q)
//已知h指向线性链表的头结点，删除链表中的第一个结点并以q返回。
{
	if(!((*h).next)) return ERROR;
	if(!(*(*h).next).next) (*L).tail=(*L).head;
	*q=(*h).next;
	(*h).next=(*(*h).next).next;
	(*L).len--;
	return OK;
}

Status Append_E(LinkList *L,Link s)
//将指针s所指(彼此以指针相连)的一串结点链接在线性表L的最后一个结点
//之后，并改变链表L的尾指针指向新的尾结点。
{
	Link p,q;
	int count=0;
	p=(*L).tail;
	(*p).next=s;
	while(s)
	{
		q=s;
		s=(*s).next;
		count++;
	}
	(*L).tail=q;
	(*L).len+=count;
	return OK;
}

Status Remove_E(LinkList *L,Link *q)
//删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点。
{
	Link p,r;
	p=(*L).head;
	if(p)
	{
		while((*p).next)
		{
			r=p;
			p=(*p).next;
		}
		(*r).next=NULL;
		*q=p;
		(*L).tail=r;
		(*L).len--;
		return OK;
	}
	*q=NULL;
	return FALSE;
}

Status InsBefore_E(LinkList *L,Link *p,Link s)
//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前，
//并修改指针p指向新插入的结点。
{
	if(!(*p)||(*L).head==*p||!(*L).head) return ERROR;
	Link q,r;
	q=(*L).head;
	while(!(q==*p))
	{
		r=q;
		q=(*q).next;
		if(!q) return ERROR;
	}
	(*s).next=*p;
	(*r).next=s;
	*p=s;
	(*L).len++;
	return OK;
}

Status InsAfter_E(LinkList *L,Link *p,Link s)
//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后，
//并修改指针p指向新插入的结点。
{
	if(!(*p)||!(*L).head) return ERROR;
	Link q;
	(*s).next=(**p).next;
	(**p).next=s;
	if(!(**p).next) (*L).tail=s;
	*p==s;
	(*L).len++;
	return OK;
}

Status SetCurElem_E(Link *p,ElemType e)
//已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值。
{
	if(!(*p)) return ERROR;
	(**p).data=e;
	return OK;
}

ElemType GetCurElem_E(Link p)
//已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值。
{ 
	if(!p) return ERROR;
	return (*p).data;
}

Status ListEmpty_E(LinkList L)
//若线性表L为空表，则返回TRUE，否则返回FALSE。
{
	if(L.len==0) return TRUE;
	else return FALSE;
}

int ListLength_E(LinkList L)
//返回线性链表L中元素的个数。
{
	return L.len;
}

Position GetHead_E(LinkList L)
//返回线性链表L中头结点的位置。
{
	return L.head;
}

Position GetLast_E(LinkList L)
//返回线性链表L中最后一个结点的位置。
{
	return L.tail;
}

Position PriorPos_E(LinkList L,Link p)
//已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置，
//若无前驱，则返回NULL。
{
	if((L.head==p)||(*L.head).next==p) return NULL;
	Link q,r;
	q=L.head;
	while(!(q==p))
	{
		r=q;
		q=(*q).next;
		if(!q) return NULL;
	}
	return r;
}

Position NextPos_E(LinkList L,Link p)
//已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的位置，
//若无后继，则返回NULL。
{
	return (*p).next;
}

Status LocatePos_E(LinkList L,int i,Link *p)
//返回p指示线性链表L中第i个结点的位置并返回OK，i值不合法时返回ERROR。
{
	*p=L.head;
	if(i<0||i>L.len) return ERROR;
	while(*p&&i>0)
	{
		(*p)=(**p).next;
		i--;
	}
	return OK;
}

Position LocateElem_E(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
//返回链表L中第1个与e满足函数compare()判定关系的元素的位置，
//若不存在这样的元素，则返回NULL。
{
	Link p;
	p=(*(L).head).next;
	while(p&&!compare((*p).data,e))
		p=(*p).next;
	return p;
}

Status ListTraverse_E(LinkList L,Status(*visit)(ElemType))
//依次对L中每个元素调用函数visit()。一旦visit()失败，则操作失败。
{
	Link p;
	int i;
	p=(*(L).head).next;
	for(i=0;i<L.len;i++)
	{
		visit((*p).data);
		p=(*p).next;
	}
	return OK;
}

Status ListInsert_L_E(LinkList *L,int i,ElemType e)
//算法2.20：在带头结点的单链线性表L的第i个元素之前插入元素e
{
	Link h,s;
	if(!LocatePos_E(*L,i-1,&h)) return ERROR;
	if(!MakeNode_E(&s,e)) return ERROR;
	InsFirst_E(L,h,s);
	return OK;
}

Status MergList_L_E(LinkList *La,LinkList *Lb,LinkList *Lc,int (*compare)(ElemType,ElemType))
//算法2.21：已知单链线性表La和Lb的元素按值非递减排列。
//归并La和La得到新的单链线性表Lc，Lc的元素也按值非递减排列。
{
	Position ha,hb,pa,pb;
	ElemType a,b;
	Link q;
	if(!InitList_E(Lc)) return ERROR;
	ha=GetHead_E(*La);
	hb=GetHead_E(*Lb);
	pa=NextPos_E(*La,ha);
	pb=NextPos_E(*Lb,hb);
	while(pa&&pb)
	{
		a=GetCurElem_E(pa);
		b=GetCurElem_E(pb);
		if(compare(a,b)<=0)
		{
			DelFirst_E(La,ha,&q);
			InsFirst_E(Lc,(*Lc).tail,q);
			pa=NextPos_E(*La,ha);
		}
		else
		{
			DelFirst_E(Lb,hb,&q);
			InsFirst_E(Lc,(*Lc).tail,q);
			pb=NextPos_E(*Lb,hb);
		}
	}
	if(pa) Append_E(Lc,pa);
	else Append_E(Lc,pb);
	FreeNode_E(&ha);
	FreeNode_E(&hb);
	return OK;
}#include"predef