首页
社区
课程
招聘
[原创]链表之“结点即负载”
2013-11-6 14:21 5705

[原创]链表之“结点即负载”

2013-11-6 14:21
5705
struct Node {
    struct Node *next;
    void *load;
};

一般情况下, next只是起连接结点的作用, 真正需要的值存在load里面, 而,
以下这样的情况, 每个结点的load值, 正好就是next的值, 那就不需要load这个变量了:
     node0         ->      node1       ->  ..  ->  node(n)  -> ..
next = &node1    next = &node2             next = &node(n+1)
load = &node1    load = &node2             load = &node(n+1)

比如我们需要将一堆指针的地址链在一起, 就可以定义:
struct Node {
    struct Node *next;
};
     ptr0         ->      ptr1       ->  ..  ->  ptr(n)  -> ..
next = &ptr1     next = &ptr2            next = &ptr(n+1)
这样, 每个next的值已经是我们需要的值了, 而且大家也是链在一起的。

很明显, 这里节省了内存, 在很多特殊的情况还是很有用的, 而且看一起伟大前辈写的代码时, 他们那个时候本来内存就紧张, 所以可能会使用这些技巧, 遇到时就不会觉得迷茫了, “结点即负载”是自己为了方便记忆这个技巧随便起的一个名称。

这份代码里面就看到这种技巧了: http://swtch.com/~rsc/regexp/nfa.c.txt

[培训]《安卓高级研修班(网课)》月薪三万计划,掌 握调试、分析还原ollvm、vmp的方法,定制art虚拟机自动化脱壳的方法

收藏
点赞0
打赏
分享
最新回复 (15)
雪    币: 239
活跃值: (190)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
choday 2 2013-11-6 15:24
2
0
但是,一般编程,不会像你这样写呀,估计只有你才会这样写吧。反正 我是从来没有像你那样写过代码。

一般,。链表结点都包含在“负载”里面的。。可以参考一下LIST_ENTRY 用法.而且一个“负载”可以包含多个链表节点。

这样写,不是因为内存紧张,而是因为减少错误,减少内存碎片,减少编程工作量。

按你的写法,
要访问load的话,需要先找到节点,再取load地址,多了一个过程,取load时,还得判断load值是否为空,这样,即增加代码书写量,还增加cpu运算量。
删除 load后,还得删除你的struct Node,同样 ,增加工作量,增加cpu运算量。
雪    币: 357
活跃值: (2643)
能力值: ( LV3,RANK:25 )
在线值:
发帖
回帖
粉丝
KooJiSung 2013-11-6 15:38
3
0
没看懂, 没值, 还要指针干嘛?

指针和值怎么可能合体?

你是分开处理吧,最后还是要处理值.

搞得那么复杂干嘛?
雪    币: 185
活跃值: (25)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
whnet 2013-11-6 15:38
4
0
那也就是说值不能变了? 那你这还能叫链表? 为何不直接使用数组.
雪    币: 2155
活跃值: (29)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
LiXMX 2013-11-6 17:26
5
0
LZ你这个链表不对啊。。。

你的每一个节点中的load都指向下一个节点是为什么?
load指针是用来指向节点所绑定的数据区块的。。。

就好像楼上仁兄说的,你这个就成了数组了啊。。。
雪    币: 5
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
nosay丶 2013-11-7 12:36
6
0
① 要访问load的话,需要先找到节点,再取load地址,多了一个过程;
如果可以随机访问,那不就是数组了?
② 取load时,还得判断load值是否为空,这样,即增加代码书写量,还增加cpu运算量。
值为空就是链表尾巴了啊,你访问单向链表难道都不判断是否已到达尾部的吗?

建议这位兄弟看看这个代码,是1个简单的正则表达式功能,不到400行代码,保证你会遇到和我一样的疑惑,顺便看看我们的理解是否一致:http://swtch.com/~rsc/regexp/nfa.c.txt。
雪    币: 5
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
nosay丶 2013-11-7 12:44
7
0
没值, 还要指针干嘛?
next的值正好就是我要的值啊,next不是指向下1个结点的地址麽,即下1个结点的地址正是哥想要的值,从整个链表看,所有结点的地址都是我要的值,即所有结点的next值以及链表头的值正好是我要的值。从应用场景看,如果我想把一组指针的地址(甚至是指针,知道指针地址还得不到指针?)保存起来,而且指针的个数事先无法预计,且随时都可能添加、删除,就可以用这种方式。
雪    币: 239
活跃值: (190)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
choday 2 2013-11-8 12:31
8
0
我想兄弟是没有明白我的意思,跟本不知道什么是LIST_ENTRY

我的意思是:

比如你说的负载为
struct loader
{

int data0;
int data1;
int data2;
.....
};

按你的思路 来,是这样写
struct link
{
struct link* next;
struct loader* loaderptr;//这里是指针
};

你是这意思吧。

而我的意思是

struct linknode
{
struct linknode* next;
strcut loader       value;//这里不是指针

}

你看清楚 这两种表达 方式 ,
我为什么要用你说所的那种方式呢,
雪    币: 238
活跃值: (55)
能力值: ( LV5,RANK:70 )
在线值:
发帖
回帖
粉丝
sierra 1 2013-11-8 13:34
9
0
愚以为lz陷入了误区,不知道对不对
雪    币: 2155
活跃值: (29)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
LiXMX 2013-11-8 14:01
10
0
那你的最后一个节点的值呢?放到哪里去了?

假如有一个节点A,他是链表上的最后一个节点,要求每个节点的NEXT指向的是下一个节点或者NULL。

这时候节点A的实际值怎么存放?放到next里则next不为空说明后面还有一个节点,如果next为null则说明最后一个节点没有值。。。
雪    币: 357
活跃值: (2643)
能力值: ( LV3,RANK:25 )
在线值:
发帖
回帖
粉丝
KooJiSung 2013-11-8 14:38
11
0
楼主是吃shi多了溢出来吗?
雪    币: 5
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
nosay丶 2013-11-9 01:48
12
0
场景:void *p1, *p2, *p3, ...,将这些指针的地址值用链表保存起来:

方法①:
struct paddr {
    struct paddr *next;
    void *pvalue;
};
struct paddr head, node1, node2, node3, ...;
head.next = &node1, head.pvalue = NULL;
node1.next = &node2, node1.pvalue = &p1;
node2.next = &node3, node2.pvalue = &p2;
node3.next = &node4, node3.pvalue = &p3;
... ...

方法②:
void *head = &p1;
p1 = &p2;
p2 = &p3;
p3 = &p4;
... ...

如果这样还看不明白,可以这样理解:
struct paddr {
    struct paddr *next;
};

将p1,p2,p3,...分别看作node1,node2,node3,...,问题转换成需要将这些node的地址保存起来。茅塞顿开了没有?node的地址?每个node的地址不就是上个node的next值。

只是说还是有些抽象,以下算是证明吧:
struct paddr head, node1, node2, node3, ...;
                   p1     p2     p3     ...
既然你提到LIST_ENTRY,那麽应该能理解&node1->next == &node1吧?
还是跟你解释一下吧,next成员相对于paddr结构的偏移是0,所以它的地址与整个结构变量的地址相同。
以此类推:&node2->next == &node2;
         &node3->next == &node3;
         ... ...

目的不就是要保存这些指针的地址麽!从p1开始,保存到head结点中:
head.next = &p1 (其中,&p1 == &node1 == &node1->next)
这里head.next不仅保存了p1指针的地址值,而且正好也指向了node1->next地址,即head与node1链在了一起;
将p2的地址保存到p1中:
p1 = &p2 (其中,&p2 == &node2 == &node2->next)
这里p1不仅保存了p2指针的地址值,而且正好也指向了node2->next地址,即node1与node2链在了一起;
... ...

这样,不需要void *pvalue成员,也达到效果了。当然这种方法只能使用于特定的应用场景,这些指针最终肯定是要指向一些有具体意义的对象,而不是仅仅手拉手白站在链表里,比如一些指针的指向,需要等到某个计算结果出来以后才能明确,就可以先加到链表里“排队”。

还是建议看看这份代码:http://swtch.com/~rsc/regexp/nfa.c.txt
不要什么状况都还没搞清楚,就表示反对,做人要理性。
雪    币: 239
活跃值: (190)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
choday 2 2013-11-10 17:59
13
0
搞不明白你的意图,猜测你只是想表达链表这一个数据结构吧,但真心的,没那么复杂
你发的链接,看了,没发现什么特别之处,很平常的代码。
“结点即负载”
一般情况下结点本来就是负载,但也有人,就是要弄一个不是“负载”的节点出来,而是在节点中放负载指针,就像你例子中前一种情况 ,但是我想不出来,为什么需要这样处理,除非什么特殊情况,比如虚拟内存文件页表,就是这样的情况,节点不需要包含虚拟内存数据,只需要包含指针而已,这样,便可能存在如你所说,节点的负载可以为空的情况,仅仅是一个节点,而不包含任何负载“虚拟内存”。当需要把虚拟 内存从虚拟文件中调出来时,相应节点上才会有负载

一般情况下,只需要“结点即负载”,不需要用“节点”来包含“负载”指针 。
雪    币: 238
活跃值: (55)
能力值: ( LV5,RANK:70 )
在线值:
发帖
回帖
粉丝
sierra 1 2013-11-10 19:18
14
0
为楼主的IQ捉急。请问编译好后,用方法2写的程序如何在所谓的链末尾动态增加一个新的节点?方法2中的链的节点数目在编译后已经无法改变,而方法1中的结构是单向链表可以动态增加节点。楼主你有空应该看看c语言的指针部分和数据结构,否则会问一些引人发笑的问题。我写此文只是希望楼主不要误入歧途愈陷愈深。
雪    币: 239
活跃值: (190)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
choday 2 2013-11-10 20:18
15
0
的确捉急
雪    币: 5
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
nosay丶 2013-11-10 22:02
16
0
呵呵,我写这个东西的目的是为自己做个笔记,不是逗你们发笑,只有浮躁的人才会轻易嘲笑别人。给了一份大牛的代码,不知道才理解多少就评价是一份普通的代码,很多人看完都会赞写的妙,包括一些码龄将近10年的大牛。不理解方式②,我敢确定你根本没有静下心来看过这份代码,又或许你们是超大牛吧,因为好像对别人写的东西很不屑的样子。我能体会到你们的一点点好意,想劝我回头是岸、悬崖勒马,但你们连我表达的是什么意思都不理解,就开始攻击我的IQ,就相当于我站在楼顶看风景,你们俩在后面鬼哭狼嚎:不要跳楼,不要跳楼。呵呵,好玩 。
游客
登录 | 注册 方可回帖
返回