data-structures - 数据结构对嵌入式软件工程师的重要性

Question

我是一名嵌入式软件工程师。我从来没有使用过像树、图或链表这样的数据结构。我只使用了循环缓冲区、数组等。我很想知道嵌入式系统数据结构的哪一部分是显式使用的树、图和链表。有没有具体的例子？

Answer 1

您使用的数据结构与您的软件在哪里运行（即微控制器与 PC）几乎没有关系。它更多地与您的软件正在做什么有关。

您在快餐店看到的触摸屏收银机可能完全在微控制器上运行。或者它可能是一个 Windows 应用程序（我以前在麦当劳看到过蓝屏）。

话虽如此，诸如树和图形之类的结构通常用于机器人技术中来规划路线并记住它们去过的地方。3D 打印机广泛使用这些结构，并且通常在嵌入式环境中运行。PC 将创建要打印的对象切片的各种图形，然后将它们放在树中。然后打印机中的微控制器遍历树并打印图形。

链表可以用在与循环缓冲区或数组（或堆栈或队列）类似的地方，在这些地方需要更多的灵活性。我经常看到它们用于任务调度算法。它们也可以用于上述树和图表。

Answer 2

您必须了解每个特定的数据结构有什么好处——即每个特定的数据存储、组织或访问问题都旨在解决什么问题。一旦您了解对于一些常见数据结构的选择，您将有能力识别可能被利用的情况。

由于缺乏知识或经验，或者由于次优解决方案的可接受性和简单性，您可能已经使用次优数据结构实现了系统。例如，如果一个简单数组的详尽搜索满足性能要求；因为要么数组足够小，处理器足够快，或者实时要求足够宽松，那么您可能会合理地选择不使用更适合高效和确定性搜索的数据结构使事情复杂化。尤其是因为调试器擅长显示数组内容，但通常不知道更高级别的数据结构。

另一方面，您可能使用了其他数据结构而不是您提到的那些数据结构，而您可能没有意识到这一点。堆栈（FILO）和队列（FIFO）在许多嵌入式系统中很普遍，如果您没有使用它们，我会感到惊讶，即使它们是基于数组的临时实现。