graph.java

一次数据结构的课程设计

package src;

class Edge
{
	public String[] autoName;
	public int distant;
	public int cost;
	public int autoNum;
	private final int MAX_EDGES = 100;
	private final int MAX_AM = 99999;
	public Edge()
	{
		distant = MAX_AM;
		cost = MAX_AM;
		autoNum = 0;
		autoName = new String[MAX_EDGES];
		autoName[autoNum] = null;
	}
}


class Record
{
	public int from;
	public int to;
	public int distance;
	public int cash;
	public String name;
	public Record next;

	public Record()
	{
		from = 0;
		to = 0;
		distance = 0;
		cash = 0;
		name = null;
		next = null;
	}
	public boolean setRecord(int f,int t,int d,int c,String n)
	{
		from = f;
		to = t;
		distance = d;
		cash = c;
		name = new String(n);
		return true;
	}
}

public class Graph
{
	public Record records;
	public Edge[][] cityEdge;
	public int adjMat[][];
	public int shorestMat[][][];

	private int MAX = 100;
	public String citylist[];
	public int  cityNum;
	private final int MAX_VERTS = 100;
    private final int INFINITY = 1000000;
    private final int MAX_AM = 99999;

	public Graph()
	{
	   cityFile file = new cityFile();
	   records = new Record();
	   String[] temp = file.inputfromNameFile();
	   cityNum = temp.length;

	   shorestMat = new int[cityNum][cityNum][cityNum];
	   citylist = new String[MAX];
	   cityEdge = new Edge[cityNum][cityNum];
	   adjMat = new int[cityNum][cityNum];

	   for(int i=0; i<cityNum; i++)
	   {
			citylist[i] = new String(temp[i]);
			for(int j=0; j<cityNum; j++)
			{
				cityEdge[i][j] = new Edge();
				adjMat[i][j] = INFINITY;
				for(int x=0; x<cityNum; x++)
					shorestMat[i][j][x] = -1;
			}
	   }

    }
//about graph of vertex
	public boolean insertCity(String name)
	{
		if( changetoNum(name) >= 0 )
			return false;
		if(cityNum == MAX)
		{
			System.out.println("citylist FULL");
			return false;
		}
		citylist[cityNum] = name;
		cityNum++;
		return true;
	}
	public boolean delCity(String name)
	{
		cityFile file = new cityFile();
		int f;
		if( (f=changetoNum(name)) < 0 )
			return false;

		for(int i=f; i<cityNum-1; i++)
		{
			citylist[i]=new String(citylist[i+1]);
		}
		citylist[cityNum-1] = null;
		cityNum--;

		Record r = records;
		while(r!=null)
		{
			if(r.from == f|| r.to == f)
			{
				deletEdge(r.from,r.to);
				deletEdge(r.to,r.from);
			}
			if(r.from > f)
				r.from--;
			if(r.to > f)
			    r.to--;
			 r = r.next;
		}
		file.outtoNameFile(citylist,cityNum);
		file.outputtoInfoFile(records);
		return true;
	}
//about graph of edge
	public boolean insertEdge(int from,int to,int dist,int money,String carName)
	{
		cityEdge[from][to].distant = dist;
		cityEdge[from][to].cost = money;
		if(adjMat[from][to] == 1)
		{
			int num = ++cityEdge[from][to].autoNum;
			cityEdge[from][to].autoName[num] = new String(carName);
		}
		else
		{
			cityEdge[from][to].autoName[0] = new String(carName);
			adjMat[from][to] = 1;
		}

		shorestMat[from][to][0] = to;
		addRecord(from,to,dist,money,carName);
		return true;
	}

	public boolean deletEdge(int from,int to)
	{	if(adjMat[from][to] == 1)
		{
			cityEdge[from][to].distant = MAX_AM;
			cityEdge[from][to].cost = MAX_AM;
			cityEdge[from][to].autoName = null;
			cityEdge[from][to].autoNum = 0;
			adjMat[from][to] = INFINITY;
			shorestMat[from][to][0] = -1;
			delRecord(from,to);
			return true;
		}
		else
			return false;
	}

	public boolean modifyEdge(int from,int to,int dist,int money,String name)
	{
			deletEdge(from,to);
			insertEdge(from,to,dist,money,name);

			return true;
	}// end edge

//about Record
	public boolean addRecord(int from,int to,int dist,int money,String n)
	{
		Record p = new Record();
		p.setRecord(from,to,dist,money,n);
		p.next = records.next;
		records.next = p;

		return true;
	}

	public boolean delRecord(int from,int to)
	{
		Record p,q;
		p = records.next;
		q = p;
		while(p!=null && p.from!=from && p.to!=to)
		{
			q = p;
			p = p.next;
		}
		if(p==null)
			System.out.println("无法删除");
		else if(p==q)
			records.next = p.next;
		else
			q.next = p.next;

		return true;
	}//end Record

//change
	public int changetoNum(String cname)
	{
		int i=0;
		while(!citylist[i].equals(cname))
		{
			i++;
			if(i==cityNum)
				break;
		}
		if(i==cityNum)
			return -2;
		return i;
	}

//
	public void print()
	{
		for(int i=0; i<cityNum; i++)
		{
			System.out.println(citylist[i]+"\n");
			for(int j=0; j<cityNum; j++)
			{
				//System.out.println("adjMat"+adjMat[i][j]);
				System.out.println("Num"+cityEdge[i][j].autoNum);
				//for(int d=0;d<cityEdge[i][j].autoNum;d++)
				//	System.out.println("carname:"+cityEdge[i][j].autoName[d]);
			}
		}
	}
	//main for test
	public static void main(String[] args)
	{
		Graph g = new Graph();
		cityFile file = new cityFile();
	//	g.insertEdge(1,0,123,2,"T-2571");
	//	g.insertEdge(0,1,123,2,"T-2672");
	//	g.insertEdge(1,2,23,4,"S-234");
	////	g.insertEdge(1,2,23,4,"S-110");
	//	g.insertEdge(2,1,23,4,"S-23e");
		g.insertEdge(2,3,34,56,"X-521");
		g.insertEdge(2,3,34,56,"WC-521");
		g.insertEdge(3,2,34,56,"X-520");
		g.insertEdge(3,0,342,5,"U-571");
		g.insertEdge(0,3,342,5,"U-573");
		//g.insertEdge(4,3,232,4,"U-571");
	//	g.insertEdge(4,3,232,4,"P-341");
	//	g.insertEdge(3,4,232,4,"Q-341");
	//	g.insertEdge(1,4,343,6,"T-2571");
	//	g.insertEdge(4,1,343,6,"M-2570");
		System.out.println("*****************");
		g.delCity("石家庄");
		g.print();
		file.outputtoInfoFile(g.records);
	}
}