1

2 つの構造体を作成しました。

typedef struct mainNode {
    int theNode;
    int visited;
    struct mainNode *next;
} node_rec, *node_ptr;

と

typedef struct neighborNode {
    struct neighborNode *next;
} neighbor_node_rec, *neighbor_node_ptr;

リストに挿入する必要があるもの:

void insert(node_ptr head, int theNodeVal, int neighborNodeVal, int weight) {

//if list is empty
if (head == NULL) {
    head = (node_ptr) malloc(sizeof (node_rec)); //create head of list
    head->theNode = theNodeVal; //set head value to node value
    head->next = NULL; //point to null       
}

//while list is not pointing no null
while (head != NULL) {
    //if node IS NOT equal to node value   
    if (head->theNode != theNodeVal) {
        head->theNode = theNodeVal; //set head value (new node) to node value
        head->next = tail; //connect to next node
        tail->next = NULL; //point to null
    }
    else
    {          
        //if node IS equal to node value (the node already exists)
        tail->next = head // head is the new tail
        head->neighbor = n; //point at the neighbor of head (new tail)
    }
}
}

実装したロジックが正しいかどうかを確認しようとしています。それが私がすべての行にコメントした理由です。ビジュアルについては、ページ上部のリンクを参照できます。

4

1 に答える 1

2

if (head->theNode = theNodeVal) {を に置き換え if (head->theNode == theNodeVal) {ます。それが役立つだろう？

これは、このアルゴリズムのグラフを実装する方法です。

#include <limits.h>
#include <string.h>
#include <malloc.h>
#include <stdio.h>

struct Vertex {
    struct Vertex *next; // The reference to the next vertex in the global list of vertices
    int nodeId;
    int distance;
    struct Vertex *previous; // The reference to trace back the shortest path;
    struct Edge *neighbor; // The reference to the list of edges of this 
};

struct Edge {
    struct Edge *next;   // The reference to the next edge of this vertex;
    struct Vertex *node; // The reference to the vertex at other end of this edge;
    int weight;
};


struct Vertex *head = NULL;

struct Vertex *newVertex(int nodeId) {
    struct Vertex *p = malloc(sizeof(struct Vertex));
    memset(p,0,sizeof(struct Vertex));
    p->nodeId = nodeId;
    p->distance=INT_MAX;
    p->next = head;
    head = p;
    return p;
}

void addEdge(struct Vertex *v1, struct Vertex *v2, int weight) {
    struct Edge *e = malloc(sizeof(struct Edge));
    e->next = v1->neighbor;
    v1->neighbor = e;
    e->node = v2;
    e->weight = weight;
}

void insert(int node1, int node2, int weight) {
    struct Vertex *current = head, *p1 = NULL, *p2 = NULL;

    while (current != NULL) {
        if (current->nodeId == node1) p1 = current;
        if (current->nodeId == node2) p2 = current;
        current = current->next;
    }

    if (p1 == NULL) p1 = newVertex(node1);
    if (p2 == NULL) p2 = newVertex(node2);

    addEdge(p1,p2,weight);
    addEdge(p2,p1,weight);
}

void main(int argc, char **argv) {
    int node1, node2, weight;
    while (EOF != scanf("%d %d %d \n", &node1, &node2, &weight)) {
        insert(node1, node2, weight);
    }
}
于 2012-10-21T04:44:04.823 に答える