以下情况查找数据用什么数据结构比较高效呢？
1、先说一个简单的情况：假设一群学生的学号范围是1-3000，想要记录或者查询每个人的成绩的话，主需要建立一个uint16score的数组就行
2、问题来了：
如果学号范围是1-65535，并且一个班一共3000人，每个学生的学号都是1-65535中随机且唯一的数值。这样要随时记录并且查找的话，用uint16score显然不合适，首先占用太大的ram，其次很多数组元素根本用不到。
请问有什么合适的数据结构能做到随时读写对应学号学生的成绩？
欢迎大家一起讨论 你内存足够大就不用管了。多占点内存换更少的编码时间和运行时间，何乐而不为呢? wye11083 发表于 2018-8-14 00:01
你内存足够大就不用管了。多占点内存换更少的编码时间和运行时间，何乐而不为呢? ...
mcu一共才多少ram哦，又不是pc有好几个g的内存 这个应该没办法吧？用结构至少要有学号跟成绩，合起来就快比直接存用的内存多了 使用链表，用到一个就malloc一个，并添加到链表中 支持C++不？支持的话，最简单就是std::map
不支持的话，自己造一个map，或者两个数组：一个常量数组存放学号（不占用RAM）另一个记录成绩。
使用map速度快，学号排完序二分法查找学号最多只需要查找13次，但是占用RAM多出1倍；使用两个数组查找学号最多需要3000次，占用CPU。 wistarky 发表于 2018-8-14 01:36
这个应该没办法吧？用结构至少要有学号跟成绩，合起来就快比直接存用的内存多了 ...
办法肯定有的，只是看时间和空间怎么妥协了 undead 发表于 2018-8-14 03:32
使用链表，用到一个就malloc一个，并添加到链表中
查询某个学号对应的成绩会比较慢哎，比如存了n个学生，正好被查询学生的学号是链表尾巴，需要查询n次 takashiki 发表于 2018-8-14 06:18
支持C++不？支持的话，最简单就是std::map
不支持的话，自己造一个map，或者两个数组：一个常量数组存放学 ...
您说的这个map是哈希表吗？ 按6楼的补充如下，结合上面两种方案：
做成两个表，一个放学号的常量数组，预先排序好。另一个放成绩。使用时首先查找学号所在的位置，二分法最多查找13次，然后修改成绩表。
当然最简单方便的还是std::map，本来就是他该干的事情。std::map<uint16_t, uint16_t> Students; 读写30342号学生的成绩就是这样：Students = 成绩; 成绩 = Students; 没有用到的学号不占空间的 tim4146 发表于 2018-8-14 06:57
您说的这个map是哈希表吗？
大概不是吧……你就认为是吧，反正这些数据结构都差不多，我的原则能用好用就行了，懒得去纠结叫啥名称。C++的动态数组叫vector，array是静态的，找谁说理去。 takashiki 发表于 2018-8-14 07:16
大概不是吧……你就认为是吧，反正这些数据结构都差不多，我的原则能用好用就行了，懒得去纠结叫啥名称。 ...
stl map不是哈希表，而是红黑树。完全两码事。当然都可以做为查找用的数据结构。
如果不想用c++只用c，请找别人写好的红黑树的库，别自己写，很少有人能写对的。
按学号从小到大存放，然后用二分法查找 本帖最后由 think_a_second 于 2021-2-25 16:31 编辑
纯C的情况下，小内存而追求效率时，同时使用链表和红黑树
1. 使用链表，方便增加、删除
2. 红黑树，用于查找，算法复杂度就跟排序后的二分法一样 think_a_second 发表于 2021-2-25 16:11
纯C的情况下，小内存而追求效率时，同时使用链表和红黑树
1. 使用链表，方便增加、删除
2. 红黑树，用于查 ...
https://www.amobbs.com/thread-5716767-1-1.html
看了这个帖子，只用红黑树就可以了 二维数组，一纬学号，一纬成绩
页:
[1]