Code666 (代码贴、代码片段)

[C++] 图的基本操作——邻接链表表示（网（边带权值的图）的编程没有给出，与一般的图类似） →→→→→进入此内容的聊天室

来自 , 2020-07-20, 写在 C++, 查看 115 次.
URL http://www.code666.cn/view/d523773c
  1. temp1.cpp
  2.  
  3. #include<iostream>
  4. #include"temp1.h"
  5. #include<fstream>
  6.         using namespace std;
  7.  
  8. Status CreateAlGraph(AlGraph &G){
  9.         ifstream in;
  10.         in.open("data3.txt", ios::in);
  11.         cout<<"下列数据从文件data3.txt读入"<<endl<<endl;
  12.         cout<<"请输入图的顶点数,边/弧的数目，图的类型"<<endl;
  13.         int kind;
  14.         in>>G.vexnum>>G.arcnum>>kind;//从文件读入数据，遇到任何结束标记（如空格和换行）则停止。
  15.         switch(kind){
  16.         case 0 :
  17.                 G.kind = NG;
  18.                 break;
  19.         case 1:
  20.                 G.kind = DG;
  21.                 break;
  22.         case 2:
  23.                 G.kind = NW;
  24.                 break;
  25.         case 3:
  26.                 G.kind = DW;
  27.                 break;
  28.         }
  29.         cout<<"请依次输入顶点的值"<<endl;
  30.         for(int i = 0; i < G.vexnum; i++){
  31.                 in>>G.vertices[i].data;
  32.                 G.vertices[i].firstarc = NULL;
  33.         }
  34.         cout<<"请依次输入一条边的起点和终点："<<endl;
  35.         for(int k = 0; k < G.arcnum; k++){
  36.                 int i, j;
  37.                 in>>i>>j;
  38.                 ArcNode *p = new ArcNode;
  39.                 p->adjvex = j;
  40.                 //头插入
  41.                 p->nextarc = G.vertices[i].firstarc;
  42.                 G.vertices[i].firstarc = p;
  43.                 if(G.kind == NG){
  44.                         ArcNode *p = new ArcNode;
  45.                         p->adjvex = i;
  46.                         //头插入
  47.                         p->nextarc = G.vertices[j].firstarc;
  48.                         G.vertices[j].firstarc = p;
  49.                 }
  50.         }
  51.         in.close();
  52.         return OK;
  53. }
  54.  
  55. int Degree(AlGraph G, VertexType v){
  56.         int i;
  57.         for(i = 0; i < G.vexnum; i++){
  58.                 if(G.vertices[i].data == v){
  59.                         break;
  60.                 }
  61.         }
  62.         if(i >= G.vexnum){
  63.                 return -1;
  64.         }
  65.         ArcNode *p = G.vertices[i].firstarc;
  66.         int num = 0;
  67.         while(p){
  68.                 num++;
  69.                 p = p->nextarc;
  70.         }
  71.         if(G.kind == DG){
  72.                 for(int k = 0; k < G.vexnum; k++){
  73.                         if(k == i){
  74.                                 continue;
  75.                         }
  76.                         p = G.vertices[k].firstarc;
  77.                         while(p){
  78.                                 if(p->adjvex == i){
  79.                                         num++;
  80.                                 }
  81.                                 p = p->nextarc;
  82.                         }
  83.                 }
  84.         }
  85.         return num;
  86. }
  87.  
  88. Status InsertVex(AlGraph &G, VertexType v){
  89.         //先判断v是否存在
  90.         for(int i = 0; i < G.vexnum; i++){
  91.                 if(G.vertices[i].data == v){
  92.                         return ERROR;
  93.                 }
  94.         }
  95.         G.vertices[G.vexnum].data = v;
  96.         G.vertices[G.vexnum].firstarc = NULL;
  97.         G.vexnum++;
  98.         return OK;
  99. }
  100.  
  101. int main(){
  102.         //依次测试函数CreateMGraph Degree IsAdj InsertVertex
  103.         //InsertAdj DeleteAdj
  104.         AlGraph G;
  105.         CreateAlGraph(G);
  106.         int n;
  107.         n = Degree(G, 2);
  108.         cout<<"顶点2的度为："<<n<<endl;
  109.         InsertVex(G, 5);
  110.         system("pause");
  111.         return 0;
  112. }
  113.  
  114.  
  115.  
  116.  
  117.  
  118. temp1.h
  119.  
  120. #define VertexType int//顶点的类型
  121. #define MAX_VERTEX_NUM 20 //最大顶点数
  122. #define Status int
  123. #define OK 1
  124. #define ERROR 0
  125. #define NULL 0
  126.  
  127.         typedef enum{NG, DG, NW, DW}GraphType;//图的类型
  128.  
  129. typedef struct ArcNode{  //边结点
  130.         int adjvex;     //邻接点的下标
  131.         struct ArcNode  *nextarc; //后继链指针
  132. }ArcNode;
  133.  
  134. typedef struct VNode{    //顶点结点
  135.         VertexType data;         //顶点数据
  136.         ArcNode *firstarc;      //边链头指针
  137. }VNode, AdjList[MAX_VERTEX_NUM];
  138.  
  139. typedef struct{
  140.         AdjList vertices;        //邻接表
  141.         int vexnum,arcnum;      //顶点数和边数
  142.         GraphType kind;  //图种类标志
  143. }AlGraph;
  144.  
  145.  
  146.  
  147.  
  148.  
  149. data3.txt
  150.  
  151.         5
  152.         5
  153.         0
  154.         0
  155.         1
  156.         2
  157.         3
  158.         4
  159.         1
  160.         1
  161.         1
  162.         2
  163.         2
  164.         4
  165.         3
  166.         3
  167.         3
  168.         4

回复 "图的基本操作——邻接链表表示（网（边带权值的图）的编程没有给出，与一般的图类似）"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666