数据结构实战java实现线性表

news/2024/11/24 13:53:43/

此方法参照了《数据结构与算法分析,java语言描述》

顺序表实现

接口分析

接口1

Iterable<AnyType>
此接口来自于java.lang.iterable
接口定义的方法

 iteratorIterator<T> iterator()返回一个在一组 T 类型的元素上进行迭代的迭代器。返回:一个迭代器。 

接口2

java.util.Iterator<AnyType>
接口定义的方法

 hasNextboolean hasNext()如果仍有元素可以迭代,则返回 true。(换句话说,如果 next 返回了元素而不是抛出异常,则返回 true)。返回:如果迭代器具有多个元素,则返回 truenextE next()返回迭代的下一个元素。返回:迭代的下一个元素。 抛出:NoSuchElementException - 没有元素可以迭代。 removevoid remove()从迭代器指向的 collection 中移除迭代器返回的最后一个元素(可选操作)。每次调用 next 只能调用一次此方法。如果进行迭代时用调用此方法之外的其他方式修改了该迭代器所指向的 collection,则迭代器的行为是不确定的。抛出:UnsupportedOperationException - 如果迭代器不支持 remove 操作。 IllegalStateException - 如果尚未调用 next 方法,或者在上一次调用 next 方法之后已经调用了 remove 方法。 
public class MyArrayList<AnyType> implements Iterable<AnyType> {//默认容量为10private static final int DEFAULT_CAPACITY = 10;private int theSize;private AnyType [] theItems;//初始化listpublic MyArrayList() {clear();}//设定初始尺寸,和缓冲区大小public void clear() {theSize = 0;ensureCapacity( DEFAULT_CAPACITY );}//返回现在的列表大小public int size() {return theSize;}//列表为空返回true,否则返回falsepublic boolean isEmpty() {return size() == 0;}//设置缓冲区大小public void trimToSize() {ensureCapacity( size() );}//得到索引对象,错误则弹出索引错误public AnyType get(int index) {if (index < 0 || index >= size())//throw 类似于python的raise用法throw new ArrayIndexOutOfBoundsException();return theItems[index];}//为列表按索引加入新的对象public AnyType set(int index, AnyType newValue) {if (index < 0 || index >= size())throw new ArrayIndexOutOfBoundsException();AnyType old = theItems[index];theItems[index] = newValue;return old;        }//设置新的缓冲区大小,如果输入值小于列表长度则啥也不干,直接返回,//否则建立一个更大的AnyType组,并将旧值转移到新组上public void ensureCapacity( int newCapacity ) {if ( newCapacity < theSize )return;AnyType [] old = theItems;theItems = (AnyType []) new Object[newCapacity];for (int i = 0; i < size(); i++)theItems[ i ] = old[ i ];}//类似于python的append方法public boolean add( AnyType value) {add( size(), value);return true;}//线性表的插入方法public void add( int index, AnyType value ) {if ( theItems.length == size() )//空间满了就将列表空间扩充为原2倍加1ensureCapacity( size() * 2 + 1 );//给索引地址腾位置for ( int i = theSize; i > index; i-- )theItems[i] = theItems[i-1];theItems[index] = value;theSize++;           }//从列表中移除索引所指向的值并返回此值public AnyType remove( int index ) {AnyType removedItem = theItems[ index ];//补上空隙for ( int i = index; i < size() - 1; i++ )theItems[i] = theItems[ i+1 ];theSize--;return removedItem;}public java.util.Iterator<AnyType> iterator() {return new ArrayListIterator();       }//一个内部类,实现可迭代算法private class ArrayListIterator implements java.util.Iterator<AnyType> {private int current = 0;//判断是否还有下一个值public boolean hasNext() {return current < size();}//返回列表中下一个值public AnyType next() {if ( !hasNext() )throw new java.util.NoSuchElementException();// i=0; j=i++ ;  此时j=0, i=1.return theItems[ current++ ];}public void remove() {// i=0; j= ++i; 此时 j=1, i=1MyArrayList.this.remove( --current );}}}

测试代码

    public static void main(String[] args) {MyArrayList  test = new MyArrayList();test.add(10);test.add(11);test.add(12);test.add("anything");for (int i = 0; i < test.size(); i++)System.out.println(test.get(i));java.util.Iterator it = test.iterator();while (it.hasNext()) {System.out.println(it.next());}

运行结果

10
11
12
anything
10
11
12
anything

写法分析

内部类实现迭代器,它可以直接访问主类中的变量,所以达到一个较好的结果。
如果不采用内部类的话,需要显式的传递结果不利于函数的抽象性。

链表实现

将要实现一个双链表,以及他的方法
双链表的组成
每个元素是这样的
这里写图片描述
中间为所存储的元素,俩边的指针指向上一个元素和下一个元素。(而在计算机内存中,例如我们规定指针长度16位bit,中间16位bit,那么在某段内存中前后16位比特所储存的数是一个元素的内存地址,中间16位比特则是元素的内容)

public class MyLinkedList<AnyType> implements Iterable<AnyType> {//此内部类构建双向链表中的每一个元素private static class Node<AnyType> {public Node( AnyType d, Node<AnyType> p, Node<AnyType> n) {data = d;prev = p;next = n;}public AnyType data;public Node<AnyType> prev;public Node<AnyType> next;}//初始化MyLinkedList对象public MyLinkedList() {clear();}//创建链表的头元素,和尾元素public void clear() {beginMarker = new Node<AnyType>( null, null, null );endMarker = new Node<AnyType>( null, beginMarker, null ); beginMarker.next = endMarker;theSize = 0;modCount++;}//返回链表有多少元素public int size() {return theSize;}public boolean isEmpty() {return size() == 0;}//链表的append方法public boolean add( AnyType value ) {add( size(), value);return true;}//链表的插入方法public void add( int index, AnyType value) {addBefore( getNode( index ), value ); }//返回索引值public AnyType get( int index ) {return getNode( index ).data;}//为索引点赋上新值public AnyType set( int index, AnyType newValue ) {Node<AnyType> p = getNode( index );AnyType oldValue = p.data;p.data = newValue;return oldValue;       }//移除索引值并返回它public AnyType remove( int index ) {return remove( getNode( index ));}//将一个数据构建为一个 Node , 然后 它放到索引 元素之前 private void addBefore ( Node<AnyType> p, AnyType value) {Node<AnyType> newNode = new Node<AnyType>(value, p.prev, p);newNode.prev.next = newNode;p.prev = newNode;theSize++;modCount++;       }//移除 参数所代表的Node元素,并返回参数所代表的Node元素数据private AnyType remove( Node<AnyType> p) {p.next.prev = p.prev;p.prev.next = p.next;theSize--;modCount++;return p.data;      }//返回索引值所代表的 Node对象private Node<AnyType> getNode( int index) {Node<AnyType> p;if ( index < 0 || index > size())throw new IndexOutOfBoundsException();if ( index < size() / 2 ) {p = beginMarker.next;for ( int i = 0; i < index; i++ )p = p.next;}else {p = endMarker;for ( int i = size(); i > index; i-- )p = p.prev;}return p;       }public java.util.Iterator<AnyType> iterator() {return new LinkedListIterator();}private class LinkedListIterator implements java.util.Iterator<AnyType> {private Node<AnyType> current =beginMarker.next;private int expectedModCount = modCount;private boolean okToRemove = false;public boolean hasNext() {return current != endMarker;}public AnyType next() {if ( modCount != expectedModCount )throw new java.util.ConcurrentModificationException();if (!hasNext() )throw new java.util.NoSuchElementException();AnyType nextItem = current.data;current = current.next;okToRemove =true;return nextItem;}public void remove() {if ( modCount != expectedModCount )throw new java.util.ConcurrentModificationException();if ( !okToRemove )throw new IllegalStateException();//this 类似于python的selfMyLinkedList.this.remove( current.prev );okToRemove = false;expectedModCount++;}}private int theSize;private int modCount = 0;private Node<AnyType> beginMarker;private Node<AnyType> endMarker;}

接口分析

与顺序实现接口相同

测试代码

    //测试代码public static void main(String[] args) {MyLinkedList test = new MyLinkedList();test.add(1);test.add(2);test.add(1, "插入");for (int i = 0; i < test.size(); i++)System.out.println(test.get(i));}

输出结果

1
插入
2

写法分析

对于java这样的面对对象语言,链表的实现显得非常直接明了。在高层的抽象层面链表可以看做是一个内部嵌套了所有值得对象。


http://www.ppmy.cn/news/534399.html

相关文章

冒泡排序java

时间复杂度&#xff1a;O(n^2)若原数组本身有序&#xff0c;只需n-1次比较就可完成。若是倒序&#xff0c;比较次数为(n-1)(n-2)(n-3)…1 n(n-1)/2,交换次数和比较次数等值。 public class BubbleSort {public static <AnyType extends Comparable<? super AnyType>…

1.5.5--1.5.6泛型static方法和类型限界、implement和extends的区别

1.5.5泛型static方法 编程时候使用特定类型出现以下情况&#xff1a; 1、该特定类型用做返回类型 2、该类型用在多于一个的参数类型中 3、该类型用于声明一个局部变量 必须要声明一种带有若干类型参数的显示泛型方法。 public static <AnyType> boolean contains( AnyT…

实现 LinkedList

使用 LinkedList 泛型类实现 MytLinkedList&#xff0c;以避免与库中的相关类混淆 定期整理点滴&#xff0c;完善自己&#xff0c;今后给洋哥挣钱&#xff0c;陪伴着让我的小宝贝发自内心爱上笑&#xff0c;加油吧 import java.util.ConcurrentModificationException; import j…

C++ Primer Plus书之--C++函数模版及模板重载

函数模板 函数模板允许以任意类型的方式来定义函数, 例如:可以这样建立一个交换模板(交换两个参数的数值) // 建立一个模板, 并将类型命名为AnyType, 关键字template是必须的 // 类型名AnyType可以任意选择, 只要遵守C命名规则即可. 例如T. // typename也是必须的, 但是可以用…

谈一谈个人对于java内部类的理解

谈一谈个人对于java内部类的理解 内部类分为非静态内部类和静态内部类&#xff0c;在这里我就他们在java中的应用谈一谈个人的理解 非静态内部类 非静态内部类也就是普通的内部类&#xff0c;参考ArrayList的源码&#xff0c;其中就用到了非静态内部类。 &#xff08;下面是…

【C++】第五章 模板

该文章内容整理自《C Primer Plus&#xff08;第6版&#xff09;》、《Effective C&#xff08;第三版&#xff09;》、以及网上各大博客 文章目录 函数模板类模板模板别名可变参数模板 函数模板 函数模板是通用的函数描述&#xff0c;即使用泛型来定义函数。以类型作为参数传…

oracle plsql index_by表 clear,oracle中pl/sql记录与index-by表

其他资料&#xff1a; 标量数据类型 Number系列及其子类型 Char系列及其子类型 Date等比列及其子类型 Interval系列 (oracle 9i 特有 ) Timestamp 系列 (oracle 9i 特有 ) MSLABEL 系列 复合数据类型 记录类型 (record) 、 Index-By 表 嵌套表、 Varray 对象数据类型 Object 类…

插入排序(Insertsort)之Java实现

目录(?)[] 插入排序算法介绍 排序算法是最简单的算法&#xff0c;也是最基本的算法。顾名思义&#xff0c;插入排序就是把当前待排序的元素插入到一个已经排好序的列表里面。 一个非常形象的例子就是右手抓取一张扑克牌&#xff0c;并把它插入左手拿着的排好序的扑克里面。插入…