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

[c++]代码库
temp1.cpp
 
#include<iostream>
#include"temp1.h"
#include<fstream>
    using namespace std;
 
Status CreateAlGraph(AlGraph &G){
    ifstream in;
    in.open("data3.txt", ios::in);
    cout<<"下列数据从文件data3.txt读入"<<endl<<endl;
    cout<<"请输入图的顶点数,边/弧的数目，图的类型"<<endl;
    int kind;
    in>>G.vexnum>>G.arcnum>>kind;//从文件读入数据，遇到任何结束标记（如空格和换行）则停止。
    switch(kind){
    case 0 :
        G.kind = NG;
        break;
    case 1:
        G.kind = DG;
        break;
    case 2:
        G.kind = NW;
        break;
    case 3:
        G.kind = DW;
        break;
    }
    cout<<"请依次输入顶点的值"<<endl;
    for(int i = 0; i < G.vexnum; i++){
        in>>G.vertices[i].data;
        G.vertices[i].firstarc = NULL;
    }
    cout<<"请依次输入一条边的起点和终点："<<endl;
    for(int k = 0; k < G.arcnum; k++){
        int i, j;
        in>>i>>j;
        ArcNode *p = new ArcNode;
        p->adjvex = j;
        //头插入
        p->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p;
        if(G.kind == NG){
            ArcNode *p = new ArcNode;
            p->adjvex = i;
            //头插入
            p->nextarc = G.vertices[j].firstarc;
            G.vertices[j].firstarc = p;
        }
    }
    in.close();
    return OK;
}
 
int Degree(AlGraph G, VertexType v){
    int i;
    for(i = 0; i < G.vexnum; i++){
        if(G.vertices[i].data == v){
            break;
        }
    }
    if(i >= G.vexnum){
        return -1;
    }
    ArcNode *p = G.vertices[i].firstarc;
    int num = 0;
    while(p){
        num++;
        p = p->nextarc;
    }
    if(G.kind == DG){
        for(int k = 0; k < G.vexnum; k++){
            if(k == i){
                continue;
            }
            p = G.vertices[k].firstarc;
            while(p){
                if(p->adjvex == i){
                    num++;
                }
                p = p->nextarc;
            }
        }
    }
    return num;
}
 
Status InsertVex(AlGraph &G, VertexType v){
    //先判断v是否存在
    for(int i = 0; i < G.vexnum; i++){
        if(G.vertices[i].data == v){
            return ERROR;
        }
    }
    G.vertices[G.vexnum].data = v;
    G.vertices[G.vexnum].firstarc = NULL;
    G.vexnum++;
    return OK;
}
 
int main(){
    //依次测试函数CreateMGraph Degree IsAdj InsertVertex 
    //InsertAdj DeleteAdj
    AlGraph G;
    CreateAlGraph(G);
    int n;
    n = Degree(G, 2);
    cout<<"顶点2的度为："<<n<<endl;
    InsertVex(G, 5);
    system("pause");
    return 0;
}
 
 
 
 
 
temp1.h
 
#define VertexType int//顶点的类型
#define MAX_VERTEX_NUM 20 //最大顶点数
#define Status int
#define OK 1
#define ERROR 0
#define NULL 0
 
    typedef enum{NG, DG, NW, DW}GraphType;//图的类型
 
typedef struct ArcNode{  //边结点
    int adjvex; //邻接点的下标
    struct ArcNode  *nextarc; //后继链指针
}ArcNode;
 
typedef struct VNode{    //顶点结点
    VertexType data;     //顶点数据 
    ArcNode *firstarc;  //边链头指针
}VNode, AdjList[MAX_VERTEX_NUM];
 
typedef struct{
    AdjList vertices;    //邻接表
    int vexnum,arcnum;  //顶点数和边数
    GraphType kind;  //图种类标志
}AlGraph;
 
 
 
 
 
data3.txt
 
    5
    5
    0
    0
    1
    2
    3
    4
    1
    1
    1
    2
    2
    4
    3
    3
    3
    4
用户注册

用户登录

发表随想

该用户最新代码

编程随想

[c++]代码库

网友评论 (发表评论)

发表评论：

评论须知：

扫码下载

输入口令后可复制整站源码
