grcreatl.cpp

来自「经典c++程序的实现」· C++ 代码 · 共 90 行

// Create a graph -- Adjacency list
#include <stdio.h>
#include <iostream.h>
#include <assert.h>
#include <stdlib.h>
#include <ctype.h>

#include "..\..\include\book.h"

#define LINELEN 80

#include "..\..\include\grlist.h"

char* getl(char* buffer, int n, FILE* fid) {
  char* ptr;
  ptr = fgets(buffer, n, fid);
  while ((ptr != NULL) && (buffer[0] == '#'))
    ptr = fgets(buffer, n, fid);
  return ptr;
}

// Create a graph from file
bool createGraph(Graph& G, FILE* fid) {
  char buffer[LINELEN+1]; // Line buffer for reading
  bool undirected;  // TRUE if graph is undirected, FALSE if directed
  int i;
  int v1, v2, weight;
  Edge curr;

  if (getl(buffer, LINELEN, fid) == NULL) // Unable to get number of vertices
{ cout << "Unable to read number of vertices\n";
    return FALSE;
}
  G.numVertex = atoi(buffer);
  if (getl(buffer, LINELEN, fid) == NULL) // Unable to get graph type
{ cout << "Unable to read graph type\n";
    return FALSE ;
}
  if (buffer[0] == 'U')
    undirected = TRUE;
  else if (buffer[0] == 'D')
    undirected = FALSE;
  else {
    cout << "Bad graph type: |" << buffer << "|\n";
    return FALSE;
  }

  // Create space
  G.Mark = new bool[G.n()];
  G.list = new Edge [G.n()];
  for (i=0; i< G.n(); i++) // Initialize matrix
    G.list[i] = NULL;

  // Read in edges
  G.numEdge = 0;
  while (getl(buffer, LINELEN, fid) != NULL) {
    v1 = atoi(buffer);
    i = 0;
    while (isdigit(buffer[i])) i++;
    while (buffer[i] == ' ') i++;
    v2 = atoi(&buffer[i]);
    while (isdigit(buffer[i])) i++;
    if (buffer[i] == ' ') { // There is a weight
      while (buffer[i] == ' ') i++;
      weight = atoi(&buffer[i]);
    }
    else weight = 1;
    // Put the edge on the list
    G.numEdge++;
    if (((curr = G.list[v1]) == NULL) || (v2 < curr->v2))
      G.list[v1] = new EdgeLink(v1, v2, weight, curr);
    else {
      while ((curr->next != NULL) && (curr->next->v2 < v2))
         curr = curr-> next;
      curr->next = new EdgeLink(v1, v2, weight, curr->next);
    }
    if (undirected) {// Put in edge in other direction
      G.numEdge++;
      if (((curr = G.list[v2]) == NULL) || (v1 < curr->v2))
        G.list[v2] = new EdgeLink(v2, v1, weight, curr);
      else {
        while ((curr->next != NULL) && (curr->next->v2 < v1))
           curr = curr-> next;
        curr->next = new EdgeLink(v2, v1, weight, curr->next);
      }
    }
  }
  return TRUE;
}