Обход пользовательского связанного списка - PullRequest
2 голосов
/ 28 июня 2011

Я пишу программу для симуляции фрагментации памяти.Входной файл сообщает, какие сегменты нужно вводить в какое время.

Пример файла:

N  
C 200  
P 1 2 3  
P 2 3 4  
P 2 3 1  
R  
E

, где C - объем памяти, P - сегмент впорядок (размер, время начала и время жизни) и R (должен) распечатать отчет, показывающий, какие сегменты и какие дыры находятся в памяти и где.

Одно из правил этого назначениязаключается в создании связанного списка событий, где вставки и удаления сегментов создаются как события, и мне нужно просмотреть список событий.ОБНОВЛЕНИЕ: у меня есть кое-что другое, но я точно знаю, что это не вставляет мои События в Список событий.Я не понимаю почему.Кто-нибудь видит, где отключена моя логика?

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;

public class TestEventList{
    public static void main(String[] args){
    //read file
    File file = new File("b.txt");

    try {
        Scanner scanner = new Scanner(file);
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();

            //send it to interpret file method:
            interpretFile(line);
        }
    } catch (FileNotFoundException ex) {
        ex.printStackTrace();
    }  //end try-catch
}

public static void interpretFile(String command) {
    EventList evtList = new EventList();

    Scanner sc = new Scanner(command);


    char initialCommand = command.charAt(0);

    if (initialCommand == 'N') {
        System.out.println("Name");
    } else {
    }//end else
    //file error

    char commandCode = command.charAt(0);
    String skip = sc.next();  //skips next character to get to integers
    switch (commandCode) {
    case 'C':/*create Memory! which means, create Event!
                Form: Event(int startTime, Segment memSegment)*/
        int size = sc.nextInt();

        Segment defaultMemoryNode = new Segment(size, 100, false );
        /*create event node*/
        Event insertDefaultNode = new Event(0, defaultMemoryNode);
        /*insert this event*/
        evtList.insertEvent(insertDefaultNode);

        break;

    case 'P':

            int segmentSize = sc.nextInt();
            int segmentStart = sc.nextInt();
            int segmentLife = sc.nextInt();

            int segmentExpiration = segmentLife + segmentStart;

            Segment memorySegment = new Segment(segmentSize, segmentExpiration, true );
            Event addSegment = new Event(segmentStart, memorySegment);
            evtList.insertEvent(addSegment);

            memorySegment.occupied = false;

            Event removeSegment = new Event(segmentExpiration, memorySegment);
            evtList.insertEvent(removeSegment);

            break;

    case 'R':
        evtList.traverseEventList();

        break;
    case 'E':
        System.exit(0);
        }//end switch

}//end interpretfile method
}  //end class T.E.L.

/*This class has-a Linked List, has-a memoryNode, has-a Segment*/
class MemoryList{

 private Node memoryNode = new Node();
 private Segment memorySegment = new Segment();
 private LinkedList memoryList = new LinkedList();
 Node head;
 Node current;

public MemoryList(){
   super();
}
   /*define blocks and holes*/
   public void insertBlock(Segment memorySegment) {
    current = head;
    if (current == null) {
        memoryList.Add(memorySegment);
        System.out.println(memorySegment.size);
        }
    else {
        System.out.println("Checking for room");
        System.out.println(current.getSize());
        int invalidFit=0;
        if(current.getStatus() == false && current.getSize()>=memorySegment.size){
            System.out.println("Verified space");
            int freeSpace = current.getSize() - memorySegment.size;
            memoryList.Add(memorySegment);
            createHole(freeSpace);
            current = current.next;
         }  //end if
         else {
            current = current.next;

        } //end else
    }//end else
  }  //end insert block

  public void removeBlock(Segment expiredSegment){
    current = head;
    //search for segment

    while(current.next != null){
        if(current.getTimetoLeave() == expiredSegment.timeToLeave
                && current.getSize() == expiredSegment.size){

        memoryList.Remove(expiredSegment);
        int freespace = expiredSegment.size;
        createHole(freespace);
    }
        else{
            current = current.next;
        }
    }//end while
}

    private void createHole(int space) {
    Node hole = new Node(space, 100, false);
    memoryList.Add(hole);
    //test if there are two holes together. if so, mergeHoles.
    }

   *Merge 2 Consecutive Holes*/
   private void mergeHoles(Node a, Node b) {
   //getPrev(a);  //find previous of node a
   //use the size through the end of a's prev to
   //get start of prev.next (a)+

   //make a point to b.next?
  } //end mergeHoles

  public void traverseMemoryList(){
    current = head;

    if(current == null){
        System.out.println("Memoryless");
    }
    else{
        while(current.next != null){
            if(memoryNode.getStatus() == false){
                System.out.println("Hole");
                current = current.next;
            }
        }
        System.out.println("Segment of size " + current.getSize());
        current = current.next;
    }
   }

} //end MemoryList

class MemoryNode extends Node{
   public MemoryNode(){
    super();
   }


}
class Segment{
  int size;
  int timeToLeave;
  boolean occupied;

  /*constructor*/
  public Segment(){

  }

public Segment(int newSize, int newTime, boolean isOccupied){
    this.size = newSize;
    this.timeToLeave = newTime;
    this.occupied = isOccupied;
 }

}

class Node {
     private int size;
     private int timeToDepart;
     boolean occupied;  // True if segment, false if hole
     Node next;
     public Object data;  //data in a node

    public Node() {
    }

    public Node(int segmentSize, int timeToLeave, boolean type) {
    this.size = segmentSize;
    this.timeToDepart = timeToLeave;
    this.occupied = type;

    }

    public int getSize() {
    return size;
    }

    public void setSize(int segmentSize) {
        size = segmentSize;
    }

    public int getTimetoLeave() {
        return timeToDepart;
    }

     public void setTimetoLeave(int timeToLeave) {
            timeToDepart = timeToLeave;
    }

    public void setStatus(boolean type) {
        occupied = type;
    }

    public boolean getStatus() {
        return occupied;
    }

}  //end Node

/* class LL has-a Node*/
class LinkedList{
  private Node listNode= new Node();

   Node current;
   Node head;
   Node prev;

   int size;

/*Constructors:*/
public LinkedList() {
    super();
}

public LinkedList(int j, int k, boolean l) {
    super();  //essentially the same as a node
}

/*LL proprietary methods*/
 /*test if the list is empty, to avoid NullPointerException*/
public boolean isEmpty() {
    return head == null;
}
//insert method:

public void Add(Object data1) {
    listNode.data = data1;

    /*special case: list is empty*/
    if (isEmpty()) {
        listNode.next = head;
        head = listNode;
        head.data = listNode.data;
    }

    else{
        current = head;

        while(current.next != null)
    {
        current.data = data1;
        current.next = null;
        head = current;
    }
        current.data = data1;
        current.next = head; //newNode now points to head
        head = current;      //now newNode is the head
    }
}

public void Remove(Object delData) {
    /*pointers*/

    //special case: if head is the removed node;
    if (current.data == delData) {
        head = current.next;
    } else {
        prev = head;  //it's not the head, keep moving.
        current = current.next;

        while (current.next != null) {  //reached end of list
            if (current.data == delData) {      //if
                prev.next = current.next;       //just skip the current node
            } else {
                prev = current;          //now prev is that node
                current = current.next;  //current is the next node

            }
        }  //end while
        //what if current.next = null (it's at the end)?
        if (current.next == null && current.data == delData) {
            prev.next = null;

        }
    }//end else
}
public void traverse(){
    if(head== null){
        System.out.println("no elements to show");
    }
else{
    current = head;
    while(current.next != null){
        current = current.next;
    }

  }}
  }// end LL class

 /*class EventList has-an Event, is-a LinkedList*/
class EventList{
   private Event event = new Event();
   private LinkedList evtList = new LinkedList();
   private MemoryList memList = new MemoryList();
   Node current;
   Node head;
   int time;  //set to the most recent time

   /*constructor*/
   public EventList(){
    super();

  }

  public void actionOfEvent(Event event1){
    Segment p = event.getMemorySegment();
    if(p.occupied == true){
        insertSegment(event1);
    }
    else
        removeSegment(event1);
   }

  //a linked list to control creation of events
  public void insertEvent(Event event) {
    current = head;
    if(current == null){

        evtList.Add(event);
        System.out.println("Added 1st event " + event.startTime);
    }
    else{
        while(current.next != null){
            if(event.startTime <= event.getTime()){
                //if the event start was before the current time...
                evtList.Add(event);
                current = current.next;
            }
            else{
                current = current.next;
            }

        }//end while
        evtList.Add(event);
        System.out.println("Added 2nd event");
    }
   }//end insertEvent

  public void traverseEventList(){
    current = head;

    if(current == null){
        System.out.println("At time " + event.getTime());
        System.out.println("uneventful");
       }
    else{
        while (current.next != null){
        Segment segment1 = event.getMemorySegment();
        if(segment1.occupied = true){
            memList.insertBlock(segment1);
            System.out.println(segment1.size + " inserted");
        }

        else{
            memList.removeBlock(segment1);
            System.out.println(segment1.size + " removed from memory.");
        }


        }
      }
   }

  public void insertSegment(Event addEvent){
    addEvent.getMemorySegment();
    memList.insertBlock(addEvent.getMemorySegment());
    }
  public void removeSegment(Event expEvent){

}

} //end eventList

 /*class Event is-a Node*/
class Event{

   int startTime;
   Segment memoryNode;
   int time;

   public Event(){
       super();
   }

   //pretty much the same as Node.
   public Event(int newStartTime, Segment newMemNode){
      super();
      this.startTime = newStartTime;
      this.memoryNode = newMemNode;
   }

   public void setTime(int newStartTime){
      time = newStartTime;
   }

   public int getTime(){
    return time;
   }

   public void setMemorySegment(Segment newMemNode){
       memoryNode = newMemNode;
   }

   public Segment getMemorySegment(){
       return memoryNode;
   }

}//end class Event

class Report{
   int currentTime= 0;


    //this creates and prints the segments/holes in the list at curTime

}    

Ответы [ 2 ]

1 голос
/ 28 июня 2011

Всего несколько (других) замечаний

Дизайн

Вы используете много наследства.Это действительно необходимо?Позже, для производственного кода, вы должны рассмотреть возможность использования композиция вместо наследование и код для интерфейсов.Это удалит много уродливых зависимостей и улучшит удобство обслуживания.Теперь у вас есть

EventSequenceList is-a MemoryList is-a LinkedList is-a Узел

Только из названий у меня есть некоторые сомнения, что LinkedList действительно является узлом.Я ожидаю Узел в деревьях или графиках, и даже там обычно это отношение has-a .

Именование

Иногда вы нарушаете соглашения об именах Java: имена методов не должны начинаться с заглавной буквы (например, Add).Иногда вы используете имена из одной буквы (как в большинстве ваших конструкторов).

Иногда имя метода не говорит нам, что на самом деле делает метод (например, iterpretFile, который на самом деле не интерпретирует файлно только одна команда, которая может была прочитана из файла)


Чем больше я смотрю на задание, тем больше у меня возникает ощущение, что вы застрялис вашим дизайном рано или поздно (раньше, чем позже).Из того, что я прочитал, что требуется:

  • Один класс модели событий.Класс, представляющий событие вставки или удаления.
  • Один класс модели памяти.Класс, представляющий всю память
  • Один класс модели сегмента.Класс, который представляет сегмент.Класс памяти имеет список или массив сегментов
  • Один связанный список, содержащий все события.Этот пользовательский связанный список может быть способен вставлять событие в нужное место
  • Один класс отчетности.Класс, который может создавать и печатать отчет.
  • Один анализатор входных файлов.Он будет использовать входные данные для
    • создания класса памяти (с соответствующим количеством сегментов)
    • создания событий вставки и удаления из P строк
    • вставки событийв связанном списке

Абсолютно нет наследование необходимо.


Редактировать - в ответ на ваши последние комментарии

A Память имеет массив ячеек.Ячейки индексируются, начиная с 0. Они не связаны, поэтому я на самом деле не вижу смысла использовать LinkedList здесь.Модель памяти может выглядеть следующим образом:

public class Memory {
  private int[] cells;
  public Memory(int size) { cells = new int[size]; }
  public void store(int index, int value) { 
    if (index < 0 || index >= size) throw new IllegalArgumentException("..");
    cells[index] = value;
  }
  public int read(int index) {
    if (index < 0 || index >= size) throw new IllegalArgumentException("..");
    return cells[index];
  }
}

A сегмент может рассматриваться как подкласс памяти.В реальной жизни сегмент запрашивается у менеджера памяти, и менеджер выделяет регион, если это возможно.Сегменты полностью независимы, никакой связи между ними нет, здесь нет необходимости в LinkedList.Краткий черновик:

public class MemoryManager {
  private Memory managedMemory;
  public MemoryManager(Memory memory) { this.memory = memory; }
  public Segment getSegment(int size) {
    int startAddress = allocateSegment(int size);
    if (startAddress != -1) {
      return new Segment(this, startAddress, size);
    }
    return null;
  }
}

public class Segment extends Memory {
  private MemoryManager memoryManager;
  private int startAddress;  // usually - a handle, so that the memoryManager can
                             // relocate the segment - we keep it simple
  public Segment(MemoryManager memoryManager, int startAdress, int size) {
    super(size);
    this.memoryManager = memoryManager;
    this.startAddress = startAddress;
  }

Теперь вернемся к событиям.

Одним из правил этого назначения является создание связанного списка событий [eventList = new EventList<Event>()] , где вставки и удаления сегментов создаются как события [new Event(EventType.INSERT, int time, Segment segment)); new Event(EventType.DELETE, int time, Segment segment);] , и мне нужно просмотреть список событий [for(Event event:eventList)].

Это задача.реализовать класс Event, реализовать класс EventList, реализовать небольшое перечисление EventType.Задача состоит в том, чтобы внедрить метод insert в EventClass, который вставляет два события для одной строки P в нужных местах (отметки времени).

1 голос
/ 28 июня 2011

Я запустил ваш код, и кажется, что вы никогда не звоните:

setMemoryNode();

Это вызывает исключения NullPointerExceptions.

Также:

Некоторые из нескольких экземпляров событий вызываются следующими строками:

EventSequenceList expiredNode = new EventSequenceList(newMemNode,
1, expir, 1, true);
insertEvent(expiredNode);

Я отредактирую это, как только увижу.

...