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

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

2013-11-6 14:21
5900
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的值已经是我们需要的值了, 而且大家也是链在一起的。

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

这份代码里面就看到这种技巧了: 18fK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4y4%4N6r3y4Z5i4K6u0W2j5$3!0E0i4K6u0r3i4K6N6q4M7Y4y4U0i4K6u0r3M7X3g2Y4k6i4S2H3i4K6u0r3L8X3k6S2i4K6u0W2j5#2)9J5k6i4c8^5N6l9`.`.

[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 0
支持
分享
最新回复 (15)
雪    币: 240
活跃值: (190)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
2
但是,一般编程,不会像你这样写呀,估计只有你才会这样写吧。反正 我是从来没有像你那样写过代码。

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

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

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

指针和值怎么可能合体?

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

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

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

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

建议这位兄弟看看这个代码,是1个简单的正则表达式功能,不到400行代码,保证你会遇到和我一样的疑惑,顺便看看我们的理解是否一致:a60K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4y4%4N6r3y4Z5i4K6u0W2j5$3!0E0i4K6u0r3i4K6N6q4M7Y4y4U0i4K6u0r3M7X3g2Y4k6i4S2H3i4K6u0r3L8X3k6S2i4K6u0W2j5#2)9J5k6i4c8^5N6q4!0q4x3#2)9^5x3q4)9^5x3R3`.`.
2013-11-7 12:36
0
雪    币: 5
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
没值, 还要指针干嘛?
next的值正好就是我要的值啊,next不是指向下1个结点的地址麽,即下1个结点的地址正是哥想要的值,从整个链表看,所有结点的地址都是我要的值,即所有结点的next值以及链表头的值正好是我要的值。从应用场景看,如果我想把一组指针的地址(甚至是指针,知道指针地址还得不到指针?)保存起来,而且指针的个数事先无法预计,且随时都可能添加、删除,就可以用这种方式。
2013-11-7 12:44
0
雪    币: 240
活跃值: (190)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
8
我想兄弟是没有明白我的意思,跟本不知道什么是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;//这里不是指针

}

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

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

这时候节点A的实际值怎么存放?放到next里则next不为空说明后面还有一个节点,如果next为null则说明最后一个节点没有值。。。
2013-11-8 14:01
0
雪    币: 357
活跃值: (4528)
能力值: ( LV3,RANK:25 )
在线值:
发帖
回帖
粉丝
11
楼主是吃shi多了溢出来吗?
2013-11-8 14:38
0
雪    币: 5
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
12
场景: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成员,也达到效果了。当然这种方法只能使用于特定的应用场景,这些指针最终肯定是要指向一些有具体意义的对象,而不是仅仅手拉手白站在链表里,比如一些指针的指向,需要等到某个计算结果出来以后才能明确,就可以先加到链表里“排队”。

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

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