求个数据结构的算法问题

0 0

求个数据结构的算法问题0

目前有两个List
其中一个内容是 1,2,3,4,5,6,7,8,8,9,4,4,10
另一个内容是 2,3,4,5,6,7,8,9,15,8,16,3,11

其中第一个list是起点第二个list是终点比如起点是1 终点是2 ，启动2终点是3 ，起点是3 终点是4 ，启动时4 终点是5，启点是5 终点是6 ，。。。。。。。。。。
我想通过这两个list查询出以下链路
链路1:1-2-3-4-5-6-7-8-9
链路2:1-2-3-4-16
链路3:1-2-3-4-5-6-7-8-15
链路4:10-11

请问大家有没有好的算法请提供以下最好能附上代码。

数据结构算法

2012年11月27日 22:37

ljz0898
3
0 0 4

1个答案按时间排序按投票排序

0 0

public class ItEyeQues
{
	private int[] int1 = {1,2,3,4,5,6,7,8,8,9,4,4,10};
	private int[] int2 = {2,3,4,5,6,7,8,9,15,8,16,3,11};
	
	/**
	 *  传入一个终点，返回他对应的起点坐标
	 * @param i
	 * @return
	 */
	public List<Integer> getIndex(int i) {
		List<Integer> index = new ArrayList<Integer>();
		for(int j = 0; j < int1.length; j++) {
			if(int1[j] == i) {
				index.add(j);
			}
		}
		return index;
			
	}
	
	/**
	 * 启动程序，初始化值
	 */
	public void getPath() {
		for(int i = 0 ; i < int1.length; i++) {
			int startIndex = i;
			StringBuffer path = new StringBuffer();
			buildPath(startIndex, path);
		}
	}
	
	/**
	 * 防止回路 如 1-2-3-4-5-6-7-8-9-8
	 * @param end
	 * @param sb
	 * @return
	 */
	public boolean check(int end, StringBuffer sb) {
		String[] str = sb.toString().split("-");
		for(int i =0; i < str.length; i++) {
			if(!"".equals(str[i])) {
				if(Integer.parseInt(str[i]) == end) {
					return false;
				}
			}
		}
		return true;
	}
	
	/**
	 * 递归算法
	 * @param startIndex
	 * @param sb
	 */
	public void buildPath(int startIndex,StringBuffer sb) {
		int start = int1[startIndex];
		int end = int2[startIndex];
		if(check(end,sb) == false) {
			System.out.println(sb.toString());
			return;
		}
		if(sb.length() == 0) {
			sb.append(start + "-" + end);
		} else {
			sb.append("-" + end);
		}
		List<Integer> list = getIndex(end);
		if(list.size() == 0) {
			System.out.println(sb.toString());
			return;
		}
		for(int n = 0; n < list.size(); n++) {
			int startindex = list.get(n);
			buildPath(startindex, new StringBuffer(sb.toString()));
		}
	}
	
	/**
	 * test
	 * @param args
	 */
	public static void main(String[] args) {
		ItEyeQues it = new ItEyeQues();
		it.getPath();
	}
}

这个程序可以输出所有的路径，不太明白你想问什么，但是这个可以解决你所有的问题了

2012年11月28日 13:55