Dijkstra/Structure3_4.java at master · pom75/Dijkstra · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57


public abstract class Structure3_4 extends Bordure {

	protected Liste [] paquets;          // tableau des paquets (P dans le sujet)
	protected ElementListe [] sommets;   // tableau des références aux sommets


	public abstract void initialiser(int n, int C);

	public abstract boolean estVide();

	public abstract void ajouter(Sommet x);


	public Sommet recupMin() {
		int i;
		int num;

		for (i = 0 ; i<paquets.length ; i++) {
			if (!paquets[i].estVide()) {
				num = paquets[i].retirerAvecNum();
				Sommet s = sommets[num].getS();
				sommets[num] = null;
				return s;
			}
		} return null;


	}


	public void supprimer(Sommet s) {
		 ElementListe elem = sommets[s.num];

		if (elem.estPremier()) {
			paquets[elem.getDist()].retirer();    // retire le premier élément
		} else {
			if (elem.estDernier()) {
				elem.getPrec().setSuiv(null);
				paquets[s.num].decrementeNbElem();
			} else {
				elem.getPrec().setSuiv(elem.getSuiv());
				elem.getSuiv().setPrec(elem.getPrec());
				paquets[s.num].decrementeNbElem();
			}
		}
		sommets[s.num] = null;
	}


	// rend le paquet numéro i
	public Liste getPaquet (int i) {
		return paquets[i];
	}

}