选择数据结构的问题，大家帮忙看看

frog_skywalker

有一个比较大的结构体数组，几千吧

现在经常需要对其进行增删，删除的地方就变空位了。多次以后可能会空很多
给确定实际有的数据数量带来困难。因此想改用链表，对面实验室一个类似的东西就是全链表的。


但是我的算法依赖于一个对那个数组下标的一些操作，直接取数据进行运算。
如果放弃这个算法，对所有数据便利，整个算法复杂程度会从n变为n^2

各位给支个招看看



如果有比较好的数据紧缩的办法就好了，就是把数组删掉的位置用后面的数据顶上来，全部移一遍会不会很好时间啊。有没有什么好的解决办法

//bow

assiss

根据你的需求选。

增删多，就用链表；随机访问多，就用数组。两个差不多，丢硬币决定。

如果你的程序具有这样的特点：集中增删，然后集中随机访问，
则可以采用链表+数组的形式：
主要结构用链表，完成增删；
随机访问前，先遍历链表，生成一个临时数组用于随机访问。

如果程序符合使用HASH的特征，则可以用HASH数组的方法。

如果……
你自己的程序你自己清楚。

frog_skywalker

程序是一个分子模拟的程序

每一运行周期内都是 集中增删，然后集中随机访问

一共运行5w-10w步

默难

对于LZ的这个项目我不是很了解，我暂时把它想象成UNIX下用文件描述符进行文件操作一样。（不知道我这么说是不是足够清楚，UNIX文件操作的内容可以参看APUE第三章，图3.2，英文版是p58页，由于我手头只有第一版的APUE，所以我这里说的都是第一版的东西……）
既然这样，可不可以考虑像UNIX分配文件描述符那样，每次分配的都是最小的未使用的下标（我不知道这么说LZ是否能清楚，具体内容可以看APUE啦）
但是这样的做法依赖的一个前提是增加和删除的数目大致相同，而且频率接近。否则一样会带来一些问题。

另外，LZ所谓的“依赖于一个对那个数组下标的一些操作，直接取数据进行运算。”是什么？依赖到什么程度呢？能不能有个比较概括的描述呢？（因为考虑到LZ项目的规模，把全部内容都说全不太可能，所以概括地说一下就好，我们能理解就可以了）

assiss

原帖由 frog_skywalker 于 2006-8-7 20:13 发表
程序是一个分子模拟的程序

每一运行周期内都是 集中增删，然后集中随机访问

一共运行5w-10w步

那用主链表+临时数组的方法是最省时间的了。
临时数组可以只存储对应链表的指针

zxh5187406

-__-b 重新设计一种自己的数据结构吧....
比如可以用array实现list功能....这样就不会出现效率上问题了...

frog_skywalker

原帖由 zxh5187406 于 2006-8-7 20:24 发表
-__-b 重新设计一种自己的数据结构吧....
比如可以用array实现list功能....这样就不会出现效率上问题了...

有这个想法，无从下手阿

connet

集中增删？还是数组快。
增删结束后移出所有空位即可。不要增/删一个就马上已空位。
也适合需要排序的情况。

net_robber

对数组申请的部分空间进行释放，在C/C++的级别上好像做不到吧？？？

等牛人解答

运算符重载可以解决你的问题，

单纯的用C，而且还想使用[]运算符也可以
你试一下，在数组里面存放地址，地址指向你要的数据结构体

然后一个1000000个地址元素的数组对于现在的机器来说，大概内存消耗不掉太多吧？？？？？？？


当然如果你要求善待内存，虐待时间的话，可以考虑过一会儿这里一下你的数组

思一克

用DB不行吗。