数据结构与算法分析(第3版)练习题-第3章-表、栈和队列

时间:2023-02-14 15:41:34

仅个人练习Java语言所记录,不足之处,请多指点。

3.9 提供对MyArrayList类的allAll方法的实现。方法addAll将由items给定的特定集合的所有项添加到MyArrayList的末端。再提供上述实现的运行时间。你使用的方法声明与Java Collections API的略有不同,形式如下:

public void addAll(Iterable<? extends AnyType> items)


package org.my.excreise;

import java.util.Iterator;

public class MyArrayList<AnyType> implements Iterable<AnyType>
{
private static final int DEFAULT_CAPACITY=10;

private int thesize;

private AnyType[] theItems;

public MyArrayList () {
doClear();
}

public void clear() {
doClear();
}


private void doClear() {
thesize=0;
ensureCapacity(DEFAULT_CAPACITY);
}

public int size() {
return thesize;
}

public boolean isEmpty() {
return size()==0;
}

public void trimToSize() {
ensureCapacity(size());
}

public AnyType get(int idx) {
if (idx<0 || idx>=size()) {
throw new ArrayIndexOutOfBoundsException();
}
return theItems[idx];
}

public AnyType set(int idx,AnyType newval) {
if (idx<0 || idx>=size()) {
throw new ArrayIndexOutOfBoundsException();
}
AnyType old=theItems[idx];
theItems[idx]=newval;
return old;
}


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];
}
}

public boolean add(AnyType xType) {
add(size(),xType);
return true;
}

public void add(int idx,AnyType xType) {
if (theItems.length==size()) {
ensureCapacity(size()*2+1);
}
for (int i = thesize; i >idx; i--) {
theItems[i]=theItems[i-1];
}
theItems[idx]=xType;
thesize++;
}
 
    public void addAll(Iterable<? extends AnyType> items) {    Iterator<? extends AnyType> iterator=items.iterator();        while(iterator.hasNext()){            add(iterator.next());        }}            public AnyType remove(int idx) {AnyType removed=theItems[idx];for (int i = idx; i < size()-1; i++) {theItems[i]=theItems[i+1];}thesize--;return removed;}        public Iterator<AnyType> iterator() {return new ArrayListIterator();}    private class ArrayListIterator implements Iterator<AnyType> {private int current=0;@Overridepublic boolean hasNext() {// TODO Auto-generated method stubreturn current<size();}         @Overridepublic AnyType next() {// TODO Auto-generated method stubif (!hasNext()) {throw new java.util.NoSuchElementException();}return theItems[current++];}public void remove() {MyArrayList.this.remove(--current);}}}

public static void main(String[] args) {
// TODO Auto-generated method stub
MyArrayList<String> list=new MyArrayList<>();
list.add("abc");
System.out.println("----------");
System.out.println(list.size());
list.addAll(new ArrayList<String>(Arrays.asList("12","34")));
System.out.println("----------");
System.out.println(list.get(list.size()-1));
}
输出:

----------
1
----------
34


3.10 提供对MyLinkedList类的removeAll方法的实现。方法removeAll将由items给定的特定集合的所有项从MyLinkedList中删除。再提供上述实现的运行时间。你使用的方法声明与Java Collections API中的略有不同,其形式如下:

public void removeAll(Iterable<? extends AnyType> items)


package org.my.excreise;

import java.util.Iterator;

public class MyLinkedList<AnyType> implements Iterable<AnyType>
{

private static class Node<AnyType>
{
public AnyType data;
public Node<AnyType> prev;
public Node<AnyType> next;
public Node(AnyType d,Node<AnyType> p,Node<AnyType> n)
{
data=d;prev=p;next=n;
}
}

public MyLinkedList()
{
doClear();
}

private Node<AnyType> beginMarker;
private Node<AnyType> endMaker;
private int theSize;
private int modCount=0;

private void doClear() {
beginMarker=new Node<AnyType>(null, null, null);
endMaker=new Node<AnyType>(null, beginMarker, null);
beginMarker.next=endMaker;
theSize=0;
modCount++;
}

public void clear() {
doClear();
}

@Override
public Iterator<AnyType> iterator() {
// TODO Auto-generated method stub
return new LinkedListIterator();
}

public int size() {
return theSize;
}

public boolean isEmpty() {
return size()==0;
}

private AnyType remove(Node<AnyType> p)
{
p.next.prev=p.prev;
p.prev.next=p.next;
theSize--;
modCount++;
return p.data;
}

public AnyType remove(int idx) {
return remove(getNode(idx));
}


private void addBefore(Node<AnyType> pNode,AnyType xType) {
Node<AnyType> newNode=new Node<>(xType, pNode.prev, pNode);
newNode.prev.next=newNode;
pNode.prev=newNode;
theSize++;
modCount++;
}

public void add(int idx,AnyType xAnyType) {
addBefore(getNode(idx, 0, size()), xAnyType);
}

public boolean add(AnyType xType) {
add(size(),xType);
return true;
}

public AnyType get(int idx) {
return getNode(idx).data;
}

public AnyType set(int idx,AnyType newVal)
{
Node<AnyType> pNode=getNode(idx);
AnyType oldval=pNode.data;
pNode.data=newVal;
return oldval;
}

private Node<AnyType> getNode(int idx,int lower,int upper)
{
Node<AnyType> pNode;
if (idx<lower || idx>upper) {
throw new IndexOutOfBoundsException();
}
if (idx<size()/2) {
pNode=beginMarker.next;
for(int i=0;i<idx;i++)
{
pNode=pNode.next;
}
}
else {
pNode=endMaker;
for(int i=size();i>idx;i--)
{
pNode=pNode.prev;
}
}
return pNode;
}

public void removeAll(Iterable<? extends AnyType> items) {
Iterator<? extends AnyType> iterator=iterator();
while (iterator.hasNext()) {
AnyType anyType = (AnyType) iterator.next();
Iterator<? extends AnyType> iterator2=items.iterator();
while (iterator2.hasNext()) {
AnyType anyType2 = (AnyType) iterator2.next();
if (anyType.equals(anyType2)) {
iterator.remove();
}
}
}
}


private Node<AnyType> getNode(int idx) {
return getNode(idx, 0, size()-1);
}

private class LinkedListIterator implements Iterator<AnyType>{

private Node<AnyType> current=beginMarker.next;
private int expectedModCount=modCount;
private boolean okToRemove=false;
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
return current!=endMaker;
}

@Override
public AnyType next() {
// TODO Auto-generated method stub
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();
}
MyLinkedList.this.remove(current.prev);
expectedModCount++;
okToRemove=false;
}

}


}


public static void main(String[] args) {
// TODO Auto-generated method stub
MyLinkedList<String> list=new MyLinkedList<>();
list.add("ab");
list.add("bc");
list.add("ef");
list.add("gh");
System.out.println("-------当前大小:"+list.size()+"-------");
list.removeAll(new ArrayList<String>(Arrays.asList("ab","gh")));
//System.out.println("-------当前大小:"+list.size()+"-------");
System.out.println(list.get(1));
}
输出:

-------当前大小:4-------
ef