El siguiente ejercicio fue propuesto en la Materia Sistémico I del grado Técnico de Sistemas de la Universidad Politécnico Jaime Izasa Cadavid. El problema original dice:
Problem
Eliminate repeated numbers from a double linked list. Code a program that reads the number of elements of a list, inserts integer values in a double linked and prints the list having erased the elements that are repeated.
You must implement the double linked list and erase the nodes in it.
For example,
Input
4 25 25 8 8
Output 25 8
Notice that the first number, in the above sample 4, indicates the amount of integer numbers to be read.
Solución
Se desarrollan dos clases: Node (Nodo) y DDLink (Lista Doble). Una lista doble, tiene referencia o acceso directo a dos elementos: el siguiente y el anterior, ambos nodos. Por lo tanto, si parto del nodo cabeza (head) y empleo el método: head.next(); lo que se obtiene es un NODO. La mayoría de los estudiantes piensan que lo que se obtiene es el siguiente dato y eso es un error. Lo único complicado del programa que se propone se encuentra en el método delete_duplicates() de la clase DDLink (Lista Doble). Igualmente se emplean métodos no requeridos, pero interesante desde el punto de vista del aprendizaje.
Clase Node
package ddlink;
public class Node {
private final int data;
public Node next;
public Node previous;
public Node(int data){
this.data = data;
this.previous = null;
this.next = null;
}
public Node(Node previous, int data, Node next){
this.data = data;
this.previous = previous;
this.next = next;
}
public int GetData(){
return data;
}
}
package ddlink;
public class DDLink {
private Node head;
private int size;
public DDLink(){
head = null;
size = 0;
}
public void addFront(int data){
if(head == null){
head = new Node(null,data,null);
}else {
Node current = new Node(null,data,head);
head.previous = current;
head = current;
}
size++;
}
public void addBack(int data){
if(head == null){
head = new Node(null,data,null);
}else{
Node current = new Node(head,data,null);
head.next = current;
}
size++;
}
// Delete repeated element in DDL
public void delete_duplicates(){
if(head == null){
System.err.println("No node to eliminate");
return;
}
// Identify node to eliminate
Node current = head;
while(current != null){
Node tmp = current.next;
while(tmp != null){
if(current.GetData() == tmp.GetData()){
System.out.println("Repeated number: "+ tmp.GetData());
size--;
if(tmp.next == null){
tmp.previous.next = null;
}else{
tmp.previous.next = tmp.next;
tmp.next.previous = tmp.previous;
}
}
tmp = tmp.next;
}
current = current.next;
}
}
public Node goHead(Node any){
while(any.previous != null){
any = any.previous.previous;
}
return any;
}
public void print(){
Node current = head;
while(current != null){
System.out.println(current.GetData());
current = current.next;
}
}
public boolean isEmpty(){
return (head == null);
}
public int size(){
return size;
}
}
Clase Test_DDLink (contiene main)
import java.util.Scanner;
public class Test_DDlink {
private int num_elements;
public void start(){
Scanner read = new Scanner(System.in);
DDLink DD_link = new DDLink();
System.out.printf("%10s %n","Welcome");
System.out.printf("%10s ","Define number of elements to read from the screen: ");
num_elements = read.nextInt();
System.out.printf("%10s %n","----------");
System.out.printf("%10s %3s %n", "Number of Elements: " , num_elements);
for(int x = 0; x < num_elements; x++){
System.out.print("Add number at front: ");
int data = read.nextInt();
DD_link.addFront(data);
}
System.out.printf("%10s %n","----------");
System.out.printf("%10s %n", "Input");
DD_link.print();
System.out.printf("%10s %n","----------");
System.out.printf("%10s %n", "Output");
DD_link.delete_duplicates();
System.out.printf("%10s %3s %n", "Number of Elements: " , DD_link.size());
System.out.printf("%10s %n","----------");
DD_link.print();
}
public static void main(String[] arg){
try{
Test_DDlink DDL = new Test_DDlink();
DDL.start();
}
catch(Exception e){
System.err.print(e.getMessage());
}
}
}
Se empleo Netbeans 8.2 y se creo un proyecto con el nombre DDLink. Observar que en este caso, el método start() no es estático.
Se expone a continuación un método start() alternativo en la clase Test_DDLink, que considera los datos de entrada como se expone en el ejercicio.
import java.util.Scanner;
public class Test_DDlink {
public void start1(){
Scanner read = new Scanner(System.in);
DDLink DD_link = new DDLink();
System.out.printf("%10s %n","Welcome. Define data input: ");
// Datos
int n = read.nextInt();
int i = 0;
while(i < n){
DD_link.addFront(read.nextInt());
i++;
}
System.out.printf("%10s %n","----------");
System.out.printf("%10s %n", "Input");
DD_link.print();
System.out.printf("%10s %n","----------");
System.out.printf("%10s %n", "Output");
DD_link.delete_duplicates();
System.out.printf("%10s %3s %n", "Number of Elements: " , DD_link.size());
System.out.printf("%10s %n","----------");
DD_link.print();
}
public static void main(String[] arg){
try{
Test_DDlink DDL = new Test_DDlink();
DDL.start1();
}
catch(Exception e){
System.err.print(e.getMessage());
}
}
}
No comments:
Post a Comment