Chinaunix

标题: 数据结构保存问题!急!(高手请进) [打印本页]

作者: 3018857 时间: 2007-10-10 17:03
标题: 数据结构保存问题!急!(高手请进)
现在在工程中已经有了一套数据结构(比如树).现在需要用其他的工程来用这套结构中的数据,及每个对象间的关系.
我知道现在的文件只能保存数据(比如struct中的变量等),但如果变量成员中有指向其他对象的指针,也就是是他们之间是有联系的.该如何实现其保存呢?

如果用fread/fwrite来处理,只能保存数据,不知道这些对象(或结构)之间的关系该如何保存下来让后续工程直接利用呢?

万分感谢!!

作者: MMMIX 时间: 2007-10-10 18:52
将用非线性数据结构保存的数据先线性化, 然后写入文件, 后面的代码要使用这些数据, 将这个过程反着做一遍即可.

BTW, 可以参考通过网络传输通过复杂数据结构保存的数据的实现方法.

作者: 3018857 时间: 2007-10-10 19:02
标题: 回复 #2 MMMIX 的帖子
谢谢你了!老大!
当时也是考虑到时间紧迫,所以不想用网络来连接.
现在我倒是要看看数据结构线性化方面的东西了!等有了问题再来请教!

作者: MMMIX 时间: 2007-10-10 19:05

原帖由 3018857 于 2007-10-10 19:02 发表
谢谢你了!老大!
当时也是考虑到时间紧迫,所以不想用网络来连接.
现在我倒是要看看数据结构线性化方面的东西了!等有了问题再来请教!

很简单的, 基本就是写/读双方约定好就可以了.

作者: cugb_cat 时间: 2007-10-10 19:32
跟网络协议是一个道理，双方说好，第一个字节是什么意思，第二个字节是什么意思。。。。。。。。等等

作者: 3018857 时间: 2007-10-10 22:11
标题: 回复 #4 MMMIX 的帖子
不懂！约定好了就没有意思了吧。读方根本就不知道写方数据结构的任何信息，如果用而进制文件只能将保存的数据提取出来，而指针变量没法知道啊！而且数据结构的节点也在变化啊，每次都不定，当保存下来，每次读的时候该怎么读呢？真是太郁闷了！

例如：
　　　写方有三层数据，每次数据都有联系，我把每个节点可以保存下来，但该怎么保存呢，因为它们的大小不同，读取的时候也不知道现在读的是谁，读完没有，该类型一共有几个。

你说的约定能给稍微具体点吗？是说我该用到其他的工具吗还是要对二进制文件的存法有处理呢，等等！！

[ 本帖最后由 3018857 于 2007-10-10 22:17 编辑 ]

作者: 3018857 时间: 2007-10-10 22:13
标题: 回复 #5 cugb_cat 的帖子
你说的约定能给稍微具体点吗？是说我该用到其他的工具吗还是要对二进制文件的存法有处理呢，等等！！对于字节我怎么规定呢？谢谢！

作者: evaspring 时间: 2007-10-11 11:05
约定好预先读取几个字节，然后将这段字节强制转化为约定好的数据结构。

作者: JohnBull 时间: 2007-10-11 11:54
用广义表，或者干脆用XML。

作者: 3018857 时间: 2007-10-11 12:12
标题: 回复 #8 evaspring 的帖子
我的要求是第一个工程关闭后，将整个数据保存下来，然后再启动令一个数据处理的工程来处理数据。
他们之间能约定好数据结构吗？应该没办法吧！比如一个树，最底层的节点每次保存的数目是不同的，如何约定呢？是不是事先把文件分块，然后往里面扔东西，取的时候就按事先的地址来取！？？？

作者: 3018857 时间: 2007-10-11 12:14
标题: 回复 #9 JohnBull 的帖子
我想用二进制文件，并且是一个文件来保存！因为我的任务比较急，没时间去弄xml！因为没有接触过。
我的要求是第一个工程关闭后，将整个数据保存下来，然后再启动令一个数据处理的工程来处理数据。
他们之间能约定好数据结构吗？应该没办法吧！比如一个树，最底层的节点每次保存的数目是不同的，如何约定呢？是不是事先把文件分块，然后往里面扔东西，取的时候就按事先的地址来取！？？？

[ 本帖最后由 3018857 于 2007-10-11 12:15 编辑 ]

作者: 思一克 时间: 2007-10-11 12:22
用目录表示树。接点内容保存为文件。
保存好后，tar成一个文件。

作者: cugb_cat 时间: 2007-10-11 13:16

原帖由 3018857 于 2007-10-11 12:14 发表
我想用二进制文件，并且是一个文件来保存！因为我的任务比较急，没时间去弄xml！因为没有接触过。
我的要求是第一个工程关闭后，将整个数据保存下来，然后再启动令一个数据处理的工程来处理数据。
他们之间能 ...

比如一棵树：
                     1
                  / |    \
               2    3    4
         /  | \ / | \    | \
         5 6  7 8 9 10 11 12
那么在一个文件中可以这样存储：
125.6.7..38.9.10..4(11).(12)...
其中.表示该节点已经没有子节点可访问了。
另一个程序在读这个数据的时候就可以重建这棵树。

作者: cugb_cat 时间: 2007-10-11 13:17

原帖由 思一克 于 2007-10-11 12:22 发表
用目录表示树。接点内容保存为文件。
保存好后，tar成一个文件。

这个最方便了

作者: littledick 时间: 2007-10-11 14:46
简化成最小生成树，遍历并保存到文件。
读文件重新生成树。

作者: 3018857 时间: 2007-10-11 19:30
标题: 回复 #12 思一克的帖子
首先,谢谢大家了!真的很高兴能有热心的朋友探讨!

我的结构比较复杂啦,不是树,是b-rep边界表示:

            <-||    solid    ||->
               /    \    \
                                 \
         <- face-> <-edge ->  \
               /                \
      <- ||loop ||-> \       \
            /             \       \
      <-||    halfedge ||--> \
                  /                \
         <-||    vertex                ||-->

所以遍历等都比较困难!你们觉得呢?

作者: 3018857 时间: 2007-10-11 19:31
标题: 回复 #15 littledick 的帖子
首先,谢谢大家了!真的很高兴能有热心的朋友探讨!

我的结构比较复杂啦,不是树,是b-rep边界表示:

            <-||    solid    ||->
               /    \    \
                                 \
         <- face-> <-edge ->  \
               /                \
      <- ||loop ||-> \       \
            /             \       \
      <-||    halfedge ||--> \
                  /                \
         <-||    vertex                ||-->

所以遍历等都比较困难!你们觉得呢?

作者: 3018857 时间: 2007-10-11 19:32
标题: 回复 #13 cugb_cat 的帖子
首先,谢谢大家了!真的很高兴能有热心的朋友探讨!

我的结构比较复杂啦,不是树,是b-rep边界表示:

            <-||    solid    ||->
               /    \    \
                                 \
         <- face-> <-edge ->  \
               /                \
      <- ||loop ||-> \       \
            /             \       \
      <-||    halfedge ||--> \
                  /                \
         <-||    vertex                ||-->

所以遍历等都比较困难!你们觉得呢?

作者: cugb_cat 时间: 2007-10-11 21:19

原帖由 3018857 于 2007-10-11 19:32 发表
首先,谢谢大家了!真的很高兴能有热心的朋友探讨!

我的结构比较复杂啦,不是树,是b-rep边界表示:


               /    \    \
                                 \
      ...

不知道b-rep是什么，不懂

作者: buxoman 时间: 2007-10-12 09:10

原帖由 MMMIX 于 2007-10-10 18:52 发表
将用非线性数据结构保存的数据先线性化, 然后写入文件, 后面的代码要使用这些数据, 将这个过程反着做一遍即可.

BTW, 可以参考通过网络传输通过复杂数据结构保存的数据的实现方法.

怎么样把指针这种东西给线性化呢？

作者: buxoman 时间: 2007-10-12 09:12
楼主，看看本版有个帖子讲ooc，里面有一章：storing and loading data structure. 或许其中有你需要的内容。
我还没有看过。

作者: cugb_cat 时间: 2007-10-12 09:14

原帖由 buxoman 于 2007-10-12 09:10 发表

怎么样把指针这种东西给线性化呢？

类似于线索化二叉树或者理解为遍历也可以

作者: jato 时间: 2007-10-12 09:42

原帖由 3018857 于 2007-10-11 12:14 发表
我想用二进制文件，并且是一个文件来保存！因为我的任务比较急，没时间去弄xml！因为没有接触过。
我的要求是第一个工程关闭后，将整个数据保存下来，然后再启动令一个数据处理的工程来处理数据。
他们之间能 ...

把指针当作ID存不就完了吗. 读的时候再把ID恢复成指针

作者: woshiwo 时间: 2007-10-12 11:18

原帖由 buxoman 于 2007-10-12 09:10 发表

怎么样把指针这种东西给线性化呢？

遍历的过程就是线性化的过程。
但指针的线性化确实是问题，如果数据结构中的每个节点属性足以唯一的重构整个数据链，那么指针不需要线性化，在载入所有的节点后再重新动态生成即可。
否则就比较难办，对比较规则的结构，如二叉树，可以在store时对每个节点附加新的域，例如前面说的加一个ID,再线性化存储，载入时再依据ID动态生成整课树

作者: woshiwo 时间: 2007-10-12 11:21

原帖由 jato 于 2007-10-12 09:42 发表

把指针当作ID存不就完了吗. 读的时候再把ID恢复成指针

每个节点对象地址是动态的，指针当作ID存储是没有用的，这正是楼主要解决的问题

作者: halve 时间: 2007-10-12 12:06
楼主要的不是对象的地址，而是地址间的关系
用id应该是可以的

作者: 3018857 时间: 2007-10-12 14:52
标题: 回复 #24 woshiwo 的帖子
说的有理,我的结构确实比较复杂.
请问用ID的方法是指什么,我的每个节点大小不同,如果用ID来区别的话,还是存在文件分段的问题吧!如果不分段,那些属于不同父节点但编号有一样的节点,在从新载入的时候就没办法了吧?

作者: 3018857 时间: 2007-10-12 14:55
标题: 回复 #26 halve 的帖子
谢谢你能帮助解决问题,万分感谢!
用ID的方法是指什么呢?载入的时候是不是首先都载入,再根据事先约定的ID来建立关系呢?还有我的每个节点都是一个结构( struct),而且大小不同!

作者: 3018857 时间: 2007-10-12 14:55
标题: 回复 #23 jato 的帖子
谢谢你能帮助解决问题,万分感谢!
用ID的方法是指什么呢?载入的时候是不是首先都载入,再根据事先约定的ID来建立关系呢?还有我的每个节点都是一个结构( struct),而且大小不同!

作者: 3018857 时间: 2007-10-12 14:56
标题: 回复 #21 buxoman 的帖子
谢谢你能帮助解决问题,万分感谢!

作者: Maitou 时间: 2007-10-12 15:01
两个数组，一个存节点，
一个数组保存节点的关系（使用二维）如果2节点和4节点相连，表达为（2,4)，那么建立他们之间的连接。

作者: woshiwo 时间: 2007-10-12 15:43

原帖由 3018857 于 2007-10-12 14:52 发表
说的有理,我的结构确实比较复杂.
请问用ID的方法是指什么,我的每个节点大小不同,如果用ID来区别的话,还是存在文件分段的问题吧!如果不分段,那些属于不同父节点但编号有一样的节点,在从新载入的时候就没办法了吧?

一般的数结构或图结构每个节点大小是相同的，麻烦的是可能节点中除了用于建立自身的树结构的指针外，还有指向其他树结构的指针。

序列化时可对不同结构的对象分别建立各自的数组，遍历时将不同结构的节点或对象序列化到各自的数组中，然后就用数组下标作为ID即可，store时将指针转换为ID存档，load时反之。

作者: woshiwo 时间: 2007-10-12 15:45
另外如果有类的继承关系可能还要麻烦点

作者: jato 时间: 2007-10-12 21:43

原帖由 3018857 于 2007-10-12 14:55 发表
谢谢你能帮助解决问题,万分感谢!
用ID的方法是指什么呢?载入的时候是不是首先都载入,再根据事先约定的ID来建立关系呢?还有我的每个节点都是一个结构( struct),而且大小不同!

我是说存的时候把指针 cast 成32的整数或64位整数(根据你机器来确定)做ID 就可以存储了. 读进来的时候, 你的object 放在什么地址, 就把这地址得到, 取代原来的那个 ID 就可以了. 你若是都在一个内存块里, 就可以只取首地址, 其他的减一下偏移就可以了

作者: 3018857 时间: 2007-10-12 22:05
标题: 回复 #34 jato 的帖子
我读的时候根本不知道我有几个对象啊,需要根据存储的数据及关系自动生成!

作者: 3018857 时间: 2007-10-12 22:15
标题: 回复 #32 woshiwo 的帖子
谢谢!
不过我的问题是:现在结构(struct)相同的节点,他们有不同的父节点,在不同父节点下他们的ID都是1,2,3,.....

如
         s:       s1 <->       s2

                  /  /  \       / /  \ \

         f:    1<-> 2<-> 3    1<-> 2<->3<->4

struct ss
{
struct ff *f;
id;
struct ....

} s1,s2;

struct ff
{
struct ss m_pS;
id;
.....

};
f层每个需要时才建立.
即我不知道每个s下面有多少个f!

如果s层作为一个数组存起来,f层也用令一数组存,则出现ID相同的情况啊!

[ 本帖最后由 3018857 于 2007-10-12 22:35 编辑 ]

作者: 3018857 时间: 2007-10-12 22:27
标题: 回复 #31 Maitou 的帖子
你说的情况适合简单的问题,如果我的每个节点大小不同呢?

struct ss
{
struct ff *f;
id;
struct ....

} s1,s2;

struct ff
{
struct ss m_pS;
id;
.....

}

         s:       s1             s2
                  / / \       /  /  \  \

         f:    1 2    3    1  2 3 4

作者: 思一克 时间: 2007-10-12 22:37
可以这样想问题:

如果计算机休眠了,是不是要将内存全部保存到一个文件?

你也这样做不就可以了? 只不过是只保留你的数据的部分,在将文件中的空洞压缩掉.

作者: woshiwo 时间: 2007-10-12 23:16

不过我的问题是:现在结构(struct)相同的节点,他们有不同的父节点,在不同父节点下他们的ID都是1,2,3,.....

如
         s:       s1 <->       s2

                  /  /  \       / /  \ \

         f:    1<-> 2<-> 3    1<-> 2<->3<->4

struct ss
{
struct ff *f;
id;
struct ....

} s1,s2;

struct ff
{
struct ss m_pS;
id;
.....

};
f层每个需要时才建立.
即我不知道每个s下面有多少个f!

如果s层作为一个数组存起来,f层也用令一数组存,则出现ID相同的情况啊!

不同父节点下的相同结构的子节点应该使用相同的全局数组，ID当然也应该统一编码才对。

你这个其实不是真正的树结构。但同样可以实现：
定义ff层数组：struct ff ffff[many];
定义ss层数组：struct ss ssss[many-many];

遍历ff：

int  ff_index, ss_index;

for_each_ff (ff) {
   ffff[ff_index] = ff;
   ff->ff_ID = ff_index;
   ff_index++;

ff->fist_ss_ID = ss_index;

for_each_sub_ss(ss) {
      ssss[ss_index] = ss;
      ss->ss_ID = ss_index;
      ss->ff_ID = ff->ff_ID;
      ss_index++;
}

ff->last_ss_ID = ss_index - 1;
}

然后将ffff ssss存档。load时，先载入ffff ssss,再依据ID重建结构。

只是粗略的想法……

作者: tyc611 时间: 2007-10-13 01:23
如果不太在乎效率，用XML方便、可扩展性强

作者: 3018857 时间: 2007-10-13 09:46
标题: 回复 #39 woshiwo 的帖子
遍历当然不难,再复杂的都可以!
我画的结构只是一部分,比树麻烦些,光靠一两个数组不够,如果想用数组来保存估计要很多数组.
最主要的是:
我从新载入的时候只知道结构,对于有多少个节点(比如ff层)根本不知道,而且哪个ID是属于哪个s节点该如何辨别?

这么说吧: 根据我画的结构:

存储顺序:
s1->s2->f1->f2->f3->f4->f5->f6->f7;

载入:
ss ssss[many];
ff ffff[many];

将s再入SSSS,
f再入FFFF,你如何知道谁属于SS1,谁属于SS2呢,如果统一编号的话?

谢谢探讨!

[ 本帖最后由 3018857 于 2007-10-13 10:02 编辑 ]

作者: 3018857 时间: 2007-10-13 09:47
标题: 回复 #39 woshiwo 的帖子
应用多维数组倒是可以!呵呵!不过层次多了,维数太多!

[ 本帖最后由 3018857 于 2007-10-13 10:03 编辑 ]

作者: 柳五随风 时间: 2007-10-13 13:03
看看PDF 的格式文档。问题就迎刃而解了。

作者: woshiwo 时间: 2007-10-13 21:28

原帖由 3018857 于 2007-10-13 09:46 发表
遍历当然不难,再复杂的都可以!
我画的结构只是一部分,比树麻烦些,光靠一两个数组不够,如果想用数组来保存估计要很多数组.
最主要的是:
我从新载入的时候只知道结构,对于有多少个节点(比如ff层)根本不知道 ...

1、先遍历一次获取节点数再动态申请数组，或者直接采用动态数组，STL里有动态数组的实现。

2、你原来的结构是怎么存储的，现在还怎么存储，只不过用ID代替原来的指针来维持整个结构而已。比如
ff->first_child_ID = first_ss_ID;
each_ss_ID->next_ss_ID = next_ss->self_ID;
想想你原来的所有结构的指针是不是全都在相同的地址空间统一编址的？现在换成ID不也一样可以吗？只要是相同类型的节点都可以

作者: 3018857 时间: 2007-10-21 14:43
标题: 回复 #44 woshiwo 的帖子
问题已经很好的解决！多谢谢你了！

作者: imzdh 时间: 2007-11-07 11:38
递归方法解决不知道行不？

我也是刚刚遇到这个问题，数据量很大，要是按照网络协议那样的方法去规定的话，那恐怕完蛋了。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)