线性表的操作(java语言实现)

线性表的操作(java语言实现)

一、需求分析

本次实验主要完成以下内容:

  1. 线性表基本操作的实现,分别采用数组和链表结构实现线性表,实现线性表的基本操作
  2. 利用实现的线性表,存储一元n次多项式,完成多项式的输入、显示;实现多项式的加法操作

经过分析,程序主要需求如下:

  1. 输出的形式 :控制台输出
  2. 程序所能达到的功能 :用户输入多项式每一项的系数和指数,控制台打印出该多项式
  3. 测试数据

    输入 输出
    1,3 4,5,

二、概要设计

程序定义以下抽象数据类型

数据类型 说明
MyList接口 定义了操作线性表的方法,为MyArrayList和MyLinkedList定义公共的接口,实现了部分定义在Collection接口中的方法
MyArrayList类 实验所要求的线性表的顺序实现
MyLinkedList类 实验所要求的线性表的链式实现
Term类 表示多项式的每一项
Polynomial类 表示多项式,继承自MyLinkedList或MyArrayList

MyList中定义的实现线性表基本操作的方法

方法 内容
+add(index: int, e: E): void 在线性表指定的位置插入元素
+get(index: int): E 返回线性表中给定索引位置的元素
+indexOf(e: Object): int 返回该元素在表中第一次匹配到的索引
+lastIndexOf(e: E): int 返回该元素在表中最后一个匹配到的索引
+remove(index: int): E 删除表中指定位置的元素,将其后的所有元素向左移动. 删除后放返回该元素
+set(index: int, e: E): E 以新元素替换表中指定位置的元素,并返回新元素

类图.png
类图.svg

MyList接口的定义

import java.util.Collection;

public interface MyList<E> extends java.util.Collection<E> {
  /** 在指定索引处添加元素 */
  public void add(int index, E e);

  /** 返回给定索引处的元素 */
  public E get(int index);

  /**返回该元素在表中第一次匹配到的索引 若未匹配,返回-1*/
  public int indexOf(Object e);

  /**返回该元素在表中最后一个匹配到的索引 若未匹配,返回-1*/
  public int lastIndexOf(E e);

  /** 删除表中指定位置的元素 将其后的所有元素先左移动. 删除后放返回该元素*/
  public E remove(int index);

  /** 替换表中指定位置的元素,返回新元素*/
  public E set(int index, E e);

  @Override /** 在末尾添加元素 */
  public default boolean add(E e) {
    add(size(), e);
    return true;
  }

  @Override /** 若表中不含任何元素则返回true */
  public default boolean isEmpty() {
    return size() == 0;
  }

  @Override /**删除表中出现的第一个该元素,将其之后的元素向左移,返回true*/
  public default boolean remove(Object e) {
    if (indexOf(e) >= 0) {
      remove(indexOf(e));
      return true;
    } else
      return false;
  }

  @Override
  public default boolean containsAll(Collection<?> c) {
    for (Object e: c)
      if (!this.contains(e)) return false;
    return true;
  }
  
  
  @Override/** 将另一表中的所有元素添加到表中,结果符合调用则返回真 */
  public default boolean addAll(Collection<? extends E> c) {
    for (E e: c)
      this.add(e);
    
    return c.size() > 0;
  }

  
  @Override/** 从表中删除另一表中的所有元素 */
  public default boolean removeAll(Collection<?> c) {
    boolean changed = false;
    for (Object e: c) {
      if (remove(e))
        changed = true;
    }
    return changed;
  }  
  
  
  @Override/** 保留此表中和另一表中共有的元素 */
  public default boolean retainAll(Collection<?> c) {
    boolean changed = false;
    for (int i = 0; i < this.size(); ) {
      if (!c.contains(this.get(i))) {
        this.remove(get(i));
        changed = true;
      }
      else
        i++;
    }
    return changed;
  }

  @Override
  public default Object[] toArray() {
    Object[] result = new Object[size()];
    for (int i = 0; i < size(); i++) {
      result[i] = this.get(i);
    }
    return result;
  }

  @Override
  public default <T> T[] toArray(T[] a) {
    for (int i = 0; i < size(); i++) {
      a[i] = (T)this.get(i);
    }
    return a;
  }
}

顺序存储结构的实现MyArrayList.java

public class MyArrayList<E> implements MyList<E> {
  public static final int INITIAL_CAPACITY = 16;
  private E[] data = (E[])new Object[INITIAL_CAPACITY];
  private int size = 0; // Number of elements in the list

  /** Create an empty list */
  public MyArrayList() {
  }

  /** Create a list from an array of objects */
  public MyArrayList(E[] objects) {
    for (int i = 0; i < objects.length; i++)
      add(objects[i]); // Warning: don�t use super(objects)! 
  }

  @Override /** Add a new element at the specified index */
  public void add(int index, E e) {   
    ensureCapacity();

    // Move the elements to the right after the specified index
    for (int i = size - 1; i >= index; i--)
      data[i + 1] = data[i];

    // Insert new element to data[index]
    data[index] = e;

    // Increase size by 1
    size++;
  }

  /** Create a new larger array, double the current size + 1 */
  private void ensureCapacity() {
    if (size >= data.length) {
      E[] newData = (E[])(new Object[size * 2 + 1]);
      System.arraycopy(data, 0, newData, 0, size);
      data = newData;
    }
  }

  @Override /** Clear the list */
  public void clear() {
    data = (E[])new Object[INITIAL_CAPACITY];
    size = 0;
  }

  @Override /** Return true if this list contains the element */
  public boolean contains(Object e) {
    for (int i = 0; i < size; i++)
      if (e.equals(data[i])) return true;

    return false;
  }

  @Override /** Return the element at the specified index */
  public E get(int index) {
    checkIndex(index);
    return data[index];
  }

  private void checkIndex(int index) {
    if (index < 0 || index >= size)
      throw new IndexOutOfBoundsException
        ("Index: " + index + ", Size: " + size);
  }
  
  @Override /** Return the index of the first matching element 
   *  in this list. Return -1 if no match. */
  public int indexOf(Object e) {
    for (int i = 0; i < size; i++)
      if (e.equals(data[i])) return i;

    return -1;
  }

  @Override /** Return the index of the last matching element 
   *  in this list. Return -1 if no match. */
  public int lastIndexOf(E e) {
    for (int i = size - 1; i >= 0; i--)
      if (e.equals(data[i])) return i;

    return -1;
  }

  @Override /** Remove the element at the specified position 
   *  in this list. Shift any subsequent elements to the left.
   *  Return the element that was removed from the list. */
  public E remove(int index) {
    checkIndex(index);
    
    E e = data[index];

    // Shift data to the left
    for (int j = index; j < size - 1; j++)
      data[j] = data[j + 1];

    data[size - 1] = null; // This element is now null

    // Decrement size
    size--;

    return e;
  }

  @Override /** Replace the element at the specified position 
   *  in this list with the specified element. */
  public E set(int index, E e) {
    checkIndex(index);
    E old = data[index];
    data[index] = e;
    return old;
  }

  @Override
  public String toString() {
    StringBuilder result = new StringBuilder("[");

    for (int i = 0; i < size; i++) {
      result.append(data[i]);
      if (i < size - 1) result.append(", ");
    }

    return result.toString() + "]";
  }

  /** Trims the capacity to current size */
  public void trimToSize() {
    if (size != data.length) { 
      E[] newData = (E[])(new Object[size]);
      System.arraycopy(data, 0, newData, 0, size);
      data = newData;
    } // If size == capacity, no need to trim
  }

  @Override /** Override iterator() defined in Iterable */
  public java.util.Iterator<E> iterator() {
    return new ArrayListIterator();
  }
 
  private class ArrayListIterator 
      implements java.util.Iterator<E> {
    private int current = 0; // Current index 

    @Override
    public boolean hasNext() {
      return (current < size);
    }

    @Override
    public E next() {
      return data[current++];
    }

    @Override
    public void remove() {
      MyArrayList.this.remove(current);
    }
  }
  
  @Override /** Return the number of elements in this list */
  public int size() {
    return size;
  }


  
}

链式存储结构的实现MyLinkedList.java

import java.util.Iterator;

public class MyLinkedList<E> implements MyList<E> {
    protected Node<E> head;
    private Node<E> tail;
    protected int size = 0;// 链表的元素个数

    /** 创建空链表 */
    public MyLinkedList() {
    }

    /** 泛型对象数组创建链表 */
    public MyLinkedList(E[] objects) {
        for (int i = 0; i < objects.length; i++) add(objects[i]);
    }

    public E getFirst() {
        return size!=0? head.element:null;
    }

    public E getLast() {
        return size!=0? tail.element:null;
    }

    public void addFirst(E e) {
        Node<E> newNode = new Node<>(e); // 创建新节点
        newNode.next = head; // 将新节点与head连接
        head = newNode; // head指向新节点
        size++; // 增加链表的长度
        if (tail == null) tail = head;
    }

    public void addLast(E e) {
        Node<E> newNode = new Node<>(e);
        if (tail == null)  head = tail = newNode;
        else {
            tail.next = newNode; // 将新节点与链表末尾的节点相连
            tail = tail.next; // 尾节点指向末尾
        }
        size++;
    }

    @Override /** 向指定位置添加新元素,头节点的索引为0 */
    public void add(int index, E e) {
        if (index == 0) addFirst(e);
        else if (index >= size) addLast(e);
        else {
            Node<E> current = head;
            for (int i = 1; i < index; i++) current = current.next;// 找到要插入的索引的前一个节点
            Node<E> temp = current.next;// 保存要插入的索引处的节点
            current.next = new Node<>(e);// 前一个节点指向新节点
            (current.next).next = temp;// 新节点next指向原来的节点
            size++;
        }
    }

    /** 删除头节点并返回被删除的节点中的对象 */
    public E removeFirst() {
        if (size == 0) return null;
         else {
            Node<E> temp = head;// 保存头节点
            head = head.next;// 头节点指向下一个节点
            size--;
            if (head == null) tail = null;// 若只有一个节点,删除头节点后tail为null
            return temp.element;
        }
    }

    /** 删除末尾节点并返回被删除的节点中的对象 */
    public E removeLast() {
        if (size == 0) return null;
        else if (size == 1) {
            Node<E> temp = head;
            head = tail = null;
            size = 0;
            return temp.element;
        } else {
            Node<E> current = head;
            for (int i = 0; i < size - 2; i++) current = current.next;// 找到倒数第二个节点
            Node<E> temp = tail;
            tail = current;
            tail.next = null;
            size--;
            return temp.element;
        }
    }

    @Override
    public E get(int index) {
        if (index < 0 || index > size - 1) return null;
        Node<E> current = head;
        for (int i = 0; i < index; i++) current = current.next;
        return current.element;
    }

    @Override
    public int indexOf(Object o) {
        Node<E> current = head;
        for (int i = 0; i < size; i++) {
            if (current.element.equals(o))
                return i;
            current = current.next;
        }

        return -1;
    }

    @Override
    public int lastIndexOf(E e) {
        int lastIndex = -1;
        Node<E> current = head;
        for (int i = 0; i < size; i++) {
            if (current.element.equals(e))
                lastIndex = i;
            current = current.next;
        }
        return lastIndex;
    }

    @Override
    public E remove(int index) {
        if (index < 0 || index >= size)  return null;
        else if (index == 0) return removeFirst();
        else if (index == size - 1) return removeLast();
        else {
            Node<E> previous = head;
            for (int i = 1; i < index; i++) {
                previous = previous.next;
            }
            Node<E> current = previous.next;
            previous.next = current.next;
            size--;
            return current.element;
        }
    }

    @Override
    public E set(int index, E e) {
        if (index < 0 || index > size - 1)  return null;
        Node<E> current = head;
        for (int i = 0; i < index; i++) current = current.next;
        E temp = current.element;
        current.element = e;
        return temp;
    }

    @Override
    public void clear() {
        size = 0;
        head = tail = null;
    }

    @Override
    public boolean contains(Object o) {
        Node<E> current = head;
        for (int i = 0; i < size; i++) {
            if (current.element.equals(o))
                return true;
            current = current.next;
        }
        return false;
    }

    @Override
    public Iterator<E> iterator() {
        return new LinkedListIterator();
    }

    @Override
    public int size() {
        return size;
    }

    @Override /** Override toString() to return elements in the list */
    public String toString() {
        StringBuilder result = new StringBuilder("[");

        Node<E> current = head;
        for (int i = 0; i < size; i++) {
            result.append(current.element);
            current = current.next;
            if (current != null) {
                result.append(", "); // Separate two elements with a comma
            } else {
                result.append("]"); // Insert the closing ] in the string
            }
        }

        return result.toString();
    }

    private class LinkedListIterator 
        implements java.util.Iterator<E> {
      private Node<E> current = head; // Current index 
      
      @Override
      public boolean hasNext() {
        return (current != null);
      }

      @Override
      public E next() {
        E e = current.element;
        current = current.next;
        return e;
      }

      @Override
      public void remove() {
        // Left as an exercise
      }
    }

    class Node<E> {
        E element;
        Node<E> next;
  
        public Node(E element) {
          this.element = element;
        }
      }

}

用于表示多项式中每一项的Term类Term.java

public class Term {
    private int exof;
    private double coef;

    public Term( double coef,int exof) {
      this.exof = exof;
      this.coef = coef;
    }

    @Override
    public String toString() {
      return coef + "x^"+ exof;
    }

    public int getExof() {
      return exof;
    }

    public void setExof(int exof) {
      this.exof = exof;
    }

    public double getCoef() {
      return coef;
    }

    public void setCoef(double coef) {
      this.coef = coef;
    }

  }

继承自MyLinkedList的类Polynomial.java

public class Polynomial extends MyLinkedList<Term> {

    public Polynomial() {
    }

    public Polynomial(Term[] objects) {
        super(objects);
    }

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        Node<Term> current = head;
        for (int i = 0; i < size; i++) {
            result.append(current.element);
            current = current.next;
            if (current != null) result.append("+"); // 加号分隔多项式的项
        }
        return result.toString();
    }

    public static void main(String[] args) {
        Polynomial poly = new Polynomial();
        poly.add(new Term(1, 2));
        poly.add(new Term(2, 4));
        poly.add(new Term(2, 4));
        System.out.println(poly.toString());
      }
}

评论

暂无评论