首页 > 其他分享 >链式前向星

链式前向星

时间:2024-05-11 21:43:41浏览次数:14  
标签:idx int 权值 ne 索引 链式 idx0 前向星

存边的结构,也是挺简单的,重点就三个数组h,ne,e和一个变量idx
idx是index索引的缩写,这就是它的作用,索引。
时间空间复杂度都是$O(n + m)$很不错
h是存的表头,ne存的是下一个点的idx,e是当前点的序号,一般还有一个w存的是当前点的权值

更详细一些
h[a]表示a的表头,里面存储的是a所连向点b的idx,而e[idx]就是b点的序号b,ne[idx]是a连向的下一个边的idx,w[idx]存的是权值。
这都有什么用?
看看加边代码

void add(int a, int b, int c) // 从a向b连一条权值为c的边
{
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}

现在来说说这些量是怎么存边的。
首先idx开始为0,且此时没有被任何一条边使用。
开始我们让h[a] = -1
-1表示没有,即a现在不连向任何一条边
现在加入一条从a连向b的边
这时候索引idx,正好没用我们把它分配给这条边。
这条边的终点e[idx] = b,我们让ne[idx] = h[a], h[a] = idx
表示a里面添加了一个索引idx,通过h[a]就能找到这个点,再通过ne[idx]
就能找到之前存的点,而这条边的信息e[idx],也有idx所关联。就相当于存起来了。
给一张好懂的图
链式前向星

关于w,它和e作用一样都是存储当前边信息的
而加边,就是让ne[idx0] = h[a]也就是ne[idx0] = idx1
然后让h[a] = idx0即可

标签:idx,int,权值,ne,索引,链式,idx0,前向星
From: https://www.cnblogs.com/blind5883/p/18187185

相关文章

  • 10.5线性表的链式存储
    链表顺序表:缺点1、插入和删除操作移动大量元素。2、数组大小不好确定。3、占用空间。优点随机访问逻辑相邻物理位置上也相邻单链表(逻辑上相邻物理不相邻)链表定义:typedefintElemtype;structLNode{ Elemtypedata;//数据域 structLNode*next;//指针域};优点1......
  • js 链式调用
    functionarrany(name){lettasks=[]tasks.push(()=>{console.log(name)})functionwait(duration){tasks.push(()=>newPromise(resolve=>{setTimeout(resolve,duration)}))returnthis}functionexecute(......
  • 链式栈设计
    链式栈接口设计/***@name:链式栈接口设计*@brief*@[email protected]*@date2024/04/28*@version1.0:版本*@property:类比于顺序栈,链式栈也有一个栈顶和栈底。根据链式表特性,将第一个插入的值作为栈底,即尾节点作为栈底。首节点作为栈顶。*@note*CopyR......
  • 链式队列
    以链表为基础实现链式队列/**********************************************************************************filename:Linked_Queues*author:[email protected]*date:2024/04/26*function:以链表为基础实现链式队列,一般把链表头......
  • 以链表为基础实现链式队列
    以链表为基础实现链式队列如果打算以链表作为基础来实现队列的操作,可以避免内存浪费以及避免内存成片移动,只需要确定队头和队尾即可,一般把链表头部作为队头,可以实现头删,把链表尾部作为队尾,可以实现尾插。#include<stdio.h>#include<stdbool.h>#include<stdlib.h>//对输入......
  • 数据结构——链式栈
    二、链式栈构造链式栈//链式栈的有效数据类型,用户可以根据需要进行修改typedefintDataType_t;//构造单链式栈的结点typedefstructLinkedStack{DataType_tdata;//结点的数据域structLinkedStack*next;//结点的的指针域}LinStack_t......
  • 链式队列
    队列原理介绍:​ 队列(Queue)和栈类似,相同点是都属于线性结构,不同点是栈遵循“后进先出”原则,而队列遵循“*先进先出*”的原则,也被称为“FIFO”结构,就是“FirstInputFirstOutput”​ 数据结构中的队列的两端都允许操作,只不过要求数据只能从队列的一端插入,从队列的另一端删除,可......
  • 单向链式队列
    目录目录单向链式队列创建空链表创建新结点入队判断链表是否为空出队遍历代码验证单向链式队列/**@filename: main.c@brief单向链式队列@[email protected]@date2024/04/[email protected]:版本@property:属性介绍@note补充注意说明CopyRight(c)2023......
  • 以链表为基础实现链式队列
    数据结构链式队列以链表为基础实现链式队列1.思路:如果打算以链表作为基础来实现队列的操作,可以避免内存浪费以及避免内存成片移动,只需要确定队头和队尾即可,一般把链表头部作为队头,可以实现头删,把链表尾部作为队尾,可以实现尾插。2.图示:3.代码:/****************************......
  • 链式栈接口程序
    链式栈接口程序目录链式栈接口程序以链表作为基础实现栈空间(链式栈)头文件链式栈的创建创建一个空的链式栈节点入栈出栈验证输出结果以链表作为基础实现栈空间(链式栈)图解头文件/********************************************************************* filename: 链式......