欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

链表输入与输出

程序员文章站 2022-04-11 13:18:18
...
/********
6 11
1 4 4 
1 2 3
2 5 4
2 4 2
2 3 3
2 1 5
4 5 4
4 1 2
5 6 5
5 2 6
6 3 4
********/ 
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
const int MaxNum = 1005; 
//边集 
struct edge{
    int from,to,w; //起点,终点 ,权重 
};
//邻接点
struct node{
    int idx;//邻接点下标
    int w;//边权重
    node* next;//下一个邻接点的指针 
}; 
//邻接表
struct vnode{
    node *first; //边表的头指针,每个点的第一条边的指针
    int data; //点编号 
}; 
struct graph{
    int nVertex; //顶点数 
    int mEdge; //边数
    vnode adjlist[MaxNum]; //邻接表 
}; 
//根据点的数量n初始化图
graph* initGraph(int n,int m);
//加边 
void insertEdge(graph* g,edge e);
//建图
graph* buildGraph();
//打印图
void printGraph(graph*);
//打印邻接点 
void printlist(node* head);
int main(){
    graph *g = buildGraph();
    printGraph(g);
    return 0;
}
//根据点的数量n初始化图
graph* initGraph(int n,int m){
    graph *g = new graph();//(graph*)malloc(sizeof(graph))
    g->nVertex = n;
    g->mEdge = m;
    for(int i = 1;i<=n;i++){
        g->adjlist[i].data = i;//点的数据默认编号
        g->adjlist[i].first = NULL; //默认没有边 
    }
    return g;
}
//建图
graph* buildGraph(){
    int n,m;
    scanf("%d%d",&n,&m);    //读入点数和边数 
    graph *g = initGraph(n,m);//初始化图 
    //加边
     while(m--){
         edge te;    //定义一条边 
         scanf("%d%d%d",&te.from,&te.to,&te.w); 
         insertEdge(g,te);
    }
    return g;
}
//加边 
void insertEdge(graph* g,edge e){
    //插入边<e.from,e.to>
    node *p = new node();//创建一个新否邻接点 
    p->idx = e.to;        //终点 
    p->w = e.w;            //权重 
    p->next = g->adjlist[e.from].first;
    g->adjlist[e.from].first = p;
    //无向图,还需要在增加一个邻接表 
} 

void printGraph(graph* g){
    for(int i = 1;i <= g->nVertex;i++){
        printf("%d ",i);                    //打印定点数据 
        printlist(g->adjlist[i].first);//打印每个顶点的邻接表 
    } 
}
//打印邻接点 
void printlist(node* head){
    if(head == NULL){
        printf("\n");
        return;
    }    
    node *p = head;
    while(p != NULL){
        printf("-> %d ",p->idx);
        p = p->next;
    } 
    printf("\n"); 
}


 

链表输入与输出