习题－30.c

来自「这个是数据结构经典实现算法」· C语言 代码 · 共 57 行

//本程序只给出了算法思想
//读者可以自己完善本程序
Status Delete_Vex(OLGraph &G,char v)//在十字链表表示的图G上删除顶点v
{
	if((m=LocateVex(G,v))<0) 
		return ERROR;
	n=G.vexnum;
	for(i=0;i<n;i++) //删除所有以v为头的边
	{
		if(G.xlist[i].firstin->tailvex==m) //如果待删除的边是头链上的第一个结点
		{
			q=G.xlist[i].firstin;
			G.xlist[i].firstin=q->hlink;
			free(q);G.arcnum--;
		}
		else //否则
		{
			for(p=G.xlist[i].firstin;p&&p->hlink->tailvex!=m;p=p->hlink);
			if(p)
			{
				q=p->hlink;
				p->hlink=q->hlink;
				free(q);G.arcnum--;
			}
		}//else
	}//for
	for(i=0;i<n;i++) //删除所有以v为尾的边
	{
		if(G.xlist[i].firstout->headvex==m) //如果待删除的边是尾链上的第一个结点
		{
			q=G.xlist[i].firstout;
			G.xlist[i].firstout=q->tlink;
			free(q);G.arcnum--;
		}
		else //否则
		{
			for(p=G.xlist[i].firstout;p&&p->tlink->headvex!=m;p=p->tlink);
			if(p)
			{
				q=p->tlink;
				p->tlink=q->tlink;
				free(q);G.arcnum--;
			}
		}//else
	}//for
	for(i=m;i<n;i++) //顺次用结点m之后的顶点取代前一个顶点
	{
		G.xlist[i]=G.xlist[i+1]; //修改表头向量
		for(p=G.xlist[i].firstin;p;p=p->hlink)
			p->headvex--;
		for(p=G.xlist[i].firstout;p;p=p->tlink)
			p->tailvex--; //修改各链中的顶点序号
	}
	G.vexnum--;
	return OK;
}//Delete_Vex