邯郸国外网站建设费用,做的最好的网站公司,公司logo查询,揭阳网站制作工具线性表接口LList#xff1a;package com.clarck.datastructure.linked;/*** 线性表接口LList#xff0c;描述线性表抽象数据类型#xff0c;泛型参数T表示数据元素的数据类型** author clarck**/public interface LList {/*** 判断线性表是否空* return*/boolean isEmpty();…线性表接口LListpackage com.clarck.datastructure.linked;/*** 线性表接口LList描述线性表抽象数据类型泛型参数T表示数据元素的数据类型** author clarck**/public interface LList {/*** 判断线性表是否空* return*/boolean isEmpty();/*** 返回线性表长度* return*/int length();/*** 返回第i(i≥0)个元素* param i* return*/T get(int i);/*** 设置第i个元素值为x* param i* param x*/void set(int i, T x);/*** 插入x作为第i个元素* param i* param x*/void insert(int i, T x);/*** 在线性表最后插入x元素* param x*/void append(T x);/*** 删除第i个元素并返回被删除对象* param i* return*/T remove(int i);/*** 删除线性表所有元素*/void removeAll();/*** 查找返回首次出现的关键字为key元素* param key* return*/T search(T key);}单链表结点类package com.clarck.datastructure.linked;/*** 单链表结点类T指定结点的元素类型** author clarck** param */public class Node {/*** 数据域保存数据元素*/public T data;/*** 地址域引用后继结点*/public Node next;/*** 构造结点data指定数据元素next指定后继结点** param data* param next*/public Node(T data, Node next) {this.data data;this.next next;}/*** 构造节点*/public Node() {this(null, null);}/*** 返回结点元素值对应的字符串*/Overridepublic String toString() {return this.data.toString();}/*** 比较两个结点值是否相等覆盖Object类的equals(obj)方法*/SuppressWarnings(unchecked)Overridepublic boolean equals(Object obj) {return obj this || obj instanceof Node this.data.equals(((Node)obj).data);}}线性表的链式表示和实现package com.clarck.datastructure.linked;/*** 线性表的链式表示和实现 带头结点的单链表类实现线性表接口** author clarck** param */public class SinglyLinkedList implements LList {/*** 头指针指向单链表的头结点*/public Node head;/*** 默认构造方法构造空单链表*/public SinglyLinkedList() {// 创建头结点data和next值均为nullthis.head new Node();}/*** 由指定数组中的多个对象构造单链表。采用尾插入构造单链表* 若elementnullJava将抛出空对象异常若element.length0构造空链表** param element*/public SinglyLinkedList(T[] element) {// 创建空单链表只有头结点this();// rear指向单链表最后一个结点Node rear this.head;for (int i 0; i element.length; i) {rear.next new Node(element[i], null);rear rear.next;}}/*** 判断单链表是否空O(1)*/Overridepublic boolean isEmpty() {return this.head.next null;}/*** 返回单链表长度O(n), 基于单链表遍历算法*/Overridepublic int length() {int i 0;// p从单链表第一个结点开始Node p this.head.next;// 若单链表未结束while (p ! null) {i;// p到达后继结点p p.next;}return i;}/*** 返回第i(≥0)个元素若i0或大于表长则返回nullO(n)*/Overridepublic T get(int i) {if (i 0) {Node p this.head.next;for (int j 0; p ! null j i; j) {p p.next;}// p指向第i个结点if (p ! null) {return p.data;}}return null;}/*** 设置第i(≥0)个元素值为x。若i0或大于表长则抛出序号越界异常若xnull不操作。O(n)*/Overridepublic void set(int i, T x) {if (x null)return;Node p this.head.next;for (int j 0; p ! null j i; j) {p p.next;}if (i 0 p ! null) {p.data x;} else {throw new IndexOutOfBoundsException(i );}}/*** 插入第i(≥0)个元素值为x。若xnull不插入。 若i0插入x作为第0个元素若i大于表长插入x作为最后一个元素。O(n)*/Overridepublic void insert(int i, T x) {// 不能插入空对象if (x null) {return;}// p指向头结点Node p this.head;// 寻找插入位置for (int j 0; p.next ! null j i; j) {// 循环停止时p指向第i-1结点或最后一个结点p p.next;}// 插入x作为p结点的后继结点包括头插入(i0)、中间/尾插入(i0)p.next new Node(x, p.next);}/*** 在单链表最后添加x对象O(n)*/Overridepublic void append(T x) {insert(Integer.MAX_VALUE, x);}/*** 删除第i(≥0)个元素返回被删除对象。若i0或i大于表长不删除返回null。O(n)*/Overridepublic T remove(int i) {if (i 0) {Node p this.head;for (int j 0; p.next ! null j i; j) {p p.next;}if (p ! null) {// 获得原对象T old p.next.data;// 删除p的后继结点p.next p.next.next;return old;}}return null;}/*** 删除单链表所有元素 Java将自动收回各结点所占用的内存空间*/Overridepublic void removeAll() {this.head.next null;}/*** 顺序查找关键字为key元素返回首次出现的元素若查找不成功返回null* key可以只包含关键字数据项由T类的equals()方法提供比较对象相等的依据*/Overridepublic T search(T key) {if (key null)return null;for (Node p this.head.next; p ! null; p p.next)if (p.data.equals(key))return p.data;return null;}/*** 返回单链表所有元素的描述字符串形式为“(,)”覆盖Object类的toString()方法O(n)*/Overridepublic String toString() {String str (;for (Node p this.head.next; p ! null; p p.next) {str p.data.toString();if (p.next ! null)str ,; // 不是最后一个结点时后加分隔符}return str ); // 空表返回()}/*** 比较两条单链表是否相等*/SuppressWarnings(unchecked)Overridepublic boolean equals(Object obj) {if (obj this)return true;if (obj instanceof SinglyLinkedList) {SinglyLinkedList list (SinglyLinkedList) obj;return equals(this.head.next, list.head.next);}return false;}/*** 比较两条单链表是否相等递归方法** param p* param q* return*/private boolean equals(Node p, Node q) {return p null q null || p ! null q ! null p.data.equals(q.data) equals(p.next, q.next);}}测试类package com.clarck.datastructure.linked;/*** 单链表的测试** author clarck**/public class SinglyLinkedList_test {public static void main(String args[]) {SinglyLinkedList lista new SinglyLinkedList();for (int i 0; i 5; i)lista.insert(i, new String((char) (A i) ));System.out.println(lista: lista.toString() length() lista.length());lista.set(3, new String((char) (lista.get(0).charAt(0) 32) ));lista.remove(0);lista.remove(3);System.out.println(lista: lista.toString());}}测试结果lista: (A,B,C,D,E,F)length()6lista: (B,C,a,F)
