C中的哪个数据结构允许我轻松存储行和追加行？

Question

我得到了一个字符串数据列表.10,20,30是行号

10. string 1
20. string 2
30. string 3

如果用户输入"23字符串数据".23是用户想要插入的行号.数据应该变成这样

10. string 1
20. string 2
23. string data
30. string 3

如果用户输入"40字符串数据".数据应该变成这样

10. string 1
20. string 2
23. string data
30. string 3
40. string data

我在C的数据结构方面相对较新.我应该使用哪种数据结构来有效地存储这种数据？我目前的方向是实现动态数组或链表.但是,下面列出了我遇到的问题.

动态数组的问题:

1. 使用行号作为索引并创建足够的空间以确保数组长度始终大于或等于最高行号.为未使用的索引浪费了大量内存.
2. 打印出数据将是一个问题.例如.索引0-9没有分配内存.访问它将导致错误.需要找到方法来了解使用哪个索引？

链表问题:

1. 我不能跳索引(不确定).如何确定哪一条线路在另一条线路之间并在两者之间轻松插入线路？

Answer 1

我将给出我能想到的两个解决方案，但这个问题可能是开放式的。

1. 使用哈希表。键是行号。值为(string, pointer to next line's value). 这使得随机和线性访问都变得更快。编辑：插入仍然O(n)如此。它只会有助于缩短访问时间，即O(1). 第二种解决方案有O(1)插入。

2. 假设您没有间隔很大的行号：使用单链表L来存储字符串。还创建一个单独的数组，其中包含指向列表中P每个第一个节点的指针。k要访问 line i，请检查P[floor(i/k)]，跳转到它指向的节点 in L，然后向前跳转i mod k几次以到达您的字符串。因此访问时间为O(k)。插入时间为O(1). n字符串的空间使用量为O(n + max{i}/k)。

与 C 相关的一件事是……当然，没有内置哈希表！所以#2 可能更容易实现。