c - 使用字符串邻接列表的图

Question

我知道如何使用邻接表来表示整数图。然而，对于字符串来说，这有点棘手。我正在尝试创建一个 friend 图。其中源位于指针数组的索引处。然后使用链表(如散列)添加源的好友现在我创建了一个指针数组，与使用索引作为图形值的整数程序不同，我无法使用字符串列表来做到这一点。

指针数组存储初始字符串

请查看它，任何解决方案都会很棒

// A C Program to demonstrate adjacency list 
// representation of graphs
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include  <string.h>
#include <string>

#define maxNode 4
int i;
int z;
typedef struct Node
{
    char vertexString[10];
    struct Node *next;
}Node;

Node *dest, *tmp;
typedef struct List
{
    Node*head;
    char vertexS[10];
    struct Node *next;
}List;

List*adjlist[maxNode] = { 0 };

void addNode(const char s[10], const char d[10]);
void printList();

int main()
{
        int i;
        for (i = 0; i < maxNode; i++)
        {
            adjlist[i] = (List *)malloc(sizeof(List));
            adjlist[i]->head = NULL;
        }
        addNode("Alam", "Shaib");
        addNode("ZEE", "PEE");
        addNode("ALOO", ",ALOO");

        printList();
        _getch();
}


void addNode(const char s[10],const char d[10])
{
        for (i = 0; i < 4;i++);
        {
            if (adjlist[i]->vertexS == s)
            {
                dest = (Node *)malloc(sizeof(Node));

                for (int j = 0; j < 10; j++)
                {
                    dest->vertexString[j] = d[j];
                }
                dest->next = NULL;

                tmp = adjlist[i]->head;
                while (tmp->next != NULL)
                    tmp = tmp->next;
                tmp->next = dest;
            }
        }

        for (z = 0; z < 4; z++);
        {
            if (adjlist[z] == 0)
            {
                dest = (Node *)malloc(sizeof(Node));
                for (int L = 0; L < 10; L++)
                {
                    dest->vertexString[L] = d[L];
                }
                dest->next = NULL;

                tmp = adjlist[z]->head;
                while (tmp->next != NULL)
                    tmp = tmp->next;
                tmp->next = dest;
            }
        }
    }

    void printList()
    {
        int i;
        for (i = 0; i < maxNode; i++)
        {
            Node *p;
            p = adjlist[i]->head;
            printf("Adjency list for vertex %s\n", adjlist[i]->vertexS);
            p = p->next;
            while (p)
            {
                printf("%s",p->vertexString);
                p = p->next;
            }

            printf("\n");
        }
    }

Answer 1

无需复制邻接列表中的数据，只需包含对描述节点的结构的引用(数组索引或指针)即可。

例如，假设您使用链表描述节点

typedef  struct node_list  node_list;
struct node_list {
    struct node_list *next;
    size_t            len;
    size_t            flag; /* Not usually needed, but sometimes useful */
    char              data[]; /* C99 flexible array member */
};

要查找现有节点或添加新节点，您可以使用

node_list *node_list_node(node_list **rootptr, const char *name)
{
    const size_t  namelen = (name) ? strlen(name) : 0;
    node_list   **prev = rootptr, *curr;

    if (!rootptr)
        return NULL;  /* Error: No reference to node list root! */
    if (namelen < 1)
        return NULL;  /* Error: Empty name! */ 

    while ((curr = *prev))
        if (curr->len == namelen && !memcmp(curr->data, name, namelen))
            return curr;
        else
            prev = &(curr->next);

    curr = malloc(sizeof (node_list) + name_len + 1);        
    if (!curr)
        return NULL; /* Not enough memory */

    curr->next = NULL;
    curr->len  = namelen;
    memcpy(curr->data, name, namelen + 1);

    *prev = curr;

    return curr;
}

然后，您可以将图形边缘定义为另一个链接列表，例如

typedef  struct adjacency_list  adjacency_list;
struct adjacency_list {
    struct adjacency_list  *next;
    struct node_list       *edge_from;
    struct node_list       *edge_to;
};

这样添加一条边(不检查重复项)就像这样简单

adjacency_list *add_edge(node_list **node, adjacency_list **edge,
                         const char *from, const char *to)
{
    node_list      *node_from, *node_to;
    adjacency_list *newedge;

    if (!node || !edge || !from || !*from || !to || !*to)
        return NULL;

    node_from = node_list_node(node, from);
    node_to   = node_list_node(node, to);
    if (!node_from || !node_to)
        return NULL;

    newedge = malloc(sizeof (adjacency_list));
    if (!newedge)
        return NULL;

    newedge->edge_from = node_from;
    newedge->edge_to   = node_to;

    /* Prepend to the existing adjacency list. */
    newedge->next = *edge;
    *edge = newedge;

    return newedge;
}

当然，您必须注意不要重新分配或释放 node_list如果它被任何 adjacency_list 引用对象，因为重新分配可能会移动对象。 (话又说回来，您可以通过检查所有对象来调整 adjacency_list 对象，但如果您认为可以这样做，通常最好使用指针数组而不是链表，并使用数组索引而不是指针本身来引用每个节点。)

如果您想输出 adjacency_list 描述的(子)图链表，Graphviz Dot格式，但只输出列表中包含的节点，即flag node_list 中的成员结构派上用场。例如:

void fgraph(FILE *out, adjacency_list *edges)
{
    adjacency_list *curredge;

    if (!out)
        return;

    /* First, clear the 'flag' field in all referred to nodes.
       (We actually only need one bit, though.) */
    for (curredge = edges; curredge != NULL; curredge = curredge->next) {
         curredge->edge_from->flag = 0;
         curredge->edge_to->flag = 0;
    }

    /* Print a directed graph DOT preamble. */
    fprintf(out, "digraph {\n");

    /* Print each referred to node, but only once. */
    for (curredge = edges; curredge != NULL; curredge = curredge->next) {
        if (!curredge->edge_from->flag) {
            node_list *currnode = curredge->edge_from;

            currnode->flag = 1;
            fprintf(out, "    \"%p\" [ label=\"%s\" ];\n",
                         (void *)currnode, currnode->data);
        }
        if (!curredge->edge_to->flag) {
            node_list *currnode = curredge->edge_to;

            currnode->flag = 1;
            fprintf(out, "    \"%p\" [ label=\"%s\" ];\n",
                         (void *)currnode, currnode->data);
        }
    }

    /* Print each edge in the (sub)graph. */
    for (curredge = edges; curredge != NULL; curredge = curredge->next) {
        fprintf(out, "    \"%p\" -> \"%p\";\n",
                     (void *)(curredge->edge_from),
                     (void *)(curredge->edge_to));
    }

    /* Done. */
    fprintf(out, "}\n");
}

然后您可以使用 Graphviz 工具，例如 dot , twopi ，或circo创建图表的图像。