Demo entry 6746751

a

   

Submitted by a on May 31, 2018 at 05:04
Language: C++. Code size: 3.1 kB.

#include "stdafx.h"

#include <iostream>
#include <cstdio>
using namespace std;

#define maxn 100  //最大顶点个数
int n, m;       //顶点数,边数

struct arcnode  //边结点
{
	int vertex;     //与表头结点相邻的顶点编号
	int weight = 0;     //连接两顶点的边的权值
	arcnode * next; //指向下一相邻接点
	arcnode() {}
	arcnode(int v, int w) :vertex(v), weight(w), next(NULL) {}
	arcnode(int v) :vertex(v), next(NULL) {}
};

struct vernode      //顶点结点,为每一条邻接表的表头结点
{
	int vex;    //当前定点编号
	arcnode * firarc;   //与该顶点相连的第一个顶点组成的边
}Ver[maxn];

void Init()  //建立图的邻接表需要先初始化,建立顶点结点
{
	for (int i = 1; i <= n; i++)
	{
		Ver[i].vex = i;
		Ver[i].firarc = NULL;
	}
}

void Insert(int a, int b, int w)  //尾插法,插入以a为起点,b为终点,权为w的边,效率不如头插,但是可以去重边
{
	arcnode * q = new arcnode(b, w);
	if (Ver[a].firarc == NULL)
		Ver[a].firarc = q;
	else
	{
		arcnode * p = Ver[a].firarc;	//顶点的第一个弧
		if (p->vertex == b)  //如果不要去重边,去掉这一段
		{
			if (p->weight < w)
				p->weight = w;
			return;
		}
		while (p->next != NULL)
		{
			if (p->next->vertex == b)    //如果不要去重边,去掉这一段
			{
				if (p->next->weight < w);
				p->next->weight = w;
				return;
			}
			p = p->next;
		}
		p->next = q;
	}
}
void Insert2(int a, int b, int w)   //头插法,效率更高,但不能去重边
{
	arcnode * q = new arcnode(b, w);
	if (Ver[a].firarc == NULL)
		Ver[a].firarc = q;
	else
	{
		arcnode * p = Ver[a].firarc;
		q->next = p;
		Ver[a].firarc = q;
	}
}

void Insert(int a, int b)   //尾插法,插入以a为起点,b为终点,无权的边,效率不如头插,但是可以去重边
{
	arcnode * q = new arcnode(b);
	if (Ver[a].firarc == NULL)
		Ver[a].firarc = q;
	else
	{
		arcnode * p = Ver[a].firarc;
		if (p->vertex == b) return;      //去重边,如果不要去重边,去掉这一句
		while (p->next != NULL)
		{
			if (p->next->vertex == b)    //去重边,如果不要去重边,去掉这一句
				return;
			p = p->next;
		}
		p->next = q;
	}
}
void Insert2(int a, int b)   //头插法,效率跟高,但不能去重边
{
	arcnode * q = new arcnode(b);
	if (Ver[a].firarc == NULL)
		Ver[a].firarc = q;
	else
	{
		arcnode * p = Ver[a].firarc;
		q->next = p;
		Ver[a].firarc = q;
	}
}
void Delete(int a, int b)   //删除以a为起点,b为终点的边
{
	arcnode * p = Ver[a].firarc;
	if (p->vertex == b)
	{
		Ver[a].firarc = p->next;
		delete p;
		return;
	}
	while (p->next != NULL)
		if (p->next->vertex == b)
		{
			p->next = p->next->next;
			delete p->next;
			return;
		}
}

void Show()     //打印图的邻接表(有权值)
{
	for (int i = 1; i <= n; i++)
	{
		cout << Ver[i].vex;
		arcnode * p = Ver[i].firarc;
		while (p != NULL)
		{
			cout << "->(" << p->vertex << "," << p->weight << ")";
			p = p->next;
		}
		cout << "->NULL" << endl;
	}
}

void Show2()     //打印图的邻接表(无权值)
{
	for (int i = 1; i <= n; i++)
	{
		cout << Ver[i].vex;
		arcnode * p = Ver[i].firarc;
		while (p != NULL)
		{
			cout << "->" << p->vertex;
			p = p->next;
		}
		cout << "->NULL" << endl;
	}
}
int main()
{
	int a, b, w;
	cout << "Enter n and m:";
	cin >> n >> m;
	Init();
	while (m--)
	{
		cin >> a >> b >> w;       //输入起点、终点
		Insert(a, b, w);        //插入操作
		Insert(b, a, w);        //如果是无向图还需要反向插入
	}
	Show();
	return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).