icoding复习6 图
icoding復習6?
1. 鄰接表1
試在鄰接表存儲結構上實現圖的基本操作 insert_vertex 和 insert_arc，相關定義如下：
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); //返回頂點 v 在vertex數組中的下標，如果v不存在，返回-1
bool insert_vertex(ListGraph *G, VertexType v);
bool insert_arc(ListGraph *G, VertexType v, VertexType w);
當成功插入頂點或邊時，函數返回true，否則（如頂點或邊已存在、插入邊時頂點v或w不存在）返回false。
//寫下locate函數
int locate_vertex(ListGraph *G, VertexType v){
?? ?int i;
?? ?for(i = 0; i < G->vexnum; i++)
?? ??? ?if(G->vertex[i].data == v)
?? ??? ??? ?return i;
?? ?return -1;
}?
#include
#include
//記得加這個頭文件消除黃色警告?
#include "graph.h" //請勿刪除，否則檢查不通過
bool insert_vertex(ListGraph *G, VertexType v){
?? ?int ?i = 0;
?? ?//2個易錯點: 指針置空,可以省略; 點運算符!!務必區分?
?? ?i = locate_vertex(G, v);
?? ?if(i != -1) return false;
?? ?G->vertex[G->vexnum].data = v;
?? ?G->vertex[G->vexnum].firstarc = NULL;
?? ?G->vexnum++;
?? ?return true;?
}
bool insert_arc(ListGraph *G, VertexType v, VertexType w){
?? ?int i = locate_vertex(G, v);
?? ?int j = locate_vertex(G, w);
?? ?
?? ?//點不存在?
?? ?if(i == -1 || j == -1) return false;
?? ?//邊已經存在
?? ?ArcNode *p = G->vertex[i].firstarc;
?? ?for(; p; p = p->nextarc)
?? ??? ?if(p->adjvex == j)
?? ??? ??? ?return false;?
?? ??? ?
?? ?ArcNode *q;
?? ?p = G->vertex[i].firstarc;
?? ?if(!(q = (ArcNode *)malloc(sizeof(ArcNode)))) return false;?? ?
?? ?q->adjvex = j;
?? ?if(!p){
?? ??? ?G->vertex[i]->firstarc = q;
?? ??? ?q->nextarc = NULL;
?? ?}
?? ?else{
?? ??? ?q->nextarc = p->nextarc;
?? ??? ?p->nextarc = q;?
?? ?}
?? ?G->arcnum++;?
?? ?return true;
}
//第一次的思路
bool insert_arc(ListGraph *G, VertexType v, VertexType w){
?? ?int i, j;
?? ?ArcNode *p;
?? ?
?? ?i = locate_vertex(G, v);
?? ?j = locate_vertex(G, w);
?? ?
?? ?//判結點是否存在,不存在就返回false?
?? ?if(i == -1|| j == -1)
?? ??? ?return false;
?? ??? ?
?? ?//判邊是否存在,存在就返回false?
?? ?//需要注意的是p->adjvex = j這個判斷條件,一個是int類型,一個是不要把這個判斷條件放到for里面?
?? ?for(p = G->vertex[i].firstarc; ?p; p = p->nextarc)
?? ??? ?if(p->adjvex == j) ?? ?return false;
?? ?
?? ?//!!!!!需要注意的是這里是單項插入,不考慮有向無向
?? ?//插入到方向就是v-->w?
//?? ?for(p = G->vertex[j].firstarc; ?p; p = p->nextarc)
//?? ?if(p->adjvex == i) ?return false;
?? ?
//?? ?if(G->type == UDG){
//?? ??? ?p->nextarc = G->vertex[j].firstarc->nextarc;
//?? ??? ?p->adjvex = v;
//?? ??? ?G->vertex[j].firstarc = p;?
//?? ?}
//!!!別忘了分配空間,這個是建立一個新的節點?
?? ?p = (ArcNode *)malloc(sizeof(ArcNode));
?? ?p->adjvex = j;
?? ?G->arcnum++;?
?? ?if(!G->vertex[i].firstarc)//空的情況?
?? ??? ?G->vertex[i].firstarc = p;
?? ?else{//頭插 G->vertex[i].firstarc是頭結點?
?? ??? ?p->nextarc = G->vertex[i].firstarc->nextarc;
?? ??? ?G->vertex[i].firstarc = p;
?? ?}
?? ?return true;?? ?
}?
2. 鄰接表2
試在鄰接表存儲結構上實現圖的基本操作 del_vertex，相關定義如下：
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); //返回頂點 v 在vertex數組中的下標，如果v不存在，返回-1
bool del_vertex(ListGraph *G, VertexType v); //刪除頂點 v
當成功刪除頂點或邊時，函數返回true，否則（如頂點或邊不存在、刪除邊時頂點v或w不存在）返回false。
#include ?
#include
#include "graph.h" //請勿刪除，否則檢查不通過
bool del_vertex(ListGraph* G, VertexType v){
?? ?int i = locate_vertex(G, v), j;
?? ?if(i == -1) return false;
?? ?j = i;
?? ?ArcNode *p, *q;
?? ?
?? ?
?? ?for(p = G->vertex[i].firstarc; p;){
?? ??? ?q = p;
?? ??? ?p = p->nextarc;
?? ??? ?free(q);
?? ??? ?G->arcnum--;
?? ?}?
?? ?free(G->vertex[i].firstarc); G->arcnum--;//在最后丟表頭, 注意點, 這里不能理解為沒有數據的頭結點?
?? ?
?? ?for(; i < G->vexnum; i++)
?? ??? ?G->vertex[i] = G->vertex[i+1];
?? ?G->vexnum--;
?? ?
?? ?for(i = 0; i < G->vexnum; i++){
?? ??? ?for(p = G->vertex[i].firstarc, q = p; p->adjvex != j && p ;q = p, p = p->nextarc)
?? ??? ??? ?;
?? ??? ?if(p->adjvex == j){
?? ??? ??? ?if(p == G->vertex[i].firstarc)
?? ??? ??? ??? ?G->vertex[i].firstarc = p->nextarc;//隱含q == p?
?? ??? ??? ?else
?? ??? ??? ??? ?q->nextarc = p->nextarc;
?? ??? ??? ?free(p);
?? ??? ??? ?G->arcnum--;
?? ??? ?}?
?? ?}
}
//答案如下?
//思路整理
//1. 定位該節點是否存在,若存在
//2. 刪除該結點以之為弧尾的鏈表, 挨著刪,最后刪除表頭, 邊數減少?
//3. 結點序列前移, 結點總數減少?
//4. 遍歷鄰接表找以刪除結點為弧頭的鏈, 刪除...?
bool del_vertex(ListGraph* G, VertexType v)
{
? ? int i, j = locate_vertex(G, v);
? ? if (j == -1) //檢查是否存在該節點
? ? ? ? return false;?
? ??
? ? //先刪除從該節點出發的邊和該節點
? ? while (G->vertex[j].firstarc) {?
? ? ? ? ArcNode* p = G->vertex[j].firstarc;
? ? ? ? if (p->nextarc) { //先free表頭結點后面的
? ? ? ? ? ? ArcNode* q = p->nextarc;
? ? ? ? ? ? p->nextarc = q->nextarc;
? ? ? ? ? ? free(q);
? ? ? ? } else {
? ? ? ? ? ? free(p); //free表頭結點
? ? ? ? ? ? G->vertex[j].firstarc = NULL;
? ? ? ? }
? ? ? ? G->arcnum--; //邊的數量-1
? ? }
? ? G->vexnum--; //結點的數量-1
? ? for (i = j; i < G->vexnum; i++) { //表頭結點中，后面的向前移動
? ? ? ? G->vertex[i] = G->vertex[i + 1];
? ? }
? ??
? ? //再刪除到該節點的邊
? ? for (i = 0; i < G->vexnum; i++) {
? ? ? ? ArcNode *p = G->vertex[i].firstarc, *pNode = NULL;
? ? ? ? ArcNode* q; //存儲要被刪掉的結點
? ? ? ? while (p) {
? ? ? ? ? ? if (p->adjvex == j) { //P的下個結點是V
? ? ? ? ? ? ? ? if (!pNode) { //P是表頭結點
? ? ? ? ? ? ? ? ? ? q = G->vertex[i].firstarc;
? ? ? ? ? ? ? ? ? ? G->vertex[i].firstarc = p->nextarc;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else {
? ? ? ? ? ? ? ? ? ? pNode->nextarc = p->nextarc;
? ? ? ? ? ? ? ? ? ? q = p;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? p = p->nextarc;
? ? ? ? ? ? ? ? free(q);
? ? ? ? ? ? ? ? G->arcnum--;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? pNode = p;
? ? ? ? ? ? ? ? p = p->nextarc;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return true;
}
3. 鄰接矩陣
試在鄰接矩陣存儲結構上實現圖的基本操作 matrix_insert_vertex 和matrix_insert_arc，相關定義如下：
typedef int VertexType;
typedef enum{
? ? DG, UDG
}GraphType;
typedef struct{
? ? VertexType vertex[MAX_VERTEX_NUM]; //頂點向量
? ? int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //鄰接矩陣
? ? int vexnum, arcnum; ? //圖的當前頂點數和弧數
? ? GraphType type; ? ? //圖的種類標志
}MatrixGraph;
int matrix_locate_vertex(MatrixGraph *MG, VertexType vex); //返回頂點 v 在vertex數組中的下標，
//如果v不存在，返回-1
bool matrix_insert_vertex(MatrixGraph *G, VertexType v);
bool matrix_insert_arc(MatrixGraph *G, VertexType v, VertexType w);
當成功插入頂點或邊時，函數返回true，否則（如頂點或邊已存在、插入邊時頂點v或w不存在）返回false。
#include ?
#include "graph.h" // 請不要刪除，否則檢查不通過
bool matrix_insert_vertex(MatrixGraph *G, VertexType v){
?? ?int i = matrix_locate_vertex(G, v);
?? ?
?? ?if(i != -1 || G->vexnum == MAX_VERTEX_NUM - 1) return false;
?? ?
?? ?G->vertex[G->vexnum] = v;
?? ?for(i = 0; i < G->vexnum; i++){
?? ??? ?G->arcs[G->vexnum][i] = 0;
?? ??? ?G->arcs[i][G->vexnum] = 0;
?? ?}
?? ?G->arcnum++;
?? ?return true;
}
bool matrix_insert_arc(MatrixGraph *G, VertexType v, VertexType w){
?? ?int i = matrix_locate_vertex(G, v);
?? ?int j = matrix_locate_vertex(G, w);
?? ?
?? ?if(i == -1 || j == -1 || G->arcs[i][j] == 1) return false;
//如果加上判斷圖的類型?
//?? ?if(G->type == UDG &&( G->arcs[i][j] == 1 || G->arcs[j][i] == 1))
//?? ??? ?return false;
//?? ?else if(G->arcs[i][j] == 1)?? ?
//?? ??? ?return false;
?? ?G->arcs[i][j] = 1;
?? ?if(G->type == UDG)
?? ??? ?G->arcs[j][i] = 1;
?? ?G->arcnum++;
?? ?return true;
}
?
總結
以上是生活随笔為你收集整理的icoding复习6 图的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： icoding复习1,2
- 下一篇： icoding复习3