[置頂] 看數據結構寫代碼（37） 圖的十字鏈表的表示與實現
來源：程序員人生 發布時間：2015-04-21 09:16:53 閱讀次數：3281次
圖的鄰接表在 查找 有向圖的 出度 很 方便，但是 在 查找 入度 時，需要遍歷全部圖。如果想要 方便的 查找 入度，需要 建立 逆鄰接表。10字鏈表 正好 就是 鄰接表 和 逆鄰接表的結合。具體結構圖以下：
感覺 10字鏈表 在 查找 入度時 方便 1些，其他 跟 鄰接表沒甚么區分。
源代碼 網盤地址：點擊打開鏈接
代碼以下：
// CrossLinkGraph.cpp : 定義控制臺利用程序的入口點。
//有向圖的10字鏈表表示法
#include "stdafx.h"
#include <cstdlib>
#define MAX_VEX_NUM 20
enum E_State
{
E_State_Error = 0,
E_State_Ok = 1,
};
struct ArcNode//弧節點
{
int tailIndex;//弧尾位置
int headIndex;//弧頭位置
ArcNode * tailNext;//下1個弧尾相同的弧
ArcNode * headNext;//下1個弧頭相同的弧
};
typedef struct VNode
{
char vexName;//頂點名稱
ArcNode * firstIn;
ArcNode * firstOut;
}GraphList[MAX_VEX_NUM];//
struct Graph
{
GraphList list;//頂點數組.
int vexNum,arcNum;
};
//獲得弧 的 頭節點
ArcNode * getHeadNode(){
ArcNode * pNode = (ArcNode *)malloc(sizeof(ArcNode));
if (pNode){
pNode->headIndex = pNode->tailIndex = ⑴;
pNode->headNext = pNode->tailNext = NULL;
}
return pNode;
}
ArcNode * getArcNode(int tailIndex,int headIndex){
ArcNode * pNode = getHeadNode();
if (pNode){
pNode->headIndex = headIndex;
pNode->tailIndex = tailIndex;
}
return pNode;
}
int vexLocation(Graph g,char vex){
for (int i = 0; i < g.vexNum; i++){
if (g.list[i].vexName == vex){
return i;
}
}
return ⑴;
}
void createGrahp(Graph * g){
printf("輸入圖的頂點數 和 邊（弧）數
");
scanf("%d%d%*c",&g->vexNum,&g->arcNum);
//構造頂點集
printf("請輸入頂點集
");
for (int i = 0; i < g->vexNum; i++){
char name;
scanf("%c",&name);
g->list[i].vexName = name;
g->list[i].firstIn = g->list[i].firstOut = getHeadNode();//建立 頭節點，并讓頭指針指向頭節點
}
//構造頂點關系
fflush(stdin);
printf("請輸入頂點的關系
");
for (int i = 0; i < g->arcNum; i++){
char vex1,vex2;
scanf("%c%c%*c",&vex1,&vex2);
int location1 = vexLocation(*g,vex1);
int location2 = vexLocation(*g,vex2);
ArcNode * pNode = getArcNode(location1,location2);
pNode->tailNext = g->list[location1].firstOut->tailNext;
g->list[location1].firstOut->tailNext = pNode;
pNode->headNext = g->list[location2].firstIn->headNext;
g->list[location2].firstIn->headNext = pNode;
}
}
//只要刪除所有頂點的弧尾（或弧頭）節點便可，
//同時刪除弧頭弧尾 ，內存毛病
void destoryGraph(Graph * g){
for (int i = 0; i < g->vexNum; i++){
ArcNode * next = g->list[i].firstOut;//刪除所有弧尾
while (next != NULL){
ArcNode * freeNode = next;
next = next->tailNext;
free(freeNode);
}
g->list[i].firstIn = g->list[i].firstOut = NULL;
g->list[i].vexName = ' ';
g->vexNum = g->arcNum = 0;
}
}
//頂點vex1 和頂點vex2 是不是相鄰
bool graphIsAdj(Graph g,char vex1,char vex2){
int location = vexLocation(g,vex1);
ArcNode * next = g.list[location].firstOut->tailNext;
while (next != NULL){
if (g.list[next->headIndex].vexName == vex2){
return true;
}
next = next->tailNext;
}
return false;
}
int graphDegree(Graph g,char vex){
int degree = 0;
int locaiton = vexLocation(g,vex);
ArcNode * next = g.list[locaiton].firstOut->tailNext;//計算所有出度
while (next != NULL){
degree++;
next = next->tailNext;
}
next = g.list[locaiton].firstIn->headNext;//計算所有入度
while (next != NULL){
degree++;
next = next->headNext;
}
return degree;
}
char firstAdj(Graph g,char vex){
int location = vexLocation(g,vex);
ArcNode * next = g.list[location].firstOut->tailNext;
if (next != NULL)
{
return g.list[next->headIndex].vexName;
}
return ' ';
}
char nextAdj(Graph g,char vex1,char vex2){
int location = vexLocation(g,vex1);
ArcNode * next = g.list[location].firstOut->tailNext;
while (next != NULL){//查找到 vex2
if (g.list[next->headIndex].vexName == vex2){
break;
}
next = next->tailNext;
}
if (next != NULL){
ArcNode * nextNode = next->tailNext;
if (nextNode != NULL){
return g.list[nextNode->headIndex].vexName;
}
}
return ' ';
}
//插入邊（弧）
void insertArc(Graph * g,char vex1,char vex2){
int location1 = vexLocation(*g,vex1);
int location2 = vexLocation(*g,vex2);
ArcNode * node = getArcNode(location1,location2);
node->tailNext = g->list[location1].firstOut->tailNext;
g->list[location1].firstOut->tailNext = node;
node->headNext = g->list[location2].firstIn->headNext;
g->list[location2].firstIn->headNext = node;
g->arcNum ++;
}
//刪除邊（弧）
void deleteArc(Graph * g,char vex1,char vex2){
g->arcNum--;
int location1 = vexLocation(*g,vex1);
int location2 = vexLocation(*g,vex2);
ArcNode * next = g->list[location1].firstOut->tailNext;
ArcNode * pre = g->list[location1].firstOut;
while (next != NULL){//在更改 尾部相同的 鏈表時，不能刪除 弧
if (next->headIndex == location2){
pre->tailNext = next->tailNext;
//free(next);
break;
}
pre = next;
next = next->tailNext;
}
next = g->list[location2].firstIn->headNext;
pre = g->list[location2].firstIn;
//在更改弧頭相同的鏈表時，釋放空間.
while (next != NULL){
if (next->tailIndex == location1){
pre->headNext = next->headNext;
free(next);
break;
}
pre = next;
next = next->headNext;
}
}
//插入頂點
void insertVex(Graph * g, char vex){
if (g->vexNum < MAX_VEX_NUM){
g->list[g->vexNum].vexName = vex;
g->list[g->vexNum].firstIn = g->list[g->vexNum].firstOut = getHeadNode();
g->vexNum++;
}
}
//刪除頂點
void deleteVex(Graph * g,char vex){
int location = vexLocation(*g,vex);
//刪除頂點 一樣需要 遍歷全部 圖 查找 與 vex 相干的弧節點
for (int i = 0; i < g->vexNum; i++){
ArcNode * next = g->list[i].firstOut->tailNext;
while (next != NULL){
if (next->headIndex == location || next->tailIndex == location){
ArcNode * delNode = next;
next = next->tailNext;
char delData1 = g->list[delNode->tailIndex].vexName;
char delData2 = g->list[delNode->headIndex].vexName;
deleteArc(g,delData1,delData2);
}
else{
next = next->tailNext;
}
}
}
for (int i = 0; i < g->vexNum; i++){
ArcNode * next = g->list[i].firstOut->tailNext;
while (next != NULL){
if(next->headIndex > location){
next->headIndex --;
}
if(next->tailIndex > location){
next->tailIndex --;
}
next = next->tailNext;
}
}
free(g->list[location].firstIn);//釋放頭節點
//vex下面的 頂點上移
for (int i = location + 1; i < g->vexNum; i++){
g->list[i⑴] = g->list[i];
}
g->vexNum --;
}
void printGrahp(Graph g){
for (int i = 0; i < g.vexNum; i++){
printf("以%c為弧尾的 頂點有：",g.list[i].vexName);
ArcNode * next = g.list[i].firstOut->tailNext;//刪除所有弧尾
while (next != NULL){
printf("%c",g.list[next->headIndex].vexName);
next = next->tailNext;
}
printf("
以%c為弧頭的 頂點有：",g.list[i].vexName);
next = g.list[i].firstIn->headNext;//刪除所有弧尾
while (next != NULL){
printf("%c",g.list[next->tailIndex].vexName);
next = next->headNext;
}
printf("
");
}
}
int _tmain(int argc, _TCHAR* argv[])
{
Graph g;
createGrahp(&g);
printGrahp(g);
printf("圖的頂點數：%d,邊（弧）樹為：%d
",g.vexNum,g.arcNum);
char * isAdj = graphIsAdj(g,'b','d')? "相鄰" : "不相鄰";
int degree = graphDegree(g,'d');
char first = firstAdj(g,'c');
char next = nextAdj(g,'d','c');
printf("c的第1個鄰接點是%c,d的c鄰接點的下1個鄰接點是：%c
",first,next);
printf("b 和 d %s,d的度為：%d
",isAdj,degree);
insertVex(&g,'e');
printf("插入e頂點以后圖結構以下：
");
printGrahp(g);
insertArc(&g,'a','e');
printf("插入(a,e) 以后圖結構以下：
");
printGrahp(g);
deleteArc(&g,'d','c');
printf("刪除(d,c)以后圖結構以下：
");
printGrahp(g);
deleteVex(&g,'a');
printf("刪除頂點a以后圖結構以下：
");
printGrahp(g);
printf("圖的頂點數：%d,邊（弧）數為：%d
",g.vexNum,g.arcNum);
destoryGraph(&g);
return 0;
}
運行截圖：
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
