插入/更新到稀疏数组的一般想法是仅在到达较大位置的节点时才添加节点。当然，您需要前一个节点指针来执行此操作，因此在您找到放置数据的位置时，请继续进行扫描。
还有一些注意事项：
- 不要
malloc()在 C 程序中强制转换。
- 我将列表清理作为一项任务留给您。
- 如果给定的位置已经在列表中，这将更新现有节点。如果你想将一个节点推到那个位置并增加它之后的元素直到找到一个间隙，那是相当多的工作。然而，这是可行的。
接着就，随即。干得好。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct node* createNode(int,int);
struct node {
int data, posi;
struct node *next;
};
struct node *head = NULL;
struct node *tail = NULL;
struct node * createNode(int data, int pos)
{
struct node *ptr = malloc(sizeof(*ptr));
ptr->data = data;
ptr->posi = pos;
ptr->next = NULL;
return ptr;
}
void insertAtPos(int pos, int data)
{
struct node *ptr = head, *prev = NULL;
while (ptr && ptr->posi < pos)
{
prev = ptr;
ptr = ptr->next;
}
// make sure we have a node.
if (ptr)
{
// Case 1: update existing element.
if (ptr->posi == pos)
{
// update in place
ptr->data = data;
}
// Case 2: insert new element
else if (prev)
{
prev->next = createNode(data, pos);
prev->next->next = ptr;
}
// Case 3: new list head.
else
{
head = createNode(data, pos);
head->next = ptr;
}
}
else if (prev)
{
// means we hit the end of the list.
prev->next = createNode(data, pos);
}
else
{ // means empty list. new head.
head = createNode(data, pos);
}
}
void print()
{
struct node *p = head;
while (p)
{
printf("list[%d] = %d\n", p->posi, p->data);
p = p->next;
}
printf("\n");
}
int main()
{
int i = 0;
srand((unsigned)time(NULL));
// fill our list with some elements
for (i=0;i<10;++i)
insertAtPos(rand() % 20 + 1, rand() % 100);
print();
// add or update element
insertAtPos(15, 100000);
print();
// update element at location 20;
insertAtPos(15, 200000);
print();
// prove we can add an element at beginning of list
insertAtPos(0, 1000);
print();
// prove we can add an element at end of list
insertAtPos(100, 2000);
print();
return 0;
}
输出（随机）
list[3] = 86
list[5] = 10
list[9] = 63
list[12] = 86
list[14] = 93
list[19] = 86
list[20] = 49
list[3] = 86
list[5] = 10
list[9] = 63
list[12] = 86
list[14] = 93
list[15] = 100000
list[19] = 86
list[20] = 49
list[3] = 86
list[5] = 10
list[9] = 63
list[12] = 86
list[14] = 93
list[15] = 200000
list[19] = 86
list[20] = 49
list[0] = 1000
list[3] = 86
list[5] = 10
list[9] = 63
list[12] = 86
list[14] = 93
list[15] = 200000
list[19] = 86
list[20] = 49
list[0] = 1000
list[3] = 86
list[5] = 10
list[9] = 63
list[12] = 86
list[14] = 93
list[15] = 200000
list[19] = 86
list[20] = 49
list[100] = 2000
编辑关于如何完成插入的请求。
将新项目滑入给定索引可能需要在其之后更新现有索引。前提是以下内容应该构建一个具有升序posi值的列表：
int main()
{
int i = 0;
srand((unsigned)time(NULL));
// fill our list with some elements
for (i=0;i<10;++i)
insertAtPos(0, rand() % 100);
print();
return 0;
}
注意我们插入的索引。它始终为零。之前的版本insertAtPos()会简单地重复替换现有值，我们会以单个节点 ( posi = 0) 的列表结束。为了滑动一个值并相应地调整列表，我们应该有一个完美的 0..9 值序列posi。这可以按如下方式完成：
void insertAtPos(int pos, int data)
{
// same as before. find the right slot
struct node *ptr = head, *prev = NULL;
while (ptr && ptr->posi < pos)
{
prev = ptr;
ptr = ptr->next;
}
if (prev)
{
// slip new node in.
prev->next = createNode(data, pos);
prev->next->next = ptr;
}
else
{ // no prev means this goes to the head of the list.
head = createNode(data, pos);
head->next = ptr;
}
// it is possible the new node has the same
// index as its successor. to account for this
// we must walk successor nodes, incrementing
// their posi values until a gap is found (or
// end of list).
while (ptr && (ptr->posi == pos++))
{
ptr->posi++;
ptr = ptr->next;
}
}
运行上述main()..
list[0] = 90
list[1] = 34
list[2] = 45
list[3] = 27
list[4] = 45
list[5] = 88
list[6] = 75
list[7] = 50
list[8] = 68
list[9] = 41
当然，您的值会因rand(). 与两个插入循环略有不同main()，一个总是在 slot-0 插入，另一个总是在 slot-4 插入。
int main()
{
int i = 0;
srand((unsigned)time(NULL));
// fill our list with some elements
for (i=0;i<5;++i)
insertAtPos(0, rand() % 100);
print();
for (i=0;i<5;++i)
insertAtPos(4, rand() % 100);
print();
return 0;
}
应该导致相同的索引，但明显不同的值（同样，它毕竟是 `rand()）。
list[0] = 74
list[1] = 35
list[2] = 72
list[3] = 22
list[4] = 0
list[0] = 74
list[1] = 35
list[2] = 72
list[3] = 22
list[4] = 40
list[5] = 38
list[6] = 31
list[7] = 57
list[8] = 42
list[9] = 0
请注意该0值是如何一直推到列表末尾的。它在 4-index 中，因此每次插入都会“下推”，就像我们一个接一个插入的每个数字一样。
最后，为了证明这仅在检测到间隙之前正确调整索引，请考虑以下内容：
int main()
{
int i = 0;
srand((unsigned)time(NULL));
// fill our list with some elements
for (i=0;i<10;i+=2)
insertAtPos(i, rand() % 100);
print();
for (i=0;i<2;++i)
insertAtPos(3, rand() % 100);
print();
return 0;
}
这应该最初在索引 0,2,4,6,8 中插入值，然后在插槽“3”处插入两个值。第一次插入应该给我们索引 0,2,3,4,6,8。第二次插入应该给我们索引 0,2,3,4,5,6,8。
list[0] = 22
list[2] = 3
list[4] = 91
list[6] = 15
list[8] = 68
list[0] = 22
list[2] = 3
list[3] = 94
list[4] = 48
list[5] = 91
list[6] = 15
list[8] = 68
正如预期的那样。