《JAVA循环双链表的建立.docx》由会员分享，可在线阅读，更多相关《JAVA循环双链表的建立.docx（5页珍藏版）》请在三一文库上搜索。
1、JAVA 循环双链表的建立import java.util.Scanner; /循环双向链表的结点类class DuLNode private Object data;/存放结点值private DuLNode prior; /前驱结点的引用private DuLNode next; /后继结点的引用public DuLNode() /无参数时的构造函数this(null);public DuLNode(Object data) /构造值为 data 的结点this.data = data;this.prior = null;this.next = null;public Object get
2、Data() return data;public DuLNode getNext() return next;public DuLNode getPrior() return prior;public void setData(Object data) this.data = data;public void setNext(DuLNode next) this.next = next;public void setPrior(DuLNode prior) this.prior = prior;/双向链表类public class DuLinkListprivate DuLNode head
3、;/双向循环链表的头结点/ 双向链表的构造函数 public DuLinkList() head = new DuLNode(); / 初始化头结点head.setPrior(head);/初始化头结点的前驱和后继head.setNext(head);/ 从表尾到表头逆向建立双向链表的算法。其中 n 为该双向链表的元素个数 public DuLinkList(int n) throws Exception this();Scanner sc = new Scanner(System.in);/ 构造用于输入的对象 for (int j = 0; j < n; j+)insert(0, s
4、c.next();/生成新结点,插入到表头/*在双向循环链表的第 i 个数据元素之前插入一个值为 x 的数据元素，i 等于表长时， p 指向头结点；i 大于表长时，p=NULL。其中i取值范围为：0?i?length()。当i=0时表示在表头插入一个数据元素x,当 i=length()时表示在表尾插入一个数据元素 x*/ public void insert(int i, Object x) throws Exception DuLNode p = head.getNext();/ 初始化,p 指向首结点,j 为计数器 int j = 0;while (!p.equals(head) &
5、;& j < i) / 寻找插入位置 i p = p.getNext();/ 指向后继结点 +j;/ 计数器的值增 1if (j != i && !p.equals(head) / i 小于 0 或者大于表长throw new Exception("插入位置不合理");/输出异常DuLNode s = new DuLNode(x);/生成新结点s.setPrior(p.getPrior();p.getPrior().setNext(s);s.setNext(p);p.setPrior(s);/将双向循环链表中第 i 个数据元素删除。其中 i 取
6、值范围为：0?i?ength()-1 public void remove(int i) throws Exception DuLNode p = head.getNext();/ 初始化,p 指向首节点结点,j 为计数器 int j = 0;while (!p.equals(head) && j < i) / 寻找删除位置 i p = p.getNext();/ 指向后继结点 +j;/ 计数器的值增 1if (j != i) / i 小于 0 或者大于表长减 1throw new Exception("删除位置不合理");/ 输出异常 p.getPr
7、ior().setNext(p.getNext(); p.getNext().setPrior(p.getPrior(); /将一个已经存在的双向循环链表置成空表public void clear() head.setPrior(head);head.setNext(head);/判断当前双向循环链表是否为空public boolean isEmpty() return head.equals(head.getNext();/读取双向循环链表中的第 i 个数据元素public Object get(int i) throws Exception DuLNode p = head.getNext
8、();/ 初始化,p 指向首结点,j 为计数器 int j = 0;while (!p.equals(head) && j < i) / 从首结点向后查找，直到 p 指向第 i 个元素或 p 指向头结点p = p.getNext();/指向后继结点+j;/计数器的值增 1if (j > i | p.equals(head) / i 小于 0 或者大于表长减 1throw new Exception("第" + i + "个元素不存在");/输出异常return p.getData();/返回元素 p/求双向循环链表中的数据元素
9、个数并由函数返回其值public int length() DuLNode p = head.getNext();/初始化,p 指向首结点,length 为计数器int length = 0;while (!p.equals(head) /从首结点向后查找，直到 p 指向头结点p = p.getNext();/指向后继结点+length;/长度增 1return length;/在双向循环链表中查找值为 x 的元素，如果找到，则函数返回该元素在线性表中的位置，否则返回-1public int indexOf(Object x) DuLNode p = head.getNext();/ 初始化,
10、p 指向首结点,j 为计数器 int j = 0;while(!p.equals(head)&& !p.getData().equals(x) / 从链表中的首结点元素开始查找，直到 p.getData()指向元素 x 或到达链表的表尾p = p.getNext();/指向下一个元素+j;/计数器的值增 1if (!p.equals(head)/ 如果 p 指向表中的某一元素 return j;/ 返回 x 元素在顺序表中的位置elsereturn -1;/ x 元素不在顺序表中public void display() DuLNode node = head.getNext(
11、);/ 取出带头结点的双向链表中的首结点 while (!node.equals(head) System.out.print(node.getData() + " ");/输出数据元素的值node = node.getNext();System.out.println();public DuLNode getHead() return head;public void setHead(DuLNode head) this.head = head;/测试类public static void main(String args) throws Exception / -调用构
12、造函数-System.out.println("请输入 3 个双向循环链表中的数据元素："); DuLinkList L = new DuLinkList(3);/ 从表尾到表头逆向建立一个表长为 3 的单链表System.out.println("双向循环链表中各个数据元素："); L.display();/ -调用 length()求顺序表的长度-System.out.println("双向循环链表的长度:" + L.length();/ 输出顺序表的长度/ -调用 get(int i)取出第 i 个元素-if (L.get(2)
13、 != null)/ 取第二个元素System.out.println("双向循环链表中第 2 个元素:" + L.get(2);/ -调用 indexOf(Object x)查找 x 元素所在的位置-int order = L.indexOf("c");/求出数据元素字符串 c 在顺序表中的位置if (order != -1)System.out.println("双向循环链表中值为字符串 c 的数据元素的位置为：" + order);elseSystem.out.println("字符c不在此双向循环链表中")
14、;/-调用 remove(int i)删除数据元素-L.remove(2); /删除第二个数据元素System.out.println("删除第二个数据元素后双向循环链表中各个数据元素：");L.display();/-调用insert(int i, Object x)插入数据元素-L.insert(2, d);/在双向循环链表的第三个位置插入数据元素 dSystem.out.println("在 2 的位置插入数据元素 d 后双向循环链表中各个数据元素：");L.display();/-调用 L.clear()将顺序表置空-L.clear();System.out.println("将双向循环链表置空后，再次打印表中的元素:");/-调用 isEmpty()判断顺序表是否为空-if (L.isEmpty()System.out.println("双向循环链表为空"); else System.out.println("双向循环链表不为空,双向循环链表中各个数据元素：");L.display();