武汉纺织大学《数据结构》实验报告(共23页).doc

《武汉纺织大学《数据结构》实验报告(共23页).doc》由会员分享，可在线阅读，更多相关《武汉纺织大学《数据结构》实验报告(共23页).doc（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上武汉纺织大学数据结构实验报告班级： 管工类 专业 班 姓名： 序号： 实验时间： 2014 年 5 月 16 日 指导教师： 实验三：图的基本操作与应用一、实验目的： 1、掌握图的几种主要存储方法及基本操作2、掌握图的两种遍历方法3、掌握利用普里姆算法和克鲁斯卡尔算法求取最小生成树的方法4、掌握求取AOE网关键路径的方法，以实现项目时间管理二、实验内容：1、编写程序，输出图的邻接矩阵，输出两种遍历序列，并求出最小生成树。 实验步骤： 、在Java语言编辑环境中新建程序，输入顶点集合和边集合，构造一个图7-15所示的带权图，可参考书本225页示例程序； 、对该带权图，进

2、行插入顶点、插入边、删除顶点、删除边操作，并输出操作后的邻接矩阵，可参考书本226-228页示例程序； 、输出从顶点A开始的深度优先遍历和广度优先遍历的序列，可参考书本238、240页示例程序； 、输出运用普里姆算法求出的最小生成树，可参考书本245页示例程序。2、设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。实验步骤： 、在Java语言编辑环境中新建程序，输入如下图所示的AOE网； 、按照关键路径求取步骤，求出各个顶点的最早开始时间和最迟开始时间； 、求出各个活动的最早开始时间和最迟开始时间； 、找出该AOE网的关键路径，并计算出该项目的完成时间。关键路径相关时间知识

3、点： 设活动ai由弧(即从顶点j到k)表示，其持续时间记为dut(),则： e(i)=ve(j) l(i)=vl(k)-dut()求ve(i)和vl(j)分两步： （1）.从ve(1)=0开始向前递推ve(j)=Maxve(i)+dut()T, 2=j=n ，其中，T是所有以j为弧头的弧的集合。（2）.从vl(n)=ve(n)开始向后递推vl(i)=Minvl(j)-dut() S,1=i=n-1，其中，S是所有以i为弧尾的弧的集合。求关键路径的算法： 、输入e条弧，建立AOE网的存储结构； 、从起始点出发，令ve0=0，按拓扑顺序求其余各顶点的最早发生时间vei(1=i=i=0)； 、根据各

4、顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某弧满足条件e(s)=l(s)，则为关键活动。三、操作步骤：Test1代码：Graph1.javapackage Frist;public class Graph1 public static void main(String args) String vertices = A, B, C, D, E ;Edge edges = new Edge(0, 1, 5), new Edge(0, 3, 2),new Edge(1, 0, 5), new Edge(1, 2, 7), new Edge(1, 3, 6),ne

5、w Edge(2, 1, 7), new Edge(2, 3, 8), new Edge(2, 4, 3),new Edge(3, 0, 2), new Edge(3, 1, 6), new Edge(3, 2, 8),new Edge(3, 4, 9), new Edge(4, 2, 3), new Edge(4, 3, 9) ;AdjMatrixGraph graph = new AdjMatrixGraph(vertices,edges);System.out.println(带权无向图, + graph.toString();System.out.println(插入顶点F,插入边(A

6、,F,20),删除顶点C,删除边(D,E);int i = graph.insertVertex(F);graph.insertEdge(0, i, 20);graph.insertEdge(i, 0, 20);graph.removeVertex(2);graph.removeEdge(2, 3);graph.removeEdge(3, 2);System.out.println(graph.toString();AdjMatrixGraph graph1 = new AdjMatrixGraph(vertices,edges);System.out.print(深度优先遍历序列为：);gr

7、aph1.DFSTraverse(0);System.out.print(广度优先遍历序列为：);graph1.BFSTraverse(0);AdjMatrixGraph graph2 = new AdjMatrixGraph(vertices,edges);System.out.print(带权无向图, + graph2.toString();graph2.minSpanTree_prim();LList.javapackage Frist;public interface LList boolean isEmpty();int length();T get(int i);void set(

8、int i, T x);void insert(int i, T x);T remove(int i);void removeAll();QQueue.javapackage Frist;public interface QQueue boolean isEmpty();void enqueue(T x);T dequeue();SeqList.javapackage Frist;public class SeqList implements LList private Object element;private int len;public SeqList(int size) this.e

9、lement = new Objectsize;this.len = 0;public SeqList() this(64);public boolean isEmpty() return this.len = 0;public int length() return this.len;public T get(int i) if (i = 0 & i = 0 & i 0)str += this.element0.toString();for (int i = 1; i this.len; i+)str += , + this.elementi.toString();return str +

10、);public void insert(int i, T x) if (x = null)return;if (this.len = element.length) Object temp = this.element;this.element = new Objecttemp.length * 2;for (int j = 0; j temp.length; i+)this.elementi = tempj;if (i this.len)i = this.len;for (int j = this.len - 1; j = i; j-)this.elementj + 1 = this.el

11、ementj;this.elementi = x;this.len+;public void append(T x) insert(this.len, x);public T remove(int i) if (this.len = 0 | i = this.len)return null;T old = (T) this.elementi;for (int j = i; j this.len - 1; j+)this.elementj = this.elementj + 1;this.elementthis.len - 1 = null;this.len-;return old;public

12、 void removeAll() this.len = 0;SeqQueue.javapackage Frist;public class SeqQueue implements QQueue private Object element;private int front, rear;public SeqQueue(int length) if (length 64)length = 64;this.element = new ObjectMath.abs(length);this.front = this.rear = 0;public SeqQueue() this(64);publi

13、c boolean isEmpty() return this.front = this.rear;public void enqueue(T x) if (x = null)return;if (this.front = (this.rear + 1) % this.element.length) Object temp = this.element;this.element = new Objecttemp.length * 2;int i = this.front, j = 0;while (i != this.rear) this.elementj = tempi;i = (i + 1

14、) % temp.length;j+;this.front = 0;this.rear = j;this.elementthis.rear = x;this.rear = (this.rear + 1) % this.element.length;public T dequeue() if (isEmpty()return null;T temp = (T) this.elementthis.front;this.front = (this.front + 1) % this.element.length;return temp;public String toString() String

15、str = (;if (!isEmpty() str += this.elementthis.front.toString();int i = (this.front + 1) % this.element.length;while (i != this.rear) str += , + this.element.length;return str + );GGraph.javapackage Frist;public interface GGraph public static final int MAX_WEIGHT = 99999;int vertexCount();T get(int

16、i);int getWeight(int i, int j);int insertVertex(T x);void insertEdge(int i, int j, int weight);void removeEdge(int i, int j);void removeVertex(int i);int getNextNeighbor(int i, int j);void DFSTraverse(int i);void BFSTraverse(int i);AbstractGraph.javapackage Frist;public abstract class AbstractGraph

17、implements GGraph public abstract int vertexCount();public abstract T get(int i);public abstract int getNextNeighbor(int i, int j);public void DFSTraverse(int i) boolean visited = new booleanthis.vertexCount();int j = i;do if (!visitedj) System.out.print();this.depthfs(j, visited);System.out.print()

18、;j = (j + 1) % this.vertexCount(); while (j != i);System.out.println();private void depthfs(int i, boolean visited) System.out.print(this.get(i) + );visitedi = true;int j = this.getNextNeighbor(i, -1);while (j != -1) if (!visitedj)depthfs(j, visited);j = this.getNextNeighbor(i, j);public void BFSTra

19、verse(int i) boolean visited = new booleanthis.vertexCount();int j = i;do if (!visitedj) System.out.print();breadthfs(j, visited);System.out.print();j = (j + 1) % this.vertexCount(); while (j != i);System.out.println();private void breadthfs(int i, boolean visited) System.out.print(this.get(i) + );v

20、isitedi = true;SeqQueue que = new SeqQueue(this.vertexCount();que.enqueue(new Integer(i);while (!que.isEmpty() i = que.dequeue().intValue();int j = this.getNextNeighbor(i, -1);while (j != -1) if (!visitedj) System.out.print(this.get(j) + );visitedj = true;que.enqueue(new Integer(j);j = this.getNextN

21、eighbor(i, j);public abstract int getWeight(int i, int j);public void minSpanTree_prim() Edge mst = new EdgevertexCount() - 1;for (int i = 0; i mst.length; i+)msti = new Edge(0, i + 1, this.getWeight(0, i + 1);for (int i = 0; i mst.length; i+) int minweight = MAX_WEIGHT;int min = i;for (int j = i; j

22、 mst.length; j+)if (mstj.weight minweight) minweight = mstj.weight;min = j;Edge temp = msti;msti = mstmin;mstmin = temp;int tv = msti.dest;for (int j = i + 1; j mst.length; j+) int v = mstj.dest;if (this.getWeight(tv, v) mstj.weight) msti.weight = this.getWeight(tv, v);mstj.start = tv;System.out.pri

23、nt(n最小生成树边的集合:);int mincost = 0;for (int i = 0; i mst.length - 1; i+) System.out.print(msti + );mincost += msti.weight;System.out.print(,最小代价为 + mincost);AdjMatrixGraph.javapackage Frist;public class AdjMatrixGraph extends AbstractGraph protected SeqList vertexlist;protected int adjmatrix;private fi

24、nal int MAX_WEIGHT = 99999;public AdjMatrixGraph(int size) size = size 10 ? 10 : size;this.vertexlist = new SeqList(size);this.adjmatrix = new intsizesize;for (int i = 0; i size; i+)for (int j = 0; j size; j+)this.adjmatrixij = (i = j) ? 0 : MAX_WEIGHT;public AdjMatrixGraph(T vertices, Edge edges) t

25、his(vertices.length);if (vertices = null)return;for (int i = 0; i vertices.length; i+)insertVertex(verticesi);if (edges != null)for (int j = 0; j 0 & i = 0 & j this.adjmatrix.length) int temp = adjmatrix, i, j;this.adjmatrix = new inttemp.length * 2temp.length * 2;for (i = 0; i temp.length; i+) for

26、(j = 0; j temp.length; j+)this.adjmatrixij = tempij;for (j = temp.length; j temp.length * 2; j+)this.adjmatrixij = MAX_WEIGHT;for (i = temp.length; i temp.length * 2; i+)for (j = 0; j temp.length * 2; j+)this.adjmatrixij = (i = j) ? 0 : MAX_WEIGHT;return this.vertexlist.length() - 1;public int verte

27、xCount() return this.vertexlist.length();public T get(int i) return this.vertexlist.get(i);public int getWeight(int i, int j) return this.adjmatrixij;public String toString() String str = 顶点集合： + this.vertexlist.toString() + n邻接矩阵： n;int n = this.vertexCount();for (int i = 0; i n; i+) for (int j = 0

28、; j = 0 & i = 0 & j vertexCount()& i != j)this.adjmatrixij = MAX_WEIGHT;public void removeVertex(int i) int n = this.vertexCount();if (i n)return;this.vertexlist.remove(i);for (int j = 0; j i; j+)for (int k = i + 1; k n; k+)this.adjmatrixjk - 1 = this.adjmatrixjk;for (int j = i + 1; j n; j+)for (int

29、 k = 0; k i; k+)this.adjmatrixj - 1k = adjmatrixjk;for (int j = i + 1; j n; j+)for (int k = i + 1; k = 0 & i = -1 & j n & i != j)for (int k = j + 1; k 0& this.adjmatrixik MAX_WEIGHT)return k;return -1;Edge.javapackage Frist;public class Edge implements Comparable public int start, dest, weight;publi

30、c Edge(int start, int dest, int weight) super();this.start = start;this.dest = dest;this.weight = weight;public String toString() return ( + start + , + dest + , + weight + );public int compareTo(Edge e) if (this.start != e.start)return this.start = e.start;return this.dest = e.dest;运行结果:Test2代码;Gra

31、phT2.javapackage Second;public class GraphT2 public static void main(String args) Graph graph = new Graph(9); graph.add(1); graph.add(2); graph.add(3); graph.add(4); graph.add(5); graph.add(6); graph.add(7); graph.add(8); graph.add(9); graph.addEdge(0, 1, 6); graph.addEdge(0, 2, 4); graph.addEdge(0,

32、 3, 5); graph.addEdge(1, 4, 1); graph.addEdge(2, 4, 1); graph.addEdge(3, 5, 2); graph.addEdge(4, 6, 9); graph.addEdge(4, 7, 7); graph.addEdge(5, 7, 4); graph.addEdge(6, 8, 2); graph.addEdge(7, 8, 4); if (graph.topo() graph.calculate(); int e = graph.getE(); int l = graph.getL(); int key = graph.getK

33、ey(); int ve = graph.getVE(); int vl = graph.getVl(); System.out.println(事件的最早发生时间：); for (int w = 0; w ve.length; w+) System.out.print(vew + ); System.out.println(); System.out.println(事件的最晚发生时间：); for (int w = 0; w vl.length; w+) System.out.print(vlw + ); System.out.println(); System.out.println(活

34、动的最早发生时间：); for (int w = 0; w e.length; w+) System.out.print(ew + ); System.out.println(); System.out.println(活动的最迟发生时间：); for (int w = 0; w l.length; w+) System.out.print(lw + ); System.out.println(); System.out.println(关键活动有：); for (int w = 0; w graph.getKNum(); w+) System.out.print(keyw + ); System.out.println(); Graph.javapackage Second;public class Graph private Vertex vertexs;private Link adjTab;private int pos = -1;privat