以下情况查找数据用什么数据结构比较高效呢？

tim4146 · 发表于 2018-8-13 23:29:52

1、先说一个简单的情况：
假设一群学生的学号范围是1-3000，想要记录或者查询每个人的成绩的话，主需要建立一个uint16 score[3001]的数组就行
2、问题来了：
如果学号范围是1-65535，并且一个班一共3000人，每个学生的学号都是1-65535中随机且唯一的数值。这样要随时记录并且查找的话，用uint16 score[65535]显然不合适，首先占用太大的ram，其次很多数组元素根本用不到。
请问有什么合适的数据结构能做到随时读写对应学号学生的成绩？
欢迎大家一起讨论

wye11083 · 发表于 2018-8-14 00:01:55

你内存足够大就不用管了。多占点内存换更少的编码时间和运行时间，何乐而不为呢?

tim4146 · 发表于 2018-8-14 00:53:49

wye11083 发表于 2018-8-14 00:01
你内存足够大就不用管了。多占点内存换更少的编码时间和运行时间，何乐而不为呢? ...

mcu一共才多少ram哦，又不是pc有好几个g的内存

wistarky · 发表于 2018-8-14 01:36:38

这个应该没办法吧？用结构至少要有学号跟成绩，合起来就快比直接存用的内存多了

undead · 发表于 2018-8-14 03:32:22

使用链表，用到一个就malloc一个，并添加到链表中

takashiki · 发表于 2018-8-14 06:18:23

支持C++不？支持的话，最简单就是std::map
不支持的话，自己造一个map，或者两个数组：一个常量数组存放学号（不占用RAM）另一个记录成绩。
使用map速度快，学号排完序二分法查找学号最多只需要查找13次，但是占用RAM多出1倍；使用两个数组查找学号最多需要3000次，占用CPU。

tim4146 · 发表于 2018-8-14 06:54:28

wistarky 发表于 2018-8-14 01:36
这个应该没办法吧？用结构至少要有学号跟成绩，合起来就快比直接存用的内存多了 ...

办法肯定有的，只是看时间和空间怎么妥协了

tim4146 · 发表于 2018-8-14 06:56:32

undead 发表于 2018-8-14 03:32
使用链表，用到一个就malloc一个，并添加到链表中

查询某个学号对应的成绩会比较慢哎，比如存了n个学生，正好被查询学生的学号是链表尾巴，需要查询n次

tim4146 · 发表于 2018-8-14 06:57:06

takashiki 发表于 2018-8-14 06:18
支持C++不？支持的话，最简单就是std::map
不支持的话，自己造一个map，或者两个数组：一个常量数组存放学 ...

您说的这个map是哈希表吗？

takashiki · 发表于 2018-8-14 07:03:32

按6楼的补充如下，结合上面两种方案：
做成两个表，一个放学号的常量数组，预先排序好。另一个放成绩。使用时首先查找学号所在的位置，二分法最多查找13次，然后修改成绩表。
当然最简单方便的还是std::map，本来就是他该干的事情。std::map<uint16_t, uint16_t> Students; 读写30342号学生的成绩就是这样：Students[30342] = 成绩; 成绩 = Students[30342]; 没有用到的学号不占空间的

takashiki · 发表于 2018-8-14 07:16:10

tim4146 发表于 2018-8-14 06:57
您说的这个map是哈希表吗？

大概不是吧……你就认为是吧，反正这些数据结构都差不多，我的原则能用好用就行了，懒得去纠结叫啥名称。C++的动态数组叫vector，array是静态的，找谁说理去。

redroof · 发表于 2018-8-14 08:14:18

takashiki 发表于 2018-8-14 07:16
大概不是吧……你就认为是吧，反正这些数据结构都差不多，我的原则能用好用就行了，懒得去纠结叫啥名称。 ...

stl map不是哈希表，而是红黑树。完全两码事。当然都可以做为查找用的数据结构。
如果不想用c++只用c，请找别人写好的红黑树的库，别自己写，很少有人能写对的。

lcw_swust · 发表于 2018-8-14 08:45:24

按学号从小到大存放，然后用二分法查找

think_a_second · 发表于 2021-2-25 16:11:18

本帖最后由 think_a_second 于 2021-2-25 16:31 编辑

纯C的情况下，小内存而追求效率时，同时使用链表和红黑树
1. 使用链表，方便增加、删除
2. 红黑树，用于查找，算法复杂度就跟排序后的二分法一样

think_a_second · 发表于 2021-2-25 22:00:36

think_a_second 发表于 2021-2-25 16:11
纯C的情况下，小内存而追求效率时，同时使用链表和红黑树
1. 使用链表，方便增加、删除
2. 红黑树，用于查 ...

https://www.amobbs.com/thread-5716767-1-1.html
看了这个帖子，只用红黑树就可以了

zchong · 发表于 2021-2-26 16:31:29

二维数组，一纬学号，一纬成绩

以下情况查找数据用什么数据结构比较高效呢？

阿莫论坛20周年了！感谢大家的支持与爱护！！