From f4ad9443f6fc46958bbfdacdf13278ff2a96c072 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Thu, 15 Feb 2018 15:00:56 +0100 Subject: [PATCH] Add Structure code. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- Structure/Entiers.java | 106 ++++++++++++++++++++++++++++++ Structure/Liste.java | 137 +++++++++++++++++++++++++++++++++++++++ Structure/Main.java | 75 +++++++++++++++++++++ Structure/Makefile | 92 ++++++++++++++++++++++++++ Structure/Structure.java | 8 +++ 5 files changed, 418 insertions(+) create mode 100644 Structure/Entiers.java create mode 100644 Structure/Liste.java create mode 100644 Structure/Main.java create mode 100644 Structure/Makefile create mode 100644 Structure/Structure.java diff --git a/Structure/Entiers.java b/Structure/Entiers.java new file mode 100644 index 0000000..b2c9247 --- /dev/null +++ b/Structure/Entiers.java @@ -0,0 +1,106 @@ + +class Entiers extends Structure { + private int int_array[]; + private int array_size; + private int current_size; + + public void setSize(int size) { + array_size = size; + } + + public int getSize() { + return array_size; + } + + public void setCurrentSize(int index) { + current_size = index; + } + + public int getCurrentSize() { + return current_size; + } + + Entiers(int size) { + int_array = new int[size]; + setSize(size); + setCurrentSize(0); + } + + public boolean inserer(int value) { + if (isFull()) { + System.out.println("Tableau plein"); + return false; + } + if (isEmpty()) { + int_array[0] = value; + current_size++; + return true; + } else { + for (int i = 0; i < getCurrentSize(); i++) { + if (int_array[i] == value) { + return true; + } else if (int_array[i] > value) { + for (int j = getCurrentSize(); j > i; j--) { + int_array[j] = int_array[j - 1]; + } + int_array[i] = value; + current_size++; + return true; + } + } + } + /** + * The current value to add is > to all elements in the tab. + * So add it at the end. + */ + int_array[getCurrentSize()] = value; + current_size++; + return true; + } + + private int binarySearch(int first, int last, int value) { + if (last < first) + return -1; + int middle = (first + last) / 2; + if (value == int_array[middle]) + return middle; + else if (value > int_array[middle]) + return binarySearch((middle + 1), last, value); + return binarySearch(first, (middle -1), value); + } + + public boolean supprimer(int value) { + if (isEmpty()) { + System.out.println("Aucune valeur à supprimer"); + return false; + } + + for (int i = 0; i < getCurrentSize(); i++) { + if (int_array[i] == value) { + // Deleting the element in the tab + for (int j = i; j < getCurrentSize() - 1; j++) { + int_array[j] = int_array[j + 1]; + } + current_size--; + return true; + } + } + return true; + } + + private boolean isFull() { + return (getCurrentSize() >= getSize()); + } + + private boolean isEmpty() { + return (getCurrentSize() == 0); + } + + public void afficher() { + System.out.println("----"); + for (int i = 0; i < getCurrentSize(); i++) { + System.out.println("element " + i + " " + int_array[i]); + } + } + +} diff --git a/Structure/Liste.java b/Structure/Liste.java new file mode 100644 index 0000000..d6bd963 --- /dev/null +++ b/Structure/Liste.java @@ -0,0 +1,137 @@ + + +public class Liste extends Structure { + + private class IntNode { + private int data; + private IntNode next; + + IntNode(int value) { + setData(value); + setNext(null); + } + + IntNode(int value, IntNode nextNode) { + setData(value); + setNext(nextNode); + } + + public int getData() { + return data; + } + + public void setData(int value) { + data = value; + } + + public IntNode getNext() { + return next; + } + + public void setNext(IntNode nextNode) { + next = nextNode; + } + + } + + private IntNode headNode; + private int list_counter; + + Liste() { + setHeadNode(null); + setSize(0); + } + + private boolean isEmpty() + { + return getHeadNode() == null; + } + + public int getSize() { + return list_counter; + } + + public void setSize(int size) { + list_counter = size; + } + + public void setHeadNode(IntNode node) { + headNode = node; + } + + public IntNode getHeadNode() { + return headNode; + } + + public boolean inserer(int value) { + boolean found = false; + if (isEmpty()) { + headNode = new IntNode(value); + list_counter++; + return true; + } else if (value == headNode.getData()) { + found = true; + return true; + } else { + IntNode nodeCursorNext = headNode.getNext(); + while (nodeCursorNext != null) { + if (value == nodeCursorNext.getData()) { + found = true; + break; + } else { + nodeCursorNext = nodeCursorNext.getNext(); + } + } + if (!found) { + headNode = new IntNode(value, headNode); + list_counter++; + } + // Insertion in a linked list can't fail + return true; + } + } + + public boolean supprimer(int value) { + boolean deleted = false; + if (isEmpty()) { + return deleted; + } else if (value == headNode.getData()) { + headNode = headNode.getNext(); + deleted = true; + list_counter--; + } else { + IntNode nodeCursor = headNode; + IntNode nodeCursorNext = headNode.getNext(); + while (nodeCursorNext != null) { + if (value == nodeCursorNext.getData()) { + nodeCursor.setNext(nodeCursorNext.getNext()); + deleted = true; + list_counter--; + break; + } else { + nodeCursor = nodeCursorNext; + nodeCursorNext = nodeCursorNext.getNext(); + } + } + } + return deleted; + } + + public void afficher() { + if (isEmpty()) { + System.out.println("Liste vide"); + } else if (headNode.getNext() == null) { + System.out.println("Valeur du noeud 0 : " + headNode.getData()); + } else { + IntNode nodeCursor = headNode; + int i = 0; + while (nodeCursor.getNext() != null) { + System.out.println("Valeur du noeud " + i + " : " + nodeCursor.getData()); + nodeCursor = nodeCursor.getNext(); + i++; + } + System.out.println("Valeur du noeud " + i++ + " : " + nodeCursor.getData()); + } + } + +} diff --git a/Structure/Main.java b/Structure/Main.java new file mode 100644 index 0000000..de10882 --- /dev/null +++ b/Structure/Main.java @@ -0,0 +1,75 @@ + + + +class Main { + + public static void main_liste() { + Liste LinkedList = new Liste(); + + LinkedList.inserer(2); + LinkedList.inserer(1); + LinkedList.inserer(4); + LinkedList.afficher(); + System.out.println("Taille de la liste : " + LinkedList.getSize()); + + LinkedList.inserer(2); + LinkedList.inserer(10); + LinkedList.inserer(0); + LinkedList.afficher(); + System.out.println("Taille de la liste : " + LinkedList.getSize()); + + LinkedList.supprimer(4); + LinkedList.afficher(); + System.out.println("Taille de la liste : " + LinkedList.getSize()); + LinkedList.supprimer(0); + LinkedList.afficher(); + System.out.println("Taille de la liste : " + LinkedList.getSize()); + LinkedList.supprimer(0); + LinkedList.afficher(); + System.out.println("Taille de la liste : " + LinkedList.getSize()); + LinkedList.supprimer(10); + LinkedList.afficher(); + System.out.println("Taille de la liste : " + LinkedList.getSize()); + } + + public static void main_entiers() { + Entiers integer = new Entiers(5); + + integer.inserer(1); + + integer.afficher(); + + integer.inserer(12); + + integer.afficher(); + + integer.inserer(3); + + integer.afficher(); + + integer.inserer(0); + + integer.inserer(1); + + integer.afficher(); + + integer.supprimer(12); + + integer.afficher(); + System.out.println("Current size " + integer.getCurrentSize()); + + integer.supprimer(1); + + integer.afficher(); + System.out.println("Current size " + integer.getCurrentSize()); + + } + + public static void main(String[] args) { + + main_liste(); + main_entiers(); + + } + +} diff --git a/Structure/Makefile b/Structure/Makefile new file mode 100644 index 0000000..c4447fc --- /dev/null +++ b/Structure/Makefile @@ -0,0 +1,92 @@ +# define compiler and compiler flag variables +# define a variable for compiler flags (JFLAGS) +# define a variable for the compiler (JC) +# define a variable for the Java Virtual Machine (JVM) + +JFLAGS = -g +JC = javac +JVM = java + +# +# Clear any default targets for building .class files from .java files; we +# will provide our own target entry to do this in this makefile. +# make has a set of default targets for different suffixes (like .c.o) +# Currently, clearing the default for .java.class is not necessary since +# make does not have a definition for this target, but later versions of +# make may, so it doesn't hurt to make sure that we clear any default +# definitions for these +# + +.SUFFIXES: .java .class + + +# +# Here is our target entry for creating .class files from .java files +# This is a target entry that uses the suffix rule syntax: +# DSTS: +# rule +# DSTS (Dependency Suffix Target Suffix) +# 'TS' is the suffix of the target file, 'DS' is the suffix of the dependency +# file, and 'rule' is the rule for building a target +# '$*' is a built-in macro that gets the basename of the current target +# Remember that there must be a < tab > before the command line ('rule') +# + +.java.class: + $(JC) $(JFLAGS) $*.java + + +# +# CLASSES is a macro consisting of N words (one for each java source file) +# When a single line is too long, use \ to split lines that then will be +# considered as a single line. For example: +# NAME = Camilo \ + Juan +# is understood as +# NAME = Camilo Juan + +CLASSES = \ + Structure.java \ + Entiers.java \ + Liste.java \ + Main.java + +# +# MAIN is a variable with the name of the file containing the main method +# + +MAIN = Main + +# +# the default make target entry +# for this example it is the target classes + +default: classes + + +# Next line is a target dependency line +# This target entry uses Suffix Replacement within a macro: +# $(macroname:string1=string2) +# In the words in the macro named 'macroname' replace 'string1' with 'string2' +# Below we are replacing the suffix .java of all words in the macro CLASSES +# with the .class suffix +# + +classes: $(CLASSES:.java=.class) + + +# Next two lines contain a target for running the program +# Remember the tab in the second line. +# $(JMV) y $(MAIN) are replaced by their values + +run: $(MAIN).class + $(JVM) $(MAIN) + +# this line is to remove all unneeded files from +# the directory when we are finished executing(saves space) +# and "cleans up" the directory of unneeded .class files +# RM is a predefined macro in make (RM = rm -f) +# + +clean: + $(RM) *.class diff --git a/Structure/Structure.java b/Structure/Structure.java new file mode 100644 index 0000000..2a40d24 --- /dev/null +++ b/Structure/Structure.java @@ -0,0 +1,8 @@ + +public abstract class Structure { + + public abstract boolean inserer(int value); + public abstract boolean supprimer(int value); + public abstract void afficher(); + +} -- 2.34.1