Programutvikling V2015 — øvingsoppgaver for uke 4

Oppgave 1

Følgende klasse er gitt:

class Node
{
  private int info;
  Node neste;

  public Node( int data, Node etterfølger )
  {
    info = data;
    neste = etterfølger;
  }

  public int getInfo()
  {
    return info;
  }

  public void setInfo( int nyVerdi )
  {
    info = nyVerdi;
  }
}

Klassen definerer datatypen for noder i en sammenkjedet liste. Anta at det er opprettet en slik liste med noder som inneholder verdiene 4, 1, 2, 9, 7 (i denne rekkefølge). Anta videre at Node-pekerne første, p, q refererer til nodene med verdiene henholdsvis 4, 2 og 7.

1. Tegn en figur av lista. (Siste node har neste-peker lik null.)
2. Hva returneres av første.getInfo()?
3. Skriv to forskjellige instruksjoner som begge endrer info-feltet i tredje listenode til 8.
4. Hva returneres av p.neste.neste.getInfo()?
5. Hva er verdien til p.neste.neste.neste?
6. Hva er verdien til q.neste?
7. Anta at følgende kode utføres:
   q.neste = new Node( 5, q.neste );
   Hva er verdien til p.neste.neste.neste.neste? Tegn en figur av lista.
8. Gitt den opprinnelige lista, men uten pekerne p og q. Skriv et segment med kode som fjerner den siste noden fra lista.
9. Skriv et segment med kode som oppretter en liste med 11 noder som inneholder verdiene 10, 11, 12, ..., 20 (i denne rekkefølge), slik at pekeren hode peker på første node i lista, og neste-pekeren til siste node er lik null.
10. Anta at du har den opprinnelige lista (beskrevet ovenfor), men uten pekerne p og q, samt lista beskrevet i foregående spørsmål. Skriv et segment med kode som skjøter sammen de to listene, med den første lista først, slik at pekeren første peker på første node i den sammenskjøtte lista.
11. Anta at du har den sammenskjøtte lista beskrevet i foregående spørsmål. Skriv et segment med kode som i denne lista setter inn en ny node med verdien 0 etter hver node, slik at du får en liste med noder som inneholder verdiene 4, 0, 1, 0, 2, 0, 9, 0, 7, 0, 10, 0, 11, 0, ..., 19, 0, 20, 0.
12. Anta at du har lista beskrevet på slutten av foregående spørsmål. Skriv et segment med kode som fjerner igjen fra lista alle nodene som inneholder verdien 0.
13. Anta at du igjen har den lista som var utgangspunktet i foregående spørsmål, altså den som inneholder verdien 0 i annen hver node. Skriv et segment med kode som i denne lista fjerner alle noder som ikke inneholder verdien 0, slik at du står igjen med en liste som har verdien 0 i alle noder.

Oppgave 2

Anta at samme klasse Node som er beskrevet i Oppgave 1 er gitt. Klassen definerer datatypen for nodene i en sammenkjedet liste definert av klassen som er skissert nedenfor.

public class Liste
{
  private Node første;

  public void settInnForrest( int verdi )
  {
    < oppretter og setter inn en ny node forrest i lista >
  }

  public void settInnForrest( Node ny )
  {
    < setter inn forrest i lista noden som er parameter til metoden >
  }

  public void settInnBakerst( int verdi )
  {
    < oppretter og setter inn en ny node bakerst i lista >
  }

  public void settInnBakerst( Node ny )
  {
    < setter inn bakerst i lista noden som er parameter til metoden >
  }

  public Node fjernFørste()
  {
    < fjerner og returnerer første node i lista,
      returnerer null i tilfelle lista er tom >
  }

  public Node fjernSiste()
  {
    < fjerner og returnerer siste node i lista,
      returnerer null i tilfelle lista er tom >
  }

  public String toString()
  {
    < returnerer en streng som inneholder alle verdier i lista
      med et mellomrom mellom hver verdi. Returnerer en tom streng
      i tilfelle lista er tom. >
  }
}

Programmer klassen Liste. Alle beskrevne metoder skal virke riktig også i spesielle tilfeller som at lista på forhånd er tom eller bare inneholder én node.

Løsningsforslag