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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
#include <iostream>
#include <fstream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "progListeSC.h"
#include "fichierTP3.h"
using namespace std;
bool estTrieeLSC(ListeSC L){
// Res : Renvoie true si L est une ListeSC tri�e, false sinon
if (estVideLSC(L) || estVideLSC(L->succ))
return true;
else
return (L->info < (L->succ)->info) && estTrieeLSC(L->succ);
}
bool estListeIntervalle(ListeSC L){
// Res : renvoie true si L est une Liste intervalle, renvoie false sinon
// A COMPLETER
while ( L->succ != NULL) {
if (L->succ->info - L->info != 1) return false;
L=L->succ;
}
return true;
}
ListeSC consListeIntervalle1(int l, int p){
// Donn�e : l>0
// Res : renvoie une liste intervalle de longueur l et dont le premier �l�ment a pour valeur p
// Complexit� : Complexité dans le pire cas : O(N^2) ( boucle for + complexité de base de insererFinLC)
assert(l>0);
int i; ListeSC L;
L=NULL;
for(i=0;i<l;i++)
insererFinLSC(L,p+i);
return L;
}
ListeSC consListeIntervalle2(int l, int p){
// Donn�e : l>0
// Res : renvoie une liste intervalle de longueur l et dont le premier �l�ment a pour valeur p
// Complexit� : O(N)
// Version iterative
p=p+l-1 ; //valeur du dernier element
ListeSC L = NULL;
while ( l>0) {
L=creerLSC(p, L);
p--;
l--;
}
return L;
}
ListeSC consListeIntervalle3(int l, int p){
// Donn�e : l>0
// Res : renvoie une liste intervalle de longueur l et dont le premier �l�ment a pour valeur p
// Complexit� : O(N-1)
// Version r�cursive
ListeSC L=NULL;
if ( l == 0) return L;
else {
L = creerLSC(p,consListeIntervalle3(l-1,p+1));
return L;
}
}
void transfListeIntervalle(ListeSC L){
// Donn�e : L est une liste tri�e non vide
// Res : modifie L en y inserant des �l�ments de sorte qu'elle soit une Liste Intervalle
// Complexit� : ????
while ( L->succ != NULL) {
if (L->succ->info - L->info != 1) {
insererApresLSC(L,L,L->info+1);
}
L=L->succ;
}
return;
}
ListeSC intersectionListesIntervalles(ListeSC l1, ListeSC l2){
// Donn�e : l1 et l2 2 listes intervalles
// Res : Renvoie l'intersection de l1 et l2; les �l�ments de la liste r�sultat sont recopi�s
// Complexit� : ordre O(N) une premiere partie au moins inferieure a la somme
// de la longueur des listes, plus un appel lineaire a consListeIntervalle2
assert(estListeIntervalle(l1));
assert(estListeIntervalle(l2));
while (l1 != NULL && l2 != NULL && l1->info != l2->info){
if (l1->info<l2->info){
l1= l1->succ;
}
else {
l2=l2->succ;
}
}
int p= l1->info;
int l =0;
while ( l1 != NULL && l2 != NULL && l1->info == l2->info){
l1=l1->succ;
l2=l2->succ;
l++;
}
return consListeIntervalle2(l,p);
}
void plusLgSsLiInterv(ListeSC &L){
// Donn�e : L liste
// Res : L est modifiee, elle est la plus longue sous-liste intervalle de la liste en entr�e
// Complexit� : ????
// ListeSC ret = L;
// ListeSC ancien = NULL;
// int lenght = 0;
// while ( ret->succ != NULL){
// if (ret->succ->info - ret->info != 1){
// lenght=0;
// ret=ret->succ;
// }
// else {
// ancien
// }
// }
}
|
