习题－24.c

来自「数据结构经典算法」· C语言 代码 · 共 33 行

//本程序只给出了算法思想
//读者可以自己完善本程序
Status Delete_XorLinkedList(XorlinkedList &L,int i)//删除异或链表L的第i个元素
{
	p=L.left;pre=NULL;
	if(i==1) //删除最左结点的情况
	{
		q=p->LRPtr;
		q->LRPtr=XorP(q->LRPtr,p);
		L.left=q;free(p);
		return OK;
	}
	j=1;q=p->LRPtr;
	while(++j<i&&q)
	{
		q=XorP(p->LRPtr,pre);
		pre=p;p=q;
	}//while //找到待删结点q
	if(!q) 
		return INFEASIBLE; //i不可以超过表长
	if(L.right==q) //q为最右结点的情况
	{
		p->LRPtr=XorP(p->LRPtr,q);
		L.right=p;free(q);
		return OK;
	}
	r=XorP(q->LRPtr,p); //q为中间结点的情况,此时p,r分别为其左右结点
	p->LRPtr=XorP(XorP(p->LRPtr,q),r);
	r->LRPtr=XorP(XorP(r->LRPtr,q),p); //修改指针
	free(q);
	return OK;
}//Delete_XorLinkedList