循环单链表操作
1.CircleLinkList 类实现循环单链表基本操作
1 package com.neusoft.link; 2 import com.neusoft.List.IList; 3 public class CircleLinkList implements IList{ 4 public Node head; 5 public CircleLinkList() { 6 // TODO 初始化 7 head=new Node();//初始化头结点 8 head.next=head; 9 } 10 @Override 11 public void clear() { 12 // TODO 清空 13 head.next=head; 14 } 15 @Override 16 public boolean isEmpty() { 17 // TODO 判空 18 return head.next.equals(head); 19 } 20 @Override 21 public int length() { 22 // TODO 长度 23 Node p =head.next; 24 int length=0; 25 while (!p.equals(head)) { 26 p=p.next; 27 length++; 28 } 29 return length; 30 } 31 @Override 32 public Object get(int i) { 33 // TODO 读取带头结点的循环链表中第i个数据元素 34 Node p=head.next; 35 int j=0; 36 while (!p.equals(head)&&j<i) { 37 p=p.next; 38 j++; 39 } 40 if (j>i||p.equals(head)) { 41 System.out.println("第"+i+"个元素不存在！"); 42 } 43 return p.data; 44 } 45 46 @Override 47 public void insert(int i, Object x) { 48 // TODO 带头结点的循环链表中第i个节点之前插入一个值为x的元素 49 Node p = head; 50 int j=-1;//第i个节点前驱位置 51 while ((!p.equals(head)||j==-1)&&j<i-1) { 52 p=p.next; 53 j++; 54 } 55 if (j>i-1||(p.equals(head)&&j!=-1)) { 56 System.out.println("插入位置不合法！"); 57 } 58 Node s =new Node(x); 59 s.next=p.next; 60 p.next=s; 61 } 62 63 @Override 64 public void remove(int i) { 65 // TODO 移除循环单链表中第i个元素的节点，注意i的范围 66 Node p=head;//p指向要删除节点的前驱节点 67 int j=-1; 68 while ((!p.next.equals(head)||j==-1)&&j<i-1) {//找前驱元素 69 p=p.next; 70 j++; 71 } 72 if (j>i-1||(p.next.equals(head)&&j!=-1)) { 73 System.out.println("删除位置不合法！"); 74 } 75 p.next=p.next.next; 76 } 77 78 @Override 79 public int indexOf(Object x) { 80 // TODO 查找值为x的元素，返回位置 81 Node p =head.next;//p指向首节点 82 int j=0; 83 while ((!p.equals(head))&&(!p.data.equals(x))) { 84 p=p.next; 85 j++; 86 } 87 if (!p.equals(head)) { 88 return j; 89 }else { 90 return -1; 91 } 92 } 93 @Override 94 public void display() { 95 // TODO 输出元素 96 Node p =head.next; 97 while (!p.equals(head)) { 98 System.out.print(p.data+" "); 99 p=p.next; 100 } 101 System.out.println(); 102 } 103 104 @Override 105 public int remove(Object i) { 106 // TODO Auto-generated method stub 107 return 0; 108 } 109 110 }
2.循环单链表的测试
1 package com.neusoft.link; 2 /** 3 * @author zhao-chj 4 * 测试循环单链表 5 */ 6 public class DebugCircleLinkList { 7 public static void main(String[] args) { 8 //-----------初始化循环链表中各个元素--------- 9 CircleLinkList L = new CircleLinkList(); 10 int n = 8; 11 for (int i = 0; i <n ; i++) { 12 L.insert(i, i); 13 } 14 System.out.println("循环链表的各个元素为："); 15 L.display(); 16 //----------调用length()求长度----------- 17 int length = L.length(); 18 System.out.println("循环链表长度为："+length); 19 //----------调用get(int i)取出第i个元素---- 20 if (L.get(2) !=null ) { 21 System.out.println("循环链表中第2个元素为"+L.get(2)); 22 } 23 //----------index(Object x)查找x所在的位置-------- 24 int order = L.indexOf('c'); 25 if (order!=-1) { 26 System.out.println("c元素与的位置为" + order); 27 }else { 28 System.out.println("字符c不在此链表中"); 29 } 30 //-----------调用remove(i)删除元素--------------- 31 L.remove(2); 32 System.out.println("移除数据元素2后循环链表中的各个元素为:"); 33 L.display(); 34 //-----------调用insert(int i，Object x)插入元素------------ 35 L.insert(3,'d'); 36 System.out.println("在第3个位置上插入元素d后的显示输出为："); 37 L.display(); 38 //----------调用L.clear()将循环链表置空------------------ 39 L.clear(); 40 System.out.println("循环链表执行了置空操作"); 41 //-----------调用isEmpty()查看循环链表是否为空------ 42 if (L.isEmpty()) { 43 System.out.println("循环链表为空"); 44 }else { 45 System.out.println("循环链表不为空,循环链表中各个元素为："); 46 L.display(); 47 } 48 } 49 }
3.测试结果
