目錄

?

一、圖的鄰接矩陣

存儲結(jié)構(gòu)

總代碼

二、網(wǎng)圖的鄰接矩陣

存儲結(jié)構(gòu)

總代碼

?三、圖的鄰接表

存儲結(jié)構(gòu)

1、頂點列表結(jié)構(gòu)體

2、鄰接頂點結(jié)構(gòu)體

?總代碼

四、網(wǎng)圖的鄰接表

?存儲結(jié)構(gòu)

?1、頂點列表結(jié)構(gòu)體

2、鄰接頂點結(jié)構(gòu)體

總代碼?

---

---

一、圖的鄰接矩陣

存儲結(jié)構(gòu)

頂點數(shù)組：存儲頂點數(shù)據(jù)

邊數(shù)組：存儲邊數(shù)據(jù)

typedef struct
{char vertex[MAXSIZE];					//頂點int edge[MAXSIZE][MAXSIZE];		//鄰接頂點int vertexNum;								//頂點數(shù)量
}Graph;
Graph G;

總代碼

//無/有向圖的鄰接矩陣
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>#define MAXSIZE 20typedef struct
{char vertex[MAXSIZE];					//頂點int edge[MAXSIZE][MAXSIZE];		//鄰接頂點int vertexNum;								//頂點數(shù)量
}Graph;
Graph G;//輸入頂點
void InputVertex()
{int i = 0;char ch;printf("請輸入需要創(chuàng)建的圖頂點（不需要空格）：\n");do{scanf("%c", &ch);if (ch != '\n')G.vertex[i++] = ch;} while (ch != '\n');G.vertexNum = i;
}//查找（根據(jù)結(jié)點找索引）
int findIndex(char ch)
{int i;for (i = 0; i < G.vertexNum; i++){if (G.vertex[i] == ch)return i;}return -1;				//沒找到
}//創(chuàng)建圖
void InputEdge()
{int i, index;char ch;for (i = 0; i < G.vertexNum; i++){printf("請輸入%c指向的鄰接結(jié)點：\n", G.vertex[i]);scanf("%c", &ch);while (ch != '\n'){index = findIndex(ch);			//查找輸入結(jié)點的索引G.edge[i][index] = 1;scanf("%c", &ch);}}
}//輸出測試
void Print()
{int i, j;for (i = 0; i < G.vertexNum; i++){printf("\n%c結(jié)點的鄰接結(jié)點為：\t", G.vertex[i]);for (j = 0; j < G.vertexNum; j++){if (G.edge[i][j] != 0)printf("%c\t", G.vertex[j]);}}
}int main()
{//創(chuàng)建圖InputVertex();InputEdge();//輸出測試Print();return 0;
}

二、網(wǎng)圖的鄰接矩陣

存儲結(jié)構(gòu)

頂點數(shù)組：存儲頂點數(shù)據(jù)

邊數(shù)組：存儲邊數(shù)據(jù)

網(wǎng)圖與圖相比多了一個“權(quán)”，可以理解為距離。

邊數(shù)組中對角線為0：因為對角線表示的是指向自身，自身到自身的距離自然是0。

到其他相鄰結(jié)點距離為：權(quán)。

到其他不相鄰結(jié)點距離為：無窮大（可以用計算機允許的盡可能大的數(shù)據(jù)代替無窮大）。

總代碼

//鄰接矩陣（無向網(wǎng)圖）
#include<iostream>
#include<stdio.h>
using namespace std;#define MAXSIZE 20
#define MAX 65535							//無窮大typedef struct Graph
{char vertex[MAXSIZE];					//頂點int arc[MAXSIZE][MAXSIZE];		//邊	（權(quán)存放在其中）int numVertex, numArc;				//頂點數(shù)、邊數(shù)
}Graph;
Graph G;void Input()
{cout << "請輸入需要創(chuàng)建的頂點數(shù)量和邊的數(shù)量：\n";cin >> G.numVertex >> G.numArc;
}//初始化
void Init_Graph()
{int i, j;//給數(shù)組賦0for (i = 0; i < G.numVertex; i++){for (j = 0; j < G.numVertex; j++){G.arc[i][j] = MAX;						//先把所有元素賦為無窮大}G.arc[i][i] = 0;								//對角線元素}
}//創(chuàng)建無向圖
void CreateGraph()
{int i, j, num, index = 0;for (i = 0; i < G.numVertex; i++){printf("請輸入第%d個結(jié)點及相鄰結(jié)點數(shù)量：\n", i + 1);getchar();cin >> G.vertex[i] >> num;if (num > 0)printf("請分別輸入相鄰結(jié)點下標(biāo)和權(quán)（空格分隔）：\n", num);for (j = 0; j < num; j++){getchar();cin >> index;cin >> G.arc[i][index];}}
}//遍歷
void Traverse()
{int i, j;for (i = 0; i < G.numVertex; i++){for (j = 0; j < G.numVertex; j++)printf("%d\t", G.arc[i][j]);cout << endl;}
}int main()
{Input();Init_Graph();CreateGraph();		//創(chuàng)建Traverse();			//遍歷return 0;
}

?三、圖的鄰接表

存儲結(jié)構(gòu)

無向圖鄰接表：

有向圖鄰接表：

1、頂點列表結(jié)構(gòu)體

//頂點列表
typedef struct VertexList
{int index;							//索引char data;							//數(shù)據(jù)EdgeNode* firstedge;		//指向第一個鄰接結(jié)點
}VertexList;
VertexList L[MAXSIZE];

2、鄰接頂點結(jié)構(gòu)體

//鄰接頂點
typedef struct EdgeNode
{int index;							//鄰接結(jié)點索引char data;							//鄰接結(jié)點數(shù)據(jù)struct EdgeNode* next;	//指向下一個鄰接結(jié)點
}EdgeNode;

?總代碼

//圖的鄰接表
#include<stdio.h>
#include<iostream>
#include<malloc.h>
using namespace std;#define MAXSIZE 100
int listLength = 0;//鄰接頂點
typedef struct EdgeNode
{int index;							//鄰接結(jié)點索引char data;							//鄰接結(jié)點數(shù)據(jù)struct EdgeNode* next;	//指向下一個鄰接結(jié)點
}EdgeNode;//頂點列表
typedef struct VertexList
{int index;							//索引char data;							//數(shù)據(jù)EdgeNode* firstedge;		//指向第一個鄰接結(jié)點
}VertexList;
VertexList L[MAXSIZE];//輸入
void Input()
{int i = 0;char ch = ' ';cout << "請輸入需要創(chuàng)建的結(jié)點：\n";scanf_s("%c", &ch, 1);for (i = 0; i < MAXSIZE && ch != '\n'; i++){L[i].data = ch;scanf_s("%c", &ch, 1);}listLength = i;				//獲取列表長度（吸收空格）
}void InitList()
{int i;for (i = 0; i < listLength; i++)L[i].firstedge = NULL;
}//查找
int find(char ch)
{int i;for (i = 0; i < listLength; i++){if (ch == L[i].data)return ch;}return NULL;
}//初始化列表
void Create_List()
{int i;char ch, choice;EdgeNode* N = NULL;for (i = 0; i < listLength; i++){printf("%c是否有鄰接結(jié)點？(Y/N)\n", L[i].data);scanf_s("%c", &choice, 1);getchar();if (choice == 'y' || choice == 'Y'){L[i].firstedge = (EdgeNode*)malloc(sizeof(EdgeNode));N = (EdgeNode*)malloc(sizeof(EdgeNode));N = L[i].firstedge;												//連接printf("請輸入%c的鄰接結(jié)點：\n", L[i].data);while (1){scanf_s("%c", &ch, 1);if (ch == '\n')break;else if (ch == ' ')continue;N->data = ch;						//值N->index = find(ch);			//查找并賦值索引N->next = (EdgeNode*)malloc(sizeof(EdgeNode));		//下一個N = N->next;}N->next = NULL;}}
}void Print()
{int i;EdgeNode* N = NULL;for (i = 0; i < listLength; i++){printf("\n%c的鄰接結(jié)點：", L[i].data);N = L[i].firstedge;while (N){cout << N->data;N = N->next;}cout << endl;}
}int main()
{Input();InitList();Create_List();Print();return 0;
}

四、網(wǎng)圖的鄰接表

?存儲結(jié)構(gòu)

?1、頂點列表結(jié)構(gòu)體

//結(jié)點列表
typedef struct NodeList
{char data;int length;EdgeNode* firstEdge;
}NodeList;
NodeList L[MAXSIZE];

2、鄰接頂點結(jié)構(gòu)體

//鄰接結(jié)點
typedef struct EdgeNode
{int index;char data;int weight;								//權(quán)重struct EdgeNode* next;
}EdgeNode, * pEdgeNode;			//*pEdgeNode后面為創(chuàng)建二級指針

總代碼?

//網(wǎng)圖的鄰接表
//運用了二級指針：要直接修改地址需要用到二級指針
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<malloc.h>
using namespace std;#define MAXSIZE 100
int length = 0;//鄰接結(jié)點
typedef struct EdgeNode
{int index;char data;int weight;								//權(quán)重struct EdgeNode* next;
}EdgeNode, * pEdgeNode;			//*pEdgeNode后面為創(chuàng)建二級指針//結(jié)點列表
typedef struct NodeList
{char data;int length;EdgeNode* firstEdge;
}NodeList;
NodeList L[MAXSIZE];//輸入并初始化
void Input_Init()
{int i = 0;char ch = ' ';printf("請輸入需要創(chuàng)建的結(jié)點：\n");while (ch != '\n')						//（這里其實用do while()會更好）{scanf_s("%c", &ch);L[i].data = ch;L[i].firstEdge = NULL;i++;}length = i - 1;						//包括了換行符printf("請分別輸入這%d個結(jié)點的鄰接結(jié)點的數(shù)量：\n", length);for (i = 0; i < length; i++){scanf("%d", &L[i].length);}
}//獲取索引
int findIndex(char ch)
{int i = 0;for (i = 0; i < length; i++){if (ch == L[i].data)return i;}return -1;
}//創(chuàng)建列表
void CreateList()
{int i, j, weight;char ch = ' ';pEdgeNode* N = NULL;								//----------------------二級指針--------------------//for (i = 0; i < length; i++){if (ch != '\n')					//創(chuàng)建首{L[i].firstEdge = (EdgeNode*)malloc(sizeof(EdgeNode));//-----------------二級指針---------------//N = (pEdgeNode*)malloc(sizeof(pEdgeNode));N = &L[i].firstEdge;}printf("請分別輸入%c結(jié)點的鄰接結(jié)點和權(quán)重：\n", L[i].data);for (j = 0; j < L[i].length; j++){getchar();scanf("%c %d", &ch, &weight);if (ch == ' ')								//空格不計{j--;continue;}//-----------------二級指針操作---------------//(*N)->index = findIndex(ch);		//獲取索引if ((*N)->index != -1)					//有該元素{(*N)->data = ch;							//賦值(*N)->weight = weight;				//權(quán)重(*N)->next = (EdgeNode*)malloc(sizeof(EdgeNode));	//創(chuàng)建next指針N = &((*N)->next);						//后移（指向next指針的地址）（注：next也為二級指針時不行，不知道為什么）}}(*N) = NULL;										//----------地址置空，用到了二級指針----------//}
}//遍歷
void Print()
{int i = 0, j;pEdgeNode* N;for (i = 0; i < length; i++){N = &L[i].firstEdge;printf("\n%c結(jié)點鄰接結(jié)點：\n", L[i].data);while ((*N) != NULL){printf("%c權(quán)重：%d\n", (*N)->data, (*N)->weight);N = &((*N)->next);}}
}int main()
{Input_Init();CreateList();Print();return 0;
}

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法（7-1）图的存储（邻接矩阵、邻接表）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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