C++實(shí)現(xiàn)鄰接表頂點(diǎn)的刪除
本文實(shí)例為大家分享了C++實(shí)現(xiàn)鄰接表頂點(diǎn)的刪除代碼,供大家參考,具體內(nèi)容如下
這里的邊是無向邊
刪除頂點(diǎn)v時(shí),要找到頂點(diǎn)v的鄰接頂點(diǎn)w,把w中指向v的邊刪除掉,再刪除邊(v,w)。循環(huán)這個(gè)過程,直到把和頂點(diǎn)v有關(guān)的邊都刪除掉為止。
再接著需要?jiǎng)h除頂點(diǎn)v。
不可以直接像數(shù)組那樣直接把頂點(diǎn)v之后的頂點(diǎn)位置像前移動(dòng)一位,因?yàn)檫@樣其他頂點(diǎn)的位置將會(huì)發(fā)生變化,頂點(diǎn)邊中的頂點(diǎn)位置將會(huì)出錯(cuò)。
邊和頂點(diǎn)的定義如下:
struct Edge{//邊節(jié)點(diǎn)的定義 int dest;//邊的另一頂點(diǎn)位置 E cost;//邊上的權(quán)值 Edge<T, E> *link;//下一條邊鏈指針 Edge(){}//構(gòu)造函數(shù) Edge(int num, E weight):dest(num),cost(weight),link(NULL){}//構(gòu)造函數(shù) bool operator!=(Edge<T, E>& R)const{ return (dest!=R.dest)?true:false; } }; template <class T, class E> struct Vertex{//頂點(diǎn)的定義 T data;//頂點(diǎn)的名字 Edge<T, E> *adj;//邊鏈表的頭指針 };
刪除函數(shù)如下:
//在圖中刪除一個(gè)指定頂點(diǎn)v,v是頂點(diǎn)號(hào)。 template <class T, class E> bool Graphlink<T,E>::removeVertex(int v){ if(v<0||v>=numVertices||numVertices==1)return false; Edge<T,E> *t, *p, *s; int i, k; while(NodeTable[v].adj!=NULL){ //將頂點(diǎn) 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){//說明第一條邊的另一個(gè)頂點(diǎn)就是v NodeTable[k].adj = s->link; } else{ t->link = s->link; } delete s; } //以上代碼是用來將頂點(diǎn)v的入度刪除 NodeTable[v].adj = p->link; delete p;//刪除頂點(diǎn)v的邊 numEdges--; } //以上代碼將所有涉及到頂點(diǎn)v的邊都刪除了,接下來要調(diào)整表結(jié)構(gòu) numVertices--; NodeTable[v].data = NodeTable[numVertices].data; p = NodeTable[v].adj = NodeTable[numVertices].adj; //把原來頂點(diǎn)numVertices的入度改為頂點(diǎn)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; }
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
C語言順序表的基本結(jié)構(gòu)與實(shí)現(xiàn)思路詳解
順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu),一般情況下采用數(shù)組存儲(chǔ)。本文將通過示例為大家講解一下順序表的基本操作,需要的可以參考一下2023-02-02C語言中0、‘\0‘、‘0‘、NULL以及類型轉(zhuǎn)化
在C語言中, NULL和0的值都是一樣的,但是為了目的和用途及容易識(shí)別的原因,下面這篇文章主要給大家介紹了關(guān)于C語言中0、‘\0‘、‘0‘、NULL以及類型轉(zhuǎn)化的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2021-08-08C++實(shí)現(xiàn)圖形界面時(shí)鐘表盤代碼
這篇文章主要介紹了C++實(shí)現(xiàn)圖形界面時(shí)鐘表盤代碼,涉及坐標(biāo)函數(shù)的應(yīng)用及圖形界面程序設(shè)計(jì),需要的朋友可以參考下2014-10-10OpenCV4 實(shí)現(xiàn)背景分離的詳細(xì)步驟(背景減法模型)
背景分離(BS)是一種通過使用靜態(tài)相機(jī)來生成前景掩碼(即包含屬于場景中的移動(dòng)對象像素的二進(jìn)制圖像)的常用技術(shù),本文給大家介紹OpenCV4 實(shí)現(xiàn)背景分離的詳細(xì)步驟,需要的朋友可以參考下2021-09-09C語言實(shí)現(xiàn)紙牌24點(diǎn)小游戲
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)紙牌24點(diǎn)小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-10-10