Oppgavesett 3
Fra Hiofwiki
Innhold |
[rediger]
Gruppe 4 og N+1
[rediger]
Oppgave 3.1
import java.util.Iterator;
import java.io.*;
import java.util.*;
public class SortertMengde <E extends Comparable<? super E>> implements Mengde<E>{
LinkedList<E> liste = new LinkedList<E>();
public boolean leggTil(E element) {
int i = 0;
for(i=0; i<liste.size();i++)
{
if(liste.get(i).compareTo(element)>0)
{
liste.add(i,element);
break;
}
}
if(i == liste.size()){
liste.add(element);
}
return true;
}
public boolean leggTilAlle(Mengde<? extends E> mengde) {
Iterator<E> iter = (Iterator<E>) mengde.iterator();
while(iter.hasNext())
{
E ting = iter.next();
leggTil(ting);
}
return true;
}
public Mengde<E> union(Mengde<? extends E> mengde) {
throw new UnsupportedOperationException("Not supported yet.");
}
public Mengde<E> differanse(Mengde<? extends E> mengde) {
throw new UnsupportedOperationException("Not supported yet.");
}
public Mengde<E> snitt(Mengde<? extends E> mengde) {
throw new UnsupportedOperationException("Not supported yet.");
}
public E fjern(E element) {
throw new UnsupportedOperationException("Not supported yet.");
}
public boolean erTom() {
throw new UnsupportedOperationException("Not supported yet.");
}
public int antall() {
return liste.size();
}
public boolean inneholder(E element) {
throw new UnsupportedOperationException("Not supported yet.");
}
private class SortertMengdeIterator implements Iterator<E>
{
private int pos;
public boolean hasNext() {
return (pos < liste.size());
}
public E next() {
return liste.get(pos++);
}
public void remove() {
throw new UnsupportedOperationException("Not supported yet.");
}
}
public Iterator<E> iterator() {
return new SortertMengdeIterator();
}
}
[rediger]
Oppgave 3.2
package oppgavesett3;
import forelesning.LenketMengde;
import java.util.Iterator;
public class MySingleLinkedList<E> {
private int antall;
private Node start;
public void leggTil(E element){
boolean leggesTil = !inneholder(element);
if (leggesTil){
start = new Node(element,start);
antall++;
}
}
public boolean inneholder(E element) {
boolean funnet = false;
Iterator<E> it = iterator();
while (it.hasNext() && !funnet){
E verdi = it.next();
if (verdi.equals(element))
funnet = true;
}
return funnet;
}
public int antall(){
return antall;
}
public E fjern(E element){
E retur = null;
Node p, q;
boolean funnet = false;
if (erTom()){
//Kast unntak
}
//er det første element i listen som skal slettes?
if (start.verdi.equals(element)){
retur = start.verdi;
start = start.neste;
}
else {
// hvis ikke må vi lete oss frem til noden som skal slettes, og ta
// vare på referansen til noden _før_ den som skal slettes.
q = start;
p = start.neste;
while(p != null && !funnet ){
if (p.verdi.equals(element))
funnet = true;
else {
q = p;
p = p.neste;
}
}
if (!funnet ){
// kast unntak
}
retur = p.verdi;
q.neste = p.neste;
}
return retur;
}
public Iterator<E> iterator() {
return new LenketMengdeIterator();
}
public boolean erTom() {
return (antall == 0);
}
private class Node {
private E verdi;
private Node neste;
private Node(E verdi, Node neste){
this.verdi = verdi;
this.neste = neste;
}
}
private class LenketMengdeIterator implements Iterator<E> {
private Node p;
public LenketMengdeIterator(){
p = start;
}
public boolean hasNext() {
return (p != null);
}
public E next() {
E verdi = p.verdi;
p = p.neste;
return verdi;
}
public void remove() {
throw new UnsupportedOperationException("Not supported yet.");
}
}
}
</code>
[rediger]
Oppgave 3.3
package oppgavesett3;
import forelesning.LenketMengde;
import java.lang.reflect.Array;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Random;
public class TestMySingleLinkedList {
private MySingleLinkedList myList;
public TestMySingleLinkedList() {
myList = new MySingleLinkedList();
settInn(10);
System.out.println("Lista forlengs");
lesUt();
System.out.println("Lista baklengs");
lesUtBaklengs();
}
public static void main(String[] args) {
TestMySingleLinkedList testMySingleLinkedList = new TestMySingleLinkedList();
}
private void settInn(int i) {
Random r = new Random();
for (int j=0;j<i;j++){
myList.leggTil(Long.toString(Math.abs(r.nextLong()), 36));
}
}
private void lesUt() {
Iterator it = myList.iterator();
int i = 1;
while (it.hasNext()){
System.out.println(i+" : "+it.next());
i++;
}
}
/// Mulig denne fungerer, men den er møkkete. Se under for en renere løsning
private void lesUtBaklengs() {
Object P = null;
Object Q = null;
Object T = null;
Iterator it = myList.iterator();
// Finner siste objekt i lista
while (it.hasNext()){
T = it.next();
P = T;
}
for (int i = 0;i<=myList.antall();i++){
it = myList.iterator();
while (it.hasNext()){
if (T.equals(Q)){
System.out.println(i+" : "+Q);
T = P;
}
P = Q;
Q = it.next();
}
}
}
// RENERE LØSNING AV LARS
public void skrivBaklengs()
{
Stack<E> temp = new Stack();
Iterator iter = myList.iterator();
while(iter.hasNext())
temp.push(iter.next());
while(!temp.empty())
{
System.out.println(temp.pop());
}
}
}
[rediger]
Oppgave 3.4
Se lesUtBaklengs() i oppgave 3.3
[rediger]
Oppgave 3.5
package oppgavesett3;
import java.util.Iterator;
import java.util.ListIterator;
public class MyDoubleLinkedList<E> {
private int antall=0;
private DoubleNode<E> head;
private DoubleNode<E> tail;
public void leggTil(E element){
boolean leggesTil = !inneholder(element);
if (antall>0 && leggesTil){
//System.out.println(antall+" # "+head.hentVerdi());
head = new DoubleNode(element,head);
//tail.settForrige(head);
antall++;
} else {
//System.out.println("1: "+element);
head = new DoubleNode(element,head);
tail = head;
antall++;
}
}
public boolean inneholder(E element) {
boolean funnet = false;
Iterator<E> it = iterator();
while (it.hasNext() && !funnet){
E verdi = it.next();
if (verdi.equals(element))
funnet = true;
}
return funnet;
}
public int antall(){
return antall;
}
public E fjern(E element){
E retur = null;
DoubleNode p, q;
boolean funnet = false;
if (erTom()){
//Kast unntak
}
//er det første element i listen som skal slettes?
if (head.verdi.equals(element)){
retur = head.verdi;
head = head.neste;
}
else {
// hvis ikke må vi lete oss frem til noden som skal slettes, og ta
// vare på referansen til noden _før_ den som skal slettes.
q = head;
p = head.neste;
while(p != null && !funnet ){
if (p.verdi.equals(element))
funnet = true;
else {
q = p;
p = p.neste;
}
}
if (!funnet ){
// kast unntak
}
retur = (E) p.hentVerdi();
q.neste = p.neste;
}
return retur;
}
public Iterator<E> iterator() {
return new LenketMengdeIterator();
}
public ListIterator<E> listIterator(){
return new LenketMengdeIterator();
}
public boolean erTom() {
return (antall == 0);
}
public class DoubleNode<E> {
private E verdi;
private DoubleNode<E> neste;
private DoubleNode<E> forrige;
public DoubleNode(){
neste =null;
verdi = null;
forrige = null;
}
public DoubleNode(E elem){
neste =null;
verdi = elem;
forrige = null;
}
public DoubleNode(E verdi, DoubleNode<E> neste){
this.verdi = verdi;
this.neste = neste;
if (this.neste()!=null) this.neste.settForrige(this);
}
public DoubleNode<E> neste(){
return neste;
}
public DoubleNode<E> forrige(){
return forrige;
}
public void settNeste(DoubleNode<E> dnode){
neste = dnode;
}
public void settForrige(DoubleNode<E> dnode){
forrige = dnode;
}
public E hentVerdi(){
return verdi;
}
public void settVerdi(E elem){
verdi = elem;
}
}
public class LenketMengdeIterator implements ListIterator<E> {
private DoubleNode<E> p;
private DoubleNode<E> n;
public LenketMengdeIterator(){
p = head;
n = tail;
}
public boolean hasNext() {
return (p != null);
}
public E next() {
E verdi = p.hentVerdi();
n = p;
p = p.neste;
return verdi;
}
public DoubleNode<E> siste(){
return n;
}
public void remove() {
throw new UnsupportedOperationException("Not supported yet.");
}
public boolean hasPrevious() {
return (n != null);
}
public E previous() {
E verdi = n.hentVerdi();
p = n;
n = n.forrige();
return verdi; }
public int nextIndex() {
return 0;
}
public int previousIndex() {
return 0;
}
public void set(E e) {
throw new UnsupportedOperationException("Not supported yet.");
}
public void add(E e) {
throw new UnsupportedOperationException("Not supported yet.");
}
}
}
[rediger]
Oppgave 3.6
package oppgavesett3;
import java.util.Iterator;
import java.util.ListIterator;
public class TestMyDoubleLinkedList {
public TestMyDoubleLinkedList() {
MyDoubleLinkedList myList = new MyDoubleLinkedList();
myList.leggTil("Atle");
myList.leggTil("Bjarte");
myList.leggTil("Stine");
myList.leggTil("Maria");
myList.leggTil("Tine");
System.out.println("Lista har "+myList.antall()+" elementer");
System.out.println("\n### Lista forlengs ###");
ListIterator lit = myList.listIterator();
while (lit.hasNext()){
System.out.println(lit.next());
}
System.out.println("\n### Lista baklengs ###");
while (lit.hasPrevious()){
System.out.println(lit.previous());
}
}
public static void main(String[] args) {
TestMyDoubleLinkedList testMyDoubleLinkedList = new TestMyDoubleLinkedList();
}
}
[rediger]
Oppgave 3.5 / 3.6 Gruppe N +1
<code>
import java.util.Iterator;
import java.util.LinkedList;
public class MyDoubleLinkedList<E> implements Mengde<E> {
private Node start;
private Node slutt;
private int antall;
public boolean leggTil(E element)
{
Node<E> newNode= new Node<E>(element,start, null);
if(slutt == null && start == null)
slutt = newNode;
else if(start != null)
start.forrige = newNode;
start = newNode;
antall++;
return true;
}
public boolean leggTilAlle(Mengde<? extends E> mengde) {
int antallLagtTil = 0;
for (E e : mengde ){
leggTil(e);
}
return (antallLagtTil > 0);
}
public E fjern(E element) {
boolean funnet = false;
if (erTom()){
return null;
}
Node<E> p = start;
while (p != null && !funnet)
{
if(p.verdi.equals(element))
{
//hvis neste og forrige er null (kun ett element i lista)
if(p.forrige == null && p.neste == null)
{
start = null;
slutt = null;
}
// hvis neste null (siste element)
else if(p.neste == null)
{
p.forrige.neste = null;
slutt = p.forrige;
}
// hvis forrige null (første element)
else if(p.forrige == null)
{
start = p.neste;
}
else
{
p.forrige.neste = p.neste;
p.neste.forrige = p.forrige;
}
funnet = true;
}
}
return p.verdi;
}
public boolean erTom() {
return(slutt == null && start == null);
}
public int antall() {
return antall;
}
public boolean inneholder(Object element) {
boolean funnet = false;
Iterator<E> it = iterator();
while (it.hasNext() && !funnet){
E verdi = it.next();
if (verdi.equals(element))
funnet = true;
}
return funnet;
}
public int get(Object element){
boolean fins = false;
int nr = 0;
Iterator<E> it = iterator();
if(inneholder(element)){
while (it.hasNext() && !fins){
E verdi = it.next();
nr++;
if (verdi.equals(element))
fins = true;
}
return nr;
}
else
return 0;
}
public E get(int nr){
int n = 0;
Iterator<E> it = iterator();
E verdi = null;
while (it.hasNext() && n>=nr){
verdi = it.next();
n++;
}
return verdi;
}
public void skrivBaklengs (){
Iterator<E> i = reversIterator();
while (i.hasNext()){
E verdi = i.next();
System.out.println(verdi + ", ");
}
}
public void skrivUt (){
int n = 0;
Iterator<E> it = iterator();
E verdi = null;
while (it.hasNext()){
verdi = it.next();
n++;
System.out.println(verdi + ", ");
}
}
public Iterator<E> iterator() {
return new DoubleLinkedListIterator();
}
public Iterator<E> reversIterator(){
return new ReverseListIterator();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (E element : this ){
sb.append(element.toString() + " ");
}
return sb.toString();
}
private class Node<E> {
private E verdi;
private Node neste;
private Node forrige;
private Node(E verdi, Node neste, Node forrige){
this.verdi = verdi;
this.neste = neste;
this.forrige = forrige;
}
}
private class DoubleLinkedListIterator implements Iterator<E> {
private Node<E> p;
public DoubleLinkedListIterator(){
p = null;
}
public boolean hasNext() {
if(p == null)
return true;
else
return (p.neste != null);
}
public E next() {
if(p == null)
p = start;
else
p = p.neste;
E verdi = p.verdi;
return verdi;
}
public void remove() {
throw new UnsupportedOperationException("Not supported yet.");
}
}
private class ReverseListIterator implements Iterator<E> {
private Node<E> p;
public ReverseListIterator(){
p = null;
}
public boolean hasNext() {
if(p == null)
return true;
else
return (p.forrige != null);
}
public E next() {
if(p == null)
p = slutt;
else
p = p.forrige;
E verdi = p.verdi;
return verdi;
}
public void remove() {
throw new UnsupportedOperationException("Not supported yet.");
}
}
public Mengde<E> union(Mengde<? extends E> mengde) {
throw new UnsupportedOperationException("Not supported yet.");
}
public Mengde<E> differanse(Mengde<? extends E> mengde) {
throw new UnsupportedOperationException("Not supported yet.");
}
public Mengde<E> snitt(Mengde<? extends E> mengde) {
throw new UnsupportedOperationException("Not supported yet.");
}
</code>
