java链表

好久没有上新课啦~  今天学习了链表方面的内容，完成了一些作业。
个人小总结：之前学过C、C++，因此对链表也有所了解，也知道它是用指针来实现的。现在接触了java的链表，由于java中没有了指针这一概念，因此我们必须找到一个可以替代C或C++中指针的东西。那么我们就用到了对象的引用，用它来代替指针。 链表其他的操作感觉和C、C++的差不多，这里就不多做解释啦~！~

下面是作业的完成情况（总共是5道题，粘贴部分代码）：
1.单链表排序（部分代码）

package cjl.list;

/*
 * 链表的结点类
 */
public class Node {

	int obj;// 结点中的元素
	Node next;// 下一个结点的引用

	public Node(int obj) {
		this.obj = obj;
	}

}


/**
 *  链表排序
 */
package cjl.list;

public class LinkSort {
	private Node head = null;
	private Node last = null;

	public LinkSort(Node head2) {
		this.head = head2;
		this.sort();
	}

	public void sort() {
		// 判断是否传输成功
		Node node = head;
		Node node2 = node.next;
		int temp;
		int t;
		while (node != null) {
			node2 = node.next;
			while (node2 != null) {

				if (node.obj > node2.obj) {
					temp = node.obj;
					node.obj = node2.obj;
					node2.obj = temp;
					// node2.next=node;

				}

				node2 = node2.next;
			}
			node = node.next;
		}

		// node=node2.next;
		System.out.println("检测排序后！！！！");
		node = head;
		while (node != null) {
			System.out.print(node.obj + "  ");
			node = node.next;
		}
		System.out.println();

	}
}

2.单链表反转

/**
 *  链表的反向
 */

package cjl.list;

import java.security.acl.LastOwnerException;

public class LinkReverse {
	private Node head = null;
	private int size;
	private Node tempnode = null;
	private Node lastnode = null;
	private Node node = null;
	private Node node2 = null;
	private int temp;

	public LinkReverse(Node head, int size) {
		this.head = head;
		this.size = size;
		this.reverse(this.head);

	}

	private void reverse(Node head2) {
		node = head2;
		// 创建一个新的节点
		// 打印测试
		System.out.println("反向后结果：");

		// // 判断第一个节点时候存在
		// if (head2 != null) {
		// // 创建一个节点
		// lastnode.obj = head2.obj;
		//
		// lastnode.next = null;
		//
		// node = node.next;
		// }
		// 逐个获取node元素
		while (node != null) {
			node2 = node.next;
			while (node2 != null) {

				temp = node.obj;
				node.obj = node2.obj;
				node2.obj = temp;
				// node2.next=node;

				node2 = node2.next;
			}
			node = node.next;
		}
		node = head;
		while (node != null) {
			System.out.print(node.obj + "  ");
			node = node.next;
		}
		System.out.println();
	}
}

3.如何判断一个链表是否有环？
   如果链表为存在环，如果找到环的入口点？

/**
 *   判断链表是否有环
 */
package cjl.list;

public class LinkIsloop {
	private Node head = null;
	private Node node = null;
	private Node node2 = null;
	private int temp;

	public LinkIsloop(Node head) {
		this.head = head;
		this.node = head;
		this.node2 = head.next;
		this.findentrance(head);
	}

	private void isloop(Node head2) {
		// TODO Auto-generated method stub

	}

	private void findentrance(Node head2) {
		Node node = head2;
		Node node2 = node.next;

		while (node != null) {
			node2 = node.next;
			while (node2 != null) {

				if (node == node2) {
					// 说明有环
					System.out.println("**************链表有环！！！***********");
					System.out.println("**************链表的入口是" + node.obj+"**************");
					// node2.next=node;
					break;
				}

				node2 = node2.next;
			}
			if (node == node2) {
				break;
			}
			node = node.next;
		}

		System.out.println("****************链表没没没有环！！**************");
	}

}

4.判断两个单链表是否相交？

*  判断链表是否相交
 */
package cjl.list;

public class LinkIsIntersect {
	private Node head1 = null;
	private Node head2 = null;
	private Node node1 = null;
	private Node node2 = null;

	public LinkIsIntersect(Node head1, Node head2) {

		this.head1 = head1;
		this.head2 = head2;
		// 调用判断是否相交的方法
		this.isintersect();
	}

	// 判断链表是否相交的方法
	private void isintersect() {

		node1 = head1;
		node2 = head2;

		while (node1 != null) {
			node1 = node1.next;
			Node node3 = head2;
			while (node3 != null) {
				if (node1 != node3) {
					node3 = node3.next;
				} else {
					System.out.println("******两链表相交*****");
					break;
				}
			}
			if (node1 == node3) {
				break;
			} else

				node1 = node1.next;

		}
		if (node1 == null) {
			System.out.println("********两链表不相交******");
		}
	}
}

5.约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。例如：n = 9,k = 1,m = 5

/*   模拟约瑟夫问题
 * 约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。
 * 从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；
 * 依此规律重复下去，直到圆桌周围的人全部出列。例如：n = 9,k = 1,m = 5
 */
package cjl.list;

public class Joseph {
	private Node head;
	private int n;
	private int k;
	private int m;
	private Node node;
	private Node starnode;
	private Node node2; // 前驱

	public Joseph(Node head, int n, int k, int m) {
		this.head = head;
		this.n = n;
		this.k = k;
		this.m = m;
		System.out
				.println("\n------------------------模拟约瑟夫问题----------------------------------");
		// 原始素具
		System.out.println("原始数据为：");
		node = head;
		// 打印原始数据
		while (node != null) {
			System.out.print(node.obj + "  ");
			node = node.next;
		}
		// 打印报数的规则
		System.out.println("\n报数从" + k + "开始，跨度为" + m + ",下面开始准备报数.........\n");

		// 调用报数的方法
		this.saynumber();
	}

	// 报数的方法
	private void saynumber() {
		int temp = 1;
		starnode = head;
		
		// 手动生成环形列表
		while (temp != 10) {
			starnode = starnode.next;
			temp++;
		}
		starnode.next = head;
		temp = 1;
		starnode = head;
		
		// 根据k的值，定位开始报数的位置
		while (temp != k) {
			starnode = starnode.next;
			temp++;
		}

		// 将temp 的值重新赋值为1
		temp = 1;
		node2 = node = starnode;

		while (n != 0) {
			// 创建一个报数器
			int count = 1;

			System.out.print("第" + temp + "轮报数结束:");
			while (count != m) {
				node2 = node;
				node = node.next;
				count++;
			}
			System.out.println("被淘汰的元素为——>" + node.obj);
			// 去除node元素
			node2.next = node.next;
			node = node.next;
			temp++;
			n--;
		}

	}
}

评论

2 楼 smallboby 2014-05-07  

fxrz12 写道

知道为什么会被踩吗？java根本不需要链表，应该讲不需要去写。老师讲些些东西太落伍了，输入法工具随便拿来用，没听说还要自己先做个输入法试试，且还是残缺的没经过验证的。

使用输入法为何不能考虑怎么实现的？为何不能自己试着研究出来一个？
即使自己不能为何还要打击别人的积极性.

1 楼 fxrz12 2013-05-07  

知道为什么会被踩吗？java根本不需要链表，应该讲不需要去写。老师讲些些东西太落伍了，输入法工具随便拿来用，没听说还要自己先做个输入法试试，且还是残缺的没经过验证的。