C++如何实现邻接表顶点的删除
这篇文章主要讲解了C++如何实现邻接表顶点的删除,内容清晰明了,对此有兴趣的小伙伴可以学习一下,相信大家阅读完之后会有帮助。
创新互联专注为客户提供全方位的互联网综合服务,包含不限于网站制作、成都网站设计、索县网络推广、小程序开发、索县网络营销、索县企业策划、索县品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们最大的嘉奖;创新互联为所有大学生创业者提供索县建站搭建服务,24小时服务热线:18980820575,官方网址:www.cdcxhl.com
这里的边是无向边
删除顶点v时,要找到顶点v的邻接顶点w,把w中指向v的边删除掉,再删除边(v,w)。循环这个过程,直到把和顶点v有关的边都删除掉为止。
再接着需要删除顶点v。
不可以直接像数组那样直接把顶点v之后的顶点位置像前移动一位,因为这样其他顶点的位置将会发生变化,顶点边中的顶点位置将会出错。
边和顶点的定义如下:
struct Edge{//边节点的定义 int dest;//边的另一顶点位置 E cost;//边上的权值 Edge*link;//下一条边链指针 Edge(){}//构造函数 Edge(int num, E weight):dest(num),cost(weight),link(NULL){}//构造函数 bool operator!=(Edge & R)const{ return (dest!=R.dest)?true:false; } }; template struct Vertex{//顶点的定义 T data;//顶点的名字 Edge *adj;//边链表的头指针 };
删除函数如下:
//在图中删除一个指定顶点v,v是顶点号。 templatebool Graphlink ::removeVertex(int v){ if(v<0||v>=numVertices||numVertices==1)return false; Edge *t, *p, *s; int i, k; while(NodeTable[v].adj!=NULL){ //将顶点 p = NodeTable[v].adj; k = p->dest; s = NodeTable[k].adj; t = NULL; while(s!=NULL&&s->dest!=v){ t = s; s = s->link; } if(s!=NULL){ if(t==NULL){//说明第一条边的另一个顶点就是v NodeTable[k].adj = s->link; } else{ t->link = s->link; } delete s; } //以上代码是用来将顶点v的入度删除 NodeTable[v].adj = p->link; delete p;//删除顶点v的边 numEdges--; } //以上代码将所有涉及到顶点v的边都删除了,接下来要调整表结构 numVertices--; NodeTable[v].data = NodeTable[numVertices].data; p = NodeTable[v].adj = NodeTable[numVertices].adj; //把原来顶点numVertices的入度改为顶点v的入度 while(p!=NULL){ s = NodeTable[p->dest].adj; while(s!=NULL){ if(s->dest==numVertices){ s->dest = v; break; } else s = s->link; } p = p->link; } return true; }
看完上述内容,是不是对C++如何实现邻接表顶点的删除有进一步的了解,如果还想学习更多内容,欢迎关注创新互联行业资讯频道。
分享名称:C++如何实现邻接表顶点的删除
网站URL:http://myzitong.com/article/iiopci.html