https://stackoverflow.com/questions/19074816
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianThe general idea of insertion/updating into a sparse array is to only add nodes when you arrive at a node at a larger position. Of course, you need the previous node pointer to do that, so keep one hopping along for the scan while you find where to put your data.
And some notes:
- Don't cast
malloc()in C programs. - I left the list cleanup as a task for you.
- This updates an existing node if the position given is already in the list. if you want to shove a node into that position and increment the elements after it until a gap is found, that is considerably more work. It is doable, however.
With that. here you go.
#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;
}
Output (Random)
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
EDIT Request for how shove-in insertion is done.
To slip a new item into a given index potentially requires updating existing indexes after it. The premise is that the following should build a list with ascending posi values:
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;
}
Note the index we're inserting with. It is always zero. The prior version of insertAtPos() would simply replace the existing value repeatedly and we would end with a list of a single node (posi = 0). To slip a value and adjust the list accordingly we should instead have a perfect sequence of 0..9 values for posi. This can be done as follows:
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;
}
}
Run with the aforementioned 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
And of course, your values will vary due to the nature of rand(). A slightly different main() with two loops of insertion, one that always inserts at slot-0, the other that always inserts at 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;
}
Should result in identical indexing, but obviously different values (again, it is `rand(), after all).
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
Note how the 0 value was shoved all the way through to the end of the list. It was in the 4-index so it was "pushed" down with each insertion, as was each number we inserted one after another.
Finally, to prove this properly only adjusts the indexing until a detected gap, consider this:
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;
}
This should insert values in indexes 0,2,4,6,8 initially, then insert two values at slot "3". The first insertion should give us indexes 0,2,3,4,6,8. The second insertion should give us indexes 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
As expected.
