c - 如何在 C 中置换(洗牌)动态/链表

Question

我使用这个数据结构来存储一个图:

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;
};

我在循环中生成一个顶点链接列表(该列表是我的图):

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;
}

现在我需要置换结果数组。常见的整数数组很简单:

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]);
  }
}

但是如何对链表做同样的事情呢？

Answer 1

创建一个包含所有边的 struct Edge * 数组，在创建链表时构建，置换该数组，重建链表。

变量

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

然后当创建列表时

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

排列以同样的方式完成

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]);
   }
}

最后，重建链表

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

确保最后一项 next 属性指向 NULL

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

---

请注意，您可以动态分配pedges(使用后释放)。例如，如果您将数组用于单次随机播放，则无需在堆中保留该数量的内存。

动态分配

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

...use it...

free(pedges);