鄰接表2

試在鄰接表存儲結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作 del_vertex，相關(guān)定義如下：

typedef int VertexType;typedef enum{DG, UDG }GraphType;typedef struct ArcNode{int adjvex;InfoPtr *info;struct ArcNode *nextarc; }ArcNode;typedef struct VNode{VertexType data;ArcNode *firstarc; }VNode; typedef struct{VNode vertex[MAX_VERTEX_NUM];int vexnum, arcnum;GraphType type; }ListGraph;int locate_vertex(ListGraph *G, VertexType v); //返回頂點(diǎn) v 在vertex數(shù)組中的下標(biāo)，如果v不存在，返回-1 bool del_vertex(ListGraph *G, VertexType v); //刪除頂點(diǎn) v

Attention: 判斷條件如下:

當(dāng)成功刪除頂點(diǎn)或邊時，函數(shù)返回true，否則（如頂點(diǎn)或邊不存在、刪除邊時頂點(diǎn)v或w不存在）返回false。

參考代碼如下:

//注意的一點(diǎn)是free函數(shù)包含在頭文件<stdlib.h>中

#include <stdio.h> #include <stdlib.h> #include "graph.h" //請勿刪除，否則檢查不通過 bool del_vertex(ListGraph* G, VertexType v) {int i, j;ArcNode* p, *q;j = locate_vertex(G, v);if (j == -1) return false; q = G->vertex[j].firstarc;if(q){//q存在出度 for(p = q->nextarc; p != NULL; p = q->nextarc){q->nextarc = p->nextarc;free(p);G->arcnum--;}//刪除結(jié)點(diǎn)直接鏈接出去的邊結(jié)點(diǎn), 表頭結(jié)點(diǎn)最后循環(huán)完單獨(dú)刪除free(q);//刪除表頭結(jié)點(diǎn) G->vertex[j].firstarc = NULL;G->arcnum--;}G->vexnum--;//再刪除到該節(jié)點(diǎn)的邊f(xié)or (i = 0; i < G->vexnum; i++) {p = G->vertex[i].firstarc;pNode = NULL;while (p) {if (p->adjvex == j) { //P的下個結(jié)點(diǎn)是Vif (!pNode) { //P是表頭結(jié)點(diǎn)q = G->vertex[i].firstarc;//方便最后統(tǒng)一free G->vertex[i].firstarc = p->nextarc;}else {pNode->nextarc = p->nextarc;q = p;}free(q);G->arcnum--;break;//這個鏈表后面不可能還有邊 (對于頂點(diǎn)v的入度)} else {pNode = p;p = p->nextarc;}}}return true; }

//另外, 對于后半部分的free掉對于頂點(diǎn)v的入度, 我感覺icoding有問題, 另解如下, 歡迎大佬指正!!

#include <stdio.h> #include <stdlib.h> #include "graph.h" //請勿刪除，否則檢查不通過 bool del_vertex(ListGraph* G, VertexType v) {int i, j;ArcNode* p, *q;j = locate_vertex(G, v);if (j == -1) return false; q = G->vertex[j].firstarc;if(q){//q存在出度 for(p = q->nextarc; p != NULL; p = q->nextarc){q->nextarc = p->nextarc;free(p);G->arcnum--;}//刪除結(jié)點(diǎn)直接鏈接出去的邊結(jié)點(diǎn), 表頭結(jié)點(diǎn)最后循環(huán)完單獨(dú)刪除free(q);//刪除表頭結(jié)點(diǎn) G->vertex[j].firstarc = NULL;G->arcnum--;}G->vexnum--;for (i = j; i < G->vexnum; i++) { //表頭結(jié)點(diǎn)中，后面的向前移動G->vertex[i] = G->vertex[i + 1];}for(i = 0; i < G->vexnum; i++){q = G->vertex[i].firstarc;if(q){if(q->adjvex == v){//q為表頭 G->vertex[i].firstarc = q->nextarc;free(q);G->arcnum--;continue;}for(p = q->nextarc; p!=NULL;q = p, p = p->nextarc){if(p->adjvex == v){q->nextarc = p->nextarc;free(p);G->arcnum--;break;}}}}return true; }

歡迎討論區(qū)交流哦!

總結(jié)

以上是生活随笔為你收集整理的邻接表2 -试在邻接表存储结构上实现图的基本操作 del_vertex-数据结构-图-icoding的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。