歡迎您光臨本站 註冊首頁

C++實現鄰接表頂點的刪除

←手機掃碼閱讀     火星人 @ 2020-04-26 , reply:0

本文實例為大家分享了C++實現鄰接表頂點的刪除代碼,供大家參考,具體內容如下

這裡的邊是無向邊

刪除頂點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; } }; templatestruct 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++實現鄰接表頂點的刪除已經有131次圍觀

http://coctec.com/docs/c/language/show-post-231724.html