一些简单的算法与数据结构

稀疏数组

int chessArr1[][] = new int[11][11];//11*11的数组
         int sum = 0;
         chessArr1[1][2] = 1;//设置两个值
         chessArr1[2][3] = 2;
         //打印原数组
         for(int[] row : chessArr1) {
        	 for(int data : row) {
        		 System.out.printf("%d\t", data);
        		 if(data != 0) sum++;
        	 }
        	 System.out.println();
         }
         //稀疏数组建立
         int sparseArr[][] = new int[sum + 1][3];
         sparseArr[0][0] = 11;
         sparseArr[0][1] = 11;
         sparseArr[0][2] = sum;
         int temp = 0;
         //遍历查找非0元素，赋值给稀疏数组
         for(int i = 0; i < 11; i++)
         {
        	 for(int j = 0; j < 11; j++) {
        		 if(chessArr1[i][j] != 0) {
        			 sparseArr[++temp][0] = i;
        			 sparseArr[temp][1] = j;
        			 sparseArr[temp][2] = chessArr1[i][j];
        		 }
        	 }
         }
         //输出稀疏数组
         for(int[] row : sparseArr) {
        	 for(int data : row) {
        		 System.out.printf("%d\t", data);
        	 }
        	 System.out.println();
         }

队列

实现类：

private int maxSize;
	private int front;
	private int rear;
	private int[] arr;
	
	public ArrayQueue(int arrMaxSize) {
		maxSize = arrMaxSize;
		arr = new int[maxSize];
		front = -1;
		rear = -1;		
	}
	//是否满
	public boolean isFull() {
		return rear == maxSize - 1;
	}
	//是否空
	public boolean isEmpty() {
		return rear == front;		
	}
	//增加元素
	public void addQueue(int i) {
		if(isFull()) {
			System.out.println("队列满");
			return;
		}
		rear++;
		arr[rear] = i;
	}
	//依次返回从头开始的元素
	public int getQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列空");
		}
		front++;
		return arr[front];
	}
	//显示队列
	public void showQueue() {
		if(isEmpty()) {
			System.out.println("队列空");
			return;
		}
		int temp = 0;
		for(int i : arr) {
			System.out.printf("arr[%d]=%d\n", temp++, i);
		}
	}
	//返回队首元素
	public int headQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列空");
		}
		return arr[front + 1];
	}

测试类

ArrayQueue aq = new ArrayQueue(3);
		char key = ' ';
		Scanner sc = new Scanner(System.in);
		boolean loop = true;
		while(loop) {
			System.out.println("s:show");//显示
			System.out.println("e:exit");//退出
			System.out.println("a:add");//增加
			System.out.println("g:get");//依次显示
			System.out.println("h:head");//头元素
			key = sc.next().charAt(0);
			switch(key) {
			case 's':
				aq.showQueue();
				break;
			case 'a':
				System.out.println("输入一个数");
				int value = sc.nextInt();
				aq.addQueue(value);
				break;
			case 'g':
				try {
					int res = aq.getQueue();
					System.out.println(res);
				} catch (Exception e) {
					// TODO: handle exception
					System.out.println(e.getMessage());
				}
			case 'h':
				try {
					int res = aq.headQueue();
					System.out.println(res);
				} catch (Exception e) {
					// TODO: handle exception
					System.out.println(e.getMessage());
				}
				break;
			case 'e':
				sc.close();
				loop = false;
				break;
			default :
				break;
			}
		}

环形队列

与队列大致一致，有略微的不同

private int maxSize;
	private int front;
	private int rear;
	private int[] arr;
	public CircleArray(int arrMaxSize) {
		maxSize = arrMaxSize;
		arr = new int[maxSize];
//		front = 0;
//		rear = 0;
		
	}
	public boolean isFull() {
		return (rear + 1) % maxSize == front;
	}
	
	public boolean isEmpty() {
		return rear == front;		
	}
	
	public void addQueue(int i) {
		if(isFull()) {
			System.out.println("队列满");
			return;
		}		
		arr[rear] = i;
		rear = (rear + 1) % maxSize;
	}
	
	public int getQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列空");
		}
		//这里需要分析出front是指向队列的第一个元素
		/*
		 * 先把front对应的值保留到一个临时变量
		 * 将front后移
		 * 将临时保存的变量返回
		 */
		int value = arr[front];
		front = (front + 1) % maxSize;
		return value;
	}
	
	public void showQueue() {
		if(isEmpty()) {
			System.out.println("队列空");
			return;
		}
		/*
		 * 思路：从front开始遍历，遍历多少个元素
		 * 需要求出当前队列有效数据的个数
		 */
		for (int i = front; i < front + size(); i++) {
			System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
		}
	}
	
	public int size() {
		return (rear + maxSize - front) % maxSize;
	}
	
	public int headQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列空");
		}
		return arr[front];
	}

单链表

实现类

class SingleLinkedList {
	/*
	 * 初始化头节点，头节点不要动
	 */
	private HeroNode head = new HeroNode(0, "", "");
	
	public HeroNode getHead() {
		return head;
	}
	public void setHead(HeroNode head) {
		this.head = head;
	}
	//得到链表长度
	public int getLength(HeroNode head) {
    	if(head.next == null) {
    		return 0;
    	}
    	int length = 0;
    	HeroNode cur = head.next;
    	while(cur != null)
    	{
    		length++;
    		cur = cur.next;
    	}
    	return length;
    }
	//合并两个有序链表
	public HeroNode addToOne(HeroNode h1, HeroNode h2) {
		if(h1 == null && h2 == null) {
			return null;
		}
		if(h1 == null) {
			return h2;
		}
		if(h2 == null) {
			return h1;
		}
		HeroNode head = null;
		if(h1.no < h2.no) {
			head = h1;
			head.next = addToOne(h1.next, h2);
		}
		else {
			head = h2;
			head.next = addToOne(h1, h2.next);
		}
		return head;
	}
	//增加链表元素
	public void add(HeroNode hn) {
//		HeroNode temp = head;
//		//遍历链表找到最后
//		while(true) {
//			if(temp.next == null) {
//				break;
//			}
//			temp = temp.next;
//		}
//		temp.next = hn;
		HeroNode temp = head;
		boolean flag = false;//标志添加的编号是否存在
		while(true) {
			if(temp.next == null) {
				break;
			}
			if(temp.next.no > hn.no) {
				break;
			}
			else if(temp.next.no == hn.no) {
				flag = true;//说明编号存在
				break;
			}
			temp = temp.next;
		}
		if(flag) {//不能添加，已存在
			System.out.println("isExisting");
		}
		else {
		hn.next = temp.next;
		temp.next = hn;
		}
	}
	
	/*
	 * 查找单链表中倒数第K个节点
	 */
	public HeroNode getKNode(int k) {
		int i = getLength(head) - k;
		HeroNode temp = head.next;
		while(i != 0) {
			temp = temp.next;
			i--;
		}
		return temp;
		
	}
	
	/*
	 * 单链表的反转
	 */
	public void reverse(HeroNode head) {
		HeroNode reverseHead = new HeroNode(0, null, null);
		if(head.next == null || head.next.next == null) {
			return;
		}
		HeroNode temp = head.next;
		HeroNode next = null;//指向当前的下一个节点
		while(temp != null) {
			next = temp.next;
			temp.next = reverseHead.next;//将next的下一个节点指向新链表的最前端			
			reverseHead.next = temp;
			temp = next;
		}
		head.next = reverseHead.next;
	}
	
	/*
	 * 修改信息
	 */
	public void update(HeroNode hn) {
		if(head.next == null)
		{
			System.out.println("链表为空");
			return;
		}
		HeroNode temp = head.next;
		boolean flag = false;
		while(true) {
			if(temp == null) {
				break;//到了链表的结束
			}
			if(temp.no == hn.no) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			temp.name = hn.name;
			temp.nickname = hn.nickname;
		}
		else {
			System.out.println("没有找到，不能修改");
		}
	}
	
	//删除节点
	public void delete(HeroNode hn) {
		HeroNode temp = head.next;
		boolean flag = false;
		while(true) {
			if(temp.next == null) {
				break;//到了链表的结束
			}
			if(temp.next.no == hn.no) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			temp.next = temp.next.next;
		}
		else {
			System.out.println("没有找到，不能删除");
		}
	}
	
	//显示链表【遍历】
	public void list() {
		//判断链表是否为空
	
	if(head.next == null) {
		System.out.println("isempty");
		return;
	}
	HeroNode temp = head.next;
	while(true) {
		if(temp == null) {
			break;
		}
		System.out.println(temp);
		//将temp后移
		temp = temp.next;
	}
}
}
/*
 *定义HeroNode,每个HeroNode对象就是一个节点
 */
class HeroNode {
	public int no;
	public String name;
	public String nickname;
	public HeroNode next;//指向下一个节点
	public HeroNode(int no, String name, String nickname) {
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}
	//为了显示方法，重写tostring
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}
}

测试类

HeroNode hero1 = new HeroNode(1, "songjiang", "jishiyu");
		HeroNode hero2 = new HeroNode(3, "ghcfg", "gfdf");
		HeroNode hero3 = new HeroNode(6, "vhthggg", "gdg");
		HeroNode hero4 = new HeroNode(2, "dgsdc", "drg");
		HeroNode hero5 = new HeroNode(5, "dgsdc", "drg");
		HeroNode hero6 = new HeroNode(8, "dgsdc", "drg");
		HeroNode hero7 = new HeroNode(4, "dgsdc", "drg");
		HeroNode hero8 = new HeroNode(7, "dgsdc", "drg");
//		HeroNode hero5 = new HeroNode(4, "5744645", "8465");
//	    SingleLinkedList sll = new SingleLinkedList();
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		SingleLinkedList singleLinkedList1 = new SingleLinkedList();
		singleLinkedList.add(hero4);
		singleLinkedList.add(hero2);
		singleLinkedList.add(hero1);
		singleLinkedList.add(hero3);
		singleLinkedList1.add(hero5);
		singleLinkedList1.add(hero6);
		singleLinkedList1.add(hero7);
		singleLinkedList1.add(hero8);
		
//		singleLinkedList.update(hero5);
//		singleLinkedList.delete(hero4);
//		singleLinkedList.list();
//		System.out.println(singleLinkedList.getLength(singleLinkedList.getHead()));
//		System.out.println(singleLinkedList.getKNode(3));
		
//		singleLinkedList.reverse(singleLinkedList.getHead());
//		singleLinkedList.list();
//		//测试用栈实现倒序打印
//		Stack<HeroNode> stack = new Stack();
//		stack.push(hero1);
//		stack.push(hero2);
//		stack.push(hero3);
//		stack.push(hero4);
//		while(stack.size() > 0) {
//			System.out.println(stack.pop());
//		}
		
		singleLinkedList.getHead().next = singleLinkedList.addToOne(singleLinkedList.getHead().next, singleLinkedList1.getHead().next);
		singleLinkedList.list();

双向链表

实现类

// 显示链表【遍历】
	public void list() {
		// 判断链表是否为空

		if (head.next == null) {
			System.out.println("isempty");
			return;
		}
		HeroNode2 temp = head.next;
		while (true) {
			if (temp == null) {
				break;
			}
			System.out.println(temp);
			// 将temp后移
			temp = temp.next;
		}
	}
    
	public void add(HeroNode2 hn) {
		HeroNode2 temp = head;
		//遍历链表找到最后
		while(true) {
			if(temp.next == null) {
				break;
			}
			temp = temp.next;
		}
		/*
		 * 形成一个双向链表
		 */
		temp.next = hn;
		hn.pre = temp;
	}
	
	/*
	 * 修改信息
	 */
	public void update(HeroNode2 hn) {
		if(head.next == null)
		{
			System.out.println("链表为空");
			return;
		}
		HeroNode2 temp = head.next;
		boolean flag = false;
		while(true) {
			if(temp == null) {
				break;//到了链表的结束
			}
			if(temp.no == hn.no) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			temp.name = hn.name;
			temp.nickname = hn.nickname;
		}
		else {
			System.out.println("没有找到，不能修改");
		}
	}
	
	//删除节点
	public void delete(int no) {
		
		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
		HeroNode2 temp = head.next;
		boolean flag = false;
		while(true) {
			if(temp == null) {
				break;//到了链表的结束
			}
			if(temp.no == no) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		/*
		 * 有风险，删最后一个节点时。
		 * 会出现空指针异常。
		 */
		if(flag) {
			temp.pre.next = temp.next;
			if (temp.next != null) {
				temp.next.pre = temp.pre;
			}
		}
		else {
			System.out.println("没有找到，不能删除");
		}
	}

环形链表

实现类

class CircleList {
    private Boy first = new Boy(-1);
    public void addBoy(int nums) {//nums做数据校验
    	if(nums < 1) {
    		System.out.println("值不正确");
    		return;
    	}
    	Boy curboy = null;//辅助指针
    	for(int i = 1; i <= nums; i++) {
    		Boy boy = new Boy(i);
    		if(i == 1) {
    			first = boy;
    			first.setNext(first);//使成环
    			curboy = first;//指向第一个
    		}else {
    			curboy.setNext(boy);
    			boy.setNext(first);
    			curboy = boy;
    		}
    	}
    }
    
    public void showBoy() {
    	if(first == null) {
    		System.out.println("链表为空");
    		return;
    	}
    	Boy curboy = first;
    	while(true) {
    		System.out.println("编号为:" + curboy.getNo());
    		if(curboy.getNext() == first) {
    			break;
    		}
    		curboy = curboy.getNext();
    	}
    }
    
    /*
     * startNo表示从第几个小孩开始数数
     * countNum表示数几下
     * nums表示最初有几个小孩
     */
    public void outList(int startNo, int countNum, int nums) {
    	if(first == null || startNo < 1 || startNo > nums) {
    		System.out.println("参数输入有误");
    		return;
    	}
    	Boy curboy = first;
    	//指向链表最后的节点
    	while(true) {
    		if(curboy.getNext() == first) {
    			break;
    		}
    		curboy = curboy.getNext();
    	}
    	//报数前first curboy同时移动k-1次
    	for(int j = 0; j < startNo - 1; j++) {
    		first = first.getNext();
    		curboy = curboy.getNext();
    	}
    	//报数时移动m-1次
    	while(true) {
    		if(curboy == first) {
    			break;
    		}
    		for(int j = 0; j < countNum - 1; j++) {
        		first = first.getNext();
        		curboy = curboy.getNext();
        	}
    		System.out.println("小孩出圈" + first.getNo());
    		first = first.getNext();
    		curboy.setNext(first);  
    	}
    	System.out.println("最后的小孩编号是:" + first.getNo());
    }
    
}

测试类

		CircleList cl = new CircleList();		cl.addBoy(10);		cl.showBoy();		cl.outList(2, 6, 10);