Le type de données LISTE 

Def1 (récursive) : une liste est soit la liste vide soit composée d'un élément suivi d'une liste.

Def2 (itérative) : une liste est une collection ordonnée (par la relation d'ordre induite par la position 
des éléments dans la liste) d'éléments.

On note : 

En plus des opérations de base, on souhaite disposer des fonctions suivantes dont voici les profils et la spécification.

Profils :
	longueur		Liste		-> Entier
	rang 			Elément, Liste	-> Entier
	ajouter_fin		Elément, Liste	-> Liste
	concatener		Liste, Liste	-> Liste
	inverser 		Liste		-> Liste

Spécifications :
	Définition informelle des opérations ci-dessus.

Dans les sections qui suivent, nous prendrons :
	Elément=Entier
car Pascal ne gére pas le polymorphisme 
(i.e. on ne peut pas définir un module générique Liste(X), contrairement à Ada par exemple).


1. Listes récursives

TDA inspiré des listes de Scheme.
Profils et spécifications des fonctions de base :

	liste_vide 		 	-> Liste
	cons			Elément, Liste 	-> Liste
	tete 			Liste 		-> Elément
	reste  		Liste		-> Liste
	est_vide		Liste 		-> Booleen

Implantations possibles : cf Tdao listes
	- par pointeur ;
	- en utilisant un unique tableau pour stocker toutes les listes 
(mais cette implantation suppose un dimensionnement a priori de la taille du tableau).

Définition des fonctions auxiliaires (style fonctionnel, syntaxe pseudo-Pascal)

	fonction longueur(l:Liste):Entier
	...

	fonction rang(n:Entier;l:Liste):Indice
		var i:Entier
	si est_vide(l)  alors	rang:=0
	sinon 	si n=tete(l) alors rang:=1
	sinon si rang(n,reste(l))=0 alors rang:=0
	sinon rang:=rang(n,reste(l))+1

	fonction ajouter_fin(n:Entier; l:Liste):Liste
	si est_vide(l) 
	alors ajouter_fin:=cons(n,liste_vide)
	sinon ajouter_fin:=
			cons(tete(l),ajouter_fin(n,reste(l)))

	fonction concatener(l1,l2:Liste):Liste
	si est_vide(l1)
	alors concatener:=l2
	sinon concatener:=cons(tete(l1),concatener(reste(l1),l2))

	fonction inverser(l:Liste):Liste
	si est_vide(l)
	alors inverser:=liste_vide
	sinon inverser:=concatener(inverser(reste(l)),cons(tete(l),liste_vide))

autre solution :

	fonction inverser(l:Liste):Liste
	si est_vide(l)
	alors inverser:=liste_vide
	sinon inverser:= ajouter_fin(inverser(reste(l)),tete(l))


Questions : On se place dans le cadre d'une implantation par pointeurs.

	- coût en espace d'une liste de n entiers ?
	- comment désallouer la mémoire utilisée par une liste dont on ne se servira plus ?
cf procédure rend_mem(l:Liste).
	- que penser de l3 après exécution de :

var l1,l2,l3:Liste;

	... 	
	l1 vaut <1,2,3>;
	l2 vaut <4,5,6>;
	l3:=concatener(l1,l2);
	rend_mem(l2);
	... 	
	l1 vaut <1,2,3>;
	l2 vaut <4,5,6>;
	l3:=concatener(l1,l2);
	rend_mem(l1);

Proposer une solution.
	
	-  complexité en temps et en espace des fonctions ?

----------------------------------------------------------------------
% implantation par pointeurs

unit liste1;

interface

type
	liste = ^cell;
	cell = record info:integer; suiv:liste; end;
	
function vide : liste;
function cons(i:integer; L:liste):liste;
function tete(L:liste):integer;
function reste(L:liste):liste;
function est_vide(L:liste):boolean;
procedure rend_mem(L:liste);

implementation

function vide;
	begin vide:=nil end;
	
function cons;
	var p : liste;
	begin
	new(p);
	p^.info := i;
	p^.suiv := L;
	cons := p;
	end;

function tete;
	begin tete:=L^.info end;
	
function reste;
	begin reste:=L^.suiv end;

function est_vide;
	begin est_vide:= (L=nil) end;
	
procedure rend_mem(L:liste);
	begin
	if not(est_vide(L)) then
		begin
		rend_mem(L^.suiv);
		dispose(L)
		end
	end;
end.

----------------------------------------------------------------------
% implantation à l'aide d'un tableau unique

unit liste2;

interface

type liste = integer;
	
procedure init_mem;
function vide : liste;
function cons(i:integer; L:liste):liste;
function tete(L:liste):integer;
function reste(L:liste):liste;
function est_vide(L:liste):boolean;

implementation

const max_mem=1000;

type 
	cell=record  info:integer; suiv : integer;  end;
var
	mem : array [0..max_mem] of cell;
	
procedure verif(c:boolean;msg:string);
	begin 
	if not(c) begin
		writeln(msg); halt;
	end; 
	end;

procedure init_mem;
	begin mem[0].info:=1 end;
	
function vide;
	begin vide:= -1 end;
	
function cons;
	var p : liste;
	begin
	p:=mem[0].info;
	verif(p Liste
	longueur		Liste 			-> Entier
	ieme 			Liste, Entier 		-> Elément		
	inserer  		Liste, Entier, Elément	-> Liste
	supprimer		Liste, Entier 		-> Liste

Hypothèse supplémentaire : 
il existe un entier MAX tel que, pour toutes les exécutions des
programmes utilisant ce modules, les listes sont de tailles
inférieures à MAX.

Implantation possible :

----------------------------------------------------------------------
	const	MAX = 100;

 	type
  		Element = integer;
 		Liste = record
    			nb_elts: integer;
    			tab: array[1..MAX] of Element;
   			end;

 procedure verif (c: boolean; msg: string);
 begin
 if not (c) then begin 
	writeln(msg);readln;halt;
 end;
 end;

 procedure liste_vide (var l: Liste);
 begin
 l.nb_elts := 0
 end;

 function longueur (var l: Liste): integer;
 begin
 longueur := l.nb_elts;
 end;

 function ieme (var l: Liste; i: integer): Element;
 begin
 verif((1 <= i) and (i <= l.nb_elts), 
	' ieme : indice inadequat');
 ieme := l.tab[i];
 end;

 procedure inserer (var l: Liste; ind: integer; 
							n: Element);
  var  i: integer;
 begin
 verif(l.nb_elts <= MAX, 'Liste pleine');
 verif((1 <= ind) and (ind <= l.nb_elts + 1), 
					'inserer : indice inadequat');
 for i := l.nb_elts downto ind do
	l.tab[i + 1] := l.tab[i];
 l.tab[ind] := n;
 l.nb_elts := l.nb_elts + 1;
 end;

 procedure supprimer (var l: Liste; ind: integer);
  var i: integer;
 begin
 verif((1 <= ind) and (ind <= l.nb_elts), 'supprimer : indice inadequat');
 for i := ind to l.nb_elts - 1 do
 	l.tab[i] := l.tab[i + 1];
 l.nb_elts := l.nb_elts - 1;
 end;


Définition des fonctions auxiliaires (style itératif, syntaxe Pascal) :

function rang (var l: Liste; e: integer): integer;
  var i: integer; test: boolean;
 begin
 test := false; i := 1;
 while (i <= longueur(l)) and not (test) do
	  if l.tab[i] = e then test := true
	  else i := i + 1;
 if test then rang := i
 else rang := 0
 end;

 procedure ajouter_fin (var l: Liste; e: Element);
 begin
 verif(l.nb_elts < MAX, 'ajouter_fin : liste pleine');
 l.tab[l.nb_elts + 1] := e;
 l.nb_elts := l.nb_elts + 1;
 end;

 procedure concatener (var l1, l2: Liste);
  var i: integer;
 begin
 verif(l1.nb_elts + l2.nb_elts <= MAX, 
				'concatener : listes trop grandes');
 for i := 1 to l2.nb_elts do
  	l1.tab[i + l1.nb_elts] := l2.tab[i];
 l1.nb_elts := l1.nb_elts + l2.nb_elts;
 end;

 procedure dupliquer (var l1, l2: liste);
 begin
 l2 := l1;
 end;

 procedure inverser (var l1: Liste);
  var i: integer; l: Liste;
 begin
 dupliquer(l1, l);
 for i := 1 to l1.nb_elts do
  l1.tab[i] := l.tab[l1.nb_elts - i + 1];
 end;

Sans hypothèse supplémentaire. On peut implanter les listes à l'aide des fichiers à accès direct. 
A défaut d'être efficace (quoique ...), c'est pédagogiquement défendable !

----------------------------------------------------------------------
 type
  Element = integer;
  Liste = record
    nb_elts: integer;
    nom: string;
    fich: file of Element;
   end;

 var compteur: integer;
 {variable globale pour generer des noms de fichier}

 procedure verif (c: boolean; msg: string);
 begin
  if not (c) then begin
   writeln(msg); readln; halt;
  end;
 end;

 procedure init;
 begin
  compteur := 0;
 end;

 procedure liste_vide (var l: Liste);
  function int_to_string (n: integer): string;
  begin
   if n = 0 then
    int_to_string := 'f'
   else
    int_to_string := concat(
		int_to_string(n div 10), 
		chr(n mod 10 + ord('0')))
  end;
 begin
  l.nb_elts := 0;
  l.nom := int_to_string(compteur);
  compteur := compteur + 1;
  rewrite(l.fich, l.nom);
  l.fich^ := 0;
  put(l.fich);
  close(l.fich);
 end;

 function longueur (var l: Liste): integer;
 begin
  longueur := l.nb_elts;
 end;

 function ieme (var l: Liste; i: integer): Element;
 begin
  verif((1 <= i) and (i <= l.nb_elts),
		 ' ieme : indice inadequat');
  open(l.fich, l.nom);
  seek(l.fich, i);
  ieme := l.fich^;
  close(l.fich);
 end;

 procedure inserer (var l: Liste; ind: integer; n: Element);
  var
   i,temp: integer;
 begin
  verif((1 <= ind) and (ind <= l.nb_elts + 1), 'inserer : indice inadequat');
  open(l.fich, l.nom);
  for i := l.nb_elts downto ind do begin
   seek(l.fich, i);
   temp := l.fich^;
   seek(l.fich, i + 1);
   l.fich^ := temp;
   put(l.fich);
  end;
  seek(l.fich, ind);
  l.fich^ := n;
  put(l.fich);
  close(l.fich);
  l.nb_elts := l.nb_elts + 1;
 end;

 procedure supprimer (var l: Liste; ind: integer);
  var
   temp, i: integer;
 begin
  verif((1 <= ind) and (ind <= l.nb_elts), 
					'supprimer : indice inadequat');
  open(l.fich, l.nom);
  for i := ind to l.nb_elts do begin
   seek(l.fich, i);
   temp := l.fich^;
   seek(l.fich, i - 1);
   l.fich^ := temp;
   put(l.fich);
  end;
  close(l.fich);
  l.nb_elts := l.nb_elts - 1;
 end;

 function rang (var l: Liste; e: integer): integer;
  var
   i: integer;
   test: boolean;
 begin
  test := false; i := 1;
  while (i <= longueur(l)) and not (test) do
   if ieme(l, i) = e then test := true
   else i := i + 1;
  if test then  rang := i
  else rang := 0
 end;

 procedure ajouter_fin (var l: Liste; e: Element);
 begin
  inserer(l, longueur(l) + 1, e)
 end;
procedure concatener (var l1, l2: Liste);
  var
   i: integer;
 begin
  for i := 1 to l2.nb_elts do
   ajouter_fin(l1, ieme(l2, i));
 end;

 procedure dupliquer (var l1, l2: liste);
  var
   i: integer;
 begin
  liste_vide(l2);
  for i := 1 to longueur(l1) do
   inserer(l2, i, ieme(l1, i));
 end;

 procedure inverser (var l1: Liste);
  var
   i: integer;
   l: Liste;
 begin
  dupliquer(l1, l);
  liste_vide(l1);
  for i := longueur(l) downto 1 do
   ajouter_fin(l1, ieme(l, i));
 end;

 procedure affiche (var L: liste);
  var
   i: integer;
 begin
  for i := 1 to longueur(L) do
   writeln(ieme(L, i));
 end;

 procedure entree_liste (var L: liste);
  var
   n: integer;
 begin
  writeln('Entrer une liste : ');
  readln(n);
  liste_vide(L);
  while n >= 0 do begin
   ajouter_fin(L, n);
   readln(n);
  end;
 end;