CODEWITHSUNDEEP
carrayslistarraylistlinked-list
Tsema Alexander
Tsema Alexander

Reputation: 13

How to permute(shuffle) dynamic/linked list in C

I use this data structure to store a graph:

struct Vertex
{
    struct Line *a;
    struct Line *b;
    int X;
    int Y;
    struct Vertex *next;
    struct Edge *edges;
    int edgeCount;
};
struct Edge
{
   struct Vertex *dst;
   struct Vertex *src;
   struct Edge *next;
   float weight;
   bool included;
   bool visited;
};

I generate a linked list of vertices(the list is my graph) in a loop:

struct Edge *edge= malloc(sizeof(struct Edge));
////here I add edge's data
if(graph->edges == NULL)
{
    graph->edges = edge;
}
else
{
    edge->next = graph->edges;
}

And now I need to permute resulting array. It is simple with common array of integers:

void swap(int a, int b)
{
   int temp = a;
   a = b;
   b = temp;
}

void permutation(int* randomArray, int numIndex)
{
  for (i = 0; i < numIndex; i++)
  {
    int randomOffset = rand() % (numIndex - i);
    swap(randomArray[i], randomArray[i+randomOffset]);
  }
}

But how to do the same with linked list?

Upvotes: 1

Views: 108

Answers (1)

D&#233;j&#224; vu
D&#233;j&#224; vu

Reputation: 28830

Create an array of struct Edge * that contains all edges, built when the linked list is created, permute that array, rebuild the linked list.

The variables

struct Edge *pedges[MAXEDGES]; // or allocate dynamically (see below)
int nedges = 0;

then when list is created

struct Edge *edge= malloc(sizeof(struct Edge)); // your code
pedges[nedges++] = edge;

permutations are done the same way

void permuteEdges(struct Edge *pe, int ne) {
   int i;
   for (i = 0 ; i < ne ; i++) {
      int randomOffset = rand() % (ne - i);
      swap(pe[i], pe[i+randomOffset]);
   }
}

finally, rebuild the linked list

for (i = 0 ; i < ne ; i++) {
   if ( ! i) {
      graph->edges = pe[i];
   }
   else {
      pe[i-1]->next = pe[i];
   }
}

ensure the last item next property points to NULL

pe[ne-1]->next = NULL;

Note that you could allocate pedges dynamically (to be freed after use). For instance if you use the array for a single shuffle, there is no need to keep that amount of memory in the heap.

Dynamic allocation

struct Edge *pedges = malloc(MAXEDGES * sizeof(*pedges));

...use it...

free(pedges);

Upvotes: 1

Related Questions