数据结构(图)HD201801

把一件事做好,做简单,就是对自己最好的一份靠赏.
今天把建图的代码自己模拟了一下,是使用领接表写的,产出量太低,明天来写图的两个遍历算法吧.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define MAXVERTEXNUM 6 //图的顶点数
#define MAXARCNUM 7 //图的弧数
void createGraph();	//建立图
void deleteGraph();	//删除图,释放内存
void DFS();			   //深度优先
void BFS();			   //广度优先
void PrintGraph();	 //打印图

//边表
typedef struct ArcNode
{
	int adjvex;			  //该弧所指向的顶点的位置
	struct ArcNode *next; //指向下一条弧的指针
	ArcNode(int a)
	{
		this->adjvex = a;
	}
} ArcNode;

//顶点表
typedef struct VNode
{
	int data;
	// int num;
	ArcNode *first;
} VNode;

//领接表
typedef struct ALGraph
{
	int vexnum; //图的顶点数
	int arcnum; //图的弧数
	ALGraph(int v, int a)
	{
		this->vexnum = v;
		this->arcnum = a;
	}
} ALGraph;

//建立一个图
ALGraph G(MAXVERTEXNUM, MAXARCNUM);
//建立顶点表
VNode AdjList[MAXVERTEXNUM];

//初始化顶点表(在顶点表后面加入边表结合)
void createGraph(ALGraph &G, VNode (&AdjList)[MAXVERTEXNUM])
{
	int i;
	printf("依次输入顶点表结点");
	for (i = 0; i < G.vexnum; ++i)
	{
		//输入顶点表结点
		scanf("%d", &AdjList[i].data);
	}

	//处理边表结点
	for (i = 0; i < G.vexnum; ++i)
	{
		//依次处理每个顶点表的结点
		int n = 0;
		int input = 0;
		printf("please input node(%d)'s edge-nodes num\n", (i + 1));
		scanf("%d", &n);
		if (n == 0)
		{
			continue;
		}
		printf("please input edge-nodes one by one\n");
		scanf("%d", &input);
		n--;
		ArcNode *arc = new ArcNode(input);
		AdjList[i].first = arc;
		while (n > 0)
		{
			scanf("%d", &input);
			ArcNode *temp = new ArcNode(input);
			arc->next = temp;
			arc = arc->next;
			n--;
		}
	}
	printf("---------------------------------------------------\n");
}

void deleteGraph(ALGraph &G, VNode (&AdjList)[MAXVERTEXNUM])
{
	//这个函数很简单,删除所有结点与指针,释放内存空间即可
	for (int i = 0; i < G.vexnum; ++i)
	{
		if (AdjList[i].first)
		{
			delete[] AdjList[i].first;
		}
	}
	printf("delete OK");
}

void PrintGraph()
{
	for (int i = 0; i < G.vexnum; ++i)
	{
		printf("node(%d)'s information\n", (i + 1));
		printf("node number is %d\t", AdjList[i].data);
		printf("the edge-nodes contains\n");
		ArcNode *temp = AdjList[i].first;
		while (temp != NULL)
		{
			printf("%d", temp->adjvex);
			temp = temp->next;
		}
		printf("\n");
	}
}
int main(int argc, char const *argv[])
{
	createGraph(G, AdjList);
	PrintGraph();
	deleteGraph(G, AdjList);
	return 0;
}
全部评论

相关推荐

coffrar:全都是已读😅沟通一千五百多个了
点赞 评论 收藏
分享
03-15 20:26
已编辑
电子科技大学 C++
T3题面:给一个3e5数组,每次询问长度为len的子数组乘积的和,如果子数组乘积&gt;1e9,则视为0.赛后一分钟想出来了,比赛时打了个暴力+线段树注意到1e9大约是2^30,&nbsp;因此len长度如果&gt;30就直接输出0,30以内做一个记忆化就行,复杂度O(30*n)感觉是以前比赛做过的题,忘了怎么做了。。。---upd:&nbsp;忘了数据范围了,如果有0,1的话那这样也不行
blueswiller:给出一个做法,刚刚才想到,应该没问题,时间复杂度为 O(max(30n, nlogn)): 1. 根据 0 切分数组。2. 现在问题转化为>=1 的情况,我们首先维护每一个数前一个 > 1 的数的位置,同时维护一个长度的差分数组,初始值全为 0。3. 我们从每一个数 i 开始向前跳,至多跳 30 次,维护这个过程中的乘积,于是得到 30 个区间加和。举例:假设从 j1 跳到 j2 ,相当于对查询长度 (i- j1 + 1) 至 (i - j2) 贡献 a_i * ... * a_j1。4. 对于所有区间加和,我们采用差分数组结合树状数组对其进行维护,由于长度至多为 n ,树状数组构建的复杂度为 O(nlogn),于是,构建阶段的复杂度为 O(max(30n, nlogn))。在线单次查询的复杂度为树状数组查询的复杂度 O(logn)。
投递淘天集团等公司10个岗位 > 笔试
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务