产品网站建设设计方案,免费做网站的优缺点,律师事务所网站 备案,福田营销型网站建站推广外包用链式实现的线性表#xff0c;公共接口ADT跟上一篇一样 1#xff0c;有序链表 成员变量和构造函数#xff1a; privateLinearNode front;privateintcount;publicLinkedOrderedList(){ front null; count 0;实现清单#xff08;将ADT和有序链表扩展的独有操作分别作了注释公共接口ADT跟上一篇一样 1有序链表 成员变量和构造函数 private LinearNode front;private int count;public LinkedOrderedList(){ front null; count 0; 实现清单将ADT和有序链表扩展的独有操作分别作了注释 LinkedOrderedList package List;import Bag.LinearNode;public class LinkedOrderedList implements ListADT {private LinearNode front;private int count;public LinkedOrderedList() { front null; count 0; }//三种链表的接口公共操作实现是一样的 public int size() {return count; }public boolean isEmpty() {return (count 0); }public Object first() {if(size() 0){ System.out.println(链表为空没有元素);return null; }return front.getElement(); }public Object last() {if(size() 0){ System.out.println(链表为空没有元素);return null; } LinearNode last front;//遍历链表求last的代码 for(int i 0;i count-1;i) last last.getNext();return last.getElement(); }public Object removeFirst() {if(size() 0){ System.out.println(链表为空没有元素);return null; } Object result front.getElement(); front front.getNext(); count--;return result; }public Object removeLast() {if(size() 0){ System.out.println(链表为空没有元素);return null; } LinearNode last front;for(int i 0;i count-1;i) last last.getNext(); count--;//count-1自动删除最后一个结点 return last.getElement(); }public Object remove(Object element) { Object result null;if(size() 0){//如果为空 System.out.println(链表为空没有元素);return null; }else if(front.getElement().equals(element)){//如果是链表的第一个元素 result front.getElement(); front front.getNext(); count--; }else{ LinearNode pre,current; pre front;for(int i 0;i count-1;i) { current pre.getNext();if(current.getElement().equals(element)) { result current.getElement(); pre.setNext(current.getNext());//如果current到了最后一个元素getNext就是null count--;return result; } pre pre.getNext(); } } return result; }public boolean contains(Object element) { LinearNode temp front;for(int i 0;i count;i){if(temp.getElement().equals(element))return true; temp temp.getNext(); }return false; }//有序链表扩展的操作 public void add(Comparable element){ LinearNode node new LinearNode(element); LinearNode last front;for(int i 1;i count;i) last last.getNext();if(size() 0){//链为空 front node; count;return; }else if(element.compareTo(front.getElement()) 0){//插入在链首 node.setNext(front); front node; count;return; }else if(element.compareTo(last.getElement()) 0){//插入在链尾 last.setNext(node); count; }else{//插入在链中间 LinearNode current front; LinearNode next current.getNext();for(int i 0;i count-1;i){if(element.compareTo(next.getElement()) 0){ current.setNext(node); node.setNext(next); count;return; } current next; next next.getNext(); } } }public static void main(String[] args) { LinkedOrderedList list new LinkedOrderedList(); System.out.println(将0到24打乱顺序加入表因为是有序表它将自动排好序);for(int i 20;i 25;i) list.add(i);for(int i 0;i 10;i) list.add(i);for(int i 10;i 20;i) list.add(i); System.out.println(表的大小为 list.size()); System.out.println(表为空吗 list.isEmpty()); System.out.println(表的第一个元素为 list.first()); System.out.println(表的最后一个元素为 list.last()); System.out.println(\n删除第一个元素); list.removeFirst(); System.out.println(表的大小为 list.size()); System.out.println(表为空吗 list.isEmpty()); System.out.println(表的第一个元素为 list.first()); System.out.println(表的最后一个元素为 list.last()); System.out.println(\n再接着删除最后一个元素); list.removeLast(); System.out.println(表的大小为 list.size()); System.out.println(表为空吗 list.isEmpty()); System.out.println(表的第一个元素为 list.first()); System.out.println(表的最后一个元素为 list.last()); System.out.println(\n再接着删除指定元素20,15,10,5); list.remove(20); list.remove(10); list.remove(15); list.remove(5); list.remove(23); System.out.println(表的大小为 list.size()); System.out.println(表为空吗 list.isEmpty()); System.out.println(表的第一个元素为 list.first()); System.out.println(表的最后一个元素为 list.last()); }} 2无序链表 成员变量构造函数公共操作完全一样扩展的操作 LinkedUnorderedList //无序链表扩展的操作 public void addToFront(Object element){ LinearNode node new LinearNode(element); node.setNext(front); front node; count; }public void addToRear(Object element){ LinearNode last front;for(int i 0;i count-1;i) last last.getNext(); LinearNode node new LinearNode(element); last.setNext(node); count; }public void addAfter(Object after,Object element){ LinearNode temp front; LinearNode elenode new LinearNode(element);for(int index 0;index count;index){if(temp.getElement().equals(after) index ! count-1) { elenode.setNext(temp.getNext()); temp.setNext(elenode); count;return; }else if(temp.getElement().equals(after) index count-1) { LinearNode last front;for(int i 0;i count-1;i) last last.getNext(); last.setNext(elenode); count;return; } temp temp.getNext(); } } 3索引链表扩展的操作LinkedIndexedList //索引链表扩展的操作 public void add(Object element){//在表尾插入 if(size() 0) { front new LinearNode(element); count;return; } LinearNode node new LinearNode(element); LinearNode last front;for(int i 0;i count-1;i) last last.getNext(); last.setNext(node); count; }public void add(int index,Object element){ LinearNode node new LinearNode(element);if(index 0) { node.setNext(front); front node; count; }else { LinearNode pre front;for(int i 0;i index-1;i) pre pre.getNext(); LinearNode current pre.getNext(); node.setNext(current); pre.setNext(node); count; } }public void set(int index,Object element){//设置某个索引上的元素覆盖原来的不需要移动元素 LinearNode node new LinearNode(element); LinearNode temp front;for(int i 0;i index;i) temp temp.getNext(); temp.setElement(element); }public Object get(int index){//返回某个索引上的元素 LinearNode temp front;for(int i 0;i index;i) temp temp.getNext();return temp.getElement(); }public int indexOf(Object element){//返回某个元素的索引 LinearNode temp front;for(int index 0;index count;index){if(element.equals(temp.getElement()))return index; temp temp.getNext(); }return -1; }public Object remove(int index){//移除指定索引上的元素 if(index 0) { Object result front.getElement(); front front.getNext(); count--;return result; }else if(index count-1) { LinearNode last front;for(int i 0;i count;i) last last.getNext(); Object result last.getElement(); count--;return result; } else { LinearNode pre front;for(int i 0;i index-1;i) pre pre.getNext(); LinearNode current pre.getNext(); Object result current.getElement(); pre.setNext(current.getNext()); count--; return result; } }
