数据结构之循环链表

- 日理万妓 2022-08-11 12:28 176阅读 0赞

package com.zhiru;
    
    /*
     * 循环链表例子
     */
    public class CircularList {
    
    	private LinkNode first, last;// 头尾指针.
    
    	CircularList() {
    		first = new LinkNode();
    		last = null;
    
    	}
    
    	CircularList(int d) {
    		first = last = new LinkNode(d);
    		System.out.print("first.data=" + first.data + "\n");
    		System.out.print("last.data=" + last.data + "\n");
    	}
    
    	/*
    	 * 链表结点类
    	 */
    	class LinkNode {
    		int data;
    		LinkNode link;
    
    		LinkNode() {
    			link = null;
    		}
    
    		LinkNode(int d) {
    			data = d;
    			link = null;
    		}
    	}
    
    	// 是否为空
    	public boolean isEmpty() {
    		return first == null;
    	}
    
    	// 获取链表长度
    	public int length() {
    		LinkNode l = first;
    		int count = 0;
    		if (l == null)
    			return 0;
    		while (l.link != last.link) {
    			count++;
    			l = l.link;
    		}
    		return count;
    	}
    
    	private LinkNode getFirst() {
    		return first;
    	}
    
    	private LinkNode getLast() {
    		return last;
    	}
    
    	// 获取头结点数据值
    	public int getFirstData() {
    		return getFirst().data;
    	}
    
    	// 获取尾结点值
    	public int getLastData() {
    		return getLast().data;
    	}
    
    	public int getData(int index) {
    		return locate(index).data;
    	}
    
    	public LinkNode locate(int index) {
    		LinkNode l = first;
    		int i = 0;
    		if (l != null && index >= 1 && index <= length()) {
    			while (l.link != last.link) {
    				i++;
    				l = l.link;
    				if (i == index)
    					break;
    			}
    			return l;
    		}
    		return null;
    	}
    
    	public void setData(int index, int data) {
    		locate(index).data = data;
    	}
    
    	/*
    	 * 将值val插入到index后
    	 */
    	public void insert(int index, int val) {
    		LinkNode l = locate(index);
    		LinkNode newNode = new LinkNode(val);
    
    		if (l != last) {
    			newNode.link = l.link;
    			l.link = newNode;
    		} else {
    
    			newNode.link = last.link;
    			last.link = newNode;
    			last = newNode;
    		}
    	}
    
    	/*
    	 * 删除index处的结点
    	 */
    	public void delete(int index) {
    		LinkNode l = locate(index);
    		l.data = l.link.data;// 用它的下个节点的值覆盖它的值
    		l.link = l.link.link;// 将它的下个节点删掉，相当于将其删除
    	}
    
    	/*
    	 * 人数n 报数值m
    	 */
    	// public void josephus(CircularList cl, int n, int m) {
    	//
    	// LinkNode p = cl.locate(1), pre = null;
    	// int i, j;
    	// for (i = 0; i < n - 1; i++) {
    	// for(j=1;j<m;j++){
    	// pre=p;
    	// p=p.link;
    	// }
    	// prt("出列的人："+p.data);
    	// pre.link=p.link;
    	// p=pre.link;
    	// }
    	// }
    
    	public void buildLink(int[] a) {
    		LinkNode newNode;
    		if (a != null) {
    			int i = 0;
    			while (i < a.length) {
    				newNode = new LinkNode(a[i]);
    				last.link = newNode;
    				last = newNode;
    				i++;
    			}
    			last.link = first;
    		}
    		// return first;// return first
    	}
    
    	public void printList() {
    		LinkNode l = last.link;
    		while (l.link != last.link) {
    			System.out.print(l.link.data + " ");
    			l = l.link;
    		}
    	}
    
    	public static void prt(String s) {
    		System.out.println(s);
    	}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    
    		CircularList cl = new CircularList(0);
    		// CircularList c2 = new CircularList(0);
    		int[] a = { 1, 2, 3, 4, 5, 6, 7 };
    		cl.buildLink(a);
    		prt("头结点值:" + cl.getFirstData() + "\n");
    		prt("尾结点值:" + cl.getLastData() + "\n");
    		prt("链表长度:" + cl.length() + "\n");
    		prt("获取第3个" + cl.getData(3) + " " + "获取第7个值" + cl.getData(7) + "\n");
    		cl.insert(1, 100);
    		cl.insert(cl.length(), 10);
    		prt("链表长度:" + cl.length() + "\n");
    		cl.printList();
    		cl.delete(4);
    		prt("链表长度:" + cl.length() + "\n");
    		cl.printList();
    		// int[]b={1,2,3,4,5,6,7,8};
    		// c2.buildLink(b);
    		// cl.josephus(c2, 8, 3);
    	}
    
    }

first.data=0  
last.data=0  
头结点值:0  
  
  
尾结点值:7  
  
  
链表长度:7  
  
  
获取第3个3 获取第7个值7  
  
  
链表长度:9  
  
  
1 100 2 3 4 5 6 7 10 链表长度:8  
  
  
1 100 2 4 5 6 7 10