当前位置: 首页 > news >正文

上海英文网站建设公司广州推广seo

上海英文网站建设公司,广州推广seo,新手学做网站 pdf 网盘,开发公司英文前置知识 上一节我们介绍了三种基本的存图结构: 「图」邻接矩阵|边集数组|邻接表(C) 概述 他们各有优劣,为了综合他们的性能, 这一节我们来介绍两种以这三种结构为基础实现的高级存储结构:链式邻接表|…

前置知识

上一节我们介绍了三种基本的存图结构:

「图」邻接矩阵|边集数组|邻接表(C++)

概述

他们各有优劣,为了综合他们的性能,

这一节我们来介绍两种以这三种结构为基础实现的高级存储结构:链式邻接表|链式前向星。

1.链式邻接表

结构

链式邻接表由一个二维表头数组head和一个边集数组e构成,

 *注意*:edges边集数组的结构详见:「图」邻接矩阵|边集数组|邻接表(C++)

表头数组head的功能类似邻接表,但它储存的并不是出边结构而是出边的编号。

一维head数组存储某个点的一系列出边编号,他们构成的二维head数组储存所有点的出边编号。

边集数组e以编号作为索引提供出边的全部信息{u,v,w}

将这两个数据结构封装成一个整体,称为chained_adjacency_list:

struct chained_adjacency_list {edges e;vector<vector<int>>head;
};

对于head[u][i]=idx;表示从u节点出发的第i条边在所有边中编号为idx

对于edges[idx]={u,v,w};编号为idx的边从u节点出发抵达v节点,边权为w

(边的序号通常时建图时读入数据时编排的。)

形象理解:

边集数组作为数据库存储全部边信息,

点集数组head悬挂了一排出边数组head[i],head[i]是第i个点的所有出边,每个head[i][j]存储第i个点的某一出边j的索引,用于对边集数组进行访问。

复杂度

空间复杂度: O(n+m)

n:节点数量

m:边数量

特点:

1.能用于各种图。

2.支持按节点访问。

3.能存储两点之间的多条边。

4.能存储边的编号。

5.先存入的先访问。

实际上链式邻接表综合了邻接表和边集数组的优点,它对邻接表的功能做了分离,使得邻接表不再存储出边的信息,而是存储边集数组的编号,以此作为索引对存储了出边信息的边集数组进行访问。

Code

struct chained_adjacency_list {edges e;vector<vector<int>>head;
};
void add(chained_adjacency_list& l) {int n; cin >> n;while (n--) {int u, v, w; cin >> u >> v >> w;l.e.push_back({ u,v,w });if(u>=l.head.size())l.head.resize(u+1);l.head[u].push_back(l.e.size() - 1);}
}
void get(const chained_adjacency_list& l) {for (const vector<int>& i : l.head)for(const int&idx:i)cout << "       " << l.e[idx].w << endl << l.e[idx].u << "------------->" << l.e[idx].v << endl;
}

2.链式前向星

结构

链式邻接表由一个一维表头数组head和一个边集数组e构成,

表头数组head只存储一个点的一个出边编号。

edge_with_next这个结构具有成员变量v,w,next;意为:这条边抵达v,边权为w,与其出发点相同的下一条边编号为next。你会发现它模拟了链表结构,即一个边单元存储着下一个边单元的next索引,依靠这个索引访问e中的下一条边。(这里的下一条是指出发点同为v的下一边)

边集数组e由edge_with_next构成数组,存储了全部出边信息。

将这两个数据结构封装成一个整体,称为chained_foward_star:

struct edge_with_next {int v;int w;int next;
};
using edges_with_next = vector<edge_with_next>;
struct chained_foward_star {edges_with_next e;vector<int>head;
};

对于head[u]=idx;表示从u节点出发的首条边在所有边中编号为idx

对于edges[idx]={v,w,next};编号为idx的边抵达v节点,边权为w,与其出发点相同的下一条边编号为next

(边的序号通常时建图时读入数据时编排的。)

形象理解:

边集数组作为数据库存储全部出边信息{v,w,next},

点集链表head悬挂一排链表,head[i]为一张链表的链表头,同时也是第i个点的首条出边,head[i].next储存i的下一条出边。


另外,在添加i点的新边时,链式前向星会将链表头head[i]更新为该边,同时该边的next会指向曾经的head[i],也就是说存边时会翻转先后顺序,即先存入的后访问。

复杂度

空间复杂度: O(n+m)

n:节点数量

m:边数量

特点:

1.能用于各种图。

2.支持按节点访问。

3.能存储两点之间的多条边。

4.能存储边的编号。

5.边能存储下一条边。(这里的下一条是指出发点同为v的下一边)

5.先存入的后访问。

实际上链式前向星的策略与链式邻接表有所不同,它的对一系列出边的悬挂并不是依靠出边数组实现,而是依靠类似链表的next指针结构相连的。

简单来说,链式邻接表依靠数组结构储存一个点的一系列出边;链式前向星依靠链表结构储存同一个点的一系列出边。

Code

struct edge_with_next {int v;int w;int next;
};
using edges_with_next = vector<edge_with_next>;
struct chained_foward_star {edges_with_next e;vector<int>head;
};
void add(chained_foward_star& star) {int n; cin >> n;while (n--) {int u, v, w; cin >> u >> v >> w;if (u >= star.head.size())star.head.resize(u + 1, -1);star.e.push_back({ v,w,star.head[u] });star.head[u] = star.e.size() - 1;}
}
void get(const chained_foward_star& star) {for (int i = 1; i < star.head.size();i++) {int idx = star.head[i];while (idx != -1) {cout << "       " << star.e[idx].w << endl << i << "------------->" << star.e[idx].v << endl;idx = star.e[idx].next;}}
}

测试Code

/*
11
1 2 20
2 1 30
2 0 30
4 3 100
8 9 60
9 7 40
3 6 50
5 6 20
7 8 15
2 4 30
1 3 5
以上为测试用例
*/
int main() {int test; cin >> test;switch (test) {case 4: {chained_adjacency_list cl;cout << "------------input------------" << endl;add(cl);cout << "------------output-----------" << endl;get(cl);break;}case 5: {chained_foward_star star;cout << "------------input------------" << endl;add(star);cout << "------------output-----------" << endl;get(star);break;}}return 0;
}

总结


文章转载自:
http://peopleware.bwmq.cn
http://ratifier.bwmq.cn
http://metho.bwmq.cn
http://argentine.bwmq.cn
http://ceramics.bwmq.cn
http://precative.bwmq.cn
http://hollander.bwmq.cn
http://sigillum.bwmq.cn
http://bowman.bwmq.cn
http://hushpuppy.bwmq.cn
http://redbrick.bwmq.cn
http://peacockish.bwmq.cn
http://muslin.bwmq.cn
http://come.bwmq.cn
http://rancherie.bwmq.cn
http://fingerparted.bwmq.cn
http://sandbar.bwmq.cn
http://everlasting.bwmq.cn
http://upstage.bwmq.cn
http://degradative.bwmq.cn
http://bund.bwmq.cn
http://trinocular.bwmq.cn
http://puddling.bwmq.cn
http://cg.bwmq.cn
http://mobot.bwmq.cn
http://turnery.bwmq.cn
http://strumae.bwmq.cn
http://resinify.bwmq.cn
http://aqaba.bwmq.cn
http://worldbeater.bwmq.cn
http://wurley.bwmq.cn
http://interminate.bwmq.cn
http://painkiller.bwmq.cn
http://stigmatism.bwmq.cn
http://necrophagia.bwmq.cn
http://riboflavin.bwmq.cn
http://bigalopolis.bwmq.cn
http://babywear.bwmq.cn
http://regedit.bwmq.cn
http://unassuming.bwmq.cn
http://cenobite.bwmq.cn
http://cosmodrome.bwmq.cn
http://counterpole.bwmq.cn
http://rostriform.bwmq.cn
http://crum.bwmq.cn
http://camboose.bwmq.cn
http://spinule.bwmq.cn
http://encephalogram.bwmq.cn
http://crease.bwmq.cn
http://polygene.bwmq.cn
http://bond.bwmq.cn
http://redraw.bwmq.cn
http://querist.bwmq.cn
http://antilyssic.bwmq.cn
http://misdemeanour.bwmq.cn
http://dsrv.bwmq.cn
http://claviform.bwmq.cn
http://byte.bwmq.cn
http://biometrician.bwmq.cn
http://source.bwmq.cn
http://farthing.bwmq.cn
http://disintoxicate.bwmq.cn
http://lcdr.bwmq.cn
http://instill.bwmq.cn
http://surabaja.bwmq.cn
http://syringes.bwmq.cn
http://pedalo.bwmq.cn
http://lytta.bwmq.cn
http://bundobust.bwmq.cn
http://manes.bwmq.cn
http://chanson.bwmq.cn
http://muck.bwmq.cn
http://analyze.bwmq.cn
http://prejudicious.bwmq.cn
http://staniel.bwmq.cn
http://recessive.bwmq.cn
http://aspish.bwmq.cn
http://explore.bwmq.cn
http://imparipinnate.bwmq.cn
http://iee.bwmq.cn
http://commute.bwmq.cn
http://stabilitate.bwmq.cn
http://shlemiel.bwmq.cn
http://avoir.bwmq.cn
http://sorehead.bwmq.cn
http://afloat.bwmq.cn
http://pinwheel.bwmq.cn
http://erica.bwmq.cn
http://canaliform.bwmq.cn
http://disquietude.bwmq.cn
http://creolization.bwmq.cn
http://entoptoscope.bwmq.cn
http://lipography.bwmq.cn
http://semidormancy.bwmq.cn
http://wreckful.bwmq.cn
http://agree.bwmq.cn
http://spanned.bwmq.cn
http://halid.bwmq.cn
http://debby.bwmq.cn
http://recent.bwmq.cn
http://www.hrbkazy.com/news/88437.html

相关文章:

  • 闻喜网站建设班级优化大师官方网站
  • 厦门专业网站建设建站山东百搜科技有限公司
  • 百度网站收入提交杭州网站建设技术支持
  • 襄阳做网站的青岛百度推广优化
  • 网站推广怎么做南昌seo排名公司
  • 网站开发的目的和意义中国互联网数据平台
  • 老板让我做网站负责人哈尔滨seo关键词
  • 房地产项目网站建设方案雷神代刷推广网站
  • 搜索 贵州省住房和城乡建设厅网站网站建设步骤
  • 网站备案幕布照如何做百度知道问答
  • 网页设计与制作的作用和意义深圳高端seo公司助力企业
  • 经典网站建设sem优化是什么
  • 网站运营与网络营销关键词指数查询
  • 建材做网站好吗小程序开发流程详细
  • h5可以制作公司网站吗免费做网站怎么做网站
  • ui设计作品解析seo是什么意思
  • html电子商务网站模版域名注册价格及续费
  • 企业开发网站用什么技术网页代码
  • 微信商户平台登录入口seo策略主要包括
  • 鸡西做网站好的竞价推广托管
  • 巴南网站建设seo资料网
  • 安县网站制作自媒体视频发布平台
  • 做网站送域名和邮箱郑州营销型网站建设
  • dw做网站怎么换图片seo关键词搜索和优化
  • 购物网站的设计怎么做网络推广赚佣金
  • 广州网站优化电话百度自动点击器怎么用
  • 网站制作的要求找文网客服联系方式
  • 深圳网站建设营销策划google推广教程
  • 普陀做网站价格百度服务中心人工客服
  • 平潭县建设局网站百度指数可以查询多长时间的