bo2-6.cpp

数据结构里面中的一元多项式的表示及相加,用到了比较复杂的数据结构

void MakeNode(Link &p,ElemType e)
{
	p=(Link)malloc(sizeof(LNode));
	if(!p)
		exit(ERROR);
	p->data=e;
}

void FreeNode(Link &p)
{
	free(p);
	p=NULL;
}

void InitList(LinkList &L)
{
	Link p;
	p=(Link)malloc(sizeof(LNode));
	if(p)
	{
		p->next=NULL;
		L.head=L.tail=p;
		L.len=0;
	}
	else
		exit(ERROR);
}

void ClearList(LinkList &L)
{
	Link p,q;
	if(L.head!=L.tail)
	{
		p=q=L.head->next;
		L.head->next=NULL;
		while(p!=L.tail)
		{
			p=q->next;
			free(q);
			q=p;
		}
		free(q);
		L.tail=L.head;
		L.len=0;
	}
}

void DestroyList(LinkList &L)
{
	ClearList(L);
	FreeNode(L.head);
	L.tail=NULL;
	L.len=0;
}

void InsFirst(LinkList &L,Link h,Link s)
{
	s->next=h->next;
	h->next=s;
	if(h==L.tail)
		L.tail=h->next;
	L.len++;
}

Status DelFirst(LinkList &L,Link h,Link &q)
{
	q=h->next;
	if(q)
	{
		h->next=q->next;
		if(!h->next)
			L.tail=h;
		L.len--;
		return OK;
	}
	else
		return FALSE;
}

void Append(LinkList &L,Link s)
{
	int i=1;
	L.tail->next=s;
	while(s->next)
	{
		s=s->next;
		i++;
	}
		L.tail=s;
		L.len+=i;
}

Position PriorPos(LinkList L,Link p)
{
	Link q;
	q=L.head->next;
	if(q==p)
		return NULL;
	else
	{
		while(q->next!=p)
			q=q->next;
		return q;
	}
}

Status Remove(LinkList &L,Link &q)
{
	Link p=L.head;
	if(L.len==0)
	{
		q=NULL;
		return FALSE;
	}
	while(p->next=L.tail)
		p=p->next;
	q=L.tail;
	p->next=NULL;
	L.tail=p;
	L.len--;
	return OK;
}

void InsBefore(LinkList &L,Link &p,Link s)
{
	Link q;
	q=PriorPos(L,p);
	if(!q)
		q=L.head;
	s->next=p;
	q->next=s;
	p=s;
	L.len++;
}

void InsAfter(LinkList &L,Link &p,Link s)
{
	if(p==L.tail)
		L.tail=s;
	s->next=p->next;
	p->next=s;
	p=s;
	L.len++;
}

void SetCurElem(Link p,ElemType e)
{
	p->data=e;
}

ElemType GetCurElem(Link p)
{
	return p->data;
}

Status ListEmpty(LinkList L)
{
	if(L.len)
		return FALSE;
	else
		return TRUE;
}

int ListLength(LinkList L)
{
	return L.len;
}

Position GetHead(LinkList L)
{
	return L.head;
}

Position GetLast(LinkList L)
{
	return L.tail;
}

Position NextPos(Link p)
{
	return p->next;
}

Status LocatePos(LinkList L,int i,Link &p)
{
	int j;
	if(i<0||i>L.len)
		return ERROR;
	else
	{
		p=L.head;
		for(j=1;j<=i;j++)
			p=p->next;
		return OK;
	}
}

Position LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
	Link p=L.head;
	do
	p=p->next;
	while(p&&!(compare(p->data,e)));
	return p;
}

void ListTraverse(LinkList L,void(*visit)(ElemType))
{
	Link p=L.head->next;
	int j;
	for(j=1;j<=L.len;j++)
	{
		visit(p->data);
		p=p->next;
	}
	printf("\n");
}

void OrderInsert(LinkList &L,ElemType e,int (*comp)(ElemType,ElemType))
{
	Link o,p,q;
	q=L.head;
	p=q->next;
	while(p!=NULL&&comp(p->data,e)<0)
	{
		q=p;
		p=p->next;}
	o=(Link)malloc(sizeof(LNode));
	o->data=e;
	q->next=o;
	o->next=p;
	L.len++;
	if(!p)
		L.tail=o;
}

Status LocateElem(LinkList L,ElemType e,Position &q,int(*compare)(ElemType,ElemType))
{
	Link p=L.head,pp;
	do
	{
		pp=p;
		p=p->next;
	}while(p&&(compare(p->data,e)<0));
	if(!p||compare(p->data,e)>0)
	{
		q=pp;
		return FALSE;
	}
	else
	{
		q=p;
		return TRUE;
	}
}