0

我使用 ncurses 启动了一个实验性代码编辑器。我正在使用双链表来存储/解析/打印文本。尽管我对实现还很了解，但我还没有完全确定使用双链表是否是最好的主意（而不是使用数组）。

请注意，当我指的是数组时，我指的是每行字符的数组——而不是单个线性数组。

以下是我权衡利弊的方法：

双链表：

  • 更快的字符和行插入
  • 更快的代码折叠

数组：

  • 使用更少的内存
  • 更快的解析
  • 打印速度更快 我使用链表是否正确？或者，它们是更好的方法吗？

笔记：

数组的打印速度更快，因为只需一次调用即可printw打印一整行。printw而不是按字符调用。

4

1 回答 1

1

将评论转移到答案中，因为没有其他人参与进来。

为什么不使用（双向链接）字符串列表，其中列表中的每个项目都是一行，因此您可以printw()像使用数组一样每行调用一次？您还将大大减少存储需求；在 64 位机器上，单个字符的双向链表可能每个字符使用 24 个字节，这是相当高的开销。

我实际上才开始这样做。这似乎是一个相当不错的妥协（我有一种预感，那就是 nano 使用的东西）。我可能会删除这个问题，因为我认为这是我将使用的解决方案。realloc()此外，在每次插入/移除时使用是不是一个坏主意？

我可能会按照以下方式设计列表节点：

struct Line
{
    struct Line *next;
    struct Line *prev;
    char        *line;
    size_t       line_len;
    size_t       line_max;
};

line_len记录当前行长度，并记录line_max分配的空间。

realloc()当角色被删除时，我不会打电话；除非实际大小和最大大小之间存在相当大的（256 字节？）差异，否则我可能不会这样做。

对于插入，我只会在不再有空间时重新分配（当line_len == line_max，但要小心一个一个），并且我会以至少 16 个字符的增量分配（因为这可能是malloc()et al 实际分配的最小数量, 加上当用户插入一个字符时，他们通常会插入几个）。因此，您希望避免每个字符更改内存分配（调用realloc()），而不必害怕在必要时重新分配。

于 2013-06-19T16:41:03.130 回答