Structure de donnees Questions Reponses

​
Bienvenue dans cette nouvelle rubrique sur le jeux Questions-Reponses, il s'agit dans un premier temps d'aborder des thematiques sur des arguments qui peuvent vous etres utiles en tant que developpeur, bref des choses toujours bien à savoir et par la suite un ensemble de Quiz ou jeux questions-reponses pas forcement lié à la thematique du post question de vous ammener le plus souvent à reflechir sur plusieurs choses à la fois, car un bon developpeur doit toujours etre animé par le deveoir de connaitre, etre curieux, chercher à aller au dela de sa zone de comfort.

Dans la rubrique d'aujourd'hui je vous reparle des structures de données qu'il faut comprendre leur fonctionnement et surtout leur complexité et comment on les code dans different langage, ces structures de données sont dejà présent dans les bibliothèques de base qui accompagnent les langages de programmation et vous devez connaitre leur complexité algorithmique pour savoir les utilisé pour implementer votre propre algorithme dans vos projet, un bon dev doit comprendre le fonctionnement de chaque structure de données et surtout sa complexité algorithmique en terme d'insertion, de recherche, d'elimination et de mise à jour d'un element dans cette structure, je vous en parles de 3 structures avec code à l'appuis dans plusieurs langages juste pour vous donner l'idée soudjacente et son codage.

Les Listes chainée (LinkedList en anglais)

Une liste chaînée est une collection linéaire d'éléments de données, appelés nœuds, chacun pointant vers le nœud suivant au moyen d'un pointeur. C'est une structure de données constituée d'un groupe de nœuds qui représentent ensemble une séquence.
Liste chaînée simple : liste chaînée dans laquelle chaque nœud pointe vers le nœud suivant et le dernier nœud pointe vers null
Liste doublement chaînée : liste chaînée dans laquelle chaque nœud a deux pointeurs, p et n, tels que p pointe vers le nœud précédent et n pointe vers le nœud suivant ; le pointeur n du dernier nœud pointe vers null
Liste chaînée circulaire : liste chaînée dans laquelle chaque nœud pointe vers le nœud suivant et le dernier nœud pointe vers le premier nœud.

Complexité temporaire:
Lecture: O(n)
Recherche: O(n)
Insertion: O(1)
Elimination: O(1)
Implementation d'une liste chainée en Java

import java.util.ListIterator;
import java.util.NoSuchElementException;

public class DoublyLinkedList implements Iterable {
    private int N;        // number of elements on list
    private Node pre;     // sentinel before first item
    private Node post;    // sentinel after last item

    public DoublyLinkedList() {
        pre  = new Node();
        post = new Node();
        pre.next = post;
        post.prev = pre;
    }

    // linked list node helper data type
    private class Node {
        private Item item;
        private Node next;
        private Node prev;
    }

    public boolean isEmpty()    { return N == 0; }
    public int size()           { return N;      }

    // add the item to the list
    public void add(Item item) {
        Node last = post.prev;
        Node x = new Node();
        x.item = item;
        x.next = post;
        x.prev = last;
        post.prev = x;
        last.next = x;
        N++;
    }

    public ListIterator iterator()  { return new DoublyLinkedListIterator(); }

    // assumes no calls to DoublyLinkedList.add() during iteration
    private class DoublyLinkedListIterator implements ListIterator {
        private Node current      = pre.next;  // the node that is returned by next()
        private Node lastAccessed = null;      // the last node to be returned by prev() or next()
                                               // reset to null upon intervening remove() or add()
        private int index = 0;

        public boolean hasNext()      { return index < N; }
        public boolean hasPrevious()  { return index > 0; }
        public int previousIndex()    { return index - 1; }
        public int nextIndex()        { return index;     }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            lastAccessed = current;
            Item item = current.item;
            current = current.next; 
            index++;
            return item;
        }

        public Item previous() {
            if (!hasPrevious()) throw new NoSuchElementException();
            current = current.prev;
            index--;
            lastAccessed = current;
            return current.item;
        }

        // replace the item of the element that was last accessed by next() or previous()
        // condition: no calls to remove() or add() after last call to next() or previous()
        public void set(Item item) {
            if (lastAccessed == null) throw new IllegalStateException();
            lastAccessed.item = item;
        }

        // remove the element that was last accessed by next() or previous()
        // condition: no calls to remove() or add() after last call to next() or previous()
        public void remove() { 
            if (lastAccessed == null) throw new IllegalStateException();
            Node x = lastAccessed.prev;
            Node y = lastAccessed.next;
            x.next = y;
            y.prev = x;
            N--;
            if (current == lastAccessed)
                current = y;
            else
                index--;
            lastAccessed = null;
        }

        // add element to list 
        public void add(Item item) {
            Node x = current.prev;
            Node y = new Node();
            Node z = current;
            y.item = item;
            x.next = y;
            y.next = z;
            z.prev = y;
            y.prev = x;
            N++;
            index++;
            lastAccessed = null;
        }

    }

    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this)
            s.append(item + " ");
        return s.toString();
    }

Implementation d'une liste chainée en Javscript

var LinkedList = module.exports = function (value) {
  this.value = value;
  this.prev  = this;
  this.next  = this;
};

LinkedList.prototype.appendNode = function (value) {
  var node  = new LinkedList(value);
  node.prev = this;
  node.next = this.next;
  // Fix the linked list references
  this.next = this.next.prev = node;
  return node;
};

LinkedList.prototype.prependNode = function (value) {
  var node  = new LinkedList(value);
  node.prev = this.prev;
  node.next = this;
  // Fix the linked list references
  this.prev = this.prev.next = node;
  return node;
};

LinkedList.prototype.removeNode = function () {
  // Create a reference around the node to be removed
  this.prev.next = this.next;
  this.next.prev = this.prev;
  // Remove existing references to the current list
  this.next = this.prev = this;
  return this;
};

LinkedList.prototype.containsNode = function (value) {
  if (this.value === value) { return true; }

  var node = this.next;
  // Loop through the connections until we hit ourselves again
  while (node !== this) {
    if (node.value === value) {
      return true;
    }
    node = node.next;
  }

  return false;
};

Implementation d'une liste chainée en Python

class Node():
    def __init__(self, val, next=None, prev=None):
        self.val, self.next, self.prev = val, next, prev

class List():
    def __init__(self, head=None):
        self.head = None

    def add(self, val):
        node = Node(val)
        if self.head:
            node.next = self.head
            self.head.prev = node
        self.head = node

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def __str__(self):
        curr = self.head
        vals = []
        while(curr):
            vals.append(curr.val)
            curr = curr.next
        return str(vals)

l = List()
l.add(12)
l.add(13)
l.add(14)
print l

La PILE (Stack en anglais)

Une pile est une collection d'éléments, avec deux opérations principales : push, qui ajoute à la collection, et pop, qui supprime l'élément le plus récemment ajouté.
c'est une structure de donnée qui fonctione en moalité dite (LIFO =Last In First Out = Dernier entrée premier à sortir): l'objet ajouté le plus récemment est le premier à être supprimé. cette structure est utilisé beaucoup par les compilateurs et les interpreteurs, la fameuse parole de Stack raison d'etre du site StackOverflow car pour executer nos lignes de codes dans les langages de programmations le compilateur lit ligne par ligne, le meme dans la pile l'execute et vide la pile, vous serez ammenez dans vos projets avenir à utiliser cette structure pour mettre sous pieds vos algorithmes
Complexité temporelle :
Lecture : O(n)
Recherche : O(n)
Insertion: O(1)
Elimination : O(1)

Implementation de la pile en javascript

var Stack = module.exports = function () {
  this.head   = null;
  this.length = 0;
};

Stack.prototype.push = function (value) {
  var node = {
    value: value,
    next: null
  };

  if (!this.head) {
    this.head = node;
  } else {
    node.next = this.head;
    this.head = node;
  }

  return this.length += 1;
};

Stack.prototype.pop = function () {
  // If there is no head node, return `undefined`
  if (!this.head) { return; }

  var node = this.head;

  // Update the head reference and remove the next node reference from the previous head
  this.head = node.next;
  node.next = null;

  this.length -= 1;

  return node.value;
};

Implementation de la Pile EN PHP

class Stack {

  public function __construct()
  {
    $this->stack = [];
  }

  public function push($val)
  {
    $this->stack[] = $val;
  }

  public function pop()
  {
    return array_pop($this->stack);
  }

  public function length()
  {
    return count($this->stack);
  }

  public function isEmpty()
  {
    return count($this->stack) === 0;
  }
}

$s = new Stack();
assert($s->isEmpty());
assert($s->length() === 0);
$s->push("hello");
assert($s->length() === 1);
$s->push("world");
assert($s->length() === 2);
$v = $s->pop();
assert($v === "world");
assert($s->length() === 1);
$v = $s->pop();
assert($v === "hello");
assert($s->length() === 0);
assert($s->isEmpty());

Implementation de la Pile en python

class Stack():
    """
    Simple LIFO Stack data structure
    """

    def __init__(self):
        """Constructor declaring the private variable"""
        self._items = []
    
    def is_empty(self):
        """Check the emptiness of the stack"""
        return len(self._items) == 0

    def size(self):
        """Get the number of items in the stack"""
        return len(self._items)

    def push(self, item):
        """Push an item to the stack"""
        self._items.append(item)

    def pop(self):
        """Pop an item from the end of the stack"""
        if self.is_empty():
            raise RuntimeError("Attempt to pop an empty Stack!")
        return self._items.pop()

    def show(self):
        """Show the contents of the stack"""
        res = "Stack (["
        if self.is_empty():
            print(res + "])")
            return
        for i in range(len(self._items)-1):
            res += str(self._items[i]) + ', '
        res += str(self._items[len(self._items)-1]) + "])"
        print(res)
        return

def main():
    stack = Stack()

    stack.show()          # Stack ([])
    stack.push(42)        # At this point, the stack looks like this: Stack ([42])
    stack.push(23)        # At this point, the stack looks like this: Stack ([42, 23])
    stack.push(5)         # At this point, the stack looks like this: Stack ([42, 23, 5])
    print(stack.size())   # 3
    stack.show()          # Stack ([42, 23, 5])
    print(stack.pop())    # 5
    stack.show()          # Stack ([42, 23])
    print(stack.pop())    # 23
    print(stack.size())   # 1
    stack.show()          # Stack ([42])
    print(stack.pop())    # 42
    stack.show()          # Stack ([])
    print(stack.pop())    # Underflow condition, should raise the RuntimeError exception and print "Attempt to pop an empty Stack!"

if __name__ == "__main__":
    main()

Implementation de la PILE en C stack.h

#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED

typedef struct Nodestack {
    int value;
    struct Nodestack *next;
}NodeStack;

typedef NodeStack *Stack;

// add the element onto the stack
void _add(Stack*,int);

//returns the element on top of the stack
int _remove(Stack*);

#endif // STACK_H_INCLUDED

Implementation de la PILE en C stack.c

#include
#include "stack.h"

void _add(Stack *head,int value){
    Stack node = (Stack)malloc(sizeof(Stack));
    if(node !=NULL){
      node->value = value;
      node->next = *head;
      *head = node;
    }
}

int _remove(Stack *head){
   int value = -1;
   if(head!=NULL){
        Stack top = *head;
        value = (*head)->value;
        *head = (*head)->next;
        free(top);

    }
    return value;
}

 

La Queue Ou FILE d'attente

Une file ou queue autant pour moi ou simple file d'attente, est une collection d'éléments, prenant en charge deux opérations principales : enqueue, qui insère un élément dans la file d'attente, et dequeue, qui supprime un élément de la file d'attente.
Structure de données de type  premier entré, premier sorti (FIFO=First In First Out) : le plus ancien objet ajouté est le premier à être supprimé
Complexité temporelle :
Lecture : O(n)
Recherche : O(n)
Insertion : O(1)
Elimination : O(1)

Implementation de la File d'attente en Javascript

var Queue = module.exports = function () {
  this.head   = null;
  this.tail   = null;
  this.length = 0;
};

Queue.prototype.enqueue = function (value) {
  var node = {
    value: value,
    next: null
  };

  // If there is currently no head node, set it to the current node
  if (!this.head) {
    this.head = node;
  }

  // If we have a tail node already, set it's next property to be the current node
  if (this.tail) {
    this.tail.next = node;
  }

  // Update the tail to be the next node
  this.tail = node;

  return this.length += 1;
};

Queue.prototype.dequeue = function () {
  if (!this.head) { return; }

  var node = this.head;

  // Update the head reference and remove the next node reference from the previous head
  this.head = node.next;
  node.next = null;

  // Remove the tail node if we have no more head node
  if (!this.head) { this.tail = null; }

  this.length -= 1;

  return node.value;
};

Implementation d ela file d'attente en python

class Queue():
    """
    Simple FIFO queue
    """
    def __init__(self):
        self.queue = []

    def add(self, i):
        self.queue.append(i)

    def remove(self):
        if self.queue:
            i, self.queue = self.queue[0], self.queue[1:]
            return i

q = Queue()
q.add(1)
q.add(2)
q.add(3)
print q.remove()
print q.remove()

 

Questions-Reponses

1. Pour les 3 structures de données précedentes, proposez leur implementation dans d'autres langages pas présent dans les codes/langage ci dessus par exemple en C#, java(ou il manque), php(ou il manque) etc..

2. Calculer la somme d'un tableau contenant des entiers et d'autres tableaux contenant des entiers. Par exemple (vous devez ecrire cette fonction dans le langage que vous maitrisez le mieux):

Va retourner comme result = 15;

Je vous propose la solution ici en PHP pour vous donner une idée et j'attend les solutions en python, javascript,c# typescript, kotlin, rugby, go

function arraySum($arr)
{
  $sum = 0;
  foreach ($arr as $item)
  {
    if (is_array($item))
    {
      $sum += arraySum($item);
    }
    else
    {
      $sum += $item;
    }
  }
  return $sum;
}

var_dump(arraySum([1,2,[3,4,[5]]]));

3. Étant donné une chaîne contenant uniquement des caractères ASCII alphanumériques ([A-Za-z0-9]), triez et imprimez la chaîne de la manière suivante :

toutes les lettres minuscules triées sont devant les lettres majuscules,
toutes les lettres majuscules triées précèdent les chiffres, et
tous les chiffres pairs triés précèdent les chiffres impairs triés.

Je vous propose comme dans le point 2 la solution en PHP et j'attends de vous les memes solutions en java, go, javascript, typescript cpp etc   

$chars = str_split($argv[1]);
natsort($chars);
$lower = $upper = $even = $odd = "";
foreach ($chars as $c) {
    if ('a' <= $c && $c <= 'z') {
        $lower .= $c;
    } elseif ('A' <= $c && $c <= 'Z') {
        $upper .= $c;
    } elseif ($c % 2 === 0) {
        $even .= $c;
    } else {
        $odd .= $c;
    }
}
echo "$lower$upper$even$odd";

4. Vous êtes dans un hôtel et vous avez oublié le numéro de chambre dans lequel vous étiez, mais vous vous rappellez que la somme de ses diviseurs est supérieure au nombre, mais il n'y a pas de sous-ensemble de ces diviseurs qui s'additionnent au nombre lui-même. Il y a 100 chambres dans l'hôtel, quel est votre numéro de chambre ?

Je vous propose un code en Javascript qui trouve le numero de chambre, puvez vous nous donnez le meme resultat en php?, c#?

module.exports = function (totalRooms) {
  var findDivisors = function (number) {
    var divisors = [],
        iterator = number;

    while (iterator--) {
      if (number % iterator === 0) {
        divisors.push(iterator);
      }
    }

    return divisors;
  };

  // Returns true or false based on whether the number is found in the sum of array subsets
  var isSubsetSum = function (number, array) {
    var hasSubset = false;

    (function findSubset (total, numbers) {
      !hasSubset && (hasSubset = total === number);

      if (hasSubset || total > number) { return; }

      numbers.forEach(function (num, index) {
        return findSubset(total + num, numbers.slice(0, index).concat(numbers.slice(index + 1)));
      });
    })(0, array);

    return hasSubset;
  };

  // Need a simple helper method that returns the sum of an array
  var sumArray = function (array) {
    return array.reduce(function (memo, num) {
      return memo + num;
    }, 0);
  };

  // Find the room using the provided functions
  var divisors;

  for (var room = 0; room <= totalRooms; room++) {
    divisors = findDivisors(room);

    // The sum of all the divisors must be greater than the number
    if (sumArray(divisors) > room && !isSubsetSum(room, divisors)) {
      return room;
    }
  }

  return 0; // No room number found
};

Les reponses seront comuniquées seulement aux abonnés de ce blog, mettez vos reponses en commentaire ou sur le commentaire lié à cet article sur ma page facebook pour qu'on en discute, et surtout partagez et inscrivez vous à ce blog.

Lien relatif sur ma page facebook ici

Happy Coding

​

---

---

Share

Comments (0)

Leave A Comment

Your Name:
Comment: