人在德国社区 - Powered by Discuz! Board

标题: 这里有没有编程高手阿？ [打印本页]

作者: chanel0388la 时间: 2006-4-17 22:26 标题: 这里有没有编程高手阿？

c++编程,小妹做作业中,有问题请教!谢谢谢谢了``````````

[ 本帖最后由 chanel0388la 于 2006-4-18 00:02 编辑 ]

作者: chanel0388la 时间: 2006-4-17 23:03

是不是偶谢得不够诚恳阿？~~~~~~~~~~~~~~~~~~~

作者: zizidodoII 时间: 2006-4-17 23:07

原帖由 chanel0388la 于 2006-4-18 00:03 发表
是不是偶谢得不够诚恳阿？~~~~~~~~~~~~~~~~~~~

你找高手解答问题么大家都不敢妄称所以咯

作者: STROM 时间: 2006-4-17 23:11

楼上这个就是~

作者: zizidodoII 时间: 2006-4-17 23:12

原帖由 STROM 于 2006-4-18 00:11 发表
楼上这个就是~

我要是高手

Storm就情圣了

lol.giflol.giflol.gif

作者: STROM 时间: 2006-4-17 23:13

原帖由 zizidodoII 于 2006-4-18 00:12 发表

我要是高手

Storm就情圣了

lol.giflol.giflol.gif

册那,算你狠lol.gif

作者: zizidodoII 时间: 2006-4-17 23:15

原帖由 STROM 于 2006-4-18 00:13 发表

册那,算你狠lol.gif

哪里还是您内行到了春天就开花啊佩服~恭喜~

作者: 野林歌声 时间: 2006-4-17 23:15

具体什么问题，说出来大家参祥一下

作者: Constantine 时间: 2006-4-18 11:26

水好大呀，是有关EBNF的问题吧，呵呵。

作者: 野林歌声 时间: 2006-4-18 12:07

没有想到一包Räucherlachs,一个甜椒也能吃得这么香，哈当然加了酱油和绿色的芥末lol.gif 甜椒被我啃掉一大半，看起来真没胃口

[ 本帖最后由野林歌声于 2006-4-18 13:09 编辑 ]

作者: sagood 时间: 2006-4-18 12:48

问题呢？好大的水哦，哈哈

作者: 野林歌声 时间: 2006-4-18 13:45

洗澡了。。。。

作者: chanel0388la 时间: 2006-4-18 20:12

:9

[ 本帖最后由 chanel0388la 于 2006-4-23 20:41 编辑 ]

作者: sagood 时间: 2006-4-18 20:55

为什么要用C++，不能用Java或者C#么？

作者: chanel0388la 时间: 2006-4-18 20:58

原帖由 sagood 于 2006-4-18 21:55 发表
为什么要用C++，不能用Java或者C#么？

可以，但是我只会++

作者: sagood 时间: 2006-4-18 21:04

参考一下Java的：
class Vertex
{
public char label;
public boolean wasVisited;
public Vertex(char lab)
{
label = lab;
wasVisited = false;
}
}

class Graph
{
private final int MAX_VERTS = 20;
private Vertex vertexList[];
private int adjMat[][];
private int nVerts;

public Graph()
{
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for(int j=0; j<MAX_VERTS; j++)
for(int k=0; k<MAX_VERTS; k++)
adjMat[j][k] = 0;
}

public void addVertex(char lab) // argument is label
{
vertexList[nVerts++] = new Vertex(lab);
}

public void addEdge(int start, int end)
{
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}

public void displayVertex(int v)
{
System.out.print(vertexList[v].label);
}
}

[ 本帖最后由 sagood 于 2006-4-18 22:09 编辑 ]

作者: Flea 时间: 2006-4-18 21:27

找到高手了么, 我也在找

作者: 橙色坦克 时间: 2006-4-18 21:40

Sedgewick的"Algorithms in C++" 第5卷全是图算法，上面有这些东西。这书比较实用，Lehrbuchsammlung有。

作者: sagood 时间: 2006-4-18 21:45

因为是学C#的，所以去找了一下用C#表示的Graph，顺便也给自己复习一下：(不用泛型的)

Node.cs

using System;
using System.Collections;

namespace skmDataStructures.Graph
{
/// <summary>
/// A Node is uniquely identified by its string Key. A Node also has a Data property of type object
/// that can be used to store any extra information associated with the Node.
///
/// The Node has a property of type AdjacencyList, which represents the node's neighbors. To add a neighbor,
/// the Node class exposes an AddDirected() method, which adds a directed edge with an (optional) weight to
/// some other Node. These methods are marked internal, and are called by the Graph class.
/// </summary>
public class Node
{
#region Private Member Variables
// private member variables
private string key;
private object data;
private AdjacencyList neighbors;
#endregion

#region Constructors
private Node() {} // remove default constructor

public Node(string key, object data) : this(key, data, null) {}

public Node(string key, object data, AdjacencyList neighbors)
{
this.key = key;
this.data = data;
if (neighbors == null)
this.neighbors = new AdjacencyList();
else
this.neighbors = neighbors;
}
#endregion

#region Public Methods
#region Add Methods
/// <summary>
/// Adds an unweighted, directed edge from this node to the passed-in Node n.
/// </summary>
protected internal virtual void AddDirected(Node n)
{
AddDirected(new EdgeToNeighbor(n));
}

/// <summary>
/// Adds a weighted, directed edge from this node to the passed-in Node n.
/// </summary>
/// <param name="cost">The weight of the edge.</param>
protected internal virtual void AddDirected(Node n, int cost)
{
AddDirected(new EdgeToNeighbor(n, cost));
}

/// <summary>
/// Adds an edge based on the data in the passed-in EdgeToNeighbor instance.
/// </summary>
protected internal virtual void AddDirected(EdgeToNeighbor e)
{
neighbors.Add(e);
}
#endregion
#endregion

#region Public Properties
/// <summary>
/// Returns the Node's Key.
/// </summary>
public virtual string Key
{
get
{
return key;
}
}

/// <summary>
/// Returns the Node's Data.
/// </summary>
public virtual object Data
{
get
{
return data;
}
set
{
data = value;
}
}

/// <summary>
/// Returns an AdjacencyList of the Node's neighbors.
/// </summary>
public virtual AdjacencyList Neighbors
{
get
{
return neighbors;
}
}
#endregion
}
}

[ 本帖最后由 sagood 于 2006-4-18 23:30 编辑 ]

作者: sagood 时间: 2006-4-18 21:47

NodeList.cs

using System;
using System.Collections;

namespace skmDataStructures.Graph
{
/// <summary>
/// The NodeList class represents a collection of nodes. Internally, it uses a Hashtable instance to provide
/// fast lookup via a <see cref="Node"/> class's Key value. The <see cref="Graph"/> class maintains its
/// list of nodes via this class.
/// </summary>
public class NodeList : IEnumerable
{
// private member variables
private Hashtable data = new Hashtable();

#region Public Methods
/// <summary>
/// Adds a new Node to the NodeList.
/// </summary>
public virtual void Add(Node n)
{
data.Add(n.Key, n);
}

/// <summary>
/// Removes a Node from the NodeList.
/// </summary>
public virtual void Remove(Node n)
{
data.Remove(n.Key);
}

/// <summary>
/// Determines if a node with a specified Key value exists in the NodeList.
/// </summary>
/// <param name="key">The Key value to search for.</param>
/// <returns>True if a Node with the specified Key exists in the NodeList; False otherwise.</returns>
public virtual bool ContainsKey(string key)
{
return data.ContainsKey(key);
}

/// <summary>
/// Clears out all of the nodes from the NodeList.
/// </summary>
public virtual void Clear()
{
data.Clear();
}

/// <summary>
/// Returns an enumerator that can be used to iterate through the Nodes.
/// </summary>
/// <returns></returns>
public IEnumerator GetEnumerator()
{
return new NodeListEnumerator(data.GetEnumerator());
}
#endregion

#region Public Properties
/// <summary>
/// Returns a particular <see cref="Node"/> instance by index.
/// </summary>
public virtual Node this[string key]
{
get
{
return (Node) data[key];
}
}

/// <summary>
/// Returns the number of nodes in the NodeList.
/// </summary>
public virtual int Count
{
get
{
return data.Count;
}
}
#endregion

#region NodeList Enumerator
/// <summary>
/// The NodeListEnumerator method is a custom enumerator for the NodeList object. It essentially serves
/// as an enumerator over the NodeList's Hashtable class, but rather than returning DictionaryEntry values,
/// it returns just the Node object.
/// 
/// This allows for a developer using the Graph class to use a foreach to enumerate the Nodes in the graph.
/// </summary>
public class NodeListEnumerator : IEnumerator, IDisposable
{
IDictionaryEnumerator list;
public NodeListEnumerator(IDictionaryEnumerator coll)
{
list = coll;
}

public void Reset()
{
list.Reset();
}

public bool MoveNext()
{
return list.MoveNext();
}

public Node Current
{
get
{
return (Node) ((DictionaryEntry) list.Current).Value;
}
}

// The current property on the IEnumerator interface:
object IEnumerator.Current
{
get
{
return (Current);
}
}

public void Dispose()
{
list = null;
}
}
#endregion
}
}

[ 本帖最后由 sagood 于 2006-4-18 23:31 编辑 ]

作者: sagood 时间: 2006-4-18 21:50

AdjacencyList.cs

using System;
using System.Collections;

namespace skmDataStructures.Graph
{
/// <summary>
/// AdjacencyList maintains a list of neighbors for a particular <see cref="Node"/>. It is derived from CollectionBase
/// and provides a strongly-typed collection of <see cref="EdgeToNeighbor"/> instances.
/// </summary>
public class AdjacencyList : CollectionBase
{
/// <summary>
/// Adds a new <see cref="EdgeToNeighbor"/> instance to the AdjacencyList.
/// </summary>
/// <param name="e">The <see cref="EdgeToNeighbor"/> instance to add.</param>
protected internal virtual void Add(EdgeToNeighbor e)
{
base.InnerList.Add(e);
}

/// <summary>
/// Returns a particular <see cref="EdgeToNeighbor"/> instance by index.
/// </summary>
public virtual EdgeToNeighbor this[int index]
{
get { return (EdgeToNeighbor) base.InnerList[index]; }
set { base.InnerList[index] = value; }
}
}
}

[ 本帖最后由 sagood 于 2006-4-18 23:32 编辑 ]

作者: sagood 时间: 2006-4-18 22:03

EdgeToNeighbor.cs

using System;

namespace skmDataStructures.Graph
{
/// <summary>
/// EdgeToNeighbor represents an edge eminating from one <see cref="Node"/> to its neighbor. The EdgeToNeighbor
/// class, then, contains a reference to the neighbor and the weight of the edge.
/// </summary>
public class EdgeToNeighbor
{
#region Private Member Variables
// private member variables
private int cost;
private Node neighbor;
#endregion

#region Constructors
private EdgeToNeighbor() {}

public EdgeToNeighbor(Node neighbor) : this(neighbor, 0) {}

public EdgeToNeighbor(Node neighbor, int cost)
{
this.cost = cost;
this.neighbor = neighbor;
}
#endregion

#region Public Properties
/// <summary>
/// The weight of the edge.
/// </summary>
/// <remarks>A value of 0 would indicate that there is no weight, and is the value used when an unweighted
/// edge is added via the <see cref="Graph"/> class.</remarks>
public virtual int Cost
{
get
{
return cost;
}
}

/// <summary>
/// The neighbor the edge is leading to.
/// </summary>
public virtual Node Neighbor
{
get
{
return neighbor;
}
}
#endregion
}
}

[ 本帖最后由 sagood 于 2006-4-18 23:33 编辑 ]

作者: sagood 时间: 2006-4-18 22:33

Graph.cs

using System;

namespace skmDataStructures.Graph
{
/// <summary>
/// The Graph class represents a graph, which is composed of a collection of nodes and edges. This Graph class
/// maintains its collection of nodes using the NodeList class, which is a collection of Node objects.
/// It delegates the edge maintenance to the Node class. The Node class maintains the edge information using
/// the adjacency list technique.
/// </summary>
public class Graph
{
#region Private Member Variables
// private member variables
private NodeList nodes;
#endregion

#region Constructor
/// <summary>
/// Default constructor. Creates a new Graph class instance.
/// </summary>
public Graph()
{
this.nodes = new NodeList();
}

/// <summary>
/// Creates a new graph class instance based on a list of nodes.
/// </summary>
/// <param name="nodes">The list of nodes to populate the newly created Graph class with.</param>
public Graph(NodeList nodes)
{
this.nodes = nodes;
}
#endregion

#region Public Methods
/// <summary>
/// Clears out all of the nodes in the graph.
/// </summary>
public virtual void Clear()
{
nodes.Clear();
}

#region Adding Node Methods
/// <summary>
/// Adds a new node to the graph.
/// </summary>
/// <param name="key">The key value of the node to add.</param>
/// <param name="data">The data of the node to add.</param>
/// <returns>A reference to the Node that was created and added to the graph.</returns>
/// <remarks>If there already exists a node in the graph with the same key value then an
/// ArgumentException exception will be thrown.</remarks>
public virtual Node AddNode(string key, object data)
{
// Make sure the key is unique
if (!nodes.ContainsKey(key))
{
Node n = new Node(key, data);
nodes.Add(n);
return n;
}
else
throw new ArgumentException("There already exists a node in the graph with key " + key);
}

/// <summary>
/// Adds a new node to the graph.
/// </summary>
/// <param name="n">A node instance to add to the graph</param>
/// <remarks>If there already exists a node in the graph with the same key value as n then an
/// ArgumentException exception will be thrown.</remarks>
public virtual void AddNode(Node n)
{
// Make sure this node is unique
if (!nodes.ContainsKey(n.Key))
nodes.Add(n);
else
throw new ArgumentException("There already exists a node in the graph with key " + n.Key);
}
#endregion

#region Adding Edge Methods
/// <summary>
/// Adds a directed edge from one node to another.
/// </summary>
/// <param name="uKey">The Key of the node from which the directed edge eminates.</param>
/// <param name="vKey">The Key of the node from which the directed edge leads to.</param>
/// <remarks>If nodes with uKey and vKey do not exist in the graph, an ArgumentException
/// exception is thrown.</remarks>
public virtual void AddDirectedEdge(string uKey, string vKey)
{
AddDirectedEdge(uKey, vKey, 0);
}

/// <summary>
/// Adds a directed, weighted edge from one node to another.
/// </summary>
/// <param name="uKey">The Key of the node from which the directed edge eminates.</param>
/// <param name="vKey">The Key of the node from which the directed edge leads to.</param>
/// <param name="cost">The weight of the edge.</param>
/// <remarks>If nodes with uKey and vKey do not exist in the graph, an ArgumentException
/// exception is thrown.</remarks>
public virtual void AddDirectedEdge(string uKey, string vKey, int cost)
{
// get references to uKey and vKey
if (nodes.ContainsKey(uKey) && nodes.ContainsKey(vKey))
AddDirectedEdge(nodes[uKey], nodes[vKey], cost);
else
throw new ArgumentException("One or both of the nodes supplied were not members of the graph.");
}

/// <summary>
/// Adds a directed edge from one node to another.
/// </summary>
/// <param name="u">The node from which the directed edge eminates.</param>
/// <param name="v">The node from which the directed edge leads to.</param>
/// <remarks>If the passed-in nodes do not exist in the graph, an ArgumentException
/// exception is thrown.</remarks>
public virtual void AddDirectedEdge(Node u, Node v)
{
AddDirectedEdge(u, v, 0);
}

/// <summary>
/// Adds a directed, weighted edge from one node to another.
/// </summary>
/// <param name="u">The node from which the directed edge eminates.</param>
/// <param name="v">The node from which the directed edge leads to.</param>
/// <param name="cost">The weight of the edge.</param>
/// <remarks>If the passed-in nodes do not exist in the graph, an ArgumentException
/// exception is thrown.</remarks>
public virtual void AddDirectedEdge(Node u, Node v, int cost)
{
// Make sure u and v are Nodes in this graph
if (nodes.ContainsKey(u.Key) && nodes.ContainsKey(v.Key))
// add an edge from u -> v
u.AddDirected(v, cost);
else
// one or both of the nodes were not found in the graph
throw new ArgumentException("One or both of the nodes supplied were not members of the graph.");
}

/// <summary>
/// Adds an undirected edge from one node to another.
/// </summary>
/// <remarks>If nodes with uKey and vKey do not exist in the graph, an ArgumentException
/// exception is thrown.</remarks>
public virtual void AddUndirectedEdge(string uKey, string vKey)
{
AddUndirectedEdge(uKey, vKey, 0);
}

/// <summary>
/// Adds an undirected, weighted edge from one node to another.
/// </summary>
/// <param name="cost">The weight of the edge.</param>
/// <remarks>If nodes with uKey and vKey do not exist in the graph, an ArgumentException
/// exception is thrown.</remarks>
public virtual void AddUndirectedEdge(string uKey, string vKey, int cost)
{
// get references to uKey and vKey
if (nodes.ContainsKey(uKey) && nodes.ContainsKey(vKey))
AddUndirectedEdge(nodes[uKey], nodes[vKey], cost);
else
throw new ArgumentException("One or both of the nodes supplied were not members of the graph.");
}

/// <summary>
/// Adds an undirected edge from one node to another.
/// </summary>
/// <remarks>If the passed-in nodes do not exist in the graph, an ArgumentException
/// exception is thrown.</remarks>
public virtual void AddUndirectedEdge(Node u, Node v)
{
AddUndirectedEdge(u, v, 0);
}

/// <summary>
/// Adds an undirected, weighted edge from one node to another.
/// </summary>
/// <param name="cost">The weight of the edge.</param>
/// <remarks>If the passed-in nodes do not exist in the graph, an ArgumentException
/// exception is thrown.</remarks>
public virtual void AddUndirectedEdge(Node u, Node v, int cost)
{
// Make sure u and v are Nodes in this graph
if (nodes.ContainsKey(u.Key) && nodes.ContainsKey(v.Key))
{
// Add an edge from u -> v and from v -> u
u.AddDirected(v, cost);
v.AddDirected(u, cost);
}
else
// one or both of the nodes were not found in the graph
throw new ArgumentException("One or both of the nodes supplied were not members of the graph.");
}
#endregion

#region Contains Methods
/// <summary>
/// Determines if a node exists within the graph.
/// </summary>
/// <param name="n">The node to check for in the graph.</param>
/// <returns>True if the node n exists in the graph, False otherwise.</returns>
public virtual bool Contains(Node n)
{
return Contains(n.Key);
}

/// <summary>
/// Determines if a node exists within the graph.
/// </summary>
/// <param name="key">The key of the node to check for in the graph.</param>
/// <returns>True if a node with key key exists in the graph, False otherwise.</returns>
public virtual bool Contains(string key)
{
return nodes.ContainsKey(key);
}
#endregion
#endregion

#region Public Properties
/// <summary>
/// Returns the number of nodes in the graph.
/// </summary>
public virtual int Count
{
get
{
return nodes.Count;
}
}

/// <summary>
/// Returns a reference to the set of nodes in the graph.
/// </summary>
public virtual NodeList Nodes
{
get
{
return this.nodes;
}
}
#endregion
}
}

作者: sagood 时间: 2006-4-18 22:35

/**** START DIJKSTRA ****/
while (nodes.Count > 0)
{
Node u = GetMin(nodes); // get the minimum node
nodes.Remove(u); // remove it from the set Q

// iterate through all of u's neighbors
foreach(EdgeToNeighbor edge in u.Neighbors)
Relax(u, edge.Neighbor, edge.Cost); // relax each edge
} // repeat until Q is empty
/**** END DIJKSTRA ****/

private void Relax(Node uCity, Node vCity, int cost)
{
int distTouCity = (int) dist[uCity.Key];
int distTovCity = (int) dist[vCity.Key];

if (distTovCity > distTouCity + cost)
{
// update distance and route
dist[vCity.Key] = distTouCity + cost;
route[vCity.Key] = uCity;
}
}

private Node GetMin(NodeList nodes)
{
// find the node in nodes with the smallest distance value
int minDist = Int32.MaxValue;
Node minNode = null;
foreach(Node n in nodes)
{
if (((int) dist[n.Key]) <= minDist)
{
minDist = (int) dist[n.Key];
minNode = n;
}
}

return minNode;
}

作者: chanel0388la 时间: 2006-4-19 05:23

学习中

[ 本帖最后由 chanel0388la 于 2006-4-19 08:18 编辑 ]

欢迎光临人在德国社区 (http://csuchen.de/bbs/)