问答题
已知某有向图用邻接表表示。该邻接表的结点表及边表说明如下(编者略)。设该有向图中必须删除数据场之值为key的结点，请设计一个程序加以实现。【上海交通大学2003四(20分)】
【正确答案】正确答案：在有向图的邻接表中删除一个顶点，除在顶点向量中删除该顶点并顶点数减1外，要删除该顶点的所有出度边和入度边，并调整相关边结点中邻接点的值。核心语句段如下： for(i=0；i
next；delete(u)；} ／／删除被删顶点的所有出度边 for(j=0； j＜n；j++) ／／查被删顶点的所有入度边 if(j!=i) {p=q=g[j]．firstarc ； ／／设置前驱q if(p一>adjvex==i) ／／第一个邻接点是被删顶点 (u=p； g[j]．firstarc=p一>next； p=p->next； free(u)；} else ／／第一个邻接点不是被删顶点，查找被删结点的入度边 while(p) (if(p一>adjvex==i) {u=p；q->next=p一>next；delete(u)；break；} ／／删除被删顶点的入度边 if(p一>adjvex>i)P一>adjvex一一； ／／i之后的顶点在向量中的下标前移 q一>next=p；q=p；p=p一>next； ／／邻接点链表指针后移继续查找 }while(p) } ／／if(j!=i) for(j=i+1 ； j
【答案解析】