《數(shù)據(jù)結(jié)構(gòu)（C語言描述）（第2版）》教學(xué)課件5-05建立圖的鄰接表算法

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：劉斌 建立圖的鄰接表算法常州信息職業(yè)技術(shù)學(xué)院02教學(xué)目標(biāo)12圖的鄰接表存儲(chǔ)結(jié)構(gòu)的描述03建立無向圖的鄰接表算法三、鏈表的插入04建立圖的鄰接表算法0.5圖的鄰接表算法1、圖的鄰接表存儲(chǔ)結(jié)構(gòu)的描述typedef struct node/邊表結(jié)點(diǎn)定義int adjvex; /鄰接點(diǎn)域struct node *next; /指針域/若要表示邊上的權(quán)，則應(yīng)增加一個(gè)數(shù)據(jù)域EdgeNode;typedef struct vnode /頂點(diǎn)表結(jié)點(diǎn)定義VertexType vertex; /頂點(diǎn)域EdgeNode *firstedge;/邊表頭指針Vertex

2、Node;typedef VertexNode AdjListVertexNum;/AdjList是鄰接表類型typedef struct/鄰接表定義AdjList adjlist;/鄰接表int n,e;/圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)ALGraph;頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)指針域頂點(diǎn)域邊表結(jié)點(diǎn)結(jié)構(gòu)指針域鄰接點(diǎn)域05建立圖的鄰接表算法0.52建立無向圖的鄰接表算法void CreateALGraph(ALGraph *G)/建立無向圖的鄰接表int i,j,k;EdgeNode *s;scanf(%d%d,&G-n,&G-e);/讀入頂點(diǎn)數(shù)和邊數(shù)getchar();for(i=0;in;i+) /建立頂點(diǎn)表 G

3、-adjlisti.vertex=getchar();/讀入頂點(diǎn)信息 G-adjlisti.firstedge=NULL;/邊表置為空表 06建立圖的鄰接表算法0.5for(k=0;ke;k+)/建立邊表scanf(%d%d,&i,&j);/讀入邊(vi,vj)頂點(diǎn)對序號s=(EdgeNode *)malloc(sizeof(EdgeNode);/生成邊表結(jié)點(diǎn)if(s=NULL)puts(空間申請失敗);return;s-adjvex=j; /鄰接點(diǎn)序號為js-next=G-adjlisti.firstedge;G-adjlisti.firstedge=s;/將新結(jié)點(diǎn)*s插入頂點(diǎn)vi的邊表頭部s=(EdgeNode *)malloc(sizeof(EdgeNode);if(s=NULL)puts(空間申請失敗);return;s-adjvex=i;/鄰接點(diǎn)序號為is-next=G-adjlistj.firstedge;G-a